LLVM  8.0.0svn
InstCombineInternal.h
Go to the documentation of this file.
1 //===- InstCombineInternal.h - InstCombine pass internals -------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 /// \file
11 ///
12 /// This file provides internal interfaces used to implement the InstCombine.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
17 #define LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
18 
19 #include "llvm/ADT/ArrayRef.h"
25 #include "llvm/IR/Argument.h"
26 #include "llvm/IR/BasicBlock.h"
27 #include "llvm/IR/Constant.h"
28 #include "llvm/IR/Constants.h"
29 #include "llvm/IR/DerivedTypes.h"
30 #include "llvm/IR/IRBuilder.h"
31 #include "llvm/IR/InstVisitor.h"
32 #include "llvm/IR/InstrTypes.h"
33 #include "llvm/IR/Instruction.h"
34 #include "llvm/IR/IntrinsicInst.h"
35 #include "llvm/IR/Intrinsics.h"
36 #include "llvm/IR/Use.h"
37 #include "llvm/IR/Value.h"
38 #include "llvm/Support/Casting.h"
39 #include "llvm/Support/Compiler.h"
40 #include "llvm/Support/Debug.h"
41 #include "llvm/Support/KnownBits.h"
44 #include <cassert>
45 #include <cstdint>
46 
47 #define DEBUG_TYPE "instcombine"
48 
49 namespace llvm {
50 
51 class APInt;
52 class AssumptionCache;
53 class CallSite;
54 class DataLayout;
55 class DominatorTree;
56 class GEPOperator;
57 class GlobalVariable;
58 class LoopInfo;
59 class OptimizationRemarkEmitter;
60 class TargetLibraryInfo;
61 class User;
62 
63 /// Assign a complexity or rank value to LLVM Values. This is used to reduce
64 /// the amount of pattern matching needed for compares and commutative
65 /// instructions. For example, if we have:
66 /// icmp ugt X, Constant
67 /// or
68 /// xor (add X, Constant), cast Z
69 ///
70 /// We do not have to consider the commuted variants of these patterns because
71 /// canonicalization based on complexity guarantees the above ordering.
72 ///
73 /// This routine maps IR values to various complexity ranks:
74 /// 0 -> undef
75 /// 1 -> Constants
76 /// 2 -> Other non-instructions
77 /// 3 -> Arguments
78 /// 4 -> Cast and (f)neg/not instructions
79 /// 5 -> Other instructions
80 static inline unsigned getComplexity(Value *V) {
81  if (isa<Instruction>(V)) {
82  if (isa<CastInst>(V) || BinaryOperator::isNeg(V) ||
84  return 4;
85  return 5;
86  }
87  if (isa<Argument>(V))
88  return 3;
89  return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2;
90 }
91 
92 /// Predicate canonicalization reduces the number of patterns that need to be
93 /// matched by other transforms. For example, we may swap the operands of a
94 /// conditional branch or select to create a compare with a canonical (inverted)
95 /// predicate which is then more likely to be matched with other values.
96 static inline bool isCanonicalPredicate(CmpInst::Predicate Pred) {
97  switch (Pred) {
98  case CmpInst::ICMP_NE:
99  case CmpInst::ICMP_ULE:
100  case CmpInst::ICMP_SLE:
101  case CmpInst::ICMP_UGE:
102  case CmpInst::ICMP_SGE:
103  // TODO: There are 16 FCMP predicates. Should others be (not) canonical?
104  case CmpInst::FCMP_ONE:
105  case CmpInst::FCMP_OLE:
106  case CmpInst::FCMP_OGE:
107  return false;
108  default:
109  return true;
110  }
111 }
112 
113 /// Return the source operand of a potentially bitcasted value while optionally
114 /// checking if it has one use. If there is no bitcast or the one use check is
115 /// not met, return the input value itself.
116 static inline Value *peekThroughBitcast(Value *V, bool OneUseOnly = false) {
117  if (auto *BitCast = dyn_cast<BitCastInst>(V))
118  if (!OneUseOnly || BitCast->hasOneUse())
119  return BitCast->getOperand(0);
120 
121  // V is not a bitcast or V has more than one use and OneUseOnly is true.
122  return V;
123 }
124 
125 /// Add one to a Constant
126 static inline Constant *AddOne(Constant *C) {
127  return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
128 }
129 
130 /// Subtract one from a Constant
131 static inline Constant *SubOne(Constant *C) {
132  return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1));
133 }
134 
135 /// Return true if the specified value is free to invert (apply ~ to).
136 /// This happens in cases where the ~ can be eliminated. If WillInvertAllUses
137 /// is true, work under the assumption that the caller intends to remove all
138 /// uses of V and only keep uses of ~V.
139 static inline bool IsFreeToInvert(Value *V, bool WillInvertAllUses) {
140  // ~(~(X)) -> X.
141  if (BinaryOperator::isNot(V))
142  return true;
143 
144  // Constants can be considered to be not'ed values.
145  if (isa<ConstantInt>(V))
146  return true;
147 
148  // A vector of constant integers can be inverted easily.
149  if (V->getType()->isVectorTy() && isa<Constant>(V)) {
150  unsigned NumElts = V->getType()->getVectorNumElements();
151  for (unsigned i = 0; i != NumElts; ++i) {
152  Constant *Elt = cast<Constant>(V)->getAggregateElement(i);
153  if (!Elt)
154  return false;
155 
156  if (isa<UndefValue>(Elt))
157  continue;
158 
159  if (!isa<ConstantInt>(Elt))
160  return false;
161  }
162  return true;
163  }
164 
165  // Compares can be inverted if all of their uses are being modified to use the
166  // ~V.
167  if (isa<CmpInst>(V))
168  return WillInvertAllUses;
169 
170  // If `V` is of the form `A + Constant` then `-1 - V` can be folded into `(-1
171  // - Constant) - A` if we are willing to invert all of the uses.
172  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V))
173  if (BO->getOpcode() == Instruction::Add ||
174  BO->getOpcode() == Instruction::Sub)
175  if (isa<Constant>(BO->getOperand(0)) || isa<Constant>(BO->getOperand(1)))
176  return WillInvertAllUses;
177 
178  return false;
179 }
180 
181 /// Specific patterns of overflow check idioms that we match.
189 
191 };
192 
193 /// Returns the OverflowCheckFlavor corresponding to a overflow_with_op
194 /// intrinsic.
195 static inline OverflowCheckFlavor
197  switch (ID) {
198  default:
199  return OCF_INVALID;
200  case Intrinsic::uadd_with_overflow:
201  return OCF_UNSIGNED_ADD;
202  case Intrinsic::sadd_with_overflow:
203  return OCF_SIGNED_ADD;
204  case Intrinsic::usub_with_overflow:
205  return OCF_UNSIGNED_SUB;
206  case Intrinsic::ssub_with_overflow:
207  return OCF_SIGNED_SUB;
208  case Intrinsic::umul_with_overflow:
209  return OCF_UNSIGNED_MUL;
210  case Intrinsic::smul_with_overflow:
211  return OCF_SIGNED_MUL;
212  }
213 }
214 
215 /// Some binary operators require special handling to avoid poison and undefined
216 /// behavior. If a constant vector has undef elements, replace those undefs with
217 /// identity constants if possible because those are always safe to execute.
218 /// If no identity constant exists, replace undef with some other safe constant.
220  BinaryOperator::BinaryOps Opcode, Constant *In, bool IsRHSConstant) {
221  assert(In->getType()->isVectorTy() && "Not expecting scalars here");
222 
223  Type *EltTy = In->getType()->getVectorElementType();
224  auto *SafeC = ConstantExpr::getBinOpIdentity(Opcode, EltTy, IsRHSConstant);
225  if (!SafeC) {
226  // TODO: Should this be available as a constant utility function? It is
227  // similar to getBinOpAbsorber().
228  if (IsRHSConstant) {
229  switch (Opcode) {
230  case Instruction::SRem: // X % 1 = 0
231  case Instruction::URem: // X %u 1 = 0
232  SafeC = ConstantInt::get(EltTy, 1);
233  break;
234  case Instruction::FRem: // X % 1.0 (doesn't simplify, but it is safe)
235  SafeC = ConstantFP::get(EltTy, 1.0);
236  break;
237  default:
238  llvm_unreachable("Only rem opcodes have no identity constant for RHS");
239  }
240  } else {
241  switch (Opcode) {
242  case Instruction::Shl: // 0 << X = 0
243  case Instruction::LShr: // 0 >>u X = 0
244  case Instruction::AShr: // 0 >> X = 0
245  case Instruction::SDiv: // 0 / X = 0
246  case Instruction::UDiv: // 0 /u X = 0
247  case Instruction::SRem: // 0 % X = 0
248  case Instruction::URem: // 0 %u X = 0
249  case Instruction::Sub: // 0 - X (doesn't simplify, but it is safe)
250  case Instruction::FSub: // 0.0 - X (doesn't simplify, but it is safe)
251  case Instruction::FDiv: // 0.0 / X (doesn't simplify, but it is safe)
252  case Instruction::FRem: // 0.0 % X = 0
253  SafeC = Constant::getNullValue(EltTy);
254  break;
255  default:
256  llvm_unreachable("Expected to find identity constant for opcode");
257  }
258  }
259  }
260  assert(SafeC && "Must have safe constant for binop");
261  unsigned NumElts = In->getType()->getVectorNumElements();
262  SmallVector<Constant *, 16> Out(NumElts);
263  for (unsigned i = 0; i != NumElts; ++i) {
264  Constant *C = In->getAggregateElement(i);
265  Out[i] = isa<UndefValue>(C) ? SafeC : C;
266  }
267  return ConstantVector::get(Out);
268 }
269 
270 /// The core instruction combiner logic.
271 ///
272 /// This class provides both the logic to recursively visit instructions and
273 /// combine them.
275  : public InstVisitor<InstCombiner, Instruction *> {
276  // FIXME: These members shouldn't be public.
277 public:
278  /// A worklist of the instructions that need to be simplified.
280 
281  /// An IRBuilder that automatically inserts new instructions into the
282  /// worklist.
285 
286 private:
287  // Mode in which we are running the combiner.
288  const bool MinimizeSize;
289 
290  /// Enable combines that trigger rarely but are costly in compiletime.
291  const bool ExpensiveCombines;
292 
293  AliasAnalysis *AA;
294 
295  // Required analyses.
296  AssumptionCache &AC;
297  TargetLibraryInfo &TLI;
298  DominatorTree &DT;
299  const DataLayout &DL;
300  const SimplifyQuery SQ;
302 
303  // Optional analyses. When non-null, these can both be used to do better
304  // combining and will be updated to reflect any changes.
305  LoopInfo *LI;
306 
307  bool MadeIRChange = false;
308 
309 public:
311  bool MinimizeSize, bool ExpensiveCombines, AliasAnalysis *AA,
313  OptimizationRemarkEmitter &ORE, const DataLayout &DL,
314  LoopInfo *LI)
315  : Worklist(Worklist), Builder(Builder), MinimizeSize(MinimizeSize),
316  ExpensiveCombines(ExpensiveCombines), AA(AA), AC(AC), TLI(TLI), DT(DT),
317  DL(DL), SQ(DL, &TLI, &DT, &AC), ORE(ORE), LI(LI) {}
318 
319  /// Run the combiner over the entire worklist until it is empty.
320  ///
321  /// \returns true if the IR is changed.
322  bool run();
323 
324  AssumptionCache &getAssumptionCache() const { return AC; }
325 
326  const DataLayout &getDataLayout() const { return DL; }
327 
328  DominatorTree &getDominatorTree() const { return DT; }
329 
330  LoopInfo *getLoopInfo() const { return LI; }
331 
332  TargetLibraryInfo &getTargetLibraryInfo() const { return TLI; }
333 
334  // Visitation implementation - Implement instruction combining for different
335  // instruction types. The semantics are as follows:
336  // Return Value:
337  // null - No change was made
338  // I - Change was made, I is still valid, I may be dead though
339  // otherwise - Change was made, replace I with returned instruction
340  //
341  Instruction *visitAdd(BinaryOperator &I);
342  Instruction *visitFAdd(BinaryOperator &I);
343  Value *OptimizePointerDifference(Value *LHS, Value *RHS, Type *Ty);
344  Instruction *visitSub(BinaryOperator &I);
345  Instruction *visitFSub(BinaryOperator &I);
346  Instruction *visitMul(BinaryOperator &I);
347  Instruction *visitFMul(BinaryOperator &I);
348  Instruction *visitURem(BinaryOperator &I);
349  Instruction *visitSRem(BinaryOperator &I);
350  Instruction *visitFRem(BinaryOperator &I);
351  bool simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I);
352  Instruction *commonRemTransforms(BinaryOperator &I);
353  Instruction *commonIRemTransforms(BinaryOperator &I);
354  Instruction *commonDivTransforms(BinaryOperator &I);
355  Instruction *commonIDivTransforms(BinaryOperator &I);
356  Instruction *visitUDiv(BinaryOperator &I);
357  Instruction *visitSDiv(BinaryOperator &I);
358  Instruction *visitFDiv(BinaryOperator &I);
359  Value *simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted);
360  Instruction *visitAnd(BinaryOperator &I);
361  Instruction *visitOr(BinaryOperator &I);
362  Instruction *visitXor(BinaryOperator &I);
363  Instruction *visitShl(BinaryOperator &I);
364  Instruction *visitAShr(BinaryOperator &I);
365  Instruction *visitLShr(BinaryOperator &I);
366  Instruction *commonShiftTransforms(BinaryOperator &I);
367  Instruction *visitFCmpInst(FCmpInst &I);
368  Instruction *visitICmpInst(ICmpInst &I);
369  Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
370  BinaryOperator &I);
371  Instruction *commonCastTransforms(CastInst &CI);
372  Instruction *commonPointerCastTransforms(CastInst &CI);
373  Instruction *visitTrunc(TruncInst &CI);
374  Instruction *visitZExt(ZExtInst &CI);
375  Instruction *visitSExt(SExtInst &CI);
376  Instruction *visitFPTrunc(FPTruncInst &CI);
377  Instruction *visitFPExt(CastInst &CI);
378  Instruction *visitFPToUI(FPToUIInst &FI);
379  Instruction *visitFPToSI(FPToSIInst &FI);
380  Instruction *visitUIToFP(CastInst &CI);
381  Instruction *visitSIToFP(CastInst &CI);
382  Instruction *visitPtrToInt(PtrToIntInst &CI);
383  Instruction *visitIntToPtr(IntToPtrInst &CI);
384  Instruction *visitBitCast(BitCastInst &CI);
385  Instruction *visitAddrSpaceCast(AddrSpaceCastInst &CI);
386  Instruction *FoldItoFPtoI(Instruction &FI);
387  Instruction *visitSelectInst(SelectInst &SI);
388  Instruction *visitCallInst(CallInst &CI);
389  Instruction *visitInvokeInst(InvokeInst &II);
390 
391  Instruction *SliceUpIllegalIntegerPHI(PHINode &PN);
392  Instruction *visitPHINode(PHINode &PN);
393  Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
394  Instruction *visitAllocaInst(AllocaInst &AI);
395  Instruction *visitAllocSite(Instruction &FI);
396  Instruction *visitFree(CallInst &FI);
397  Instruction *visitLoadInst(LoadInst &LI);
398  Instruction *visitStoreInst(StoreInst &SI);
399  Instruction *visitBranchInst(BranchInst &BI);
400  Instruction *visitFenceInst(FenceInst &FI);
401  Instruction *visitSwitchInst(SwitchInst &SI);
402  Instruction *visitReturnInst(ReturnInst &RI);
403  Instruction *visitInsertValueInst(InsertValueInst &IV);
404  Instruction *visitInsertElementInst(InsertElementInst &IE);
405  Instruction *visitExtractElementInst(ExtractElementInst &EI);
406  Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
407  Instruction *visitExtractValueInst(ExtractValueInst &EV);
408  Instruction *visitLandingPadInst(LandingPadInst &LI);
409  Instruction *visitVAStartInst(VAStartInst &I);
410  Instruction *visitVACopyInst(VACopyInst &I);
411 
412  /// Specify what to return for unhandled instructions.
413  Instruction *visitInstruction(Instruction &I) { return nullptr; }
414 
415  /// True when DB dominates all uses of DI except UI.
416  /// UI must be in the same block as DI.
417  /// The routine checks that the DI parent and DB are different.
418  bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
419  const BasicBlock *DB) const;
420 
421  /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
422  bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
423  const unsigned SIOpd);
424 
425  /// Try to replace instruction \p I with value \p V which are pointers
426  /// in different address space.
427  /// \return true if successful.
428  bool replacePointer(Instruction &I, Value *V);
429 
430 private:
431  bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
432  bool shouldChangeType(Type *From, Type *To) const;
433  Value *dyn_castNegVal(Value *V) const;
434  Type *FindElementAtOffset(PointerType *PtrTy, int64_t Offset,
435  SmallVectorImpl<Value *> &NewIndices);
436 
437  /// Classify whether a cast is worth optimizing.
438  ///
439  /// This is a helper to decide whether the simplification of
440  /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
441  ///
442  /// \param CI The cast we are interested in.
443  ///
444  /// \return true if this cast actually results in any code being generated and
445  /// if it cannot already be eliminated by some other transformation.
446  bool shouldOptimizeCast(CastInst *CI);
447 
448  /// Try to optimize a sequence of instructions checking if an operation
449  /// on LHS and RHS overflows.
450  ///
451  /// If this overflow check is done via one of the overflow check intrinsics,
452  /// then CtxI has to be the call instruction calling that intrinsic. If this
453  /// overflow check is done by arithmetic followed by a compare, then CtxI has
454  /// to be the arithmetic instruction.
455  ///
456  /// If a simplification is possible, stores the simplified result of the
457  /// operation in OperationResult and result of the overflow check in
458  /// OverflowResult, and return true. If no simplification is possible,
459  /// returns false.
460  bool OptimizeOverflowCheck(OverflowCheckFlavor OCF, Value *LHS, Value *RHS,
461  Instruction &CtxI, Value *&OperationResult,
463 
464  Instruction *visitCallSite(CallSite CS);
465  Instruction *tryOptimizeCall(CallInst *CI);
466  bool transformConstExprCastCall(CallSite CS);
467  Instruction *transformCallThroughTrampoline(CallSite CS,
468  IntrinsicInst *Tramp);
469 
470  /// Transform (zext icmp) to bitwise / integer operations in order to
471  /// eliminate it.
472  ///
473  /// \param ICI The icmp of the (zext icmp) pair we are interested in.
474  /// \parem CI The zext of the (zext icmp) pair we are interested in.
475  /// \param DoTransform Pass false to just test whether the given (zext icmp)
476  /// would be transformed. Pass true to actually perform the transformation.
477  ///
478  /// \return null if the transformation cannot be performed. If the
479  /// transformation can be performed the new instruction that replaces the
480  /// (zext icmp) pair will be returned (if \p DoTransform is false the
481  /// unmodified \p ICI will be returned in this case).
482  Instruction *transformZExtICmp(ICmpInst *ICI, ZExtInst &CI,
483  bool DoTransform = true);
484 
485  Instruction *transformSExtICmp(ICmpInst *ICI, Instruction &CI);
486 
487  bool willNotOverflowSignedAdd(const Value *LHS, const Value *RHS,
488  const Instruction &CxtI) const {
489  return computeOverflowForSignedAdd(LHS, RHS, &CxtI) ==
491  }
492 
493  bool willNotOverflowUnsignedAdd(const Value *LHS, const Value *RHS,
494  const Instruction &CxtI) const {
495  return computeOverflowForUnsignedAdd(LHS, RHS, &CxtI) ==
497  }
498 
499  bool willNotOverflowAdd(const Value *LHS, const Value *RHS,
500  const Instruction &CxtI, bool IsSigned) const {
501  return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CxtI)
502  : willNotOverflowUnsignedAdd(LHS, RHS, CxtI);
503  }
504 
505  bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
506  const Instruction &CxtI) const {
507  return computeOverflowForSignedSub(LHS, RHS, &CxtI) ==
509  }
510 
511  bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
512  const Instruction &CxtI) const {
513  return computeOverflowForUnsignedSub(LHS, RHS, &CxtI) ==
515  }
516 
517  bool willNotOverflowSub(const Value *LHS, const Value *RHS,
518  const Instruction &CxtI, bool IsSigned) const {
519  return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CxtI)
520  : willNotOverflowUnsignedSub(LHS, RHS, CxtI);
521  }
522 
523  bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
524  const Instruction &CxtI) const {
525  return computeOverflowForSignedMul(LHS, RHS, &CxtI) ==
527  }
528 
529  bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
530  const Instruction &CxtI) const {
531  return computeOverflowForUnsignedMul(LHS, RHS, &CxtI) ==
533  }
534 
535  bool willNotOverflowMul(const Value *LHS, const Value *RHS,
536  const Instruction &CxtI, bool IsSigned) const {
537  return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CxtI)
538  : willNotOverflowUnsignedMul(LHS, RHS, CxtI);
539  }
540 
541  bool willNotOverflow(BinaryOperator::BinaryOps Opcode, const Value *LHS,
542  const Value *RHS, const Instruction &CxtI,
543  bool IsSigned) const {
544  switch (Opcode) {
545  case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CxtI, IsSigned);
546  case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CxtI, IsSigned);
547  case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CxtI, IsSigned);
548  default: llvm_unreachable("Unexpected opcode for overflow query");
549  }
550  }
551 
552  Value *EmitGEPOffset(User *GEP);
553  Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
554  Value *EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask);
555  Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
556  Instruction *narrowBinOp(TruncInst &Trunc);
557  Instruction *narrowMaskedBinOp(BinaryOperator &And);
558  Instruction *narrowMathIfNoOverflow(BinaryOperator &I);
559  Instruction *narrowRotate(TruncInst &Trunc);
560  Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
561 
562  /// Determine if a pair of casts can be replaced by a single cast.
563  ///
564  /// \param CI1 The first of a pair of casts.
565  /// \param CI2 The second of a pair of casts.
566  ///
567  /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
568  /// Instruction::CastOps value for a cast that can replace the pair, casting
569  /// CI1->getSrcTy() to CI2->getDstTy().
570  ///
571  /// \see CastInst::isEliminableCastPair
572  Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
573  const CastInst *CI2);
574 
575  Value *foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &CxtI);
576  Value *foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &CxtI);
577  Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS);
578 
579  /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
580  /// NOTE: Unlike most of instcombine, this returns a Value which should
581  /// already be inserted into the function.
582  Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd);
583 
584  Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
585  bool JoinedByAnd, Instruction &CxtI);
586 public:
587  /// Inserts an instruction \p New before instruction \p Old
588  ///
589  /// Also adds the new instruction to the worklist and returns \p New so that
590  /// it is suitable for use as the return from the visitation patterns.
592  assert(New && !New->getParent() &&
593  "New instruction already inserted into a basic block!");
594  BasicBlock *BB = Old.getParent();
595  BB->getInstList().insert(Old.getIterator(), New); // Insert inst
596  Worklist.Add(New);
597  return New;
598  }
599 
600  /// Same as InsertNewInstBefore, but also sets the debug loc.
602  New->setDebugLoc(Old.getDebugLoc());
603  return InsertNewInstBefore(New, Old);
604  }
605 
606  /// A combiner-aware RAUW-like routine.
607  ///
608  /// This method is to be used when an instruction is found to be dead,
609  /// replaceable with another preexisting expression. Here we add all uses of
610  /// I to the worklist, replace all uses of I with the new value, then return
611  /// I, so that the inst combiner will know that I was modified.
613  // If there are no uses to replace, then we return nullptr to indicate that
614  // no changes were made to the program.
615  if (I.use_empty()) return nullptr;
616 
617  Worklist.AddUsersToWorkList(I); // Add all modified instrs to worklist.
618 
619  // If we are replacing the instruction with itself, this must be in a
620  // segment of unreachable code, so just clobber the instruction.
621  if (&I == V)
622  V = UndefValue::get(I.getType());
623 
624  LLVM_DEBUG(dbgs() << "IC: Replacing " << I << "\n"
625  << " with " << *V << '\n');
626 
627  I.replaceAllUsesWith(V);
628  return &I;
629  }
630 
631  /// Creates a result tuple for an overflow intrinsic \p II with a given
632  /// \p Result and a constant \p Overflow value.
634  Constant *Overflow) {
635  Constant *V[] = {UndefValue::get(Result->getType()), Overflow};
636  StructType *ST = cast<StructType>(II->getType());
637  Constant *Struct = ConstantStruct::get(ST, V);
638  return InsertValueInst::Create(Struct, Result, 0);
639  }
640 
641  /// Combiner aware instruction erasure.
642  ///
643  /// When dealing with an instruction that has side effects or produces a void
644  /// value, we can't rely on DCE to delete the instruction. Instead, visit
645  /// methods should return the value returned by this function.
647  LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n');
648  assert(I.use_empty() && "Cannot erase instruction that is used!");
649  salvageDebugInfo(I);
650 
651  // Make sure that we reprocess all operands now that we reduced their
652  // use counts.
653  if (I.getNumOperands() < 8) {
654  for (Use &Operand : I.operands())
655  if (auto *Inst = dyn_cast<Instruction>(Operand))
656  Worklist.Add(Inst);
657  }
658  Worklist.Remove(&I);
659  I.eraseFromParent();
660  MadeIRChange = true;
661  return nullptr; // Don't do anything with FI
662  }
663 
664  void computeKnownBits(const Value *V, KnownBits &Known,
665  unsigned Depth, const Instruction *CxtI) const {
666  llvm::computeKnownBits(V, Known, DL, Depth, &AC, CxtI, &DT);
667  }
668 
669  KnownBits computeKnownBits(const Value *V, unsigned Depth,
670  const Instruction *CxtI) const {
671  return llvm::computeKnownBits(V, DL, Depth, &AC, CxtI, &DT);
672  }
673 
674  bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero = false,
675  unsigned Depth = 0,
676  const Instruction *CxtI = nullptr) {
677  return llvm::isKnownToBeAPowerOfTwo(V, DL, OrZero, Depth, &AC, CxtI, &DT);
678  }
679 
680  bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth = 0,
681  const Instruction *CxtI = nullptr) const {
682  return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT);
683  }
684 
685  unsigned ComputeNumSignBits(const Value *Op, unsigned Depth = 0,
686  const Instruction *CxtI = nullptr) const {
687  return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
688  }
689 
690  OverflowResult computeOverflowForUnsignedMul(const Value *LHS,
691  const Value *RHS,
692  const Instruction *CxtI) const {
693  return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
694  }
695 
696  OverflowResult computeOverflowForSignedMul(const Value *LHS,
697  const Value *RHS,
698  const Instruction *CxtI) const {
699  return llvm::computeOverflowForSignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
700  }
701 
702  OverflowResult computeOverflowForUnsignedAdd(const Value *LHS,
703  const Value *RHS,
704  const Instruction *CxtI) const {
705  return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
706  }
707 
708  OverflowResult computeOverflowForSignedAdd(const Value *LHS,
709  const Value *RHS,
710  const Instruction *CxtI) const {
711  return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
712  }
713 
714  OverflowResult computeOverflowForUnsignedSub(const Value *LHS,
715  const Value *RHS,
716  const Instruction *CxtI) const {
717  return llvm::computeOverflowForUnsignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
718  }
719 
720  OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS,
721  const Instruction *CxtI) const {
722  return llvm::computeOverflowForSignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
723  }
724 
725  /// Maximum size of array considered when transforming.
727 
728 private:
729  /// Performs a few simplifications for operators which are associative
730  /// or commutative.
731  bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
732 
733  /// Tries to simplify binary operations which some other binary
734  /// operation distributes over.
735  ///
736  /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
737  /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
738  /// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified
739  /// value, or null if it didn't simplify.
740  Value *SimplifyUsingDistributiveLaws(BinaryOperator &I);
741 
742  /// Tries to simplify add operations using the definition of remainder.
743  ///
744  /// The definition of remainder is X % C = X - (X / C ) * C. The add
745  /// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to
746  /// X % (C0 * C1)
747  Value *SimplifyAddWithRemainder(BinaryOperator &I);
748 
749  // Binary Op helper for select operations where the expression can be
750  // efficiently reorganized.
751  Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
752  Value *RHS);
753 
754  /// This tries to simplify binary operations by factorizing out common terms
755  /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
756  Value *tryFactorization(BinaryOperator &, Instruction::BinaryOps, Value *,
757  Value *, Value *, Value *);
758 
759  /// Match a select chain which produces one of three values based on whether
760  /// the LHS is less than, equal to, or greater than RHS respectively.
761  /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
762  /// Equal and Greater values are saved in the matching process and returned to
763  /// the caller.
764  bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
766  ConstantInt *&Greater);
767 
768  /// Attempts to replace V with a simpler value based on the demanded
769  /// bits.
770  Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known,
771  unsigned Depth, Instruction *CxtI);
772  bool SimplifyDemandedBits(Instruction *I, unsigned Op,
773  const APInt &DemandedMask, KnownBits &Known,
774  unsigned Depth = 0);
775 
776  /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
777  /// bits. It also tries to handle simplifications that can be done based on
778  /// DemandedMask, but without modifying the Instruction.
779  Value *SimplifyMultipleUseDemandedBits(Instruction *I,
780  const APInt &DemandedMask,
781  KnownBits &Known,
782  unsigned Depth, Instruction *CxtI);
783 
784  /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
785  /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
786  Value *simplifyShrShlDemandedBits(
787  Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
788  const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
789 
790  /// Tries to simplify operands to an integer instruction based on its
791  /// demanded bits.
792  bool SimplifyDemandedInstructionBits(Instruction &Inst);
793 
794  Value *simplifyAMDGCNMemoryIntrinsicDemanded(IntrinsicInst *II,
795  APInt DemandedElts,
796  int DmaskIdx = -1);
797 
798  Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
799  APInt &UndefElts, unsigned Depth = 0);
800 
801  /// Canonicalize the position of binops relative to shufflevector.
802  Instruction *foldShuffledBinop(BinaryOperator &Inst);
803 
804  /// Given a binary operator, cast instruction, or select which has a PHI node
805  /// as operand #0, see if we can fold the instruction into the PHI (which is
806  /// only possible if all operands to the PHI are constants).
807  Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN);
808 
809  /// Given an instruction with a select as one operand and a constant as the
810  /// other operand, try to fold the binary operator into the select arguments.
811  /// This also works for Cast instructions, which obviously do not have a
812  /// second operand.
813  Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI);
814 
815  /// This is a convenience wrapper function for the above two functions.
816  Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
817 
818  Instruction *foldAddWithConstant(BinaryOperator &Add);
819 
820  /// Try to rotate an operation below a PHI node, using PHI nodes for
821  /// its operands.
822  Instruction *FoldPHIArgOpIntoPHI(PHINode &PN);
823  Instruction *FoldPHIArgBinOpIntoPHI(PHINode &PN);
824  Instruction *FoldPHIArgGEPIntoPHI(PHINode &PN);
825  Instruction *FoldPHIArgLoadIntoPHI(PHINode &PN);
826  Instruction *FoldPHIArgZextsIntoPHI(PHINode &PN);
827 
828  /// If an integer typed PHI has only one use which is an IntToPtr operation,
829  /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
830  /// insert a new pointer typed PHI and replace the original one.
831  Instruction *FoldIntegerTypedPHI(PHINode &PN);
832 
833  /// Helper function for FoldPHIArgXIntoPHI() to set debug location for the
834  /// folded operation.
835  void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN);
836 
837  Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
839  Instruction *foldAllocaCmp(ICmpInst &ICI, const AllocaInst *Alloca,
840  const Value *Other);
841  Instruction *foldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP,
842  GlobalVariable *GV, CmpInst &ICI,
843  ConstantInt *AndCst = nullptr);
844  Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
845  Constant *RHSC);
846  Instruction *foldICmpAddOpConst(Value *X, const APInt &C,
847  ICmpInst::Predicate Pred);
848  Instruction *foldICmpWithCastAndCast(ICmpInst &ICI);
849 
850  Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
851  Instruction *foldICmpWithConstant(ICmpInst &Cmp);
852  Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
853  Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
854  Instruction *foldICmpBinOp(ICmpInst &Cmp);
855  Instruction *foldICmpEquality(ICmpInst &Cmp);
856  Instruction *foldICmpWithZero(ICmpInst &Cmp);
857 
858  Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,
859  ConstantInt *C);
860  Instruction *foldICmpBitCastConstant(ICmpInst &Cmp, BitCastInst *Bitcast,
861  const APInt &C);
862  Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc,
863  const APInt &C);
864  Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
865  const APInt &C);
866  Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
867  const APInt &C);
868  Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
869  const APInt &C);
870  Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
871  const APInt &C);
872  Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
873  const APInt &C);
874  Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
875  const APInt &C);
876  Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
877  const APInt &C);
878  Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
879  const APInt &C);
880  Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
881  const APInt &C);
882  Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
883  const APInt &C);
884  Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
885  const APInt &C1);
886  Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
887  const APInt &C1, const APInt &C2);
888  Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
889  const APInt &C2);
890  Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
891  const APInt &C2);
892 
893  Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
894  BinaryOperator *BO,
895  const APInt &C);
896  Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, const APInt &C);
897 
898  // Helpers of visitSelectInst().
899  Instruction *foldSelectExtConst(SelectInst &Sel);
900  Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
901  Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
902  Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1,
903  Value *A, Value *B, Instruction &Outer,
904  SelectPatternFlavor SPF2, Value *C);
905  Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI);
906 
907  Instruction *OptAndOp(BinaryOperator *Op, ConstantInt *OpRHS,
908  ConstantInt *AndRHS, BinaryOperator &TheAnd);
909 
910  Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
911  bool isSigned, bool Inside);
912  Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI);
913  Instruction *MatchBSwap(BinaryOperator &I);
914  bool SimplifyStoreAtEndOfBlock(StoreInst &SI);
915 
916  Instruction *SimplifyAnyMemTransfer(AnyMemTransferInst *MI);
917  Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI);
918 
919  Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
920 
921  /// Returns a value X such that Val = X * Scale, or null if none.
922  ///
923  /// If the multiplication is known not to overflow then NoSignedWrap is set.
924  Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
925 };
926 
927 } // end namespace llvm
928 
929 #undef DEBUG_TYPE
930 
931 #endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
Type * getVectorElementType() const
Definition: Type.h:371
Value * EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &DL, User *GEP, bool NoAssumptions=false)
Given a getelementptr instruction/constantexpr, emit the code necessary to compute the offset from th...
Definition: Local.h:29
uint64_t CallInst * C
Return a value (possibly void), from a function.
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:68
Instruction * InsertNewInstWith(Instruction *New, Instruction &Old)
Same as InsertNewInstBefore, but also sets the debug loc.
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:675
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool IsFreeToInvert(Value *V, bool WillInvertAllUses)
Return true if the specified value is free to invert (apply ~ to).
This instruction extracts a struct member or array element value from an aggregate value...
Base class for instruction visitors.
Definition: InstVisitor.h:81
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
An instruction for ordering other memory operations.
Definition: Instructions.h:444
This class represents zero extension of integer types.
This class represents a function call, abstracting a target machine&#39;s calling convention.
static bool isCanonicalPredicate(CmpInst::Predicate Pred)
Predicate canonicalization reduces the number of patterns that need to be matched by other transforms...
unsigned less or equal
Definition: InstrTypes.h:711
void Remove(Instruction *I)
A cache of @llvm.assume calls within a function.
bool salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage debug users of I by writing the...
Definition: Local.cpp:1609
This instruction constructs a fixed permutation of two input vectors.
void Add(Instruction *I)
Add - Add the specified instruction to the worklist if it isn&#39;t already in it.
This class represents a sign extension of integer types.
An instruction for reading from memory.
Definition: Instructions.h:168
uint64_t MaxArraySizeForCombine
Maximum size of array considered when transforming.
Hexagon Common GEP
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2197
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:230
static OverflowCheckFlavor IntrinsicIDToOverflowCheckFlavor(unsigned ID)
Returns the OverflowCheckFlavor corresponding to a overflow_with_op intrinsic.
static bool willNotOverflow(IntrinsicInst *II, LazyValueInfo *LVI)
This defines the Use class.
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:268
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2186
This class represents a conversion between pointers from one address space to another.
static unsigned getComplexity(Value *V)
Assign a complexity or rank value to LLVM Values.
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL, bool OrZero=false, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to have exactly one bit set when defined. ...
This class represents the LLVM &#39;select&#39; instruction.
OverflowCheckFlavor
Specific patterns of overflow check idioms that we match.
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:392
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Class to represent struct types.
Definition: DerivedTypes.h:201
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
Instruction * eraseInstFromFunction(Instruction &I)
Combiner aware instruction erasure.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:731
The core instruction combiner logic.
static Constant * AddOne(Constant *C)
Add one to a Constant.
0 1 0 1 True if ordered and less than or equal
Definition: InstrTypes.h:692
bool MaskedValueIsZero(const Value *V, const APInt &Mask, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if &#39;V & Mask&#39; is known to be zero.
This class represents a cast from a pointer to an integer.
DominatorTree & getDominatorTree() const
static Value * peekThroughBitcast(Value *V, bool OneUseOnly=false)
Return the source operand of a potentially bitcasted value while optionally checking if it has one us...
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
This represents the llvm.va_start intrinsic.
static Constant * getSafeVectorConstantForBinop(BinaryOperator::BinaryOps Opcode, Constant *In, bool IsRHSConstant)
Some binary operators require special handling to avoid poison and undefined behavior.
This instruction compares its operands according to the predicate given to the constructor.
This class represents a no-op cast from one type to another.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
An instruction for storing to memory.
Definition: Instructions.h:310
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
Instruction * visitInstruction(Instruction &I)
Specify what to return for unhandled instructions.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:439
This class represents a cast from floating point to signed integer.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
This class represents a truncation of integer types.
Class to represent pointers.
Definition: DerivedTypes.h:467
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:338
const DataLayout & getDataLayout() const
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:841
unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return the number of times the sign bit of the register is replicated into the other bits...
This instruction inserts a single (scalar) element into a VectorType value.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:304
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
void AddUsersToWorkList(Instruction &I)
AddUsersToWorkList - When an instruction is simplified, add all users of the instruction to the work ...
Conditional or Unconditional Branch instruction.
This is an important base class in LLVM.
Definition: Constant.h:42
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero=false, unsigned Depth=0, const Instruction *CxtI=nullptr)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
InstCombiner(InstCombineWorklist &Worklist, BuilderTy &Builder, bool MinimizeSize, bool ExpensiveCombines, AliasAnalysis *AA, AssumptionCache &AC, TargetLibraryInfo &TLI, DominatorTree &DT, OptimizationRemarkEmitter &ORE, const DataLayout &DL, LoopInfo *LI)
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:685
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false)
Return the identity constant for a binary opcode.
Definition: Constants.cpp:2274
This class represents any memset intrinsic.
Instruction * CreateOverflowTuple(IntrinsicInst *II, Value *Result, Constant *Overflow)
Creates a result tuple for an overflow intrinsic II with a given Result and a constant Overflow value...
static Constant * get(StructType *T, ArrayRef< Constant *> V)
Definition: Constants.cpp:1021
op_range operands()
Definition: User.h:238
static bool isNot(const Value *V)
self_iterator getIterator()
Definition: ilist_node.h:82
This class represents a cast from an integer to a pointer.
InstCombineWorklist - This is the worklist management logic for InstCombine.
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1392
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
TargetLibraryInfo & getTargetLibraryInfo() const
InstCombineWorklist & Worklist
A worklist of the instructions that need to be simplified.
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:329
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
unsigned getNumOperands() const
Definition: User.h:192
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
BlockVerifier::State From
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
SelectPatternFlavor
Specific patterns of select instructions we can match.
Provides information about what library functions are available for the current target.
unsigned ComputeNumSignBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
This class represents a cast from floating point to unsigned integer.
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:621
static Constant * get(Type *Ty, double V)
This returns a ConstantFP, or a vector containing a splat of a ConstantFP, for the specified value in...
Definition: Constants.cpp:684
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
unsigned getVectorNumElements() const
Definition: DerivedTypes.h:462
signed less or equal
Definition: InstrTypes.h:715
static bool isNeg(const Value *V)
Check if the given Value is a NEG, FNeg, or NOT instruction.
Class for arbitrary precision integers.
Definition: APInt.h:70
LoopInfo * getLoopInfo() const
bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth=0, const Instruction *CxtI=nullptr) const
iterator insert(iterator where, pointer New)
Definition: ilist.h:228
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:307
OverflowResult
unsigned greater or equal
Definition: InstrTypes.h:709
KnownBits computeKnownBits(const Value *V, unsigned Depth, const Instruction *CxtI) const
static bool isFNeg(const Value *V, bool IgnoreZeroSign=false)
static InsertValueInst * Create(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
#define I(x, y, z)
Definition: MD5.cpp:58
0 1 1 0 True if ordered and operands are unequal
Definition: InstrTypes.h:693
This instruction extracts a single (scalar) element from a VectorType value.
Instruction * InsertNewInstBefore(Instruction *New, Instruction &Old)
Inserts an instruction New before instruction Old.
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library...
Definition: Compiler.h:108
AssumptionCache & getAssumptionCache() const
Multiway switch.
This represents the llvm.va_copy intrinsic.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
This class represents a truncation of floating point types.
LLVM Value Representation.
Definition: Value.h:73
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:81
Invoke instruction.
IRTranslator LLVM IR MI
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
#define LLVM_DEBUG(X)
Definition: Debug.h:123
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:690
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
The optimization diagnostic interface.
bool use_empty() const
Definition: Value.h:323
static Constant * get(ArrayRef< Constant *> V)
Definition: Constants.cpp:1056
static Constant * SubOne(Constant *C)
Subtract one from a Constant.
signed greater or equal
Definition: InstrTypes.h:713
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
const BasicBlock * getParent() const
Definition: Instruction.h:67
an instruction to allocate memory on the stack
Definition: Instructions.h:60
This instruction inserts a struct field of array element value into an aggregate value.