LLVM 17.0.0git
BasicBlockUtils.cpp
Go to the documentation of this file.
1//===- BasicBlockUtils.cpp - BasicBlock Utilities --------------------------==//
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
15#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/Twine.h"
19#include "llvm/Analysis/CFG.h"
24#include "llvm/IR/BasicBlock.h"
25#include "llvm/IR/CFG.h"
26#include "llvm/IR/Constants.h"
27#include "llvm/IR/DebugInfo.h"
29#include "llvm/IR/Dominators.h"
30#include "llvm/IR/Function.h"
31#include "llvm/IR/InstrTypes.h"
32#include "llvm/IR/Instruction.h"
35#include "llvm/IR/LLVMContext.h"
36#include "llvm/IR/Type.h"
37#include "llvm/IR/User.h"
38#include "llvm/IR/Value.h"
39#include "llvm/IR/ValueHandle.h"
42#include "llvm/Support/Debug.h"
45#include <cassert>
46#include <cstdint>
47#include <string>
48#include <utility>
49#include <vector>
50
51using namespace llvm;
52
53#define DEBUG_TYPE "basicblock-utils"
54
56 "max-deopt-or-unreachable-succ-check-depth", cl::init(8), cl::Hidden,
57 cl::desc("Set the maximum path length when checking whether a basic block "
58 "is followed by a block that either has a terminating "
59 "deoptimizing call or is terminated with an unreachable"));
60
64 bool KeepOneInputPHIs) {
65 for (auto *BB : BBs) {
66 // Loop through all of our successors and make sure they know that one
67 // of their predecessors is going away.
68 SmallPtrSet<BasicBlock *, 4> UniqueSuccessors;
69 for (BasicBlock *Succ : successors(BB)) {
70 Succ->removePredecessor(BB, KeepOneInputPHIs);
71 if (Updates && UniqueSuccessors.insert(Succ).second)
72 Updates->push_back({DominatorTree::Delete, BB, Succ});
73 }
74
75 // Zap all the instructions in the block.
76 while (!BB->empty()) {
77 Instruction &I = BB->back();
78 // If this instruction is used, replace uses with an arbitrary value.
79 // Because control flow can't get here, we don't care what we replace the
80 // value with. Note that since this block is unreachable, and all values
81 // contained within it must dominate their uses, that all uses will
82 // eventually be removed (they are themselves dead).
83 if (!I.use_empty())
84 I.replaceAllUsesWith(PoisonValue::get(I.getType()));
85 BB->back().eraseFromParent();
86 }
87 new UnreachableInst(BB->getContext(), BB);
88 assert(BB->size() == 1 &&
89 isa<UnreachableInst>(BB->getTerminator()) &&
90 "The successor list of BB isn't empty before "
91 "applying corresponding DTU updates.");
92 }
93}
94
96 bool KeepOneInputPHIs) {
97 DeleteDeadBlocks({BB}, DTU, KeepOneInputPHIs);
98}
99
100void llvm::DeleteDeadBlocks(ArrayRef <BasicBlock *> BBs, DomTreeUpdater *DTU,
101 bool KeepOneInputPHIs) {
102#ifndef NDEBUG
103 // Make sure that all predecessors of each dead block is also dead.
104 SmallPtrSet<BasicBlock *, 4> Dead(BBs.begin(), BBs.end());
105 assert(Dead.size() == BBs.size() && "Duplicating blocks?");
106 for (auto *BB : Dead)
107 for (BasicBlock *Pred : predecessors(BB))
108 assert(Dead.count(Pred) && "All predecessors must be dead!");
109#endif
110
112 detachDeadBlocks(BBs, DTU ? &Updates : nullptr, KeepOneInputPHIs);
113
114 if (DTU)
115 DTU->applyUpdates(Updates);
116
117 for (BasicBlock *BB : BBs)
118 if (DTU)
119 DTU->deleteBB(BB);
120 else
121 BB->eraseFromParent();
122}
123
125 bool KeepOneInputPHIs) {
127
128 // Mark all reachable blocks.
129 for (BasicBlock *BB : depth_first_ext(&F, Reachable))
130 (void)BB/* Mark all reachable blocks */;
131
132 // Collect all dead blocks.
133 std::vector<BasicBlock*> DeadBlocks;
134 for (BasicBlock &BB : F)
135 if (!Reachable.count(&BB))
136 DeadBlocks.push_back(&BB);
137
138 // Delete the dead blocks.
139 DeleteDeadBlocks(DeadBlocks, DTU, KeepOneInputPHIs);
140
141 return !DeadBlocks.empty();
142}
143
145 MemoryDependenceResults *MemDep) {
146 if (!isa<PHINode>(BB->begin()))
147 return false;
148
149 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
150 if (PN->getIncomingValue(0) != PN)
151 PN->replaceAllUsesWith(PN->getIncomingValue(0));
152 else
153 PN->replaceAllUsesWith(PoisonValue::get(PN->getType()));
154
155 if (MemDep)
156 MemDep->removeInstruction(PN); // Memdep updates AA itself.
157
158 PN->eraseFromParent();
159 }
160 return true;
161}
162
164 MemorySSAUpdater *MSSAU) {
165 // Recursively deleting a PHI may cause multiple PHIs to be deleted
166 // or RAUW'd undef, so use an array of WeakTrackingVH for the PHIs to delete.
168 for (PHINode &PN : BB->phis())
169 PHIs.push_back(&PN);
170
171 bool Changed = false;
172 for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
173 if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*()))
174 Changed |= RecursivelyDeleteDeadPHINode(PN, TLI, MSSAU);
175
176 return Changed;
177}
178
180 LoopInfo *LI, MemorySSAUpdater *MSSAU,
182 bool PredecessorWithTwoSuccessors,
183 DominatorTree *DT) {
184 if (BB->hasAddressTaken())
185 return false;
186
187 // Can't merge if there are multiple predecessors, or no predecessors.
188 BasicBlock *PredBB = BB->getUniquePredecessor();
189 if (!PredBB) return false;
190
191 // Don't break self-loops.
192 if (PredBB == BB) return false;
193
194 // Don't break unwinding instructions or terminators with other side-effects.
195 Instruction *PTI = PredBB->getTerminator();
196 if (PTI->isExceptionalTerminator() || PTI->mayHaveSideEffects())
197 return false;
198
199 // Can't merge if there are multiple distinct successors.
200 if (!PredecessorWithTwoSuccessors && PredBB->getUniqueSuccessor() != BB)
201 return false;
202
203 // Currently only allow PredBB to have two predecessors, one being BB.
204 // Update BI to branch to BB's only successor instead of BB.
205 BranchInst *PredBB_BI;
206 BasicBlock *NewSucc = nullptr;
207 unsigned FallThruPath;
208 if (PredecessorWithTwoSuccessors) {
209 if (!(PredBB_BI = dyn_cast<BranchInst>(PTI)))
210 return false;
211 BranchInst *BB_JmpI = dyn_cast<BranchInst>(BB->getTerminator());
212 if (!BB_JmpI || !BB_JmpI->isUnconditional())
213 return false;
214 NewSucc = BB_JmpI->getSuccessor(0);
215 FallThruPath = PredBB_BI->getSuccessor(0) == BB ? 0 : 1;
216 }
217
218 // Can't merge if there is PHI loop.
219 for (PHINode &PN : BB->phis())
220 if (llvm::is_contained(PN.incoming_values(), &PN))
221 return false;
222
223 LLVM_DEBUG(dbgs() << "Merging: " << BB->getName() << " into "
224 << PredBB->getName() << "\n");
225
226 // Begin by getting rid of unneeded PHIs.
227 SmallVector<AssertingVH<Value>, 4> IncomingValues;
228 if (isa<PHINode>(BB->front())) {
229 for (PHINode &PN : BB->phis())
230 if (!isa<PHINode>(PN.getIncomingValue(0)) ||
231 cast<PHINode>(PN.getIncomingValue(0))->getParent() != BB)
232 IncomingValues.push_back(PN.getIncomingValue(0));
233 FoldSingleEntryPHINodes(BB, MemDep);
234 }
235
236 if (DT) {
237 assert(!DTU && "cannot use both DT and DTU for updates");
238 DomTreeNode *PredNode = DT->getNode(PredBB);
239 DomTreeNode *BBNode = DT->getNode(BB);
240 if (PredNode) {
241 assert(BBNode && "PredNode unreachable but BBNode reachable?");
242 for (DomTreeNode *C : to_vector(BBNode->children()))
243 C->setIDom(PredNode);
244 }
245 }
246 // DTU update: Collect all the edges that exit BB.
247 // These dominator edges will be redirected from Pred.
248 std::vector<DominatorTree::UpdateType> Updates;
249 if (DTU) {
250 assert(!DT && "cannot use both DT and DTU for updates");
251 // To avoid processing the same predecessor more than once.
253 SmallPtrSet<BasicBlock *, 2> SuccsOfPredBB(succ_begin(PredBB),
254 succ_end(PredBB));
255 Updates.reserve(Updates.size() + 2 * succ_size(BB) + 1);
256 // Add insert edges first. Experimentally, for the particular case of two
257 // blocks that can be merged, with a single successor and single predecessor
258 // respectively, it is beneficial to have all insert updates first. Deleting
259 // edges first may lead to unreachable blocks, followed by inserting edges
260 // making the blocks reachable again. Such DT updates lead to high compile
261 // times. We add inserts before deletes here to reduce compile time.
262 for (BasicBlock *SuccOfBB : successors(BB))
263 // This successor of BB may already be a PredBB's successor.
264 if (!SuccsOfPredBB.contains(SuccOfBB))
265 if (SeenSuccs.insert(SuccOfBB).second)
266 Updates.push_back({DominatorTree::Insert, PredBB, SuccOfBB});
267 SeenSuccs.clear();
268 for (BasicBlock *SuccOfBB : successors(BB))
269 if (SeenSuccs.insert(SuccOfBB).second)
270 Updates.push_back({DominatorTree::Delete, BB, SuccOfBB});
271 Updates.push_back({DominatorTree::Delete, PredBB, BB});
272 }
273
274 Instruction *STI = BB->getTerminator();
275 Instruction *Start = &*BB->begin();
276 // If there's nothing to move, mark the starting instruction as the last
277 // instruction in the block. Terminator instruction is handled separately.
278 if (Start == STI)
279 Start = PTI;
280
281 // Move all definitions in the successor to the predecessor...
282 PredBB->splice(PTI->getIterator(), BB, BB->begin(), STI->getIterator());
283
284 if (MSSAU)
285 MSSAU->moveAllAfterMergeBlocks(BB, PredBB, Start);
286
287 // Make all PHI nodes that referred to BB now refer to Pred as their
288 // source...
289 BB->replaceAllUsesWith(PredBB);
290
291 if (PredecessorWithTwoSuccessors) {
292 // Delete the unconditional branch from BB.
293 BB->back().eraseFromParent();
294
295 // Update branch in the predecessor.
296 PredBB_BI->setSuccessor(FallThruPath, NewSucc);
297 } else {
298 // Delete the unconditional branch from the predecessor.
299 PredBB->back().eraseFromParent();
300
301 // Move terminator instruction.
302 PredBB->splice(PredBB->end(), BB);
303
304 // Terminator may be a memory accessing instruction too.
305 if (MSSAU)
306 if (MemoryUseOrDef *MUD = cast_or_null<MemoryUseOrDef>(
307 MSSAU->getMemorySSA()->getMemoryAccess(PredBB->getTerminator())))
308 MSSAU->moveToPlace(MUD, PredBB, MemorySSA::End);
309 }
310 // Add unreachable to now empty BB.
311 new UnreachableInst(BB->getContext(), BB);
312
313 // Inherit predecessors name if it exists.
314 if (!PredBB->hasName())
315 PredBB->takeName(BB);
316
317 if (LI)
318 LI->removeBlock(BB);
319
320 if (MemDep)
322
323 if (DTU)
324 DTU->applyUpdates(Updates);
325
326 if (DT) {
327 assert(succ_empty(BB) &&
328 "successors should have been transferred to PredBB");
329 DT->eraseNode(BB);
330 }
331
332 // Finally, erase the old block and update dominator info.
333 DeleteDeadBlock(BB, DTU);
334
335 return true;
336}
337
340 LoopInfo *LI) {
341 assert(!MergeBlocks.empty() && "MergeBlocks should not be empty");
342
343 bool BlocksHaveBeenMerged = false;
344 while (!MergeBlocks.empty()) {
345 BasicBlock *BB = *MergeBlocks.begin();
346 BasicBlock *Dest = BB->getSingleSuccessor();
347 if (Dest && (!L || L->contains(Dest))) {
348 BasicBlock *Fold = Dest->getUniquePredecessor();
349 (void)Fold;
350 if (MergeBlockIntoPredecessor(Dest, DTU, LI)) {
351 assert(Fold == BB &&
352 "Expecting BB to be unique predecessor of the Dest block");
353 MergeBlocks.erase(Dest);
354 BlocksHaveBeenMerged = true;
355 } else
356 MergeBlocks.erase(BB);
357 } else
358 MergeBlocks.erase(BB);
359 }
360 return BlocksHaveBeenMerged;
361}
362
363/// Remove redundant instructions within sequences of consecutive dbg.value
364/// instructions. This is done using a backward scan to keep the last dbg.value
365/// describing a specific variable/fragment.
366///
367/// BackwardScan strategy:
368/// ----------------------
369/// Given a sequence of consecutive DbgValueInst like this
370///
371/// dbg.value ..., "x", FragmentX1 (*)
372/// dbg.value ..., "y", FragmentY1
373/// dbg.value ..., "x", FragmentX2
374/// dbg.value ..., "x", FragmentX1 (**)
375///
376/// then the instruction marked with (*) can be removed (it is guaranteed to be
377/// obsoleted by the instruction marked with (**) as the latter instruction is
378/// describing the same variable using the same fragment info).
379///
380/// Possible improvements:
381/// - Check fully overlapping fragments and not only identical fragments.
382/// - Support dbg.addr, dbg.declare. dbg.label, and possibly other meta
383/// instructions being part of the sequence of consecutive instructions.
387 for (auto &I : reverse(*BB)) {
388 if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) {
389 DebugVariable Key(DVI->getVariable(),
390 DVI->getExpression(),
391 DVI->getDebugLoc()->getInlinedAt());
392 auto R = VariableSet.insert(Key);
393 // If the variable fragment hasn't been seen before then we don't want
394 // to remove this dbg intrinsic.
395 if (R.second)
396 continue;
397
398 if (auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI)) {
399 // Don't delete dbg.assign intrinsics that are linked to instructions.
400 if (!at::getAssignmentInsts(DAI).empty())
401 continue;
402 // Unlinked dbg.assign intrinsics can be treated like dbg.values.
403 }
404
405 // If the same variable fragment is described more than once it is enough
406 // to keep the last one (i.e. the first found since we for reverse
407 // iteration).
408 ToBeRemoved.push_back(DVI);
409 continue;
410 }
411 // Sequence with consecutive dbg.value instrs ended. Clear the map to
412 // restart identifying redundant instructions if case we find another
413 // dbg.value sequence.
414 VariableSet.clear();
415 }
416
417 for (auto &Instr : ToBeRemoved)
418 Instr->eraseFromParent();
419
420 return !ToBeRemoved.empty();
421}
422
423/// Remove redundant dbg.value instructions using a forward scan. This can
424/// remove a dbg.value instruction that is redundant due to indicating that a
425/// variable has the same value as already being indicated by an earlier
426/// dbg.value.
427///
428/// ForwardScan strategy:
429/// ---------------------
430/// Given two identical dbg.value instructions, separated by a block of
431/// instructions that isn't describing the same variable, like this
432///
433/// dbg.value X1, "x", FragmentX1 (**)
434/// <block of instructions, none being "dbg.value ..., "x", ...">
435/// dbg.value X1, "x", FragmentX1 (*)
436///
437/// then the instruction marked with (*) can be removed. Variable "x" is already
438/// described as being mapped to the SSA value X1.
439///
440/// Possible improvements:
441/// - Keep track of non-overlapping fragments.
445 VariableMap;
446 for (auto &I : *BB) {
447 if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) {
448 DebugVariable Key(DVI->getVariable(), std::nullopt,
449 DVI->getDebugLoc()->getInlinedAt());
450 auto VMI = VariableMap.find(Key);
451 auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI);
452 // A dbg.assign with no linked instructions can be treated like a
453 // dbg.value (i.e. can be deleted).
454 bool IsDbgValueKind = (!DAI || at::getAssignmentInsts(DAI).empty());
455
456 // Update the map if we found a new value/expression describing the
457 // variable, or if the variable wasn't mapped already.
458 SmallVector<Value *, 4> Values(DVI->getValues());
459 if (VMI == VariableMap.end() || VMI->second.first != Values ||
460 VMI->second.second != DVI->getExpression()) {
461 // Use a sentinal value (nullptr) for the DIExpression when we see a
462 // linked dbg.assign so that the next debug intrinsic will never match
463 // it (i.e. always treat linked dbg.assigns as if they're unique).
464 if (IsDbgValueKind)
465 VariableMap[Key] = {Values, DVI->getExpression()};
466 else
467 VariableMap[Key] = {Values, nullptr};
468 continue;
469 }
470
471 // Don't delete dbg.assign intrinsics that are linked to instructions.
472 if (!IsDbgValueKind)
473 continue;
474 ToBeRemoved.push_back(DVI);
475 }
476 }
477
478 for (auto &Instr : ToBeRemoved)
479 Instr->eraseFromParent();
480
481 return !ToBeRemoved.empty();
482}
483
484/// Remove redundant undef dbg.assign intrinsic from an entry block using a
485/// forward scan.
486/// Strategy:
487/// ---------------------
488/// Scanning forward, delete dbg.assign intrinsics iff they are undef, not
489/// linked to an intrinsic, and don't share an aggregate variable with a debug
490/// intrinsic that didn't meet the criteria. In other words, undef dbg.assigns
491/// that come before non-undef debug intrinsics for the variable are
492/// deleted. Given:
493///
494/// dbg.assign undef, "x", FragmentX1 (*)
495/// <block of instructions, none being "dbg.value ..., "x", ...">
496/// dbg.value %V, "x", FragmentX2
497/// <block of instructions, none being "dbg.value ..., "x", ...">
498/// dbg.assign undef, "x", FragmentX1
499///
500/// then (only) the instruction marked with (*) can be removed.
501/// Possible improvements:
502/// - Keep track of non-overlapping fragments.
504 assert(BB->isEntryBlock() && "expected entry block");
506 DenseSet<DebugVariable> SeenDefForAggregate;
507 // Returns the DebugVariable for DVI with no fragment info.
508 auto GetAggregateVariable = [](DbgValueInst *DVI) {
509 return DebugVariable(DVI->getVariable(), std::nullopt,
510 DVI->getDebugLoc()->getInlinedAt());
511 };
512
513 // Remove undef dbg.assign intrinsics that are encountered before
514 // any non-undef intrinsics from the entry block.
515 for (auto &I : *BB) {
516 DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I);
517 if (!DVI)
518 continue;
519 auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI);
520 bool IsDbgValueKind = (!DAI || at::getAssignmentInsts(DAI).empty());
521 DebugVariable Aggregate = GetAggregateVariable(DVI);
522 if (!SeenDefForAggregate.contains(Aggregate)) {
523 bool IsKill = DVI->isKillLocation() && IsDbgValueKind;
524 if (!IsKill) {
525 SeenDefForAggregate.insert(Aggregate);
526 } else if (DAI) {
527 ToBeRemoved.push_back(DAI);
528 }
529 }
530 }
531
532 for (DbgAssignIntrinsic *DAI : ToBeRemoved)
533 DAI->eraseFromParent();
534
535 return !ToBeRemoved.empty();
536}
537
539 bool MadeChanges = false;
540 // By using the "backward scan" strategy before the "forward scan" strategy we
541 // can remove both dbg.value (2) and (3) in a situation like this:
542 //
543 // (1) dbg.value V1, "x", DIExpression()
544 // ...
545 // (2) dbg.value V2, "x", DIExpression()
546 // (3) dbg.value V1, "x", DIExpression()
547 //
548 // The backward scan will remove (2), it is made obsolete by (3). After
549 // getting (2) out of the way, the foward scan will remove (3) since "x"
550 // already is described as having the value V1 at (1).
552 if (BB->isEntryBlock() &&
554 MadeChanges |= remomveUndefDbgAssignsFromEntryBlock(BB);
556
557 if (MadeChanges)
558 LLVM_DEBUG(dbgs() << "Removed redundant dbg instrs from: "
559 << BB->getName() << "\n");
560 return MadeChanges;
561}
562
564 Instruction &I = *BI;
565 // Replaces all of the uses of the instruction with uses of the value
566 I.replaceAllUsesWith(V);
567
568 // Make sure to propagate a name if there is one already.
569 if (I.hasName() && !V->hasName())
570 V->takeName(&I);
571
572 // Delete the unnecessary instruction now...
573 BI = BI->eraseFromParent();
574}
575
577 Instruction *I) {
578 assert(I->getParent() == nullptr &&
579 "ReplaceInstWithInst: Instruction already inserted into basic block!");
580
581 // Copy debug location to newly added instruction, if it wasn't already set
582 // by the caller.
583 if (!I->getDebugLoc())
584 I->setDebugLoc(BI->getDebugLoc());
585
586 // Insert the new instruction into the basic block...
587 BasicBlock::iterator New = I->insertInto(BB, BI);
588
589 // Replace all uses of the old instruction, and delete it.
591
592 // Move BI back to point to the newly inserted instruction
593 BI = New;
594}
595
597 // Remember visited blocks to avoid infinite loop
599 unsigned Depth = 0;
601 VisitedBlocks.insert(BB).second) {
603 isa<UnreachableInst>(BB->getTerminator()))
604 return true;
605 BB = BB->getUniqueSuccessor();
606 }
607 return false;
608}
609
612 ReplaceInstWithInst(From->getParent(), BI, To);
613}
614
616 LoopInfo *LI, MemorySSAUpdater *MSSAU,
617 const Twine &BBName) {
618 unsigned SuccNum = GetSuccessorNumber(BB, Succ);
619
620 Instruction *LatchTerm = BB->getTerminator();
621
624
625 if ((isCriticalEdge(LatchTerm, SuccNum, Options.MergeIdenticalEdges))) {
626 // If it is a critical edge, and the succesor is an exception block, handle
627 // the split edge logic in this specific function
628 if (Succ->isEHPad())
629 return ehAwareSplitEdge(BB, Succ, nullptr, nullptr, Options, BBName);
630
631 // If this is a critical edge, let SplitKnownCriticalEdge do it.
632 return SplitKnownCriticalEdge(LatchTerm, SuccNum, Options, BBName);
633 }
634
635 // If the edge isn't critical, then BB has a single successor or Succ has a
636 // single pred. Split the block.
637 if (BasicBlock *SP = Succ->getSinglePredecessor()) {
638 // If the successor only has a single pred, split the top of the successor
639 // block.
640 assert(SP == BB && "CFG broken");
641 SP = nullptr;
642 return SplitBlock(Succ, &Succ->front(), DT, LI, MSSAU, BBName,
643 /*Before=*/true);
644 }
645
646 // Otherwise, if BB has a single successor, split it at the bottom of the
647 // block.
648 assert(BB->getTerminator()->getNumSuccessors() == 1 &&
649 "Should have a single succ!");
650 return SplitBlock(BB, BB->getTerminator(), DT, LI, MSSAU, BBName);
651}
652
654 if (auto *II = dyn_cast<InvokeInst>(TI))
655 II->setUnwindDest(Succ);
656 else if (auto *CS = dyn_cast<CatchSwitchInst>(TI))
657 CS->setUnwindDest(Succ);
658 else if (auto *CR = dyn_cast<CleanupReturnInst>(TI))
659 CR->setUnwindDest(Succ);
660 else
661 llvm_unreachable("unexpected terminator instruction");
662}
663
665 BasicBlock *NewPred, PHINode *Until) {
666 int BBIdx = 0;
667 for (PHINode &PN : DestBB->phis()) {
668 // We manually update the LandingPadReplacement PHINode and it is the last
669 // PHI Node. So, if we find it, we are done.
670 if (Until == &PN)
671 break;
672
673 // Reuse the previous value of BBIdx if it lines up. In cases where we
674 // have multiple phi nodes with *lots* of predecessors, this is a speed
675 // win because we don't have to scan the PHI looking for TIBB. This
676 // happens because the BB list of PHI nodes are usually in the same
677 // order.
678 if (PN.getIncomingBlock(BBIdx) != OldPred)
679 BBIdx = PN.getBasicBlockIndex(OldPred);
680
681 assert(BBIdx != -1 && "Invalid PHI Index!");
682 PN.setIncomingBlock(BBIdx, NewPred);
683 }
684}
685
687 LandingPadInst *OriginalPad,
688 PHINode *LandingPadReplacement,
690 const Twine &BBName) {
691
692 auto *PadInst = Succ->getFirstNonPHI();
693 if (!LandingPadReplacement && !PadInst->isEHPad())
694 return SplitEdge(BB, Succ, Options.DT, Options.LI, Options.MSSAU, BBName);
695
696 auto *LI = Options.LI;
698 // Check if extra modifications will be required to preserve loop-simplify
699 // form after splitting. If it would require splitting blocks with IndirectBr
700 // terminators, bail out if preserving loop-simplify form is requested.
701 if (Options.PreserveLoopSimplify && LI) {
702 if (Loop *BBLoop = LI->getLoopFor(BB)) {
703
704 // The only way that we can break LoopSimplify form by splitting a
705 // critical edge is when there exists some edge from BBLoop to Succ *and*
706 // the only edge into Succ from outside of BBLoop is that of NewBB after
707 // the split. If the first isn't true, then LoopSimplify still holds,
708 // NewBB is the new exit block and it has no non-loop predecessors. If the
709 // second isn't true, then Succ was not in LoopSimplify form prior to
710 // the split as it had a non-loop predecessor. In both of these cases,
711 // the predecessor must be directly in BBLoop, not in a subloop, or again
712 // LoopSimplify doesn't hold.
713 for (BasicBlock *P : predecessors(Succ)) {
714 if (P == BB)
715 continue; // The new block is known.
716 if (LI->getLoopFor(P) != BBLoop) {
717 // Loop is not in LoopSimplify form, no need to re simplify after
718 // splitting edge.
719 LoopPreds.clear();
720 break;
721 }
722 LoopPreds.push_back(P);
723 }
724 // Loop-simplify form can be preserved, if we can split all in-loop
725 // predecessors.
726 if (any_of(LoopPreds, [](BasicBlock *Pred) {
727 return isa<IndirectBrInst>(Pred->getTerminator());
728 })) {
729 return nullptr;
730 }
731 }
732 }
733
734 auto *NewBB =
735 BasicBlock::Create(BB->getContext(), BBName, BB->getParent(), Succ);
736 setUnwindEdgeTo(BB->getTerminator(), NewBB);
737 updatePhiNodes(Succ, BB, NewBB, LandingPadReplacement);
738
739 if (LandingPadReplacement) {
740 auto *NewLP = OriginalPad->clone();
741 auto *Terminator = BranchInst::Create(Succ, NewBB);
742 NewLP->insertBefore(Terminator);
743 LandingPadReplacement->addIncoming(NewLP, NewBB);
744 } else {
745 Value *ParentPad = nullptr;
746 if (auto *FuncletPad = dyn_cast<FuncletPadInst>(PadInst))
747 ParentPad = FuncletPad->getParentPad();
748 else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(PadInst))
749 ParentPad = CatchSwitch->getParentPad();
750 else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(PadInst))
751 ParentPad = CleanupPad->getParentPad();
752 else if (auto *LandingPad = dyn_cast<LandingPadInst>(PadInst))
753 ParentPad = LandingPad->getParent();
754 else
755 llvm_unreachable("handling for other EHPads not implemented yet");
756
757 auto *NewCleanupPad = CleanupPadInst::Create(ParentPad, {}, BBName, NewBB);
758 CleanupReturnInst::Create(NewCleanupPad, Succ, NewBB);
759 }
760
761 auto *DT = Options.DT;
762 auto *MSSAU = Options.MSSAU;
763 if (!DT && !LI)
764 return NewBB;
765
766 if (DT) {
767 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
769
770 Updates.push_back({DominatorTree::Insert, BB, NewBB});
771 Updates.push_back({DominatorTree::Insert, NewBB, Succ});
772 Updates.push_back({DominatorTree::Delete, BB, Succ});
773
774 DTU.applyUpdates(Updates);
775 DTU.flush();
776
777 if (MSSAU) {
778 MSSAU->applyUpdates(Updates, *DT);
779 if (VerifyMemorySSA)
780 MSSAU->getMemorySSA()->verifyMemorySSA();
781 }
782 }
783
784 if (LI) {
785 if (Loop *BBLoop = LI->getLoopFor(BB)) {
786 // If one or the other blocks were not in a loop, the new block is not
787 // either, and thus LI doesn't need to be updated.
788 if (Loop *SuccLoop = LI->getLoopFor(Succ)) {
789 if (BBLoop == SuccLoop) {
790 // Both in the same loop, the NewBB joins loop.
791 SuccLoop->addBasicBlockToLoop(NewBB, *LI);
792 } else if (BBLoop->contains(SuccLoop)) {
793 // Edge from an outer loop to an inner loop. Add to the outer loop.
794 BBLoop->addBasicBlockToLoop(NewBB, *LI);
795 } else if (SuccLoop->contains(BBLoop)) {
796 // Edge from an inner loop to an outer loop. Add to the outer loop.
797 SuccLoop->addBasicBlockToLoop(NewBB, *LI);
798 } else {
799 // Edge from two loops with no containment relation. Because these
800 // are natural loops, we know that the destination block must be the
801 // header of its loop (adding a branch into a loop elsewhere would
802 // create an irreducible loop).
803 assert(SuccLoop->getHeader() == Succ &&
804 "Should not create irreducible loops!");
805 if (Loop *P = SuccLoop->getParentLoop())
806 P->addBasicBlockToLoop(NewBB, *LI);
807 }
808 }
809
810 // If BB is in a loop and Succ is outside of that loop, we may need to
811 // update LoopSimplify form and LCSSA form.
812 if (!BBLoop->contains(Succ)) {
813 assert(!BBLoop->contains(NewBB) &&
814 "Split point for loop exit is contained in loop!");
815
816 // Update LCSSA form in the newly created exit block.
817 if (Options.PreserveLCSSA) {
818 createPHIsForSplitLoopExit(BB, NewBB, Succ);
819 }
820
821 if (!LoopPreds.empty()) {
823 Succ, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA);
824 if (Options.PreserveLCSSA)
825 createPHIsForSplitLoopExit(LoopPreds, NewExitBB, Succ);
826 }
827 }
828 }
829 }
830
831 return NewBB;
832}
833
835 BasicBlock *SplitBB, BasicBlock *DestBB) {
836 // SplitBB shouldn't have anything non-trivial in it yet.
837 assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() ||
838 SplitBB->isLandingPad()) &&
839 "SplitBB has non-PHI nodes!");
840
841 // For each PHI in the destination block.
842 for (PHINode &PN : DestBB->phis()) {
843 int Idx = PN.getBasicBlockIndex(SplitBB);
844 assert(Idx >= 0 && "Invalid Block Index");
845 Value *V = PN.getIncomingValue(Idx);
846
847 // If the input is a PHI which already satisfies LCSSA, don't create
848 // a new one.
849 if (const PHINode *VP = dyn_cast<PHINode>(V))
850 if (VP->getParent() == SplitBB)
851 continue;
852
853 // Otherwise a new PHI is needed. Create one and populate it.
854 PHINode *NewPN = PHINode::Create(
855 PN.getType(), Preds.size(), "split",
856 SplitBB->isLandingPad() ? &SplitBB->front() : SplitBB->getTerminator());
857 for (BasicBlock *BB : Preds)
858 NewPN->addIncoming(V, BB);
859
860 // Update the original PHI.
861 PN.setIncomingValue(Idx, NewPN);
862 }
863}
864
865unsigned
868 unsigned NumBroken = 0;
869 for (BasicBlock &BB : F) {
870 Instruction *TI = BB.getTerminator();
871 if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI))
872 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
873 if (SplitCriticalEdge(TI, i, Options))
874 ++NumBroken;
875 }
876 return NumBroken;
877}
878
881 LoopInfo *LI, MemorySSAUpdater *MSSAU,
882 const Twine &BBName, bool Before) {
883 if (Before) {
884 DomTreeUpdater LocalDTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
885 return splitBlockBefore(Old, SplitPt,
886 DTU ? DTU : (DT ? &LocalDTU : nullptr), LI, MSSAU,
887 BBName);
888 }
889 BasicBlock::iterator SplitIt = SplitPt->getIterator();
890 while (isa<PHINode>(SplitIt) || SplitIt->isEHPad()) {
891 ++SplitIt;
892 assert(SplitIt != SplitPt->getParent()->end());
893 }
894 std::string Name = BBName.str();
895 BasicBlock *New = Old->splitBasicBlock(
896 SplitIt, Name.empty() ? Old->getName() + ".split" : Name);
897
898 // The new block lives in whichever loop the old one did. This preserves
899 // LCSSA as well, because we force the split point to be after any PHI nodes.
900 if (LI)
901 if (Loop *L = LI->getLoopFor(Old))
902 L->addBasicBlockToLoop(New, *LI);
903
904 if (DTU) {
906 // Old dominates New. New node dominates all other nodes dominated by Old.
907 SmallPtrSet<BasicBlock *, 8> UniqueSuccessorsOfOld;
908 Updates.push_back({DominatorTree::Insert, Old, New});
909 Updates.reserve(Updates.size() + 2 * succ_size(New));
910 for (BasicBlock *SuccessorOfOld : successors(New))
911 if (UniqueSuccessorsOfOld.insert(SuccessorOfOld).second) {
912 Updates.push_back({DominatorTree::Insert, New, SuccessorOfOld});
913 Updates.push_back({DominatorTree::Delete, Old, SuccessorOfOld});
914 }
915
916 DTU->applyUpdates(Updates);
917 } else if (DT)
918 // Old dominates New. New node dominates all other nodes dominated by Old.
919 if (DomTreeNode *OldNode = DT->getNode(Old)) {
920 std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
921
922 DomTreeNode *NewNode = DT->addNewBlock(New, Old);
923 for (DomTreeNode *I : Children)
924 DT->changeImmediateDominator(I, NewNode);
925 }
926
927 // Move MemoryAccesses still tracked in Old, but part of New now.
928 // Update accesses in successor blocks accordingly.
929 if (MSSAU)
930 MSSAU->moveAllAfterSpliceBlocks(Old, New, &*(New->begin()));
931
932 return New;
933}
934
936 DominatorTree *DT, LoopInfo *LI,
937 MemorySSAUpdater *MSSAU, const Twine &BBName,
938 bool Before) {
939 return SplitBlockImpl(Old, SplitPt, /*DTU=*/nullptr, DT, LI, MSSAU, BBName,
940 Before);
941}
943 DomTreeUpdater *DTU, LoopInfo *LI,
944 MemorySSAUpdater *MSSAU, const Twine &BBName,
945 bool Before) {
946 return SplitBlockImpl(Old, SplitPt, DTU, /*DT=*/nullptr, LI, MSSAU, BBName,
947 Before);
948}
949
951 DomTreeUpdater *DTU, LoopInfo *LI,
952 MemorySSAUpdater *MSSAU,
953 const Twine &BBName) {
954
955 BasicBlock::iterator SplitIt = SplitPt->getIterator();
956 while (isa<PHINode>(SplitIt) || SplitIt->isEHPad())
957 ++SplitIt;
958 std::string Name = BBName.str();
959 BasicBlock *New = Old->splitBasicBlock(
960 SplitIt, Name.empty() ? Old->getName() + ".split" : Name,
961 /* Before=*/true);
962
963 // The new block lives in whichever loop the old one did. This preserves
964 // LCSSA as well, because we force the split point to be after any PHI nodes.
965 if (LI)
966 if (Loop *L = LI->getLoopFor(Old))
967 L->addBasicBlockToLoop(New, *LI);
968
969 if (DTU) {
971 // New dominates Old. The predecessor nodes of the Old node dominate
972 // New node.
973 SmallPtrSet<BasicBlock *, 8> UniquePredecessorsOfOld;
974 DTUpdates.push_back({DominatorTree::Insert, New, Old});
975 DTUpdates.reserve(DTUpdates.size() + 2 * pred_size(New));
976 for (BasicBlock *PredecessorOfOld : predecessors(New))
977 if (UniquePredecessorsOfOld.insert(PredecessorOfOld).second) {
978 DTUpdates.push_back({DominatorTree::Insert, PredecessorOfOld, New});
979 DTUpdates.push_back({DominatorTree::Delete, PredecessorOfOld, Old});
980 }
981
982 DTU->applyUpdates(DTUpdates);
983
984 // Move MemoryAccesses still tracked in Old, but part of New now.
985 // Update accesses in successor blocks accordingly.
986 if (MSSAU) {
987 MSSAU->applyUpdates(DTUpdates, DTU->getDomTree());
988 if (VerifyMemorySSA)
989 MSSAU->getMemorySSA()->verifyMemorySSA();
990 }
991 }
992 return New;
993}
994
995/// Update DominatorTree, LoopInfo, and LCCSA analysis information.
999 LoopInfo *LI, MemorySSAUpdater *MSSAU,
1000 bool PreserveLCSSA, bool &HasLoopExit) {
1001 // Update dominator tree if available.
1002 if (DTU) {
1003 // Recalculation of DomTree is needed when updating a forward DomTree and
1004 // the Entry BB is replaced.
1005 if (NewBB->isEntryBlock() && DTU->hasDomTree()) {
1006 // The entry block was removed and there is no external interface for
1007 // the dominator tree to be notified of this change. In this corner-case
1008 // we recalculate the entire tree.
1009 DTU->recalculate(*NewBB->getParent());
1010 } else {
1011 // Split block expects NewBB to have a non-empty set of predecessors.
1013 SmallPtrSet<BasicBlock *, 8> UniquePreds;
1014 Updates.push_back({DominatorTree::Insert, NewBB, OldBB});
1015 Updates.reserve(Updates.size() + 2 * Preds.size());
1016 for (auto *Pred : Preds)
1017 if (UniquePreds.insert(Pred).second) {
1018 Updates.push_back({DominatorTree::Insert, Pred, NewBB});
1019 Updates.push_back({DominatorTree::Delete, Pred, OldBB});
1020 }
1021 DTU->applyUpdates(Updates);
1022 }
1023 } else if (DT) {
1024 if (OldBB == DT->getRootNode()->getBlock()) {
1025 assert(NewBB->isEntryBlock());
1026 DT->setNewRoot(NewBB);
1027 } else {
1028 // Split block expects NewBB to have a non-empty set of predecessors.
1029 DT->splitBlock(NewBB);
1030 }
1031 }
1032
1033 // Update MemoryPhis after split if MemorySSA is available
1034 if (MSSAU)
1035 MSSAU->wireOldPredecessorsToNewImmediatePredecessor(OldBB, NewBB, Preds);
1036
1037 // The rest of the logic is only relevant for updating the loop structures.
1038 if (!LI)
1039 return;
1040
1041 if (DTU && DTU->hasDomTree())
1042 DT = &DTU->getDomTree();
1043 assert(DT && "DT should be available to update LoopInfo!");
1044 Loop *L = LI->getLoopFor(OldBB);
1045
1046 // If we need to preserve loop analyses, collect some information about how
1047 // this split will affect loops.
1048 bool IsLoopEntry = !!L;
1049 bool SplitMakesNewLoopHeader = false;
1050 for (BasicBlock *Pred : Preds) {
1051 // Preds that are not reachable from entry should not be used to identify if
1052 // OldBB is a loop entry or if SplitMakesNewLoopHeader. Unreachable blocks
1053 // are not within any loops, so we incorrectly mark SplitMakesNewLoopHeader
1054 // as true and make the NewBB the header of some loop. This breaks LI.
1055 if (!DT->isReachableFromEntry(Pred))
1056 continue;
1057 // If we need to preserve LCSSA, determine if any of the preds is a loop
1058 // exit.
1059 if (PreserveLCSSA)
1060 if (Loop *PL = LI->getLoopFor(Pred))
1061 if (!PL->contains(OldBB))
1062 HasLoopExit = true;
1063
1064 // If we need to preserve LoopInfo, note whether any of the preds crosses
1065 // an interesting loop boundary.
1066 if (!L)
1067 continue;
1068 if (L->contains(Pred))
1069 IsLoopEntry = false;
1070 else
1071 SplitMakesNewLoopHeader = true;
1072 }
1073
1074 // Unless we have a loop for OldBB, nothing else to do here.
1075 if (!L)
1076 return;
1077
1078 if (IsLoopEntry) {
1079 // Add the new block to the nearest enclosing loop (and not an adjacent
1080 // loop). To find this, examine each of the predecessors and determine which
1081 // loops enclose them, and select the most-nested loop which contains the
1082 // loop containing the block being split.
1083 Loop *InnermostPredLoop = nullptr;
1084 for (BasicBlock *Pred : Preds) {
1085 if (Loop *PredLoop = LI->getLoopFor(Pred)) {
1086 // Seek a loop which actually contains the block being split (to avoid
1087 // adjacent loops).
1088 while (PredLoop && !PredLoop->contains(OldBB))
1089 PredLoop = PredLoop->getParentLoop();
1090
1091 // Select the most-nested of these loops which contains the block.
1092 if (PredLoop && PredLoop->contains(OldBB) &&
1093 (!InnermostPredLoop ||
1094 InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth()))
1095 InnermostPredLoop = PredLoop;
1096 }
1097 }
1098
1099 if (InnermostPredLoop)
1100 InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI);
1101 } else {
1102 L->addBasicBlockToLoop(NewBB, *LI);
1103 if (SplitMakesNewLoopHeader)
1104 L->moveToHeader(NewBB);
1105 }
1106}
1107
1108/// Update the PHI nodes in OrigBB to include the values coming from NewBB.
1109/// This also updates AliasAnalysis, if available.
1110static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB,
1112 bool HasLoopExit) {
1113 // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB.
1114 SmallPtrSet<BasicBlock *, 16> PredSet(Preds.begin(), Preds.end());
1115 for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) {
1116 PHINode *PN = cast<PHINode>(I++);
1117
1118 // Check to see if all of the values coming in are the same. If so, we
1119 // don't need to create a new PHI node, unless it's needed for LCSSA.
1120 Value *InVal = nullptr;
1121 if (!HasLoopExit) {
1122 InVal = PN->getIncomingValueForBlock(Preds[0]);
1123 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1124 if (!PredSet.count(PN->getIncomingBlock(i)))
1125 continue;
1126 if (!InVal)
1127 InVal = PN->getIncomingValue(i);
1128 else if (InVal != PN->getIncomingValue(i)) {
1129 InVal = nullptr;
1130 break;
1131 }
1132 }
1133 }
1134
1135 if (InVal) {
1136 // If all incoming values for the new PHI would be the same, just don't
1137 // make a new PHI. Instead, just remove the incoming values from the old
1138 // PHI.
1139
1140 // NOTE! This loop walks backwards for a reason! First off, this minimizes
1141 // the cost of removal if we end up removing a large number of values, and
1142 // second off, this ensures that the indices for the incoming values
1143 // aren't invalidated when we remove one.
1144 for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i)
1145 if (PredSet.count(PN->getIncomingBlock(i)))
1146 PN->removeIncomingValue(i, false);
1147
1148 // Add an incoming value to the PHI node in the loop for the preheader
1149 // edge.
1150 PN->addIncoming(InVal, NewBB);
1151 continue;
1152 }
1153
1154 // If the values coming into the block are not the same, we need a new
1155 // PHI.
1156 // Create the new PHI node, insert it into NewBB at the end of the block
1157 PHINode *NewPHI =
1158 PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI);
1159
1160 // NOTE! This loop walks backwards for a reason! First off, this minimizes
1161 // the cost of removal if we end up removing a large number of values, and
1162 // second off, this ensures that the indices for the incoming values aren't
1163 // invalidated when we remove one.
1164 for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) {
1165 BasicBlock *IncomingBB = PN->getIncomingBlock(i);
1166 if (PredSet.count(IncomingBB)) {
1167 Value *V = PN->removeIncomingValue(i, false);
1168 NewPHI->addIncoming(V, IncomingBB);
1169 }
1170 }
1171
1172 PN->addIncoming(NewPHI, NewBB);
1173 }
1174}
1175
1177 BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix1,
1178 const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs,
1179 DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI,
1180 MemorySSAUpdater *MSSAU, bool PreserveLCSSA);
1181
1182static BasicBlock *
1184 const char *Suffix, DomTreeUpdater *DTU,
1185 DominatorTree *DT, LoopInfo *LI,
1186 MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
1187 // Do not attempt to split that which cannot be split.
1188 if (!BB->canSplitPredecessors())
1189 return nullptr;
1190
1191 // For the landingpads we need to act a bit differently.
1192 // Delegate this work to the SplitLandingPadPredecessors.
1193 if (BB->isLandingPad()) {
1195 std::string NewName = std::string(Suffix) + ".split-lp";
1196
1197 SplitLandingPadPredecessorsImpl(BB, Preds, Suffix, NewName.c_str(), NewBBs,
1198 DTU, DT, LI, MSSAU, PreserveLCSSA);
1199 return NewBBs[0];
1200 }
1201
1202 // Create new basic block, insert right before the original block.
1204 BB->getContext(), BB->getName() + Suffix, BB->getParent(), BB);
1205
1206 // The new block unconditionally branches to the old block.
1207 BranchInst *BI = BranchInst::Create(BB, NewBB);
1208
1209 Loop *L = nullptr;
1210 BasicBlock *OldLatch = nullptr;
1211 // Splitting the predecessors of a loop header creates a preheader block.
1212 if (LI && LI->isLoopHeader(BB)) {
1213 L = LI->getLoopFor(BB);
1214 // Using the loop start line number prevents debuggers stepping into the
1215 // loop body for this instruction.
1216 BI->setDebugLoc(L->getStartLoc());
1217
1218 // If BB is the header of the Loop, it is possible that the loop is
1219 // modified, such that the current latch does not remain the latch of the
1220 // loop. If that is the case, the loop metadata from the current latch needs
1221 // to be applied to the new latch.
1222 OldLatch = L->getLoopLatch();
1223 } else
1225
1226 // Move the edges from Preds to point to NewBB instead of BB.
1227 for (BasicBlock *Pred : Preds) {
1228 // This is slightly more strict than necessary; the minimum requirement
1229 // is that there be no more than one indirectbr branching to BB. And
1230 // all BlockAddress uses would need to be updated.
1231 assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
1232 "Cannot split an edge from an IndirectBrInst");
1233 Pred->getTerminator()->replaceSuccessorWith(BB, NewBB);
1234 }
1235
1236 // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
1237 // node becomes an incoming value for BB's phi node. However, if the Preds
1238 // list is empty, we need to insert dummy entries into the PHI nodes in BB to
1239 // account for the newly created predecessor.
1240 if (Preds.empty()) {
1241 // Insert dummy values as the incoming value.
1242 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I)
1243 cast<PHINode>(I)->addIncoming(PoisonValue::get(I->getType()), NewBB);
1244 }
1245
1246 // Update DominatorTree, LoopInfo, and LCCSA analysis information.
1247 bool HasLoopExit = false;
1248 UpdateAnalysisInformation(BB, NewBB, Preds, DTU, DT, LI, MSSAU, PreserveLCSSA,
1249 HasLoopExit);
1250
1251 if (!Preds.empty()) {
1252 // Update the PHI nodes in BB with the values coming from NewBB.
1253 UpdatePHINodes(BB, NewBB, Preds, BI, HasLoopExit);
1254 }
1255
1256 if (OldLatch) {
1257 BasicBlock *NewLatch = L->getLoopLatch();
1258 if (NewLatch != OldLatch) {
1259 MDNode *MD = OldLatch->getTerminator()->getMetadata("llvm.loop");
1260 NewLatch->getTerminator()->setMetadata("llvm.loop", MD);
1261 // It's still possible that OldLatch is the latch of another inner loop,
1262 // in which case we do not remove the metadata.
1263 Loop *IL = LI->getLoopFor(OldLatch);
1264 if (IL && IL->getLoopLatch() != OldLatch)
1265 OldLatch->getTerminator()->setMetadata("llvm.loop", nullptr);
1266 }
1267 }
1268
1269 return NewBB;
1270}
1271
1274 const char *Suffix, DominatorTree *DT,
1275 LoopInfo *LI, MemorySSAUpdater *MSSAU,
1276 bool PreserveLCSSA) {
1277 return SplitBlockPredecessorsImpl(BB, Preds, Suffix, /*DTU=*/nullptr, DT, LI,
1278 MSSAU, PreserveLCSSA);
1279}
1282 const char *Suffix,
1283 DomTreeUpdater *DTU, LoopInfo *LI,
1284 MemorySSAUpdater *MSSAU,
1285 bool PreserveLCSSA) {
1286 return SplitBlockPredecessorsImpl(BB, Preds, Suffix, DTU,
1287 /*DT=*/nullptr, LI, MSSAU, PreserveLCSSA);
1288}
1289
1291 BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix1,
1292 const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs,
1293 DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI,
1294 MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
1295 assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!");
1296
1297 // Create a new basic block for OrigBB's predecessors listed in Preds. Insert
1298 // it right before the original block.
1299 BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(),
1300 OrigBB->getName() + Suffix1,
1301 OrigBB->getParent(), OrigBB);
1302 NewBBs.push_back(NewBB1);
1303
1304 // The new block unconditionally branches to the old block.
1305 BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1);
1306 BI1->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
1307
1308 // Move the edges from Preds to point to NewBB1 instead of OrigBB.
1309 for (BasicBlock *Pred : Preds) {
1310 // This is slightly more strict than necessary; the minimum requirement
1311 // is that there be no more than one indirectbr branching to BB. And
1312 // all BlockAddress uses would need to be updated.
1313 assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
1314 "Cannot split an edge from an IndirectBrInst");
1315 Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
1316 }
1317
1318 bool HasLoopExit = false;
1319 UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DTU, DT, LI, MSSAU,
1320 PreserveLCSSA, HasLoopExit);
1321
1322 // Update the PHI nodes in OrigBB with the values coming from NewBB1.
1323 UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, HasLoopExit);
1324
1325 // Move the remaining edges from OrigBB to point to NewBB2.
1326 SmallVector<BasicBlock*, 8> NewBB2Preds;
1327 for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB);
1328 i != e; ) {
1329 BasicBlock *Pred = *i++;
1330 if (Pred == NewBB1) continue;
1331 assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
1332 "Cannot split an edge from an IndirectBrInst");
1333 NewBB2Preds.push_back(Pred);
1334 e = pred_end(OrigBB);
1335 }
1336
1337 BasicBlock *NewBB2 = nullptr;
1338 if (!NewBB2Preds.empty()) {
1339 // Create another basic block for the rest of OrigBB's predecessors.
1340 NewBB2 = BasicBlock::Create(OrigBB->getContext(),
1341 OrigBB->getName() + Suffix2,
1342 OrigBB->getParent(), OrigBB);
1343 NewBBs.push_back(NewBB2);
1344
1345 // The new block unconditionally branches to the old block.
1346 BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2);
1347 BI2->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
1348
1349 // Move the remaining edges from OrigBB to point to NewBB2.
1350 for (BasicBlock *NewBB2Pred : NewBB2Preds)
1351 NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
1352
1353 // Update DominatorTree, LoopInfo, and LCCSA analysis information.
1354 HasLoopExit = false;
1355 UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DTU, DT, LI, MSSAU,
1356 PreserveLCSSA, HasLoopExit);
1357
1358 // Update the PHI nodes in OrigBB with the values coming from NewBB2.
1359 UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, HasLoopExit);
1360 }
1361
1362 LandingPadInst *LPad = OrigBB->getLandingPadInst();
1363 Instruction *Clone1 = LPad->clone();
1364 Clone1->setName(Twine("lpad") + Suffix1);
1365 Clone1->insertInto(NewBB1, NewBB1->getFirstInsertionPt());
1366
1367 if (NewBB2) {
1368 Instruction *Clone2 = LPad->clone();
1369 Clone2->setName(Twine("lpad") + Suffix2);
1370 Clone2->insertInto(NewBB2, NewBB2->getFirstInsertionPt());
1371
1372 // Create a PHI node for the two cloned landingpad instructions only
1373 // if the original landingpad instruction has some uses.
1374 if (!LPad->use_empty()) {
1375 assert(!LPad->getType()->isTokenTy() &&
1376 "Split cannot be applied if LPad is token type. Otherwise an "
1377 "invalid PHINode of token type would be created.");
1378 PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad);
1379 PN->addIncoming(Clone1, NewBB1);
1380 PN->addIncoming(Clone2, NewBB2);
1381 LPad->replaceAllUsesWith(PN);
1382 }
1383 LPad->eraseFromParent();
1384 } else {
1385 // There is no second clone. Just replace the landing pad with the first
1386 // clone.
1387 LPad->replaceAllUsesWith(Clone1);
1388 LPad->eraseFromParent();
1389 }
1390}
1391
1394 const char *Suffix1, const char *Suffix2,
1396 DominatorTree *DT, LoopInfo *LI,
1397 MemorySSAUpdater *MSSAU,
1398 bool PreserveLCSSA) {
1400 OrigBB, Preds, Suffix1, Suffix2, NewBBs,
1401 /*DTU=*/nullptr, DT, LI, MSSAU, PreserveLCSSA);
1402}
1405 const char *Suffix1, const char *Suffix2,
1407 DomTreeUpdater *DTU, LoopInfo *LI,
1408 MemorySSAUpdater *MSSAU,
1409 bool PreserveLCSSA) {
1410 return SplitLandingPadPredecessorsImpl(OrigBB, Preds, Suffix1, Suffix2,
1411 NewBBs, DTU, /*DT=*/nullptr, LI, MSSAU,
1412 PreserveLCSSA);
1413}
1414
1416 BasicBlock *Pred,
1417 DomTreeUpdater *DTU) {
1418 Instruction *UncondBranch = Pred->getTerminator();
1419 // Clone the return and add it to the end of the predecessor.
1420 Instruction *NewRet = RI->clone();
1421 NewRet->insertInto(Pred, Pred->end());
1422
1423 // If the return instruction returns a value, and if the value was a
1424 // PHI node in "BB", propagate the right value into the return.
1425 for (Use &Op : NewRet->operands()) {
1426 Value *V = Op;
1427 Instruction *NewBC = nullptr;
1428 if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
1429 // Return value might be bitcasted. Clone and insert it before the
1430 // return instruction.
1431 V = BCI->getOperand(0);
1432 NewBC = BCI->clone();
1433 NewBC->insertInto(Pred, NewRet->getIterator());
1434 Op = NewBC;
1435 }
1436
1437 Instruction *NewEV = nullptr;
1438 if (ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(V)) {
1439 V = EVI->getOperand(0);
1440 NewEV = EVI->clone();
1441 if (NewBC) {
1442 NewBC->setOperand(0, NewEV);
1443 NewEV->insertInto(Pred, NewBC->getIterator());
1444 } else {
1445 NewEV->insertInto(Pred, NewRet->getIterator());
1446 Op = NewEV;
1447 }
1448 }
1449
1450 if (PHINode *PN = dyn_cast<PHINode>(V)) {
1451 if (PN->getParent() == BB) {
1452 if (NewEV) {
1453 NewEV->setOperand(0, PN->getIncomingValueForBlock(Pred));
1454 } else if (NewBC)
1455 NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred));
1456 else
1457 Op = PN->getIncomingValueForBlock(Pred);
1458 }
1459 }
1460 }
1461
1462 // Update any PHI nodes in the returning block to realize that we no
1463 // longer branch to them.
1464 BB->removePredecessor(Pred);
1465 UncondBranch->eraseFromParent();
1466
1467 if (DTU)
1468 DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}});
1469
1470 return cast<ReturnInst>(NewRet);
1471}
1472
1473static Instruction *
1475 bool Unreachable, MDNode *BranchWeights,
1476 DomTreeUpdater *DTU, DominatorTree *DT,
1477 LoopInfo *LI, BasicBlock *ThenBlock) {
1479 BasicBlock *Head = SplitBefore->getParent();
1480 BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
1481 if (DTU) {
1482 SmallPtrSet<BasicBlock *, 8> UniqueSuccessorsOfHead;
1483 Updates.push_back({DominatorTree::Insert, Head, Tail});
1484 Updates.reserve(Updates.size() + 2 * succ_size(Tail));
1485 for (BasicBlock *SuccessorOfHead : successors(Tail))
1486 if (UniqueSuccessorsOfHead.insert(SuccessorOfHead).second) {
1487 Updates.push_back({DominatorTree::Insert, Tail, SuccessorOfHead});
1488 Updates.push_back({DominatorTree::Delete, Head, SuccessorOfHead});
1489 }
1490 }
1491 Instruction *HeadOldTerm = Head->getTerminator();
1492 LLVMContext &C = Head->getContext();
1493 Instruction *CheckTerm;
1494 bool CreateThenBlock = (ThenBlock == nullptr);
1495 if (CreateThenBlock) {
1496 ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
1497 if (Unreachable)
1498 CheckTerm = new UnreachableInst(C, ThenBlock);
1499 else {
1500 CheckTerm = BranchInst::Create(Tail, ThenBlock);
1501 if (DTU)
1502 Updates.push_back({DominatorTree::Insert, ThenBlock, Tail});
1503 }
1504 CheckTerm->setDebugLoc(SplitBefore->getDebugLoc());
1505 } else
1506 CheckTerm = ThenBlock->getTerminator();
1507 BranchInst *HeadNewTerm =
1508 BranchInst::Create(/*ifTrue*/ ThenBlock, /*ifFalse*/ Tail, Cond);
1509 if (DTU)
1510 Updates.push_back({DominatorTree::Insert, Head, ThenBlock});
1511 HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
1512 ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
1513
1514 if (DTU)
1515 DTU->applyUpdates(Updates);
1516 else if (DT) {
1517 if (DomTreeNode *OldNode = DT->getNode(Head)) {
1518 std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
1519
1520 DomTreeNode *NewNode = DT->addNewBlock(Tail, Head);
1521 for (DomTreeNode *Child : Children)
1522 DT->changeImmediateDominator(Child, NewNode);
1523
1524 // Head dominates ThenBlock.
1525 if (CreateThenBlock)
1526 DT->addNewBlock(ThenBlock, Head);
1527 else
1528 DT->changeImmediateDominator(ThenBlock, Head);
1529 }
1530 }
1531
1532 if (LI) {
1533 if (Loop *L = LI->getLoopFor(Head)) {
1534 L->addBasicBlockToLoop(ThenBlock, *LI);
1535 L->addBasicBlockToLoop(Tail, *LI);
1536 }
1537 }
1538
1539 return CheckTerm;
1540}
1541
1543 Instruction *SplitBefore,
1544 bool Unreachable,
1545 MDNode *BranchWeights,
1546 DominatorTree *DT, LoopInfo *LI,
1547 BasicBlock *ThenBlock) {
1548 return SplitBlockAndInsertIfThenImpl(Cond, SplitBefore, Unreachable,
1549 BranchWeights,
1550 /*DTU=*/nullptr, DT, LI, ThenBlock);
1551}
1553 Instruction *SplitBefore,
1554 bool Unreachable,
1555 MDNode *BranchWeights,
1556 DomTreeUpdater *DTU, LoopInfo *LI,
1557 BasicBlock *ThenBlock) {
1558 return SplitBlockAndInsertIfThenImpl(Cond, SplitBefore, Unreachable,
1559 BranchWeights, DTU, /*DT=*/nullptr, LI,
1560 ThenBlock);
1561}
1562
1564 Instruction **ThenTerm,
1565 Instruction **ElseTerm,
1566 MDNode *BranchWeights,
1567 DomTreeUpdater *DTU) {
1568 BasicBlock *Head = SplitBefore->getParent();
1569
1570 SmallPtrSet<BasicBlock *, 8> UniqueOrigSuccessors;
1571 if (DTU)
1572 UniqueOrigSuccessors.insert(succ_begin(Head), succ_end(Head));
1573
1574 BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
1575 Instruction *HeadOldTerm = Head->getTerminator();
1576 LLVMContext &C = Head->getContext();
1577 BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
1578 BasicBlock *ElseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
1579 *ThenTerm = BranchInst::Create(Tail, ThenBlock);
1580 (*ThenTerm)->setDebugLoc(SplitBefore->getDebugLoc());
1581 *ElseTerm = BranchInst::Create(Tail, ElseBlock);
1582 (*ElseTerm)->setDebugLoc(SplitBefore->getDebugLoc());
1583 BranchInst *HeadNewTerm =
1584 BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/ElseBlock, Cond);
1585 HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
1586 ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
1587 if (DTU) {
1589 Updates.reserve(4 + 2 * UniqueOrigSuccessors.size());
1590 for (BasicBlock *Succ : successors(Head)) {
1591 Updates.push_back({DominatorTree::Insert, Head, Succ});
1592 Updates.push_back({DominatorTree::Insert, Succ, Tail});
1593 }
1594 for (BasicBlock *UniqueOrigSuccessor : UniqueOrigSuccessors)
1595 Updates.push_back({DominatorTree::Insert, Tail, UniqueOrigSuccessor});
1596 for (BasicBlock *UniqueOrigSuccessor : UniqueOrigSuccessors)
1597 Updates.push_back({DominatorTree::Delete, Head, UniqueOrigSuccessor});
1598 DTU->applyUpdates(Updates);
1599 }
1600}
1601
1603 BasicBlock *&IfFalse) {
1604 PHINode *SomePHI = dyn_cast<PHINode>(BB->begin());
1605 BasicBlock *Pred1 = nullptr;
1606 BasicBlock *Pred2 = nullptr;
1607
1608 if (SomePHI) {
1609 if (SomePHI->getNumIncomingValues() != 2)
1610 return nullptr;
1611 Pred1 = SomePHI->getIncomingBlock(0);
1612 Pred2 = SomePHI->getIncomingBlock(1);
1613 } else {
1614 pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1615 if (PI == PE) // No predecessor
1616 return nullptr;
1617 Pred1 = *PI++;
1618 if (PI == PE) // Only one predecessor
1619 return nullptr;
1620 Pred2 = *PI++;
1621 if (PI != PE) // More than two predecessors
1622 return nullptr;
1623 }
1624
1625 // We can only handle branches. Other control flow will be lowered to
1626 // branches if possible anyway.
1627 BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator());
1628 BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator());
1629 if (!Pred1Br || !Pred2Br)
1630 return nullptr;
1631
1632 // Eliminate code duplication by ensuring that Pred1Br is conditional if
1633 // either are.
1634 if (Pred2Br->isConditional()) {
1635 // If both branches are conditional, we don't have an "if statement". In
1636 // reality, we could transform this case, but since the condition will be
1637 // required anyway, we stand no chance of eliminating it, so the xform is
1638 // probably not profitable.
1639 if (Pred1Br->isConditional())
1640 return nullptr;
1641
1642 std::swap(Pred1, Pred2);
1643 std::swap(Pred1Br, Pred2Br);
1644 }
1645
1646 if (Pred1Br->isConditional()) {
1647 // The only thing we have to watch out for here is to make sure that Pred2
1648 // doesn't have incoming edges from other blocks. If it does, the condition
1649 // doesn't dominate BB.
1650 if (!Pred2->getSinglePredecessor())
1651 return nullptr;
1652
1653 // If we found a conditional branch predecessor, make sure that it branches
1654 // to BB and Pred2Br. If it doesn't, this isn't an "if statement".
1655 if (Pred1Br->getSuccessor(0) == BB &&
1656 Pred1Br->getSuccessor(1) == Pred2) {
1657 IfTrue = Pred1;
1658 IfFalse = Pred2;
1659 } else if (Pred1Br->getSuccessor(0) == Pred2 &&
1660 Pred1Br->getSuccessor(1) == BB) {
1661 IfTrue = Pred2;
1662 IfFalse = Pred1;
1663 } else {
1664 // We know that one arm of the conditional goes to BB, so the other must
1665 // go somewhere unrelated, and this must not be an "if statement".
1666 return nullptr;
1667 }
1668
1669 return Pred1Br;
1670 }
1671
1672 // Ok, if we got here, both predecessors end with an unconditional branch to
1673 // BB. Don't panic! If both blocks only have a single (identical)
1674 // predecessor, and THAT is a conditional branch, then we're all ok!
1675 BasicBlock *CommonPred = Pred1->getSinglePredecessor();
1676 if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor())
1677 return nullptr;
1678
1679 // Otherwise, if this is a conditional branch, then we can use it!
1680 BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator());
1681 if (!BI) return nullptr;
1682
1683 assert(BI->isConditional() && "Two successors but not conditional?");
1684 if (BI->getSuccessor(0) == Pred1) {
1685 IfTrue = Pred1;
1686 IfFalse = Pred2;
1687 } else {
1688 IfTrue = Pred2;
1689 IfFalse = Pred1;
1690 }
1691 return BI;
1692}
1693
1694// After creating a control flow hub, the operands of PHINodes in an outgoing
1695// block Out no longer match the predecessors of that block. Predecessors of Out
1696// that are incoming blocks to the hub are now replaced by just one edge from
1697// the hub. To match this new control flow, the corresponding values from each
1698// PHINode must now be moved a new PHINode in the first guard block of the hub.
1699//
1700// This operation cannot be performed with SSAUpdater, because it involves one
1701// new use: If the block Out is in the list of Incoming blocks, then the newly
1702// created PHI in the Hub will use itself along that edge from Out to Hub.
1703static void reconnectPhis(BasicBlock *Out, BasicBlock *GuardBlock,
1704 const SetVector<BasicBlock *> &Incoming,
1705 BasicBlock *FirstGuardBlock) {
1706 auto I = Out->begin();
1707 while (I != Out->end() && isa<PHINode>(I)) {
1708 auto Phi = cast<PHINode>(I);
1709 auto NewPhi =
1710 PHINode::Create(Phi->getType(), Incoming.size(),
1711 Phi->getName() + ".moved", &FirstGuardBlock->front());
1712 for (auto *In : Incoming) {
1713 Value *V = UndefValue::get(Phi->getType());
1714 if (In == Out) {
1715 V = NewPhi;
1716 } else if (Phi->getBasicBlockIndex(In) != -1) {
1717 V = Phi->removeIncomingValue(In, false);
1718 }
1719 NewPhi->addIncoming(V, In);
1720 }
1721 assert(NewPhi->getNumIncomingValues() == Incoming.size());
1722 if (Phi->getNumOperands() == 0) {
1723 Phi->replaceAllUsesWith(NewPhi);
1724 I = Phi->eraseFromParent();
1725 continue;
1726 }
1727 Phi->addIncoming(NewPhi, GuardBlock);
1728 ++I;
1729 }
1730}
1731
1734
1735// Redirects the terminator of the incoming block to the first guard
1736// block in the hub. The condition of the original terminator (if it
1737// was conditional) and its original successors are returned as a
1738// tuple <condition, succ0, succ1>. The function additionally filters
1739// out successors that are not in the set of outgoing blocks.
1740//
1741// - condition is non-null iff the branch is conditional.
1742// - Succ1 is non-null iff the sole/taken target is an outgoing block.
1743// - Succ2 is non-null iff condition is non-null and the fallthrough
1744// target is an outgoing block.
1745static std::tuple<Value *, BasicBlock *, BasicBlock *>
1747 const BBSetVector &Outgoing) {
1748 assert(isa<BranchInst>(BB->getTerminator()) &&
1749 "Only support branch terminator.");
1750 auto Branch = cast<BranchInst>(BB->getTerminator());
1751 auto Condition = Branch->isConditional() ? Branch->getCondition() : nullptr;
1752
1753 BasicBlock *Succ0 = Branch->getSuccessor(0);
1754 BasicBlock *Succ1 = nullptr;
1755 Succ0 = Outgoing.count(Succ0) ? Succ0 : nullptr;
1756
1757 if (Branch->isUnconditional()) {
1758 Branch->setSuccessor(0, FirstGuardBlock);
1759 assert(Succ0);
1760 } else {
1761 Succ1 = Branch->getSuccessor(1);
1762 Succ1 = Outgoing.count(Succ1) ? Succ1 : nullptr;
1763 assert(Succ0 || Succ1);
1764 if (Succ0 && !Succ1) {
1765 Branch->setSuccessor(0, FirstGuardBlock);
1766 } else if (Succ1 && !Succ0) {
1767 Branch->setSuccessor(1, FirstGuardBlock);
1768 } else {
1769 Branch->eraseFromParent();
1770 BranchInst::Create(FirstGuardBlock, BB);
1771 }
1772 }
1773
1774 assert(Succ0 || Succ1);
1775 return std::make_tuple(Condition, Succ0, Succ1);
1776}
1777// Setup the branch instructions for guard blocks.
1778//
1779// Each guard block terminates in a conditional branch that transfers
1780// control to the corresponding outgoing block or the next guard
1781// block. The last guard block has two outgoing blocks as successors
1782// since the condition for the final outgoing block is trivially
1783// true. So we create one less block (including the first guard block)
1784// than the number of outgoing blocks.
1786 const BBSetVector &Outgoing,
1787 BBPredicates &GuardPredicates) {
1788 // To help keep the loop simple, temporarily append the last
1789 // outgoing block to the list of guard blocks.
1790 GuardBlocks.push_back(Outgoing.back());
1791
1792 for (int i = 0, e = GuardBlocks.size() - 1; i != e; ++i) {
1793 auto Out = Outgoing[i];
1794 assert(GuardPredicates.count(Out));
1795 BranchInst::Create(Out, GuardBlocks[i + 1], GuardPredicates[Out],
1796 GuardBlocks[i]);
1797 }
1798
1799 // Remove the last block from the guard list.
1800 GuardBlocks.pop_back();
1801}
1802
1803/// We are using one integer to represent the block we are branching to. Then at
1804/// each guard block, the predicate was calcuated using a simple `icmp eq`.
1806 const BBSetVector &Incoming, const BBSetVector &Outgoing,
1807 SmallVectorImpl<BasicBlock *> &GuardBlocks, BBPredicates &GuardPredicates) {
1808 auto &Context = Incoming.front()->getContext();
1809 auto FirstGuardBlock = GuardBlocks.front();
1810
1811 auto Phi = PHINode::Create(Type::getInt32Ty(Context), Incoming.size(),
1812 "merged.bb.idx", FirstGuardBlock);
1813
1814 for (auto In : Incoming) {
1815 Value *Condition;
1816 BasicBlock *Succ0;
1817 BasicBlock *Succ1;
1818 std::tie(Condition, Succ0, Succ1) =
1819 redirectToHub(In, FirstGuardBlock, Outgoing);
1820 Value *IncomingId = nullptr;
1821 if (Succ0 && Succ1) {
1822 // target_bb_index = Condition ? index_of_succ0 : index_of_succ1.
1823 auto Succ0Iter = find(Outgoing, Succ0);
1824 auto Succ1Iter = find(Outgoing, Succ1);
1826 std::distance(Outgoing.begin(), Succ0Iter));
1828 std::distance(Outgoing.begin(), Succ1Iter));
1829 IncomingId = SelectInst::Create(Condition, Id0, Id1, "target.bb.idx",
1830 In->getTerminator());
1831 } else {
1832 // Get the index of the non-null successor.
1833 auto SuccIter = Succ0 ? find(Outgoing, Succ0) : find(Outgoing, Succ1);
1835 std::distance(Outgoing.begin(), SuccIter));
1836 }
1837 Phi->addIncoming(IncomingId, In);
1838 }
1839
1840 for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) {
1841 auto Out = Outgoing[i];
1842 auto Cmp = ICmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_EQ, Phi,
1844 Out->getName() + ".predicate", GuardBlocks[i]);
1845 GuardPredicates[Out] = Cmp;
1846 }
1847}
1848
1849/// We record the predicate of each outgoing block using a phi of boolean.
1851 const BBSetVector &Incoming, const BBSetVector &Outgoing,
1852 SmallVectorImpl<BasicBlock *> &GuardBlocks, BBPredicates &GuardPredicates,
1853 SmallVectorImpl<WeakVH> &DeletionCandidates) {
1854 auto &Context = Incoming.front()->getContext();
1855 auto BoolTrue = ConstantInt::getTrue(Context);
1856 auto BoolFalse = ConstantInt::getFalse(Context);
1857 auto FirstGuardBlock = GuardBlocks.front();
1858
1859 // The predicate for the last outgoing is trivially true, and so we
1860 // process only the first N-1 successors.
1861 for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) {
1862 auto Out = Outgoing[i];
1863 LLVM_DEBUG(dbgs() << "Creating guard for " << Out->getName() << "\n");
1864
1865 auto Phi =
1867 StringRef("Guard.") + Out->getName(), FirstGuardBlock);
1868 GuardPredicates[Out] = Phi;
1869 }
1870
1871 for (auto *In : Incoming) {
1872 Value *Condition;
1873 BasicBlock *Succ0;
1874 BasicBlock *Succ1;
1875 std::tie(Condition, Succ0, Succ1) =
1876 redirectToHub(In, FirstGuardBlock, Outgoing);
1877
1878 // Optimization: Consider an incoming block A with both successors
1879 // Succ0 and Succ1 in the set of outgoing blocks. The predicates
1880 // for Succ0 and Succ1 complement each other. If Succ0 is visited
1881 // first in the loop below, control will branch to Succ0 using the
1882 // corresponding predicate. But if that branch is not taken, then
1883 // control must reach Succ1, which means that the incoming value of
1884 // the predicate from `In` is true for Succ1.
1885 bool OneSuccessorDone = false;
1886 for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) {
1887 auto Out = Outgoing[i];
1888 PHINode *Phi = cast<PHINode>(GuardPredicates[Out]);
1889 if (Out != Succ0 && Out != Succ1) {
1890 Phi->addIncoming(BoolFalse, In);
1891 } else if (!Succ0 || !Succ1 || OneSuccessorDone) {
1892 // Optimization: When only one successor is an outgoing block,
1893 // the incoming predicate from `In` is always true.
1894 Phi->addIncoming(BoolTrue, In);
1895 } else {
1896 assert(Succ0 && Succ1);
1897 if (Out == Succ0) {
1898 Phi->addIncoming(Condition, In);
1899 } else {
1900 auto Inverted = invertCondition(Condition);
1901 DeletionCandidates.push_back(Condition);
1902 Phi->addIncoming(Inverted, In);
1903 }
1904 OneSuccessorDone = true;
1905 }
1906 }
1907 }
1908}
1909
1910// Capture the existing control flow as guard predicates, and redirect
1911// control flow from \p Incoming block through the \p GuardBlocks to the
1912// \p Outgoing blocks.
1913//
1914// There is one guard predicate for each outgoing block OutBB. The
1915// predicate represents whether the hub should transfer control flow
1916// to OutBB. These predicates are NOT ORTHOGONAL. The Hub evaluates
1917// them in the same order as the Outgoing set-vector, and control
1918// branches to the first outgoing block whose predicate evaluates to true.
1919static void
1921 SmallVectorImpl<WeakVH> &DeletionCandidates,
1922 const BBSetVector &Incoming,
1923 const BBSetVector &Outgoing, const StringRef Prefix,
1924 std::optional<unsigned> MaxControlFlowBooleans) {
1925 BBPredicates GuardPredicates;
1926 auto F = Incoming.front()->getParent();
1927
1928 for (int i = 0, e = Outgoing.size() - 1; i != e; ++i)
1929 GuardBlocks.push_back(
1930 BasicBlock::Create(F->getContext(), Prefix + ".guard", F));
1931
1932 // When we are using an integer to record which target block to jump to, we
1933 // are creating less live values, actually we are using one single integer to
1934 // store the index of the target block. When we are using booleans to store
1935 // the branching information, we need (N-1) boolean values, where N is the
1936 // number of outgoing block.
1937 if (!MaxControlFlowBooleans || Outgoing.size() <= *MaxControlFlowBooleans)
1938 calcPredicateUsingBooleans(Incoming, Outgoing, GuardBlocks, GuardPredicates,
1939 DeletionCandidates);
1940 else
1941 calcPredicateUsingInteger(Incoming, Outgoing, GuardBlocks, GuardPredicates);
1942
1943 setupBranchForGuard(GuardBlocks, Outgoing, GuardPredicates);
1944}
1945
1948 const BBSetVector &Incoming, const BBSetVector &Outgoing,
1949 const StringRef Prefix, std::optional<unsigned> MaxControlFlowBooleans) {
1950 if (Outgoing.size() < 2)
1951 return Outgoing.front();
1952
1954 if (DTU) {
1955 for (auto *In : Incoming) {
1956 for (auto Succ : successors(In))
1957 if (Outgoing.count(Succ))
1958 Updates.push_back({DominatorTree::Delete, In, Succ});
1959 }
1960 }
1961
1962 SmallVector<WeakVH, 8> DeletionCandidates;
1963 convertToGuardPredicates(GuardBlocks, DeletionCandidates, Incoming, Outgoing,
1964 Prefix, MaxControlFlowBooleans);
1965 auto FirstGuardBlock = GuardBlocks.front();
1966
1967 // Update the PHINodes in each outgoing block to match the new control flow.
1968 for (int i = 0, e = GuardBlocks.size(); i != e; ++i)
1969 reconnectPhis(Outgoing[i], GuardBlocks[i], Incoming, FirstGuardBlock);
1970
1971 reconnectPhis(Outgoing.back(), GuardBlocks.back(), Incoming, FirstGuardBlock);
1972
1973 if (DTU) {
1974 int NumGuards = GuardBlocks.size();
1975 assert((int)Outgoing.size() == NumGuards + 1);
1976
1977 for (auto In : Incoming)
1978 Updates.push_back({DominatorTree::Insert, In, FirstGuardBlock});
1979
1980 for (int i = 0; i != NumGuards - 1; ++i) {
1981 Updates.push_back({DominatorTree::Insert, GuardBlocks[i], Outgoing[i]});
1982 Updates.push_back(
1983 {DominatorTree::Insert, GuardBlocks[i], GuardBlocks[i + 1]});
1984 }
1985 Updates.push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1],
1986 Outgoing[NumGuards - 1]});
1987 Updates.push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1],
1988 Outgoing[NumGuards]});
1989 DTU->applyUpdates(Updates);
1990 }
1991
1992 for (auto I : DeletionCandidates) {
1993 if (I->use_empty())
1994 if (auto Inst = dyn_cast_or_null<Instruction>(I))
1995 Inst->eraseFromParent();
1996 }
1997
1998 return FirstGuardBlock;
1999}
SmallVector< MachineOperand, 4 > Cond
static BasicBlock * SplitBlockPredecessorsImpl(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
static void convertToGuardPredicates(SmallVectorImpl< BasicBlock * > &GuardBlocks, SmallVectorImpl< WeakVH > &DeletionCandidates, const BBSetVector &Incoming, const BBSetVector &Outgoing, const StringRef Prefix, std::optional< unsigned > MaxControlFlowBooleans)
static bool removeRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB)
Remove redundant instructions within sequences of consecutive dbg.value instructions.
static void calcPredicateUsingBooleans(const BBSetVector &Incoming, const BBSetVector &Outgoing, SmallVectorImpl< BasicBlock * > &GuardBlocks, BBPredicates &GuardPredicates, SmallVectorImpl< WeakVH > &DeletionCandidates)
We record the predicate of each outgoing block using a phi of boolean.
static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB, ArrayRef< BasicBlock * > Preds, BranchInst *BI, bool HasLoopExit)
Update the PHI nodes in OrigBB to include the values coming from NewBB.
static BasicBlock * SplitBlockImpl(BasicBlock *Old, Instruction *SplitPt, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName, bool Before)
static Instruction * SplitBlockAndInsertIfThenImpl(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, BasicBlock *ThenBlock)
static std::tuple< Value *, BasicBlock *, BasicBlock * > redirectToHub(BasicBlock *BB, BasicBlock *FirstGuardBlock, const BBSetVector &Outgoing)
static bool remomveUndefDbgAssignsFromEntryBlock(BasicBlock *BB)
Remove redundant undef dbg.assign intrinsic from an entry block using a forward scan.
static void setupBranchForGuard(SmallVectorImpl< BasicBlock * > &GuardBlocks, const BBSetVector &Outgoing, BBPredicates &GuardPredicates)
static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB, ArrayRef< BasicBlock * > Preds, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA, bool &HasLoopExit)
Update DominatorTree, LoopInfo, and LCCSA analysis information.
static void reconnectPhis(BasicBlock *Out, BasicBlock *GuardBlock, const SetVector< BasicBlock * > &Incoming, BasicBlock *FirstGuardBlock)
static void calcPredicateUsingInteger(const BBSetVector &Incoming, const BBSetVector &Outgoing, SmallVectorImpl< BasicBlock * > &GuardBlocks, BBPredicates &GuardPredicates)
We are using one integer to represent the block we are branching to.
static bool removeRedundantDbgInstrsUsingForwardScan(BasicBlock *BB)
Remove redundant dbg.value instructions using a forward scan.
static void SplitLandingPadPredecessorsImpl(BasicBlock *OrigBB, ArrayRef< BasicBlock * > Preds, const char *Suffix1, const char *Suffix2, SmallVectorImpl< BasicBlock * > &NewBBs, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
static cl::opt< unsigned > MaxDeoptOrUnreachableSuccessorCheckDepth("max-deopt-or-unreachable-succ-check-depth", cl::init(8), cl::Hidden, cl::desc("Set the maximum path length when checking whether a basic block " "is followed by a block that either has a terminating " "deoptimizing call or is terminated with an unreachable"))
BlockVerifier::State From
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
std::string Name
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static LVOptions Options
Definition: LVOptions.cpp:25
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
LLVMContext & Context
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
iterator end() const
Definition: ArrayRef.h:152
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:163
iterator begin() const
Definition: ArrayRef.h:151
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:158
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator end()
Definition: BasicBlock.h:316
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:314
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:372
const LandingPadInst * getLandingPadInst() const
Return the landingpad instruction associated with the landing pad.
Definition: BasicBlock.cpp:517
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:245
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
Definition: BasicBlock.h:495
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:208
const Instruction & front() const
Definition: BasicBlock.h:326
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:105
bool isEntryBlock() const
Return true if this is the entry block of the containing function.
Definition: BasicBlock.cpp:395
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:401
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
Definition: BasicBlock.cpp:322
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:284
const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
Definition: BasicBlock.cpp:181
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:292
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:314
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
Definition: BasicBlock.cpp:215
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:35
bool isLandingPad() const
Return true if this basic block is a landing pad.
Definition: BasicBlock.cpp:513
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:512
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.h:127
bool canSplitPredecessors() const
Definition: BasicBlock.cpp:370
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
Definition: BasicBlock.h:468
const Instruction & back() const
Definition: BasicBlock.h:328
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:341
This class represents a no-op cast from one type to another.
Conditional or Unconditional Branch instruction.
bool isConditional() const
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
static CleanupPadInst * Create(Value *ParentPad, ArrayRef< Value * > Args=std::nullopt, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
static CleanupReturnInst * Create(Value *CleanupPad, BasicBlock *UnwindBB=nullptr, Instruction *InsertBefore=nullptr)
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:835
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:887
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:842
DWARF expression.
This represents the llvm.dbg.assign instruction.
This represents the llvm.dbg.value instruction.
Identifies a unique instance of a variable.
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:145
iterator end()
Definition: DenseMap.h:84
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
iterator_range< iterator > children()
NodeT * getBlock() const
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
void recalculate(Function &F)
Notify DTU that the entry block was replaced.
bool hasDomTree() const
Returns true if it holds a DominatorTree.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
void splitBlock(NodeT *NewBB)
splitBlock - BB is split and now it has one successor.
DomTreeNodeBase< NodeT > * setNewRoot(NodeT *BB)
Add a new node to the forward dominator tree and make it a new root.
void eraseNode(NodeT *BB)
eraseNode - Removes a node from the dominator tree.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:335
This instruction extracts a struct member or array element value from an aggregate value.
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:652
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:358
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:685
const BasicBlock * getParent() const
Definition: Instruction.h:90
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:275
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1455
bool isExceptionalTerminator() const
Definition: Instruction.h:178
SymbolTableList< Instruction >::iterator insertInto(BasicBlock *ParentBB, SymbolTableList< Instruction >::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Definition: Instruction.cpp:98
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:82
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:355
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
The landingpad instruction holds all of the information necessary to generate correct exception handl...
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:139
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:232
unsigned getLoopDepth() const
Return the nesting level of this loop.
Definition: LoopInfo.h:97
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:258
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:114
void moveToHeader(BlockT *BB)
This method is used to move BB (which must be part of this loop) to be the loop header of the loop (t...
Definition: LoopInfo.h:460
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
Definition: LoopInfo.h:1057
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:1005
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: LoopInfo.cpp:631
Metadata node.
Definition: Metadata.h:943
Provides a lazy, caching interface for making common memory aliasing information queries,...
void invalidateCachedPredecessors()
Clears the PredIteratorCache info.
void removeInstruction(Instruction *InstToRemove)
Removes an instruction from the dependence analysis, updating the dependence of instructions that pre...
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was spliced into From and To.
void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT, bool UpdateDTFirst=false)
Apply CFG updates, analogous with the DT edge updates.
void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was merged into To.
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock * > Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1863
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:717
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:252
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1759
Return a value (possibly void), from a function.
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
A vector that has set insertion semantics.
Definition: SetVector.h:40
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:208
const T & front() const
Return the first element of the SetVector.
Definition: SetVector.h:122
const T & back() const
Return the last element of the SetVector.
Definition: SetVector.h:128
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:82
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition: DenseSet.h:290
size_type size() const
Definition: SmallPtrSet.h:93
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:379
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
iterator begin() const
Definition: SmallPtrSet.h:403
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void reserve(size_type N)
Definition: SmallVector.h:667
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
Provides information about what library functions are available for the current target.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
std::string str() const
Return the twine contents as a std::string.
Definition: Twine.cpp:17
static IntegerType * getInt1Ty(LLVMContext &C)
static IntegerType * getInt32Ty(LLVMContext &C)
bool isTokenTy() const
Return true if this is 'token'.
Definition: Type.h:219
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1740
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
op_range operands()
Definition: User.h:242
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:375
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
bool use_empty() const
Definition: Value.h:344
bool hasName() const
Definition: Value.h:261
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:381
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
Definition: DenseSet.h:185
self_iterator getIterator()
Definition: ilist_node.h:82
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ Tail
Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...
Definition: CallingConv.h:76
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
AssignmentInstRange getAssignmentInsts(DIAssignID *ID)
Return a range of instructions (typically just one) that have ID as an attachment.
Definition: DebugInfo.cpp:1738
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void ReplaceInstWithInst(BasicBlock *BB, BasicBlock::iterator &BI, Instruction *I)
Replace the instruction specified by BI with the instruction specified by I.
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1755
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
bool succ_empty(const Instruction *I)
Definition: CFG.h:255
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 @...
BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ)
Search for the specified successor of basic block BB and return its position in the terminator instru...
Definition: CFG.cpp:79
void detachDeadBlocks(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs=false)
Replace contents of every block in BBs with single unreachable instruction.
auto successors(const MachineBasicBlock *BB)
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...
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
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...
BasicBlock * splitBlockBefore(BasicBlock *Old, Instruction *SplitPt, DomTreeUpdater *DTU, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName="")
Split the specified block at the specified instruction SplitPt.
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
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...
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...
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,...
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1742
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.
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:484
bool EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete all basic blocks from F that are not reachable from its entry node.
bool MergeBlockSuccessorsIntoGivenBlocks(SmallPtrSetImpl< BasicBlock * > &MergeBlocks, Loop *L=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr)
Merge block(s) sucessors, if possible.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:109
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.
SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)
Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...
Definition: SmallVector.h:1298
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...
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:89
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.
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.
bool isAssignmentTrackingEnabled(const Module &M)
Return true if assignment tracking is enabled for module M.
Definition: DebugInfo.cpp:2033
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...
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.
bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition: CFG.cpp:95
unsigned SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
Loop over all of the edges in the CFG, breaking critical edges as they are found.
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.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1869
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.
bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
If the specified value is an effectively dead PHI node, due to being a def-use chain of single-use no...
Definition: Local.cpp:645
unsigned succ_size(const MachineBasicBlock *BB)
Value * invertCondition(Value *Condition)
Invert the given true/false value, possibly reusing an existing copy.
Definition: Local.cpp:3477
void DeleteDeadBlocks(ArrayRef< BasicBlock * > BBs, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified blocks from BB.
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...
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 ...
void setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ)
Sets the unwind edge of an instruction to a particular successor.
unsigned pred_size(const MachineBasicBlock *BB)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
Option class for critical edge splitting.
CriticalEdgeSplittingOptions & setPreserveLCSSA()