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/InstCombineWorklist.h"
  29 #include "llvm/Transforms/InstCombine/InstCombiner.h"
  30 #include "llvm/Transforms/Utils/Local.h"
  31 #include <cassert>
  32
  33 #define DEBUG_TYPE "instcombine"
  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(InstCombineWorklist &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 *visitAllocaInst(AllocaInst &AI);
 152   Instruction *visitAllocSite(Instruction &FI);
 153   Instruction *visitFree(CallInst &FI);
 154   Instruction *visitLoadInst(LoadInst &LI);
 155   Instruction *visitStoreInst(StoreInst &SI);
 156   Instruction *visitAtomicRMWInst(AtomicRMWInst &SI);
 157   Instruction *visitUnconditionalBranchInst(BranchInst &BI);
 158   Instruction *visitBranchInst(BranchInst &BI);
 159   Instruction *visitFenceInst(FenceInst &FI);
 160   Instruction *visitSwitchInst(SwitchInst &SI);
 161   Instruction *visitReturnInst(ReturnInst &RI);
 162   Instruction *visitUnreachableInst(UnreachableInst &I);
 163   Instruction *
 164   foldAggregateConstructionIntoAggregateReuse(InsertValueInst &OrigIVI);
 165   Instruction *visitInsertValueInst(InsertValueInst &IV);
 166   Instruction *visitInsertElementInst(InsertElementInst &IE);
 167   Instruction *visitExtractElementInst(ExtractElementInst &EI);
 168   Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
 169   Instruction *visitExtractValueInst(ExtractValueInst &EV);
 170   Instruction *visitLandingPadInst(LandingPadInst &LI);
 171   Instruction *visitVAEndInst(VAEndInst &I);
 172   Value *pushFreezeToPreventPoisonFromPropagating(FreezeInst &FI);
 173   bool freezeDominatedUses(FreezeInst &FI);
 174   Instruction *visitFreeze(FreezeInst &I);
 175
 176   /// Specify what to return for unhandled instructions.
 177   Instruction *visitInstruction(Instruction &I) { return nullptr; }
 178
 179   /// True when DB dominates all uses of DI except UI.
 180   /// UI must be in the same block as DI.
 181   /// The routine checks that the DI parent and DB are different.
 182   bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
 183                         const BasicBlock *DB) const;
 184
 185   /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
 186   bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
 187                                  const unsigned SIOpd);
 188
 189   LoadInst *combineLoadToNewType(LoadInst &LI, Type *NewTy,
 190                                  const Twine &Suffix = "");
 191
 192 private:
 193   void annotateAnyAllocSite(CallBase &Call, const TargetLibraryInfo *TLI);
 194   bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
 195   bool shouldChangeType(Type *From, Type *To) const;
 196   Value *dyn_castNegVal(Value *V) const;
 197   Type *FindElementAtOffset(PointerType *PtrTy, int64_t Offset,
 198                             SmallVectorImpl<Value *> &NewIndices);
 199
 200   /// Classify whether a cast is worth optimizing.
 201   ///
 202   /// This is a helper to decide whether the simplification of
 203   /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
 204   ///
 205   /// \param CI The cast we are interested in.
 206   ///
 207   /// \return true if this cast actually results in any code being generated and
 208   /// if it cannot already be eliminated by some other transformation.
 209   bool shouldOptimizeCast(CastInst *CI);
 210
 211   /// Try to optimize a sequence of instructions checking if an operation
 212   /// on LHS and RHS overflows.
 213   ///
 214   /// If this overflow check is done via one of the overflow check intrinsics,
 215   /// then CtxI has to be the call instruction calling that intrinsic.  If this
 216   /// overflow check is done by arithmetic followed by a compare, then CtxI has
 217   /// to be the arithmetic instruction.
 218   ///
 219   /// If a simplification is possible, stores the simplified result of the
 220   /// operation in OperationResult and result of the overflow check in
 221   /// OverflowResult, and return true.  If no simplification is possible,
 222   /// returns false.
 223   bool OptimizeOverflowCheck(Instruction::BinaryOps BinaryOp, bool IsSigned,
 224                              Value *LHS, Value *RHS,
 225                              Instruction &CtxI, Value *&OperationResult,
 226                              Constant *&OverflowResult);
 227
 228   Instruction *visitCallBase(CallBase &Call);
 229   Instruction *tryOptimizeCall(CallInst *CI);
 230   bool transformConstExprCastCall(CallBase &Call);
 231   Instruction *transformCallThroughTrampoline(CallBase &Call,
 232                                               IntrinsicInst &Tramp);
 233
 234   Value *simplifyMaskedLoad(IntrinsicInst &II);
 235   Instruction *simplifyMaskedStore(IntrinsicInst &II);
 236   Instruction *simplifyMaskedGather(IntrinsicInst &II);
 237   Instruction *simplifyMaskedScatter(IntrinsicInst &II);
 238
 239   /// Transform (zext icmp) to bitwise / integer operations in order to
 240   /// eliminate it.
 241   ///
 242   /// \param ICI The icmp of the (zext icmp) pair we are interested in.
 243   /// \parem CI The zext of the (zext icmp) pair we are interested in.
 244   /// \param DoTransform Pass false to just test whether the given (zext icmp)
 245   /// would be transformed. Pass true to actually perform the transformation.
 246   ///
 247   /// \return null if the transformation cannot be performed. If the
 248   /// transformation can be performed the new instruction that replaces the
 249   /// (zext icmp) pair will be returned (if \p DoTransform is false the
 250   /// unmodified \p ICI will be returned in this case).
 251   Instruction *transformZExtICmp(ICmpInst *ICI, ZExtInst &CI,
 252                                  bool DoTransform = true);
 253
 254   Instruction *transformSExtICmp(ICmpInst *ICI, Instruction &CI);
 255
 256   bool willNotOverflowSignedAdd(const Value *LHS, const Value *RHS,
 257                                 const Instruction &CxtI) const {
 258     return computeOverflowForSignedAdd(LHS, RHS, &CxtI) ==
 259            OverflowResult::NeverOverflows;
 260   }
 261
 262   bool willNotOverflowUnsignedAdd(const Value *LHS, const Value *RHS,
 263                                   const Instruction &CxtI) const {
 264     return computeOverflowForUnsignedAdd(LHS, RHS, &CxtI) ==
 265            OverflowResult::NeverOverflows;
 266   }
 267
 268   bool willNotOverflowAdd(const Value *LHS, const Value *RHS,
 269                           const Instruction &CxtI, bool IsSigned) const {
 270     return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CxtI)
 271                     : willNotOverflowUnsignedAdd(LHS, RHS, CxtI);
 272   }
 273
 274   bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
 275                                 const Instruction &CxtI) const {
 276     return computeOverflowForSignedSub(LHS, RHS, &CxtI) ==
 277            OverflowResult::NeverOverflows;
 278   }
 279
 280   bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
 281                                   const Instruction &CxtI) const {
 282     return computeOverflowForUnsignedSub(LHS, RHS, &CxtI) ==
 283            OverflowResult::NeverOverflows;
 284   }
 285
 286   bool willNotOverflowSub(const Value *LHS, const Value *RHS,
 287                           const Instruction &CxtI, bool IsSigned) const {
 288     return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CxtI)
 289                     : willNotOverflowUnsignedSub(LHS, RHS, CxtI);
 290   }
 291
 292   bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
 293                                 const Instruction &CxtI) const {
 294     return computeOverflowForSignedMul(LHS, RHS, &CxtI) ==
 295            OverflowResult::NeverOverflows;
 296   }
 297
 298   bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
 299                                   const Instruction &CxtI) const {
 300     return computeOverflowForUnsignedMul(LHS, RHS, &CxtI) ==
 301            OverflowResult::NeverOverflows;
 302   }
 303
 304   bool willNotOverflowMul(const Value *LHS, const Value *RHS,
 305                           const Instruction &CxtI, bool IsSigned) const {
 306     return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CxtI)
 307                     : willNotOverflowUnsignedMul(LHS, RHS, CxtI);
 308   }
 309
 310   bool willNotOverflow(BinaryOperator::BinaryOps Opcode, const Value *LHS,
 311                        const Value *RHS, const Instruction &CxtI,
 312                        bool IsSigned) const {
 313     switch (Opcode) {
 314     case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CxtI, IsSigned);
 315     case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CxtI, IsSigned);
 316     case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CxtI, IsSigned);
 317     default: llvm_unreachable("Unexpected opcode for overflow query");
 318     }
 319   }
 320
 321   Value *EmitGEPOffset(User *GEP);
 322   Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
 323   Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
 324   Instruction *narrowBinOp(TruncInst &Trunc);
 325   Instruction *narrowMaskedBinOp(BinaryOperator &And);
 326   Instruction *narrowMathIfNoOverflow(BinaryOperator &I);
 327   Instruction *narrowFunnelShift(TruncInst &Trunc);
 328   Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
 329   Instruction *matchSAddSubSat(Instruction &MinMax1);
 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   /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
 352   /// NOTE: Unlike most of instcombine, this returns a Value which should
 353   /// already be inserted into the function.
 354   Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd);
 355
 356   Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
 357                                        Instruction *CxtI, bool IsAnd,
 358                                        bool IsLogical = false);
 359   Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D);
 360   Value *getSelectCondition(Value *A, Value *B);
 361
 362   Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
 363   Instruction *foldFPSignBitOps(BinaryOperator &I);
 364
 365   // Optimize one of these forms:
 366   //   and i1 Op, SI / select i1 Op, i1 SI, i1 false (if IsAnd = true)
 367   //   or i1 Op, SI  / select i1 Op, i1 true, i1 SI  (if IsAnd = false)
 368   // into simplier select instruction using isImpliedCondition.
 369   Instruction *foldAndOrOfSelectUsingImpliedCond(Value *Op, SelectInst &SI,
 370                                                  bool IsAnd);
 371
 372 public:
 373   /// Inserts an instruction \p New before instruction \p Old
 374   ///
 375   /// Also adds the new instruction to the worklist and returns \p New so that
 376   /// it is suitable for use as the return from the visitation patterns.
 377   Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) {
 378     assert(New && !New->getParent() &&
 379            "New instruction already inserted into a basic block!");
 380     BasicBlock *BB = Old.getParent();
 381     BB->getInstList().insert(Old.getIterator(), New); // Insert inst
 382     Worklist.add(New);
 383     return New;
 384   }
 385
 386   /// Same as InsertNewInstBefore, but also sets the debug loc.
 387   Instruction *InsertNewInstWith(Instruction *New, Instruction &Old) {
 388     New->setDebugLoc(Old.getDebugLoc());
 389     return InsertNewInstBefore(New, Old);
 390   }
 391
 392   /// A combiner-aware RAUW-like routine.
 393   ///
 394   /// This method is to be used when an instruction is found to be dead,
 395   /// replaceable with another preexisting expression. Here we add all uses of
 396   /// I to the worklist, replace all uses of I with the new value, then return
 397   /// I, so that the inst combiner will know that I was modified.
 398   Instruction *replaceInstUsesWith(Instruction &I, Value *V) {
 399     // If there are no uses to replace, then we return nullptr to indicate that
 400     // no changes were made to the program.
 401     if (I.use_empty()) return nullptr;
 402
 403     Worklist.pushUsersToWorkList(I); // Add all modified instrs to worklist.
 404
 405     // If we are replacing the instruction with itself, this must be in a
 406     // segment of unreachable code, so just clobber the instruction.
 407     if (&I == V)
 408       V = UndefValue::get(I.getType());
 409
 410     LLVM_DEBUG(dbgs() << "IC: Replacing " << I << "\n"
 411                       << "    with " << *V << '\n');
 412
 413     I.replaceAllUsesWith(V);
 414     MadeIRChange = true;
 415     return &I;
 416   }
 417
 418   /// Replace operand of instruction and add old operand to the worklist.
 419   Instruction *replaceOperand(Instruction &I, unsigned OpNum, Value *V) {
 420     Worklist.addValue(I.getOperand(OpNum));
 421     I.setOperand(OpNum, V);
 422     return &I;
 423   }
 424
 425   /// Replace use and add the previously used value to the worklist.
 426   void replaceUse(Use &U, Value *NewValue) {
 427     Worklist.addValue(U);
 428     U = NewValue;
 429   }
 430
 431   /// Create and insert the idiom we use to indicate a block is unreachable
 432   /// without having to rewrite the CFG from within InstCombine.
 433   void CreateNonTerminatorUnreachable(Instruction *InsertAt) {
 434     auto &Ctx = InsertAt->getContext();
 435     new StoreInst(ConstantInt::getTrue(Ctx),
 436                   UndefValue::get(Type::getInt1PtrTy(Ctx)),
 437                   InsertAt);
 438   }
 439
 440
 441   /// Combiner aware instruction erasure.
 442   ///
 443   /// When dealing with an instruction that has side effects or produces a void
 444   /// value, we can't rely on DCE to delete the instruction. Instead, visit
 445   /// methods should return the value returned by this function.
 446   Instruction *eraseInstFromFunction(Instruction &I) override {
 447     LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n');
 448     assert(I.use_empty() && "Cannot erase instruction that is used!");
 449     salvageDebugInfo(I);
 450
 451     // Make sure that we reprocess all operands now that we reduced their
 452     // use counts.
 453     for (Use &Operand : I.operands())
 454       if (auto *Inst = dyn_cast<Instruction>(Operand))
 455         Worklist.add(Inst);
 456
 457     Worklist.remove(&I);
 458     I.eraseFromParent();
 459     MadeIRChange = true;
 460     return nullptr; // Don't do anything with FI
 461   }
 462
 463   void computeKnownBits(const Value *V, KnownBits &Known,
 464                         unsigned Depth, const Instruction *CxtI) const {
 465     llvm::computeKnownBits(V, Known, DL, Depth, &AC, CxtI, &DT);
 466   }
 467
 468   KnownBits computeKnownBits(const Value *V, unsigned Depth,
 469                              const Instruction *CxtI) const {
 470     return llvm::computeKnownBits(V, DL, Depth, &AC, CxtI, &DT);
 471   }
 472
 473   bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero = false,
 474                               unsigned Depth = 0,
 475                               const Instruction *CxtI = nullptr) {
 476     return llvm::isKnownToBeAPowerOfTwo(V, DL, OrZero, Depth, &AC, CxtI, &DT);
 477   }
 478
 479   bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth = 0,
 480                          const Instruction *CxtI = nullptr) const {
 481     return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT);
 482   }
 483
 484   unsigned ComputeNumSignBits(const Value *Op, unsigned Depth = 0,
 485                               const Instruction *CxtI = nullptr) const {
 486     return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
 487   }
 488
 489   OverflowResult computeOverflowForUnsignedMul(const Value *LHS,
 490                                                const Value *RHS,
 491                                                const Instruction *CxtI) const {
 492     return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
 493   }
 494
 495   OverflowResult computeOverflowForSignedMul(const Value *LHS,
 496                                              const Value *RHS,
 497                                              const Instruction *CxtI) const {
 498     return llvm::computeOverflowForSignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
 499   }
 500
 501   OverflowResult computeOverflowForUnsignedAdd(const Value *LHS,
 502                                                const Value *RHS,
 503                                                const Instruction *CxtI) const {
 504     return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
 505   }
 506
 507   OverflowResult computeOverflowForSignedAdd(const Value *LHS,
 508                                              const Value *RHS,
 509                                              const Instruction *CxtI) const {
 510     return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
 511   }
 512
 513   OverflowResult computeOverflowForUnsignedSub(const Value *LHS,
 514                                                const Value *RHS,
 515                                                const Instruction *CxtI) const {
 516     return llvm::computeOverflowForUnsignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
 517   }
 518
 519   OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS,
 520                                              const Instruction *CxtI) const {
 521     return llvm::computeOverflowForSignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
 522   }
 523
 524   OverflowResult computeOverflow(
 525       Instruction::BinaryOps BinaryOp, bool IsSigned,
 526       Value *LHS, Value *RHS, Instruction *CxtI) const;
 527
 528   /// Performs a few simplifications for operators which are associative
 529   /// or commutative.
 530   bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
 531
 532   /// Tries to simplify binary operations which some other binary
 533   /// operation distributes over.
 534   ///
 535   /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
 536   /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
 537   /// & (B | C) -> (A&B) | (A&C)" if this is a win).  Returns the simplified
 538   /// value, or null if it didn't simplify.
 539   Value *SimplifyUsingDistributiveLaws(BinaryOperator &I);
 540
 541   /// Tries to simplify add operations using the definition of remainder.
 542   ///
 543   /// The definition of remainder is X % C = X - (X / C ) * C. The add
 544   /// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to
 545   /// X % (C0 * C1)
 546   Value *SimplifyAddWithRemainder(BinaryOperator &I);
 547
 548   // Binary Op helper for select operations where the expression can be
 549   // efficiently reorganized.
 550   Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
 551                                         Value *RHS);
 552
 553   /// This tries to simplify binary operations by factorizing out common terms
 554   /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
 555   Value *tryFactorization(BinaryOperator &, Instruction::BinaryOps, Value *,
 556                           Value *, Value *, Value *);
 557
 558   /// Match a select chain which produces one of three values based on whether
 559   /// the LHS is less than, equal to, or greater than RHS respectively.
 560   /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
 561   /// Equal and Greater values are saved in the matching process and returned to
 562   /// the caller.
 563   bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
 564                                ConstantInt *&Less, ConstantInt *&Equal,
 565                                ConstantInt *&Greater);
 566
 567   /// Attempts to replace V with a simpler value based on the demanded
 568   /// bits.
 569   Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known,
 570                                  unsigned Depth, Instruction *CxtI);
 571   bool SimplifyDemandedBits(Instruction *I, unsigned Op,
 572                             const APInt &DemandedMask, KnownBits &Known,
 573                             unsigned Depth = 0) override;
 574
 575   /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
 576   /// bits. It also tries to handle simplifications that can be done based on
 577   /// DemandedMask, but without modifying the Instruction.
 578   Value *SimplifyMultipleUseDemandedBits(Instruction *I,
 579                                          const APInt &DemandedMask,
 580                                          KnownBits &Known,
 581                                          unsigned Depth, Instruction *CxtI);
 582
 583   /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
 584   /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
 585   Value *simplifyShrShlDemandedBits(
 586       Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
 587       const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
 588
 589   /// Tries to simplify operands to an integer instruction based on its
 590   /// demanded bits.
 591   bool SimplifyDemandedInstructionBits(Instruction &Inst);
 592
 593   virtual Value *
 594   SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &UndefElts,
 595                              unsigned Depth = 0,
 596                              bool AllowMultipleUsers = false) override;
 597
 598   /// Canonicalize the position of binops relative to shufflevector.
 599   Instruction *foldVectorBinop(BinaryOperator &Inst);
 600   Instruction *foldVectorSelect(SelectInst &Sel);
 601
 602   /// Given a binary operator, cast instruction, or select which has a PHI node
 603   /// as operand #0, see if we can fold the instruction into the PHI (which is
 604   /// only possible if all operands to the PHI are constants).
 605   Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN);
 606
 607   /// Given an instruction with a select as one operand and a constant as the
 608   /// other operand, try to fold the binary operator into the select arguments.
 609   /// This also works for Cast instructions, which obviously do not have a
 610   /// second operand.
 611   Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI);
 612
 613   /// This is a convenience wrapper function for the above two functions.
 614   Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
 615
 616   Instruction *foldAddWithConstant(BinaryOperator &Add);
 617
 618   /// Try to rotate an operation below a PHI node, using PHI nodes for
 619   /// its operands.
 620   Instruction *foldPHIArgOpIntoPHI(PHINode &PN);
 621   Instruction *foldPHIArgBinOpIntoPHI(PHINode &PN);
 622   Instruction *foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN);
 623   Instruction *foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN);
 624   Instruction *foldPHIArgGEPIntoPHI(PHINode &PN);
 625   Instruction *foldPHIArgLoadIntoPHI(PHINode &PN);
 626   Instruction *foldPHIArgZextsIntoPHI(PHINode &PN);
 627   Instruction *foldPHIArgIntToPtrToPHI(PHINode &PN);
 628
 629   /// If an integer typed PHI has only one use which is an IntToPtr operation,
 630   /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
 631   /// insert a new pointer typed PHI and replace the original one.
 632   Instruction *foldIntegerTypedPHI(PHINode &PN);
 633
 634   /// Helper function for FoldPHIArgXIntoPHI() to set debug location for the
 635   /// folded operation.
 636   void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN);
 637
 638   Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
 639                            ICmpInst::Predicate Cond, Instruction &I);
 640   Instruction *foldAllocaCmp(ICmpInst &ICI, const AllocaInst *Alloca,
 641                              const Value *Other);
 642   Instruction *foldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP,
 643                                             GlobalVariable *GV, CmpInst &ICI,
 644                                             ConstantInt *AndCst = nullptr);
 645   Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
 646                                     Constant *RHSC);
 647   Instruction *foldICmpAddOpConst(Value *X, const APInt &C,
 648                                   ICmpInst::Predicate Pred);
 649   Instruction *foldICmpWithCastOp(ICmpInst &ICI);
 650
 651   Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
 652   Instruction *foldICmpWithDominatingICmp(ICmpInst &Cmp);
 653   Instruction *foldICmpWithConstant(ICmpInst &Cmp);
 654   Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
 655   Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
 656   Instruction *foldICmpBinOp(ICmpInst &Cmp, const SimplifyQuery &SQ);
 657   Instruction *foldICmpEquality(ICmpInst &Cmp);
 658   Instruction *foldIRemByPowerOfTwoToBitTest(ICmpInst &I);
 659   Instruction *foldSignBitTest(ICmpInst &I);
 660   Instruction *foldICmpWithZero(ICmpInst &Cmp);
 661
 662   Value *foldUnsignedMultiplicationOverflowCheck(ICmpInst &Cmp);
 663
 664   Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,
 665                                       ConstantInt *C);
 666   Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc,
 667                                      const APInt &C);
 668   Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
 669                                    const APInt &C);
 670   Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
 671                                    const APInt &C);
 672   Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
 673                                   const APInt &C);
 674   Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
 675                                    const APInt &C);
 676   Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
 677                                    const APInt &C);
 678   Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
 679                                    const APInt &C);
 680   Instruction *foldICmpSRemConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
 681                                     const APInt &C);
 682   Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
 683                                     const APInt &C);
 684   Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
 685                                    const APInt &C);
 686   Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
 687                                    const APInt &C);
 688   Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
 689                                    const APInt &C);
 690   Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
 691                                      const APInt &C1);
 692   Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
 693                                 const APInt &C1, const APInt &C2);
 694   Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
 695                                      const APInt &C2);
 696   Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
 697                                      const APInt &C2);
 698
 699   Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
 700                                                  BinaryOperator *BO,
 701                                                  const APInt &C);
 702   Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
 703                                              const APInt &C);
 704   Instruction *foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
 705                                                const APInt &C);
 706   Instruction *foldICmpBitCast(ICmpInst &Cmp);
 707
 708   // Helpers of visitSelectInst().
 709   Instruction *foldSelectExtConst(SelectInst &Sel);
 710   Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
 711   Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
 712   Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1,
 713                             Value *A, Value *B, Instruction &Outer,
 714                             SelectPatternFlavor SPF2, Value *C);
 715   Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI);
 716   Instruction *foldSelectValueEquivalence(SelectInst &SI, ICmpInst &ICI);
 717
 718   Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
 719                          bool isSigned, bool Inside);
 720   Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI);
 721   bool mergeStoreIntoSuccessor(StoreInst &SI);
 722
 723   /// Given an initial instruction, check to see if it is the root of a
 724   /// bswap/bitreverse idiom. If so, return the equivalent bswap/bitreverse
 725   /// intrinsic.
 726   Instruction *matchBSwapOrBitReverse(Instruction &I, bool MatchBSwaps,
 727                                       bool MatchBitReversals);
 728
 729   Instruction *SimplifyAnyMemTransfer(AnyMemTransferInst *MI);
 730   Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI);
 731
 732   Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
 733
 734   /// Returns a value X such that Val = X * Scale, or null if none.
 735   ///
 736   /// If the multiplication is known not to overflow then NoSignedWrap is set.
 737   Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
 738 };
 739
 740 class Negator final {
 741   /// Top-to-bottom, def-to-use negated instruction tree we produced.
 742   SmallVector<Instruction *, NegatorMaxNodesSSO> NewInstructions;
 743
 744   using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
 745   BuilderTy Builder;
 746
 747   const DataLayout &DL;
 748   AssumptionCache &AC;
 749   const DominatorTree &DT;
 750
 751   const bool IsTrulyNegation;
 752
 753   SmallDenseMap<Value *, Value *> NegationsCache;
 754
 755   Negator(LLVMContext &C, const DataLayout &DL, AssumptionCache &AC,
 756           const DominatorTree &DT, bool IsTrulyNegation);
 757
 758 #if LLVM_ENABLE_STATS
 759   unsigned NumValuesVisitedInThisNegator = 0;
 760   ~Negator();
 761 #endif
 762
 763   using Result = std::pair<ArrayRef<Instruction *> /*NewInstructions*/,
 764                            Value * /*NegatedRoot*/>;
 765
 766   std::array<Value *, 2> getSortedOperandsOfBinOp(Instruction *I);
 767
 768   LLVM_NODISCARD Value *visitImpl(Value *V, unsigned Depth);
 769
 770   LLVM_NODISCARD Value *negate(Value *V, unsigned Depth);
 771
 772   /// Recurse depth-first and attempt to sink the negation.
 773   /// FIXME: use worklist?
 774   LLVM_NODISCARD Optional<Result> run(Value *Root);
 775
 776   Negator(const Negator &) = delete;
 777   Negator(Negator &&) = delete;
 778   Negator &operator=(const Negator &) = delete;
 779   Negator &operator=(Negator &&) = delete;
 780
 781 public:
 782   /// Attempt to negate \p Root. Retuns nullptr if negation can't be performed,
 783   /// otherwise returns negated value.
 784   LLVM_NODISCARD static Value *Negate(bool LHSIsZero, Value *Root,
 785                                       InstCombinerImpl &IC);
 786 };
 787
 788 } // end namespace llvm
 789
 790 #undef DEBUG_TYPE
 791
 792 #endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H