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