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 /// By default do not merge blocks if BB's predecessor has multiple successors.
87 /// If PredecessorWithTwoSuccessors = true, the blocks can only be merged
88 /// if BB's Pred has a branch to BB and to AnotherBB, and BB has a single
89 /// successor Sing. In this case the branch will be updated with Sing instead of
90 /// BB, and BB will still be merged into its predecessor and removed.
91 bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU = nullptr,
92  LoopInfo *LI = nullptr,
93  MemorySSAUpdater *MSSAU = nullptr,
94  MemoryDependenceResults *MemDep = nullptr,
95  bool PredecessorWithTwoSuccessors = false);
96 
97 /// Replace all uses of an instruction (specified by BI) with a value, then
98 /// remove and delete the original instruction.
100  BasicBlock::iterator &BI, Value *V);
101 
102 /// Replace the instruction specified by BI with the instruction specified by I.
103 /// Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. The
104 /// original instruction is deleted and BI is updated to point to the new
105 /// instruction.
107  BasicBlock::iterator &BI, Instruction *I);
108 
109 /// Replace the instruction specified by From with the instruction specified by
110 /// To. Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc.
111 void ReplaceInstWithInst(Instruction *From, Instruction *To);
112 
113 /// Option class for critical edge splitting.
114 ///
115 /// This provides a builder interface for overriding the default options used
116 /// during critical edge splitting.
122  bool MergeIdenticalEdges = false;
123  bool KeepOneInputPHIs = false;
124  bool PreserveLCSSA = false;
126 
128  LoopInfo *LI = nullptr,
129  MemorySSAUpdater *MSSAU = nullptr,
130  PostDominatorTree *PDT = nullptr)
131  : DT(DT), PDT(PDT), LI(LI), MSSAU(MSSAU) {}
132 
134  MergeIdenticalEdges = true;
135  return *this;
136  }
137 
139  KeepOneInputPHIs = true;
140  return *this;
141  }
142 
144  PreserveLCSSA = true;
145  return *this;
146  }
147 
149  IgnoreUnreachableDests = true;
150  return *this;
151  }
152 };
153 
154 /// If this edge is a critical edge, insert a new node to split the critical
155 /// edge. This will update the analyses passed in through the option struct.
156 /// This returns the new block if the edge was split, null otherwise.
157 ///
158 /// If MergeIdenticalEdges in the options struct is true (not the default),
159 /// *all* edges from TI to the specified successor will be merged into the same
160 /// critical edge block. This is most commonly interesting with switch
161 /// instructions, which may have many edges to any one destination. This
162 /// ensures that all edges to that dest go to one block instead of each going
163 /// to a different block, but isn't the standard definition of a "critical
164 /// edge".
165 ///
166 /// It is invalid to call this function on a critical edge that starts at an
167 /// IndirectBrInst. Splitting these edges will almost always create an invalid
168 /// program because the address of the new block won't be the one that is jumped
169 /// to.
170 BasicBlock *SplitCriticalEdge(Instruction *TI, unsigned SuccNum,
171  const CriticalEdgeSplittingOptions &Options =
173 
174 inline BasicBlock *
176  const CriticalEdgeSplittingOptions &Options =
179  Options);
180 }
181 
182 /// If the edge from *PI to BB is not critical, return false. Otherwise, split
183 /// all edges between the two blocks and return true. This updates all of the
184 /// same analyses as the other SplitCriticalEdge function. If P is specified, it
185 /// updates the analyses described above.
187  const CriticalEdgeSplittingOptions &Options =
189  bool MadeChange = false;
190  Instruction *TI = (*PI)->getTerminator();
191  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
192  if (TI->getSuccessor(i) == Succ)
193  MadeChange |= !!SplitCriticalEdge(TI, i, Options);
194  return MadeChange;
195 }
196 
197 /// If an edge from Src to Dst is critical, split the edge and return true,
198 /// otherwise return false. This method requires that there be an edge between
199 /// the two blocks. It updates the analyses passed in the options struct
200 inline BasicBlock *
202  const CriticalEdgeSplittingOptions &Options =
204  Instruction *TI = Src->getTerminator();
205  unsigned i = 0;
206  while (true) {
207  assert(i != TI->getNumSuccessors() && "Edge doesn't exist!");
208  if (TI->getSuccessor(i) == Dst)
209  return SplitCriticalEdge(TI, i, Options);
210  ++i;
211  }
212 }
213 
214 /// Loop over all of the edges in the CFG, breaking critical edges as they are
215 /// found. Returns the number of broken edges.
217  const CriticalEdgeSplittingOptions &Options =
219 
220 /// Split the edge connecting specified block.
222  DominatorTree *DT = nullptr, LoopInfo *LI = nullptr,
223  MemorySSAUpdater *MSSAU = nullptr);
224 
225 /// Split the specified block at the specified instruction - everything before
226 /// SplitPt stays in Old and everything starting with SplitPt moves to a new
227 /// block. The two blocks are joined by an unconditional branch and the loop
228 /// info is updated.
230  DominatorTree *DT = nullptr, LoopInfo *LI = nullptr,
231  MemorySSAUpdater *MSSAU = nullptr,
232  const Twine &BBName = "");
233 
234 /// This method introduces at least one new basic block into the function and
235 /// moves some of the predecessors of BB to be predecessors of the new block.
236 /// The new predecessors are indicated by the Preds array. The new block is
237 /// given a suffix of 'Suffix'. Returns new basic block to which predecessors
238 /// from Preds are now pointing.
239 ///
240 /// If BB is a landingpad block then additional basicblock might be introduced.
241 /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more
242 /// details on this case.
243 ///
244 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but
245 /// no other analyses. In particular, it does not preserve LoopSimplify
246 /// (because it's complicated to handle the case where one of the edges being
247 /// split is an exit of a loop with other exits).
249  const char *Suffix,
250  DominatorTree *DT = nullptr,
251  LoopInfo *LI = nullptr,
252  MemorySSAUpdater *MSSAU = nullptr,
253  bool PreserveLCSSA = false);
254 
255 /// This method transforms the landing pad, OrigBB, by introducing two new basic
256 /// blocks into the function. One of those new basic blocks gets the
257 /// predecessors listed in Preds. The other basic block gets the remaining
258 /// predecessors of OrigBB. The landingpad instruction OrigBB is clone into both
259 /// of the new basic blocks. The new blocks are given the suffixes 'Suffix1' and
260 /// 'Suffix2', and are returned in the NewBBs vector.
261 ///
262 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but
263 /// no other analyses. In particular, it does not preserve LoopSimplify
264 /// (because it's complicated to handle the case where one of the edges being
265 /// split is an exit of a loop with other exits).
267  BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix,
268  const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs,
269  DominatorTree *DT = nullptr, LoopInfo *LI = nullptr,
270  MemorySSAUpdater *MSSAU = nullptr, bool PreserveLCSSA = false);
271 
272 /// This method duplicates the specified return instruction into a predecessor
273 /// which ends in an unconditional branch. If the return instruction returns a
274 /// value defined by a PHI, propagate the right value into the return. It
275 /// returns the new return instruction in the predecessor.
277  BasicBlock *Pred,
278  DomTreeUpdater *DTU = nullptr);
279 
280 /// Split the containing block at the specified instruction - everything before
281 /// SplitBefore stays in the old basic block, and the rest of the instructions
282 /// in the BB are moved to a new block. The two blocks are connected by a
283 /// conditional branch (with value of Cmp being the condition).
284 /// Before:
285 /// Head
286 /// SplitBefore
287 /// Tail
288 /// After:
289 /// Head
290 /// if (Cond)
291 /// ThenBlock
292 /// SplitBefore
293 /// Tail
294 ///
295 /// If \p ThenBlock is not specified, a new block will be created for it.
296 /// If \p Unreachable is true, the newly created block will end with
297 /// UnreachableInst, otherwise it branches to Tail.
298 /// Returns the NewBasicBlock's terminator.
299 ///
300 /// Updates DT and LI if given.
302  bool Unreachable,
303  MDNode *BranchWeights = nullptr,
304  DominatorTree *DT = nullptr,
305  LoopInfo *LI = nullptr,
306  BasicBlock *ThenBlock = nullptr);
307 
308 /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen,
309 /// but also creates the ElseBlock.
310 /// Before:
311 /// Head
312 /// SplitBefore
313 /// Tail
314 /// After:
315 /// Head
316 /// if (Cond)
317 /// ThenBlock
318 /// else
319 /// ElseBlock
320 /// SplitBefore
321 /// Tail
322 void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore,
323  Instruction **ThenTerm,
324  Instruction **ElseTerm,
325  MDNode *BranchWeights = nullptr);
326 
327 /// Check whether BB is the merge point of a if-region.
328 /// If so, return the boolean condition that determines which entry into
329 /// BB will be taken. Also, return by references the block that will be
330 /// entered from if the condition is true, and the block that will be
331 /// entered if the condition is false.
332 ///
333 /// This does no checking to see if the true/false blocks have large or unsavory
334 /// instructions in them.
336  BasicBlock *&IfFalse);
337 
338 // Split critical edges where the source of the edge is an indirectbr
339 // instruction. This isn't always possible, but we can handle some easy cases.
340 // This is useful because MI is unable to split such critical edges,
341 // which means it will not be able to sink instructions along those edges.
342 // This is especially painful for indirect branches with many successors, where
343 // we end up having to prepare all outgoing values in the origin block.
344 //
345 // Our normal algorithm for splitting critical edges requires us to update
346 // the outgoing edges of the edge origin block, but for an indirectbr this
347 // is hard, since it would require finding and updating the block addresses
348 // the indirect branch uses. But if a block only has a single indirectbr
349 // predecessor, with the others being regular branches, we can do it in a
350 // different way.
351 // Say we have A -> D, B -> D, I -> D where only I -> D is an indirectbr.
352 // We can split D into D0 and D1, where D0 contains only the PHIs from D,
353 // and D1 is the D block body. We can then duplicate D0 as D0A and D0B, and
354 // create the following structure:
355 // A -> D0A, B -> D0A, I -> D0B, D0A -> D1, D0B -> D1
356 // If BPI and BFI aren't non-null, BPI/BFI will be updated accordingly.
358  BranchProbabilityInfo *BPI = nullptr,
359  BlockFrequencyInfo *BFI = nullptr);
360 
361 } // end namespace llvm
362 
363 #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
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...
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false)
Attempts to merge a block into its predecessor, if possible.
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 ...