LLVM  7.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 BlockFrequencyInfo;
29 class BranchProbabilityInfo;
30 class DeferredDominance;
31 class DominatorTree;
32 class Function;
33 class Instruction;
34 class LoopInfo;
35 class MDNode;
36 class MemoryDependenceResults;
37 class ReturnInst;
38 class TargetLibraryInfo;
39 class Value;
40 
41 /// Delete the specified block, which must have no predecessors.
42 void DeleteDeadBlock(BasicBlock *BB, DeferredDominance *DDT = nullptr);
43 
44 /// We know that BB has one predecessor. If there are any single-entry PHI nodes
45 /// in it, fold them away. This handles the case when all entries to the PHI
46 /// nodes in a block are guaranteed equal, such as when the block has exactly
47 /// one predecessor.
49  MemoryDependenceResults *MemDep = nullptr);
50 
51 /// Examine each PHI in the given block and delete it if it is dead. Also
52 /// recursively delete any operands that become dead as a result. This includes
53 /// tracing the def-use list from the PHI to see if it is ultimately unused or
54 /// if it reaches an unused cycle. Return true if any PHIs were deleted.
55 bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr);
56 
57 /// Attempts to merge a block into its predecessor, if possible. The return
58 /// value indicates success or failure.
59 bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT = nullptr,
60  LoopInfo *LI = nullptr,
61  MemoryDependenceResults *MemDep = nullptr);
62 
63 /// Replace all uses of an instruction (specified by BI) with a value, then
64 /// remove and delete the original instruction.
66  BasicBlock::iterator &BI, Value *V);
67 
68 /// Replace the instruction specified by BI with the instruction specified by I.
69 /// Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. The
70 /// original instruction is deleted and BI is updated to point to the new
71 /// instruction.
73  BasicBlock::iterator &BI, Instruction *I);
74 
75 /// Replace the instruction specified by From with the instruction specified by
76 /// To. Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc.
77 void ReplaceInstWithInst(Instruction *From, Instruction *To);
78 
79 /// Option class for critical edge splitting.
80 ///
81 /// This provides a builder interface for overriding the default options used
82 /// during critical edge splitting.
86  bool MergeIdenticalEdges = false;
87  bool DontDeleteUselessPHIs = false;
88  bool PreserveLCSSA = false;
89 
91  LoopInfo *LI = nullptr)
92  : DT(DT), LI(LI) {}
93 
95  MergeIdenticalEdges = true;
96  return *this;
97  }
98 
100  DontDeleteUselessPHIs = true;
101  return *this;
102  }
103 
105  PreserveLCSSA = true;
106  return *this;
107  }
108 };
109 
110 /// If this edge is a critical edge, insert a new node to split the critical
111 /// edge. This will update the analyses passed in through the option struct.
112 /// This returns the new block if the edge was split, null otherwise.
113 ///
114 /// If MergeIdenticalEdges in the options struct is true (not the default),
115 /// *all* edges from TI to the specified successor will be merged into the same
116 /// critical edge block. This is most commonly interesting with switch
117 /// instructions, which may have many edges to any one destination. This
118 /// ensures that all edges to that dest go to one block instead of each going
119 /// to a different block, but isn't the standard definition of a "critical
120 /// edge".
121 ///
122 /// It is invalid to call this function on a critical edge that starts at an
123 /// IndirectBrInst. Splitting these edges will almost always create an invalid
124 /// program because the address of the new block won't be the one that is jumped
125 /// to.
126 BasicBlock *SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
127  const CriticalEdgeSplittingOptions &Options =
129 
130 inline BasicBlock *
132  const CriticalEdgeSplittingOptions &Options =
135  Options);
136 }
137 
138 /// If the edge from *PI to BB is not critical, return false. Otherwise, split
139 /// all edges between the two blocks and return true. This updates all of the
140 /// same analyses as the other SplitCriticalEdge function. If P is specified, it
141 /// updates the analyses described above.
143  const CriticalEdgeSplittingOptions &Options =
145  bool MadeChange = false;
146  TerminatorInst *TI = (*PI)->getTerminator();
147  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
148  if (TI->getSuccessor(i) == Succ)
149  MadeChange |= !!SplitCriticalEdge(TI, i, Options);
150  return MadeChange;
151 }
152 
153 /// If an edge from Src to Dst is critical, split the edge and return true,
154 /// otherwise return false. This method requires that there be an edge between
155 /// the two blocks. It updates the analyses passed in the options struct
156 inline BasicBlock *
158  const CriticalEdgeSplittingOptions &Options =
160  TerminatorInst *TI = Src->getTerminator();
161  unsigned i = 0;
162  while (true) {
163  assert(i != TI->getNumSuccessors() && "Edge doesn't exist!");
164  if (TI->getSuccessor(i) == Dst)
165  return SplitCriticalEdge(TI, i, Options);
166  ++i;
167  }
168 }
169 
170 /// Loop over all of the edges in the CFG, breaking critical edges as they are
171 /// found. Returns the number of broken edges.
173  const CriticalEdgeSplittingOptions &Options =
175 
176 /// Split the edge connecting specified block.
178  DominatorTree *DT = nullptr, LoopInfo *LI = nullptr);
179 
180 /// Split the specified block at the specified instruction - everything before
181 /// SplitPt stays in Old and everything starting with SplitPt moves to a new
182 /// block. The two blocks are joined by an unconditional branch and the loop
183 /// info is updated.
185  DominatorTree *DT = nullptr, LoopInfo *LI = nullptr);
186 
187 /// This method introduces at least one new basic block into the function and
188 /// moves some of the predecessors of BB to be predecessors of the new block.
189 /// The new predecessors are indicated by the Preds array. The new block is
190 /// given a suffix of 'Suffix'. Returns new basic block to which predecessors
191 /// from Preds are now pointing.
192 ///
193 /// If BB is a landingpad block then additional basicblock might be introduced.
194 /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more
195 /// details on this case.
196 ///
197 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but
198 /// no other analyses. In particular, it does not preserve LoopSimplify
199 /// (because it's complicated to handle the case where one of the edges being
200 /// split is an exit of a loop with other exits).
202  const char *Suffix,
203  DominatorTree *DT = nullptr,
204  LoopInfo *LI = nullptr,
205  bool PreserveLCSSA = false);
206 
207 /// This method transforms the landing pad, OrigBB, by introducing two new basic
208 /// blocks into the function. One of those new basic blocks gets the
209 /// predecessors listed in Preds. The other basic block gets the remaining
210 /// predecessors of OrigBB. The landingpad instruction OrigBB is clone into both
211 /// of the new basic blocks. The new blocks are given the suffixes 'Suffix1' and
212 /// 'Suffix2', and are returned in the NewBBs vector.
213 ///
214 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but
215 /// no other analyses. In particular, it does not preserve LoopSimplify
216 /// (because it's complicated to handle the case where one of the edges being
217 /// split is an exit of a loop with other exits).
220  const char *Suffix, const char *Suffix2,
222  DominatorTree *DT = nullptr,
223  LoopInfo *LI = nullptr,
224  bool PreserveLCSSA = false);
225 
226 /// This method duplicates the specified return instruction into a predecessor
227 /// which ends in an unconditional branch. If the return instruction returns a
228 /// value defined by a PHI, propagate the right value into the return. It
229 /// returns the new return instruction in the predecessor.
231  BasicBlock *Pred);
232 
233 /// Split the containing block at the specified instruction - everything before
234 /// SplitBefore stays in the old basic block, and the rest of the instructions
235 /// in the BB are moved to a new block. The two blocks are connected by a
236 /// conditional branch (with value of Cmp being the condition).
237 /// Before:
238 /// Head
239 /// SplitBefore
240 /// Tail
241 /// After:
242 /// Head
243 /// if (Cond)
244 /// ThenBlock
245 /// SplitBefore
246 /// Tail
247 ///
248 /// If Unreachable is true, then ThenBlock ends with
249 /// UnreachableInst, otherwise it branches to Tail.
250 /// Returns the NewBasicBlock's terminator.
251 ///
252 /// Updates DT and LI if given.
254  bool Unreachable,
255  MDNode *BranchWeights = nullptr,
256  DominatorTree *DT = nullptr,
257  LoopInfo *LI = nullptr);
258 
259 /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen,
260 /// but also creates the ElseBlock.
261 /// Before:
262 /// Head
263 /// SplitBefore
264 /// Tail
265 /// After:
266 /// Head
267 /// if (Cond)
268 /// ThenBlock
269 /// else
270 /// ElseBlock
271 /// SplitBefore
272 /// Tail
273 void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore,
274  TerminatorInst **ThenTerm,
275  TerminatorInst **ElseTerm,
276  MDNode *BranchWeights = nullptr);
277 
278 /// Check whether BB is the merge point of a if-region.
279 /// If so, return the boolean condition that determines which entry into
280 /// BB will be taken. Also, return by references the block that will be
281 /// entered from if the condition is true, and the block that will be
282 /// entered if the condition is false.
283 ///
284 /// This does no checking to see if the true/false blocks have large or unsavory
285 /// instructions in them.
287  BasicBlock *&IfFalse);
288 
289 // Split critical edges where the source of the edge is an indirectbr
290 // instruction. This isn't always possible, but we can handle some easy cases.
291 // This is useful because MI is unable to split such critical edges,
292 // which means it will not be able to sink instructions along those edges.
293 // This is especially painful for indirect branches with many successors, where
294 // we end up having to prepare all outgoing values in the origin block.
295 //
296 // Our normal algorithm for splitting critical edges requires us to update
297 // the outgoing edges of the edge origin block, but for an indirectbr this
298 // is hard, since it would require finding and updating the block addresses
299 // the indirect branch uses. But if a block only has a single indirectbr
300 // predecessor, with the others being regular branches, we can do it in a
301 // different way.
302 // Say we have A -> D, B -> D, I -> D where only I -> D is an indirectbr.
303 // We can split D into D0 and D1, where D0 contains only the PHIs from D,
304 // and D1 is the D block body. We can then duplicate D0 as D0A and D0B, and
305 // create the following structure:
306 // A -> D0A, B -> D0A, I -> D0B, D0A -> D1, D0B -> D1
307 // If BPI and BFI aren't non-null, BPI/BFI will be updated accordingly.
309  BranchProbabilityInfo *BPI = nullptr,
310  BlockFrequencyInfo *BFI = nullptr);
311 
312 } // end namespace llvm
313 
314 #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:162
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.
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:142
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.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
CriticalEdgeSplittingOptions & setMergeIdenticalEdges()
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:55
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.
Analysis providing branch probability information.
bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemoryDependenceResults *MemDep=nullptr)
Attempts to merge a block into its predecessor, if possible.
bool SplitIndirectBrCriticalEdges(Function &F, BranchProbabilityInfo *BPI=nullptr, BlockFrequencyInfo *BFI=nullptr)
#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.
void DeleteDeadBlock(BasicBlock *BB, DeferredDominance *DDT=nullptr)
Delete the specified block, which must have no predecessors.
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:138