1283625Sdim//===- InstCombineInternal.h - InstCombine pass internals -------*- C++ -*-===// 2283625Sdim// 3283625Sdim// The LLVM Compiler Infrastructure 4283625Sdim// 5283625Sdim// This file is distributed under the University of Illinois Open Source 6283625Sdim// License. See LICENSE.TXT for details. 7283625Sdim// 8283625Sdim//===----------------------------------------------------------------------===// 9283625Sdim/// \file 10283625Sdim/// 11283625Sdim/// This file provides internal interfaces used to implement the InstCombine. 12283625Sdim/// 13283625Sdim//===----------------------------------------------------------------------===// 14283625Sdim 15283625Sdim#ifndef LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H 16283625Sdim#define LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H 17283625Sdim 18286684Sdim#include "llvm/Analysis/AliasAnalysis.h" 19283625Sdim#include "llvm/Analysis/AssumptionCache.h" 20283625Sdim#include "llvm/Analysis/LoopInfo.h" 21283625Sdim#include "llvm/Analysis/TargetFolder.h" 22283625Sdim#include "llvm/Analysis/ValueTracking.h" 23283625Sdim#include "llvm/IR/Dominators.h" 24283625Sdim#include "llvm/IR/IRBuilder.h" 25283625Sdim#include "llvm/IR/InstVisitor.h" 26283625Sdim#include "llvm/IR/IntrinsicInst.h" 27283625Sdim#include "llvm/IR/Operator.h" 28283625Sdim#include "llvm/IR/PatternMatch.h" 29283625Sdim#include "llvm/Pass.h" 30283625Sdim#include "llvm/Transforms/InstCombine/InstCombineWorklist.h" 31283625Sdim 32283625Sdim#define DEBUG_TYPE "instcombine" 33283625Sdim 34283625Sdimnamespace llvm { 35283625Sdimclass CallSite; 36283625Sdimclass DataLayout; 37283625Sdimclass DominatorTree; 38283625Sdimclass TargetLibraryInfo; 39283625Sdimclass DbgDeclareInst; 40283625Sdimclass MemIntrinsic; 41283625Sdimclass MemSetInst; 42283625Sdim 43283625Sdim/// \brief Assign a complexity or rank value to LLVM Values. 44283625Sdim/// 45283625Sdim/// This routine maps IR values to various complexity ranks: 46283625Sdim/// 0 -> undef 47283625Sdim/// 1 -> Constants 48283625Sdim/// 2 -> Other non-instructions 49283625Sdim/// 3 -> Arguments 50283625Sdim/// 3 -> Unary operations 51283625Sdim/// 4 -> Other instructions 52283625Sdimstatic inline unsigned getComplexity(Value *V) { 53283625Sdim if (isa<Instruction>(V)) { 54283625Sdim if (BinaryOperator::isNeg(V) || BinaryOperator::isFNeg(V) || 55283625Sdim BinaryOperator::isNot(V)) 56283625Sdim return 3; 57283625Sdim return 4; 58283625Sdim } 59283625Sdim if (isa<Argument>(V)) 60283625Sdim return 3; 61283625Sdim return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2; 62283625Sdim} 63283625Sdim 64283625Sdim/// \brief Add one to a Constant 65283625Sdimstatic inline Constant *AddOne(Constant *C) { 66283625Sdim return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1)); 67283625Sdim} 68283625Sdim/// \brief Subtract one from a Constant 69283625Sdimstatic inline Constant *SubOne(Constant *C) { 70283625Sdim return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1)); 71283625Sdim} 72283625Sdim 73283625Sdim/// \brief Return true if the specified value is free to invert (apply ~ to). 74283625Sdim/// This happens in cases where the ~ can be eliminated. If WillInvertAllUses 75283625Sdim/// is true, work under the assumption that the caller intends to remove all 76283625Sdim/// uses of V and only keep uses of ~V. 77283625Sdim/// 78283625Sdimstatic inline bool IsFreeToInvert(Value *V, bool WillInvertAllUses) { 79283625Sdim // ~(~(X)) -> X. 80283625Sdim if (BinaryOperator::isNot(V)) 81283625Sdim return true; 82283625Sdim 83283625Sdim // Constants can be considered to be not'ed values. 84283625Sdim if (isa<ConstantInt>(V)) 85283625Sdim return true; 86283625Sdim 87283625Sdim // Compares can be inverted if all of their uses are being modified to use the 88283625Sdim // ~V. 89283625Sdim if (isa<CmpInst>(V)) 90283625Sdim return WillInvertAllUses; 91283625Sdim 92283625Sdim // If `V` is of the form `A + Constant` then `-1 - V` can be folded into `(-1 93283625Sdim // - Constant) - A` if we are willing to invert all of the uses. 94283625Sdim if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V)) 95283625Sdim if (BO->getOpcode() == Instruction::Add || 96283625Sdim BO->getOpcode() == Instruction::Sub) 97283625Sdim if (isa<Constant>(BO->getOperand(0)) || isa<Constant>(BO->getOperand(1))) 98283625Sdim return WillInvertAllUses; 99283625Sdim 100283625Sdim return false; 101283625Sdim} 102283625Sdim 103283625Sdim 104283625Sdim/// \brief Specific patterns of overflow check idioms that we match. 105283625Sdimenum OverflowCheckFlavor { 106283625Sdim OCF_UNSIGNED_ADD, 107283625Sdim OCF_SIGNED_ADD, 108283625Sdim OCF_UNSIGNED_SUB, 109283625Sdim OCF_SIGNED_SUB, 110283625Sdim OCF_UNSIGNED_MUL, 111283625Sdim OCF_SIGNED_MUL, 112283625Sdim 113283625Sdim OCF_INVALID 114283625Sdim}; 115283625Sdim 116283625Sdim/// \brief Returns the OverflowCheckFlavor corresponding to a overflow_with_op 117283625Sdim/// intrinsic. 118283625Sdimstatic inline OverflowCheckFlavor 119283625SdimIntrinsicIDToOverflowCheckFlavor(unsigned ID) { 120283625Sdim switch (ID) { 121283625Sdim default: 122283625Sdim return OCF_INVALID; 123283625Sdim case Intrinsic::uadd_with_overflow: 124283625Sdim return OCF_UNSIGNED_ADD; 125283625Sdim case Intrinsic::sadd_with_overflow: 126283625Sdim return OCF_SIGNED_ADD; 127283625Sdim case Intrinsic::usub_with_overflow: 128283625Sdim return OCF_UNSIGNED_SUB; 129283625Sdim case Intrinsic::ssub_with_overflow: 130283625Sdim return OCF_SIGNED_SUB; 131283625Sdim case Intrinsic::umul_with_overflow: 132283625Sdim return OCF_UNSIGNED_MUL; 133283625Sdim case Intrinsic::smul_with_overflow: 134283625Sdim return OCF_SIGNED_MUL; 135283625Sdim } 136283625Sdim} 137283625Sdim 138283625Sdim/// \brief An IRBuilder inserter that adds new instructions to the instcombine 139283625Sdim/// worklist. 140283625Sdimclass LLVM_LIBRARY_VISIBILITY InstCombineIRInserter 141283625Sdim : public IRBuilderDefaultInserter<true> { 142283625Sdim InstCombineWorklist &Worklist; 143283625Sdim AssumptionCache *AC; 144283625Sdim 145283625Sdimpublic: 146283625Sdim InstCombineIRInserter(InstCombineWorklist &WL, AssumptionCache *AC) 147283625Sdim : Worklist(WL), AC(AC) {} 148283625Sdim 149283625Sdim void InsertHelper(Instruction *I, const Twine &Name, BasicBlock *BB, 150283625Sdim BasicBlock::iterator InsertPt) const { 151283625Sdim IRBuilderDefaultInserter<true>::InsertHelper(I, Name, BB, InsertPt); 152283625Sdim Worklist.Add(I); 153283625Sdim 154283625Sdim using namespace llvm::PatternMatch; 155283625Sdim if (match(I, m_Intrinsic<Intrinsic::assume>())) 156283625Sdim AC->registerAssumption(cast<CallInst>(I)); 157283625Sdim } 158283625Sdim}; 159283625Sdim 160283625Sdim/// \brief The core instruction combiner logic. 161283625Sdim/// 162283625Sdim/// This class provides both the logic to recursively visit instructions and 163283625Sdim/// combine them, as well as the pass infrastructure for running this as part 164283625Sdim/// of the LLVM pass pipeline. 165283625Sdimclass LLVM_LIBRARY_VISIBILITY InstCombiner 166283625Sdim : public InstVisitor<InstCombiner, Instruction *> { 167283625Sdim // FIXME: These members shouldn't be public. 168283625Sdimpublic: 169283625Sdim /// \brief A worklist of the instructions that need to be simplified. 170283625Sdim InstCombineWorklist &Worklist; 171283625Sdim 172283625Sdim /// \brief An IRBuilder that automatically inserts new instructions into the 173283625Sdim /// worklist. 174283625Sdim typedef IRBuilder<true, TargetFolder, InstCombineIRInserter> BuilderTy; 175283625Sdim BuilderTy *Builder; 176283625Sdim 177283625Sdimprivate: 178283625Sdim // Mode in which we are running the combiner. 179283625Sdim const bool MinimizeSize; 180283625Sdim 181286684Sdim AliasAnalysis *AA; 182286684Sdim 183283625Sdim // Required analyses. 184283625Sdim // FIXME: These can never be null and should be references. 185283625Sdim AssumptionCache *AC; 186283625Sdim TargetLibraryInfo *TLI; 187283625Sdim DominatorTree *DT; 188283625Sdim const DataLayout &DL; 189283625Sdim 190283625Sdim // Optional analyses. When non-null, these can both be used to do better 191283625Sdim // combining and will be updated to reflect any changes. 192283625Sdim LoopInfo *LI; 193283625Sdim 194283625Sdim bool MadeIRChange; 195283625Sdim 196283625Sdimpublic: 197283625Sdim InstCombiner(InstCombineWorklist &Worklist, BuilderTy *Builder, 198286684Sdim bool MinimizeSize, AliasAnalysis *AA, 199286684Sdim AssumptionCache *AC, TargetLibraryInfo *TLI, 200283625Sdim DominatorTree *DT, const DataLayout &DL, LoopInfo *LI) 201283625Sdim : Worklist(Worklist), Builder(Builder), MinimizeSize(MinimizeSize), 202286684Sdim AA(AA), AC(AC), TLI(TLI), DT(DT), DL(DL), LI(LI), MadeIRChange(false) {} 203283625Sdim 204283625Sdim /// \brief Run the combiner over the entire worklist until it is empty. 205283625Sdim /// 206283625Sdim /// \returns true if the IR is changed. 207283625Sdim bool run(); 208283625Sdim 209283625Sdim AssumptionCache *getAssumptionCache() const { return AC; } 210283625Sdim 211283625Sdim const DataLayout &getDataLayout() const { return DL; } 212283625Sdim 213283625Sdim DominatorTree *getDominatorTree() const { return DT; } 214283625Sdim 215283625Sdim LoopInfo *getLoopInfo() const { return LI; } 216283625Sdim 217283625Sdim TargetLibraryInfo *getTargetLibraryInfo() const { return TLI; } 218283625Sdim 219283625Sdim // Visitation implementation - Implement instruction combining for different 220283625Sdim // instruction types. The semantics are as follows: 221283625Sdim // Return Value: 222283625Sdim // null - No change was made 223283625Sdim // I - Change was made, I is still valid, I may be dead though 224283625Sdim // otherwise - Change was made, replace I with returned instruction 225283625Sdim // 226283625Sdim Instruction *visitAdd(BinaryOperator &I); 227283625Sdim Instruction *visitFAdd(BinaryOperator &I); 228283625Sdim Value *OptimizePointerDifference(Value *LHS, Value *RHS, Type *Ty); 229283625Sdim Instruction *visitSub(BinaryOperator &I); 230283625Sdim Instruction *visitFSub(BinaryOperator &I); 231283625Sdim Instruction *visitMul(BinaryOperator &I); 232283625Sdim Value *foldFMulConst(Instruction *FMulOrDiv, Constant *C, 233283625Sdim Instruction *InsertBefore); 234283625Sdim Instruction *visitFMul(BinaryOperator &I); 235283625Sdim Instruction *visitURem(BinaryOperator &I); 236283625Sdim Instruction *visitSRem(BinaryOperator &I); 237283625Sdim Instruction *visitFRem(BinaryOperator &I); 238283625Sdim bool SimplifyDivRemOfSelect(BinaryOperator &I); 239283625Sdim Instruction *commonRemTransforms(BinaryOperator &I); 240283625Sdim Instruction *commonIRemTransforms(BinaryOperator &I); 241283625Sdim Instruction *commonDivTransforms(BinaryOperator &I); 242283625Sdim Instruction *commonIDivTransforms(BinaryOperator &I); 243283625Sdim Instruction *visitUDiv(BinaryOperator &I); 244283625Sdim Instruction *visitSDiv(BinaryOperator &I); 245283625Sdim Instruction *visitFDiv(BinaryOperator &I); 246283625Sdim Value *simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted); 247283625Sdim Value *FoldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS); 248283625Sdim Value *FoldAndOfFCmps(FCmpInst *LHS, FCmpInst *RHS); 249283625Sdim Instruction *visitAnd(BinaryOperator &I); 250283625Sdim Value *FoldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction *CxtI); 251283625Sdim Value *FoldOrOfFCmps(FCmpInst *LHS, FCmpInst *RHS); 252283625Sdim Instruction *FoldOrWithConstants(BinaryOperator &I, Value *Op, Value *A, 253283625Sdim Value *B, Value *C); 254283625Sdim Instruction *FoldXorWithConstants(BinaryOperator &I, Value *Op, Value *A, 255283625Sdim Value *B, Value *C); 256283625Sdim Instruction *visitOr(BinaryOperator &I); 257283625Sdim Instruction *visitXor(BinaryOperator &I); 258283625Sdim Instruction *visitShl(BinaryOperator &I); 259283625Sdim Instruction *visitAShr(BinaryOperator &I); 260283625Sdim Instruction *visitLShr(BinaryOperator &I); 261283625Sdim Instruction *commonShiftTransforms(BinaryOperator &I); 262283625Sdim Instruction *FoldFCmp_IntToFP_Cst(FCmpInst &I, Instruction *LHSI, 263283625Sdim Constant *RHSC); 264283625Sdim Instruction *FoldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP, 265283625Sdim GlobalVariable *GV, CmpInst &ICI, 266283625Sdim ConstantInt *AndCst = nullptr); 267283625Sdim Instruction *visitFCmpInst(FCmpInst &I); 268283625Sdim Instruction *visitICmpInst(ICmpInst &I); 269283625Sdim Instruction *visitICmpInstWithCastAndCast(ICmpInst &ICI); 270283625Sdim Instruction *visitICmpInstWithInstAndIntCst(ICmpInst &ICI, Instruction *LHS, 271283625Sdim ConstantInt *RHS); 272283625Sdim Instruction *FoldICmpDivCst(ICmpInst &ICI, BinaryOperator *DivI, 273283625Sdim ConstantInt *DivRHS); 274283625Sdim Instruction *FoldICmpShrCst(ICmpInst &ICI, BinaryOperator *DivI, 275283625Sdim ConstantInt *DivRHS); 276283625Sdim Instruction *FoldICmpCstShrCst(ICmpInst &I, Value *Op, Value *A, 277283625Sdim ConstantInt *CI1, ConstantInt *CI2); 278283625Sdim Instruction *FoldICmpCstShlCst(ICmpInst &I, Value *Op, Value *A, 279283625Sdim ConstantInt *CI1, ConstantInt *CI2); 280283625Sdim Instruction *FoldICmpAddOpCst(Instruction &ICI, Value *X, ConstantInt *CI, 281283625Sdim ICmpInst::Predicate Pred); 282283625Sdim Instruction *FoldGEPICmp(GEPOperator *GEPLHS, Value *RHS, 283283625Sdim ICmpInst::Predicate Cond, Instruction &I); 284296417Sdim Instruction *FoldAllocaCmp(ICmpInst &ICI, AllocaInst *Alloca, Value *Other); 285283625Sdim Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1, 286283625Sdim BinaryOperator &I); 287283625Sdim Instruction *commonCastTransforms(CastInst &CI); 288283625Sdim Instruction *commonPointerCastTransforms(CastInst &CI); 289283625Sdim Instruction *visitTrunc(TruncInst &CI); 290283625Sdim Instruction *visitZExt(ZExtInst &CI); 291283625Sdim Instruction *visitSExt(SExtInst &CI); 292283625Sdim Instruction *visitFPTrunc(FPTruncInst &CI); 293283625Sdim Instruction *visitFPExt(CastInst &CI); 294283625Sdim Instruction *visitFPToUI(FPToUIInst &FI); 295283625Sdim Instruction *visitFPToSI(FPToSIInst &FI); 296283625Sdim Instruction *visitUIToFP(CastInst &CI); 297283625Sdim Instruction *visitSIToFP(CastInst &CI); 298283625Sdim Instruction *visitPtrToInt(PtrToIntInst &CI); 299283625Sdim Instruction *visitIntToPtr(IntToPtrInst &CI); 300283625Sdim Instruction *visitBitCast(BitCastInst &CI); 301283625Sdim Instruction *visitAddrSpaceCast(AddrSpaceCastInst &CI); 302283625Sdim Instruction *FoldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI); 303283625Sdim Instruction *FoldSelectIntoOp(SelectInst &SI, Value *, Value *); 304283625Sdim Instruction *FoldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1, 305283625Sdim Value *A, Value *B, Instruction &Outer, 306283625Sdim SelectPatternFlavor SPF2, Value *C); 307283625Sdim Instruction *FoldItoFPtoI(Instruction &FI); 308283625Sdim Instruction *visitSelectInst(SelectInst &SI); 309283625Sdim Instruction *visitSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI); 310283625Sdim Instruction *visitCallInst(CallInst &CI); 311283625Sdim Instruction *visitInvokeInst(InvokeInst &II); 312283625Sdim 313283625Sdim Instruction *SliceUpIllegalIntegerPHI(PHINode &PN); 314283625Sdim Instruction *visitPHINode(PHINode &PN); 315283625Sdim Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP); 316283625Sdim Instruction *visitAllocaInst(AllocaInst &AI); 317283625Sdim Instruction *visitAllocSite(Instruction &FI); 318283625Sdim Instruction *visitFree(CallInst &FI); 319283625Sdim Instruction *visitLoadInst(LoadInst &LI); 320283625Sdim Instruction *visitStoreInst(StoreInst &SI); 321283625Sdim Instruction *visitBranchInst(BranchInst &BI); 322283625Sdim Instruction *visitSwitchInst(SwitchInst &SI); 323283625Sdim Instruction *visitReturnInst(ReturnInst &RI); 324283625Sdim Instruction *visitInsertValueInst(InsertValueInst &IV); 325283625Sdim Instruction *visitInsertElementInst(InsertElementInst &IE); 326283625Sdim Instruction *visitExtractElementInst(ExtractElementInst &EI); 327283625Sdim Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI); 328283625Sdim Instruction *visitExtractValueInst(ExtractValueInst &EV); 329283625Sdim Instruction *visitLandingPadInst(LandingPadInst &LI); 330283625Sdim 331283625Sdim // visitInstruction - Specify what to return for unhandled instructions... 332283625Sdim Instruction *visitInstruction(Instruction &I) { return nullptr; } 333283625Sdim 334283625Sdim // True when DB dominates all uses of DI execpt UI. 335283625Sdim // UI must be in the same block as DI. 336283625Sdim // The routine checks that the DI parent and DB are different. 337283625Sdim bool dominatesAllUses(const Instruction *DI, const Instruction *UI, 338283625Sdim const BasicBlock *DB) const; 339283625Sdim 340283625Sdim // Replace select with select operand SIOpd in SI-ICmp sequence when possible 341283625Sdim bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp, 342283625Sdim const unsigned SIOpd); 343283625Sdim 344283625Sdimprivate: 345296417Sdim bool ShouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const; 346283625Sdim bool ShouldChangeType(Type *From, Type *To) const; 347283625Sdim Value *dyn_castNegVal(Value *V) const; 348283625Sdim Value *dyn_castFNegVal(Value *V, bool NoSignedZero = false) const; 349283625Sdim Type *FindElementAtOffset(PointerType *PtrTy, int64_t Offset, 350283625Sdim SmallVectorImpl<Value *> &NewIndices); 351283625Sdim Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI); 352283625Sdim 353283625Sdim /// \brief Classify whether a cast is worth optimizing. 354283625Sdim /// 355283625Sdim /// Returns true if the cast from "V to Ty" actually results in any code 356283625Sdim /// being generated and is interesting to optimize out. If the cast can be 357283625Sdim /// eliminated by some other simple transformation, we prefer to do the 358283625Sdim /// simplification first. 359283625Sdim bool ShouldOptimizeCast(Instruction::CastOps opcode, const Value *V, 360283625Sdim Type *Ty); 361283625Sdim 362283625Sdim /// \brief Try to optimize a sequence of instructions checking if an operation 363283625Sdim /// on LHS and RHS overflows. 364283625Sdim /// 365296417Sdim /// If this overflow check is done via one of the overflow check intrinsics, 366296417Sdim /// then CtxI has to be the call instruction calling that intrinsic. If this 367296417Sdim /// overflow check is done by arithmetic followed by a compare, then CtxI has 368296417Sdim /// to be the arithmetic instruction. 369296417Sdim /// 370283625Sdim /// If a simplification is possible, stores the simplified result of the 371283625Sdim /// operation in OperationResult and result of the overflow check in 372283625Sdim /// OverflowResult, and return true. If no simplification is possible, 373283625Sdim /// returns false. 374283625Sdim bool OptimizeOverflowCheck(OverflowCheckFlavor OCF, Value *LHS, Value *RHS, 375283625Sdim Instruction &CtxI, Value *&OperationResult, 376283625Sdim Constant *&OverflowResult); 377283625Sdim 378283625Sdim Instruction *visitCallSite(CallSite CS); 379283625Sdim Instruction *tryOptimizeCall(CallInst *CI); 380283625Sdim bool transformConstExprCastCall(CallSite CS); 381283625Sdim Instruction *transformCallThroughTrampoline(CallSite CS, 382283625Sdim IntrinsicInst *Tramp); 383283625Sdim Instruction *transformZExtICmp(ICmpInst *ICI, Instruction &CI, 384283625Sdim bool DoXform = true); 385283625Sdim Instruction *transformSExtICmp(ICmpInst *ICI, Instruction &CI); 386283625Sdim bool WillNotOverflowSignedAdd(Value *LHS, Value *RHS, Instruction &CxtI); 387283625Sdim bool WillNotOverflowSignedSub(Value *LHS, Value *RHS, Instruction &CxtI); 388283625Sdim bool WillNotOverflowUnsignedSub(Value *LHS, Value *RHS, Instruction &CxtI); 389283625Sdim bool WillNotOverflowSignedMul(Value *LHS, Value *RHS, Instruction &CxtI); 390283625Sdim Value *EmitGEPOffset(User *GEP); 391283625Sdim Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN); 392283625Sdim Value *EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask); 393283625Sdim 394283625Sdimpublic: 395283625Sdim /// \brief Inserts an instruction \p New before instruction \p Old 396283625Sdim /// 397283625Sdim /// Also adds the new instruction to the worklist and returns \p New so that 398283625Sdim /// it is suitable for use as the return from the visitation patterns. 399283625Sdim Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) { 400283625Sdim assert(New && !New->getParent() && 401283625Sdim "New instruction already inserted into a basic block!"); 402283625Sdim BasicBlock *BB = Old.getParent(); 403296417Sdim BB->getInstList().insert(Old.getIterator(), New); // Insert inst 404283625Sdim Worklist.Add(New); 405283625Sdim return New; 406283625Sdim } 407283625Sdim 408283625Sdim /// \brief Same as InsertNewInstBefore, but also sets the debug loc. 409283625Sdim Instruction *InsertNewInstWith(Instruction *New, Instruction &Old) { 410283625Sdim New->setDebugLoc(Old.getDebugLoc()); 411283625Sdim return InsertNewInstBefore(New, Old); 412283625Sdim } 413283625Sdim 414283625Sdim /// \brief A combiner-aware RAUW-like routine. 415283625Sdim /// 416283625Sdim /// This method is to be used when an instruction is found to be dead, 417296417Sdim /// replaceable with another preexisting expression. Here we add all uses of 418283625Sdim /// I to the worklist, replace all uses of I with the new value, then return 419283625Sdim /// I, so that the inst combiner will know that I was modified. 420283625Sdim Instruction *ReplaceInstUsesWith(Instruction &I, Value *V) { 421283625Sdim // If there are no uses to replace, then we return nullptr to indicate that 422283625Sdim // no changes were made to the program. 423283625Sdim if (I.use_empty()) return nullptr; 424283625Sdim 425283625Sdim Worklist.AddUsersToWorkList(I); // Add all modified instrs to worklist. 426283625Sdim 427283625Sdim // If we are replacing the instruction with itself, this must be in a 428283625Sdim // segment of unreachable code, so just clobber the instruction. 429283625Sdim if (&I == V) 430283625Sdim V = UndefValue::get(I.getType()); 431283625Sdim 432283625Sdim DEBUG(dbgs() << "IC: Replacing " << I << "\n" 433283625Sdim << " with " << *V << '\n'); 434283625Sdim 435283625Sdim I.replaceAllUsesWith(V); 436283625Sdim return &I; 437283625Sdim } 438283625Sdim 439283625Sdim /// Creates a result tuple for an overflow intrinsic \p II with a given 440283625Sdim /// \p Result and a constant \p Overflow value. 441283625Sdim Instruction *CreateOverflowTuple(IntrinsicInst *II, Value *Result, 442283625Sdim Constant *Overflow) { 443283625Sdim Constant *V[] = {UndefValue::get(Result->getType()), Overflow}; 444283625Sdim StructType *ST = cast<StructType>(II->getType()); 445283625Sdim Constant *Struct = ConstantStruct::get(ST, V); 446283625Sdim return InsertValueInst::Create(Struct, Result, 0); 447283625Sdim } 448283625Sdim 449283625Sdim /// \brief Combiner aware instruction erasure. 450283625Sdim /// 451283625Sdim /// When dealing with an instruction that has side effects or produces a void 452283625Sdim /// value, we can't rely on DCE to delete the instruction. Instead, visit 453283625Sdim /// methods should return the value returned by this function. 454283625Sdim Instruction *EraseInstFromFunction(Instruction &I) { 455283625Sdim DEBUG(dbgs() << "IC: ERASE " << I << '\n'); 456283625Sdim 457283625Sdim assert(I.use_empty() && "Cannot erase instruction that is used!"); 458283625Sdim // Make sure that we reprocess all operands now that we reduced their 459283625Sdim // use counts. 460283625Sdim if (I.getNumOperands() < 8) { 461283625Sdim for (User::op_iterator i = I.op_begin(), e = I.op_end(); i != e; ++i) 462283625Sdim if (Instruction *Op = dyn_cast<Instruction>(*i)) 463283625Sdim Worklist.Add(Op); 464283625Sdim } 465283625Sdim Worklist.Remove(&I); 466283625Sdim I.eraseFromParent(); 467283625Sdim MadeIRChange = true; 468283625Sdim return nullptr; // Don't do anything with FI 469283625Sdim } 470283625Sdim 471283625Sdim void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 472283625Sdim unsigned Depth, Instruction *CxtI) const { 473283625Sdim return llvm::computeKnownBits(V, KnownZero, KnownOne, DL, Depth, AC, CxtI, 474283625Sdim DT); 475283625Sdim } 476283625Sdim 477283625Sdim bool MaskedValueIsZero(Value *V, const APInt &Mask, unsigned Depth = 0, 478283625Sdim Instruction *CxtI = nullptr) const { 479283625Sdim return llvm::MaskedValueIsZero(V, Mask, DL, Depth, AC, CxtI, DT); 480283625Sdim } 481283625Sdim unsigned ComputeNumSignBits(Value *Op, unsigned Depth = 0, 482283625Sdim Instruction *CxtI = nullptr) const { 483283625Sdim return llvm::ComputeNumSignBits(Op, DL, Depth, AC, CxtI, DT); 484283625Sdim } 485283625Sdim void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, 486283625Sdim unsigned Depth = 0, Instruction *CxtI = nullptr) const { 487283625Sdim return llvm::ComputeSignBit(V, KnownZero, KnownOne, DL, Depth, AC, CxtI, 488283625Sdim DT); 489283625Sdim } 490283625Sdim OverflowResult computeOverflowForUnsignedMul(Value *LHS, Value *RHS, 491283625Sdim const Instruction *CxtI) { 492283625Sdim return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, AC, CxtI, DT); 493283625Sdim } 494283625Sdim OverflowResult computeOverflowForUnsignedAdd(Value *LHS, Value *RHS, 495283625Sdim const Instruction *CxtI) { 496283625Sdim return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, AC, CxtI, DT); 497283625Sdim } 498283625Sdim 499283625Sdimprivate: 500283625Sdim /// \brief Performs a few simplifications for operators which are associative 501283625Sdim /// or commutative. 502283625Sdim bool SimplifyAssociativeOrCommutative(BinaryOperator &I); 503283625Sdim 504283625Sdim /// \brief Tries to simplify binary operations which some other binary 505283625Sdim /// operation distributes over. 506283625Sdim /// 507283625Sdim /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)" 508283625Sdim /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A 509283625Sdim /// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified 510283625Sdim /// value, or null if it didn't simplify. 511283625Sdim Value *SimplifyUsingDistributiveLaws(BinaryOperator &I); 512283625Sdim 513283625Sdim /// \brief Attempts to replace V with a simpler value based on the demanded 514283625Sdim /// bits. 515283625Sdim Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, APInt &KnownZero, 516283625Sdim APInt &KnownOne, unsigned Depth, 517283625Sdim Instruction *CxtI); 518283625Sdim bool SimplifyDemandedBits(Use &U, APInt DemandedMask, APInt &KnownZero, 519283625Sdim APInt &KnownOne, unsigned Depth = 0); 520283625Sdim /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded 521283625Sdim /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence. 522283625Sdim Value *SimplifyShrShlDemandedBits(Instruction *Lsr, Instruction *Sftl, 523283625Sdim APInt DemandedMask, APInt &KnownZero, 524283625Sdim APInt &KnownOne); 525283625Sdim 526283625Sdim /// \brief Tries to simplify operands to an integer instruction based on its 527283625Sdim /// demanded bits. 528283625Sdim bool SimplifyDemandedInstructionBits(Instruction &Inst); 529283625Sdim 530283625Sdim Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, 531283625Sdim APInt &UndefElts, unsigned Depth = 0); 532283625Sdim 533283625Sdim Value *SimplifyVectorOp(BinaryOperator &Inst); 534283625Sdim Value *SimplifyBSwap(BinaryOperator &Inst); 535283625Sdim 536283625Sdim // FoldOpIntoPhi - Given a binary operator, cast instruction, or select 537283625Sdim // which has a PHI node as operand #0, see if we can fold the instruction 538283625Sdim // into the PHI (which is only possible if all operands to the PHI are 539283625Sdim // constants). 540283625Sdim // 541283625Sdim Instruction *FoldOpIntoPhi(Instruction &I); 542283625Sdim 543283625Sdim /// \brief Try to rotate an operation below a PHI node, using PHI nodes for 544283625Sdim /// its operands. 545283625Sdim Instruction *FoldPHIArgOpIntoPHI(PHINode &PN); 546283625Sdim Instruction *FoldPHIArgBinOpIntoPHI(PHINode &PN); 547283625Sdim Instruction *FoldPHIArgGEPIntoPHI(PHINode &PN); 548283625Sdim Instruction *FoldPHIArgLoadIntoPHI(PHINode &PN); 549296417Sdim Instruction *FoldPHIArgZextsIntoPHI(PHINode &PN); 550283625Sdim 551283625Sdim Instruction *OptAndOp(Instruction *Op, ConstantInt *OpRHS, 552283625Sdim ConstantInt *AndRHS, BinaryOperator &TheAnd); 553283625Sdim 554283625Sdim Value *FoldLogicalPlusAnd(Value *LHS, Value *RHS, ConstantInt *Mask, 555283625Sdim bool isSub, Instruction &I); 556283625Sdim Value *InsertRangeTest(Value *V, Constant *Lo, Constant *Hi, bool isSigned, 557283625Sdim bool Inside); 558283625Sdim Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI); 559296417Sdim Instruction *MatchBSwapOrBitReverse(BinaryOperator &I); 560283625Sdim bool SimplifyStoreAtEndOfBlock(StoreInst &SI); 561283625Sdim Instruction *SimplifyMemTransfer(MemIntrinsic *MI); 562283625Sdim Instruction *SimplifyMemSet(MemSetInst *MI); 563283625Sdim 564283625Sdim Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned); 565283625Sdim 566283625Sdim /// \brief Returns a value X such that Val = X * Scale, or null if none. 567283625Sdim /// 568283625Sdim /// If the multiplication is known not to overflow then NoSignedWrap is set. 569283625Sdim Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap); 570283625Sdim}; 571283625Sdim 572283625Sdim} // end namespace llvm. 573283625Sdim 574283625Sdim#undef DEBUG_TYPE 575283625Sdim 576283625Sdim#endif 577