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/IRBuilder.h"
19#include "llvm/Operator.h"
20#include "llvm/Support/GetElementPtrTypeIterator.h"
21#include "llvm/Target/TargetData.h"
22
23namespace llvm {
24
25class User;
26class BasicBlock;
27class Function;
28class BranchInst;
29class Instruction;
30class DbgDeclareInst;
31class StoreInst;
32class LoadInst;
33class Value;
34class Pass;
35class PHINode;
36class AllocaInst;
37class ConstantExpr;
38class TargetData;
39class TargetLibraryInfo;
40class DIBuilder;
41
42template<typename T> class SmallVectorImpl;
43
44//===----------------------------------------------------------------------===//
45//  Local constant propagation.
46//
47
48/// ConstantFoldTerminator - If a terminator instruction is predicated on a
49/// constant value, convert it into an unconditional branch to the constant
50/// destination.  This is a nontrivial operation because the successors of this
51/// basic block must have their PHI nodes updated.
52/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
53/// conditions and indirectbr addresses this might make dead if
54/// DeleteDeadConditions is true.
55bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false,
56                            const TargetLibraryInfo *TLI = 0);
57
58//===----------------------------------------------------------------------===//
59//  Local dead code elimination.
60//
61
62/// isInstructionTriviallyDead - Return true if the result produced by the
63/// instruction is not used, and the instruction has no side effects.
64///
65bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=0);
66
67/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
68/// trivially dead instruction, delete it.  If that makes any of its operands
69/// trivially dead, delete them too, recursively.  Return true if any
70/// instructions were deleted.
71bool RecursivelyDeleteTriviallyDeadInstructions(Value *V,
72                                                const TargetLibraryInfo *TLI=0);
73
74/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively
75/// dead PHI node, due to being a def-use chain of single-use nodes that
76/// either forms a cycle or is terminated by a trivially dead instruction,
77/// delete it.  If that makes any of its operands trivially dead, delete them
78/// too, recursively.  Return true if a change was made.
79bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=0);
80
81
82/// SimplifyInstructionsInBlock - Scan the specified basic block and try to
83/// simplify any instructions in it and recursively delete dead instructions.
84///
85/// This returns true if it changed the code, note that it can delete
86/// instructions in other blocks as well in this block.
87bool SimplifyInstructionsInBlock(BasicBlock *BB, const TargetData *TD = 0,
88                                 const TargetLibraryInfo *TLI = 0);
89
90//===----------------------------------------------------------------------===//
91//  Control Flow Graph Restructuring.
92//
93
94/// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this
95/// method is called when we're about to delete Pred as a predecessor of BB.  If
96/// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred.
97///
98/// Unlike the removePredecessor method, this attempts to simplify uses of PHI
99/// nodes that collapse into identity values.  For example, if we have:
100///   x = phi(1, 0, 0, 0)
101///   y = and x, z
102///
103/// .. and delete the predecessor corresponding to the '1', this will attempt to
104/// recursively fold the 'and' to 0.
105void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred,
106                                  TargetData *TD = 0);
107
108
109/// MergeBasicBlockIntoOnlyPred - BB is a block with one predecessor and its
110/// predecessor is known to have one successor (BB!).  Eliminate the edge
111/// between them, moving the instructions in the predecessor into BB.  This
112/// deletes the predecessor block.
113///
114void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, Pass *P = 0);
115
116
117/// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an
118/// unconditional branch, and contains no instructions other than PHI nodes,
119/// potential debug intrinsics and the branch.  If possible, eliminate BB by
120/// rewriting all the predecessors to branch to the successor block and return
121/// true.  If we can't transform, return false.
122bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB);
123
124/// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI
125/// nodes in this block. This doesn't try to be clever about PHI nodes
126/// which differ only in the order of the incoming values, but instcombine
127/// orders them so it usually won't matter.
128///
129bool EliminateDuplicatePHINodes(BasicBlock *BB);
130
131/// SimplifyCFG - This function is used to do simplification of a CFG.  For
132/// example, it adjusts branches to branches to eliminate the extra hop, it
133/// eliminates unreachable basic blocks, and does other "peephole" optimization
134/// of the CFG.  It returns true if a modification was made, possibly deleting
135/// the basic block that was pointed to.
136///
137bool SimplifyCFG(BasicBlock *BB, const TargetData *TD = 0);
138
139/// FoldBranchToCommonDest - If this basic block is ONLY a setcc and a branch,
140/// and if a predecessor branches to us and one of our successors, fold the
141/// setcc into the predecessor and use logical operations to pick the right
142/// destination.
143bool FoldBranchToCommonDest(BranchInst *BI);
144
145/// DemoteRegToStack - This function takes a virtual register computed by an
146/// Instruction and replaces it with a slot in the stack frame, allocated via
147/// alloca.  This allows the CFG to be changed around without fear of
148/// invalidating the SSA information for the value.  It returns the pointer to
149/// the alloca inserted to create a stack slot for X.
150///
151AllocaInst *DemoteRegToStack(Instruction &X,
152                             bool VolatileLoads = false,
153                             Instruction *AllocaPoint = 0);
154
155/// DemotePHIToStack - This function takes a virtual register computed by a phi
156/// node and replaces it with a slot in the stack frame, allocated via alloca.
157/// The phi node is deleted and it returns the pointer to the alloca inserted.
158AllocaInst *DemotePHIToStack(PHINode *P, Instruction *AllocaPoint = 0);
159
160/// getOrEnforceKnownAlignment - If the specified pointer has an alignment that
161/// we can determine, return it, otherwise return 0.  If PrefAlign is specified,
162/// and it is more than the alignment of the ultimate object, see if we can
163/// increase the alignment of the ultimate object, making this check succeed.
164unsigned getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign,
165                                    const TargetData *TD = 0);
166
167/// getKnownAlignment - Try to infer an alignment for the specified pointer.
168static inline unsigned getKnownAlignment(Value *V, const TargetData *TD = 0) {
169  return getOrEnforceKnownAlignment(V, 0, TD);
170}
171
172/// EmitGEPOffset - Given a getelementptr instruction/constantexpr, emit the
173/// code necessary to compute the offset from the base pointer (without adding
174/// in the base pointer).  Return the result as a signed integer of intptr size.
175/// When NoAssumptions is true, no assumptions about index computation not
176/// overflowing is made.
177template<typename IRBuilderTy>
178Value *EmitGEPOffset(IRBuilderTy *Builder, const TargetData &TD, User *GEP,
179                     bool NoAssumptions = false) {
180  gep_type_iterator GTI = gep_type_begin(GEP);
181  Type *IntPtrTy = TD.getIntPtrType(GEP->getContext());
182  Value *Result = Constant::getNullValue(IntPtrTy);
183
184  // If the GEP is inbounds, we know that none of the addressing operations will
185  // overflow in an unsigned sense.
186  bool isInBounds = cast<GEPOperator>(GEP)->isInBounds() && !NoAssumptions;
187
188  // Build a mask for high order bits.
189  unsigned IntPtrWidth = TD.getPointerSizeInBits();
190  uint64_t PtrSizeMask = ~0ULL >> (64-IntPtrWidth);
191
192  for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); i != e;
193       ++i, ++GTI) {
194    Value *Op = *i;
195    uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType()) & PtrSizeMask;
196    if (ConstantInt *OpC = dyn_cast<ConstantInt>(Op)) {
197      if (OpC->isZero()) continue;
198
199      // Handle a struct index, which adds its field offset to the pointer.
200      if (StructType *STy = dyn_cast<StructType>(*GTI)) {
201        Size = TD.getStructLayout(STy)->getElementOffset(OpC->getZExtValue());
202
203        if (Size)
204          Result = Builder->CreateAdd(Result, ConstantInt::get(IntPtrTy, Size),
205                                      GEP->getName()+".offs");
206        continue;
207      }
208
209      Constant *Scale = ConstantInt::get(IntPtrTy, Size);
210      Constant *OC = ConstantExpr::getIntegerCast(OpC, IntPtrTy, true /*SExt*/);
211      Scale = ConstantExpr::getMul(OC, Scale, isInBounds/*NUW*/);
212      // Emit an add instruction.
213      Result = Builder->CreateAdd(Result, Scale, GEP->getName()+".offs");
214      continue;
215    }
216    // Convert to correct type.
217    if (Op->getType() != IntPtrTy)
218      Op = Builder->CreateIntCast(Op, IntPtrTy, true, Op->getName()+".c");
219    if (Size != 1) {
220      // We'll let instcombine(mul) convert this to a shl if possible.
221      Op = Builder->CreateMul(Op, ConstantInt::get(IntPtrTy, Size),
222                              GEP->getName()+".idx", isInBounds /*NUW*/);
223    }
224
225    // Emit an add instruction.
226    Result = Builder->CreateAdd(Op, Result, GEP->getName()+".offs");
227  }
228  return Result;
229}
230
231///===---------------------------------------------------------------------===//
232///  Dbg Intrinsic utilities
233///
234
235/// Inserts a llvm.dbg.value instrinsic before the stores to an alloca'd value
236/// that has an associated llvm.dbg.decl intrinsic.
237bool ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
238                                     StoreInst *SI, DIBuilder &Builder);
239
240/// Inserts a llvm.dbg.value instrinsic before the stores to an alloca'd value
241/// that has an associated llvm.dbg.decl intrinsic.
242bool ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
243                                     LoadInst *LI, DIBuilder &Builder);
244
245/// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set
246/// of llvm.dbg.value intrinsics.
247bool LowerDbgDeclare(Function &F);
248
249/// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic corresponding to
250/// an alloca, if any.
251DbgDeclareInst *FindAllocaDbgDeclare(Value *V);
252
253} // End llvm namespace
254
255#endif
256