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