//===-- Local.h - Functions to perform local transformations ----*- C++ -*-===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This family of functions perform various local transformations to the // program. // //===----------------------------------------------------------------------===// #ifndef LLVM_TRANSFORMS_UTILS_LOCAL_H #define LLVM_TRANSFORMS_UTILS_LOCAL_H #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/GetElementPtrTypeIterator.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/Operator.h" namespace llvm { class User; class BasicBlock; class Function; class BranchInst; class Instruction; class DbgDeclareInst; class StoreInst; class LoadInst; class Value; class PHINode; class AllocaInst; class AssumptionCache; class ConstantExpr; class DataLayout; class TargetLibraryInfo; class TargetTransformInfo; class DIBuilder; class DominatorTree; template<typename T> class SmallVectorImpl; //===----------------------------------------------------------------------===// // Local constant propagation. // /// ConstantFoldTerminator - If a terminator instruction is predicated on a /// constant value, convert it into an unconditional branch to the constant /// destination. This is a nontrivial operation because the successors of this /// basic block must have their PHI nodes updated. /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch /// conditions and indirectbr addresses this might make dead if /// DeleteDeadConditions is true. bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false, const TargetLibraryInfo *TLI = nullptr); //===----------------------------------------------------------------------===// // Local dead code elimination. // /// isInstructionTriviallyDead - Return true if the result produced by the /// instruction is not used, and the instruction has no side effects. /// bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI = nullptr); /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a /// trivially dead instruction, delete it. If that makes any of its operands /// trivially dead, delete them too, recursively. Return true if any /// instructions were deleted. bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI = nullptr); /// RecursivelyDeleteDeadPHINode - If the specified value is an effectively /// dead PHI node, due to being a def-use chain of single-use nodes that /// either forms a cycle or is terminated by a trivially dead instruction, /// delete it. If that makes any of its operands trivially dead, delete them /// too, recursively. Return true if a change was made. bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI = nullptr); /// SimplifyInstructionsInBlock - Scan the specified basic block and try to /// simplify any instructions in it and recursively delete dead instructions. /// /// This returns true if it changed the code, note that it can delete /// instructions in other blocks as well in this block. bool SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr); //===----------------------------------------------------------------------===// // Control Flow Graph Restructuring. // /// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this /// method is called when we're about to delete Pred as a predecessor of BB. If /// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred. /// /// Unlike the removePredecessor method, this attempts to simplify uses of PHI /// nodes that collapse into identity values. For example, if we have: /// x = phi(1, 0, 0, 0) /// y = and x, z /// /// .. and delete the predecessor corresponding to the '1', this will attempt to /// recursively fold the 'and' to 0. void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred); /// MergeBasicBlockIntoOnlyPred - BB is a block with one predecessor and its /// predecessor is known to have one successor (BB!). Eliminate the edge /// between them, moving the instructions in the predecessor into BB. This /// deletes the predecessor block. /// void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT = nullptr); /// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an /// unconditional branch, and contains no instructions other than PHI nodes, /// potential debug intrinsics and the branch. If possible, eliminate BB by /// rewriting all the predecessors to branch to the successor block and return /// true. If we can't transform, return false. bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB); /// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI /// nodes in this block. This doesn't try to be clever about PHI nodes /// which differ only in the order of the incoming values, but instcombine /// orders them so it usually won't matter. /// bool EliminateDuplicatePHINodes(BasicBlock *BB); /// SimplifyCFG - This function is used to do simplification of a CFG. For /// example, it adjusts branches to branches to eliminate the extra hop, it /// eliminates unreachable basic blocks, and does other "peephole" optimization /// of the CFG. It returns true if a modification was made, possibly deleting /// the basic block that was pointed to. /// bool SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, unsigned BonusInstThreshold, AssumptionCache *AC = nullptr); /// FlatternCFG - This function is used to flatten a CFG. For /// example, it uses parallel-and and parallel-or mode to collapse // if-conditions and merge if-regions with identical statements. /// bool FlattenCFG(BasicBlock *BB, AliasAnalysis *AA = nullptr); /// FoldBranchToCommonDest - If this basic block is ONLY a setcc and a branch, /// and if a predecessor branches to us and one of our successors, fold the /// setcc into the predecessor and use logical operations to pick the right /// destination. bool FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold = 1); /// DemoteRegToStack - This function takes a virtual register computed by an /// Instruction and replaces it with a slot in the stack frame, allocated via /// alloca. This allows the CFG to be changed around without fear of /// invalidating the SSA information for the value. It returns the pointer to /// the alloca inserted to create a stack slot for X. /// AllocaInst *DemoteRegToStack(Instruction &X, bool VolatileLoads = false, Instruction *AllocaPoint = nullptr); /// DemotePHIToStack - This function takes a virtual register computed by a phi /// node and replaces it with a slot in the stack frame, allocated via alloca. /// The phi node is deleted and it returns the pointer to the alloca inserted. AllocaInst *DemotePHIToStack(PHINode *P, Instruction *AllocaPoint = nullptr); /// getOrEnforceKnownAlignment - If the specified pointer has an alignment that /// we can determine, return it, otherwise return 0. If PrefAlign is specified, /// and it is more than the alignment of the ultimate object, see if we can /// increase the alignment of the ultimate object, making this check succeed. unsigned getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, const DataLayout &DL, const Instruction *CxtI = nullptr, AssumptionCache *AC = nullptr, const DominatorTree *DT = nullptr); /// getKnownAlignment - Try to infer an alignment for the specified pointer. static inline unsigned getKnownAlignment(Value *V, const DataLayout &DL, const Instruction *CxtI = nullptr, AssumptionCache *AC = nullptr, const DominatorTree *DT = nullptr) { return getOrEnforceKnownAlignment(V, 0, DL, CxtI, AC, DT); } /// EmitGEPOffset - Given a getelementptr instruction/constantexpr, emit the /// code necessary to compute the offset from the base pointer (without adding /// in the base pointer). Return the result as a signed integer of intptr size. /// When NoAssumptions is true, no assumptions about index computation not /// overflowing is made. template <typename IRBuilderTy> Value *EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &DL, User *GEP, bool NoAssumptions = false) { GEPOperator *GEPOp = cast<GEPOperator>(GEP); Type *IntPtrTy = DL.getIntPtrType(GEP->getType()); Value *Result = Constant::getNullValue(IntPtrTy); // If the GEP is inbounds, we know that none of the addressing operations will // overflow in an unsigned sense. bool isInBounds = GEPOp->isInBounds() && !NoAssumptions; // Build a mask for high order bits. unsigned IntPtrWidth = IntPtrTy->getScalarType()->getIntegerBitWidth(); uint64_t PtrSizeMask = ~0ULL >> (64 - IntPtrWidth); gep_type_iterator GTI = gep_type_begin(GEP); for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); i != e; ++i, ++GTI) { Value *Op = *i; uint64_t Size = DL.getTypeAllocSize(GTI.getIndexedType()) & PtrSizeMask; if (Constant *OpC = dyn_cast<Constant>(Op)) { if (OpC->isZeroValue()) continue; // Handle a struct index, which adds its field offset to the pointer. if (StructType *STy = dyn_cast<StructType>(*GTI)) { if (OpC->getType()->isVectorTy()) OpC = OpC->getSplatValue(); uint64_t OpValue = cast<ConstantInt>(OpC)->getZExtValue(); Size = DL.getStructLayout(STy)->getElementOffset(OpValue); if (Size) Result = Builder->CreateAdd(Result, ConstantInt::get(IntPtrTy, Size), GEP->getName()+".offs"); continue; } Constant *Scale = ConstantInt::get(IntPtrTy, Size); Constant *OC = ConstantExpr::getIntegerCast(OpC, IntPtrTy, true /*SExt*/); Scale = ConstantExpr::getMul(OC, Scale, isInBounds/*NUW*/); // Emit an add instruction. Result = Builder->CreateAdd(Result, Scale, GEP->getName()+".offs"); continue; } // Convert to correct type. if (Op->getType() != IntPtrTy) Op = Builder->CreateIntCast(Op, IntPtrTy, true, Op->getName()+".c"); if (Size != 1) { // We'll let instcombine(mul) convert this to a shl if possible. Op = Builder->CreateMul(Op, ConstantInt::get(IntPtrTy, Size), GEP->getName()+".idx", isInBounds /*NUW*/); } // Emit an add instruction. Result = Builder->CreateAdd(Op, Result, GEP->getName()+".offs"); } return Result; } ///===---------------------------------------------------------------------===// /// Dbg Intrinsic utilities /// /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value /// that has an associated llvm.dbg.decl intrinsic. bool ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, StoreInst *SI, DIBuilder &Builder); /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value /// that has an associated llvm.dbg.decl intrinsic. bool ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, LoadInst *LI, DIBuilder &Builder); /// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set /// of llvm.dbg.value intrinsics. bool LowerDbgDeclare(Function &F); /// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic corresponding to /// an alloca, if any. DbgDeclareInst *FindAllocaDbgDeclare(Value *V); /// \brief Replaces llvm.dbg.declare instruction when an alloca is replaced with /// a new value. If Deref is true, an additional DW_OP_deref is prepended to the /// expression. If Offset is non-zero, a constant displacement is added to the /// expression (after the optional Deref). Offset can be negative. bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, DIBuilder &Builder, bool Deref, int Offset = 0); /// Replace 'BB's terminator with one that does not have an unwind successor /// block. Rewrites `invoke` to `call`, `catchendpad unwind label %foo` to /// `catchendpad unwind to caller`, etc. Updates any PHIs in unwind successor. /// /// \param BB Block whose terminator will be replaced. Its terminator must /// have an unwind successor. void removeUnwindEdge(BasicBlock *BB); /// \brief Remove all blocks that can not be reached from the function's entry. /// /// Returns true if any basic block was removed. bool removeUnreachableBlocks(Function &F); /// \brief Combine the metadata of two instructions so that K can replace J /// /// Metadata not listed as known via KnownIDs is removed void combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsigned> KnownIDs); /// \brief Replace each use of 'From' with 'To' if that use is dominated by /// the given edge. Returns the number of replacements made. unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge); /// \brief Replace each use of 'From' with 'To' if that use is dominated by /// the given BasicBlock. Returns the number of replacements made. unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlock *BB); /// \brief Return true if the CallSite CS calls a gc leaf function. /// /// A leaf function is a function that does not safepoint the thread during its /// execution. During a call or invoke to such a function, the callers stack /// does not have to be made parseable. /// /// Most passes can and should ignore this information, and it is only used /// during lowering by the GC infrastructure. bool callsGCLeafFunction(ImmutableCallSite CS); } // End llvm namespace #endif