lib/Transforms/InstCombine/InstCombineInternal.h

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