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