1 //===- InstCombineInternal.h - InstCombine pass internals -------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 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/Analysis/AliasAnalysis.h" 19 #include "llvm/Analysis/AssumptionCache.h" 20 #include "llvm/Analysis/LoopInfo.h" 21 #include "llvm/Analysis/TargetFolder.h" 22 #include "llvm/Analysis/ValueTracking.h" 23 #include "llvm/IR/Dominators.h" 24 #include "llvm/IR/IRBuilder.h" 25 #include "llvm/IR/InstVisitor.h" 26 #include "llvm/IR/IntrinsicInst.h" 27 #include "llvm/IR/Operator.h" 28 #include "llvm/IR/PatternMatch.h" 29 #include "llvm/Pass.h" 30 #include "llvm/Transforms/InstCombine/InstCombineWorklist.h" 31 32 #define DEBUG_TYPE "instcombine" 33 34 namespace llvm { 35 class CallSite; 36 class DataLayout; 37 class DominatorTree; 38 class TargetLibraryInfo; 39 class DbgDeclareInst; 40 class MemIntrinsic; 41 class MemSetInst; 42 43 /// \brief Assign a complexity or rank value to LLVM Values. 44 /// 45 /// This routine maps IR values to various complexity ranks: 46 /// 0 -> undef 47 /// 1 -> Constants 48 /// 2 -> Other non-instructions 49 /// 3 -> Arguments 50 /// 3 -> Unary operations 51 /// 4 -> Other instructions 52 static inline unsigned getComplexity(Value *V) { 53 if (isa<Instruction>(V)) { 54 if (BinaryOperator::isNeg(V) || BinaryOperator::isFNeg(V) || 55 BinaryOperator::isNot(V)) 56 return 3; 57 return 4; 58 } 59 if (isa<Argument>(V)) 60 return 3; 61 return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2; 62 } 63 64 /// \brief Add one to a Constant 65 static inline Constant *AddOne(Constant *C) { 66 return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1)); 67 } 68 /// \brief Subtract one from a Constant 69 static inline Constant *SubOne(Constant *C) { 70 return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1)); 71 } 72 73 /// \brief Return true if the specified value is free to invert (apply ~ to). 74 /// This happens in cases where the ~ can be eliminated. If WillInvertAllUses 75 /// is true, work under the assumption that the caller intends to remove all 76 /// uses of V and only keep uses of ~V. 77 /// 78 static inline bool IsFreeToInvert(Value *V, bool WillInvertAllUses) { 79 // ~(~(X)) -> X. 80 if (BinaryOperator::isNot(V)) 81 return true; 82 83 // Constants can be considered to be not'ed values. 84 if (isa<ConstantInt>(V)) 85 return true; 86 87 // A vector of constant integers can be inverted easily. 88 Constant *CV; 89 if (V->getType()->isVectorTy() && match(V, PatternMatch::m_Constant(CV))) { 90 unsigned NumElts = V->getType()->getVectorNumElements(); 91 for (unsigned i = 0; i != NumElts; ++i) { 92 Constant *Elt = CV->getAggregateElement(i); 93 if (!Elt) 94 return false; 95 96 if (isa<UndefValue>(Elt)) 97 continue; 98 99 if (!isa<ConstantInt>(Elt)) 100 return false; 101 } 102 return true; 103 } 104 105 // Compares can be inverted if all of their uses are being modified to use the 106 // ~V. 107 if (isa<CmpInst>(V)) 108 return WillInvertAllUses; 109 110 // If `V` is of the form `A + Constant` then `-1 - V` can be folded into `(-1 111 // - Constant) - A` if we are willing to invert all of the uses. 112 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V)) 113 if (BO->getOpcode() == Instruction::Add || 114 BO->getOpcode() == Instruction::Sub) 115 if (isa<Constant>(BO->getOperand(0)) || isa<Constant>(BO->getOperand(1))) 116 return WillInvertAllUses; 117 118 return false; 119 } 120 121 122 /// \brief Specific patterns of overflow check idioms that we match. 123 enum OverflowCheckFlavor { 124 OCF_UNSIGNED_ADD, 125 OCF_SIGNED_ADD, 126 OCF_UNSIGNED_SUB, 127 OCF_SIGNED_SUB, 128 OCF_UNSIGNED_MUL, 129 OCF_SIGNED_MUL, 130 131 OCF_INVALID 132 }; 133 134 /// \brief Returns the OverflowCheckFlavor corresponding to a overflow_with_op 135 /// intrinsic. 136 static inline OverflowCheckFlavor 137 IntrinsicIDToOverflowCheckFlavor(unsigned ID) { 138 switch (ID) { 139 default: 140 return OCF_INVALID; 141 case Intrinsic::uadd_with_overflow: 142 return OCF_UNSIGNED_ADD; 143 case Intrinsic::sadd_with_overflow: 144 return OCF_SIGNED_ADD; 145 case Intrinsic::usub_with_overflow: 146 return OCF_UNSIGNED_SUB; 147 case Intrinsic::ssub_with_overflow: 148 return OCF_SIGNED_SUB; 149 case Intrinsic::umul_with_overflow: 150 return OCF_UNSIGNED_MUL; 151 case Intrinsic::smul_with_overflow: 152 return OCF_SIGNED_MUL; 153 } 154 } 155 156 /// \brief The core instruction combiner logic. 157 /// 158 /// This class provides both the logic to recursively visit instructions and 159 /// combine them, as well as the pass infrastructure for running this as part 160 /// of the LLVM pass pipeline. 161 class LLVM_LIBRARY_VISIBILITY InstCombiner 162 : public InstVisitor<InstCombiner, Instruction *> { 163 // FIXME: These members shouldn't be public. 164 public: 165 /// \brief A worklist of the instructions that need to be simplified. 166 InstCombineWorklist &Worklist; 167 168 /// \brief An IRBuilder that automatically inserts new instructions into the 169 /// worklist. 170 typedef IRBuilder<TargetFolder, IRBuilderCallbackInserter> BuilderTy; 171 BuilderTy *Builder; 172 173 private: 174 // Mode in which we are running the combiner. 175 const bool MinimizeSize; 176 /// Enable combines that trigger rarely but are costly in compiletime. 177 const bool ExpensiveCombines; 178 179 AliasAnalysis *AA; 180 181 // Required analyses. 182 AssumptionCache &AC; 183 TargetLibraryInfo &TLI; 184 DominatorTree &DT; 185 const DataLayout &DL; 186 187 // Optional analyses. When non-null, these can both be used to do better 188 // combining and will be updated to reflect any changes. 189 LoopInfo *LI; 190 191 bool MadeIRChange; 192 193 public: 194 InstCombiner(InstCombineWorklist &Worklist, BuilderTy *Builder, 195 bool MinimizeSize, bool ExpensiveCombines, AliasAnalysis *AA, 196 AssumptionCache &AC, TargetLibraryInfo &TLI, 197 DominatorTree &DT, const DataLayout &DL, LoopInfo *LI) 198 : Worklist(Worklist), Builder(Builder), MinimizeSize(MinimizeSize), 199 ExpensiveCombines(ExpensiveCombines), AA(AA), AC(AC), TLI(TLI), DT(DT), 200 DL(DL), LI(LI), MadeIRChange(false) {} 201 202 /// \brief Run the combiner over the entire worklist until it is empty. 203 /// 204 /// \returns true if the IR is changed. 205 bool run(); 206 207 AssumptionCache &getAssumptionCache() const { return AC; } 208 209 const DataLayout &getDataLayout() const { return DL; } 210 211 DominatorTree &getDominatorTree() const { return DT; } 212 213 LoopInfo *getLoopInfo() const { return LI; } 214 215 TargetLibraryInfo &getTargetLibraryInfo() const { return TLI; } 216 217 // Visitation implementation - Implement instruction combining for different 218 // instruction types. The semantics are as follows: 219 // Return Value: 220 // null - No change was made 221 // I - Change was made, I is still valid, I may be dead though 222 // otherwise - Change was made, replace I with returned instruction 223 // 224 Instruction *visitAdd(BinaryOperator &I); 225 Instruction *visitFAdd(BinaryOperator &I); 226 Value *OptimizePointerDifference(Value *LHS, Value *RHS, Type *Ty); 227 Instruction *visitSub(BinaryOperator &I); 228 Instruction *visitFSub(BinaryOperator &I); 229 Instruction *visitMul(BinaryOperator &I); 230 Value *foldFMulConst(Instruction *FMulOrDiv, Constant *C, 231 Instruction *InsertBefore); 232 Instruction *visitFMul(BinaryOperator &I); 233 Instruction *visitURem(BinaryOperator &I); 234 Instruction *visitSRem(BinaryOperator &I); 235 Instruction *visitFRem(BinaryOperator &I); 236 bool SimplifyDivRemOfSelect(BinaryOperator &I); 237 Instruction *commonRemTransforms(BinaryOperator &I); 238 Instruction *commonIRemTransforms(BinaryOperator &I); 239 Instruction *commonDivTransforms(BinaryOperator &I); 240 Instruction *commonIDivTransforms(BinaryOperator &I); 241 Instruction *visitUDiv(BinaryOperator &I); 242 Instruction *visitSDiv(BinaryOperator &I); 243 Instruction *visitFDiv(BinaryOperator &I); 244 Value *simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted); 245 Value *FoldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS); 246 Value *FoldAndOfFCmps(FCmpInst *LHS, FCmpInst *RHS); 247 Instruction *visitAnd(BinaryOperator &I); 248 Value *FoldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction *CxtI); 249 Value *FoldOrOfFCmps(FCmpInst *LHS, FCmpInst *RHS); 250 Instruction *FoldOrWithConstants(BinaryOperator &I, Value *Op, Value *A, 251 Value *B, Value *C); 252 Instruction *FoldXorWithConstants(BinaryOperator &I, Value *Op, Value *A, 253 Value *B, Value *C); 254 Instruction *visitOr(BinaryOperator &I); 255 Instruction *visitXor(BinaryOperator &I); 256 Instruction *visitShl(BinaryOperator &I); 257 Instruction *visitAShr(BinaryOperator &I); 258 Instruction *visitLShr(BinaryOperator &I); 259 Instruction *commonShiftTransforms(BinaryOperator &I); 260 Instruction *visitFCmpInst(FCmpInst &I); 261 Instruction *visitICmpInst(ICmpInst &I); 262 Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1, 263 BinaryOperator &I); 264 Instruction *commonCastTransforms(CastInst &CI); 265 Instruction *commonPointerCastTransforms(CastInst &CI); 266 Instruction *visitTrunc(TruncInst &CI); 267 Instruction *visitZExt(ZExtInst &CI); 268 Instruction *visitSExt(SExtInst &CI); 269 Instruction *visitFPTrunc(FPTruncInst &CI); 270 Instruction *visitFPExt(CastInst &CI); 271 Instruction *visitFPToUI(FPToUIInst &FI); 272 Instruction *visitFPToSI(FPToSIInst &FI); 273 Instruction *visitUIToFP(CastInst &CI); 274 Instruction *visitSIToFP(CastInst &CI); 275 Instruction *visitPtrToInt(PtrToIntInst &CI); 276 Instruction *visitIntToPtr(IntToPtrInst &CI); 277 Instruction *visitBitCast(BitCastInst &CI); 278 Instruction *visitAddrSpaceCast(AddrSpaceCastInst &CI); 279 Instruction *FoldItoFPtoI(Instruction &FI); 280 Instruction *visitSelectInst(SelectInst &SI); 281 Instruction *visitCallInst(CallInst &CI); 282 Instruction *visitInvokeInst(InvokeInst &II); 283 284 Instruction *SliceUpIllegalIntegerPHI(PHINode &PN); 285 Instruction *visitPHINode(PHINode &PN); 286 Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP); 287 Instruction *visitAllocaInst(AllocaInst &AI); 288 Instruction *visitAllocSite(Instruction &FI); 289 Instruction *visitFree(CallInst &FI); 290 Instruction *visitLoadInst(LoadInst &LI); 291 Instruction *visitStoreInst(StoreInst &SI); 292 Instruction *visitBranchInst(BranchInst &BI); 293 Instruction *visitSwitchInst(SwitchInst &SI); 294 Instruction *visitReturnInst(ReturnInst &RI); 295 Instruction *visitInsertValueInst(InsertValueInst &IV); 296 Instruction *visitInsertElementInst(InsertElementInst &IE); 297 Instruction *visitExtractElementInst(ExtractElementInst &EI); 298 Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI); 299 Instruction *visitExtractValueInst(ExtractValueInst &EV); 300 Instruction *visitLandingPadInst(LandingPadInst &LI); 301 Instruction *visitVAStartInst(VAStartInst &I); 302 Instruction *visitVACopyInst(VACopyInst &I); 303 304 /// Specify what to return for unhandled instructions. 305 Instruction *visitInstruction(Instruction &I) { return nullptr; } 306 307 /// True when DB dominates all uses of DI except UI. 308 /// UI must be in the same block as DI. 309 /// The routine checks that the DI parent and DB are different. 310 bool dominatesAllUses(const Instruction *DI, const Instruction *UI, 311 const BasicBlock *DB) const; 312 313 /// Try to replace select with select operand SIOpd in SI-ICmp sequence. 314 bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp, 315 const unsigned SIOpd); 316 317 private: 318 bool ShouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const; 319 bool ShouldChangeType(Type *From, Type *To) const; 320 Value *dyn_castNegVal(Value *V) const; 321 Value *dyn_castFNegVal(Value *V, bool NoSignedZero = false) const; 322 Type *FindElementAtOffset(PointerType *PtrTy, int64_t Offset, 323 SmallVectorImpl<Value *> &NewIndices); 324 Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI); 325 326 /// Classify whether a cast is worth optimizing. 327 /// 328 /// This is a helper to decide whether the simplification of 329 /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed. 330 /// 331 /// \param CI The cast we are interested in. 332 /// 333 /// \return true if this cast actually results in any code being generated and 334 /// if it cannot already be eliminated by some other transformation. 335 bool shouldOptimizeCast(CastInst *CI); 336 337 /// \brief Try to optimize a sequence of instructions checking if an operation 338 /// on LHS and RHS overflows. 339 /// 340 /// If this overflow check is done via one of the overflow check intrinsics, 341 /// then CtxI has to be the call instruction calling that intrinsic. If this 342 /// overflow check is done by arithmetic followed by a compare, then CtxI has 343 /// to be the arithmetic instruction. 344 /// 345 /// If a simplification is possible, stores the simplified result of the 346 /// operation in OperationResult and result of the overflow check in 347 /// OverflowResult, and return true. If no simplification is possible, 348 /// returns false. 349 bool OptimizeOverflowCheck(OverflowCheckFlavor OCF, Value *LHS, Value *RHS, 350 Instruction &CtxI, Value *&OperationResult, 351 Constant *&OverflowResult); 352 353 Instruction *visitCallSite(CallSite CS); 354 Instruction *tryOptimizeCall(CallInst *CI); 355 bool transformConstExprCastCall(CallSite CS); 356 Instruction *transformCallThroughTrampoline(CallSite CS, 357 IntrinsicInst *Tramp); 358 359 /// Transform (zext icmp) to bitwise / integer operations in order to 360 /// eliminate it. 361 /// 362 /// \param ICI The icmp of the (zext icmp) pair we are interested in. 363 /// \parem CI The zext of the (zext icmp) pair we are interested in. 364 /// \param DoTransform Pass false to just test whether the given (zext icmp) 365 /// would be transformed. Pass true to actually perform the transformation. 366 /// 367 /// \return null if the transformation cannot be performed. If the 368 /// transformation can be performed the new instruction that replaces the 369 /// (zext icmp) pair will be returned (if \p DoTransform is false the 370 /// unmodified \p ICI will be returned in this case). 371 Instruction *transformZExtICmp(ICmpInst *ICI, ZExtInst &CI, 372 bool DoTransform = true); 373 374 Instruction *transformSExtICmp(ICmpInst *ICI, Instruction &CI); 375 bool WillNotOverflowSignedAdd(Value *LHS, Value *RHS, Instruction &CxtI); 376 bool WillNotOverflowSignedSub(Value *LHS, Value *RHS, Instruction &CxtI); 377 bool WillNotOverflowUnsignedSub(Value *LHS, Value *RHS, Instruction &CxtI); 378 bool WillNotOverflowSignedMul(Value *LHS, Value *RHS, Instruction &CxtI); 379 Value *EmitGEPOffset(User *GEP); 380 Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN); 381 Value *EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask); 382 Instruction *foldCastedBitwiseLogic(BinaryOperator &I); 383 Instruction *shrinkBitwiseLogic(TruncInst &Trunc); 384 Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN); 385 386 /// Determine if a pair of casts can be replaced by a single cast. 387 /// 388 /// \param CI1 The first of a pair of casts. 389 /// \param CI2 The second of a pair of casts. 390 /// 391 /// \return 0 if the cast pair cannot be eliminated, otherwise returns an 392 /// Instruction::CastOps value for a cast that can replace the pair, casting 393 /// CI1->getSrcTy() to CI2->getDstTy(). 394 /// 395 /// \see CastInst::isEliminableCastPair 396 Instruction::CastOps isEliminableCastPair(const CastInst *CI1, 397 const CastInst *CI2); 398 399 public: 400 /// \brief Inserts an instruction \p New before instruction \p Old 401 /// 402 /// Also adds the new instruction to the worklist and returns \p New so that 403 /// it is suitable for use as the return from the visitation patterns. 404 Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) { 405 assert(New && !New->getParent() && 406 "New instruction already inserted into a basic block!"); 407 BasicBlock *BB = Old.getParent(); 408 BB->getInstList().insert(Old.getIterator(), New); // Insert inst 409 Worklist.Add(New); 410 return New; 411 } 412 413 /// \brief Same as InsertNewInstBefore, but also sets the debug loc. 414 Instruction *InsertNewInstWith(Instruction *New, Instruction &Old) { 415 New->setDebugLoc(Old.getDebugLoc()); 416 return InsertNewInstBefore(New, Old); 417 } 418 419 /// \brief A combiner-aware RAUW-like routine. 420 /// 421 /// This method is to be used when an instruction is found to be dead, 422 /// replaceable with another preexisting expression. Here we add all uses of 423 /// I to the worklist, replace all uses of I with the new value, then return 424 /// I, so that the inst combiner will know that I was modified. 425 Instruction *replaceInstUsesWith(Instruction &I, Value *V) { 426 // If there are no uses to replace, then we return nullptr to indicate that 427 // no changes were made to the program. 428 if (I.use_empty()) return nullptr; 429 430 Worklist.AddUsersToWorkList(I); // Add all modified instrs to worklist. 431 432 // If we are replacing the instruction with itself, this must be in a 433 // segment of unreachable code, so just clobber the instruction. 434 if (&I == V) 435 V = UndefValue::get(I.getType()); 436 437 DEBUG(dbgs() << "IC: Replacing " << I << "\n" 438 << " with " << *V << '\n'); 439 440 I.replaceAllUsesWith(V); 441 return &I; 442 } 443 444 /// Creates a result tuple for an overflow intrinsic \p II with a given 445 /// \p Result and a constant \p Overflow value. 446 Instruction *CreateOverflowTuple(IntrinsicInst *II, Value *Result, 447 Constant *Overflow) { 448 Constant *V[] = {UndefValue::get(Result->getType()), Overflow}; 449 StructType *ST = cast<StructType>(II->getType()); 450 Constant *Struct = ConstantStruct::get(ST, V); 451 return InsertValueInst::Create(Struct, Result, 0); 452 } 453 454 /// \brief Combiner aware instruction erasure. 455 /// 456 /// When dealing with an instruction that has side effects or produces a void 457 /// value, we can't rely on DCE to delete the instruction. Instead, visit 458 /// methods should return the value returned by this function. 459 Instruction *eraseInstFromFunction(Instruction &I) { 460 DEBUG(dbgs() << "IC: ERASE " << I << '\n'); 461 462 assert(I.use_empty() && "Cannot erase instruction that is used!"); 463 // Make sure that we reprocess all operands now that we reduced their 464 // use counts. 465 if (I.getNumOperands() < 8) { 466 for (Use &Operand : I.operands()) 467 if (auto *Inst = dyn_cast<Instruction>(Operand)) 468 Worklist.Add(Inst); 469 } 470 Worklist.Remove(&I); 471 I.eraseFromParent(); 472 MadeIRChange = true; 473 return nullptr; // Don't do anything with FI 474 } 475 476 void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 477 unsigned Depth, Instruction *CxtI) const { 478 return llvm::computeKnownBits(V, KnownZero, KnownOne, DL, Depth, &AC, CxtI, 479 &DT); 480 } 481 482 bool MaskedValueIsZero(Value *V, const APInt &Mask, unsigned Depth = 0, 483 Instruction *CxtI = nullptr) const { 484 return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT); 485 } 486 unsigned ComputeNumSignBits(Value *Op, unsigned Depth = 0, 487 Instruction *CxtI = nullptr) const { 488 return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT); 489 } 490 void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, 491 unsigned Depth = 0, Instruction *CxtI = nullptr) const { 492 return llvm::ComputeSignBit(V, KnownZero, KnownOne, DL, Depth, &AC, CxtI, 493 &DT); 494 } 495 OverflowResult computeOverflowForUnsignedMul(Value *LHS, Value *RHS, 496 const Instruction *CxtI) { 497 return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT); 498 } 499 OverflowResult computeOverflowForUnsignedAdd(Value *LHS, Value *RHS, 500 const Instruction *CxtI) { 501 return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT); 502 } 503 504 private: 505 /// \brief Performs a few simplifications for operators which are associative 506 /// or commutative. 507 bool SimplifyAssociativeOrCommutative(BinaryOperator &I); 508 509 /// \brief Tries to simplify binary operations which some other binary 510 /// operation distributes over. 511 /// 512 /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)" 513 /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A 514 /// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified 515 /// value, or null if it didn't simplify. 516 Value *SimplifyUsingDistributiveLaws(BinaryOperator &I); 517 518 /// \brief Attempts to replace V with a simpler value based on the demanded 519 /// bits. 520 Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, APInt &KnownZero, 521 APInt &KnownOne, unsigned Depth, 522 Instruction *CxtI); 523 bool SimplifyDemandedBits(Use &U, const APInt &DemandedMask, APInt &KnownZero, 524 APInt &KnownOne, unsigned Depth = 0); 525 /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded 526 /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence. 527 Value *SimplifyShrShlDemandedBits(Instruction *Lsr, Instruction *Sftl, 528 const APInt &DemandedMask, APInt &KnownZero, 529 APInt &KnownOne); 530 531 /// \brief Tries to simplify operands to an integer instruction based on its 532 /// demanded bits. 533 bool SimplifyDemandedInstructionBits(Instruction &Inst); 534 535 Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, 536 APInt &UndefElts, unsigned Depth = 0); 537 538 Value *SimplifyVectorOp(BinaryOperator &Inst); 539 Value *SimplifyBSwap(BinaryOperator &Inst); 540 541 // FoldOpIntoPhi - Given a binary operator, cast instruction, or select 542 // which has a PHI node as operand #0, see if we can fold the instruction 543 // into the PHI (which is only possible if all operands to the PHI are 544 // constants). 545 // 546 Instruction *FoldOpIntoPhi(Instruction &I); 547 548 /// \brief Try to rotate an operation below a PHI node, using PHI nodes for 549 /// its operands. 550 Instruction *FoldPHIArgOpIntoPHI(PHINode &PN); 551 Instruction *FoldPHIArgBinOpIntoPHI(PHINode &PN); 552 Instruction *FoldPHIArgGEPIntoPHI(PHINode &PN); 553 Instruction *FoldPHIArgLoadIntoPHI(PHINode &PN); 554 Instruction *FoldPHIArgZextsIntoPHI(PHINode &PN); 555 556 Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS, 557 ICmpInst::Predicate Cond, Instruction &I); 558 Instruction *foldAllocaCmp(ICmpInst &ICI, const AllocaInst *Alloca, 559 const Value *Other); 560 Instruction *foldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP, 561 GlobalVariable *GV, CmpInst &ICI, 562 ConstantInt *AndCst = nullptr); 563 Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI, 564 Constant *RHSC); 565 Instruction *foldICmpAddOpConst(Instruction &ICI, Value *X, ConstantInt *CI, 566 ICmpInst::Predicate Pred); 567 Instruction *foldICmpWithCastAndCast(ICmpInst &ICI); 568 569 Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp); 570 Instruction *foldICmpWithConstant(ICmpInst &Cmp); 571 Instruction *foldICmpInstWithConstant(ICmpInst &Cmp); 572 Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp); 573 Instruction *foldICmpBinOp(ICmpInst &Cmp); 574 Instruction *foldICmpEquality(ICmpInst &Cmp); 575 576 Instruction *foldICmpTruncConstant(ICmpInst &Cmp, Instruction *Trunc, 577 const APInt *C); 578 Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And, 579 const APInt *C); 580 Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor, 581 const APInt *C); 582 Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or, 583 const APInt *C); 584 Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul, 585 const APInt *C); 586 Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl, 587 const APInt *C); 588 Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr, 589 const APInt *C); 590 Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv, 591 const APInt *C); 592 Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div, 593 const APInt *C); 594 Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub, 595 const APInt *C); 596 Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add, 597 const APInt *C); 598 Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And, 599 const APInt *C1); 600 Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And, 601 const APInt *C1, const APInt *C2); 602 Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1, 603 const APInt &C2); 604 Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1, 605 const APInt &C2); 606 607 Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp, 608 BinaryOperator *BO, 609 const APInt *C); 610 Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, const APInt *C); 611 612 // Helpers of visitSelectInst(). 613 Instruction *foldSelectExtConst(SelectInst &Sel); 614 Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI); 615 Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *); 616 Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1, 617 Value *A, Value *B, Instruction &Outer, 618 SelectPatternFlavor SPF2, Value *C); 619 Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI); 620 621 Instruction *OptAndOp(Instruction *Op, ConstantInt *OpRHS, 622 ConstantInt *AndRHS, BinaryOperator &TheAnd); 623 624 Value *FoldLogicalPlusAnd(Value *LHS, Value *RHS, ConstantInt *Mask, 625 bool isSub, Instruction &I); 626 Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi, 627 bool isSigned, bool Inside); 628 Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI); 629 Instruction *MatchBSwap(BinaryOperator &I); 630 bool SimplifyStoreAtEndOfBlock(StoreInst &SI); 631 Instruction *SimplifyMemTransfer(MemIntrinsic *MI); 632 Instruction *SimplifyMemSet(MemSetInst *MI); 633 634 Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned); 635 636 /// \brief Returns a value X such that Val = X * Scale, or null if none. 637 /// 638 /// If the multiplication is known not to overflow then NoSignedWrap is set. 639 Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap); 640 }; 641 642 } // end namespace llvm. 643 644 #undef DEBUG_TYPE 645 646 #endif 647