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