1 //===-- Local.h - Functions to perform local transformations ----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This family of functions perform various local transformations to the
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_TRANSFORMS_UTILS_LOCAL_H
16 #define LLVM_TRANSFORMS_UTILS_LOCAL_H
18 #include "llvm/IR/DataLayout.h"
19 #include "llvm/IR/GetElementPtrTypeIterator.h"
20 #include "llvm/IR/IRBuilder.h"
21 #include "llvm/IR/Operator.h"
39 class TargetLibraryInfo;
40 class TargetTransformInfo;
44 template<typename T> class SmallVectorImpl;
46 //===----------------------------------------------------------------------===//
47 // Local constant propagation.
50 /// ConstantFoldTerminator - If a terminator instruction is predicated on a
51 /// constant value, convert it into an unconditional branch to the constant
52 /// destination. This is a nontrivial operation because the successors of this
53 /// basic block must have their PHI nodes updated.
54 /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
55 /// conditions and indirectbr addresses this might make dead if
56 /// DeleteDeadConditions is true.
57 bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false,
58 const TargetLibraryInfo *TLI = nullptr);
60 //===----------------------------------------------------------------------===//
61 // Local dead code elimination.
64 /// isInstructionTriviallyDead - Return true if the result produced by the
65 /// instruction is not used, and the instruction has no side effects.
67 bool isInstructionTriviallyDead(Instruction *I,
68 const TargetLibraryInfo *TLI = nullptr);
70 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
71 /// trivially dead instruction, delete it. If that makes any of its operands
72 /// trivially dead, delete them too, recursively. Return true if any
73 /// instructions were deleted.
74 bool RecursivelyDeleteTriviallyDeadInstructions(Value *V,
75 const TargetLibraryInfo *TLI = nullptr);
77 /// RecursivelyDeleteDeadPHINode - If the specified value is an effectively
78 /// dead PHI node, due to being a def-use chain of single-use nodes that
79 /// either forms a cycle or is terminated by a trivially dead instruction,
80 /// delete it. If that makes any of its operands trivially dead, delete them
81 /// too, recursively. Return true if a change was made.
82 bool RecursivelyDeleteDeadPHINode(PHINode *PN,
83 const TargetLibraryInfo *TLI = nullptr);
86 /// SimplifyInstructionsInBlock - Scan the specified basic block and try to
87 /// simplify any instructions in it and recursively delete dead instructions.
89 /// This returns true if it changed the code, note that it can delete
90 /// instructions in other blocks as well in this block.
91 bool SimplifyInstructionsInBlock(BasicBlock *BB, const DataLayout *TD = nullptr,
92 const TargetLibraryInfo *TLI = nullptr);
94 //===----------------------------------------------------------------------===//
95 // Control Flow Graph Restructuring.
98 /// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this
99 /// method is called when we're about to delete Pred as a predecessor of BB. If
100 /// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred.
102 /// Unlike the removePredecessor method, this attempts to simplify uses of PHI
103 /// nodes that collapse into identity values. For example, if we have:
104 /// x = phi(1, 0, 0, 0)
107 /// .. and delete the predecessor corresponding to the '1', this will attempt to
108 /// recursively fold the 'and' to 0.
109 void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred,
110 DataLayout *TD = nullptr);
113 /// MergeBasicBlockIntoOnlyPred - BB is a block with one predecessor and its
114 /// predecessor is known to have one successor (BB!). Eliminate the edge
115 /// between them, moving the instructions in the predecessor into BB. This
116 /// deletes the predecessor block.
118 void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, Pass *P = nullptr);
121 /// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an
122 /// unconditional branch, and contains no instructions other than PHI nodes,
123 /// potential debug intrinsics and the branch. If possible, eliminate BB by
124 /// rewriting all the predecessors to branch to the successor block and return
125 /// true. If we can't transform, return false.
126 bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB);
128 /// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI
129 /// nodes in this block. This doesn't try to be clever about PHI nodes
130 /// which differ only in the order of the incoming values, but instcombine
131 /// orders them so it usually won't matter.
133 bool EliminateDuplicatePHINodes(BasicBlock *BB);
135 /// SimplifyCFG - This function is used to do simplification of a CFG. For
136 /// example, it adjusts branches to branches to eliminate the extra hop, it
137 /// eliminates unreachable basic blocks, and does other "peephole" optimization
138 /// of the CFG. It returns true if a modification was made, possibly deleting
139 /// the basic block that was pointed to.
141 bool SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI,
142 const DataLayout *TD = nullptr);
144 /// FlatternCFG - This function is used to flatten a CFG. For
145 /// example, it uses parallel-and and parallel-or mode to collapse
146 // if-conditions and merge if-regions with identical statements.
148 bool FlattenCFG(BasicBlock *BB, AliasAnalysis *AA = nullptr);
150 /// FoldBranchToCommonDest - If this basic block is ONLY a setcc and a branch,
151 /// and if a predecessor branches to us and one of our successors, fold the
152 /// setcc into the predecessor and use logical operations to pick the right
154 bool FoldBranchToCommonDest(BranchInst *BI);
156 /// DemoteRegToStack - This function takes a virtual register computed by an
157 /// Instruction and replaces it with a slot in the stack frame, allocated via
158 /// alloca. This allows the CFG to be changed around without fear of
159 /// invalidating the SSA information for the value. It returns the pointer to
160 /// the alloca inserted to create a stack slot for X.
162 AllocaInst *DemoteRegToStack(Instruction &X,
163 bool VolatileLoads = false,
164 Instruction *AllocaPoint = nullptr);
166 /// DemotePHIToStack - This function takes a virtual register computed by a phi
167 /// node and replaces it with a slot in the stack frame, allocated via alloca.
168 /// The phi node is deleted and it returns the pointer to the alloca inserted.
169 AllocaInst *DemotePHIToStack(PHINode *P, Instruction *AllocaPoint = nullptr);
171 /// getOrEnforceKnownAlignment - If the specified pointer has an alignment that
172 /// we can determine, return it, otherwise return 0. If PrefAlign is specified,
173 /// and it is more than the alignment of the ultimate object, see if we can
174 /// increase the alignment of the ultimate object, making this check succeed.
175 unsigned getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign,
176 const DataLayout *TD = nullptr);
178 /// getKnownAlignment - Try to infer an alignment for the specified pointer.
179 static inline unsigned getKnownAlignment(Value *V,
180 const DataLayout *TD = nullptr) {
181 return getOrEnforceKnownAlignment(V, 0, TD);
184 /// EmitGEPOffset - Given a getelementptr instruction/constantexpr, emit the
185 /// code necessary to compute the offset from the base pointer (without adding
186 /// in the base pointer). Return the result as a signed integer of intptr size.
187 /// When NoAssumptions is true, no assumptions about index computation not
188 /// overflowing is made.
189 template<typename IRBuilderTy>
190 Value *EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &TD, User *GEP,
191 bool NoAssumptions = false) {
192 GEPOperator *GEPOp = cast<GEPOperator>(GEP);
193 Type *IntPtrTy = TD.getIntPtrType(GEP->getType());
194 Value *Result = Constant::getNullValue(IntPtrTy);
196 // If the GEP is inbounds, we know that none of the addressing operations will
197 // overflow in an unsigned sense.
198 bool isInBounds = GEPOp->isInBounds() && !NoAssumptions;
200 // Build a mask for high order bits.
201 unsigned IntPtrWidth = IntPtrTy->getScalarType()->getIntegerBitWidth();
202 uint64_t PtrSizeMask = ~0ULL >> (64 - IntPtrWidth);
204 gep_type_iterator GTI = gep_type_begin(GEP);
205 for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); i != e;
208 uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType()) & PtrSizeMask;
209 if (Constant *OpC = dyn_cast<Constant>(Op)) {
210 if (OpC->isZeroValue())
213 // Handle a struct index, which adds its field offset to the pointer.
214 if (StructType *STy = dyn_cast<StructType>(*GTI)) {
215 if (OpC->getType()->isVectorTy())
216 OpC = OpC->getSplatValue();
218 uint64_t OpValue = cast<ConstantInt>(OpC)->getZExtValue();
219 Size = TD.getStructLayout(STy)->getElementOffset(OpValue);
222 Result = Builder->CreateAdd(Result, ConstantInt::get(IntPtrTy, Size),
223 GEP->getName()+".offs");
227 Constant *Scale = ConstantInt::get(IntPtrTy, Size);
228 Constant *OC = ConstantExpr::getIntegerCast(OpC, IntPtrTy, true /*SExt*/);
229 Scale = ConstantExpr::getMul(OC, Scale, isInBounds/*NUW*/);
230 // Emit an add instruction.
231 Result = Builder->CreateAdd(Result, Scale, GEP->getName()+".offs");
234 // Convert to correct type.
235 if (Op->getType() != IntPtrTy)
236 Op = Builder->CreateIntCast(Op, IntPtrTy, true, Op->getName()+".c");
238 // We'll let instcombine(mul) convert this to a shl if possible.
239 Op = Builder->CreateMul(Op, ConstantInt::get(IntPtrTy, Size),
240 GEP->getName()+".idx", isInBounds /*NUW*/);
243 // Emit an add instruction.
244 Result = Builder->CreateAdd(Op, Result, GEP->getName()+".offs");
249 ///===---------------------------------------------------------------------===//
250 /// Dbg Intrinsic utilities
253 /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value
254 /// that has an associated llvm.dbg.decl intrinsic.
255 bool ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
256 StoreInst *SI, DIBuilder &Builder);
258 /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value
259 /// that has an associated llvm.dbg.decl intrinsic.
260 bool ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
261 LoadInst *LI, DIBuilder &Builder);
263 /// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set
264 /// of llvm.dbg.value intrinsics.
265 bool LowerDbgDeclare(Function &F);
267 /// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic corresponding to
268 /// an alloca, if any.
269 DbgDeclareInst *FindAllocaDbgDeclare(Value *V);
271 /// replaceDbgDeclareForAlloca - Replaces llvm.dbg.declare instruction when
272 /// alloca is replaced with a new value.
273 bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
276 /// \brief Remove all blocks that can not be reached from the function's entry.
278 /// Returns true if any basic block was removed.
279 bool removeUnreachableBlocks(Function &F);
281 } // End llvm namespace