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