/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h
Line | Count | Source (jump to first uncovered line) |
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" |
20 | | #include "llvm/Analysis/DomTreeUpdater.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. |
75 | | void FoldSingleEntryPHINodes(BasicBlock *BB, |
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. |
93 | | void ReplaceInstWithValue(BasicBlock::InstListType &BIL, |
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. |
100 | | void ReplaceInstWithInst(BasicBlock::InstListType &BIL, |
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. |
111 | | struct CriticalEdgeSplittingOptions { |
112 | | DominatorTree *DT; |
113 | | PostDominatorTree *PDT; |
114 | | LoopInfo *LI; |
115 | | MemorySSAUpdater *MSSAU; |
116 | | bool MergeIdenticalEdges = false; |
117 | | bool KeepOneInputPHIs = false; |
118 | | bool PreserveLCSSA = false; |
119 | | bool IgnoreUnreachableDests = false; |
120 | | |
121 | | CriticalEdgeSplittingOptions(DominatorTree *DT = nullptr, |
122 | | LoopInfo *LI = nullptr, |
123 | | MemorySSAUpdater *MSSAU = nullptr, |
124 | | PostDominatorTree *PDT = nullptr) |
125 | 101k | : DT(DT), PDT(PDT), LI(LI), MSSAU(MSSAU) {} |
126 | | |
127 | 5.48k | CriticalEdgeSplittingOptions &setMergeIdenticalEdges() { |
128 | 5.48k | MergeIdenticalEdges = true; |
129 | 5.48k | return *this; |
130 | 5.48k | } |
131 | | |
132 | 5.46k | CriticalEdgeSplittingOptions &setKeepOneInputPHIs() { |
133 | 5.46k | KeepOneInputPHIs = true; |
134 | 5.46k | return *this; |
135 | 5.46k | } |
136 | | |
137 | 76.0k | CriticalEdgeSplittingOptions &setPreserveLCSSA() { |
138 | 76.0k | PreserveLCSSA = true; |
139 | 76.0k | return *this; |
140 | 76.0k | } |
141 | | |
142 | 38 | CriticalEdgeSplittingOptions &setIgnoreUnreachableDests() { |
143 | 38 | IgnoreUnreachableDests = true; |
144 | 38 | return *this; |
145 | 38 | } |
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 = |
166 | | CriticalEdgeSplittingOptions()); |
167 | | |
168 | | inline BasicBlock * |
169 | | SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, |
170 | | const CriticalEdgeSplittingOptions &Options = |
171 | 0 | CriticalEdgeSplittingOptions()) { |
172 | 0 | return SplitCriticalEdge(BB->getTerminator(), SI.getSuccessorIndex(), |
173 | 0 | Options); |
174 | 0 | } |
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. |
180 | | inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, |
181 | | const CriticalEdgeSplittingOptions &Options = |
182 | 0 | CriticalEdgeSplittingOptions()) { |
183 | 0 | bool MadeChange = false; |
184 | 0 | Instruction *TI = (*PI)->getTerminator(); |
185 | 0 | for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) |
186 | 0 | if (TI->getSuccessor(i) == Succ) |
187 | 0 | MadeChange |= !!SplitCriticalEdge(TI, i, Options); |
188 | 0 | return MadeChange; |
189 | 0 | } |
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 * |
195 | | SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst, |
196 | | const CriticalEdgeSplittingOptions &Options = |
197 | 82.1k | CriticalEdgeSplittingOptions()) { |
198 | 82.1k | Instruction *TI = Src->getTerminator(); |
199 | 82.1k | unsigned i = 0; |
200 | 121k | while (true) { |
201 | 121k | assert(i != TI->getNumSuccessors() && "Edge doesn't exist!"); |
202 | 121k | if (TI->getSuccessor(i) == Dst) |
203 | 82.1k | return SplitCriticalEdge(TI, i, Options); |
204 | 39.5k | ++i; |
205 | 39.5k | } |
206 | 82.1k | } |
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. |
210 | | unsigned SplitAllCriticalEdges(Function &F, |
211 | | const CriticalEdgeSplittingOptions &Options = |
212 | | CriticalEdgeSplittingOptions()); |
213 | | |
214 | | /// Split the edge connecting specified block. |
215 | | BasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To, |
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. |
223 | | BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, |
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). |
241 | | BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, |
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). |
259 | | void SplitLandingPadPredecessors( |
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. |
269 | | ReturnInst *FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, |
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. |
294 | | Instruction *SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, |
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. |
328 | | Value *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, |
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. |
350 | | bool SplitIndirectBrCriticalEdges(Function &F, |
351 | | BranchProbabilityInfo *BPI = nullptr, |
352 | | BlockFrequencyInfo *BFI = nullptr); |
353 | | |
354 | | } // end namespace llvm |
355 | | |
356 | | #endif // LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H |