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