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