LLVM  6.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/InstrTypes.h"
24 #include <cassert>
25 
26 namespace llvm {
27 
28 class MemoryDependenceResults;
29 class DominatorTree;
30 class LoopInfo;
31 class Instruction;
32 class MDNode;
33 class ReturnInst;
34 class TargetLibraryInfo;
35 
36 /// Delete the specified block, which must have no predecessors.
37 void DeleteDeadBlock(BasicBlock *BB);
38 
39 /// We know that BB has one predecessor. If there are any single-entry PHI nodes
40 /// in it, fold them away. This handles the case when all entries to the PHI
41 /// nodes in a block are guaranteed equal, such as when the block has exactly
42 /// one predecessor.
44  MemoryDependenceResults *MemDep = nullptr);
45 
46 /// Examine each PHI in the given block and delete it if it is dead. Also
47 /// recursively delete any operands that become dead as a result. This includes
48 /// tracing the def-use list from the PHI to see if it is ultimately unused or
49 /// if it reaches an unused cycle. Return true if any PHIs were deleted.
50 bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr);
51 
52 /// Attempts to merge a block into its predecessor, if possible. The return
53 /// value indicates success or failure.
54 bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT = nullptr,
55  LoopInfo *LI = nullptr,
56  MemoryDependenceResults *MemDep = nullptr);
57 
58 /// Replace all uses of an instruction (specified by BI) with a value, then
59 /// remove and delete the original instruction.
61  BasicBlock::iterator &BI, Value *V);
62 
63 /// Replace the instruction specified by BI with the instruction specified by I.
64 /// Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. The
65 /// original instruction is deleted and BI is updated to point to the new
66 /// instruction.
68  BasicBlock::iterator &BI, Instruction *I);
69 
70 /// Replace the instruction specified by From with the instruction specified by
71 /// To. Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc.
72 void ReplaceInstWithInst(Instruction *From, Instruction *To);
73 
74 /// Option class for critical edge splitting.
75 ///
76 /// This provides a builder interface for overriding the default options used
77 /// during critical edge splitting.
81  bool MergeIdenticalEdges = false;
82  bool DontDeleteUselessPHIs = false;
83  bool PreserveLCSSA = false;
84 
86  LoopInfo *LI = nullptr)
87  : DT(DT), LI(LI) {}
88 
90  MergeIdenticalEdges = true;
91  return *this;
92  }
93 
95  DontDeleteUselessPHIs = true;
96  return *this;
97  }
98 
100  PreserveLCSSA = true;
101  return *this;
102  }
103 };
104 
105 /// If this edge is a critical edge, insert a new node to split the critical
106 /// edge. This will update the analyses passed in through the option struct.
107 /// This returns the new block if the edge was split, null otherwise.
108 ///
109 /// If MergeIdenticalEdges in the options struct is true (not the default),
110 /// *all* edges from TI to the specified successor will be merged into the same
111 /// critical edge block. This is most commonly interesting with switch
112 /// instructions, which may have many edges to any one destination. This
113 /// ensures that all edges to that dest go to one block instead of each going
114 /// to a different block, but isn't the standard definition of a "critical
115 /// edge".
116 ///
117 /// It is invalid to call this function on a critical edge that starts at an
118 /// IndirectBrInst. Splitting these edges will almost always create an invalid
119 /// program because the address of the new block won't be the one that is jumped
120 /// to.
121 ///
122 BasicBlock *SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
123  const CriticalEdgeSplittingOptions &Options =
125 
126 inline BasicBlock *
128  const CriticalEdgeSplittingOptions &Options =
131  Options);
132 }
133 
134 /// If the edge from *PI to BB is not critical, return false. Otherwise, split
135 /// all edges between the two blocks and return true. This updates all of the
136 /// same analyses as the other SplitCriticalEdge function. If P is specified, it
137 /// updates the analyses described above.
139  const CriticalEdgeSplittingOptions &Options =
141  bool MadeChange = false;
142  TerminatorInst *TI = (*PI)->getTerminator();
143  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
144  if (TI->getSuccessor(i) == Succ)
145  MadeChange |= !!SplitCriticalEdge(TI, i, Options);
146  return MadeChange;
147 }
148 
149 /// If an edge from Src to Dst is critical, split the edge and return true,
150 /// otherwise return false. This method requires that there be an edge between
151 /// the two blocks. It updates the analyses passed in the options struct
152 inline BasicBlock *
154  const CriticalEdgeSplittingOptions &Options =
156  TerminatorInst *TI = Src->getTerminator();
157  unsigned i = 0;
158  while (true) {
159  assert(i != TI->getNumSuccessors() && "Edge doesn't exist!");
160  if (TI->getSuccessor(i) == Dst)
161  return SplitCriticalEdge(TI, i, Options);
162  ++i;
163  }
164 }
165 
166 /// Loop over all of the edges in the CFG, breaking critical edges as they are
167 /// found. Returns the number of broken edges.
169  const CriticalEdgeSplittingOptions &Options =
171 
172 /// Split the edge connecting specified block.
174  DominatorTree *DT = nullptr, LoopInfo *LI = nullptr);
175 
176 /// Split the specified block at the specified instruction - everything before
177 /// SplitPt stays in Old and everything starting with SplitPt moves to a new
178 /// block. The two blocks are joined by an unconditional branch and the loop
179 /// info is updated.
181  DominatorTree *DT = nullptr, LoopInfo *LI = nullptr);
182 
183 /// This method introduces at least one new basic block into the function and
184 /// moves some of the predecessors of BB to be predecessors of the new block.
185 /// The new predecessors are indicated by the Preds array. The new block is
186 /// given a suffix of 'Suffix'. Returns new basic block to which predecessors
187 /// from Preds are now pointing.
188 ///
189 /// If BB is a landingpad block then additional basicblock might be introduced.
190 /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more
191 /// details on this case.
192 ///
193 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but
194 /// no other analyses. In particular, it does not preserve LoopSimplify
195 /// (because it's complicated to handle the case where one of the edges being
196 /// split is an exit of a loop with other exits).
197 ///
199  const char *Suffix,
200  DominatorTree *DT = nullptr,
201  LoopInfo *LI = nullptr,
202  bool PreserveLCSSA = false);
203 
204 /// This method transforms the landing pad, OrigBB, by introducing two new basic
205 /// blocks into the function. One of those new basic blocks gets the
206 /// predecessors listed in Preds. The other basic block gets the remaining
207 /// predecessors of OrigBB. The landingpad instruction OrigBB is clone into both
208 /// of the new basic blocks. The new blocks are given the suffixes 'Suffix1' and
209 /// 'Suffix2', and are returned in the NewBBs vector.
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).
215 ///
218  const char *Suffix, const char *Suffix2,
220  DominatorTree *DT = nullptr,
221  LoopInfo *LI = nullptr,
222  bool PreserveLCSSA = false);
223 
224 /// This method duplicates the specified return instruction into a predecessor
225 /// which ends in an unconditional branch. If the return instruction returns a
226 /// value defined by a PHI, propagate the right value into the return. It
227 /// returns the new return instruction in the predecessor.
229  BasicBlock *Pred);
230 
231 /// Split the containing block at the specified instruction - everything before
232 /// SplitBefore stays in the old basic block, and the rest of the instructions
233 /// in the BB are moved to a new block. The two blocks are connected by a
234 /// conditional branch (with value of Cmp being the condition).
235 /// Before:
236 /// Head
237 /// SplitBefore
238 /// Tail
239 /// After:
240 /// Head
241 /// if (Cond)
242 /// ThenBlock
243 /// SplitBefore
244 /// Tail
245 ///
246 /// If Unreachable is true, then ThenBlock ends with
247 /// UnreachableInst, otherwise it branches to Tail.
248 /// Returns the NewBasicBlock's terminator.
249 ///
250 /// Updates DT and LI if given.
252  bool Unreachable,
253  MDNode *BranchWeights = nullptr,
254  DominatorTree *DT = nullptr,
255  LoopInfo *LI = nullptr);
256 
257 /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen,
258 /// but also creates the ElseBlock.
259 /// Before:
260 /// Head
261 /// SplitBefore
262 /// Tail
263 /// After:
264 /// Head
265 /// if (Cond)
266 /// ThenBlock
267 /// else
268 /// ElseBlock
269 /// SplitBefore
270 /// Tail
271 void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore,
272  TerminatorInst **ThenTerm,
273  TerminatorInst **ElseTerm,
274  MDNode *BranchWeights = nullptr);
275 
276 /// Check whether BB is the merge point of a if-region.
277 /// If so, return the boolean condition that determines which entry into
278 /// BB will be taken. Also, return by references the block that will be
279 /// entered from if the condition is true, and the block that will be
280 /// entered if the condition is false.
281 ///
282 /// This does no checking to see if the true/false blocks have large or unsavory
283 /// instructions in them.
285  BasicBlock *&IfFalse);
286 
287 } // end namespace llvm
288 
289 #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.
unsigned getSuccessorIndex() const
This is used to interface between code that wants to operate on terminator instructions directly...
Definition: InstrTypes.h:161
void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, TerminatorInst **ThenTerm, TerminatorInst **ElseTerm, MDNode *BranchWeights=nullptr)
SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, but also creates the ElseBlock...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
Various leaf nodes.
Definition: ISDOpcodes.h:60
BasicBlock * getSuccessor(unsigned idx) const
Return the specified successor.
void DeleteDeadBlock(BasicBlock *BB)
Delete the specified block, which must have no predecessors.
std::pair< std::string, std::string > SplitBefore(std::string X, std::string S)
Definition: FuzzerUtil.h:70
Metadata node.
Definition: Metadata.h:862
unsigned SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
Loop over all of the edges in the CFG, breaking critical edges as they are found. ...
Option class for critical edge splitting.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
#define F(x, y, z)
Definition: MD5.cpp:55
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
void SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef< BasicBlock *> Preds, const char *Suffix, const char *Suffix2, SmallVectorImpl< BasicBlock *> &NewBBs, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, bool PreserveLCSSA=false)
This method transforms the landing pad, OrigBB, by introducing two new basic blocks into the function...
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:134
BasicBlock * SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
If this edge is a critical edge, insert a new node to split the critical edge.
CriticalEdgeSplittingOptions & setMergeIdenticalEdges()
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:54
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
SymbolTableList< Instruction > InstListType
Definition: BasicBlock.h:62
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock *> Preds, const char *Suffix, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
Value * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
TerminatorInst * 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 ...
CriticalEdgeSplittingOptions & setPreserveLCSSA()
CriticalEdgeSplittingOptions(DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:91
void FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemoryDependenceResults *MemDep=nullptr)
Attempts to merge a block into its predecessor, if possible.
#define I(x, y, z)
Definition: MD5.cpp:58
ReturnInst * FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, BasicBlock *Pred)
This method duplicates the specified return instruction into a predecessor which ends in an unconditi...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getNumSuccessors() const
Return the number of successors that this terminator has.
CriticalEdgeSplittingOptions & setDontDeleteUselessPHIs()
LLVM Value Representation.
Definition: Value.h:73
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
Split the edge connecting specified block.
const TerminatorInst * 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:120