1193323Sed//===-- Local.h - Functions to perform local transformations ----*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This family of functions perform various local transformations to the 11193323Sed// program. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#ifndef LLVM_TRANSFORMS_UTILS_LOCAL_H 16193323Sed#define LLVM_TRANSFORMS_UTILS_LOCAL_H 17193323Sed 18252723Sdim#include "llvm/IR/DataLayout.h" 19252723Sdim#include "llvm/IR/IRBuilder.h" 20252723Sdim#include "llvm/IR/Operator.h" 21245431Sdim#include "llvm/Support/GetElementPtrTypeIterator.h" 22245431Sdim 23193323Sednamespace llvm { 24193323Sed 25193323Sedclass User; 26193323Sedclass BasicBlock; 27221345Sdimclass Function; 28195340Sedclass BranchInst; 29193323Sedclass Instruction; 30221345Sdimclass DbgDeclareInst; 31221345Sdimclass StoreInst; 32221345Sdimclass LoadInst; 33193323Sedclass Value; 34193323Sedclass Pass; 35193323Sedclass PHINode; 36193323Sedclass AllocaInst; 37193323Sedclass ConstantExpr; 38245431Sdimclass DataLayout; 39245431Sdimclass TargetLibraryInfo; 40245431Sdimclass TargetTransformInfo; 41221345Sdimclass DIBuilder; 42263509Sdimclass AliasAnalysis; 43193323Sed 44193323Sedtemplate<typename T> class SmallVectorImpl; 45263509Sdim 46193323Sed//===----------------------------------------------------------------------===// 47193323Sed// Local constant propagation. 48193323Sed// 49193323Sed 50193323Sed/// ConstantFoldTerminator - If a terminator instruction is predicated on a 51193323Sed/// constant value, convert it into an unconditional branch to the constant 52193323Sed/// destination. This is a nontrivial operation because the successors of this 53193323Sed/// basic block must have their PHI nodes updated. 54223017Sdim/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch 55223017Sdim/// conditions and indirectbr addresses this might make dead if 56223017Sdim/// DeleteDeadConditions is true. 57245431Sdimbool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false, 58245431Sdim const TargetLibraryInfo *TLI = 0); 59193323Sed 60193323Sed//===----------------------------------------------------------------------===// 61193323Sed// Local dead code elimination. 62193323Sed// 63193323Sed 64193323Sed/// isInstructionTriviallyDead - Return true if the result produced by the 65193323Sed/// instruction is not used, and the instruction has no side effects. 66193323Sed/// 67245431Sdimbool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=0); 68193323Sed 69193323Sed/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a 70193323Sed/// trivially dead instruction, delete it. If that makes any of its operands 71202375Srdivacky/// trivially dead, delete them too, recursively. Return true if any 72202375Srdivacky/// instructions were deleted. 73245431Sdimbool RecursivelyDeleteTriviallyDeadInstructions(Value *V, 74245431Sdim const TargetLibraryInfo *TLI=0); 75193323Sed 76193323Sed/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively 77193323Sed/// dead PHI node, due to being a def-use chain of single-use nodes that 78193323Sed/// either forms a cycle or is terminated by a trivially dead instruction, 79193323Sed/// delete it. If that makes any of its operands trivially dead, delete them 80219077Sdim/// too, recursively. Return true if a change was made. 81245431Sdimbool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=0); 82193323Sed 83263509Sdim 84202375Srdivacky/// SimplifyInstructionsInBlock - Scan the specified basic block and try to 85202375Srdivacky/// simplify any instructions in it and recursively delete dead instructions. 86202375Srdivacky/// 87202375Srdivacky/// This returns true if it changed the code, note that it can delete 88202375Srdivacky/// instructions in other blocks as well in this block. 89245431Sdimbool SimplifyInstructionsInBlock(BasicBlock *BB, const DataLayout *TD = 0, 90245431Sdim const TargetLibraryInfo *TLI = 0); 91263509Sdim 92193323Sed//===----------------------------------------------------------------------===// 93193323Sed// Control Flow Graph Restructuring. 94193323Sed// 95193323Sed 96199481Srdivacky/// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this 97199481Srdivacky/// method is called when we're about to delete Pred as a predecessor of BB. If 98199481Srdivacky/// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred. 99199481Srdivacky/// 100199481Srdivacky/// Unlike the removePredecessor method, this attempts to simplify uses of PHI 101199481Srdivacky/// nodes that collapse into identity values. For example, if we have: 102199481Srdivacky/// x = phi(1, 0, 0, 0) 103199481Srdivacky/// y = and x, z 104199481Srdivacky/// 105199481Srdivacky/// .. and delete the predecessor corresponding to the '1', this will attempt to 106199481Srdivacky/// recursively fold the 'and' to 0. 107199481Srdivackyvoid RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, 108245431Sdim DataLayout *TD = 0); 109263509Sdim 110263509Sdim 111193323Sed/// MergeBasicBlockIntoOnlyPred - BB is a block with one predecessor and its 112193323Sed/// predecessor is known to have one successor (BB!). Eliminate the edge 113193323Sed/// between them, moving the instructions in the predecessor into BB. This 114193323Sed/// deletes the predecessor block. 115193323Sed/// 116198090Srdivackyvoid MergeBasicBlockIntoOnlyPred(BasicBlock *BB, Pass *P = 0); 117199481Srdivacky 118263509Sdim 119199481Srdivacky/// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an 120199481Srdivacky/// unconditional branch, and contains no instructions other than PHI nodes, 121199481Srdivacky/// potential debug intrinsics and the branch. If possible, eliminate BB by 122199481Srdivacky/// rewriting all the predecessors to branch to the successor block and return 123199481Srdivacky/// true. If we can't transform, return false. 124199481Srdivackybool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB); 125199511Srdivacky 126199511Srdivacky/// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI 127199511Srdivacky/// nodes in this block. This doesn't try to be clever about PHI nodes 128199511Srdivacky/// which differ only in the order of the incoming values, but instcombine 129199511Srdivacky/// orders them so it usually won't matter. 130199511Srdivacky/// 131199511Srdivackybool EliminateDuplicatePHINodes(BasicBlock *BB); 132199511Srdivacky 133193323Sed/// SimplifyCFG - This function is used to do simplification of a CFG. For 134193323Sed/// example, it adjusts branches to branches to eliminate the extra hop, it 135193323Sed/// eliminates unreachable basic blocks, and does other "peephole" optimization 136193323Sed/// of the CFG. It returns true if a modification was made, possibly deleting 137193323Sed/// the basic block that was pointed to. 138193323Sed/// 139252723Sdimbool SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, 140252723Sdim const DataLayout *TD = 0); 141193323Sed 142263509Sdim/// FlatternCFG - This function is used to flatten a CFG. For 143263509Sdim/// example, it uses parallel-and and parallel-or mode to collapse 144263509Sdim// if-conditions and merge if-regions with identical statements. 145263509Sdim/// 146263509Sdimbool FlattenCFG(BasicBlock *BB, AliasAnalysis *AA = 0); 147263509Sdim 148195340Sed/// FoldBranchToCommonDest - If this basic block is ONLY a setcc and a branch, 149195340Sed/// and if a predecessor branches to us and one of our successors, fold the 150195340Sed/// setcc into the predecessor and use logical operations to pick the right 151195340Sed/// destination. 152195340Sedbool FoldBranchToCommonDest(BranchInst *BI); 153195340Sed 154193323Sed/// DemoteRegToStack - This function takes a virtual register computed by an 155193323Sed/// Instruction and replaces it with a slot in the stack frame, allocated via 156193323Sed/// alloca. This allows the CFG to be changed around without fear of 157193323Sed/// invalidating the SSA information for the value. It returns the pointer to 158193323Sed/// the alloca inserted to create a stack slot for X. 159193323Sed/// 160198090SrdivackyAllocaInst *DemoteRegToStack(Instruction &X, 161198090Srdivacky bool VolatileLoads = false, 162193323Sed Instruction *AllocaPoint = 0); 163193323Sed 164193323Sed/// DemotePHIToStack - This function takes a virtual register computed by a phi 165193323Sed/// node and replaces it with a slot in the stack frame, allocated via alloca. 166263509Sdim/// The phi node is deleted and it returns the pointer to the alloca inserted. 167193323SedAllocaInst *DemotePHIToStack(PHINode *P, Instruction *AllocaPoint = 0); 168193323Sed 169218893Sdim/// getOrEnforceKnownAlignment - If the specified pointer has an alignment that 170218893Sdim/// we can determine, return it, otherwise return 0. If PrefAlign is specified, 171218893Sdim/// and it is more than the alignment of the ultimate object, see if we can 172218893Sdim/// increase the alignment of the ultimate object, making this check succeed. 173218893Sdimunsigned getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, 174245431Sdim const DataLayout *TD = 0); 175218893Sdim 176218893Sdim/// getKnownAlignment - Try to infer an alignment for the specified pointer. 177245431Sdimstatic inline unsigned getKnownAlignment(Value *V, const DataLayout *TD = 0) { 178218893Sdim return getOrEnforceKnownAlignment(V, 0, TD); 179218893Sdim} 180218893Sdim 181245431Sdim/// EmitGEPOffset - Given a getelementptr instruction/constantexpr, emit the 182245431Sdim/// code necessary to compute the offset from the base pointer (without adding 183245431Sdim/// in the base pointer). Return the result as a signed integer of intptr size. 184245431Sdim/// When NoAssumptions is true, no assumptions about index computation not 185245431Sdim/// overflowing is made. 186245431Sdimtemplate<typename IRBuilderTy> 187245431SdimValue *EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &TD, User *GEP, 188245431Sdim bool NoAssumptions = false) { 189263509Sdim GEPOperator *GEPOp = cast<GEPOperator>(GEP); 190263509Sdim Type *IntPtrTy = TD.getIntPtrType(GEP->getType()); 191245431Sdim Value *Result = Constant::getNullValue(IntPtrTy); 192245431Sdim 193245431Sdim // If the GEP is inbounds, we know that none of the addressing operations will 194245431Sdim // overflow in an unsigned sense. 195263509Sdim bool isInBounds = GEPOp->isInBounds() && !NoAssumptions; 196245431Sdim 197245431Sdim // Build a mask for high order bits. 198263509Sdim unsigned IntPtrWidth = IntPtrTy->getScalarType()->getIntegerBitWidth(); 199263509Sdim uint64_t PtrSizeMask = ~0ULL >> (64 - IntPtrWidth); 200245431Sdim 201263509Sdim gep_type_iterator GTI = gep_type_begin(GEP); 202245431Sdim for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); i != e; 203245431Sdim ++i, ++GTI) { 204245431Sdim Value *Op = *i; 205245431Sdim uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType()) & PtrSizeMask; 206263509Sdim if (Constant *OpC = dyn_cast<Constant>(Op)) { 207263509Sdim if (OpC->isZeroValue()) 208263509Sdim continue; 209245431Sdim 210245431Sdim // Handle a struct index, which adds its field offset to the pointer. 211245431Sdim if (StructType *STy = dyn_cast<StructType>(*GTI)) { 212263509Sdim if (OpC->getType()->isVectorTy()) 213263509Sdim OpC = OpC->getSplatValue(); 214245431Sdim 215263509Sdim uint64_t OpValue = cast<ConstantInt>(OpC)->getZExtValue(); 216263509Sdim Size = TD.getStructLayout(STy)->getElementOffset(OpValue); 217263509Sdim 218245431Sdim if (Size) 219245431Sdim Result = Builder->CreateAdd(Result, ConstantInt::get(IntPtrTy, Size), 220245431Sdim GEP->getName()+".offs"); 221245431Sdim continue; 222245431Sdim } 223245431Sdim 224245431Sdim Constant *Scale = ConstantInt::get(IntPtrTy, Size); 225245431Sdim Constant *OC = ConstantExpr::getIntegerCast(OpC, IntPtrTy, true /*SExt*/); 226245431Sdim Scale = ConstantExpr::getMul(OC, Scale, isInBounds/*NUW*/); 227245431Sdim // Emit an add instruction. 228245431Sdim Result = Builder->CreateAdd(Result, Scale, GEP->getName()+".offs"); 229245431Sdim continue; 230245431Sdim } 231245431Sdim // Convert to correct type. 232245431Sdim if (Op->getType() != IntPtrTy) 233245431Sdim Op = Builder->CreateIntCast(Op, IntPtrTy, true, Op->getName()+".c"); 234245431Sdim if (Size != 1) { 235245431Sdim // We'll let instcombine(mul) convert this to a shl if possible. 236245431Sdim Op = Builder->CreateMul(Op, ConstantInt::get(IntPtrTy, Size), 237245431Sdim GEP->getName()+".idx", isInBounds /*NUW*/); 238245431Sdim } 239245431Sdim 240245431Sdim // Emit an add instruction. 241245431Sdim Result = Builder->CreateAdd(Op, Result, GEP->getName()+".offs"); 242245431Sdim } 243245431Sdim return Result; 244245431Sdim} 245245431Sdim 246221345Sdim///===---------------------------------------------------------------------===// 247221345Sdim/// Dbg Intrinsic utilities 248221345Sdim/// 249221345Sdim 250252723Sdim/// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value 251221345Sdim/// that has an associated llvm.dbg.decl intrinsic. 252221345Sdimbool ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 253221345Sdim StoreInst *SI, DIBuilder &Builder); 254221345Sdim 255252723Sdim/// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value 256221345Sdim/// that has an associated llvm.dbg.decl intrinsic. 257221345Sdimbool ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 258221345Sdim LoadInst *LI, DIBuilder &Builder); 259221345Sdim 260221345Sdim/// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set 261221345Sdim/// of llvm.dbg.value intrinsics. 262221345Sdimbool LowerDbgDeclare(Function &F); 263221345Sdim 264223017Sdim/// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic corresponding to 265223017Sdim/// an alloca, if any. 266223017SdimDbgDeclareInst *FindAllocaDbgDeclare(Value *V); 267223017Sdim 268252723Sdim/// replaceDbgDeclareForAlloca - Replaces llvm.dbg.declare instruction when 269252723Sdim/// alloca is replaced with a new value. 270252723Sdimbool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, 271252723Sdim DIBuilder &Builder); 272252723Sdim 273252723Sdim/// \brief Remove all blocks that can not be reached from the function's entry. 274252723Sdim/// 275252723Sdim/// Returns true if any basic block was removed. 276252723Sdimbool removeUnreachableBlocks(Function &F); 277252723Sdim 278193323Sed} // End llvm namespace 279193323Sed 280193323Sed#endif 281