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/ADT/SetVector.h" |
21 | #include "llvm/IR/BasicBlock.h" |
22 | #include "llvm/IR/Dominators.h" |
23 | #include <cassert> |
24 | |
25 | namespace llvm { |
26 | class BranchInst; |
27 | class LandingPadInst; |
28 | class Loop; |
29 | class PHINode; |
30 | template <typename PtrType> class SmallPtrSetImpl; |
31 | class BlockFrequencyInfo; |
32 | class BranchProbabilityInfo; |
33 | class DomTreeUpdater; |
34 | class Function; |
35 | class IRBuilderBase; |
36 | class LoopInfo; |
37 | class MDNode; |
38 | class MemoryDependenceResults; |
39 | class MemorySSAUpdater; |
40 | class PostDominatorTree; |
41 | class ReturnInst; |
42 | class TargetLibraryInfo; |
43 | class Value; |
44 | |
45 | /// Replace contents of every block in \p BBs with single unreachable |
46 | /// instruction. If \p Updates is specified, collect all necessary DT updates |
47 | /// into this vector. If \p KeepOneInputPHIs is true, one-input Phis in |
48 | /// successors of blocks being deleted will be preserved. |
49 | void detachDeadBlocks(ArrayRef <BasicBlock *> BBs, |
50 | SmallVectorImpl<DominatorTree::UpdateType> *Updates, |
51 | bool KeepOneInputPHIs = false); |
52 | |
53 | /// Delete the specified block, which must have no predecessors. |
54 | void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU = nullptr, |
55 | bool KeepOneInputPHIs = false); |
56 | |
57 | /// Delete the specified blocks from \p BB. The set of deleted blocks must have |
58 | /// no predecessors that are not being deleted themselves. \p BBs must have no |
59 | /// duplicating blocks. If there are loops among this set of blocks, all |
60 | /// relevant loop info updates should be done before this function is called. |
61 | /// If \p KeepOneInputPHIs is true, one-input Phis in successors of blocks |
62 | /// being deleted will be preserved. |
63 | void DeleteDeadBlocks(ArrayRef <BasicBlock *> BBs, |
64 | DomTreeUpdater *DTU = nullptr, |
65 | bool KeepOneInputPHIs = false); |
66 | |
67 | /// Delete all basic blocks from \p F that are not reachable from its entry |
68 | /// node. If \p KeepOneInputPHIs is true, one-input Phis in successors of |
69 | /// blocks being deleted will be preserved. |
70 | bool EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU = nullptr, |
71 | bool KeepOneInputPHIs = false); |
72 | |
73 | /// We know that BB has one predecessor. If there are any single-entry PHI nodes |
74 | /// in it, fold them away. This handles the case when all entries to the PHI |
75 | /// nodes in a block are guaranteed equal, such as when the block has exactly |
76 | /// one predecessor. |
77 | bool FoldSingleEntryPHINodes(BasicBlock *BB, |
78 | MemoryDependenceResults *MemDep = nullptr); |
79 | |
80 | /// Examine each PHI in the given block and delete it if it is dead. Also |
81 | /// recursively delete any operands that become dead as a result. This includes |
82 | /// tracing the def-use list from the PHI to see if it is ultimately unused or |
83 | /// if it reaches an unused cycle. Return true if any PHIs were deleted. |
84 | bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr, |
85 | MemorySSAUpdater *MSSAU = nullptr); |
86 | |
87 | /// Attempts to merge a block into its predecessor, if possible. The return |
88 | /// value indicates success or failure. |
89 | /// By default do not merge blocks if BB's predecessor has multiple successors. |
90 | /// If PredecessorWithTwoSuccessors = true, the blocks can only be merged |
91 | /// if BB's Pred has a branch to BB and to AnotherBB, and BB has a single |
92 | /// successor Sing. In this case the branch will be updated with Sing instead of |
93 | /// BB, and BB will still be merged into its predecessor and removed. |
94 | /// If \p DT is not nullptr, update it directly; in that case, DTU must be |
95 | /// nullptr. |
96 | bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU = nullptr, |
97 | LoopInfo *LI = nullptr, |
98 | MemorySSAUpdater *MSSAU = nullptr, |
99 | MemoryDependenceResults *MemDep = nullptr, |
100 | bool PredecessorWithTwoSuccessors = false, |
101 | DominatorTree *DT = nullptr); |
102 | |
103 | /// Merge block(s) sucessors, if possible. Return true if at least two |
104 | /// of the blocks were merged together. |
105 | /// In order to merge, each block must be terminated by an unconditional |
106 | /// branch. If L is provided, then the blocks merged into their predecessors |
107 | /// must be in L. In addition, This utility calls on another utility: |
108 | /// MergeBlockIntoPredecessor. Blocks are successfully merged when the call to |
109 | /// MergeBlockIntoPredecessor returns true. |
110 | bool MergeBlockSuccessorsIntoGivenBlocks( |
111 | SmallPtrSetImpl<BasicBlock *> &MergeBlocks, Loop *L = nullptr, |
112 | DomTreeUpdater *DTU = nullptr, LoopInfo *LI = nullptr); |
113 | |
114 | /// Try to remove redundant dbg.value instructions from given basic block. |
115 | /// Returns true if at least one instruction was removed. Remove redundant |
116 | /// pseudo ops when RemovePseudoOp is true. |
117 | bool RemoveRedundantDbgInstrs(BasicBlock *BB); |
118 | |
119 | /// Replace all uses of an instruction (specified by BI) with a value, then |
120 | /// remove and delete the original instruction. |
121 | void ReplaceInstWithValue(BasicBlock::iterator &BI, Value *V); |
122 | |
123 | /// Replace the instruction specified by BI with the instruction specified by I. |
124 | /// Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. The |
125 | /// original instruction is deleted and BI is updated to point to the new |
126 | /// instruction. |
127 | void ReplaceInstWithInst(BasicBlock *BB, BasicBlock::iterator &BI, |
128 | Instruction *I); |
129 | |
130 | /// Replace the instruction specified by From with the instruction specified by |
131 | /// To. Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. |
132 | void ReplaceInstWithInst(Instruction *From, Instruction *To); |
133 | |
134 | /// Check if we can prove that all paths starting from this block converge |
135 | /// to a block that either has a @llvm.experimental.deoptimize call |
136 | /// prior to its terminating return instruction or is terminated by unreachable. |
137 | /// All blocks in the traversed sequence must have an unique successor, maybe |
138 | /// except for the last one. |
139 | bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB); |
140 | |
141 | /// Option class for critical edge splitting. |
142 | /// |
143 | /// This provides a builder interface for overriding the default options used |
144 | /// during critical edge splitting. |
145 | struct CriticalEdgeSplittingOptions { |
146 | DominatorTree *DT; |
147 | PostDominatorTree *PDT; |
148 | LoopInfo *LI; |
149 | MemorySSAUpdater *MSSAU; |
150 | bool MergeIdenticalEdges = false; |
151 | bool KeepOneInputPHIs = false; |
152 | bool PreserveLCSSA = false; |
153 | bool IgnoreUnreachableDests = false; |
154 | /// SplitCriticalEdge is guaranteed to preserve loop-simplify form if LI is |
155 | /// provided. If it cannot be preserved, no splitting will take place. If it |
156 | /// is not set, preserve loop-simplify form if possible. |
157 | bool PreserveLoopSimplify = true; |
158 | |
159 | CriticalEdgeSplittingOptions(DominatorTree *DT = nullptr, |
160 | LoopInfo *LI = nullptr, |
161 | MemorySSAUpdater *MSSAU = nullptr, |
162 | PostDominatorTree *PDT = nullptr) |
163 | : DT(DT), PDT(PDT), LI(LI), MSSAU(MSSAU) {} |
164 | |
165 | CriticalEdgeSplittingOptions &setMergeIdenticalEdges() { |
166 | MergeIdenticalEdges = true; |
167 | return *this; |
168 | } |
169 | |
170 | CriticalEdgeSplittingOptions &setKeepOneInputPHIs() { |
171 | KeepOneInputPHIs = true; |
172 | return *this; |
173 | } |
174 | |
175 | CriticalEdgeSplittingOptions &setPreserveLCSSA() { |
176 | PreserveLCSSA = true; |
177 | return *this; |
178 | } |
179 | |
180 | CriticalEdgeSplittingOptions &setIgnoreUnreachableDests() { |
181 | IgnoreUnreachableDests = true; |
182 | return *this; |
183 | } |
184 | |
185 | CriticalEdgeSplittingOptions &unsetPreserveLoopSimplify() { |
186 | PreserveLoopSimplify = false; |
187 | return *this; |
188 | } |
189 | }; |
190 | |
191 | /// When a loop exit edge is split, LCSSA form may require new PHIs in the new |
192 | /// exit block. This function inserts the new PHIs, as needed. Preds is a list |
193 | /// of preds inside the loop, SplitBB is the new loop exit block, and DestBB is |
194 | /// the old loop exit, now the successor of SplitBB. |
195 | void createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds, |
196 | BasicBlock *SplitBB, BasicBlock *DestBB); |
197 | |
198 | /// If this edge is a critical edge, insert a new node to split the critical |
199 | /// edge. This will update the analyses passed in through the option struct. |
200 | /// This returns the new block if the edge was split, null otherwise. |
201 | /// |
202 | /// If MergeIdenticalEdges in the options struct is true (not the default), |
203 | /// *all* edges from TI to the specified successor will be merged into the same |
204 | /// critical edge block. This is most commonly interesting with switch |
205 | /// instructions, which may have many edges to any one destination. This |
206 | /// ensures that all edges to that dest go to one block instead of each going |
207 | /// to a different block, but isn't the standard definition of a "critical |
208 | /// edge". |
209 | /// |
210 | /// It is invalid to call this function on a critical edge that starts at an |
211 | /// IndirectBrInst. Splitting these edges will almost always create an invalid |
212 | /// program because the address of the new block won't be the one that is jumped |
213 | /// to. |
214 | BasicBlock *SplitCriticalEdge(Instruction *TI, unsigned SuccNum, |
215 | const CriticalEdgeSplittingOptions &Options = |
216 | CriticalEdgeSplittingOptions(), |
217 | const Twine &BBName = "" ); |
218 | |
219 | /// If it is known that an edge is critical, SplitKnownCriticalEdge can be |
220 | /// called directly, rather than calling SplitCriticalEdge first. |
221 | BasicBlock *SplitKnownCriticalEdge(Instruction *TI, unsigned SuccNum, |
222 | const CriticalEdgeSplittingOptions &Options = |
223 | CriticalEdgeSplittingOptions(), |
224 | const Twine &BBName = "" ); |
225 | |
226 | /// If an edge from Src to Dst is critical, split the edge and return true, |
227 | /// otherwise return false. This method requires that there be an edge between |
228 | /// the two blocks. It updates the analyses passed in the options struct |
229 | inline BasicBlock * |
230 | SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst, |
231 | const CriticalEdgeSplittingOptions &Options = |
232 | CriticalEdgeSplittingOptions()) { |
233 | Instruction *TI = Src->getTerminator(); |
234 | unsigned i = 0; |
235 | while (true) { |
236 | assert(i != TI->getNumSuccessors() && "Edge doesn't exist!" ); |
237 | if (TI->getSuccessor(Idx: i) == Dst) |
238 | return SplitCriticalEdge(TI, SuccNum: i, Options); |
239 | ++i; |
240 | } |
241 | } |
242 | |
243 | /// Loop over all of the edges in the CFG, breaking critical edges as they are |
244 | /// found. Returns the number of broken edges. |
245 | unsigned SplitAllCriticalEdges(Function &F, |
246 | const CriticalEdgeSplittingOptions &Options = |
247 | CriticalEdgeSplittingOptions()); |
248 | |
249 | /// Split the edge connecting the specified blocks, and return the newly created |
250 | /// basic block between \p From and \p To. |
251 | BasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To, |
252 | DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, |
253 | MemorySSAUpdater *MSSAU = nullptr, |
254 | const Twine &BBName = "" ); |
255 | |
256 | /// Sets the unwind edge of an instruction to a particular successor. |
257 | void setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ); |
258 | |
259 | /// Replaces all uses of OldPred with the NewPred block in all PHINodes in a |
260 | /// block. |
261 | void updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred, |
262 | BasicBlock *NewPred, PHINode *Until = nullptr); |
263 | |
264 | /// Split the edge connect the specficed blocks in the case that \p Succ is an |
265 | /// Exception Handling Block |
266 | BasicBlock *ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ, |
267 | LandingPadInst *OriginalPad = nullptr, |
268 | PHINode *LandingPadReplacement = nullptr, |
269 | const CriticalEdgeSplittingOptions &Options = |
270 | CriticalEdgeSplittingOptions(), |
271 | const Twine &BBName = "" ); |
272 | |
273 | /// Split the specified block at the specified instruction. |
274 | /// |
275 | /// If \p Before is true, splitBlockBefore handles the block |
276 | /// splitting. Otherwise, execution proceeds as described below. |
277 | /// |
278 | /// Everything before \p SplitPt stays in \p Old and everything starting with \p |
279 | /// SplitPt moves to a new block. The two blocks are joined by an unconditional |
280 | /// branch. The new block with name \p BBName is returned. |
281 | /// |
282 | /// FIXME: deprecated, switch to the DomTreeUpdater-based one. |
283 | BasicBlock *SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, |
284 | LoopInfo *LI = nullptr, |
285 | MemorySSAUpdater *MSSAU = nullptr, |
286 | const Twine &BBName = "" , bool Before = false); |
287 | inline BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, |
288 | LoopInfo *LI = nullptr, |
289 | MemorySSAUpdater *MSSAU = nullptr, |
290 | const Twine &BBName = "" , bool Before = false) { |
291 | return SplitBlock(Old, SplitPt: SplitPt->getIterator(), DT, LI, MSSAU, BBName, Before); |
292 | } |
293 | |
294 | /// Split the specified block at the specified instruction. |
295 | /// |
296 | /// If \p Before is true, splitBlockBefore handles the block |
297 | /// splitting. Otherwise, execution proceeds as described below. |
298 | /// |
299 | /// Everything before \p SplitPt stays in \p Old and everything starting with \p |
300 | /// SplitPt moves to a new block. The two blocks are joined by an unconditional |
301 | /// branch. The new block with name \p BBName is returned. |
302 | BasicBlock *SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, |
303 | DomTreeUpdater *DTU = nullptr, LoopInfo *LI = nullptr, |
304 | MemorySSAUpdater *MSSAU = nullptr, |
305 | const Twine &BBName = "" , bool Before = false); |
306 | inline BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, |
307 | DomTreeUpdater *DTU = nullptr, LoopInfo *LI = nullptr, |
308 | MemorySSAUpdater *MSSAU = nullptr, |
309 | const Twine &BBName = "" , bool Before = false) { |
310 | return SplitBlock(Old, SplitPt: SplitPt->getIterator(), DTU, LI, MSSAU, BBName, Before); |
311 | } |
312 | |
313 | /// Split the specified block at the specified instruction \p SplitPt. |
314 | /// All instructions before \p SplitPt are moved to a new block and all |
315 | /// instructions after \p SplitPt stay in the old block. The new block and the |
316 | /// old block are joined by inserting an unconditional branch to the end of the |
317 | /// new block. The new block with name \p BBName is returned. |
318 | BasicBlock *splitBlockBefore(BasicBlock *Old, BasicBlock::iterator SplitPt, |
319 | DomTreeUpdater *DTU, LoopInfo *LI, |
320 | MemorySSAUpdater *MSSAU, const Twine &BBName = "" ); |
321 | inline BasicBlock *splitBlockBefore(BasicBlock *Old, Instruction *SplitPt, |
322 | DomTreeUpdater *DTU, LoopInfo *LI, |
323 | MemorySSAUpdater *MSSAU, const Twine &BBName = "" ) { |
324 | return splitBlockBefore(Old, SplitPt: SplitPt->getIterator(), DTU, LI, MSSAU, BBName); |
325 | } |
326 | |
327 | /// This method introduces at least one new basic block into the function and |
328 | /// moves some of the predecessors of BB to be predecessors of the new block. |
329 | /// The new predecessors are indicated by the Preds array. The new block is |
330 | /// given a suffix of 'Suffix'. Returns new basic block to which predecessors |
331 | /// from Preds are now pointing. |
332 | /// |
333 | /// If BB is a landingpad block then additional basicblock might be introduced. |
334 | /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more |
335 | /// details on this case. |
336 | /// |
337 | /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but |
338 | /// no other analyses. In particular, it does not preserve LoopSimplify |
339 | /// (because it's complicated to handle the case where one of the edges being |
340 | /// split is an exit of a loop with other exits). |
341 | /// |
342 | /// FIXME: deprecated, switch to the DomTreeUpdater-based one. |
343 | BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, |
344 | const char *Suffix, DominatorTree *DT, |
345 | LoopInfo *LI = nullptr, |
346 | MemorySSAUpdater *MSSAU = nullptr, |
347 | bool PreserveLCSSA = false); |
348 | |
349 | /// This method introduces at least one new basic block into the function and |
350 | /// moves some of the predecessors of BB to be predecessors of the new block. |
351 | /// The new predecessors are indicated by the Preds array. The new block is |
352 | /// given a suffix of 'Suffix'. Returns new basic block to which predecessors |
353 | /// from Preds are now pointing. |
354 | /// |
355 | /// If BB is a landingpad block then additional basicblock might be introduced. |
356 | /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more |
357 | /// details on this case. |
358 | /// |
359 | /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but |
360 | /// no other analyses. In particular, it does not preserve LoopSimplify |
361 | /// (because it's complicated to handle the case where one of the edges being |
362 | /// split is an exit of a loop with other exits). |
363 | BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, |
364 | const char *Suffix, |
365 | DomTreeUpdater *DTU = nullptr, |
366 | LoopInfo *LI = nullptr, |
367 | MemorySSAUpdater *MSSAU = nullptr, |
368 | bool PreserveLCSSA = false); |
369 | |
370 | /// This method transforms the landing pad, OrigBB, by introducing two new basic |
371 | /// blocks into the function. One of those new basic blocks gets the |
372 | /// predecessors listed in Preds. The other basic block gets the remaining |
373 | /// predecessors of OrigBB. The landingpad instruction OrigBB is clone into both |
374 | /// of the new basic blocks. The new blocks are given the suffixes 'Suffix1' and |
375 | /// 'Suffix2', and are returned in the NewBBs vector. |
376 | /// |
377 | /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but |
378 | /// no other analyses. In particular, it does not preserve LoopSimplify |
379 | /// (because it's complicated to handle the case where one of the edges being |
380 | /// split is an exit of a loop with other exits). |
381 | void SplitLandingPadPredecessors( |
382 | BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix, |
383 | const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs, |
384 | DomTreeUpdater *DTU = nullptr, LoopInfo *LI = nullptr, |
385 | MemorySSAUpdater *MSSAU = nullptr, bool PreserveLCSSA = false); |
386 | |
387 | /// This method duplicates the specified return instruction into a predecessor |
388 | /// which ends in an unconditional branch. If the return instruction returns a |
389 | /// value defined by a PHI, propagate the right value into the return. It |
390 | /// returns the new return instruction in the predecessor. |
391 | ReturnInst *FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, |
392 | BasicBlock *Pred, |
393 | DomTreeUpdater *DTU = nullptr); |
394 | |
395 | /// Split the containing block at the specified instruction - everything before |
396 | /// SplitBefore stays in the old basic block, and the rest of the instructions |
397 | /// in the BB are moved to a new block. The two blocks are connected by a |
398 | /// conditional branch (with value of Cmp being the condition). |
399 | /// Before: |
400 | /// Head |
401 | /// SplitBefore |
402 | /// Tail |
403 | /// After: |
404 | /// Head |
405 | /// if (Cond) |
406 | /// ThenBlock |
407 | /// SplitBefore |
408 | /// Tail |
409 | /// |
410 | /// If \p ThenBlock is not specified, a new block will be created for it. |
411 | /// If \p Unreachable is true, the newly created block will end with |
412 | /// UnreachableInst, otherwise it branches to Tail. |
413 | /// Returns the NewBasicBlock's terminator. |
414 | /// |
415 | /// Updates DTU and LI if given. |
416 | Instruction *SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, |
417 | bool Unreachable, |
418 | MDNode *BranchWeights = nullptr, |
419 | DomTreeUpdater *DTU = nullptr, |
420 | LoopInfo *LI = nullptr, |
421 | BasicBlock *ThenBlock = nullptr); |
422 | |
423 | inline Instruction *SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, |
424 | bool Unreachable, |
425 | MDNode *BranchWeights = nullptr, |
426 | DomTreeUpdater *DTU = nullptr, |
427 | LoopInfo *LI = nullptr, |
428 | BasicBlock *ThenBlock = nullptr) { |
429 | return SplitBlockAndInsertIfThen(Cond, SplitBefore: SplitBefore->getIterator(), |
430 | Unreachable, BranchWeights, DTU, LI, |
431 | ThenBlock); |
432 | } |
433 | |
434 | /// Similar to SplitBlockAndInsertIfThen, but the inserted block is on the false |
435 | /// path of the branch. |
436 | Instruction *SplitBlockAndInsertIfElse(Value *Cond, BasicBlock::iterator SplitBefore, |
437 | bool Unreachable, |
438 | MDNode *BranchWeights = nullptr, |
439 | DomTreeUpdater *DTU = nullptr, |
440 | LoopInfo *LI = nullptr, |
441 | BasicBlock *ElseBlock = nullptr); |
442 | |
443 | inline Instruction *SplitBlockAndInsertIfElse(Value *Cond, Instruction *SplitBefore, |
444 | bool Unreachable, |
445 | MDNode *BranchWeights = nullptr, |
446 | DomTreeUpdater *DTU = nullptr, |
447 | LoopInfo *LI = nullptr, |
448 | BasicBlock *ElseBlock = nullptr) { |
449 | return SplitBlockAndInsertIfElse(Cond, SplitBefore: SplitBefore->getIterator(), |
450 | Unreachable, BranchWeights, DTU, LI, |
451 | ElseBlock); |
452 | } |
453 | |
454 | /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, |
455 | /// but also creates the ElseBlock. |
456 | /// Before: |
457 | /// Head |
458 | /// SplitBefore |
459 | /// Tail |
460 | /// After: |
461 | /// Head |
462 | /// if (Cond) |
463 | /// ThenBlock |
464 | /// else |
465 | /// ElseBlock |
466 | /// SplitBefore |
467 | /// Tail |
468 | /// |
469 | /// Updates DT if given. |
470 | void SplitBlockAndInsertIfThenElse(Value *Cond, |
471 | BasicBlock::iterator SplitBefore, |
472 | Instruction **ThenTerm, |
473 | Instruction **ElseTerm, |
474 | MDNode *BranchWeights = nullptr, |
475 | DomTreeUpdater *DTU = nullptr, |
476 | LoopInfo *LI = nullptr); |
477 | |
478 | inline void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, |
479 | Instruction **ThenTerm, |
480 | Instruction **ElseTerm, |
481 | MDNode *BranchWeights = nullptr, |
482 | DomTreeUpdater *DTU = nullptr, |
483 | LoopInfo *LI = nullptr) |
484 | { |
485 | SplitBlockAndInsertIfThenElse(Cond, SplitBefore: SplitBefore->getIterator(), ThenTerm, |
486 | ElseTerm, BranchWeights, DTU, LI); |
487 | } |
488 | |
489 | /// Split the containing block at the specified instruction - everything before |
490 | /// SplitBefore stays in the old basic block, and the rest of the instructions |
491 | /// in the BB are moved to a new block. The two blocks are connected by a |
492 | /// conditional branch (with value of Cmp being the condition). |
493 | /// Before: |
494 | /// Head |
495 | /// SplitBefore |
496 | /// Tail |
497 | /// After: |
498 | /// Head |
499 | /// if (Cond) |
500 | /// TrueBlock |
501 | /// else |
502 | //// FalseBlock |
503 | /// SplitBefore |
504 | /// Tail |
505 | /// |
506 | /// If \p ThenBlock is null, the resulting CFG won't contain the TrueBlock. If |
507 | /// \p ThenBlock is non-null and points to non-null BasicBlock pointer, that |
508 | /// block will be inserted as the TrueBlock. Otherwise a new block will be |
509 | /// created. Likewise for the \p ElseBlock parameter. |
510 | /// If \p UnreachableThen or \p UnreachableElse is true, the corresponding newly |
511 | /// created blocks will end with UnreachableInst, otherwise with branches to |
512 | /// Tail. The function will not modify existing basic blocks passed to it. The |
513 | /// caller must ensure that Tail is reachable from Head. |
514 | /// Returns the newly created blocks in \p ThenBlock and \p ElseBlock. |
515 | /// Updates DTU and LI if given. |
516 | void SplitBlockAndInsertIfThenElse(Value *Cond, |
517 | BasicBlock::iterator SplitBefore, |
518 | BasicBlock **ThenBlock, |
519 | BasicBlock **ElseBlock, |
520 | bool UnreachableThen = false, |
521 | bool UnreachableElse = false, |
522 | MDNode *BranchWeights = nullptr, |
523 | DomTreeUpdater *DTU = nullptr, |
524 | LoopInfo *LI = nullptr); |
525 | |
526 | inline void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, |
527 | BasicBlock **ThenBlock, |
528 | BasicBlock **ElseBlock, |
529 | bool UnreachableThen = false, |
530 | bool UnreachableElse = false, |
531 | MDNode *BranchWeights = nullptr, |
532 | DomTreeUpdater *DTU = nullptr, |
533 | LoopInfo *LI = nullptr) { |
534 | SplitBlockAndInsertIfThenElse(Cond, SplitBefore: SplitBefore->getIterator(), ThenBlock, |
535 | ElseBlock, UnreachableThen, UnreachableElse, BranchWeights, DTU, LI); |
536 | } |
537 | |
538 | /// Insert a for (int i = 0; i < End; i++) loop structure (with the exception |
539 | /// that \p End is assumed > 0, and thus not checked on entry) at \p |
540 | /// SplitBefore. Returns the first insert point in the loop body, and the |
541 | /// PHINode for the induction variable (i.e. "i" above). |
542 | std::pair<Instruction*, Value*> |
543 | SplitBlockAndInsertSimpleForLoop(Value *End, Instruction *SplitBefore); |
544 | |
545 | /// Utility function for performing a given action on each lane of a vector |
546 | /// with \p EC elements. To simplify porting legacy code, this defaults to |
547 | /// unrolling the implied loop for non-scalable element counts, but this is |
548 | /// not considered to be part of the contract of this routine, and is |
549 | /// expected to change in the future. The callback takes as arguments an |
550 | /// IRBuilder whose insert point is correctly set for instantiating the |
551 | /// given index, and a value which is (at runtime) the index to access. |
552 | /// This index *may* be a constant. |
553 | void SplitBlockAndInsertForEachLane(ElementCount EC, Type *IndexTy, |
554 | Instruction *InsertBefore, |
555 | std::function<void(IRBuilderBase&, Value*)> Func); |
556 | |
557 | /// Utility function for performing a given action on each lane of a vector |
558 | /// with \p EVL effective length. EVL is assumed > 0. To simplify porting legacy |
559 | /// code, this defaults to unrolling the implied loop for non-scalable element |
560 | /// counts, but this is not considered to be part of the contract of this |
561 | /// routine, and is expected to change in the future. The callback takes as |
562 | /// arguments an IRBuilder whose insert point is correctly set for instantiating |
563 | /// the given index, and a value which is (at runtime) the index to access. This |
564 | /// index *may* be a constant. |
565 | void SplitBlockAndInsertForEachLane( |
566 | Value *End, Instruction *InsertBefore, |
567 | std::function<void(IRBuilderBase &, Value *)> Func); |
568 | |
569 | /// Check whether BB is the merge point of a if-region. |
570 | /// If so, return the branch instruction that determines which entry into |
571 | /// BB will be taken. Also, return by references the block that will be |
572 | /// entered from if the condition is true, and the block that will be |
573 | /// entered if the condition is false. |
574 | /// |
575 | /// This does no checking to see if the true/false blocks have large or unsavory |
576 | /// instructions in them. |
577 | BranchInst *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, |
578 | BasicBlock *&IfFalse); |
579 | |
580 | // Split critical edges where the source of the edge is an indirectbr |
581 | // instruction. This isn't always possible, but we can handle some easy cases. |
582 | // This is useful because MI is unable to split such critical edges, |
583 | // which means it will not be able to sink instructions along those edges. |
584 | // This is especially painful for indirect branches with many successors, where |
585 | // we end up having to prepare all outgoing values in the origin block. |
586 | // |
587 | // Our normal algorithm for splitting critical edges requires us to update |
588 | // the outgoing edges of the edge origin block, but for an indirectbr this |
589 | // is hard, since it would require finding and updating the block addresses |
590 | // the indirect branch uses. But if a block only has a single indirectbr |
591 | // predecessor, with the others being regular branches, we can do it in a |
592 | // different way. |
593 | // Say we have A -> D, B -> D, I -> D where only I -> D is an indirectbr. |
594 | // We can split D into D0 and D1, where D0 contains only the PHIs from D, |
595 | // and D1 is the D block body. We can then duplicate D0 as D0A and D0B, and |
596 | // create the following structure: |
597 | // A -> D0A, B -> D0A, I -> D0B, D0A -> D1, D0B -> D1 |
598 | // If BPI and BFI aren't non-null, BPI/BFI will be updated accordingly. |
599 | // When `IgnoreBlocksWithoutPHI` is set to `true` critical edges leading to a |
600 | // block without phi-instructions will not be split. |
601 | bool SplitIndirectBrCriticalEdges(Function &F, bool IgnoreBlocksWithoutPHI, |
602 | BranchProbabilityInfo *BPI = nullptr, |
603 | BlockFrequencyInfo *BFI = nullptr); |
604 | |
605 | /// Given a set of incoming and outgoing blocks, create a "hub" such that every |
606 | /// edge from an incoming block InBB to an outgoing block OutBB is now split |
607 | /// into two edges, one from InBB to the hub and another from the hub to |
608 | /// OutBB. The hub consists of a series of guard blocks, one for each outgoing |
609 | /// block. Each guard block conditionally branches to the corresponding outgoing |
610 | /// block, or the next guard block in the chain. These guard blocks are returned |
611 | /// in the argument vector. |
612 | /// |
613 | /// Since the control flow edges from InBB to OutBB have now been replaced, the |
614 | /// function also updates any PHINodes in OutBB. For each such PHINode, the |
615 | /// operands corresponding to incoming blocks are moved to a new PHINode in the |
616 | /// hub, and the hub is made an operand of the original PHINode. |
617 | /// |
618 | /// Input CFG: |
619 | /// ---------- |
620 | /// |
621 | /// Def |
622 | /// | |
623 | /// v |
624 | /// In1 In2 |
625 | /// | | |
626 | /// | | |
627 | /// v v |
628 | /// Foo ---> Out1 Out2 |
629 | /// | |
630 | /// v |
631 | /// Use |
632 | /// |
633 | /// |
634 | /// Create hub: Incoming = {In1, In2}, Outgoing = {Out1, Out2} |
635 | /// ---------------------------------------------------------- |
636 | /// |
637 | /// Def |
638 | /// | |
639 | /// v |
640 | /// In1 In2 Foo |
641 | /// | Hub | | |
642 | /// | + - - | - - + | |
643 | /// | ' v ' V |
644 | /// +------> Guard1 -----> Out1 |
645 | /// ' | ' |
646 | /// ' v ' |
647 | /// ' Guard2 -----> Out2 |
648 | /// ' ' | |
649 | /// + - - - - - + | |
650 | /// v |
651 | /// Use |
652 | /// |
653 | /// Limitations: |
654 | /// ----------- |
655 | /// 1. This assumes that all terminators in the CFG are direct branches (the |
656 | /// "br" instruction). The presence of any other control flow such as |
657 | /// indirectbr, switch or callbr will cause an assert. |
658 | /// |
659 | /// 2. The updates to the PHINodes are not sufficient to restore SSA |
660 | /// form. Consider a definition Def, its use Use, incoming block In2 and |
661 | /// outgoing block Out2, such that: |
662 | /// a. In2 is reachable from D or contains D. |
663 | /// b. U is reachable from Out2 or is contained in Out2. |
664 | /// c. U is not a PHINode if U is contained in Out2. |
665 | /// |
666 | /// Clearly, Def dominates Out2 since the program is valid SSA. But when the |
667 | /// hub is introduced, there is a new path through the hub along which Use is |
668 | /// reachable from entry without passing through Def, and SSA is no longer |
669 | /// valid. To fix this, we need to look at all the blocks post-dominated by |
670 | /// the hub on the one hand, and dominated by Out2 on the other. This is left |
671 | /// for the caller to accomplish, since each specific use of this function |
672 | /// may have additional information which simplifies this fixup. For example, |
673 | /// see restoreSSA() in the UnifyLoopExits pass. |
674 | BasicBlock *CreateControlFlowHub( |
675 | DomTreeUpdater *DTU, SmallVectorImpl<BasicBlock *> &GuardBlocks, |
676 | const SetVector<BasicBlock *> &Predecessors, |
677 | const SetVector<BasicBlock *> &Successors, const StringRef Prefix, |
678 | std::optional<unsigned> MaxControlFlowBooleans = std::nullopt); |
679 | |
680 | // Utility function for inverting branch condition and for swapping its |
681 | // successors |
682 | void InvertBranch(BranchInst *PBI, IRBuilderBase &Builder); |
683 | |
684 | // Check whether the function only has simple terminator: |
685 | // br/brcond/unreachable/ret |
686 | bool hasOnlySimpleTerminator(const Function &F); |
687 | |
688 | // Returns true if these basic blocks belong to a presplit coroutine and the |
689 | // edge corresponds to the 'default' case in the switch statement in the |
690 | // pattern: |
691 | // |
692 | // %0 = call i8 @llvm.coro.suspend(token none, i1 false) |
693 | // switch i8 %0, label %suspend [i8 0, label %resume |
694 | // i8 1, label %cleanup] |
695 | // |
696 | // i.e. the edge to the `%suspend` BB. This edge is special in that it will |
697 | // be elided by coroutine lowering (coro-split), and the `%suspend` BB needs |
698 | // to be kept as-is. It's not a real CFG edge - post-lowering, it will end |
699 | // up being a `ret`, and it must be thus lowerable to support symmetric |
700 | // transfer. For example: |
701 | // - this edge is not a loop exit edge if encountered in a loop (and should |
702 | // be ignored) |
703 | // - must not be split for PGO instrumentation, for example. |
704 | bool isPresplitCoroSuspendExitEdge(const BasicBlock &Src, |
705 | const BasicBlock &Dest); |
706 | } // end namespace llvm |
707 | |
708 | #endif // LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H |
709 | |