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 Instruction *foldCommutativeIntrinsicOverSelects(IntrinsicInst &II); 280 281 // Match a pair of Phi Nodes like 282 // phi [a, BB0], [b, BB1] & phi [b, BB0], [a, BB1] 283 // Return the matched two operands. 284 std::optional<std::pair<Value *, Value *>> 285 matchSymmetricPhiNodesPair(PHINode *LHS, PHINode *RHS); 286 287 // Tries to fold (op phi(a, b) phi(b, a)) -> (op a, b) 288 // while op is a commutative intrinsic call. 289 Instruction *foldCommutativeIntrinsicOverPhis(IntrinsicInst &II); 290 291 Value *simplifyMaskedLoad(IntrinsicInst &II); 292 Instruction *simplifyMaskedStore(IntrinsicInst &II); 293 Instruction *simplifyMaskedGather(IntrinsicInst &II); 294 Instruction *simplifyMaskedScatter(IntrinsicInst &II); 295 296 /// Transform (zext icmp) to bitwise / integer operations in order to 297 /// eliminate it. 298 /// 299 /// \param ICI The icmp of the (zext icmp) pair we are interested in. 300 /// \parem CI The zext of the (zext icmp) pair we are interested in. 301 /// 302 /// \return null if the transformation cannot be performed. If the 303 /// transformation can be performed the new instruction that replaces the 304 /// (zext icmp) pair will be returned. 305 Instruction *transformZExtICmp(ICmpInst *Cmp, ZExtInst &Zext); 306 307 Instruction *transformSExtICmp(ICmpInst *Cmp, SExtInst &Sext); 308 309 bool willNotOverflowSignedAdd(const WithCache<const Value *> &LHS, 310 const WithCache<const Value *> &RHS, 311 const Instruction &CxtI) const { 312 return computeOverflowForSignedAdd(LHS, RHS, &CxtI) == 313 OverflowResult::NeverOverflows; 314 } 315 316 bool willNotOverflowUnsignedAdd(const WithCache<const Value *> &LHS, 317 const WithCache<const Value *> &RHS, 318 const Instruction &CxtI) const { 319 return computeOverflowForUnsignedAdd(LHS, RHS, &CxtI) == 320 OverflowResult::NeverOverflows; 321 } 322 323 bool willNotOverflowAdd(const Value *LHS, const Value *RHS, 324 const Instruction &CxtI, bool IsSigned) const { 325 return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CxtI) 326 : willNotOverflowUnsignedAdd(LHS, RHS, CxtI); 327 } 328 329 bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS, 330 const Instruction &CxtI) const { 331 return computeOverflowForSignedSub(LHS, RHS, &CxtI) == 332 OverflowResult::NeverOverflows; 333 } 334 335 bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS, 336 const Instruction &CxtI) const { 337 return computeOverflowForUnsignedSub(LHS, RHS, &CxtI) == 338 OverflowResult::NeverOverflows; 339 } 340 341 bool willNotOverflowSub(const Value *LHS, const Value *RHS, 342 const Instruction &CxtI, bool IsSigned) const { 343 return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CxtI) 344 : willNotOverflowUnsignedSub(LHS, RHS, CxtI); 345 } 346 347 bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS, 348 const Instruction &CxtI) const { 349 return computeOverflowForSignedMul(LHS, RHS, &CxtI) == 350 OverflowResult::NeverOverflows; 351 } 352 353 bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS, 354 const Instruction &CxtI) const { 355 return computeOverflowForUnsignedMul(LHS, RHS, &CxtI) == 356 OverflowResult::NeverOverflows; 357 } 358 359 bool willNotOverflowMul(const Value *LHS, const Value *RHS, 360 const Instruction &CxtI, bool IsSigned) const { 361 return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CxtI) 362 : willNotOverflowUnsignedMul(LHS, RHS, CxtI); 363 } 364 365 bool willNotOverflow(BinaryOperator::BinaryOps Opcode, const Value *LHS, 366 const Value *RHS, const Instruction &CxtI, 367 bool IsSigned) const { 368 switch (Opcode) { 369 case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CxtI, IsSigned); 370 case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CxtI, IsSigned); 371 case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CxtI, IsSigned); 372 default: llvm_unreachable("Unexpected opcode for overflow query"); 373 } 374 } 375 376 Value *EmitGEPOffset(User *GEP); 377 Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN); 378 Instruction *foldBitcastExtElt(ExtractElementInst &ExtElt); 379 Instruction *foldCastedBitwiseLogic(BinaryOperator &I); 380 Instruction *foldBinopOfSextBoolToSelect(BinaryOperator &I); 381 Instruction *narrowBinOp(TruncInst &Trunc); 382 Instruction *narrowMaskedBinOp(BinaryOperator &And); 383 Instruction *narrowMathIfNoOverflow(BinaryOperator &I); 384 Instruction *narrowFunnelShift(TruncInst &Trunc); 385 Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN); 386 Instruction *matchSAddSubSat(IntrinsicInst &MinMax1); 387 Instruction *foldNot(BinaryOperator &I); 388 Instruction *foldBinOpOfDisplacedShifts(BinaryOperator &I); 389 390 /// Determine if a pair of casts can be replaced by a single cast. 391 /// 392 /// \param CI1 The first of a pair of casts. 393 /// \param CI2 The second of a pair of casts. 394 /// 395 /// \return 0 if the cast pair cannot be eliminated, otherwise returns an 396 /// Instruction::CastOps value for a cast that can replace the pair, casting 397 /// CI1->getSrcTy() to CI2->getDstTy(). 398 /// 399 /// \see CastInst::isEliminableCastPair 400 Instruction::CastOps isEliminableCastPair(const CastInst *CI1, 401 const CastInst *CI2); 402 Value *simplifyIntToPtrRoundTripCast(Value *Val); 403 404 Value *foldAndOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &I, 405 bool IsAnd, bool IsLogical = false); 406 Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Xor); 407 408 Value *foldEqOfParts(ICmpInst *Cmp0, ICmpInst *Cmp1, bool IsAnd); 409 410 Value *foldAndOrOfICmpsUsingRanges(ICmpInst *ICmp1, ICmpInst *ICmp2, 411 bool IsAnd); 412 413 /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp). 414 /// NOTE: Unlike most of instcombine, this returns a Value which should 415 /// already be inserted into the function. 416 Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd, 417 bool IsLogicalSelect = false); 418 419 Instruction *foldLogicOfIsFPClass(BinaryOperator &Operator, Value *LHS, 420 Value *RHS); 421 422 Instruction * 423 canonicalizeConditionalNegationViaMathToSelect(BinaryOperator &i); 424 425 Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS, 426 Instruction *CxtI, bool IsAnd, 427 bool IsLogical = false); 428 Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D, 429 bool InvertFalseVal = false); 430 Value *getSelectCondition(Value *A, Value *B, bool ABIsTheSame); 431 432 Instruction *foldLShrOverflowBit(BinaryOperator &I); 433 Instruction *foldExtractOfOverflowIntrinsic(ExtractValueInst &EV); 434 Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II); 435 Instruction *foldIntrinsicIsFPClass(IntrinsicInst &II); 436 Instruction *foldFPSignBitOps(BinaryOperator &I); 437 Instruction *foldFDivConstantDivisor(BinaryOperator &I); 438 439 // Optimize one of these forms: 440 // and i1 Op, SI / select i1 Op, i1 SI, i1 false (if IsAnd = true) 441 // or i1 Op, SI / select i1 Op, i1 true, i1 SI (if IsAnd = false) 442 // into simplier select instruction using isImpliedCondition. 443 Instruction *foldAndOrOfSelectUsingImpliedCond(Value *Op, SelectInst &SI, 444 bool IsAnd); 445 446 Instruction *hoistFNegAboveFMulFDiv(Value *FNegOp, Instruction &FMFSource); 447 448 public: 449 /// Create and insert the idiom we use to indicate a block is unreachable 450 /// without having to rewrite the CFG from within InstCombine. 451 void CreateNonTerminatorUnreachable(Instruction *InsertAt) { 452 auto &Ctx = InsertAt->getContext(); 453 auto *SI = new StoreInst(ConstantInt::getTrue(Ctx), 454 PoisonValue::get(PointerType::getUnqual(Ctx)), 455 /*isVolatile*/ false, Align(1)); 456 InsertNewInstBefore(SI, InsertAt->getIterator()); 457 } 458 459 /// Combiner aware instruction erasure. 460 /// 461 /// When dealing with an instruction that has side effects or produces a void 462 /// value, we can't rely on DCE to delete the instruction. Instead, visit 463 /// methods should return the value returned by this function. 464 Instruction *eraseInstFromFunction(Instruction &I) override { 465 LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n'); 466 assert(I.use_empty() && "Cannot erase instruction that is used!"); 467 salvageDebugInfo(I); 468 469 // Make sure that we reprocess all operands now that we reduced their 470 // use counts. 471 SmallVector<Value *> Ops(I.operands()); 472 Worklist.remove(&I); 473 DC.removeValue(&I); 474 I.eraseFromParent(); 475 for (Value *Op : Ops) 476 Worklist.handleUseCountDecrement(Op); 477 MadeIRChange = true; 478 return nullptr; // Don't do anything with FI 479 } 480 481 OverflowResult computeOverflow( 482 Instruction::BinaryOps BinaryOp, bool IsSigned, 483 Value *LHS, Value *RHS, Instruction *CxtI) const; 484 485 /// Performs a few simplifications for operators which are associative 486 /// or commutative. 487 bool SimplifyAssociativeOrCommutative(BinaryOperator &I); 488 489 /// Tries to simplify binary operations which some other binary 490 /// operation distributes over. 491 /// 492 /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)" 493 /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A 494 /// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified 495 /// value, or null if it didn't simplify. 496 Value *foldUsingDistributiveLaws(BinaryOperator &I); 497 498 /// Tries to simplify add operations using the definition of remainder. 499 /// 500 /// The definition of remainder is X % C = X - (X / C ) * C. The add 501 /// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to 502 /// X % (C0 * C1) 503 Value *SimplifyAddWithRemainder(BinaryOperator &I); 504 505 // Tries to fold (Binop phi(a, b) phi(b, a)) -> (Binop a, b) 506 // while Binop is commutative. 507 Value *SimplifyPhiCommutativeBinaryOp(BinaryOperator &I, Value *LHS, 508 Value *RHS); 509 510 // Binary Op helper for select operations where the expression can be 511 // efficiently reorganized. 512 Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS, 513 Value *RHS); 514 515 // (Binop1 (Binop2 (logic_shift X, C), C1), (logic_shift Y, C)) 516 // -> (logic_shift (Binop1 (Binop2 X, inv_logic_shift(C1, C)), Y), C) 517 // (Binop1 (Binop2 (logic_shift X, Amt), Mask), (logic_shift Y, Amt)) 518 // -> (BinOp (logic_shift (BinOp X, Y)), Mask) 519 Instruction *foldBinOpShiftWithShift(BinaryOperator &I); 520 521 /// Tries to simplify binops of select and cast of the select condition. 522 /// 523 /// (Binop (cast C), (select C, T, F)) 524 /// -> (select C, C0, C1) 525 Instruction *foldBinOpOfSelectAndCastOfSelectCondition(BinaryOperator &I); 526 527 /// This tries to simplify binary operations by factorizing out common terms 528 /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)"). 529 Value *tryFactorizationFolds(BinaryOperator &I); 530 531 /// Match a select chain which produces one of three values based on whether 532 /// the LHS is less than, equal to, or greater than RHS respectively. 533 /// Return true if we matched a three way compare idiom. The LHS, RHS, Less, 534 /// Equal and Greater values are saved in the matching process and returned to 535 /// the caller. 536 bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS, 537 ConstantInt *&Less, ConstantInt *&Equal, 538 ConstantInt *&Greater); 539 540 /// Attempts to replace V with a simpler value based on the demanded 541 /// bits. 542 Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known, 543 unsigned Depth, Instruction *CxtI); 544 bool SimplifyDemandedBits(Instruction *I, unsigned Op, 545 const APInt &DemandedMask, KnownBits &Known, 546 unsigned Depth = 0) override; 547 548 /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne 549 /// bits. It also tries to handle simplifications that can be done based on 550 /// DemandedMask, but without modifying the Instruction. 551 Value *SimplifyMultipleUseDemandedBits(Instruction *I, 552 const APInt &DemandedMask, 553 KnownBits &Known, 554 unsigned Depth, Instruction *CxtI); 555 556 /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded 557 /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence. 558 Value *simplifyShrShlDemandedBits( 559 Instruction *Shr, const APInt &ShrOp1, Instruction *Shl, 560 const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known); 561 562 /// Tries to simplify operands to an integer instruction based on its 563 /// demanded bits. 564 bool SimplifyDemandedInstructionBits(Instruction &Inst); 565 bool SimplifyDemandedInstructionBits(Instruction &Inst, KnownBits &Known); 566 567 Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, 568 APInt &PoisonElts, unsigned Depth = 0, 569 bool AllowMultipleUsers = false) override; 570 571 /// Canonicalize the position of binops relative to shufflevector. 572 Instruction *foldVectorBinop(BinaryOperator &Inst); 573 Instruction *foldVectorSelect(SelectInst &Sel); 574 Instruction *foldSelectShuffle(ShuffleVectorInst &Shuf); 575 576 /// Given a binary operator, cast instruction, or select which has a PHI node 577 /// as operand #0, see if we can fold the instruction into the PHI (which is 578 /// only possible if all operands to the PHI are constants). 579 Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN); 580 581 /// For a binary operator with 2 phi operands, try to hoist the binary 582 /// operation before the phi. This can result in fewer instructions in 583 /// patterns where at least one set of phi operands simplifies. 584 /// Example: 585 /// BB3: binop (phi [X, BB1], [C1, BB2]), (phi [Y, BB1], [C2, BB2]) 586 /// --> 587 /// BB1: BO = binop X, Y 588 /// BB3: phi [BO, BB1], [(binop C1, C2), BB2] 589 Instruction *foldBinopWithPhiOperands(BinaryOperator &BO); 590 591 /// Given an instruction with a select as one operand and a constant as the 592 /// other operand, try to fold the binary operator into the select arguments. 593 /// This also works for Cast instructions, which obviously do not have a 594 /// second operand. 595 Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI, 596 bool FoldWithMultiUse = false); 597 598 /// This is a convenience wrapper function for the above two functions. 599 Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I); 600 601 Instruction *foldAddWithConstant(BinaryOperator &Add); 602 603 Instruction *foldSquareSumInt(BinaryOperator &I); 604 Instruction *foldSquareSumFP(BinaryOperator &I); 605 606 /// Try to rotate an operation below a PHI node, using PHI nodes for 607 /// its operands. 608 Instruction *foldPHIArgOpIntoPHI(PHINode &PN); 609 Instruction *foldPHIArgBinOpIntoPHI(PHINode &PN); 610 Instruction *foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN); 611 Instruction *foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN); 612 Instruction *foldPHIArgGEPIntoPHI(PHINode &PN); 613 Instruction *foldPHIArgLoadIntoPHI(PHINode &PN); 614 Instruction *foldPHIArgZextsIntoPHI(PHINode &PN); 615 Instruction *foldPHIArgIntToPtrToPHI(PHINode &PN); 616 617 /// If an integer typed PHI has only one use which is an IntToPtr operation, 618 /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise 619 /// insert a new pointer typed PHI and replace the original one. 620 bool foldIntegerTypedPHI(PHINode &PN); 621 622 /// Helper function for FoldPHIArgXIntoPHI() to set debug location for the 623 /// folded operation. 624 void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN); 625 626 Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS, 627 ICmpInst::Predicate Cond, Instruction &I); 628 Instruction *foldSelectICmp(ICmpInst::Predicate Pred, SelectInst *SI, 629 Value *RHS, const ICmpInst &I); 630 bool foldAllocaCmp(AllocaInst *Alloca); 631 Instruction *foldCmpLoadFromIndexedGlobal(LoadInst *LI, 632 GetElementPtrInst *GEP, 633 GlobalVariable *GV, CmpInst &ICI, 634 ConstantInt *AndCst = nullptr); 635 Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI, 636 Constant *RHSC); 637 Instruction *foldICmpAddOpConst(Value *X, const APInt &C, 638 ICmpInst::Predicate Pred); 639 Instruction *foldICmpWithCastOp(ICmpInst &ICmp); 640 Instruction *foldICmpWithZextOrSext(ICmpInst &ICmp); 641 642 Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp); 643 Instruction *foldICmpWithDominatingICmp(ICmpInst &Cmp); 644 Instruction *foldICmpWithConstant(ICmpInst &Cmp); 645 Instruction *foldICmpUsingBoolRange(ICmpInst &I); 646 Instruction *foldICmpInstWithConstant(ICmpInst &Cmp); 647 Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp); 648 Instruction *foldICmpInstWithConstantAllowUndef(ICmpInst &Cmp, 649 const APInt &C); 650 Instruction *foldICmpBinOp(ICmpInst &Cmp, const SimplifyQuery &SQ); 651 Instruction *foldICmpWithMinMax(Instruction &I, MinMaxIntrinsic *MinMax, 652 Value *Z, ICmpInst::Predicate Pred); 653 Instruction *foldICmpEquality(ICmpInst &Cmp); 654 Instruction *foldIRemByPowerOfTwoToBitTest(ICmpInst &I); 655 Instruction *foldSignBitTest(ICmpInst &I); 656 Instruction *foldICmpWithZero(ICmpInst &Cmp); 657 658 Value *foldMultiplicationOverflowCheck(ICmpInst &Cmp); 659 660 Instruction *foldICmpBinOpWithConstant(ICmpInst &Cmp, BinaryOperator *BO, 661 const APInt &C); 662 Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select, 663 ConstantInt *C); 664 Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc, 665 const APInt &C); 666 Instruction *foldICmpTruncWithTruncOrExt(ICmpInst &Cmp, 667 const SimplifyQuery &Q); 668 Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And, 669 const APInt &C); 670 Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor, 671 const APInt &C); 672 Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or, 673 const APInt &C); 674 Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul, 675 const APInt &C); 676 Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl, 677 const APInt &C); 678 Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr, 679 const APInt &C); 680 Instruction *foldICmpSRemConstant(ICmpInst &Cmp, BinaryOperator *UDiv, 681 const APInt &C); 682 Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv, 683 const APInt &C); 684 Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div, 685 const APInt &C); 686 Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub, 687 const APInt &C); 688 Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add, 689 const APInt &C); 690 Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And, 691 const APInt &C1); 692 Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And, 693 const APInt &C1, const APInt &C2); 694 Instruction *foldICmpXorShiftConst(ICmpInst &Cmp, BinaryOperator *Xor, 695 const APInt &C); 696 Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1, 697 const APInt &C2); 698 Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1, 699 const APInt &C2); 700 701 Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp, 702 BinaryOperator *BO, 703 const APInt &C); 704 Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II, 705 const APInt &C); 706 Instruction *foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II, 707 const APInt &C); 708 Instruction *foldICmpBitCast(ICmpInst &Cmp); 709 Instruction *foldICmpWithTrunc(ICmpInst &Cmp); 710 Instruction *foldICmpCommutative(ICmpInst::Predicate Pred, Value *Op0, 711 Value *Op1, ICmpInst &CxtI); 712 713 // Helpers of visitSelectInst(). 714 Instruction *foldSelectOfBools(SelectInst &SI); 715 Instruction *foldSelectExtConst(SelectInst &Sel); 716 Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI); 717 Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *); 718 Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1, 719 Value *A, Value *B, Instruction &Outer, 720 SelectPatternFlavor SPF2, Value *C); 721 Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI); 722 Instruction *foldSelectValueEquivalence(SelectInst &SI, ICmpInst &ICI); 723 bool replaceInInstruction(Value *V, Value *Old, Value *New, 724 unsigned Depth = 0); 725 726 Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi, 727 bool isSigned, bool Inside); 728 bool mergeStoreIntoSuccessor(StoreInst &SI); 729 730 /// Given an initial instruction, check to see if it is the root of a 731 /// bswap/bitreverse idiom. If so, return the equivalent bswap/bitreverse 732 /// intrinsic. 733 Instruction *matchBSwapOrBitReverse(Instruction &I, bool MatchBSwaps, 734 bool MatchBitReversals); 735 736 Instruction *SimplifyAnyMemTransfer(AnyMemTransferInst *MI); 737 Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI); 738 739 Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned); 740 741 bool tryToSinkInstruction(Instruction *I, BasicBlock *DestBlock); 742 743 bool removeInstructionsBeforeUnreachable(Instruction &I); 744 void addDeadEdge(BasicBlock *From, BasicBlock *To, 745 SmallVectorImpl<BasicBlock *> &Worklist); 746 void handleUnreachableFrom(Instruction *I, 747 SmallVectorImpl<BasicBlock *> &Worklist); 748 void handlePotentiallyDeadBlocks(SmallVectorImpl<BasicBlock *> &Worklist); 749 void handlePotentiallyDeadSuccessors(BasicBlock *BB, BasicBlock *LiveSucc); 750 void freelyInvertAllUsersOf(Value *V, Value *IgnoredUser = nullptr); 751 }; 752 753 class Negator final { 754 /// Top-to-bottom, def-to-use negated instruction tree we produced. 755 SmallVector<Instruction *, NegatorMaxNodesSSO> NewInstructions; 756 757 using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>; 758 BuilderTy Builder; 759 760 const bool IsTrulyNegation; 761 762 SmallDenseMap<Value *, Value *> NegationsCache; 763 764 Negator(LLVMContext &C, const DataLayout &DL, bool IsTrulyNegation); 765 766 #if LLVM_ENABLE_STATS 767 unsigned NumValuesVisitedInThisNegator = 0; 768 ~Negator(); 769 #endif 770 771 using Result = std::pair<ArrayRef<Instruction *> /*NewInstructions*/, 772 Value * /*NegatedRoot*/>; 773 774 std::array<Value *, 2> getSortedOperandsOfBinOp(Instruction *I); 775 776 [[nodiscard]] Value *visitImpl(Value *V, bool IsNSW, unsigned Depth); 777 778 [[nodiscard]] Value *negate(Value *V, bool IsNSW, unsigned Depth); 779 780 /// Recurse depth-first and attempt to sink the negation. 781 /// FIXME: use worklist? 782 [[nodiscard]] std::optional<Result> run(Value *Root, bool IsNSW); 783 784 Negator(const Negator &) = delete; 785 Negator(Negator &&) = delete; 786 Negator &operator=(const Negator &) = delete; 787 Negator &operator=(Negator &&) = delete; 788 789 public: 790 /// Attempt to negate \p Root. Retuns nullptr if negation can't be performed, 791 /// otherwise returns negated value. 792 [[nodiscard]] static Value *Negate(bool LHSIsZero, bool IsNSW, Value *Root, 793 InstCombinerImpl &IC); 794 }; 795 796 } // end namespace llvm 797 798 #undef DEBUG_TYPE 799 800 #endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H 801