LLVM  9.0.0svn
BasicBlockUtils.h
Go to the documentation of this file.
1 //===- Transform/Utils/BasicBlockUtils.h - BasicBlock Utils -----*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This family of functions perform manipulations on basic blocks, and
10 // instructions contained within basic blocks.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H
15 #define LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H
16 
17 // FIXME: Move to this file: BasicBlock::removePredecessor, BB::splitBasicBlock
18 
19 #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 DominatorTree;
31 class DomTreeUpdater;
32 class Function;
33 class Instruction;
34 class LoopInfo;
35 class MDNode;
36 class MemoryDependenceResults;
37 class MemorySSAUpdater;
38 class PostDominatorTree;
39 class ReturnInst;
40 class TargetLibraryInfo;
41 class Value;
42 
43 /// Replace contents of every block in \p BBs with single unreachable
44 /// instruction. If \p Updates is specified, collect all necessary DT updates
45 /// into this vector. If \p KeepOneInputPHIs is true, one-input Phis in
46 /// successors of blocks being deleted will be preserved.
47 void DetatchDeadBlocks(ArrayRef <BasicBlock *> BBs,
48  SmallVectorImpl<DominatorTree::UpdateType> *Updates,
49  bool KeepOneInputPHIs = false);
50 
51 /// Delete the specified block, which must have no predecessors.
52 void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU = nullptr,
53  bool KeepOneInputPHIs = false);
54 
55 /// Delete the specified blocks from \p BB. The set of deleted blocks must have
56 /// no predecessors that are not being deleted themselves. \p BBs must have no
57 /// duplicating blocks. If there are loops among this set of blocks, all
58 /// relevant loop info updates should be done before this function is called.
59 /// If \p KeepOneInputPHIs is true, one-input Phis in successors of blocks
60 /// being deleted will be preserved.
61 void DeleteDeadBlocks(ArrayRef <BasicBlock *> BBs,
62  DomTreeUpdater *DTU = nullptr,
63  bool KeepOneInputPHIs = false);
64 
65 /// Delete all basic blocks from \p F that are not reachable from its entry
66 /// node. If \p KeepOneInputPHIs is true, one-input Phis in successors of
67 /// blocks being deleted will be preserved.
68 bool EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU = nullptr,
69  bool KeepOneInputPHIs = false);
70 
71 /// We know that BB has one predecessor. If there are any single-entry PHI nodes
72 /// in it, fold them away. This handles the case when all entries to the PHI
73 /// nodes in a block are guaranteed equal, such as when the block has exactly
74 /// one predecessor.
76  MemoryDependenceResults *MemDep = nullptr);
77 
78 /// Examine each PHI in the given block and delete it if it is dead. Also
79 /// recursively delete any operands that become dead as a result. This includes
80 /// tracing the def-use list from the PHI to see if it is ultimately unused or
81 /// if it reaches an unused cycle. Return true if any PHIs were deleted.
82 bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr);
83 
84 /// Attempts to merge a block into its predecessor, if possible. The return
85 /// value indicates success or failure.
86 bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU = nullptr,
87  LoopInfo *LI = nullptr,
88  MemorySSAUpdater *MSSAU = nullptr,
89  MemoryDependenceResults *MemDep = nullptr);
90 
91 /// Replace all uses of an instruction (specified by BI) with a value, then
92 /// remove and delete the original instruction.
94  BasicBlock::iterator &BI, Value *V);
95 
96 /// Replace the instruction specified by BI with the instruction specified by I.
97 /// Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. The
98 /// original instruction is deleted and BI is updated to point to the new
99 /// instruction.
101  BasicBlock::iterator &BI, Instruction *I);
102 
103 /// Replace the instruction specified by From with the instruction specified by
104 /// To. Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc.
105 void ReplaceInstWithInst(Instruction *From, Instruction *To);
106 
107 /// Option class for critical edge splitting.
108 ///
109 /// This provides a builder interface for overriding the default options used
110 /// during critical edge splitting.
116  bool MergeIdenticalEdges = false;
117  bool KeepOneInputPHIs = false;
118  bool PreserveLCSSA = false;
120 
122  LoopInfo *LI = nullptr,
123  MemorySSAUpdater *MSSAU = nullptr,
124  PostDominatorTree *PDT = nullptr)
125  : DT(DT), PDT(PDT), LI(LI), MSSAU(MSSAU) {}
126 
128  MergeIdenticalEdges = true;
129  return *this;
130  }
131 
133  KeepOneInputPHIs = true;
134  return *this;
135  }
136 
138  PreserveLCSSA = true;
139  return *this;
140  }
141 
143  IgnoreUnreachableDests = true;
144  return *this;
145  }
146 };
147 
148 /// If this edge is a critical edge, insert a new node to split the critical
149 /// edge. This will update the analyses passed in through the option struct.
150 /// This returns the new block if the edge was split, null otherwise.
151 ///
152 /// If MergeIdenticalEdges in the options struct is true (not the default),
153 /// *all* edges from TI to the specified successor will be merged into the same
154 /// critical edge block. This is most commonly interesting with switch
155 /// instructions, which may have many edges to any one destination. This
156 /// ensures that all edges to that dest go to one block instead of each going
157 /// to a different block, but isn't the standard definition of a "critical
158 /// edge".
159 ///
160 /// It is invalid to call this function on a critical edge that starts at an
161 /// IndirectBrInst. Splitting these edges will almost always create an invalid
162 /// program because the address of the new block won't be the one that is jumped
163 /// to.
164 BasicBlock *SplitCriticalEdge(Instruction *TI, unsigned SuccNum,
165  const CriticalEdgeSplittingOptions &Options =
167 
168 inline BasicBlock *
170  const CriticalEdgeSplittingOptions &Options =
173  Options);
174 }
175 
176 /// If the edge from *PI to BB is not critical, return false. Otherwise, split
177 /// all edges between the two blocks and return true. This updates all of the
178 /// same analyses as the other SplitCriticalEdge function. If P is specified, it
179 /// updates the analyses described above.
181  const CriticalEdgeSplittingOptions &Options =
183  bool MadeChange = false;
184  Instruction *TI = (*PI)->getTerminator();
185  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
186  if (TI->getSuccessor(i) == Succ)
187  MadeChange |= !!SplitCriticalEdge(TI, i, Options);
188  return MadeChange;
189 }
190 
191 /// If an edge from Src to Dst is critical, split the edge and return true,
192 /// otherwise return false. This method requires that there be an edge between
193 /// the two blocks. It updates the analyses passed in the options struct
194 inline BasicBlock *
196  const CriticalEdgeSplittingOptions &Options =
198  Instruction *TI = Src->getTerminator();
199  unsigned i = 0;
200  while (true) {
201  assert(i != TI->getNumSuccessors() && "Edge doesn't exist!");
202  if (TI->getSuccessor(i) == Dst)
203  return SplitCriticalEdge(TI, i, Options);
204  ++i;
205  }
206 }
207 
208 /// Loop over all of the edges in the CFG, breaking critical edges as they are
209 /// found. Returns the number of broken edges.
211  const CriticalEdgeSplittingOptions &Options =
213 
214 /// Split the edge connecting specified block.
216  DominatorTree *DT = nullptr, LoopInfo *LI = nullptr,
217  MemorySSAUpdater *MSSAU = nullptr);
218 
219 /// Split the specified block at the specified instruction - everything before
220 /// SplitPt stays in Old and everything starting with SplitPt moves to a new
221 /// block. The two blocks are joined by an unconditional branch and the loop
222 /// info is updated.
224  DominatorTree *DT = nullptr, LoopInfo *LI = nullptr,
225  MemorySSAUpdater *MSSAU = nullptr);
226 
227 /// This method introduces at least one new basic block into the function and
228 /// moves some of the predecessors of BB to be predecessors of the new block.
229 /// The new predecessors are indicated by the Preds array. The new block is
230 /// given a suffix of 'Suffix'. Returns new basic block to which predecessors
231 /// from Preds are now pointing.
232 ///
233 /// If BB is a landingpad block then additional basicblock might be introduced.
234 /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more
235 /// details on this case.
236 ///
237 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but
238 /// no other analyses. In particular, it does not preserve LoopSimplify
239 /// (because it's complicated to handle the case where one of the edges being
240 /// split is an exit of a loop with other exits).
242  const char *Suffix,
243  DominatorTree *DT = nullptr,
244  LoopInfo *LI = nullptr,
245  MemorySSAUpdater *MSSAU = nullptr,
246  bool PreserveLCSSA = false);
247 
248 /// This method transforms the landing pad, OrigBB, by introducing two new basic
249 /// blocks into the function. One of those new basic blocks gets the
250 /// predecessors listed in Preds. The other basic block gets the remaining
251 /// predecessors of OrigBB. The landingpad instruction OrigBB is clone into both
252 /// of the new basic blocks. The new blocks are given the suffixes 'Suffix1' and
253 /// 'Suffix2', and are returned in the NewBBs vector.
254 ///
255 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but
256 /// no other analyses. In particular, it does not preserve LoopSimplify
257 /// (because it's complicated to handle the case where one of the edges being
258 /// split is an exit of a loop with other exits).
260  BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix,
261  const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs,
262  DominatorTree *DT = nullptr, LoopInfo *LI = nullptr,
263  MemorySSAUpdater *MSSAU = nullptr, bool PreserveLCSSA = false);
264 
265 /// This method duplicates the specified return instruction into a predecessor
266 /// which ends in an unconditional branch. If the return instruction returns a
267 /// value defined by a PHI, propagate the right value into the return. It
268 /// returns the new return instruction in the predecessor.
270  BasicBlock *Pred,
271  DomTreeUpdater *DTU = nullptr);
272 
273 /// Split the containing block at the specified instruction - everything before
274 /// SplitBefore stays in the old basic block, and the rest of the instructions
275 /// in the BB are moved to a new block. The two blocks are connected by a
276 /// conditional branch (with value of Cmp being the condition).
277 /// Before:
278 /// Head
279 /// SplitBefore
280 /// Tail
281 /// After:
282 /// Head
283 /// if (Cond)
284 /// ThenBlock
285 /// SplitBefore
286 /// Tail
287 ///
288 /// If \p ThenBlock is not specified, a new block will be created for it.
289 /// If \p Unreachable is true, the newly created block will end with
290 /// UnreachableInst, otherwise it branches to Tail.
291 /// Returns the NewBasicBlock's terminator.
292 ///
293 /// Updates DT and LI if given.
295  bool Unreachable,
296  MDNode *BranchWeights = nullptr,
297  DominatorTree *DT = nullptr,
298  LoopInfo *LI = nullptr,
299  BasicBlock *ThenBlock = nullptr);
300 
301 /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen,
302 /// but also creates the ElseBlock.
303 /// Before:
304 /// Head
305 /// SplitBefore
306 /// Tail
307 /// After:
308 /// Head
309 /// if (Cond)
310 /// ThenBlock
311 /// else
312 /// ElseBlock
313 /// SplitBefore
314 /// Tail
315 void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore,
316  Instruction **ThenTerm,
317  Instruction **ElseTerm,
318  MDNode *BranchWeights = nullptr);
319 
320 /// Check whether BB is the merge point of a if-region.
321 /// If so, return the boolean condition that determines which entry into
322 /// BB will be taken. Also, return by references the block that will be
323 /// entered from if the condition is true, and the block that will be
324 /// entered if the condition is false.
325 ///
326 /// This does no checking to see if the true/false blocks have large or unsavory
327 /// instructions in them.
329  BasicBlock *&IfFalse);
330 
331 // Split critical edges where the source of the edge is an indirectbr
332 // instruction. This isn't always possible, but we can handle some easy cases.
333 // This is useful because MI is unable to split such critical edges,
334 // which means it will not be able to sink instructions along those edges.
335 // This is especially painful for indirect branches with many successors, where
336 // we end up having to prepare all outgoing values in the origin block.
337 //
338 // Our normal algorithm for splitting critical edges requires us to update
339 // the outgoing edges of the edge origin block, but for an indirectbr this
340 // is hard, since it would require finding and updating the block addresses
341 // the indirect branch uses. But if a block only has a single indirectbr
342 // predecessor, with the others being regular branches, we can do it in a
343 // different way.
344 // Say we have A -> D, B -> D, I -> D where only I -> D is an indirectbr.
345 // We can split D into D0 and D1, where D0 contains only the PHIs from D,
346 // and D1 is the D block body. We can then duplicate D0 as D0A and D0B, and
347 // create the following structure:
348 // A -> D0A, B -> D0A, I -> D0B, D0A -> D1, D0B -> D1
349 // If BPI and BFI aren't non-null, BPI/BFI will be updated accordingly.
351  BranchProbabilityInfo *BPI = nullptr,
352  BlockFrequencyInfo *BFI = nullptr);
353 
354 } // end namespace llvm
355 
356 #endif // LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H
void DeleteDeadBlocks(ArrayRef< BasicBlock *> BBs, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified blocks from BB.
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.
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Various leaf nodes.
Definition: ISDOpcodes.h:59
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:197
Metadata node.
Definition: Metadata.h:863
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:137
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Split the edge connecting specified block.
CriticalEdgeSplittingOptions(DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, PostDominatorTree *PDT=nullptr)
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:32
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:144
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:57
SymbolTableList< Instruction > InstListType
Definition: BasicBlock.h:60
CriticalEdgeSplittingOptions & setKeepOneInputPHIs()
CriticalEdgeSplittingOptions & setIgnoreUnreachableDests()
BlockVerifier::State From
Value * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
bool EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete all basic blocks from F that are not reachable from its entry node.
CriticalEdgeSplittingOptions & setPreserveLCSSA()
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:89
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
void FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
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
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:72
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...
void DetatchDeadBlocks(ArrayRef< BasicBlock *> BBs, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs=false)
Replace contents of every block in BBs with single unreachable instruction.
Instruction * SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...