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