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