LLVM  17.0.0git
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"
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 LoopInfo;
36 class MDNode;
37 class MemoryDependenceResults;
38 class MemorySSAUpdater;
39 class PostDominatorTree;
40 class ReturnInst;
41 class TargetLibraryInfo;
42 class Value;
43 
44 /// Replace contents of every block in \p BBs with single unreachable
45 /// instruction. If \p Updates is specified, collect all necessary DT updates
46 /// into this vector. If \p KeepOneInputPHIs is true, one-input Phis in
47 /// successors of blocks being deleted will be preserved.
48 void detachDeadBlocks(ArrayRef <BasicBlock *> BBs,
49  SmallVectorImpl<DominatorTree::UpdateType> *Updates,
50  bool KeepOneInputPHIs = false);
51 
52 /// Delete the specified block, which must have no predecessors.
53 void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU = nullptr,
54  bool KeepOneInputPHIs = false);
55 
56 /// Delete the specified blocks from \p BB. The set of deleted blocks must have
57 /// no predecessors that are not being deleted themselves. \p BBs must have no
58 /// duplicating blocks. If there are loops among this set of blocks, all
59 /// relevant loop info updates should be done before this function is called.
60 /// If \p KeepOneInputPHIs is true, one-input Phis in successors of blocks
61 /// being deleted will be preserved.
62 void DeleteDeadBlocks(ArrayRef <BasicBlock *> BBs,
63  DomTreeUpdater *DTU = nullptr,
64  bool KeepOneInputPHIs = false);
65 
66 /// Delete all basic blocks from \p F that are not reachable from its entry
67 /// node. If \p KeepOneInputPHIs is true, one-input Phis in successors of
68 /// blocks being deleted will be preserved.
69 bool EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU = nullptr,
70  bool KeepOneInputPHIs = false);
71 
72 /// We know that BB has one predecessor. If there are any single-entry PHI nodes
73 /// in it, fold them away. This handles the case when all entries to the PHI
74 /// nodes in a block are guaranteed equal, such as when the block has exactly
75 /// one predecessor.
77  MemoryDependenceResults *MemDep = nullptr);
78 
79 /// Examine each PHI in the given block and delete it if it is dead. Also
80 /// recursively delete any operands that become dead as a result. This includes
81 /// tracing the def-use list from the PHI to see if it is ultimately unused or
82 /// if it reaches an unused cycle. Return true if any PHIs were deleted.
83 bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr,
84  MemorySSAUpdater *MSSAU = nullptr);
85 
86 /// Attempts to merge a block into its predecessor, if possible. The return
87 /// value indicates success or failure.
88 /// By default do not merge blocks if BB's predecessor has multiple successors.
89 /// If PredecessorWithTwoSuccessors = true, the blocks can only be merged
90 /// if BB's Pred has a branch to BB and to AnotherBB, and BB has a single
91 /// successor Sing. In this case the branch will be updated with Sing instead of
92 /// BB, and BB will still be merged into its predecessor and removed.
93 /// If \p DT is not nullptr, update it directly; in that case, DTU must be
94 /// nullptr.
95 bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU = nullptr,
96  LoopInfo *LI = nullptr,
97  MemorySSAUpdater *MSSAU = nullptr,
98  MemoryDependenceResults *MemDep = nullptr,
99  bool PredecessorWithTwoSuccessors = false,
100  DominatorTree *DT = nullptr);
101 
102 /// Merge block(s) sucessors, if possible. Return true if at least two
103 /// of the blocks were merged together.
104 /// In order to merge, each block must be terminated by an unconditional
105 /// branch. If L is provided, then the blocks merged into their predecessors
106 /// must be in L. In addition, This utility calls on another utility:
107 /// MergeBlockIntoPredecessor. Blocks are successfully merged when the call to
108 /// MergeBlockIntoPredecessor returns true.
110  SmallPtrSetImpl<BasicBlock *> &MergeBlocks, Loop *L = nullptr,
111  DomTreeUpdater *DTU = nullptr, LoopInfo *LI = nullptr);
112 
113 /// Try to remove redundant dbg.value instructions from given basic block.
114 /// Returns true if at least one instruction was removed. Remove redundant
115 /// pseudo ops when RemovePseudoOp is true.
117 
118 /// Replace all uses of an instruction (specified by BI) with a value, then
119 /// remove and delete the original instruction.
121 
122 /// Replace the instruction specified by BI with the instruction specified by I.
123 /// Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. The
124 /// original instruction is deleted and BI is updated to point to the new
125 /// instruction.
127  Instruction *I);
128 
129 /// Replace the instruction specified by From with the instruction specified by
130 /// To. Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc.
131 void ReplaceInstWithInst(Instruction *From, Instruction *To);
132 
133 /// Check if we can prove that all paths starting from this block converge
134 /// to a block that either has a @llvm.experimental.deoptimize call
135 /// prior to its terminating return instruction or is terminated by unreachable.
136 /// All blocks in the traversed sequence must have an unique successor, maybe
137 /// except for the last one.
139 
140 /// Option class for critical edge splitting.
141 ///
142 /// This provides a builder interface for overriding the default options used
143 /// during critical edge splitting.
149  bool MergeIdenticalEdges = false;
150  bool KeepOneInputPHIs = false;
151  bool PreserveLCSSA = false;
153  /// SplitCriticalEdge is guaranteed to preserve loop-simplify form if LI is
154  /// provided. If it cannot be preserved, no splitting will take place. If it
155  /// is not set, preserve loop-simplify form if possible.
156  bool PreserveLoopSimplify = true;
157 
159  LoopInfo *LI = nullptr,
160  MemorySSAUpdater *MSSAU = nullptr,
161  PostDominatorTree *PDT = nullptr)
162  : DT(DT), PDT(PDT), LI(LI), MSSAU(MSSAU) {}
163 
165  MergeIdenticalEdges = true;
166  return *this;
167  }
168 
170  KeepOneInputPHIs = true;
171  return *this;
172  }
173 
175  PreserveLCSSA = true;
176  return *this;
177  }
178 
180  IgnoreUnreachableDests = true;
181  return *this;
182  }
183 
185  PreserveLoopSimplify = false;
186  return *this;
187  }
188 };
189 
190 /// When a loop exit edge is split, LCSSA form may require new PHIs in the new
191 /// exit block. This function inserts the new PHIs, as needed. Preds is a list
192 /// of preds inside the loop, SplitBB is the new loop exit block, and DestBB is
193 /// the old loop exit, now the successor of SplitBB.
194 void createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds,
195  BasicBlock *SplitBB, BasicBlock *DestBB);
196 
197 /// If this edge is a critical edge, insert a new node to split the critical
198 /// edge. This will update the analyses passed in through the option struct.
199 /// This returns the new block if the edge was split, null otherwise.
200 ///
201 /// If MergeIdenticalEdges in the options struct is true (not the default),
202 /// *all* edges from TI to the specified successor will be merged into the same
203 /// critical edge block. This is most commonly interesting with switch
204 /// instructions, which may have many edges to any one destination. This
205 /// ensures that all edges to that dest go to one block instead of each going
206 /// to a different block, but isn't the standard definition of a "critical
207 /// edge".
208 ///
209 /// It is invalid to call this function on a critical edge that starts at an
210 /// IndirectBrInst. Splitting these edges will almost always create an invalid
211 /// program because the address of the new block won't be the one that is jumped
212 /// to.
213 BasicBlock *SplitCriticalEdge(Instruction *TI, unsigned SuccNum,
214  const CriticalEdgeSplittingOptions &Options =
215  CriticalEdgeSplittingOptions(),
216  const Twine &BBName = "");
217 
218 /// If it is known that an edge is critical, SplitKnownCriticalEdge can be
219 /// called directly, rather than calling SplitCriticalEdge first.
220 BasicBlock *SplitKnownCriticalEdge(Instruction *TI, unsigned SuccNum,
221  const CriticalEdgeSplittingOptions &Options =
222  CriticalEdgeSplittingOptions(),
223  const Twine &BBName = "");
224 
225 /// If an edge from Src to Dst is critical, split the edge and return true,
226 /// otherwise return false. This method requires that there be an edge between
227 /// the two blocks. It updates the analyses passed in the options struct
228 inline BasicBlock *
232  Instruction *TI = Src->getTerminator();
233  unsigned i = 0;
234  while (true) {
235  assert(i != TI->getNumSuccessors() && "Edge doesn't exist!");
236  if (TI->getSuccessor(i) == Dst)
237  return SplitCriticalEdge(TI, i, Options);
238  ++i;
239  }
240 }
241 
242 /// Loop over all of the edges in the CFG, breaking critical edges as they are
243 /// found. Returns the number of broken edges.
244 unsigned SplitAllCriticalEdges(Function &F,
245  const CriticalEdgeSplittingOptions &Options =
246  CriticalEdgeSplittingOptions());
247 
248 /// Split the edge connecting the specified blocks, and return the newly created
249 /// basic block between \p From and \p To.
251  DominatorTree *DT = nullptr, LoopInfo *LI = nullptr,
252  MemorySSAUpdater *MSSAU = nullptr,
253  const Twine &BBName = "");
254 
255 /// Sets the unwind edge of an instruction to a particular successor.
256 void setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ);
257 
258 /// Replaces all uses of OldPred with the NewPred block in all PHINodes in a
259 /// block.
260 void updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred,
261  BasicBlock *NewPred, PHINode *Until = nullptr);
262 
263 /// Split the edge connect the specficed blocks in the case that \p Succ is an
264 /// Exception Handling Block
266  LandingPadInst *OriginalPad = nullptr,
267  PHINode *LandingPadReplacement = nullptr,
268  const CriticalEdgeSplittingOptions &Options =
269  CriticalEdgeSplittingOptions(),
270  const Twine &BBName = "");
271 
272 /// Split the specified block at the specified instruction.
273 ///
274 /// If \p Before is true, splitBlockBefore handles the block
275 /// splitting. Otherwise, execution proceeds as described below.
276 ///
277 /// Everything before \p SplitPt stays in \p Old and everything starting with \p
278 /// SplitPt moves to a new block. The two blocks are joined by an unconditional
279 /// branch. The new block with name \p BBName is returned.
280 ///
281 /// FIXME: deprecated, switch to the DomTreeUpdater-based one.
282 BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT,
283  LoopInfo *LI = nullptr,
284  MemorySSAUpdater *MSSAU = nullptr,
285  const Twine &BBName = "", bool Before = false);
286 
287 /// Split the specified block at the specified instruction.
288 ///
289 /// If \p Before is true, splitBlockBefore handles the block
290 /// splitting. Otherwise, execution proceeds as described below.
291 ///
292 /// Everything before \p SplitPt stays in \p Old and everything starting with \p
293 /// SplitPt moves to a new block. The two blocks are joined by an unconditional
294 /// branch. The new block with name \p BBName is returned.
295 BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt,
296  DomTreeUpdater *DTU = nullptr, LoopInfo *LI = nullptr,
297  MemorySSAUpdater *MSSAU = nullptr,
298  const Twine &BBName = "", bool Before = false);
299 
300 /// Split the specified block at the specified instruction \p SplitPt.
301 /// All instructions before \p SplitPt are moved to a new block and all
302 /// instructions after \p SplitPt stay in the old block. The new block and the
303 /// old block are joined by inserting an unconditional branch to the end of the
304 /// new block. The new block with name \p BBName is returned.
305 BasicBlock *splitBlockBefore(BasicBlock *Old, Instruction *SplitPt,
306  DomTreeUpdater *DTU, LoopInfo *LI,
307  MemorySSAUpdater *MSSAU, const Twine &BBName = "");
308 
309 /// This method introduces at least one new basic block into the function and
310 /// moves some of the predecessors of BB to be predecessors of the new block.
311 /// The new predecessors are indicated by the Preds array. The new block is
312 /// given a suffix of 'Suffix'. Returns new basic block to which predecessors
313 /// from Preds are now pointing.
314 ///
315 /// If BB is a landingpad block then additional basicblock might be introduced.
316 /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more
317 /// details on this case.
318 ///
319 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but
320 /// no other analyses. In particular, it does not preserve LoopSimplify
321 /// (because it's complicated to handle the case where one of the edges being
322 /// split is an exit of a loop with other exits).
323 ///
324 /// FIXME: deprecated, switch to the DomTreeUpdater-based one.
325 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
326  const char *Suffix, DominatorTree *DT,
327  LoopInfo *LI = nullptr,
328  MemorySSAUpdater *MSSAU = nullptr,
329  bool PreserveLCSSA = false);
330 
331 /// This method introduces at least one new basic block into the function and
332 /// moves some of the predecessors of BB to be predecessors of the new block.
333 /// The new predecessors are indicated by the Preds array. The new block is
334 /// given a suffix of 'Suffix'. Returns new basic block to which predecessors
335 /// from Preds are now pointing.
336 ///
337 /// If BB is a landingpad block then additional basicblock might be introduced.
338 /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more
339 /// details on this case.
340 ///
341 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but
342 /// no other analyses. In particular, it does not preserve LoopSimplify
343 /// (because it's complicated to handle the case where one of the edges being
344 /// split is an exit of a loop with other exits).
345 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
346  const char *Suffix,
347  DomTreeUpdater *DTU = nullptr,
348  LoopInfo *LI = nullptr,
349  MemorySSAUpdater *MSSAU = nullptr,
350  bool PreserveLCSSA = false);
351 
352 /// This method transforms the landing pad, OrigBB, by introducing two new basic
353 /// blocks into the function. One of those new basic blocks gets the
354 /// predecessors listed in Preds. The other basic block gets the remaining
355 /// predecessors of OrigBB. The landingpad instruction OrigBB is clone into both
356 /// of the new basic blocks. The new blocks are given the suffixes 'Suffix1' and
357 /// 'Suffix2', and are returned in the NewBBs vector.
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 ///
364 /// FIXME: deprecated, switch to the DomTreeUpdater-based one.
366  ArrayRef<BasicBlock *> Preds,
367  const char *Suffix, const char *Suffix2,
368  SmallVectorImpl<BasicBlock *> &NewBBs,
369  DominatorTree *DT, LoopInfo *LI = nullptr,
370  MemorySSAUpdater *MSSAU = nullptr,
371  bool PreserveLCSSA = false);
372 
373 /// This method transforms the landing pad, OrigBB, by introducing two new basic
374 /// blocks into the function. One of those new basic blocks gets the
375 /// predecessors listed in Preds. The other basic block gets the remaining
376 /// predecessors of OrigBB. The landingpad instruction OrigBB is clone into both
377 /// of the new basic blocks. The new blocks are given the suffixes 'Suffix1' and
378 /// 'Suffix2', and are returned in the NewBBs vector.
379 ///
380 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but
381 /// no other analyses. In particular, it does not preserve LoopSimplify
382 /// (because it's complicated to handle the case where one of the edges being
383 /// split is an exit of a loop with other exits).
385  BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix,
386  const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs,
387  DomTreeUpdater *DTU = nullptr, LoopInfo *LI = nullptr,
388  MemorySSAUpdater *MSSAU = nullptr, bool PreserveLCSSA = false);
389 
390 /// This method duplicates the specified return instruction into a predecessor
391 /// which ends in an unconditional branch. If the return instruction returns a
392 /// value defined by a PHI, propagate the right value into the return. It
393 /// returns the new return instruction in the predecessor.
394 ReturnInst *FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB,
395  BasicBlock *Pred,
396  DomTreeUpdater *DTU = nullptr);
397 
398 /// Split the containing block at the specified instruction - everything before
399 /// SplitBefore stays in the old basic block, and the rest of the instructions
400 /// in the BB are moved to a new block. The two blocks are connected by a
401 /// conditional branch (with value of Cmp being the condition).
402 /// Before:
403 /// Head
404 /// SplitBefore
405 /// Tail
406 /// After:
407 /// Head
408 /// if (Cond)
409 /// ThenBlock
410 /// SplitBefore
411 /// Tail
412 ///
413 /// If \p ThenBlock is not specified, a new block will be created for it.
414 /// If \p Unreachable is true, the newly created block will end with
415 /// UnreachableInst, otherwise it branches to Tail.
416 /// Returns the NewBasicBlock's terminator.
417 ///
418 /// Updates DT and LI if given.
419 ///
420 /// FIXME: deprecated, switch to the DomTreeUpdater-based one.
421 Instruction *SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore,
422  bool Unreachable, MDNode *BranchWeights,
423  DominatorTree *DT,
424  LoopInfo *LI = nullptr,
425  BasicBlock *ThenBlock = nullptr);
426 
427 /// Split the containing block at the specified instruction - everything before
428 /// SplitBefore stays in the old basic block, and the rest of the instructions
429 /// in the BB are moved to a new block. The two blocks are connected by a
430 /// conditional branch (with value of Cmp being the condition).
431 /// Before:
432 /// Head
433 /// SplitBefore
434 /// Tail
435 /// After:
436 /// Head
437 /// if (Cond)
438 /// ThenBlock
439 /// SplitBefore
440 /// Tail
441 ///
442 /// If \p ThenBlock is not specified, a new block will be created for it.
443 /// If \p Unreachable is true, the newly created block will end with
444 /// UnreachableInst, otherwise it branches to Tail.
445 /// Returns the NewBasicBlock's terminator.
446 ///
447 /// Updates DT and LI if given.
448 Instruction *SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore,
449  bool Unreachable,
450  MDNode *BranchWeights = nullptr,
451  DomTreeUpdater *DTU = nullptr,
452  LoopInfo *LI = nullptr,
453  BasicBlock *ThenBlock = nullptr);
454 
455 /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen,
456 /// but also creates the ElseBlock.
457 /// Before:
458 /// Head
459 /// SplitBefore
460 /// Tail
461 /// After:
462 /// Head
463 /// if (Cond)
464 /// ThenBlock
465 /// else
466 /// ElseBlock
467 /// SplitBefore
468 /// Tail
469 ///
470 /// Updates DT if given.
471 void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore,
472  Instruction **ThenTerm,
473  Instruction **ElseTerm,
474  MDNode *BranchWeights = nullptr,
475  DomTreeUpdater *DTU = nullptr);
476 
477 /// Check whether BB is the merge point of a if-region.
478 /// If so, return the branch instruction that determines which entry into
479 /// BB will be taken. Also, return by references the block that will be
480 /// entered from if the condition is true, and the block that will be
481 /// entered if the condition is false.
482 ///
483 /// This does no checking to see if the true/false blocks have large or unsavory
484 /// instructions in them.
485 BranchInst *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue,
486  BasicBlock *&IfFalse);
487 
488 // Split critical edges where the source of the edge is an indirectbr
489 // instruction. This isn't always possible, but we can handle some easy cases.
490 // This is useful because MI is unable to split such critical edges,
491 // which means it will not be able to sink instructions along those edges.
492 // This is especially painful for indirect branches with many successors, where
493 // we end up having to prepare all outgoing values in the origin block.
494 //
495 // Our normal algorithm for splitting critical edges requires us to update
496 // the outgoing edges of the edge origin block, but for an indirectbr this
497 // is hard, since it would require finding and updating the block addresses
498 // the indirect branch uses. But if a block only has a single indirectbr
499 // predecessor, with the others being regular branches, we can do it in a
500 // different way.
501 // Say we have A -> D, B -> D, I -> D where only I -> D is an indirectbr.
502 // We can split D into D0 and D1, where D0 contains only the PHIs from D,
503 // and D1 is the D block body. We can then duplicate D0 as D0A and D0B, and
504 // create the following structure:
505 // A -> D0A, B -> D0A, I -> D0B, D0A -> D1, D0B -> D1
506 // If BPI and BFI aren't non-null, BPI/BFI will be updated accordingly.
507 // When `IgnoreBlocksWithoutPHI` is set to `true` critical edges leading to a
508 // block without phi-instructions will not be split.
509 bool SplitIndirectBrCriticalEdges(Function &F, bool IgnoreBlocksWithoutPHI,
510  BranchProbabilityInfo *BPI = nullptr,
511  BlockFrequencyInfo *BFI = nullptr);
512 
513 /// Given a set of incoming and outgoing blocks, create a "hub" such that every
514 /// edge from an incoming block InBB to an outgoing block OutBB is now split
515 /// into two edges, one from InBB to the hub and another from the hub to
516 /// OutBB. The hub consists of a series of guard blocks, one for each outgoing
517 /// block. Each guard block conditionally branches to the corresponding outgoing
518 /// block, or the next guard block in the chain. These guard blocks are returned
519 /// in the argument vector.
520 ///
521 /// Since the control flow edges from InBB to OutBB have now been replaced, the
522 /// function also updates any PHINodes in OutBB. For each such PHINode, the
523 /// operands corresponding to incoming blocks are moved to a new PHINode in the
524 /// hub, and the hub is made an operand of the original PHINode.
525 ///
526 /// Input CFG:
527 /// ----------
528 ///
529 /// Def
530 /// |
531 /// v
532 /// In1 In2
533 /// | |
534 /// | |
535 /// v v
536 /// Foo ---> Out1 Out2
537 /// |
538 /// v
539 /// Use
540 ///
541 ///
542 /// Create hub: Incoming = {In1, In2}, Outgoing = {Out1, Out2}
543 /// ----------------------------------------------------------
544 ///
545 /// Def
546 /// |
547 /// v
548 /// In1 In2 Foo
549 /// | Hub | |
550 /// | + - - | - - + |
551 /// | ' v ' V
552 /// +------> Guard1 -----> Out1
553 /// ' | '
554 /// ' v '
555 /// ' Guard2 -----> Out2
556 /// ' ' |
557 /// + - - - - - + |
558 /// v
559 /// Use
560 ///
561 /// Limitations:
562 /// -----------
563 /// 1. This assumes that all terminators in the CFG are direct branches (the
564 /// "br" instruction). The presence of any other control flow such as
565 /// indirectbr, switch or callbr will cause an assert.
566 ///
567 /// 2. The updates to the PHINodes are not sufficient to restore SSA
568 /// form. Consider a definition Def, its use Use, incoming block In2 and
569 /// outgoing block Out2, such that:
570 /// a. In2 is reachable from D or contains D.
571 /// b. U is reachable from Out2 or is contained in Out2.
572 /// c. U is not a PHINode if U is contained in Out2.
573 ///
574 /// Clearly, Def dominates Out2 since the program is valid SSA. But when the
575 /// hub is introduced, there is a new path through the hub along which Use is
576 /// reachable from entry without passing through Def, and SSA is no longer
577 /// valid. To fix this, we need to look at all the blocks post-dominated by
578 /// the hub on the one hand, and dominated by Out2 on the other. This is left
579 /// for the caller to accomplish, since each specific use of this function
580 /// may have additional information which simplifies this fixup. For example,
581 /// see restoreSSA() in the UnifyLoopExits pass.
583  DomTreeUpdater *DTU, SmallVectorImpl<BasicBlock *> &GuardBlocks,
584  const SetVector<BasicBlock *> &Predecessors,
585  const SetVector<BasicBlock *> &Successors, const StringRef Prefix,
586  std::optional<unsigned> MaxControlFlowBooleans = std::nullopt);
587 
588 } // end namespace llvm
589 
590 #endif // LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H
i
i
Definition: README.txt:29
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
Definition: Instruction.cpp:823
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::SplitLandingPadPredecessors
void SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef< BasicBlock * > Preds, const char *Suffix, const char *Suffix2, SmallVectorImpl< BasicBlock * > &NewBBs, DominatorTree *DT, 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...
Definition: BasicBlockUtils.cpp:1392
llvm::CriticalEdgeSplittingOptions::MSSAU
MemorySSAUpdater * MSSAU
Definition: BasicBlockUtils.h:148
llvm::ReplaceInstWithInst
void ReplaceInstWithInst(BasicBlock *BB, BasicBlock::iterator &BI, Instruction *I)
Replace the instruction specified by BI with the instruction specified by I.
Definition: BasicBlockUtils.cpp:576
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
llvm::cl::Prefix
@ Prefix
Definition: CommandLine.h:159
llvm::DeleteDeadBlocks
void DeleteDeadBlocks(ArrayRef< BasicBlock * > BBs, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified blocks from BB.
Definition: BasicBlockUtils.cpp:100
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::detachDeadBlocks
void detachDeadBlocks(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs=false)
Replace contents of every block in BBs with single unreachable instruction.
Definition: BasicBlockUtils.cpp:61
llvm::createPHIsForSplitLoopExit
void createPHIsForSplitLoopExit(ArrayRef< BasicBlock * > Preds, BasicBlock *SplitBB, BasicBlock *DestBB)
When a loop exit edge is split, LCSSA form may require new PHIs in the new exit block.
Definition: BasicBlockUtils.cpp:834
llvm::SplitCriticalEdge
BasicBlock * SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
If this edge is a critical edge, insert a new node to split the critical edge.
Definition: BreakCriticalEdges.cpp:101
llvm::FoldReturnIntoUncondBranch
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...
Definition: BasicBlockUtils.cpp:1415
llvm::CriticalEdgeSplittingOptions::LI
LoopInfo * LI
Definition: BasicBlockUtils.h:147
llvm::CriticalEdgeSplittingOptions::IgnoreUnreachableDests
bool IgnoreUnreachableDests
Definition: BasicBlockUtils.h:152
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::MergeBlockIntoPredecessor
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
Definition: BasicBlockUtils.cpp:179
llvm::CriticalEdgeSplittingOptions::setKeepOneInputPHIs
CriticalEdgeSplittingOptions & setKeepOneInputPHIs()
Definition: BasicBlockUtils.h:169
llvm::SplitKnownCriticalEdge
BasicBlock * SplitKnownCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
If it is known that an edge is critical, SplitKnownCriticalEdge can be called directly,...
Definition: BreakCriticalEdges.cpp:111
llvm::CriticalEdgeSplittingOptions
Option class for critical edge splitting.
Definition: BasicBlockUtils.h:144
llvm::Instruction
Definition: Instruction.h:41
Options
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
Definition: PassBuilderBindings.cpp:48
llvm::SplitBlockAndInsertIfThenElse
void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, Instruction **ThenTerm, Instruction **ElseTerm, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr)
SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, but also creates the ElseBlock...
Definition: BasicBlockUtils.cpp:1563
llvm::SplitBlockPredecessors
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, 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...
Definition: BasicBlockUtils.cpp:1272
llvm::RemoveRedundantDbgInstrs
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
Definition: BasicBlockUtils.cpp:538
llvm::ehAwareSplitEdge
BasicBlock * ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ, LandingPadInst *OriginalPad=nullptr, PHINode *LandingPadReplacement=nullptr, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
Split the edge connect the specficed blocks in the case that Succ is an Exception Handling Block.
Definition: BasicBlockUtils.cpp:686
llvm::EliminateUnreachableBlocks
bool EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete all basic blocks from F that are not reachable from its entry node.
Definition: BasicBlockUtils.cpp:124
llvm::GetIfCondition
BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
Definition: BasicBlockUtils.cpp:1602
BasicBlock.h
llvm::CriticalEdgeSplittingOptions::KeepOneInputPHIs
bool KeepOneInputPHIs
Definition: BasicBlockUtils.h:150
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:835
llvm::CriticalEdgeSplittingOptions::CriticalEdgeSplittingOptions
CriticalEdgeSplittingOptions(DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, PostDominatorTree *PDT=nullptr)
Definition: BasicBlockUtils.h:158
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:54
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::CriticalEdgeSplittingOptions::setMergeIdenticalEdges
CriticalEdgeSplittingOptions & setMergeIdenticalEdges()
Definition: BasicBlockUtils.h:164
llvm::CriticalEdgeSplittingOptions::unsetPreserveLoopSimplify
CriticalEdgeSplittingOptions & unsetPreserveLoopSimplify()
Definition: BasicBlockUtils.h:184
llvm::updatePhiNodes
void updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred, BasicBlock *NewPred, PHINode *Until=nullptr)
Replaces all uses of OldPred with the NewPred block in all PHINodes in a block.
Definition: BasicBlockUtils.cpp:664
ArrayRef.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::CriticalEdgeSplittingOptions::PreserveLCSSA
bool PreserveLCSSA
Definition: BasicBlockUtils.h:151
llvm::SplitIndirectBrCriticalEdges
bool SplitIndirectBrCriticalEdges(Function &F, bool IgnoreBlocksWithoutPHI, BranchProbabilityInfo *BPI=nullptr, BlockFrequencyInfo *BFI=nullptr)
Definition: BreakCriticalEdges.cpp:338
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::CriticalEdgeSplittingOptions::PDT
PostDominatorTree * PDT
Definition: BasicBlockUtils.h:146
llvm::LoopInfo
Definition: LoopInfo.h:1108
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition: PostDominators.h:28
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:433
llvm::CriticalEdgeSplittingOptions::MergeIdenticalEdges
bool MergeIdenticalEdges
Definition: BasicBlockUtils.h:149
llvm::SplitEdge
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
Definition: BasicBlockUtils.cpp:615
llvm::setUnwindEdgeTo
void setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ)
Sets the unwind edge of an instruction to a particular successor.
Definition: BasicBlockUtils.cpp:653
llvm::CriticalEdgeSplittingOptions::setPreserveLCSSA
CriticalEdgeSplittingOptions & setPreserveLCSSA()
Definition: BasicBlockUtils.h:174
llvm::ReplaceInstWithValue
void ReplaceInstWithValue(BasicBlock::iterator &BI, Value *V)
Replace all uses of an instruction (specified by BI) with a value, then remove and delete the origina...
Definition: BasicBlockUtils.cpp:563
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::splitBlockBefore
BasicBlock * splitBlockBefore(BasicBlock *Old, Instruction *SplitPt, DomTreeUpdater *DTU, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName="")
Split the specified block at the specified instruction SplitPt.
Definition: BasicBlockUtils.cpp:950
llvm::FoldSingleEntryPHINodes
bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
Definition: BasicBlockUtils.cpp:144
llvm::DeleteDeadPHIs
bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Examine each PHI in the given block and delete it if it is dead.
Definition: BasicBlockUtils.cpp:163
llvm::CriticalEdgeSplittingOptions::DT
DominatorTree * DT
Definition: BasicBlockUtils.h:145
llvm::SplitAllCriticalEdges
unsigned SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
Loop over all of the edges in the CFG, breaking critical edges as they are found.
Definition: BasicBlockUtils.cpp:866
llvm::IsBlockFollowedByDeoptOrUnreachable
bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
Definition: BasicBlockUtils.cpp:596
llvm::MergeBlockSuccessorsIntoGivenBlocks
bool MergeBlockSuccessorsIntoGivenBlocks(SmallPtrSetImpl< BasicBlock * > &MergeBlocks, Loop *L=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr)
Merge block(s) sucessors, if possible.
Definition: BasicBlockUtils.cpp:338
Dominators.h
llvm::DeleteDeadBlock
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
Definition: BasicBlockUtils.cpp:95
llvm::CriticalEdgeSplittingOptions::setIgnoreUnreachableDests
CriticalEdgeSplittingOptions & setIgnoreUnreachableDests()
Definition: BasicBlockUtils.h:179
llvm::CreateControlFlowHub
BasicBlock * CreateControlFlowHub(DomTreeUpdater *DTU, SmallVectorImpl< BasicBlock * > &GuardBlocks, const SetVector< BasicBlock * > &Predecessors, const SetVector< BasicBlock * > &Successors, const StringRef Prefix, std::optional< unsigned > MaxControlFlowBooleans=std::nullopt)
Given a set of incoming and outgoing blocks, create a "hub" such that every edge from an incoming blo...
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::SplitBlockAndInsertIfThen
Instruction * SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights, DominatorTree *DT, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
Definition: BasicBlockUtils.cpp:1542
llvm::SplitBlock
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
Definition: BasicBlockUtils.cpp:935
llvm::CriticalEdgeSplittingOptions::PreserveLoopSimplify
bool PreserveLoopSimplify
SplitCriticalEdge is guaranteed to preserve loop-simplify form if LI is provided.
Definition: BasicBlockUtils.h:156
llvm::codeview::PublicSymFlags::Function
@ Function
SetVector.h