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