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