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