1//===-- Local.h - Functions to perform local transformations ----*- 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// 10// This family of functions perform various local transformations to the 11// program. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef LLVM_TRANSFORMS_UTILS_LOCAL_H 16#define LLVM_TRANSFORMS_UTILS_LOCAL_H 17 18#include "llvm/Analysis/AliasAnalysis.h" 19#include "llvm/IR/DataLayout.h" 20#include "llvm/IR/Dominators.h" 21#include "llvm/IR/GetElementPtrTypeIterator.h" 22#include "llvm/IR/IRBuilder.h" 23#include "llvm/IR/Operator.h" 24#include "llvm/ADT/SmallPtrSet.h" 25 26namespace llvm { 27 28class User; 29class BasicBlock; 30class Function; 31class BranchInst; 32class Instruction; 33class CallInst; 34class DbgDeclareInst; 35class StoreInst; 36class LoadInst; 37class Value; 38class PHINode; 39class AllocaInst; 40class AssumptionCache; 41class ConstantExpr; 42class DataLayout; 43class TargetLibraryInfo; 44class TargetTransformInfo; 45class DIBuilder; 46class DominatorTree; 47class LazyValueInfo; 48 49template<typename T> class SmallVectorImpl; 50 51//===----------------------------------------------------------------------===// 52// Local constant propagation. 53// 54 55/// If a terminator instruction is predicated on a constant value, convert it 56/// into an unconditional branch to the constant destination. 57/// This is a nontrivial operation because the successors of this basic block 58/// must have their PHI nodes updated. 59/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch 60/// conditions and indirectbr addresses this might make dead if 61/// DeleteDeadConditions is true. 62bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false, 63 const TargetLibraryInfo *TLI = nullptr); 64 65//===----------------------------------------------------------------------===// 66// Local dead code elimination. 67// 68 69/// Return true if the result produced by the instruction is not used, and the 70/// instruction has no side effects. 71bool isInstructionTriviallyDead(Instruction *I, 72 const TargetLibraryInfo *TLI = nullptr); 73 74/// If the specified value is a trivially dead instruction, delete it. 75/// If that makes any of its operands trivially dead, delete them too, 76/// recursively. Return true if any instructions were deleted. 77bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, 78 const TargetLibraryInfo *TLI = nullptr); 79 80/// If the specified value is an effectively dead PHI node, due to being a 81/// def-use chain of single-use nodes that either forms a cycle or is terminated 82/// by a trivially dead instruction, delete it. If that makes any of its 83/// operands trivially dead, delete them too, recursively. Return true if a 84/// change was made. 85bool RecursivelyDeleteDeadPHINode(PHINode *PN, 86 const TargetLibraryInfo *TLI = nullptr); 87 88/// Scan the specified basic block and try to simplify any instructions in it 89/// and recursively delete dead instructions. 90/// 91/// This returns true if it changed the code, note that it can delete 92/// instructions in other blocks as well in this block. 93bool SimplifyInstructionsInBlock(BasicBlock *BB, 94 const TargetLibraryInfo *TLI = nullptr); 95 96//===----------------------------------------------------------------------===// 97// Control Flow Graph Restructuring. 98// 99 100/// Like BasicBlock::removePredecessor, this method is called when we're about 101/// to delete Pred as a predecessor of BB. If BB contains any PHI nodes, this 102/// drops the entries in the PHI nodes for Pred. 103/// 104/// Unlike the removePredecessor method, this attempts to simplify uses of PHI 105/// nodes that collapse into identity values. For example, if we have: 106/// x = phi(1, 0, 0, 0) 107/// y = and x, z 108/// 109/// .. and delete the predecessor corresponding to the '1', this will attempt to 110/// recursively fold the 'and' to 0. 111void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred); 112 113/// BB is a block with one predecessor and its predecessor is known to have one 114/// successor (BB!). Eliminate the edge between them, moving the instructions in 115/// the predecessor into BB. This deletes the predecessor block. 116void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT = nullptr); 117 118/// BB is known to contain an unconditional branch, and contains no instructions 119/// other than PHI nodes, potential debug intrinsics and the branch. If 120/// possible, eliminate BB by rewriting all the predecessors to branch to the 121/// successor block and return true. If we can't transform, return false. 122bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB); 123 124/// Check for and eliminate duplicate PHI nodes in this block. This doesn't try 125/// to be clever about PHI nodes which differ only in the order of the incoming 126/// values, but instcombine orders them so it usually won't matter. 127bool EliminateDuplicatePHINodes(BasicBlock *BB); 128 129/// This function is used to do simplification of a CFG. For 130/// example, it adjusts branches to branches to eliminate the extra hop, it 131/// eliminates unreachable basic blocks, and does other "peephole" optimization 132/// of the CFG. It returns true if a modification was made, possibly deleting 133/// the basic block that was pointed to. LoopHeaders is an optional input 134/// parameter, providing the set of loop header that SimplifyCFG should not 135/// eliminate. 136bool SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, 137 unsigned BonusInstThreshold, AssumptionCache *AC = nullptr, 138 SmallPtrSetImpl<BasicBlock *> *LoopHeaders = nullptr); 139 140/// This function is used to flatten a CFG. For example, it uses parallel-and 141/// and parallel-or mode to collapse if-conditions and merge if-regions with 142/// identical statements. 143bool FlattenCFG(BasicBlock *BB, AliasAnalysis *AA = nullptr); 144 145/// If this basic block is ONLY a setcc and a branch, and if a predecessor 146/// branches to us and one of our successors, fold the setcc into the 147/// predecessor and use logical operations to pick the right destination. 148bool FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold = 1); 149 150/// This function takes a virtual register computed by an Instruction and 151/// replaces it with a slot in the stack frame, allocated via alloca. 152/// This allows the CFG to be changed around without fear of invalidating the 153/// SSA information for the value. It returns the pointer to the alloca inserted 154/// to create a stack slot for X. 155AllocaInst *DemoteRegToStack(Instruction &X, 156 bool VolatileLoads = false, 157 Instruction *AllocaPoint = nullptr); 158 159/// This function takes a virtual register computed by a phi node and replaces 160/// it with a slot in the stack frame, allocated via alloca. The phi node is 161/// deleted and it returns the pointer to the alloca inserted. 162AllocaInst *DemotePHIToStack(PHINode *P, Instruction *AllocaPoint = nullptr); 163 164/// If the specified pointer has an alignment that we can determine, return it, 165/// otherwise return 0. If PrefAlign is specified, and it is more than the 166/// alignment of the ultimate object, see if we can increase the alignment of 167/// the ultimate object, making this check succeed. 168unsigned getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, 169 const DataLayout &DL, 170 const Instruction *CxtI = nullptr, 171 AssumptionCache *AC = nullptr, 172 const DominatorTree *DT = nullptr); 173 174/// Try to infer an alignment for the specified pointer. 175static inline unsigned getKnownAlignment(Value *V, const DataLayout &DL, 176 const Instruction *CxtI = nullptr, 177 AssumptionCache *AC = nullptr, 178 const DominatorTree *DT = nullptr) { 179 return getOrEnforceKnownAlignment(V, 0, DL, CxtI, AC, DT); 180} 181 182/// Given a getelementptr instruction/constantexpr, emit the code necessary to 183/// compute the offset from the base pointer (without adding in the base 184/// pointer). Return the result as a signed integer of intptr size. 185/// When NoAssumptions is true, no assumptions about index computation not 186/// overflowing is made. 187template <typename IRBuilderTy> 188Value *EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &DL, User *GEP, 189 bool NoAssumptions = false) { 190 GEPOperator *GEPOp = cast<GEPOperator>(GEP); 191 Type *IntPtrTy = DL.getIntPtrType(GEP->getType()); 192 Value *Result = Constant::getNullValue(IntPtrTy); 193 194 // If the GEP is inbounds, we know that none of the addressing operations will 195 // overflow in an unsigned sense. 196 bool isInBounds = GEPOp->isInBounds() && !NoAssumptions; 197 198 // Build a mask for high order bits. 199 unsigned IntPtrWidth = IntPtrTy->getScalarType()->getIntegerBitWidth(); 200 uint64_t PtrSizeMask = ~0ULL >> (64 - IntPtrWidth); 201 202 gep_type_iterator GTI = gep_type_begin(GEP); 203 for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); i != e; 204 ++i, ++GTI) { 205 Value *Op = *i; 206 uint64_t Size = DL.getTypeAllocSize(GTI.getIndexedType()) & PtrSizeMask; 207 if (Constant *OpC = dyn_cast<Constant>(Op)) { 208 if (OpC->isZeroValue()) 209 continue; 210 211 // Handle a struct index, which adds its field offset to the pointer. 212 if (StructType *STy = dyn_cast<StructType>(*GTI)) { 213 if (OpC->getType()->isVectorTy()) 214 OpC = OpC->getSplatValue(); 215 216 uint64_t OpValue = cast<ConstantInt>(OpC)->getZExtValue(); 217 Size = DL.getStructLayout(STy)->getElementOffset(OpValue); 218 219 if (Size) 220 Result = Builder->CreateAdd(Result, ConstantInt::get(IntPtrTy, Size), 221 GEP->getName()+".offs"); 222 continue; 223 } 224 225 Constant *Scale = ConstantInt::get(IntPtrTy, Size); 226 Constant *OC = ConstantExpr::getIntegerCast(OpC, IntPtrTy, true /*SExt*/); 227 Scale = ConstantExpr::getMul(OC, Scale, isInBounds/*NUW*/); 228 // Emit an add instruction. 229 Result = Builder->CreateAdd(Result, Scale, GEP->getName()+".offs"); 230 continue; 231 } 232 // Convert to correct type. 233 if (Op->getType() != IntPtrTy) 234 Op = Builder->CreateIntCast(Op, IntPtrTy, true, Op->getName()+".c"); 235 if (Size != 1) { 236 // We'll let instcombine(mul) convert this to a shl if possible. 237 Op = Builder->CreateMul(Op, ConstantInt::get(IntPtrTy, Size), 238 GEP->getName()+".idx", isInBounds /*NUW*/); 239 } 240 241 // Emit an add instruction. 242 Result = Builder->CreateAdd(Op, Result, GEP->getName()+".offs"); 243 } 244 return Result; 245} 246 247///===---------------------------------------------------------------------===// 248/// Dbg Intrinsic utilities 249/// 250 251/// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value 252/// that has an associated llvm.dbg.decl intrinsic. 253bool ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 254 StoreInst *SI, DIBuilder &Builder); 255 256/// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value 257/// that has an associated llvm.dbg.decl intrinsic. 258bool ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 259 LoadInst *LI, DIBuilder &Builder); 260 261/// Lowers llvm.dbg.declare intrinsics into appropriate set of 262/// llvm.dbg.value intrinsics. 263bool LowerDbgDeclare(Function &F); 264 265/// Finds the llvm.dbg.declare intrinsic corresponding to an alloca, if any. 266DbgDeclareInst *FindAllocaDbgDeclare(Value *V); 267 268/// Replaces llvm.dbg.declare instruction when the address it describes 269/// is replaced with a new value. If Deref is true, an additional DW_OP_deref is 270/// prepended to the expression. If Offset is non-zero, a constant displacement 271/// is added to the expression (after the optional Deref). Offset can be 272/// negative. 273bool replaceDbgDeclare(Value *Address, Value *NewAddress, 274 Instruction *InsertBefore, DIBuilder &Builder, 275 bool Deref, int Offset); 276 277/// Replaces llvm.dbg.declare instruction when the alloca it describes 278/// is replaced with a new value. If Deref is true, an additional DW_OP_deref is 279/// prepended to the expression. If Offset is non-zero, a constant displacement 280/// is added to the expression (after the optional Deref). Offset can be 281/// negative. New llvm.dbg.declare is inserted immediately before AI. 282bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, 283 DIBuilder &Builder, bool Deref, int Offset = 0); 284 285/// Replaces multiple llvm.dbg.value instructions when the alloca it describes 286/// is replaced with a new value. If Offset is non-zero, a constant displacement 287/// is added to the expression (after the mandatory Deref). Offset can be 288/// negative. New llvm.dbg.value instructions are inserted at the locations of 289/// the instructions they replace. 290void replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress, 291 DIBuilder &Builder, int Offset = 0); 292 293/// Remove all instructions from a basic block other than it's terminator 294/// and any present EH pad instructions. 295unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB); 296 297/// Insert an unreachable instruction before the specified 298/// instruction, making it and the rest of the code in the block dead. 299unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap); 300 301/// Replace 'BB's terminator with one that does not have an unwind successor 302/// block. Rewrites `invoke` to `call`, etc. Updates any PHIs in unwind 303/// successor. 304/// 305/// \param BB Block whose terminator will be replaced. Its terminator must 306/// have an unwind successor. 307void removeUnwindEdge(BasicBlock *BB); 308 309/// Remove all blocks that can not be reached from the function's entry. 310/// 311/// Returns true if any basic block was removed. 312bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr); 313 314/// Combine the metadata of two instructions so that K can replace J 315/// 316/// Metadata not listed as known via KnownIDs is removed 317void combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsigned> KnownIDs); 318 319/// Replace each use of 'From' with 'To' if that use is dominated by 320/// the given edge. Returns the number of replacements made. 321unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, 322 const BasicBlockEdge &Edge); 323/// Replace each use of 'From' with 'To' if that use is dominated by 324/// the end of the given BasicBlock. Returns the number of replacements made. 325unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, 326 const BasicBlock *BB); 327 328 329/// Return true if the CallSite CS calls a gc leaf function. 330/// 331/// A leaf function is a function that does not safepoint the thread during its 332/// execution. During a call or invoke to such a function, the callers stack 333/// does not have to be made parseable. 334/// 335/// Most passes can and should ignore this information, and it is only used 336/// during lowering by the GC infrastructure. 337bool callsGCLeafFunction(ImmutableCallSite CS); 338 339//===----------------------------------------------------------------------===// 340// Intrinsic pattern matching 341// 342 343/// Try and match a bswap or bitreverse idiom. 344/// 345/// If an idiom is matched, an intrinsic call is inserted before \c I. Any added 346/// instructions are returned in \c InsertedInsts. They will all have been added 347/// to a basic block. 348/// 349/// A bitreverse idiom normally requires around 2*BW nodes to be searched (where 350/// BW is the bitwidth of the integer type). A bswap idiom requires anywhere up 351/// to BW / 4 nodes to be searched, so is significantly faster. 352/// 353/// This function returns true on a successful match or false otherwise. 354bool recognizeBSwapOrBitReverseIdiom( 355 Instruction *I, bool MatchBSwaps, bool MatchBitReversals, 356 SmallVectorImpl<Instruction *> &InsertedInsts); 357 358//===----------------------------------------------------------------------===// 359// Sanitizer utilities 360// 361 362/// Given a CallInst, check if it calls a string function known to CodeGen, 363/// and mark it with NoBuiltin if so. To be used by sanitizers that intend 364/// to intercept string functions and want to avoid converting them to target 365/// specific instructions. 366void maybeMarkSanitizerLibraryCallNoBuiltin(CallInst *CI, 367 const TargetLibraryInfo *TLI); 368 369} // End llvm namespace 370 371#endif 372