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