1//===- BasicBlockUtils.cpp - BasicBlock Utilities --------------------------==// 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 7//===----------------------------------------------------------------------===// 9// This family of functions perform manipulations on basic blocks, and 10// instructions contained within basic blocks. 12//===----------------------------------------------------------------------===// 54#define DEBUG_TYPE "basicblock-utils" 58cl::desc(
"Set the maximum path length when checking whether a basic block " 59"is followed by a block that either has a terminating " 60"deoptimizing call or is terminated with an unreachable"));
65bool KeepOneInputPHIs) {
67// Loop through all of our successors and make sure they know that one 68// of their predecessors is going away. 71 Succ->removePredecessor(BB, KeepOneInputPHIs);
72if (Updates && UniqueSuccessors.
insert(Succ).second)
73 Updates->
push_back({DominatorTree::Delete, BB, Succ});
76// Zap all the instructions in the block. 79// If this instruction is used, replace uses with an arbitrary value. 80// Because control flow can't get here, we don't care what we replace the 81// value with. Note that since this block is unreachable, and all values 82// contained within it must dominate their uses, that all uses will 83// eventually be removed (they are themselves dead). 86 BB->back().eraseFromParent();
90 isa<UnreachableInst>(BB->getTerminator()) &&
91"The successor list of BB isn't empty before " 92"applying corresponding DTU updates.");
97bool KeepOneInputPHIs) {
102bool KeepOneInputPHIs) {
104// Make sure that all predecessors of each dead block is also dead. 106assert(Dead.size() == BBs.
size() &&
"Duplicating blocks?");
109assert(Dead.count(Pred) &&
"All predecessors must be dead!");
122 BB->eraseFromParent();
126bool KeepOneInputPHIs) {
129// Mark all reachable blocks. 131 (void)BB
/* Mark all reachable blocks */;
133// Collect all dead blocks. 134 std::vector<BasicBlock*> DeadBlocks;
136if (!Reachable.
count(&BB))
137 DeadBlocks.push_back(&BB);
139// Delete the dead blocks. 142return !DeadBlocks.empty();
147if (!isa<PHINode>(BB->
begin()))
151if (PN->getIncomingValue(0) != PN)
152 PN->replaceAllUsesWith(PN->getIncomingValue(0));
159 PN->eraseFromParent();
166// Recursively deleting a PHI may cause multiple PHIs to be deleted 167// or RAUW'd undef, so use an array of WeakTrackingVH for the PHIs to delete. 173for (
unsigned i = 0, e = PHIs.
size(); i != e; ++i)
174if (
PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].
operatorValue*()))
183bool PredecessorWithTwoSuccessors,
188// Can't merge if there are multiple predecessors, or no predecessors. 190if (!PredBB)
returnfalse;
192// Don't break self-loops. 193if (PredBB == BB)
returnfalse;
195// Don't break unwinding instructions or terminators with other side-effects. 200// Can't merge if there are multiple distinct successors. 204// Currently only allow PredBB to have two predecessors, one being BB. 205// Update BI to branch to BB's only successor instead of BB. 208unsigned FallThruPath;
209if (PredecessorWithTwoSuccessors) {
210if (!(PredBB_BI = dyn_cast<BranchInst>(PTI)))
216 FallThruPath = PredBB_BI->
getSuccessor(0) == BB ? 0 : 1;
219// Can't merge if there is PHI loop. 227// Begin by getting rid of unneeded PHIs. 229if (isa<PHINode>(BB->
front())) {
231if (!isa<PHINode>(PN.getIncomingValue(0)) ||
232 cast<PHINode>(PN.getIncomingValue(0))->getParent() != BB)
233 IncomingValues.
push_back(PN.getIncomingValue(0));
238assert(!DTU &&
"cannot use both DT and DTU for updates");
242assert(BBNode &&
"PredNode unreachable but BBNode reachable?");
247// DTU update: Collect all the edges that exit BB. 248// These dominator edges will be redirected from Pred. 249 std::vector<DominatorTree::UpdateType> Updates;
251assert(!DT &&
"cannot use both DT and DTU for updates");
252// To avoid processing the same predecessor more than once. 256 Updates.reserve(Updates.size() + 2 *
succ_size(BB) + 1);
257// Add insert edges first. Experimentally, for the particular case of two 258// blocks that can be merged, with a single successor and single predecessor 259// respectively, it is beneficial to have all insert updates first. Deleting 260// edges first may lead to unreachable blocks, followed by inserting edges 261// making the blocks reachable again. Such DT updates lead to high compile 262// times. We add inserts before deletes here to reduce compile time. 264// This successor of BB may already be a PredBB's successor. 265if (!SuccsOfPredBB.
contains(SuccOfBB))
266if (SeenSuccs.
insert(SuccOfBB).second)
267 Updates.push_back({DominatorTree::Insert, PredBB, SuccOfBB});
270if (SeenSuccs.
insert(SuccOfBB).second)
271 Updates.push_back({DominatorTree::Delete, BB, SuccOfBB});
272 Updates.push_back({DominatorTree::Delete, PredBB, BB});
277// If there's nothing to move, mark the starting instruction as the last 278// instruction in the block. Terminator instruction is handled separately. 282// Move all definitions in the successor to the predecessor... 288// Make all PHI nodes that referred to BB now refer to Pred as their 292if (PredecessorWithTwoSuccessors) {
293// Delete the unconditional branch from BB. 296// Update branch in the predecessor. 299// Delete the unconditional branch from the predecessor. 302// Move terminator instruction. 305// Terminator may be a memory accessing instruction too. 311// Add unreachable to now empty BB. 314// Inherit predecessors name if it exists. 329"successors should have been transferred to PredBB");
333// Finally, erase the old block and update dominator info. 342assert(!MergeBlocks.
empty() &&
"MergeBlocks should not be empty");
344bool BlocksHaveBeenMerged =
false;
345while (!MergeBlocks.
empty()) {
348if (Dest && (!L || L->contains(Dest))) {
353"Expecting BB to be unique predecessor of the Dest block");
354 MergeBlocks.
erase(Dest);
355 BlocksHaveBeenMerged =
true;
357 MergeBlocks.
erase(BB);
359 MergeBlocks.
erase(BB);
361return BlocksHaveBeenMerged;
364/// Remove redundant instructions within sequences of consecutive dbg.value 365/// instructions. This is done using a backward scan to keep the last dbg.value 366/// describing a specific variable/fragment. 368/// BackwardScan strategy: 369/// ---------------------- 370/// Given a sequence of consecutive DbgValueInst like this 372/// dbg.value ..., "x", FragmentX1 (*) 373/// dbg.value ..., "y", FragmentY1 374/// dbg.value ..., "x", FragmentX2 375/// dbg.value ..., "x", FragmentX1 (**) 377/// then the instruction marked with (*) can be removed (it is guaranteed to be 378/// obsoleted by the instruction marked with (**) as the latter instruction is 379/// describing the same variable using the same fragment info). 381/// Possible improvements: 382/// - Check fully overlapping fragments and not only identical fragments. 383/// - Support dbg.declare. dbg.label, and possibly other meta instructions being 384/// part of the sequence of consecutive instructions. 391if (isa<DbgLabelRecord>(DR)) {
392// Emulate existing behaviour (see comment below for dbg.declares). 393// FIXME: Don't do this. 399// Skip declare-type records, as the debug intrinsic method only works 400// on dbg.value intrinsics. 401if (DVR.
getType() == DbgVariableRecord::LocationType::Declare) {
402// The debug intrinsic method treats dbg.declares are "non-debug" 403// instructions (i.e., a break in a consecutive range of debug 404// intrinsics). Emulate that to create identical outputs. See 405// "Possible improvements" above. 406// FIXME: Delete the line below. 413auto R = VariableSet.
insert(Key);
414// If the same variable fragment is described more than once it is enough 415// to keep the last one (i.e. the first found since we for reverse 421// Don't delete dbg.assign intrinsics that are linked to instructions. 424// Unlinked dbg.assign intrinsics can be treated like dbg.values. 429// Sequence with consecutive dbg.value instrs ended. Clear the map to 430// restart identifying redundant instructions if case we find another 431// dbg.value sequence. 435for (
auto &DVR : ToBeRemoved)
436 DVR->eraseFromParent();
438return !ToBeRemoved.
empty();
450 DVI->getExpression(),
451 DVI->getDebugLoc()->getInlinedAt());
452auto R = VariableSet.
insert(Key);
453// If the variable fragment hasn't been seen before then we don't want 454// to remove this dbg intrinsic. 458if (
auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI)) {
459// Don't delete dbg.assign intrinsics that are linked to instructions. 462// Unlinked dbg.assign intrinsics can be treated like dbg.values. 465// If the same variable fragment is described more than once it is enough 466// to keep the last one (i.e. the first found since we for reverse 471// Sequence with consecutive dbg.value instrs ended. Clear the map to 472// restart identifying redundant instructions if case we find another 473// dbg.value sequence. 477for (
auto &Instr : ToBeRemoved)
478 Instr->eraseFromParent();
480return !ToBeRemoved.
empty();
483/// Remove redundant dbg.value instructions using a forward scan. This can 484/// remove a dbg.value instruction that is redundant due to indicating that a 485/// variable has the same value as already being indicated by an earlier 488/// ForwardScan strategy: 489/// --------------------- 490/// Given two identical dbg.value instructions, separated by a block of 491/// instructions that isn't describing the same variable, like this 493/// dbg.value X1, "x", FragmentX1 (**) 494/// <block of instructions, none being "dbg.value ..., "x", ..."> 495/// dbg.value X1, "x", FragmentX1 (*) 497/// then the instruction marked with (*) can be removed. Variable "x" is already 498/// described as being mapped to the SSA value X1. 500/// Possible improvements: 501/// - Keep track of non-overlapping fragments. 510if (DVR.getType() == DbgVariableRecord::LocationType::Declare)
513 DVR.getDebugLoc()->getInlinedAt());
514auto VMI = VariableMap.
find(Key);
515// A dbg.assign with no linked instructions can be treated like a 516// dbg.value (i.e. can be deleted). 520// Update the map if we found a new value/expression describing the 521// variable, or if the variable wasn't mapped already. 523if (VMI == VariableMap.
end() || VMI->second.first != Values ||
524 VMI->second.second != DVR.getExpression()) {
526 VariableMap[Key] = {Values, DVR.getExpression()};
528 VariableMap[Key] = {Values,
nullptr};
531// Don't delete dbg.assign intrinsics that are linked to instructions. 534// Found an identical mapping. Remember the instruction for later removal. 539for (
auto *DVR : ToBeRemoved)
540 DVR->eraseFromParent();
542return !ToBeRemoved.
empty();
550// Returns the DebugVariable for DVI with no fragment info. 553 DVR.getDebugLoc().getInlinedAt());
556// Remove undef dbg.assign intrinsics that are encountered before 557// any non-undef intrinsics from the entry block. 560if (!DVR.isDbgValue() && !DVR.isDbgAssign())
565if (!SeenDefForAggregate.
contains(Aggregate)) {
566bool IsKill = DVR.isKillLocation() && IsDbgValueKind;
568 SeenDefForAggregate.
insert(Aggregate);
569 }
elseif (DVR.isDbgAssign()) {
577 DVR->eraseFromParent();
579return !ToBeRemoved.
empty();
593 DVI->getDebugLoc()->getInlinedAt());
594auto VMI = VariableMap.
find(Key);
595auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI);
596// A dbg.assign with no linked instructions can be treated like a 597// dbg.value (i.e. can be deleted). 600// Update the map if we found a new value/expression describing the 601// variable, or if the variable wasn't mapped already. 603if (VMI == VariableMap.
end() || VMI->second.first != Values ||
604 VMI->second.second != DVI->getExpression()) {
605// Use a sentinel value (nullptr) for the DIExpression when we see a 606// linked dbg.assign so that the next debug intrinsic will never match 607// it (i.e. always treat linked dbg.assigns as if they're unique). 609 VariableMap[Key] = {Values, DVI->getExpression()};
611 VariableMap[Key] = {Values,
nullptr};
615// Don't delete dbg.assign intrinsics that are linked to instructions. 622for (
auto &Instr : ToBeRemoved)
623 Instr->eraseFromParent();
625return !ToBeRemoved.
empty();
628/// Remove redundant undef dbg.assign intrinsic from an entry block using a 631/// --------------------- 632/// Scanning forward, delete dbg.assign intrinsics iff they are undef, not 633/// linked to an intrinsic, and don't share an aggregate variable with a debug 634/// intrinsic that didn't meet the criteria. In other words, undef dbg.assigns 635/// that come before non-undef debug intrinsics for the variable are 638/// dbg.assign undef, "x", FragmentX1 (*) 639/// <block of instructions, none being "dbg.value ..., "x", ..."> 640/// dbg.value %V, "x", FragmentX2 641/// <block of instructions, none being "dbg.value ..., "x", ..."> 642/// dbg.assign undef, "x", FragmentX1 644/// then (only) the instruction marked with (*) can be removed. 645/// Possible improvements: 646/// - Keep track of non-overlapping fragments. 654// Returns the DebugVariable for DVI with no fragment info. 657 DVI->getDebugLoc()->getInlinedAt());
660// Remove undef dbg.assign intrinsics that are encountered before 661// any non-undef intrinsics from the entry block. 666auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI);
669if (!SeenDefForAggregate.
contains(Aggregate)) {
672 SeenDefForAggregate.
insert(Aggregate);
680 DAI->eraseFromParent();
682return !ToBeRemoved.
empty();
686bool MadeChanges =
false;
687// By using the "backward scan" strategy before the "forward scan" strategy we 688// can remove both dbg.value (2) and (3) in a situation like this: 690// (1) dbg.value V1, "x", DIExpression() 692// (2) dbg.value V2, "x", DIExpression() 693// (3) dbg.value V1, "x", DIExpression() 695// The backward scan will remove (2), it is made obsolete by (3). After 696// getting (2) out of the way, the foward scan will remove (3) since "x" 697// already is described as having the value V1 at (1). 712// Replaces all of the uses of the instruction with uses of the value 713I.replaceAllUsesWith(V);
715// Make sure to propagate a name if there is one already. 716if (
I.hasName() && !V->hasName())
719// Delete the unnecessary instruction now... 720 BI = BI->eraseFromParent();
725assert(
I->getParent() ==
nullptr &&
726"ReplaceInstWithInst: Instruction already inserted into basic block!");
728// Copy debug location to newly added instruction, if it wasn't already set 730if (!
I->getDebugLoc())
731I->setDebugLoc(BI->getDebugLoc());
733// Insert the new instruction into the basic block... 736// Replace all uses of the old instruction, and delete it. 739// Move BI back to point to the newly inserted instruction 744// Remember visited blocks to avoid infinite loop 748 VisitedBlocks.
insert(BB).second) {
773// If it is a critical edge, and the succesor is an exception block, handle 774// the split edge logic in this specific function 778// If this is a critical edge, let SplitKnownCriticalEdge do it. 782// If the edge isn't critical, then BB has a single successor or Succ has a 783// single pred. Split the block. 785// If the successor only has a single pred, split the top of the successor 787assert(SP == BB &&
"CFG broken");
793// Otherwise, if BB has a single successor, split it at the bottom of the 796"Should have a single succ!");
801if (
auto *
II = dyn_cast<InvokeInst>(TI))
802II->setUnwindDest(Succ);
803elseif (
auto *CS = dyn_cast<CatchSwitchInst>(TI))
804 CS->setUnwindDest(Succ);
805elseif (
auto *CR = dyn_cast<CleanupReturnInst>(TI))
806 CR->setUnwindDest(Succ);
815// We manually update the LandingPadReplacement PHINode and it is the last 816// PHI Node. So, if we find it, we are done. 820// Reuse the previous value of BBIdx if it lines up. In cases where we 821// have multiple phi nodes with *lots* of predecessors, this is a speed 822// win because we don't have to scan the PHI looking for TIBB. This 823// happens because the BB list of PHI nodes are usually in the same 825if (PN.getIncomingBlock(BBIdx) != OldPred)
826 BBIdx = PN.getBasicBlockIndex(OldPred);
828assert(BBIdx != -1 &&
"Invalid PHI Index!");
829 PN.setIncomingBlock(BBIdx, NewPred);
840if (!LandingPadReplacement && !PadInst->
isEHPad())
845// Check if extra modifications will be required to preserve loop-simplify 846// form after splitting. If it would require splitting blocks with IndirectBr 847// terminators, bail out if preserving loop-simplify form is requested. 848if (
Options.PreserveLoopSimplify && LI) {
849if (
Loop *BBLoop = LI->getLoopFor(BB)) {
851// The only way that we can break LoopSimplify form by splitting a 852// critical edge is when there exists some edge from BBLoop to Succ *and* 853// the only edge into Succ from outside of BBLoop is that of NewBB after 854// the split. If the first isn't true, then LoopSimplify still holds, 855// NewBB is the new exit block and it has no non-loop predecessors. If the 856// second isn't true, then Succ was not in LoopSimplify form prior to 857// the split as it had a non-loop predecessor. In both of these cases, 858// the predecessor must be directly in BBLoop, not in a subloop, or again 859// LoopSimplify doesn't hold. 862continue;
// The new block is known. 863if (LI->getLoopFor(
P) != BBLoop) {
864// Loop is not in LoopSimplify form, no need to re simplify after 871// Loop-simplify form can be preserved, if we can split all in-loop 886if (LandingPadReplacement) {
887auto *NewLP = OriginalPad->
clone();
889 NewLP->insertBefore(Terminator->getIterator());
892Value *ParentPad =
nullptr;
893if (
auto *FuncletPad = dyn_cast<FuncletPadInst>(PadInst))
894 ParentPad = FuncletPad->getParentPad();
895elseif (
auto *CatchSwitch = dyn_cast<CatchSwitchInst>(PadInst))
896 ParentPad = CatchSwitch->getParentPad();
897elseif (
auto *CleanupPad = dyn_cast<CleanupPadInst>(PadInst))
898 ParentPad = CleanupPad->getParentPad();
899elseif (
auto *LandingPad = dyn_cast<LandingPadInst>(PadInst))
900 ParentPad = LandingPad->getParent();
917 Updates.
push_back({DominatorTree::Insert, BB, NewBB});
918 Updates.
push_back({DominatorTree::Insert, NewBB, Succ});
919 Updates.
push_back({DominatorTree::Delete, BB, Succ});
925 MSSAU->applyUpdates(Updates, *DT);
927 MSSAU->getMemorySSA()->verifyMemorySSA();
932if (
Loop *BBLoop = LI->getLoopFor(BB)) {
933// If one or the other blocks were not in a loop, the new block is not 934// either, and thus LI doesn't need to be updated. 935if (
Loop *SuccLoop = LI->getLoopFor(Succ)) {
936if (BBLoop == SuccLoop) {
937// Both in the same loop, the NewBB joins loop. 938 SuccLoop->addBasicBlockToLoop(NewBB, *LI);
939 }
elseif (BBLoop->contains(SuccLoop)) {
940// Edge from an outer loop to an inner loop. Add to the outer loop. 941 BBLoop->addBasicBlockToLoop(NewBB, *LI);
942 }
elseif (SuccLoop->contains(BBLoop)) {
943// Edge from an inner loop to an outer loop. Add to the outer loop. 944 SuccLoop->addBasicBlockToLoop(NewBB, *LI);
946// Edge from two loops with no containment relation. Because these 947// are natural loops, we know that the destination block must be the 948// header of its loop (adding a branch into a loop elsewhere would 949// create an irreducible loop). 950assert(SuccLoop->getHeader() == Succ &&
951"Should not create irreducible loops!");
952if (
Loop *
P = SuccLoop->getParentLoop())
953P->addBasicBlockToLoop(NewBB, *LI);
957// If BB is in a loop and Succ is outside of that loop, we may need to 958// update LoopSimplify form and LCSSA form. 959if (!BBLoop->contains(Succ)) {
960assert(!BBLoop->contains(NewBB) &&
961"Split point for loop exit is contained in loop!");
963// Update LCSSA form in the newly created exit block. 968if (!LoopPreds.
empty()) {
970 Succ, LoopPreds,
"split", DT, LI, MSSAU,
Options.PreserveLCSSA);
983// SplitBB shouldn't have anything non-trivial in it yet. 986"SplitBB has non-PHI nodes!");
988// For each PHI in the destination block. 990intIdx = PN.getBasicBlockIndex(SplitBB);
994// If the input is a PHI which already satisfies LCSSA, don't create 996if (
constPHINode *VP = dyn_cast<PHINode>(V))
997if (VP->getParent() == SplitBB)
1000// Otherwise a new PHI is needed. Create one and populate it. 1009// Update the original PHI. 1010 PN.setIncomingValue(
Idx, NewPN);
1017unsigned NumBroken = 0;
1033DomTreeUpdater LocalDTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
1035 DTU ? DTU : (DT ? &LocalDTU :
nullptr), LI, MSSAU,
1039while (isa<PHINode>(SplitIt) || SplitIt->isEHPad()) {
1041assert(SplitIt != SplitPt->getParent()->end());
1043 std::string
Name = BBName.
str();
1047// The new block lives in whichever loop the old one did. This preserves 1048// LCSSA as well, because we force the split point to be after any PHI nodes. 1051 L->addBasicBlockToLoop(New, *LI);
1055// Old dominates New. New node dominates all other nodes dominated by Old. 1057 Updates.
push_back({DominatorTree::Insert, Old, New});
1060if (UniqueSuccessorsOfOld.
insert(SuccessorOfOld).second) {
1061 Updates.
push_back({DominatorTree::Insert, New, SuccessorOfOld});
1062 Updates.
push_back({DominatorTree::Delete, Old, SuccessorOfOld});
1067// Old dominates New. New node dominates all other nodes dominated by Old. 1069 std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
1076// Move MemoryAccesses still tracked in Old, but part of New now. 1077// Update accesses in successor blocks accordingly. 1088returnSplitBlockImpl(Old, SplitPt,
/*DTU=*/nullptr, DT, LI, MSSAU, BBName,
1095returnSplitBlockImpl(Old, SplitPt, DTU,
/*DT=*/nullptr, LI, MSSAU, BBName,
1102constTwine &BBName) {
1105while (isa<PHINode>(SplitIt) || SplitIt->isEHPad())
1107 std::string
Name = BBName.
str();
1112// The new block lives in whichever loop the old one did. This preserves 1113// LCSSA as well, because we force the split point to be after any PHI nodes. 1116 L->addBasicBlockToLoop(New, *LI);
1120// New dominates Old. The predecessor nodes of the Old node dominate 1123 DTUpdates.
push_back({DominatorTree::Insert, New, Old});
1126if (UniquePredecessorsOfOld.
insert(PredecessorOfOld).second) {
1127 DTUpdates.
push_back({DominatorTree::Insert, PredecessorOfOld, New});
1128 DTUpdates.
push_back({DominatorTree::Delete, PredecessorOfOld, Old});
1133// Move MemoryAccesses still tracked in Old, but part of New now. 1134// Update accesses in successor blocks accordingly. 1144/// Update DominatorTree, LoopInfo, and LCCSA analysis information. 1145/// Invalidates DFS Numbering when DTU or DT is provided. 1150bool PreserveLCSSA,
bool &HasLoopExit) {
1151// Update dominator tree if available. 1153// Recalculation of DomTree is needed when updating a forward DomTree and 1154// the Entry BB is replaced. 1156// The entry block was removed and there is no external interface for 1157// the dominator tree to be notified of this change. In this corner-case 1158// we recalculate the entire tree. 1161// Split block expects NewBB to have a non-empty set of predecessors. 1164 Updates.
push_back({DominatorTree::Insert, NewBB, OldBB});
1166for (
auto *Pred : Preds)
1167if (UniquePreds.
insert(Pred).second) {
1168 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
1169 Updates.
push_back({DominatorTree::Delete, Pred, OldBB});
1178// Split block expects NewBB to have a non-empty set of predecessors. 1183// Update MemoryPhis after split if MemorySSA is available 1187// The rest of the logic is only relevant for updating the loop structures. 1193assert(DT &&
"DT should be available to update LoopInfo!");
1196// If we need to preserve loop analyses, collect some information about how 1197// this split will affect loops. 1198bool IsLoopEntry = !!L;
1199bool SplitMakesNewLoopHeader =
false;
1201// Preds that are not reachable from entry should not be used to identify if 1202// OldBB is a loop entry or if SplitMakesNewLoopHeader. Unreachable blocks 1203// are not within any loops, so we incorrectly mark SplitMakesNewLoopHeader 1204// as true and make the NewBB the header of some loop. This breaks LI. 1207// If we need to preserve LCSSA, determine if any of the preds is a loop 1211if (!PL->contains(OldBB))
1214// If we need to preserve LoopInfo, note whether any of the preds crosses 1215// an interesting loop boundary. 1218if (L->contains(Pred))
1221 SplitMakesNewLoopHeader =
true;
1224// Unless we have a loop for OldBB, nothing else to do here. 1229// Add the new block to the nearest enclosing loop (and not an adjacent 1230// loop). To find this, examine each of the predecessors and determine which 1231// loops enclose them, and select the most-nested loop which contains the 1232// loop containing the block being split. 1233Loop *InnermostPredLoop =
nullptr;
1236// Seek a loop which actually contains the block being split (to avoid 1238while (PredLoop && !PredLoop->contains(OldBB))
1241// Select the most-nested of these loops which contains the block. 1242if (PredLoop && PredLoop->contains(OldBB) &&
1243 (!InnermostPredLoop ||
1244 InnermostPredLoop->
getLoopDepth() < PredLoop->getLoopDepth()))
1245 InnermostPredLoop = PredLoop;
1249if (InnermostPredLoop)
1252 L->addBasicBlockToLoop(NewBB, *LI);
1253if (SplitMakesNewLoopHeader)
1254 L->moveToHeader(NewBB);
1258/// Update the PHI nodes in OrigBB to include the values coming from NewBB. 1259/// This also updates AliasAnalysis, if available. 1263// Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB. 1268// Check to see if all of the values coming in are the same. If so, we 1269// don't need to create a new PHI node, unless it's needed for LCSSA. 1270Value *InVal =
nullptr;
1286// If all incoming values for the new PHI would be the same, just don't 1287// make a new PHI. Instead, just remove the incoming values from the old 1293/* DeletePHIIfEmpty */false);
1295// Add an incoming value to the PHI node in the loop for the preheader 1301// If the values coming into the block are not the same, we need a new 1303// Create the new PHI node, insert it into NewBB at the end of the block 1307// NOTE! This loop walks backwards for a reason! First off, this minimizes 1308// the cost of removal if we end up removing a large number of values, and 1309// second off, this ensures that the indices for the incoming values aren't 1310// invalidated when we remove one. 1313if (PredSet.
count(IncomingBB)) {
1334// Do not attempt to split that which cannot be split. 1338// For the landingpads we need to act a bit differently. 1339// Delegate this work to the SplitLandingPadPredecessors. 1342 std::string NewName = std::string(Suffix) +
".split-lp";
1345 DTU, DT, LI, MSSAU, PreserveLCSSA);
1349// Create new basic block, insert right before the original block. 1353// The new block unconditionally branches to the old block. 1358// Splitting the predecessors of a loop header creates a preheader block. 1361// Using the loop start line number prevents debuggers stepping into the 1362// loop body for this instruction. 1365// If BB is the header of the Loop, it is possible that the loop is 1366// modified, such that the current latch does not remain the latch of the 1367// loop. If that is the case, the loop metadata from the current latch needs 1368// to be applied to the new latch. 1369 OldLatch = L->getLoopLatch();
1373// Move the edges from Preds to point to NewBB instead of BB. 1375// This is slightly more strict than necessary; the minimum requirement 1376// is that there be no more than one indirectbr branching to BB. And 1377// all BlockAddress uses would need to be updated. 1378assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
1379"Cannot split an edge from an IndirectBrInst");
1380 Pred->getTerminator()->replaceSuccessorWith(BB, NewBB);
1383// Insert a new PHI node into NewBB for every PHI node in BB and that new PHI 1384// node becomes an incoming value for BB's phi node. However, if the Preds 1385// list is empty, we need to insert dummy entries into the PHI nodes in BB to 1386// account for the newly created predecessor. 1388// Insert dummy values as the incoming value. 1393// Update DominatorTree, LoopInfo, and LCCSA analysis information. 1394bool HasLoopExit =
false;
1398if (!Preds.
empty()) {
1399// Update the PHI nodes in BB with the values coming from NewBB. 1405if (NewLatch != OldLatch) {
1408// It's still possible that OldLatch is the latch of another inner loop, 1409// in which case we do not remove the metadata. 1423bool PreserveLCSSA) {
1425 MSSAU, PreserveLCSSA);
1432bool PreserveLCSSA) {
1434/*DT=*/nullptr, LI, MSSAU, PreserveLCSSA);
1444// Create a new basic block for OrigBB's predecessors listed in Preds. Insert 1445// it right before the original block. 1451// The new block unconditionally branches to the old block. 1455// Move the edges from Preds to point to NewBB1 instead of OrigBB. 1457// This is slightly more strict than necessary; the minimum requirement 1458// is that there be no more than one indirectbr branching to BB. And 1459// all BlockAddress uses would need to be updated. 1460assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
1461"Cannot split an edge from an IndirectBrInst");
1462 Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
1465bool HasLoopExit =
false;
1467 PreserveLCSSA, HasLoopExit);
1469// Update the PHI nodes in OrigBB with the values coming from NewBB1. 1472// Move the remaining edges from OrigBB to point to NewBB2. 1477if (Pred == NewBB1)
continue;
1479"Cannot split an edge from an IndirectBrInst");
1485if (!NewBB2Preds.
empty()) {
1486// Create another basic block for the rest of OrigBB's predecessors. 1492// The new block unconditionally branches to the old block. 1496// Move the remaining edges from OrigBB to point to NewBB2. 1498 NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
1500// Update DominatorTree, LoopInfo, and LCCSA analysis information. 1503 PreserveLCSSA, HasLoopExit);
1505// Update the PHI nodes in OrigBB with the values coming from NewBB2. 1519// Create a PHI node for the two cloned landingpad instructions only 1520// if the original landingpad instruction has some uses. 1523"Split cannot be applied if LPad is token type. Otherwise an " 1524"invalid PHINode of token type would be created.");
1532// There is no second clone. Just replace the landing pad with the first 1541constchar *Suffix1,
constchar *Suffix2,
1545bool PreserveLCSSA) {
1547 NewBBs, DTU,
/*DT=*/nullptr, LI, MSSAU,
1555// Clone the return and add it to the end of the predecessor. 1559// If the return instruction returns a value, and if the value was a 1560// PHI node in "BB", propagate the right value into the return. 1565// Return value might be bitcasted. Clone and insert it before the 1566// return instruction. 1567 V = BCI->getOperand(0);
1568 NewBC = BCI->
clone();
1575 V = EVI->getOperand(0);
1576 NewEV = EVI->
clone();
1586if (
PHINode *PN = dyn_cast<PHINode>(V)) {
1587if (PN->getParent() == BB) {
1589 NewEV->
setOperand(0, PN->getIncomingValueForBlock(Pred));
1591 NewBC->
setOperand(0, PN->getIncomingValueForBlock(Pred));
1593Op = PN->getIncomingValueForBlock(Pred);
1598// Update any PHI nodes in the returning block to realize that we no 1599// longer branch to them. 1604 DTU->
applyUpdates({{DominatorTree::Delete, Pred, BB}});
1606return cast<ReturnInst>(NewRet);
1616Cond, SplitBefore, &ThenBlock,
/* ElseBlock */nullptr,
1617/* UnreachableThen */ Unreachable,
1618/* UnreachableElse */false, BranchWeights, DTU, LI);
1629Cond, SplitBefore,
/* ThenBlock */nullptr, &ElseBlock,
1630/* UnreachableThen */false,
1631/* UnreachableElse */ Unreachable, BranchWeights, DTU, LI);
1643Cond, SplitBefore, &ThenBlock, &ElseBlock,
/* UnreachableThen */false,
1644/* UnreachableElse */false, BranchWeights, DTU, LI);
1652BasicBlock **ElseBlock,
bool UnreachableThen,
bool UnreachableElse,
1654assert((ThenBlock || ElseBlock) &&
1655"At least one branch block must be created");
1656assert((!UnreachableThen || !UnreachableElse) &&
1657"Split block tail must be reachable");
1664 Updates.
reserve(4 + 2 * UniqueOrigSuccessors.
size());
1671bool ThenToTailEdge =
false;
1672bool ElseToTailEdge =
false;
1674// Encapsulate the logic around creation/insertion/etc of a new block. 1678return;
// Do not create/insert a block. 1681 BB = *PBB;
// Caller supplied block, use it. 1683// Create a new block. 1691 BB->getTerminator()->
setDebugLoc(SplitBefore->getDebugLoc());
1692// Pass the new block back to the caller. 1697 handleBlock(ThenBlock, UnreachableThen, TrueBlock, ThenToTailEdge);
1698 handleBlock(ElseBlock, UnreachableElse, FalseBlock, ElseToTailEdge);
1703 HeadNewTerm->
setMetadata(LLVMContext::MD_prof, BranchWeights);
1707 Updates.
emplace_back(DominatorTree::Insert, Head, TrueBlock);
1708 Updates.
emplace_back(DominatorTree::Insert, Head, FalseBlock);
1713for (
BasicBlock *UniqueOrigSuccessor : UniqueOrigSuccessors)
1715for (
BasicBlock *UniqueOrigSuccessor : UniqueOrigSuccessors)
1716 Updates.
emplace_back(DominatorTree::Delete, Head, UniqueOrigSuccessor);
1723 L->addBasicBlockToLoop(TrueBlock, *LI);
1725 L->addBasicBlockToLoop(FalseBlock, *LI);
1726 L->addBasicBlockToLoop(
Tail, *LI);
1731std::pair<Instruction *, Value *>
1738auto *Ty =
End->getType();
1739auto &
DL = SplitBefore->getDataLayout();
1740constunsigned Bitwidth =
DL.getTypeSizeInBits(Ty);
1745 Builder.
CreateAdd(
IV, ConstantInt::get(Ty, 1),
IV->getName() +
".next",
1746/*HasNUW=*/true,
/*HasNSW=*/Bitwidth != 2);
1748IV->getName() +
".check");
1752// Populate the IV PHI. 1753IV->addIncoming(ConstantInt::get(Ty, 0), LoopPred);
1754IV->addIncoming(IVNext, LoopBody);
1763IRBuilder<> IRB(InsertBefore->getParent(), InsertBefore);
1765if (EC.isScalable()) {
1768auto [BodyIP, Index] =
1776unsigned Num = EC.getFixedValue();
1779 Func(IRB, ConstantInt::get(IndexTy,
Idx));
1787IRBuilder<> IRB(InsertBefore->getParent(), InsertBefore);
1790if (!isa<ConstantInt>(EVL)) {
1797unsigned Num = cast<ConstantInt>(EVL)->getZExtValue();
1800 Func(IRB, ConstantInt::get(Ty,
Idx));
1817if (PI == PE)
// No predecessor 1820if (PI == PE)
// Only one predecessor 1823if (PI != PE)
// More than two predecessors 1827// We can only handle branches. Other control flow will be lowered to 1828// branches if possible anyway. 1831if (!Pred1Br || !Pred2Br)
1834// Eliminate code duplication by ensuring that Pred1Br is conditional if 1837// If both branches are conditional, we don't have an "if statement". In 1838// reality, we could transform this case, but since the condition will be 1839// required anyway, we stand no chance of eliminating it, so the xform is 1840// probably not profitable. 1849// The only thing we have to watch out for here is to make sure that Pred2 1850// doesn't have incoming edges from other blocks. If it does, the condition 1851// doesn't dominate BB. 1855// If we found a conditional branch predecessor, make sure that it branches 1856// to BB and Pred2Br. If it doesn't, this isn't an "if statement". 1866// We know that one arm of the conditional goes to BB, so the other must 1867// go somewhere unrelated, and this must not be an "if statement". 1874// Ok, if we got here, both predecessors end with an unconditional branch to 1875// BB. Don't panic! If both blocks only have a single (identical) 1876// predecessor, and THAT is a conditional branch, then we're all ok! 1881// Otherwise, if this is a conditional branch, then we can use it! 1883if (!BI)
returnnullptr;
1898// If this is a "cmp" instruction, only used for branching (and nowhere 1899// else), then we can simply invert the predicate. 1900if (NewCond->
hasOneUse() && isa<CmpInst>(NewCond)) {
1901CmpInst *CI = cast<CmpInst>(NewCond);
1912auto *Term = BB.getTerminator();
1913if (!(isa<ReturnInst>(Term) || isa<UnreachableInst>(Term) ||
1914 isa<BranchInst>(Term)))
1923if (!Src.getParent()->isPresplitCoroutine())
1925if (
auto *SW = dyn_cast<SwitchInst>(Src.getTerminator()))
1926if (
auto *
Intr = dyn_cast<IntrinsicInst>(SW->getCondition()))
1927returnIntr->getIntrinsicID() == Intrinsic::coro_suspend &&
1928 SW->getDefaultDest() == &Dest;
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static BasicBlock * SplitBlockPredecessorsImpl(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
static bool removeRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB)
static BasicBlock * SplitBlockImpl(BasicBlock *Old, BasicBlock::iterator SplitPt, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName, bool Before)
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 bool removeUndefDbgAssignsFromEntryBlock(BasicBlock *BB)
Remove redundant undef dbg.assign intrinsic from an entry block using a forward scan.
static bool DbgVariableRecordsRemoveRedundantDbgInstrsUsingForwardScan(BasicBlock *BB)
Remove redundant dbg.value instructions using a forward scan.
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 bool DbgVariableRecordsRemoveUndefDbgAssignsFromEntryBlock(BasicBlock *BB)
static bool DbgVariableRecordsRemoveRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB)
Remove redundant instructions within sequences of consecutive dbg.value instructions.
static bool removeRedundantDbgInstrsUsingForwardScan(BasicBlock *BB)
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
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
uint64_t IntrinsicInst * II
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
static const uint32_t IV[8]
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - Get the array size.
bool empty() const
empty - Check if the array is empty.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const LandingPadInst * getLandingPadInst() const
Return the landingpad instruction associated with the landing pad.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
InstListType::const_iterator getFirstNonPHIIt() const
Iterator returning form of getFirstNonPHI.
const Instruction & front() const
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
bool isEntryBlock() const
Return true if this is the entry block of the containing function.
InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
const Function * getParent() const
Return the enclosing method, or null if none.
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
bool IsNewDbgInfoFormat
Flag recording whether or not this block stores debug-info in the form of intrinsic instructions (fal...
bool isLandingPad() const
Return true if this basic block is a landing pad.
bool isEHPad() const
Return true if this basic block is an exception handling block.
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...
bool canSplitPredecessors() const
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
const Instruction & back() const
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
This class represents a no-op cast from one type to another.
Conditional or Unconditional Branch instruction.
void setCondition(Value *V)
void swapSuccessors()
Swap the successors of this branch instruction.
bool isConditional() const
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() const
static CleanupPadInst * Create(Value *ParentPad, ArrayRef< Value * > Args={}, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
static CleanupReturnInst * Create(Value *CleanupPad, BasicBlock *UnwindBB=nullptr, InsertPosition InsertBefore=nullptr)
This class is the base class for the comparison instructions.
void setPredicate(Predicate P)
Set the predicate for this instruction to the specified value.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
This class represents an Operation in the Expression.
This represents the llvm.dbg.assign instruction.
Base class for non-instruction debug metadata records that have positions within IR.
DebugLoc getDebugLoc() const
This represents the llvm.dbg.value instruction.
bool isKillLocation() const
Record of a variable value-assignment, aka a non instruction representation of the dbg....
LocationType getType() const
DIExpression * getExpression() const
DILocalVariable * getVariable() const
Identifies a unique instance of a variable.
iterator find(const_arg_type_t< KeyT > Val)
Implements a dense probed hash-table based set.
iterator_range< iterator > children()
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
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.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
This instruction extracts a struct member or array element value from an aggregate value.
DomTreeT & getDomTree()
Flush DomTree updates and return DomTree.
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
bool hasDomTree() const
Returns true if it holds a DomTreeT.
void recalculate(FuncT &F)
Notify DTU that the entry block was replaced.
Module * getParent()
Get the module that this global value is contained inside of...
Common base class shared among various IRBuilders.
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
Value * CreateNot(Value *V, const Twine &Name="")
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateElementCount(Type *DstType, ElementCount EC)
Create an expression which evaluates to the number of elements in EC at runtime.
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
void moveBeforePreserving(Instruction *MovePos)
Perform a moveBefore operation, while signalling that the caller intends to preserve the original ord...
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
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.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
bool isSpecialTerminator() const
InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
unsigned getLoopDepth() const
Return the nesting level of this loop.
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
bool isLoopHeader(const BlockT *BB) const
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Represents a single loop in the control flow graph.
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 ...
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Class that has the common methods + fields of memory uses/defs.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
void removeIncomingValueIf(function_ref< bool(unsigned)> Predicate, bool DeletePHIIfEmpty=true)
Remove all incoming values for which the predicate returns true.
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
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 PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Return a value (possibly void), from a function.
Implements a dense probed hash-table based set with some number of buckets stored inline.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
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...
std::string str() const
Return the twine contents as a std::string.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isTokenTy() const
Return true if this is 'token'.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
void setOperand(unsigned i, Value *Val)
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
std::pair< iterator, bool > insert(const ValueT &V)
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
self_iterator getIterator()
#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...
@ C
The default llvm calling convention, compatible with C.
AssignmentInstRange getAssignmentInsts(DIAssignID *ID)
Return a range of instructions (typically just one) that have ID as an attachment.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
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)
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
bool succ_empty(const Instruction *I)
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...
auto pred_end(const MachineBasicBlock *BB)
void detachDeadBlocks(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs=false)
Replace contents of every block in BBs with single unreachable instruction.
bool hasOnlySimpleTerminator(const Function &F)
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...
std::pair< Instruction *, Value * > SplitBlockAndInsertSimpleForLoop(Value *End, BasicBlock::iterator SplitBefore)
Insert a for (int i = 0; i < End; i++) loop structure (with the exception that End is assumed > 0,...
BasicBlock * splitBlockBefore(BasicBlock *Old, BasicBlock::iterator SplitPt, DomTreeUpdater *DTU, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName="")
Split the specified block at the specified instruction SplitPt.
Instruction * SplitBlockAndInsertIfElse(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ElseBlock=nullptr)
Similar to SplitBlockAndInsertIfThen, but the inserted block is on the false path of the branch.
auto pred_size(const MachineBasicBlock *BB)
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...
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,...
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
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)
void InvertBranch(BranchInst *PBI, IRBuilderBase &Builder)
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.
void SplitBlockAndInsertIfThenElse(Value *Cond, BasicBlock::iterator SplitBefore, Instruction **ThenTerm, Instruction **ElseTerm, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr)
SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, but also creates the ElseBlock...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
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.
auto succ_size(const MachineBasicBlock *BB)
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...
void SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef< BasicBlock * > Preds, const char *Suffix, const char *Suffix2, SmallVectorImpl< BasicBlock * > &NewBBs, DomTreeUpdater *DTU=nullptr, 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...
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
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.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
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.
DWARFExpression::Operation Op
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.
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 pred_begin(const MachineBasicBlock *BB)
bool isPresplitCoroSuspendExitEdge(const BasicBlock &Src, const BasicBlock &Dest)
BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
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...
Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
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...
void setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ)
Sets the unwind edge of an instruction to a particular successor.
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
void SplitBlockAndInsertForEachLane(ElementCount EC, Type *IndexTy, BasicBlock::iterator InsertBefore, std::function< void(IRBuilderBase &, Value *)> Func)
Utility function for performing a given action on each lane of a vector with EC elements.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Option class for critical edge splitting.
CriticalEdgeSplittingOptions & setPreserveLCSSA()
