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/Statistic.h"
  19 #include "llvm/Analysis/InstructionSimplify.h"
  20 #include "llvm/Analysis/TargetFolder.h"
  21 #include "llvm/Analysis/ValueTracking.h"
  22 #include "llvm/IR/IRBuilder.h"
  23 #include "llvm/IR/InstVisitor.h"
  24 #include "llvm/IR/PatternMatch.h"
  25 #include "llvm/IR/Value.h"
  26 #include "llvm/Support/Debug.h"
  27 #include "llvm/Support/KnownBits.h"
  28 #include "llvm/Transforms/InstCombine/InstCombiner.h"
  29 #include "llvm/Transforms/Utils/Local.h"
  30 #include <cassert>
  31
  32 #define DEBUG_TYPE "instcombine"
  33 #include "llvm/Transforms/Utils/InstructionWorklist.h"
  34
  35 using namespace llvm::PatternMatch;
  36
  37 // As a default, let's assume that we want to be aggressive,
  38 // and attempt to traverse with no limits in attempt to sink negation.
  39 static constexpr unsigned NegatorDefaultMaxDepth = ~0U;
  40
  41 // Let's guesstimate that most often we will end up visiting/producing
  42 // fairly small number of new instructions.
  43 static constexpr unsigned NegatorMaxNodesSSO = 16;
  44
  45 namespace llvm {
  46
  47 class AAResults;
  48 class APInt;
  49 class AssumptionCache;
  50 class BlockFrequencyInfo;
  51 class DataLayout;
  52 class DominatorTree;
  53 class GEPOperator;
  54 class GlobalVariable;
  55 class LoopInfo;
  56 class OptimizationRemarkEmitter;
  57 class ProfileSummaryInfo;
  58 class TargetLibraryInfo;
  59 class User;
  60
  61 class LLVM_LIBRARY_VISIBILITY InstCombinerImpl final
  62     : public InstCombiner,
  63       public InstVisitor<InstCombinerImpl, Instruction *> {
  64 public:
  65   InstCombinerImpl(InstructionWorklist &Worklist, BuilderTy &Builder,
  66                    bool MinimizeSize, AAResults *AA, AssumptionCache &AC,
  67                    TargetLibraryInfo &TLI, TargetTransformInfo &TTI,
  68                    DominatorTree &DT, OptimizationRemarkEmitter &ORE,
  69                    BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
  70                    const DataLayout &DL, LoopInfo *LI)
  71       : InstCombiner(Worklist, Builder, MinimizeSize, AA, AC, TLI, TTI, DT, ORE,
  72                      BFI, PSI, DL, LI) {}
  73
  74   virtual ~InstCombinerImpl() {}
  75
  76   /// Run the combiner over the entire worklist until it is empty.
  77   ///
  78   /// \returns true if the IR is changed.
  79   bool run();
  80
  81   // Visitation implementation - Implement instruction combining for different
  82   // instruction types.  The semantics are as follows:
  83   // Return Value:
  84   //    null        - No change was made
  85   //     I          - Change was made, I is still valid, I may be dead though
  86   //   otherwise    - Change was made, replace I with returned instruction
  87   //
  88   Instruction *visitFNeg(UnaryOperator &I);
  89   Instruction *visitAdd(BinaryOperator &I);
  90   Instruction *visitFAdd(BinaryOperator &I);
  91   Value *OptimizePointerDifference(
  92       Value *LHS, Value *RHS, Type *Ty, bool isNUW);
  93   Instruction *visitSub(BinaryOperator &I);
  94   Instruction *visitFSub(BinaryOperator &I);
  95   Instruction *visitMul(BinaryOperator &I);
  96   Instruction *visitFMul(BinaryOperator &I);
  97   Instruction *visitURem(BinaryOperator &I);
  98   Instruction *visitSRem(BinaryOperator &I);
  99   Instruction *visitFRem(BinaryOperator &I);
 100   bool simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I);
 101   Instruction *commonIRemTransforms(BinaryOperator &I);
 102   Instruction *commonIDivTransforms(BinaryOperator &I);
 103   Instruction *visitUDiv(BinaryOperator &I);
 104   Instruction *visitSDiv(BinaryOperator &I);
 105   Instruction *visitFDiv(BinaryOperator &I);
 106   Value *simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted);
 107   Instruction *visitAnd(BinaryOperator &I);
 108   Instruction *visitOr(BinaryOperator &I);
 109   bool sinkNotIntoOtherHandOfAndOrOr(BinaryOperator &I);
 110   Instruction *visitXor(BinaryOperator &I);
 111   Instruction *visitShl(BinaryOperator &I);
 112   Value *reassociateShiftAmtsOfTwoSameDirectionShifts(
 113       BinaryOperator *Sh0, const SimplifyQuery &SQ,
 114       bool AnalyzeForSignBitExtraction = false);
 115   Instruction *canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(
 116       BinaryOperator &I);
 117   Instruction *foldVariableSignZeroExtensionOfVariableHighBitExtract(
 118       BinaryOperator &OldAShr);
 119   Instruction *visitAShr(BinaryOperator &I);
 120   Instruction *visitLShr(BinaryOperator &I);
 121   Instruction *commonShiftTransforms(BinaryOperator &I);
 122   Instruction *visitFCmpInst(FCmpInst &I);
 123   CmpInst *canonicalizeICmpPredicate(CmpInst &I);
 124   Instruction *visitICmpInst(ICmpInst &I);
 125   Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
 126                                    BinaryOperator &I);
 127   Instruction *commonCastTransforms(CastInst &CI);
 128   Instruction *commonPointerCastTransforms(CastInst &CI);
 129   Instruction *visitTrunc(TruncInst &CI);
 130   Instruction *visitZExt(ZExtInst &CI);
 131   Instruction *visitSExt(SExtInst &CI);
 132   Instruction *visitFPTrunc(FPTruncInst &CI);
 133   Instruction *visitFPExt(CastInst &CI);
 134   Instruction *visitFPToUI(FPToUIInst &FI);
 135   Instruction *visitFPToSI(FPToSIInst &FI);
 136   Instruction *visitUIToFP(CastInst &CI);
 137   Instruction *visitSIToFP(CastInst &CI);
 138   Instruction *visitPtrToInt(PtrToIntInst &CI);
 139   Instruction *visitIntToPtr(IntToPtrInst &CI);
 140   Instruction *visitBitCast(BitCastInst &CI);
 141   Instruction *visitAddrSpaceCast(AddrSpaceCastInst &CI);
 142   Instruction *foldItoFPtoI(CastInst &FI);
 143   Instruction *visitSelectInst(SelectInst &SI);
 144   Instruction *visitCallInst(CallInst &CI);
 145   Instruction *visitInvokeInst(InvokeInst &II);
 146   Instruction *visitCallBrInst(CallBrInst &CBI);
 147
 148   Instruction *SliceUpIllegalIntegerPHI(PHINode &PN);
 149   Instruction *visitPHINode(PHINode &PN);
 150   Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
 151   Instruction *visitGEPOfGEP(GetElementPtrInst &GEP, GEPOperator *Src);
 152   Instruction *visitGEPOfBitcast(BitCastInst *BCI, GetElementPtrInst &GEP);
 153   Instruction *visitAllocaInst(AllocaInst &AI);
 154   Instruction *visitAllocSite(Instruction &FI);
 155   Instruction *visitFree(CallInst &FI);
 156   Instruction *visitLoadInst(LoadInst &LI);
 157   Instruction *visitStoreInst(StoreInst &SI);
 158   Instruction *visitAtomicRMWInst(AtomicRMWInst &SI);
 159   Instruction *visitUnconditionalBranchInst(BranchInst &BI);
 160   Instruction *visitBranchInst(BranchInst &BI);
 161   Instruction *visitFenceInst(FenceInst &FI);
 162   Instruction *visitSwitchInst(SwitchInst &SI);
 163   Instruction *visitReturnInst(ReturnInst &RI);
 164   Instruction *visitUnreachableInst(UnreachableInst &I);
 165   Instruction *
 166   foldAggregateConstructionIntoAggregateReuse(InsertValueInst &OrigIVI);
 167   Instruction *visitInsertValueInst(InsertValueInst &IV);
 168   Instruction *visitInsertElementInst(InsertElementInst &IE);
 169   Instruction *visitExtractElementInst(ExtractElementInst &EI);
 170   Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
 171   Instruction *visitExtractValueInst(ExtractValueInst &EV);
 172   Instruction *visitLandingPadInst(LandingPadInst &LI);
 173   Instruction *visitVAEndInst(VAEndInst &I);
 174   Value *pushFreezeToPreventPoisonFromPropagating(FreezeInst &FI);
 175   bool freezeDominatedUses(FreezeInst &FI);
 176   Instruction *visitFreeze(FreezeInst &I);
 177
 178   /// Specify what to return for unhandled instructions.
 179   Instruction *visitInstruction(Instruction &I) { return nullptr; }
 180
 181   /// True when DB dominates all uses of DI except UI.
 182   /// UI must be in the same block as DI.
 183   /// The routine checks that the DI parent and DB are different.
 184   bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
 185                         const BasicBlock *DB) const;
 186
 187   /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
 188   bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
 189                                  const unsigned SIOpd);
 190
 191   LoadInst *combineLoadToNewType(LoadInst &LI, Type *NewTy,
 192                                  const Twine &Suffix = "");
 193
 194 private:
 195   void annotateAnyAllocSite(CallBase &Call, const TargetLibraryInfo *TLI);
 196   bool isDesirableIntType(unsigned BitWidth) const;
 197   bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
 198   bool shouldChangeType(Type *From, Type *To) const;
 199   Value *dyn_castNegVal(Value *V) const;
 200
 201   /// Classify whether a cast is worth optimizing.
 202   ///
 203   /// This is a helper to decide whether the simplification of
 204   /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
 205   ///
 206   /// \param CI The cast we are interested in.
 207   ///
 208   /// \return true if this cast actually results in any code being generated and
 209   /// if it cannot already be eliminated by some other transformation.
 210   bool shouldOptimizeCast(CastInst *CI);
 211
 212   /// Try to optimize a sequence of instructions checking if an operation
 213   /// on LHS and RHS overflows.
 214   ///
 215   /// If this overflow check is done via one of the overflow check intrinsics,
 216   /// then CtxI has to be the call instruction calling that intrinsic.  If this
 217   /// overflow check is done by arithmetic followed by a compare, then CtxI has
 218   /// to be the arithmetic instruction.
 219   ///
 220   /// If a simplification is possible, stores the simplified result of the
 221   /// operation in OperationResult and result of the overflow check in
 222   /// OverflowResult, and return true.  If no simplification is possible,
 223   /// returns false.
 224   bool OptimizeOverflowCheck(Instruction::BinaryOps BinaryOp, bool IsSigned,
 225                              Value *LHS, Value *RHS,
 226                              Instruction &CtxI, Value *&OperationResult,
 227                              Constant *&OverflowResult);
 228
 229   Instruction *visitCallBase(CallBase &Call);
 230   Instruction *tryOptimizeCall(CallInst *CI);
 231   bool transformConstExprCastCall(CallBase &Call);
 232   Instruction *transformCallThroughTrampoline(CallBase &Call,
 233                                               IntrinsicInst &Tramp);
 234
 235   Value *simplifyMaskedLoad(IntrinsicInst &II);
 236   Instruction *simplifyMaskedStore(IntrinsicInst &II);
 237   Instruction *simplifyMaskedGather(IntrinsicInst &II);
 238   Instruction *simplifyMaskedScatter(IntrinsicInst &II);
 239
 240   /// Transform (zext icmp) to bitwise / integer operations in order to
 241   /// eliminate it.
 242   ///
 243   /// \param ICI The icmp of the (zext icmp) pair we are interested in.
 244   /// \parem CI The zext of the (zext icmp) pair we are interested in.
 245   ///
 246   /// \return null if the transformation cannot be performed. If the
 247   /// transformation can be performed the new instruction that replaces the
 248   /// (zext icmp) pair will be returned.
 249   Instruction *transformZExtICmp(ICmpInst *ICI, ZExtInst &CI);
 250
 251   Instruction *transformSExtICmp(ICmpInst *ICI, Instruction &CI);
 252
 253   bool willNotOverflowSignedAdd(const Value *LHS, const Value *RHS,
 254                                 const Instruction &CxtI) const {
 255     return computeOverflowForSignedAdd(LHS, RHS, &CxtI) ==
 256            OverflowResult::NeverOverflows;
 257   }
 258
 259   bool willNotOverflowUnsignedAdd(const Value *LHS, const Value *RHS,
 260                                   const Instruction &CxtI) const {
 261     return computeOverflowForUnsignedAdd(LHS, RHS, &CxtI) ==
 262            OverflowResult::NeverOverflows;
 263   }
 264
 265   bool willNotOverflowAdd(const Value *LHS, const Value *RHS,
 266                           const Instruction &CxtI, bool IsSigned) const {
 267     return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CxtI)
 268                     : willNotOverflowUnsignedAdd(LHS, RHS, CxtI);
 269   }
 270
 271   bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
 272                                 const Instruction &CxtI) const {
 273     return computeOverflowForSignedSub(LHS, RHS, &CxtI) ==
 274            OverflowResult::NeverOverflows;
 275   }
 276
 277   bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
 278                                   const Instruction &CxtI) const {
 279     return computeOverflowForUnsignedSub(LHS, RHS, &CxtI) ==
 280            OverflowResult::NeverOverflows;
 281   }
 282
 283   bool willNotOverflowSub(const Value *LHS, const Value *RHS,
 284                           const Instruction &CxtI, bool IsSigned) const {
 285     return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CxtI)
 286                     : willNotOverflowUnsignedSub(LHS, RHS, CxtI);
 287   }
 288
 289   bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
 290                                 const Instruction &CxtI) const {
 291     return computeOverflowForSignedMul(LHS, RHS, &CxtI) ==
 292            OverflowResult::NeverOverflows;
 293   }
 294
 295   bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
 296                                   const Instruction &CxtI) const {
 297     return computeOverflowForUnsignedMul(LHS, RHS, &CxtI) ==
 298            OverflowResult::NeverOverflows;
 299   }
 300
 301   bool willNotOverflowMul(const Value *LHS, const Value *RHS,
 302                           const Instruction &CxtI, bool IsSigned) const {
 303     return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CxtI)
 304                     : willNotOverflowUnsignedMul(LHS, RHS, CxtI);
 305   }
 306
 307   bool willNotOverflow(BinaryOperator::BinaryOps Opcode, const Value *LHS,
 308                        const Value *RHS, const Instruction &CxtI,
 309                        bool IsSigned) const {
 310     switch (Opcode) {
 311     case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CxtI, IsSigned);
 312     case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CxtI, IsSigned);
 313     case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CxtI, IsSigned);
 314     default: llvm_unreachable("Unexpected opcode for overflow query");
 315     }
 316   }
 317
 318   Value *EmitGEPOffset(User *GEP);
 319   Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
 320   Instruction *foldBitcastExtElt(ExtractElementInst &ExtElt);
 321   Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
 322   Instruction *foldBinopOfSextBoolToSelect(BinaryOperator &I);
 323   Instruction *narrowBinOp(TruncInst &Trunc);
 324   Instruction *narrowMaskedBinOp(BinaryOperator &And);
 325   Instruction *narrowMathIfNoOverflow(BinaryOperator &I);
 326   Instruction *narrowFunnelShift(TruncInst &Trunc);
 327   Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
 328   Instruction *matchSAddSubSat(Instruction &MinMax1);
 329   Instruction *foldNot(BinaryOperator &I);
 330
 331   void freelyInvertAllUsersOf(Value *V);
 332
 333   /// Determine if a pair of casts can be replaced by a single cast.
 334   ///
 335   /// \param CI1 The first of a pair of casts.
 336   /// \param CI2 The second of a pair of casts.
 337   ///
 338   /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
 339   /// Instruction::CastOps value for a cast that can replace the pair, casting
 340   /// CI1->getSrcTy() to CI2->getDstTy().
 341   ///
 342   /// \see CastInst::isEliminableCastPair
 343   Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
 344                                             const CastInst *CI2);
 345   Value *simplifyIntToPtrRoundTripCast(Value *Val);
 346
 347   Value *foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &And);
 348   Value *foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Or);
 349   Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Xor);
 350
 351   Value *foldEqOfParts(ICmpInst *Cmp0, ICmpInst *Cmp1, bool IsAnd);
 352
 353   /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
 354   /// NOTE: Unlike most of instcombine, this returns a Value which should
 355   /// already be inserted into the function.
 356   Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd);
 357
 358   Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
 359                                        Instruction *CxtI, bool IsAnd,
 360                                        bool IsLogical = false);
 361   Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D);
 362   Value *getSelectCondition(Value *A, Value *B);
 363
 364   Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
 365   Instruction *foldFPSignBitOps(BinaryOperator &I);
 366
 367   // Optimize one of these forms:
 368   //   and i1 Op, SI / select i1 Op, i1 SI, i1 false (if IsAnd = true)
 369   //   or i1 Op, SI  / select i1 Op, i1 true, i1 SI  (if IsAnd = false)
 370   // into simplier select instruction using isImpliedCondition.
 371   Instruction *foldAndOrOfSelectUsingImpliedCond(Value *Op, SelectInst &SI,
 372                                                  bool IsAnd);
 373
 374 public:
 375   /// Inserts an instruction \p New before instruction \p Old
 376   ///
 377   /// Also adds the new instruction to the worklist and returns \p New so that
 378   /// it is suitable for use as the return from the visitation patterns.
 379   Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) {
 380     assert(New && !New->getParent() &&
 381            "New instruction already inserted into a basic block!");
 382     BasicBlock *BB = Old.getParent();
 383     BB->getInstList().insert(Old.getIterator(), New); // Insert inst
 384     Worklist.add(New);
 385     return New;
 386   }
 387
 388   /// Same as InsertNewInstBefore, but also sets the debug loc.
 389   Instruction *InsertNewInstWith(Instruction *New, Instruction &Old) {
 390     New->setDebugLoc(Old.getDebugLoc());
 391     return InsertNewInstBefore(New, Old);
 392   }
 393
 394   /// A combiner-aware RAUW-like routine.
 395   ///
 396   /// This method is to be used when an instruction is found to be dead,
 397   /// replaceable with another preexisting expression. Here we add all uses of
 398   /// I to the worklist, replace all uses of I with the new value, then return
 399   /// I, so that the inst combiner will know that I was modified.
 400   Instruction *replaceInstUsesWith(Instruction &I, Value *V) {
 401     // If there are no uses to replace, then we return nullptr to indicate that
 402     // no changes were made to the program.
 403     if (I.use_empty()) return nullptr;
 404
 405     Worklist.pushUsersToWorkList(I); // Add all modified instrs to worklist.
 406
 407     // If we are replacing the instruction with itself, this must be in a
 408     // segment of unreachable code, so just clobber the instruction.
 409     if (&I == V)
 410       V = UndefValue::get(I.getType());
 411
 412     LLVM_DEBUG(dbgs() << "IC: Replacing " << I << "\n"
 413                       << "    with " << *V << '\n');
 414
 415     I.replaceAllUsesWith(V);
 416     MadeIRChange = true;
 417     return &I;
 418   }
 419
 420   /// Replace operand of instruction and add old operand to the worklist.
 421   Instruction *replaceOperand(Instruction &I, unsigned OpNum, Value *V) {
 422     Worklist.addValue(I.getOperand(OpNum));
 423     I.setOperand(OpNum, V);
 424     return &I;
 425   }
 426
 427   /// Replace use and add the previously used value to the worklist.
 428   void replaceUse(Use &U, Value *NewValue) {
 429     Worklist.addValue(U);
 430     U = NewValue;
 431   }
 432
 433   /// Create and insert the idiom we use to indicate a block is unreachable
 434   /// without having to rewrite the CFG from within InstCombine.
 435   void CreateNonTerminatorUnreachable(Instruction *InsertAt) {
 436     auto &Ctx = InsertAt->getContext();
 437     new StoreInst(ConstantInt::getTrue(Ctx),
 438                   UndefValue::get(Type::getInt1PtrTy(Ctx)),
 439                   InsertAt);
 440   }
 441
 442
 443   /// Combiner aware instruction erasure.
 444   ///
 445   /// When dealing with an instruction that has side effects or produces a void
 446   /// value, we can't rely on DCE to delete the instruction. Instead, visit
 447   /// methods should return the value returned by this function.
 448   Instruction *eraseInstFromFunction(Instruction &I) override {
 449     LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n');
 450     assert(I.use_empty() && "Cannot erase instruction that is used!");
 451     salvageDebugInfo(I);
 452
 453     // Make sure that we reprocess all operands now that we reduced their
 454     // use counts.
 455     for (Use &Operand : I.operands())
 456       if (auto *Inst = dyn_cast<Instruction>(Operand))
 457         Worklist.add(Inst);
 458
 459     Worklist.remove(&I);
 460     I.eraseFromParent();
 461     MadeIRChange = true;
 462     return nullptr; // Don't do anything with FI
 463   }
 464
 465   void computeKnownBits(const Value *V, KnownBits &Known,
 466                         unsigned Depth, const Instruction *CxtI) const {
 467     llvm::computeKnownBits(V, Known, DL, Depth, &AC, CxtI, &DT);
 468   }
 469
 470   KnownBits computeKnownBits(const Value *V, unsigned Depth,
 471                              const Instruction *CxtI) const {
 472     return llvm::computeKnownBits(V, DL, Depth, &AC, CxtI, &DT);
 473   }
 474
 475   bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero = false,
 476                               unsigned Depth = 0,
 477                               const Instruction *CxtI = nullptr) {
 478     return llvm::isKnownToBeAPowerOfTwo(V, DL, OrZero, Depth, &AC, CxtI, &DT);
 479   }
 480
 481   bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth = 0,
 482                          const Instruction *CxtI = nullptr) const {
 483     return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT);
 484   }
 485
 486   unsigned ComputeNumSignBits(const Value *Op, unsigned Depth = 0,
 487                               const Instruction *CxtI = nullptr) const {
 488     return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
 489   }
 490
 491   OverflowResult computeOverflowForUnsignedMul(const Value *LHS,
 492                                                const Value *RHS,
 493                                                const Instruction *CxtI) const {
 494     return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
 495   }
 496
 497   OverflowResult computeOverflowForSignedMul(const Value *LHS,
 498                                              const Value *RHS,
 499                                              const Instruction *CxtI) const {
 500     return llvm::computeOverflowForSignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
 501   }
 502
 503   OverflowResult computeOverflowForUnsignedAdd(const Value *LHS,
 504                                                const Value *RHS,
 505                                                const Instruction *CxtI) const {
 506     return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
 507   }
 508
 509   OverflowResult computeOverflowForSignedAdd(const Value *LHS,
 510                                              const Value *RHS,
 511                                              const Instruction *CxtI) const {
 512     return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
 513   }
 514
 515   OverflowResult computeOverflowForUnsignedSub(const Value *LHS,
 516                                                const Value *RHS,
 517                                                const Instruction *CxtI) const {
 518     return llvm::computeOverflowForUnsignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
 519   }
 520
 521   OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS,
 522                                              const Instruction *CxtI) const {
 523     return llvm::computeOverflowForSignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
 524   }
 525
 526   OverflowResult computeOverflow(
 527       Instruction::BinaryOps BinaryOp, bool IsSigned,
 528       Value *LHS, Value *RHS, Instruction *CxtI) const;
 529
 530   /// Performs a few simplifications for operators which are associative
 531   /// or commutative.
 532   bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
 533
 534   /// Tries to simplify binary operations which some other binary
 535   /// operation distributes over.
 536   ///
 537   /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
 538   /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
 539   /// & (B | C) -> (A&B) | (A&C)" if this is a win).  Returns the simplified
 540   /// value, or null if it didn't simplify.
 541   Value *SimplifyUsingDistributiveLaws(BinaryOperator &I);
 542
 543   /// Tries to simplify add operations using the definition of remainder.
 544   ///
 545   /// The definition of remainder is X % C = X - (X / C ) * C. The add
 546   /// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to
 547   /// X % (C0 * C1)
 548   Value *SimplifyAddWithRemainder(BinaryOperator &I);
 549
 550   // Binary Op helper for select operations where the expression can be
 551   // efficiently reorganized.
 552   Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
 553                                         Value *RHS);
 554
 555   /// This tries to simplify binary operations by factorizing out common terms
 556   /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
 557   Value *tryFactorization(BinaryOperator &, Instruction::BinaryOps, Value *,
 558                           Value *, Value *, Value *);
 559
 560   /// Match a select chain which produces one of three values based on whether
 561   /// the LHS is less than, equal to, or greater than RHS respectively.
 562   /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
 563   /// Equal and Greater values are saved in the matching process and returned to
 564   /// the caller.
 565   bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
 566                                ConstantInt *&Less, ConstantInt *&Equal,
 567                                ConstantInt *&Greater);
 568
 569   /// Attempts to replace V with a simpler value based on the demanded
 570   /// bits.
 571   Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known,
 572                                  unsigned Depth, Instruction *CxtI);
 573   bool SimplifyDemandedBits(Instruction *I, unsigned Op,
 574                             const APInt &DemandedMask, KnownBits &Known,
 575                             unsigned Depth = 0) override;
 576
 577   /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
 578   /// bits. It also tries to handle simplifications that can be done based on
 579   /// DemandedMask, but without modifying the Instruction.
 580   Value *SimplifyMultipleUseDemandedBits(Instruction *I,
 581                                          const APInt &DemandedMask,
 582                                          KnownBits &Known,
 583                                          unsigned Depth, Instruction *CxtI);
 584
 585   /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
 586   /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
 587   Value *simplifyShrShlDemandedBits(
 588       Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
 589       const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
 590
 591   /// Tries to simplify operands to an integer instruction based on its
 592   /// demanded bits.
 593   bool SimplifyDemandedInstructionBits(Instruction &Inst);
 594
 595   virtual Value *
 596   SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &UndefElts,
 597                              unsigned Depth = 0,
 598                              bool AllowMultipleUsers = false) override;
 599
 600   /// Canonicalize the position of binops relative to shufflevector.
 601   Instruction *foldVectorBinop(BinaryOperator &Inst);
 602   Instruction *foldVectorSelect(SelectInst &Sel);
 603   Instruction *foldSelectShuffle(ShuffleVectorInst &Shuf);
 604
 605   /// Given a binary operator, cast instruction, or select which has a PHI node
 606   /// as operand #0, see if we can fold the instruction into the PHI (which is
 607   /// only possible if all operands to the PHI are constants).
 608   Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN);
 609
 610   /// For a binary operator with 2 phi operands, try to hoist the binary
 611   /// operation before the phi. This can result in fewer instructions in
 612   /// patterns where at least one set of phi operands simplifies.
 613   /// Example:
 614   /// BB3: binop (phi [X, BB1], [C1, BB2]), (phi [Y, BB1], [C2, BB2])
 615   /// -->
 616   /// BB1: BO = binop X, Y
 617   /// BB3: phi [BO, BB1], [(binop C1, C2), BB2]
 618   Instruction *foldBinopWithPhiOperands(BinaryOperator &BO);
 619
 620   /// Given an instruction with a select as one operand and a constant as the
 621   /// other operand, try to fold the binary operator into the select arguments.
 622   /// This also works for Cast instructions, which obviously do not have a
 623   /// second operand.
 624   Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI);
 625
 626   /// This is a convenience wrapper function for the above two functions.
 627   Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
 628
 629   Instruction *foldAddWithConstant(BinaryOperator &Add);
 630
 631   /// Try to rotate an operation below a PHI node, using PHI nodes for
 632   /// its operands.
 633   Instruction *foldPHIArgOpIntoPHI(PHINode &PN);
 634   Instruction *foldPHIArgBinOpIntoPHI(PHINode &PN);
 635   Instruction *foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN);
 636   Instruction *foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN);
 637   Instruction *foldPHIArgGEPIntoPHI(PHINode &PN);
 638   Instruction *foldPHIArgLoadIntoPHI(PHINode &PN);
 639   Instruction *foldPHIArgZextsIntoPHI(PHINode &PN);
 640   Instruction *foldPHIArgIntToPtrToPHI(PHINode &PN);
 641
 642   /// If an integer typed PHI has only one use which is an IntToPtr operation,
 643   /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
 644   /// insert a new pointer typed PHI and replace the original one.
 645   Instruction *foldIntegerTypedPHI(PHINode &PN);
 646
 647   /// Helper function for FoldPHIArgXIntoPHI() to set debug location for the
 648   /// folded operation.
 649   void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN);
 650
 651   Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
 652                            ICmpInst::Predicate Cond, Instruction &I);
 653   Instruction *foldAllocaCmp(ICmpInst &ICI, const AllocaInst *Alloca,
 654                              const Value *Other);
 655   Instruction *foldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP,
 656                                             GlobalVariable *GV, CmpInst &ICI,
 657                                             ConstantInt *AndCst = nullptr);
 658   Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
 659                                     Constant *RHSC);
 660   Instruction *foldICmpAddOpConst(Value *X, const APInt &C,
 661                                   ICmpInst::Predicate Pred);
 662   Instruction *foldICmpWithCastOp(ICmpInst &ICI);
 663
 664   Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
 665   Instruction *foldICmpWithDominatingICmp(ICmpInst &Cmp);
 666   Instruction *foldICmpWithConstant(ICmpInst &Cmp);
 667   Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
 668   Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
 669   Instruction *foldICmpBinOp(ICmpInst &Cmp, const SimplifyQuery &SQ);
 670   Instruction *foldICmpEquality(ICmpInst &Cmp);
 671   Instruction *foldIRemByPowerOfTwoToBitTest(ICmpInst &I);
 672   Instruction *foldSignBitTest(ICmpInst &I);
 673   Instruction *foldICmpWithZero(ICmpInst &Cmp);
 674
 675   Value *foldMultiplicationOverflowCheck(ICmpInst &Cmp);
 676
 677   Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,
 678                                       ConstantInt *C);
 679   Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc,
 680                                      const APInt &C);
 681   Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
 682                                    const APInt &C);
 683   Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
 684                                    const APInt &C);
 685   Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
 686                                   const APInt &C);
 687   Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
 688                                    const APInt &C);
 689   Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
 690                                    const APInt &C);
 691   Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
 692                                    const APInt &C);
 693   Instruction *foldICmpSRemConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
 694                                     const APInt &C);
 695   Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
 696                                     const APInt &C);
 697   Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
 698                                    const APInt &C);
 699   Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
 700                                    const APInt &C);
 701   Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
 702                                    const APInt &C);
 703   Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
 704                                      const APInt &C1);
 705   Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
 706                                 const APInt &C1, const APInt &C2);
 707   Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
 708                                      const APInt &C2);
 709   Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
 710                                      const APInt &C2);
 711
 712   Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
 713                                                  BinaryOperator *BO,
 714                                                  const APInt &C);
 715   Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
 716                                              const APInt &C);
 717   Instruction *foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
 718                                                const APInt &C);
 719   Instruction *foldICmpBitCast(ICmpInst &Cmp);
 720
 721   // Helpers of visitSelectInst().
 722   Instruction *foldSelectExtConst(SelectInst &Sel);
 723   Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
 724   Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
 725   Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1,
 726                             Value *A, Value *B, Instruction &Outer,
 727                             SelectPatternFlavor SPF2, Value *C);
 728   Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI);
 729   Instruction *foldSelectValueEquivalence(SelectInst &SI, ICmpInst &ICI);
 730
 731   Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
 732                          bool isSigned, bool Inside);
 733   Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI);
 734   bool mergeStoreIntoSuccessor(StoreInst &SI);
 735
 736   /// Given an initial instruction, check to see if it is the root of a
 737   /// bswap/bitreverse idiom. If so, return the equivalent bswap/bitreverse
 738   /// intrinsic.
 739   Instruction *matchBSwapOrBitReverse(Instruction &I, bool MatchBSwaps,
 740                                       bool MatchBitReversals);
 741
 742   Instruction *SimplifyAnyMemTransfer(AnyMemTransferInst *MI);
 743   Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI);
 744
 745   Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
 746
 747   /// Returns a value X such that Val = X * Scale, or null if none.
 748   ///
 749   /// If the multiplication is known not to overflow then NoSignedWrap is set.
 750   Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
 751 };
 752
 753 class Negator final {
 754   /// Top-to-bottom, def-to-use negated instruction tree we produced.
 755   SmallVector<Instruction *, NegatorMaxNodesSSO> NewInstructions;
 756
 757   using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
 758   BuilderTy Builder;
 759
 760   const DataLayout &DL;
 761   AssumptionCache &AC;
 762   const DominatorTree &DT;
 763
 764   const bool IsTrulyNegation;
 765
 766   SmallDenseMap<Value *, Value *> NegationsCache;
 767
 768   Negator(LLVMContext &C, const DataLayout &DL, AssumptionCache &AC,
 769           const DominatorTree &DT, bool IsTrulyNegation);
 770
 771 #if LLVM_ENABLE_STATS
 772   unsigned NumValuesVisitedInThisNegator = 0;
 773   ~Negator();
 774 #endif
 775
 776   using Result = std::pair<ArrayRef<Instruction *> /*NewInstructions*/,
 777                            Value * /*NegatedRoot*/>;
 778
 779   std::array<Value *, 2> getSortedOperandsOfBinOp(Instruction *I);
 780
 781   LLVM_NODISCARD Value *visitImpl(Value *V, unsigned Depth);
 782
 783   LLVM_NODISCARD Value *negate(Value *V, unsigned Depth);
 784
 785   /// Recurse depth-first and attempt to sink the negation.
 786   /// FIXME: use worklist?
 787   LLVM_NODISCARD Optional<Result> run(Value *Root);
 788
 789   Negator(const Negator &) = delete;
 790   Negator(Negator &&) = delete;
 791   Negator &operator=(const Negator &) = delete;
 792   Negator &operator=(Negator &&) = delete;
 793
 794 public:
 795   /// Attempt to negate \p Root. Retuns nullptr if negation can't be performed,
 796   /// otherwise returns negated value.
 797   LLVM_NODISCARD static Value *Negate(bool LHSIsZero, Value *Root,
 798                                       InstCombinerImpl &IC);
 799 };
 800
 801 } // end namespace llvm
 802
 803 #undef DEBUG_TYPE
 804
 805 #endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H