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