LLVM  6.0.0svn
BasicBlockUtils.h
Go to the documentation of this file.
1 //===- Transform/Utils/BasicBlockUtils.h - BasicBlock Utils -----*- 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 manipulations on basic blocks, and
11 // instructions contained within basic blocks.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H
16 #define LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H
17 
18 // FIXME: Move to this file: BasicBlock::removePredecessor, BB::splitBasicBlock
19 
20 #include "llvm/ADT/ArrayRef.h"
21 #include "llvm/IR/BasicBlock.h"
22 #include "llvm/IR/CFG.h"
23 #include "llvm/IR/InstrTypes.h"
24 #include <cassert>
25 
26 namespace llvm {
27 
28 class DominatorTree;
29 class Function;
30 class Instruction;
31 class LoopInfo;
32 class MDNode;
33 class MemoryDependenceResults;
34 class ReturnInst;
35 class TargetLibraryInfo;
36 class Value;
37 
38 /// Delete the specified block, which must have no predecessors.
39 void DeleteDeadBlock(BasicBlock *BB);
40 
41 /// We know that BB has one predecessor. If there are any single-entry PHI nodes
42 /// in it, fold them away. This handles the case when all entries to the PHI
43 /// nodes in a block are guaranteed equal, such as when the block has exactly
44 /// one predecessor.
46  MemoryDependenceResults *MemDep = nullptr);
47 
48 /// Examine each PHI in the given block and delete it if it is dead. Also
49 /// recursively delete any operands that become dead as a result. This includes
50 /// tracing the def-use list from the PHI to see if it is ultimately unused or
51 /// if it reaches an unused cycle. Return true if any PHIs were deleted.
52 bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr);
53 
54 /// Attempts to merge a block into its predecessor, if possible. The return
55 /// value indicates success or failure.
56 bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT = nullptr,
57  LoopInfo *LI = nullptr,
58  MemoryDependenceResults *MemDep = nullptr);
59 
60 /// Replace all uses of an instruction (specified by BI) with a value, then
61 /// remove and delete the original instruction.
63  BasicBlock::iterator &BI, Value *V);
64 
65 /// Replace the instruction specified by BI with the instruction specified by I.
66 /// Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. The
67 /// original instruction is deleted and BI is updated to point to the new
68 /// instruction.
70  BasicBlock::iterator &BI, Instruction *I);
71 
72 /// Replace the instruction specified by From with the instruction specified by
73 /// To. Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc.
74 void ReplaceInstWithInst(Instruction *From, Instruction *To);
75 
76 /// Option class for critical edge splitting.
77 ///
78 /// This provides a builder interface for overriding the default options used
79 /// during critical edge splitting.
83  bool MergeIdenticalEdges = false;
84  bool DontDeleteUselessPHIs = false;
85  bool PreserveLCSSA = false;
86 
88  LoopInfo *LI = nullptr)
89  : DT(DT), LI(LI) {}
90 
92  MergeIdenticalEdges = true;
93  return *this;
94  }
95 
97  DontDeleteUselessPHIs = true;
98  return *this;
99  }
100 
102  PreserveLCSSA = true;
103  return *this;
104  }
105 };
106 
107 /// If this edge is a critical edge, insert a new node to split the critical
108 /// edge. This will update the analyses passed in through the option struct.
109 /// This returns the new block if the edge was split, null otherwise.
110 ///
111 /// If MergeIdenticalEdges in the options struct is true (not the default),
112 /// *all* edges from TI to the specified successor will be merged into the same
113 /// critical edge block. This is most commonly interesting with switch
114 /// instructions, which may have many edges to any one destination. This
115 /// ensures that all edges to that dest go to one block instead of each going
116 /// to a different block, but isn't the standard definition of a "critical
117 /// edge".
118 ///
119 /// It is invalid to call this function on a critical edge that starts at an
120 /// IndirectBrInst. Splitting these edges will almost always create an invalid
121 /// program because the address of the new block won't be the one that is jumped
122 /// to.
123 BasicBlock *SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
124  const CriticalEdgeSplittingOptions &Options =
126 
127 inline BasicBlock *
129  const CriticalEdgeSplittingOptions &Options =
132  Options);
133 }
134 
135 /// If the edge from *PI to BB is not critical, return false. Otherwise, split
136 /// all edges between the two blocks and return true. This updates all of the
137 /// same analyses as the other SplitCriticalEdge function. If P is specified, it
138 /// updates the analyses described above.
140  const CriticalEdgeSplittingOptions &Options =
142  bool MadeChange = false;
143  TerminatorInst *TI = (*PI)->getTerminator();
144  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
145  if (TI->getSuccessor(i) == Succ)
146  MadeChange |= !!SplitCriticalEdge(TI, i, Options);
147  return MadeChange;
148 }
149 
150 /// If an edge from Src to Dst is critical, split the edge and return true,
151 /// otherwise return false. This method requires that there be an edge between
152 /// the two blocks. It updates the analyses passed in the options struct
153 inline BasicBlock *
155  const CriticalEdgeSplittingOptions &Options =
157  TerminatorInst *TI = Src->getTerminator();
158  unsigned i = 0;
159  while (true) {
160  assert(i != TI->getNumSuccessors() && "Edge doesn't exist!");
161  if (TI->getSuccessor(i) == Dst)
162  return SplitCriticalEdge(TI, i, Options);
163  ++i;
164  }
165 }
166 
167 /// Loop over all of the edges in the CFG, breaking critical edges as they are
168 /// found. Returns the number of broken edges.
170  const CriticalEdgeSplittingOptions &Options =
172 
173 /// Split the edge connecting specified block.
175  DominatorTree *DT = nullptr, LoopInfo *LI = nullptr);
176 
177 /// Split the specified block at the specified instruction - everything before
178 /// SplitPt stays in Old and everything starting with SplitPt moves to a new
179 /// block. The two blocks are joined by an unconditional branch and the loop
180 /// info is updated.
182  DominatorTree *DT = nullptr, LoopInfo *LI = nullptr);
183 
184 /// This method introduces at least one new basic block into the function and
185 /// moves some of the predecessors of BB to be predecessors of the new block.
186 /// The new predecessors are indicated by the Preds array. The new block is
187 /// given a suffix of 'Suffix'. Returns new basic block to which predecessors
188 /// from Preds are now pointing.
189 ///
190 /// If BB is a landingpad block then additional basicblock might be introduced.
191 /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more
192 /// details on this case.
193 ///
194 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but
195 /// no other analyses. In particular, it does not preserve LoopSimplify
196 /// (because it's complicated to handle the case where one of the edges being
197 /// split is an exit of a loop with other exits).
199  const char *Suffix,
200  DominatorTree *DT = nullptr,
201  LoopInfo *LI = nullptr,
202  bool PreserveLCSSA = false);
203 
204 /// This method transforms the landing pad, OrigBB, by introducing two new basic
205 /// blocks into the function. One of those new basic blocks gets the
206 /// predecessors listed in Preds. The other basic block gets the remaining
207 /// predecessors of OrigBB. The landingpad instruction OrigBB is clone into both
208 /// of the new basic blocks. The new blocks are given the suffixes 'Suffix1' and
209 /// 'Suffix2', and are returned in the NewBBs vector.
210 ///
211 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but
212 /// no other analyses. In particular, it does not preserve LoopSimplify
213 /// (because it's complicated to handle the case where one of the edges being
214 /// split is an exit of a loop with other exits).
217  const char *Suffix, const char *Suffix2,
219  DominatorTree *DT = nullptr,
220  LoopInfo *LI = nullptr,
221  bool PreserveLCSSA = false);
222 
223 /// This method duplicates the specified return instruction into a predecessor
224 /// which ends in an unconditional branch. If the return instruction returns a
225 /// value defined by a PHI, propagate the right value into the return. It
226 /// returns the new return instruction in the predecessor.
228  BasicBlock *Pred);
229 
230 /// Split the containing block at the specified instruction - everything before
231 /// SplitBefore stays in the old basic block, and the rest of the instructions
232 /// in the BB are moved to a new block. The two blocks are connected by a
233 /// conditional branch (with value of Cmp being the condition).
234 /// Before:
235 /// Head
236 /// SplitBefore
237 /// Tail
238 /// After:
239 /// Head
240 /// if (Cond)
241 /// ThenBlock
242 /// SplitBefore
243 /// Tail
244 ///
245 /// If Unreachable is true, then ThenBlock ends with
246 /// UnreachableInst, otherwise it branches to Tail.
247 /// Returns the NewBasicBlock's terminator.
248 ///
249 /// Updates DT and LI if given.
251  bool Unreachable,
252  MDNode *BranchWeights = nullptr,
253  DominatorTree *DT = nullptr,
254  LoopInfo *LI = nullptr);
255 
256 /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen,
257 /// but also creates the ElseBlock.
258 /// Before:
259 /// Head
260 /// SplitBefore
261 /// Tail
262 /// After:
263 /// Head
264 /// if (Cond)
265 /// ThenBlock
266 /// else
267 /// ElseBlock
268 /// SplitBefore
269 /// Tail
270 void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore,
271  TerminatorInst **ThenTerm,
272  TerminatorInst **ElseTerm,
273  MDNode *BranchWeights = nullptr);
274 
275 /// Check whether BB is the merge point of a if-region.
276 /// If so, return the boolean condition that determines which entry into
277 /// BB will be taken. Also, return by references the block that will be
278 /// entered from if the condition is true, and the block that will be
279 /// entered if the condition is false.
280 ///
281 /// This does no checking to see if the true/false blocks have large or unsavory
282 /// instructions in them.
284  BasicBlock *&IfFalse);
285 
286 } // end namespace llvm
287 
288 #endif // LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H
Return a value (possibly void), from a function.
void ReplaceInstWithInst(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Instruction *I)
Replace the instruction specified by BI with the instruction specified by I.
unsigned getSuccessorIndex() const
This is used to interface between code that wants to operate on terminator instructions directly...
Definition: InstrTypes.h:161
void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, TerminatorInst **ThenTerm, TerminatorInst **ElseTerm, MDNode *BranchWeights=nullptr)
SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, but also creates the ElseBlock...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
Various leaf nodes.
Definition: ISDOpcodes.h:60
BasicBlock * getSuccessor(unsigned idx) const
Return the specified successor.
void DeleteDeadBlock(BasicBlock *BB)
Delete the specified block, which must have no predecessors.
Metadata node.
Definition: Metadata.h:862
F(f)
unsigned SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
Loop over all of the edges in the CFG, breaking critical edges as they are found. ...
Option class for critical edge splitting.
bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)
Examine each PHI in the given block and delete it if it is dead.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
void SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef< BasicBlock *> Preds, const char *Suffix, const char *Suffix2, SmallVectorImpl< BasicBlock *> &NewBBs, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, bool PreserveLCSSA=false)
This method transforms the landing pad, OrigBB, by introducing two new basic blocks into the function...
void ReplaceInstWithValue(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Value *V)
Replace all uses of an instruction (specified by BI) with a value, then remove and delete the origina...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
BasicBlock * SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
If this edge is a critical edge, insert a new node to split the critical edge.
CriticalEdgeSplittingOptions & setMergeIdenticalEdges()
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:54
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
SymbolTableList< Instruction > InstListType
Definition: BasicBlock.h:62
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock *> Preds, const char *Suffix, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
Value * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
TerminatorInst * SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
CriticalEdgeSplittingOptions & setPreserveLCSSA()
CriticalEdgeSplittingOptions(DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:91
void FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemoryDependenceResults *MemDep=nullptr)
Attempts to merge a block into its predecessor, if possible.
#define I(x, y, z)
Definition: MD5.cpp:58
ReturnInst * FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, BasicBlock *Pred)
This method duplicates the specified return instruction into a predecessor which ends in an unconditi...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getNumSuccessors() const
Return the number of successors that this terminator has.
CriticalEdgeSplittingOptions & setDontDeleteUselessPHIs()
LLVM Value Representation.
Definition: Value.h:73
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
Split the edge connecting specified block.
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:120