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