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