contrib/llvm/lib/Transforms/InstCombine/InstCombineInternal.h

   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 /// \file
  10 ///
  11 /// This file provides internal interfaces used to implement the InstCombine.
  12 ///
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
  16 #define LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
  17
  18 #include "llvm/Analysis/AliasAnalysis.h"
  19 #include "llvm/Analysis/AssumptionCache.h"
  20 #include "llvm/Analysis/InstructionSimplify.h"
  21 #include "llvm/Analysis/LoopInfo.h"
  22 #include "llvm/Analysis/TargetFolder.h"
  23 #include "llvm/Analysis/ValueTracking.h"
  24 #include "llvm/IR/DIBuilder.h"
  25 #include "llvm/IR/Dominators.h"
  26 #include "llvm/IR/IRBuilder.h"
  27 #include "llvm/IR/InstVisitor.h"
  28 #include "llvm/IR/IntrinsicInst.h"
  29 #include "llvm/IR/Operator.h"
  30 #include "llvm/IR/PatternMatch.h"
  31 #include "llvm/Pass.h"
  32 #include "llvm/Support/Dwarf.h"
  33 #include "llvm/Support/KnownBits.h"
  34 #include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
  35 #include "llvm/Transforms/Utils/Local.h"
  36
  37 #define DEBUG_TYPE "instcombine"
  38
  39 namespace llvm {
  40 class CallSite;
  41 class DataLayout;
  42 class DominatorTree;
  43 class TargetLibraryInfo;
  44 class DbgDeclareInst;
  45 class MemIntrinsic;
  46 class MemSetInst;
  47
  48 /// Assign a complexity or rank value to LLVM Values. This is used to reduce
  49 /// the amount of pattern matching needed for compares and commutative
  50 /// instructions. For example, if we have:
  51 ///   icmp ugt X, Constant
  52 /// or
  53 ///   xor (add X, Constant), cast Z
  54 ///
  55 /// We do not have to consider the commuted variants of these patterns because
  56 /// canonicalization based on complexity guarantees the above ordering.
  57 ///
  58 /// This routine maps IR values to various complexity ranks:
  59 ///   0 -> undef
  60 ///   1 -> Constants
  61 ///   2 -> Other non-instructions
  62 ///   3 -> Arguments
  63 ///   4 -> Cast and (f)neg/not instructions
  64 ///   5 -> Other instructions
  65 static inline unsigned getComplexity(Value *V) {
  66   if (isa<Instruction>(V)) {
  67     if (isa<CastInst>(V) || BinaryOperator::isNeg(V) ||
  68         BinaryOperator::isFNeg(V) || BinaryOperator::isNot(V))
  69       return 4;
  70     return 5;
  71   }
  72   if (isa<Argument>(V))
  73     return 3;
  74   return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2;
  75 }
  76
  77 /// Predicate canonicalization reduces the number of patterns that need to be
  78 /// matched by other transforms. For example, we may swap the operands of a
  79 /// conditional branch or select to create a compare with a canonical (inverted)
  80 /// predicate which is then more likely to be matched with other values.
  81 static inline bool isCanonicalPredicate(CmpInst::Predicate Pred) {
  82   switch (Pred) {
  83   case CmpInst::ICMP_NE:
  84   case CmpInst::ICMP_ULE:
  85   case CmpInst::ICMP_SLE:
  86   case CmpInst::ICMP_UGE:
  87   case CmpInst::ICMP_SGE:
  88   // TODO: There are 16 FCMP predicates. Should others be (not) canonical?
  89   case CmpInst::FCMP_ONE:
  90   case CmpInst::FCMP_OLE:
  91   case CmpInst::FCMP_OGE:
  92     return false;
  93   default:
  94     return true;
  95   }
  96 }
  97
  98 /// \brief Add one to a Constant
  99 static inline Constant *AddOne(Constant *C) {
 100   return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
 101 }
 102 /// \brief Subtract one from a Constant
 103 static inline Constant *SubOne(Constant *C) {
 104   return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1));
 105 }
 106
 107 /// \brief Return true if the specified value is free to invert (apply ~ to).
 108 /// This happens in cases where the ~ can be eliminated.  If WillInvertAllUses
 109 /// is true, work under the assumption that the caller intends to remove all
 110 /// uses of V and only keep uses of ~V.
 111 ///
 112 static inline bool IsFreeToInvert(Value *V, bool WillInvertAllUses) {
 113   // ~(~(X)) -> X.
 114   if (BinaryOperator::isNot(V))
 115     return true;
 116
 117   // Constants can be considered to be not'ed values.
 118   if (isa<ConstantInt>(V))
 119     return true;
 120
 121   // A vector of constant integers can be inverted easily.
 122   Constant *CV;
 123   if (V->getType()->isVectorTy() && match(V, PatternMatch::m_Constant(CV))) {
 124     unsigned NumElts = V->getType()->getVectorNumElements();
 125     for (unsigned i = 0; i != NumElts; ++i) {
 126       Constant *Elt = CV->getAggregateElement(i);
 127       if (!Elt)
 128         return false;
 129
 130       if (isa<UndefValue>(Elt))
 131         continue;
 132
 133       if (!isa<ConstantInt>(Elt))
 134         return false;
 135     }
 136     return true;
 137   }
 138
 139   // Compares can be inverted if all of their uses are being modified to use the
 140   // ~V.
 141   if (isa<CmpInst>(V))
 142     return WillInvertAllUses;
 143
 144   // If `V` is of the form `A + Constant` then `-1 - V` can be folded into `(-1
 145   // - Constant) - A` if we are willing to invert all of the uses.
 146   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V))
 147     if (BO->getOpcode() == Instruction::Add ||
 148         BO->getOpcode() == Instruction::Sub)
 149       if (isa<Constant>(BO->getOperand(0)) || isa<Constant>(BO->getOperand(1)))
 150         return WillInvertAllUses;
 151
 152   return false;
 153 }
 154
 155
 156 /// \brief Specific patterns of overflow check idioms that we match.
 157 enum OverflowCheckFlavor {
 158   OCF_UNSIGNED_ADD,
 159   OCF_SIGNED_ADD,
 160   OCF_UNSIGNED_SUB,
 161   OCF_SIGNED_SUB,
 162   OCF_UNSIGNED_MUL,
 163   OCF_SIGNED_MUL,
 164
 165   OCF_INVALID
 166 };
 167
 168 /// \brief Returns the OverflowCheckFlavor corresponding to a overflow_with_op
 169 /// intrinsic.
 170 static inline OverflowCheckFlavor
 171 IntrinsicIDToOverflowCheckFlavor(unsigned ID) {
 172   switch (ID) {
 173   default:
 174     return OCF_INVALID;
 175   case Intrinsic::uadd_with_overflow:
 176     return OCF_UNSIGNED_ADD;
 177   case Intrinsic::sadd_with_overflow:
 178     return OCF_SIGNED_ADD;
 179   case Intrinsic::usub_with_overflow:
 180     return OCF_UNSIGNED_SUB;
 181   case Intrinsic::ssub_with_overflow:
 182     return OCF_SIGNED_SUB;
 183   case Intrinsic::umul_with_overflow:
 184     return OCF_UNSIGNED_MUL;
 185   case Intrinsic::smul_with_overflow:
 186     return OCF_SIGNED_MUL;
 187   }
 188 }
 189
 190 /// \brief The core instruction combiner logic.
 191 ///
 192 /// This class provides both the logic to recursively visit instructions and
 193 /// combine them.
 194 class LLVM_LIBRARY_VISIBILITY InstCombiner
 195     : public InstVisitor<InstCombiner, Instruction *> {
 196   // FIXME: These members shouldn't be public.
 197 public:
 198   /// \brief A worklist of the instructions that need to be simplified.
 199   InstCombineWorklist &Worklist;
 200
 201   /// \brief An IRBuilder that automatically inserts new instructions into the
 202   /// worklist.
 203   typedef IRBuilder<TargetFolder, IRBuilderCallbackInserter> BuilderTy;
 204   BuilderTy *Builder;
 205
 206 private:
 207   // Mode in which we are running the combiner.
 208   const bool MinimizeSize;
 209   /// Enable combines that trigger rarely but are costly in compiletime.
 210   const bool ExpensiveCombines;
 211
 212   AliasAnalysis *AA;
 213
 214   // Required analyses.
 215   AssumptionCache &AC;
 216   TargetLibraryInfo &TLI;
 217   DominatorTree &DT;
 218   const DataLayout &DL;
 219   const SimplifyQuery SQ;
 220   // Optional analyses. When non-null, these can both be used to do better
 221   // combining and will be updated to reflect any changes.
 222   LoopInfo *LI;
 223
 224   bool MadeIRChange;
 225
 226 public:
 227   InstCombiner(InstCombineWorklist &Worklist, BuilderTy *Builder,
 228                bool MinimizeSize, bool ExpensiveCombines, AliasAnalysis *AA,
 229                AssumptionCache &AC, TargetLibraryInfo &TLI, DominatorTree &DT,
 230                const DataLayout &DL, LoopInfo *LI)
 231       : Worklist(Worklist), Builder(Builder), MinimizeSize(MinimizeSize),
 232         ExpensiveCombines(ExpensiveCombines), AA(AA), AC(AC), TLI(TLI), DT(DT),
 233         DL(DL), SQ(DL, &TLI, &DT, &AC), LI(LI), MadeIRChange(false) {}
 234
 235   /// \brief Run the combiner over the entire worklist until it is empty.
 236   ///
 237   /// \returns true if the IR is changed.
 238   bool run();
 239
 240   AssumptionCache &getAssumptionCache() const { return AC; }
 241
 242   const DataLayout &getDataLayout() const { return DL; }
 243
 244   DominatorTree &getDominatorTree() const { return DT; }
 245
 246   LoopInfo *getLoopInfo() const { return LI; }
 247
 248   TargetLibraryInfo &getTargetLibraryInfo() const { return TLI; }
 249
 250   // Visitation implementation - Implement instruction combining for different
 251   // instruction types.  The semantics are as follows:
 252   // Return Value:
 253   //    null        - No change was made
 254   //     I          - Change was made, I is still valid, I may be dead though
 255   //   otherwise    - Change was made, replace I with returned instruction
 256   //
 257   Instruction *visitAdd(BinaryOperator &I);
 258   Instruction *visitFAdd(BinaryOperator &I);
 259   Value *OptimizePointerDifference(Value *LHS, Value *RHS, Type *Ty);
 260   Instruction *visitSub(BinaryOperator &I);
 261   Instruction *visitFSub(BinaryOperator &I);
 262   Instruction *visitMul(BinaryOperator &I);
 263   Value *foldFMulConst(Instruction *FMulOrDiv, Constant *C,
 264                        Instruction *InsertBefore);
 265   Instruction *visitFMul(BinaryOperator &I);
 266   Instruction *visitURem(BinaryOperator &I);
 267   Instruction *visitSRem(BinaryOperator &I);
 268   Instruction *visitFRem(BinaryOperator &I);
 269   bool SimplifyDivRemOfSelect(BinaryOperator &I);
 270   Instruction *commonRemTransforms(BinaryOperator &I);
 271   Instruction *commonIRemTransforms(BinaryOperator &I);
 272   Instruction *commonDivTransforms(BinaryOperator &I);
 273   Instruction *commonIDivTransforms(BinaryOperator &I);
 274   Instruction *visitUDiv(BinaryOperator &I);
 275   Instruction *visitSDiv(BinaryOperator &I);
 276   Instruction *visitFDiv(BinaryOperator &I);
 277   Value *simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted);
 278   Instruction *visitAnd(BinaryOperator &I);
 279   Instruction *FoldOrWithConstants(BinaryOperator &I, Value *Op, Value *A,
 280                                    Value *B, Value *C);
 281   Instruction *FoldXorWithConstants(BinaryOperator &I, Value *Op, Value *A,
 282                                     Value *B, Value *C);
 283   Instruction *visitOr(BinaryOperator &I);
 284   Instruction *visitXor(BinaryOperator &I);
 285   Instruction *visitShl(BinaryOperator &I);
 286   Instruction *visitAShr(BinaryOperator &I);
 287   Instruction *visitLShr(BinaryOperator &I);
 288   Instruction *commonShiftTransforms(BinaryOperator &I);
 289   Instruction *visitFCmpInst(FCmpInst &I);
 290   Instruction *visitICmpInst(ICmpInst &I);
 291   Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
 292                                    BinaryOperator &I);
 293   Instruction *commonCastTransforms(CastInst &CI);
 294   Instruction *commonPointerCastTransforms(CastInst &CI);
 295   Instruction *visitTrunc(TruncInst &CI);
 296   Instruction *visitZExt(ZExtInst &CI);
 297   Instruction *visitSExt(SExtInst &CI);
 298   Instruction *visitFPTrunc(FPTruncInst &CI);
 299   Instruction *visitFPExt(CastInst &CI);
 300   Instruction *visitFPToUI(FPToUIInst &FI);
 301   Instruction *visitFPToSI(FPToSIInst &FI);
 302   Instruction *visitUIToFP(CastInst &CI);
 303   Instruction *visitSIToFP(CastInst &CI);
 304   Instruction *visitPtrToInt(PtrToIntInst &CI);
 305   Instruction *visitIntToPtr(IntToPtrInst &CI);
 306   Instruction *visitBitCast(BitCastInst &CI);
 307   Instruction *visitAddrSpaceCast(AddrSpaceCastInst &CI);
 308   Instruction *FoldItoFPtoI(Instruction &FI);
 309   Instruction *visitSelectInst(SelectInst &SI);
 310   Instruction *visitCallInst(CallInst &CI);
 311   Instruction *visitInvokeInst(InvokeInst &II);
 312
 313   Instruction *SliceUpIllegalIntegerPHI(PHINode &PN);
 314   Instruction *visitPHINode(PHINode &PN);
 315   Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
 316   Instruction *visitAllocaInst(AllocaInst &AI);
 317   Instruction *visitAllocSite(Instruction &FI);
 318   Instruction *visitFree(CallInst &FI);
 319   Instruction *visitLoadInst(LoadInst &LI);
 320   Instruction *visitStoreInst(StoreInst &SI);
 321   Instruction *visitBranchInst(BranchInst &BI);
 322   Instruction *visitFenceInst(FenceInst &FI);
 323   Instruction *visitSwitchInst(SwitchInst &SI);
 324   Instruction *visitReturnInst(ReturnInst &RI);
 325   Instruction *visitInsertValueInst(InsertValueInst &IV);
 326   Instruction *visitInsertElementInst(InsertElementInst &IE);
 327   Instruction *visitExtractElementInst(ExtractElementInst &EI);
 328   Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
 329   Instruction *visitExtractValueInst(ExtractValueInst &EV);
 330   Instruction *visitLandingPadInst(LandingPadInst &LI);
 331   Instruction *visitVAStartInst(VAStartInst &I);
 332   Instruction *visitVACopyInst(VACopyInst &I);
 333
 334   /// Specify what to return for unhandled instructions.
 335   Instruction *visitInstruction(Instruction &I) { return nullptr; }
 336
 337   /// True when DB dominates all uses of DI except UI.
 338   /// UI must be in the same block as DI.
 339   /// The routine checks that the DI parent and DB are different.
 340   bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
 341                         const BasicBlock *DB) const;
 342
 343   /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
 344   bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
 345                                  const unsigned SIOpd);
 346
 347   /// Try to replace instruction \p I with value \p V which are pointers
 348   /// in different address space.
 349   /// \return true if successful.
 350   bool replacePointer(Instruction &I, Value *V);
 351
 352 private:
 353   bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
 354   bool shouldChangeType(Type *From, Type *To) const;
 355   Value *dyn_castNegVal(Value *V) const;
 356   Value *dyn_castFNegVal(Value *V, bool NoSignedZero = false) const;
 357   Type *FindElementAtOffset(PointerType *PtrTy, int64_t Offset,
 358                             SmallVectorImpl<Value *> &NewIndices);
 359
 360   /// Classify whether a cast is worth optimizing.
 361   ///
 362   /// This is a helper to decide whether the simplification of
 363   /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
 364   ///
 365   /// \param CI The cast we are interested in.
 366   ///
 367   /// \return true if this cast actually results in any code being generated and
 368   /// if it cannot already be eliminated by some other transformation.
 369   bool shouldOptimizeCast(CastInst *CI);
 370
 371   /// \brief Try to optimize a sequence of instructions checking if an operation
 372   /// on LHS and RHS overflows.
 373   ///
 374   /// If this overflow check is done via one of the overflow check intrinsics,
 375   /// then CtxI has to be the call instruction calling that intrinsic.  If this
 376   /// overflow check is done by arithmetic followed by a compare, then CtxI has
 377   /// to be the arithmetic instruction.
 378   ///
 379   /// If a simplification is possible, stores the simplified result of the
 380   /// operation in OperationResult and result of the overflow check in
 381   /// OverflowResult, and return true.  If no simplification is possible,
 382   /// returns false.
 383   bool OptimizeOverflowCheck(OverflowCheckFlavor OCF, Value *LHS, Value *RHS,
 384                              Instruction &CtxI, Value *&OperationResult,
 385                              Constant *&OverflowResult);
 386
 387   Instruction *visitCallSite(CallSite CS);
 388   Instruction *tryOptimizeCall(CallInst *CI);
 389   bool transformConstExprCastCall(CallSite CS);
 390   Instruction *transformCallThroughTrampoline(CallSite CS,
 391                                               IntrinsicInst *Tramp);
 392
 393   /// Transform (zext icmp) to bitwise / integer operations in order to
 394   /// eliminate it.
 395   ///
 396   /// \param ICI The icmp of the (zext icmp) pair we are interested in.
 397   /// \parem CI The zext of the (zext icmp) pair we are interested in.
 398   /// \param DoTransform Pass false to just test whether the given (zext icmp)
 399   /// would be transformed. Pass true to actually perform the transformation.
 400   ///
 401   /// \return null if the transformation cannot be performed. If the
 402   /// transformation can be performed the new instruction that replaces the
 403   /// (zext icmp) pair will be returned (if \p DoTransform is false the
 404   /// unmodified \p ICI will be returned in this case).
 405   Instruction *transformZExtICmp(ICmpInst *ICI, ZExtInst &CI,
 406                                  bool DoTransform = true);
 407
 408   Instruction *transformSExtICmp(ICmpInst *ICI, Instruction &CI);
 409   bool willNotOverflowSignedAdd(const Value *LHS, const Value *RHS,
 410                                 const Instruction &CxtI) const {
 411     return computeOverflowForSignedAdd(LHS, RHS, &CxtI) ==
 412            OverflowResult::NeverOverflows;
 413   };
 414   bool willNotOverflowUnsignedAdd(const Value *LHS, const Value *RHS,
 415                                   const Instruction &CxtI) const {
 416     return computeOverflowForUnsignedAdd(LHS, RHS, &CxtI) ==
 417            OverflowResult::NeverOverflows;
 418   };
 419   bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
 420                                 const Instruction &CxtI) const;
 421   bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
 422                                   const Instruction &CxtI) const;
 423   bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
 424                                 const Instruction &CxtI) const;
 425   bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
 426                                   const Instruction &CxtI) const {
 427     return computeOverflowForUnsignedMul(LHS, RHS, &CxtI) ==
 428            OverflowResult::NeverOverflows;
 429   };
 430   Value *EmitGEPOffset(User *GEP);
 431   Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
 432   Value *EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask);
 433   Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
 434   Instruction *shrinkBitwiseLogic(TruncInst &Trunc);
 435   Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
 436
 437   /// Determine if a pair of casts can be replaced by a single cast.
 438   ///
 439   /// \param CI1 The first of a pair of casts.
 440   /// \param CI2 The second of a pair of casts.
 441   ///
 442   /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
 443   /// Instruction::CastOps value for a cast that can replace the pair, casting
 444   /// CI1->getSrcTy() to CI2->getDstTy().
 445   ///
 446   /// \see CastInst::isEliminableCastPair
 447   Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
 448                                             const CastInst *CI2);
 449
 450   Value *foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS);
 451   Value *foldAndOfFCmps(FCmpInst *LHS, FCmpInst *RHS);
 452   Value *foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction *CxtI);
 453   Value *foldOrOfFCmps(FCmpInst *LHS, FCmpInst *RHS);
 454   Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS);
 455
 456 public:
 457   /// \brief Inserts an instruction \p New before instruction \p Old
 458   ///
 459   /// Also adds the new instruction to the worklist and returns \p New so that
 460   /// it is suitable for use as the return from the visitation patterns.
 461   Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) {
 462     assert(New && !New->getParent() &&
 463            "New instruction already inserted into a basic block!");
 464     BasicBlock *BB = Old.getParent();
 465     BB->getInstList().insert(Old.getIterator(), New); // Insert inst
 466     Worklist.Add(New);
 467     return New;
 468   }
 469
 470   /// \brief Same as InsertNewInstBefore, but also sets the debug loc.
 471   Instruction *InsertNewInstWith(Instruction *New, Instruction &Old) {
 472     New->setDebugLoc(Old.getDebugLoc());
 473     return InsertNewInstBefore(New, Old);
 474   }
 475
 476   /// \brief A combiner-aware RAUW-like routine.
 477   ///
 478   /// This method is to be used when an instruction is found to be dead,
 479   /// replaceable with another preexisting expression. Here we add all uses of
 480   /// I to the worklist, replace all uses of I with the new value, then return
 481   /// I, so that the inst combiner will know that I was modified.
 482   Instruction *replaceInstUsesWith(Instruction &I, Value *V) {
 483     // If there are no uses to replace, then we return nullptr to indicate that
 484     // no changes were made to the program.
 485     if (I.use_empty()) return nullptr;
 486
 487     Worklist.AddUsersToWorkList(I); // Add all modified instrs to worklist.
 488
 489     // If we are replacing the instruction with itself, this must be in a
 490     // segment of unreachable code, so just clobber the instruction.
 491     if (&I == V)
 492       V = UndefValue::get(I.getType());
 493
 494     DEBUG(dbgs() << "IC: Replacing " << I << "\n"
 495                  << "    with " << *V << '\n');
 496
 497     I.replaceAllUsesWith(V);
 498     return &I;
 499   }
 500
 501   /// Creates a result tuple for an overflow intrinsic \p II with a given
 502   /// \p Result and a constant \p Overflow value.
 503   Instruction *CreateOverflowTuple(IntrinsicInst *II, Value *Result,
 504                                    Constant *Overflow) {
 505     Constant *V[] = {UndefValue::get(Result->getType()), Overflow};
 506     StructType *ST = cast<StructType>(II->getType());
 507     Constant *Struct = ConstantStruct::get(ST, V);
 508     return InsertValueInst::Create(Struct, Result, 0);
 509   }
 510
 511   /// \brief Combiner aware instruction erasure.
 512   ///
 513   /// When dealing with an instruction that has side effects or produces a void
 514   /// value, we can't rely on DCE to delete the instruction. Instead, visit
 515   /// methods should return the value returned by this function.
 516   Instruction *eraseInstFromFunction(Instruction &I) {
 517     DEBUG(dbgs() << "IC: ERASE " << I << '\n');
 518     assert(I.use_empty() && "Cannot erase instruction that is used!");
 519     salvageDebugInfo(I);
 520
 521     // Make sure that we reprocess all operands now that we reduced their
 522     // use counts.
 523     if (I.getNumOperands() < 8) {
 524       for (Use &Operand : I.operands())
 525         if (auto *Inst = dyn_cast<Instruction>(Operand))
 526           Worklist.Add(Inst);
 527     }
 528     Worklist.Remove(&I);
 529     I.eraseFromParent();
 530     MadeIRChange = true;
 531     return nullptr; // Don't do anything with FI
 532   }
 533
 534   void computeKnownBits(const Value *V, KnownBits &Known,
 535                         unsigned Depth, const Instruction *CxtI) const {
 536     llvm::computeKnownBits(V, Known, DL, Depth, &AC, CxtI, &DT);
 537   }
 538   KnownBits computeKnownBits(const Value *V, unsigned Depth,
 539                              const Instruction *CxtI) const {
 540     return llvm::computeKnownBits(V, DL, Depth, &AC, CxtI, &DT);
 541   }
 542
 543   bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero = false,
 544                               unsigned Depth = 0,
 545                               const Instruction *CxtI = nullptr) {
 546     return llvm::isKnownToBeAPowerOfTwo(V, DL, OrZero, Depth, &AC, CxtI, &DT);
 547   }
 548
 549   bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth = 0,
 550                          const Instruction *CxtI = nullptr) const {
 551     return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT);
 552   }
 553   unsigned ComputeNumSignBits(const Value *Op, unsigned Depth = 0,
 554                               const Instruction *CxtI = nullptr) const {
 555     return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
 556   }
 557   OverflowResult computeOverflowForUnsignedMul(const Value *LHS,
 558                                                const Value *RHS,
 559                                                const Instruction *CxtI) const {
 560     return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
 561   }
 562   OverflowResult computeOverflowForUnsignedAdd(const Value *LHS,
 563                                                const Value *RHS,
 564                                                const Instruction *CxtI) const {
 565     return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
 566   }
 567   OverflowResult computeOverflowForSignedAdd(const Value *LHS,
 568                                              const Value *RHS,
 569                                              const Instruction *CxtI) const {
 570     return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
 571   }
 572
 573   /// Maximum size of array considered when transforming.
 574   uint64_t MaxArraySizeForCombine;
 575
 576 private:
 577   /// \brief Performs a few simplifications for operators which are associative
 578   /// or commutative.
 579   bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
 580
 581   /// \brief Tries to simplify binary operations which some other binary
 582   /// operation distributes over.
 583   ///
 584   /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
 585   /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
 586   /// & (B | C) -> (A&B) | (A&C)" if this is a win).  Returns the simplified
 587   /// value, or null if it didn't simplify.
 588   Value *SimplifyUsingDistributiveLaws(BinaryOperator &I);
 589
 590   /// This tries to simplify binary operations by factorizing out common terms
 591   /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
 592   Value *tryFactorization(InstCombiner::BuilderTy *, BinaryOperator &,
 593                           Instruction::BinaryOps, Value *, Value *, Value *,
 594                           Value *);
 595
 596   /// \brief Attempts to replace V with a simpler value based on the demanded
 597   /// bits.
 598   Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known,
 599                                  unsigned Depth, Instruction *CxtI);
 600   bool SimplifyDemandedBits(Instruction *I, unsigned Op,
 601                             const APInt &DemandedMask, KnownBits &Known,
 602                             unsigned Depth = 0);
 603   /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
 604   /// bits. It also tries to handle simplifications that can be done based on
 605   /// DemandedMask, but without modifying the Instruction.
 606   Value *SimplifyMultipleUseDemandedBits(Instruction *I,
 607                                          const APInt &DemandedMask,
 608                                          KnownBits &Known,
 609                                          unsigned Depth, Instruction *CxtI);
 610   /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
 611   /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
 612   Value *simplifyShrShlDemandedBits(
 613       Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
 614       const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
 615
 616   /// \brief Tries to simplify operands to an integer instruction based on its
 617   /// demanded bits.
 618   bool SimplifyDemandedInstructionBits(Instruction &Inst);
 619
 620   Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
 621                                     APInt &UndefElts, unsigned Depth = 0);
 622
 623   Value *SimplifyVectorOp(BinaryOperator &Inst);
 624   Value *SimplifyBSwap(BinaryOperator &Inst);
 625
 626
 627   /// Given a binary operator, cast instruction, or select which has a PHI node
 628   /// as operand #0, see if we can fold the instruction into the PHI (which is
 629   /// only possible if all operands to the PHI are constants).
 630   Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN);
 631
 632   /// Given an instruction with a select as one operand and a constant as the
 633   /// other operand, try to fold the binary operator into the select arguments.
 634   /// This also works for Cast instructions, which obviously do not have a
 635   /// second operand.
 636   Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI);
 637
 638   /// This is a convenience wrapper function for the above two functions.
 639   Instruction *foldOpWithConstantIntoOperand(BinaryOperator &I);
 640
 641   /// \brief Try to rotate an operation below a PHI node, using PHI nodes for
 642   /// its operands.
 643   Instruction *FoldPHIArgOpIntoPHI(PHINode &PN);
 644   Instruction *FoldPHIArgBinOpIntoPHI(PHINode &PN);
 645   Instruction *FoldPHIArgGEPIntoPHI(PHINode &PN);
 646   Instruction *FoldPHIArgLoadIntoPHI(PHINode &PN);
 647   Instruction *FoldPHIArgZextsIntoPHI(PHINode &PN);
 648
 649   /// Helper function for FoldPHIArgXIntoPHI() to get debug location for the
 650   /// folded operation.
 651   DebugLoc PHIArgMergedDebugLoc(PHINode &PN);
 652
 653   Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
 654                            ICmpInst::Predicate Cond, Instruction &I);
 655   Instruction *foldAllocaCmp(ICmpInst &ICI, const AllocaInst *Alloca,
 656                              const Value *Other);
 657   Instruction *foldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP,
 658                                             GlobalVariable *GV, CmpInst &ICI,
 659                                             ConstantInt *AndCst = nullptr);
 660   Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
 661                                     Constant *RHSC);
 662   Instruction *foldICmpAddOpConst(Instruction &ICI, Value *X, ConstantInt *CI,
 663                                   ICmpInst::Predicate Pred);
 664   Instruction *foldICmpWithCastAndCast(ICmpInst &ICI);
 665
 666   Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
 667   Instruction *foldICmpWithConstant(ICmpInst &Cmp);
 668   Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
 669   Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
 670   Instruction *foldICmpBinOp(ICmpInst &Cmp);
 671   Instruction *foldICmpEquality(ICmpInst &Cmp);
 672
 673   Instruction *foldICmpTruncConstant(ICmpInst &Cmp, Instruction *Trunc,
 674                                      const APInt *C);
 675   Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
 676                                    const APInt *C);
 677   Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
 678                                    const APInt *C);
 679   Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
 680                                   const APInt *C);
 681   Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
 682                                    const APInt *C);
 683   Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
 684                                    const APInt *C);
 685   Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
 686                                    const APInt *C);
 687   Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
 688                                     const APInt *C);
 689   Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
 690                                    const APInt *C);
 691   Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
 692                                    const APInt *C);
 693   Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
 694                                    const APInt *C);
 695   Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
 696                                      const APInt *C1);
 697   Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
 698                                 const APInt *C1, const APInt *C2);
 699   Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
 700                                      const APInt &C2);
 701   Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
 702                                      const APInt &C2);
 703
 704   Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
 705                                                  BinaryOperator *BO,
 706                                                  const APInt *C);
 707   Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, const APInt *C);
 708
 709   // Helpers of visitSelectInst().
 710   Instruction *foldSelectExtConst(SelectInst &Sel);
 711   Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
 712   Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
 713   Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1,
 714                             Value *A, Value *B, Instruction &Outer,
 715                             SelectPatternFlavor SPF2, Value *C);
 716   Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI);
 717
 718   Instruction *OptAndOp(BinaryOperator *Op, ConstantInt *OpRHS,
 719                         ConstantInt *AndRHS, BinaryOperator &TheAnd);
 720
 721   Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
 722                          bool isSigned, bool Inside);
 723   Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI);
 724   Instruction *MatchBSwap(BinaryOperator &I);
 725   bool SimplifyStoreAtEndOfBlock(StoreInst &SI);
 726
 727   Instruction *SimplifyElementAtomicMemCpy(ElementAtomicMemCpyInst *AMI);
 728   Instruction *SimplifyMemTransfer(MemIntrinsic *MI);
 729   Instruction *SimplifyMemSet(MemSetInst *MI);
 730
 731   Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
 732
 733   /// \brief Returns a value X such that Val = X * Scale, or null if none.
 734   ///
 735   /// If the multiplication is known not to overflow then NoSignedWrap is set.
 736   Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
 737 };
 738
 739 } // end namespace llvm.
 740
 741 #undef DEBUG_TYPE
 742
 743 #endif