LLVM  10.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  const Twine &BBName = "");
227 
228 /// This method introduces at least one new basic block into the function and
229 /// moves some of the predecessors of BB to be predecessors of the new block.
230 /// The new predecessors are indicated by the Preds array. The new block is
231 /// given a suffix of 'Suffix'. Returns new basic block to which predecessors
232 /// from Preds are now pointing.
233 ///
234 /// If BB is a landingpad block then additional basicblock might be introduced.
235 /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more
236 /// details on this case.
237 ///
238 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but
239 /// no other analyses. In particular, it does not preserve LoopSimplify
240 /// (because it's complicated to handle the case where one of the edges being
241 /// split is an exit of a loop with other exits).
243  const char *Suffix,
244  DominatorTree *DT = nullptr,
245  LoopInfo *LI = nullptr,
246  MemorySSAUpdater *MSSAU = nullptr,
247  bool PreserveLCSSA = false);
248 
249 /// This method transforms the landing pad, OrigBB, by introducing two new basic
250 /// blocks into the function. One of those new basic blocks gets the
251 /// predecessors listed in Preds. The other basic block gets the remaining
252 /// predecessors of OrigBB. The landingpad instruction OrigBB is clone into both
253 /// of the new basic blocks. The new blocks are given the suffixes 'Suffix1' and
254 /// 'Suffix2', and are returned in the NewBBs vector.
255 ///
256 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but
257 /// no other analyses. In particular, it does not preserve LoopSimplify
258 /// (because it's complicated to handle the case where one of the edges being
259 /// split is an exit of a loop with other exits).
261  BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix,
262  const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs,
263  DominatorTree *DT = nullptr, LoopInfo *LI = nullptr,
264  MemorySSAUpdater *MSSAU = nullptr, bool PreserveLCSSA = false);
265 
266 /// This method duplicates the specified return instruction into a predecessor
267 /// which ends in an unconditional branch. If the return instruction returns a
268 /// value defined by a PHI, propagate the right value into the return. It
269 /// returns the new return instruction in the predecessor.
271  BasicBlock *Pred,
272  DomTreeUpdater *DTU = nullptr);
273 
274 /// Split the containing block at the specified instruction - everything before
275 /// SplitBefore stays in the old basic block, and the rest of the instructions
276 /// in the BB are moved to a new block. The two blocks are connected by a
277 /// conditional branch (with value of Cmp being the condition).
278 /// Before:
279 /// Head
280 /// SplitBefore
281 /// Tail
282 /// After:
283 /// Head
284 /// if (Cond)
285 /// ThenBlock
286 /// SplitBefore
287 /// Tail
288 ///
289 /// If \p ThenBlock is not specified, a new block will be created for it.
290 /// If \p Unreachable is true, the newly created block will end with
291 /// UnreachableInst, otherwise it branches to Tail.
292 /// Returns the NewBasicBlock's terminator.
293 ///
294 /// Updates DT and LI if given.
296  bool Unreachable,
297  MDNode *BranchWeights = nullptr,
298  DominatorTree *DT = nullptr,
299  LoopInfo *LI = nullptr,
300  BasicBlock *ThenBlock = nullptr);
301 
302 /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen,
303 /// but also creates the ElseBlock.
304 /// Before:
305 /// Head
306 /// SplitBefore
307 /// Tail
308 /// After:
309 /// Head
310 /// if (Cond)
311 /// ThenBlock
312 /// else
313 /// ElseBlock
314 /// SplitBefore
315 /// Tail
316 void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore,
317  Instruction **ThenTerm,
318  Instruction **ElseTerm,
319  MDNode *BranchWeights = nullptr);
320 
321 /// Check whether BB is the merge point of a if-region.
322 /// If so, return the boolean condition that determines which entry into
323 /// BB will be taken. Also, return by references the block that will be
324 /// entered from if the condition is true, and the block that will be
325 /// entered if the condition is false.
326 ///
327 /// This does no checking to see if the true/false blocks have large or unsavory
328 /// instructions in them.
330  BasicBlock *&IfFalse);
331 
332 // Split critical edges where the source of the edge is an indirectbr
333 // instruction. This isn't always possible, but we can handle some easy cases.
334 // This is useful because MI is unable to split such critical edges,
335 // which means it will not be able to sink instructions along those edges.
336 // This is especially painful for indirect branches with many successors, where
337 // we end up having to prepare all outgoing values in the origin block.
338 //
339 // Our normal algorithm for splitting critical edges requires us to update
340 // the outgoing edges of the edge origin block, but for an indirectbr this
341 // is hard, since it would require finding and updating the block addresses
342 // the indirect branch uses. But if a block only has a single indirectbr
343 // predecessor, with the others being regular branches, we can do it in a
344 // different way.
345 // Say we have A -> D, B -> D, I -> D where only I -> D is an indirectbr.
346 // We can split D into D0 and D1, where D0 contains only the PHIs from D,
347 // and D1 is the D block body. We can then duplicate D0 as D0A and D0B, and
348 // create the following structure:
349 // A -> D0A, B -> D0A, I -> D0B, D0A -> D1, D0B -> D1
350 // If BPI and BFI aren't non-null, BPI/BFI will be updated accordingly.
352  BranchProbabilityInfo *BPI = nullptr,
353  BlockFrequencyInfo *BFI = nullptr);
354 
355 } // end namespace llvm
356 
357 #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:144
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
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.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
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
constexpr double e
Definition: MathExtras.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:74
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 ...