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