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//===----------------------------------------------------------------------===//
53 #define DEBUG_TYPE "basicblock-utils"
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"));
61/// Zap all the instructions in the block and replace them with an unreachable
62/// instruction and notify the basic block's successors that one of their
63/// predecessors is going away.
67 bool KeepOneInputPHIs) {
68 // Loop through all of our successors and make sure they know that one
69 // of their predecessors is going away.
72 Succ->removePredecessor(BB, KeepOneInputPHIs);
73 if (Updates && UniqueSuccessors.
insert(Succ).second)
77 // Zap all the instructions in the block.
78 while (!BB->
empty()) {
80 // If this instruction is used, replace uses with an arbitrary value.
81 // Because control flow can't get here, we don't care what we replace the
82 // value with. Note that since this block is unreachable, and all values
83 // contained within it must dominate their uses, that all uses will
84 // eventually be removed (they are themselves dead).
91 "The successor list of BB isn't empty before "
92 "applying corresponding DTU updates.");
97 bool KeepOneInputPHIs) {
99 for (
auto *BB : BBs) {
100 auto NonFirstPhiIt = BB->getFirstNonPHIIt();
101 if (NonFirstPhiIt != BB->end()) {
103 // Exception handling funclets need to be explicitly addressed.
104 // These funclets must begin with cleanuppad or catchpad and end with
105 // cleanupred or catchret. The return instructions can be in different
106 // basic blocks than the pad instruction. If we would only delete the
107 // first block, the we would have possible cleanupret and catchret
108 // instructions with poison arguments, which wouldn't be valid.
110 UniqueEHRetBlocksToDelete.
clear();
114 // If we have a cleanupret or catchret block, replace it with just an
115 // unreachable. The other alternative, that may use a catchpad is a
116 // catchswitch. That does not need special handling for now.
120 UniqueEHRetBlocksToDelete.
insert(ReturnInstrBB);
124 for (
BasicBlock *EHRetBB : UniqueEHRetBlocksToDelete)
129 UniqueEHRetBlocksToDelete.
clear();
131 // Detaching and emptying the current basic block.
137 bool KeepOneInputPHIs) {
142 bool KeepOneInputPHIs) {
144 // Make sure that all predecessors of each dead block is also dead.
146 assert(Dead.size() == BBs.
size() &&
"Duplicating blocks?");
147 for (
auto *BB : Dead)
149 assert(Dead.count(Pred) &&
"All predecessors must be dead!");
162 BB->eraseFromParent();
166 bool KeepOneInputPHIs) {
169 // Mark all reachable blocks.
171 (void)BB
/* Mark all reachable blocks */;
173 // Collect all dead blocks.
174 std::vector<BasicBlock*> DeadBlocks;
176 if (!Reachable.count(&BB))
177 DeadBlocks.push_back(&BB);
179 // Delete the dead blocks.
182 return !DeadBlocks.empty();
191 if (PN->getIncomingValue(0) != PN)
192 PN->replaceAllUsesWith(PN->getIncomingValue(0));
199 PN->eraseFromParent();
206 // Recursively deleting a PHI may cause multiple PHIs to be deleted
207 // or RAUW'd undef, so use an array of WeakTrackingVH for the PHIs to delete.
211 for (
const auto &
PHI : PHIs)
221 bool PredecessorWithTwoSuccessors,
226 // Can't merge if there are multiple predecessors, or no predecessors.
228 if (!PredBB)
return false;
230 // Don't break self-loops.
231 if (PredBB == BB)
return false;
233 // Don't break unwinding instructions or terminators with other side-effects.
238 // Can't merge if there are multiple distinct successors.
242 // Currently only allow PredBB to have two predecessors, one being BB.
243 // Update BI to branch to BB's only successor instead of BB.
246 unsigned FallThruPath;
247 if (PredecessorWithTwoSuccessors) {
254 FallThruPath = PredBB_BI->
getSuccessor(0) == BB ? 0 : 1;
257 // Can't merge if there is PHI loop.
265 // Begin by getting rid of unneeded PHIs.
271 IncomingValues.
push_back(PN.getIncomingValue(0));
276 assert(!DTU &&
"cannot use both DT and DTU for updates");
280 assert(BBNode &&
"PredNode unreachable but BBNode reachable?");
282 C->setIDom(PredNode);
285 // DTU update: Collect all the edges that exit BB.
286 // These dominator edges will be redirected from Pred.
287 std::vector<DominatorTree::UpdateType> Updates;
289 assert(!DT &&
"cannot use both DT and DTU for updates");
290 // To avoid processing the same predecessor more than once.
294 Updates.reserve(Updates.size() + 2 *
succ_size(BB) + 1);
295 // Add insert edges first. Experimentally, for the particular case of two
296 // blocks that can be merged, with a single successor and single predecessor
297 // respectively, it is beneficial to have all insert updates first. Deleting
298 // edges first may lead to unreachable blocks, followed by inserting edges
299 // making the blocks reachable again. Such DT updates lead to high compile
300 // times. We add inserts before deletes here to reduce compile time.
302 // This successor of BB may already be a PredBB's successor.
303 if (!SuccsOfPredBB.
contains(SuccOfBB))
304 if (SeenSuccs.
insert(SuccOfBB).second)
308 if (SeenSuccs.
insert(SuccOfBB).second)
315 // If there's nothing to move, mark the starting instruction as the last
316 // instruction in the block. Terminator instruction is handled separately.
320 // Move all definitions in the successor to the predecessor...
326 // Make all PHI nodes that referred to BB now refer to Pred as their
330 if (PredecessorWithTwoSuccessors) {
331 // Delete the unconditional branch from BB.
334 // Update branch in the predecessor.
337 // Delete the unconditional branch from the predecessor.
340 // Move terminator instruction.
343 // Terminator may be a memory accessing instruction too.
349 // Add unreachable to now empty BB.
352 // Inherit predecessors name if it exists.
367 "successors should have been transferred to PredBB");
371 // Finally, erase the old block and update dominator info.
380 assert(!MergeBlocks.
empty() &&
"MergeBlocks should not be empty");
382 bool BlocksHaveBeenMerged =
false;
383 while (!MergeBlocks.
empty()) {
386 if (Dest && (!L || L->contains(Dest))) {
391 "Expecting BB to be unique predecessor of the Dest block");
392 MergeBlocks.
erase(Dest);
393 BlocksHaveBeenMerged =
true;
395 MergeBlocks.
erase(BB);
397 MergeBlocks.
erase(BB);
399 return BlocksHaveBeenMerged;
402/// Remove redundant instructions within sequences of consecutive dbg.value
403/// instructions. This is done using a backward scan to keep the last dbg.value
404/// describing a specific variable/fragment.
406/// BackwardScan strategy:
407/// ----------------------
408/// Given a sequence of consecutive DbgValueInst like this
410/// dbg.value ..., "x", FragmentX1 (*)
411/// dbg.value ..., "y", FragmentY1
412/// dbg.value ..., "x", FragmentX2
413/// dbg.value ..., "x", FragmentX1 (**)
415/// then the instruction marked with (*) can be removed (it is guaranteed to be
416/// obsoleted by the instruction marked with (**) as the latter instruction is
417/// describing the same variable using the same fragment info).
419/// Possible improvements:
420/// - Check fully overlapping fragments and not only identical fragments.
428 DVR.getDebugLoc()->getInlinedAt());
430 // If the same variable fragment is described more than once it is enough
431 // to keep the last one (i.e. the first found since we for reverse
436 if (DVR.isDbgAssign()) {
437 // Don't delete dbg.assign intrinsics that are linked to instructions.
440 // Unlinked dbg.assign intrinsics can be treated like dbg.values.
445 // Sequence with consecutive dbg.value instrs ended. Clear the map to
446 // restart identifying redundant instructions if case we find another
447 // dbg.value sequence.
451 for (
auto &DVR : ToBeRemoved)
452 DVR->eraseFromParent();
454 return !ToBeRemoved.
empty();
457/// Remove redundant dbg.value instructions using a forward scan. This can
458/// remove a dbg.value instruction that is redundant due to indicating that a
459/// variable has the same value as already being indicated by an earlier
462/// ForwardScan strategy:
463/// ---------------------
464/// Given two identical dbg.value instructions, separated by a block of
465/// instructions that isn't describing the same variable, like this
467/// dbg.value X1, "x", FragmentX1 (**)
468/// <block of instructions, none being "dbg.value ..., "x", ...">
469/// dbg.value X1, "x", FragmentX1 (*)
471/// then the instruction marked with (*) can be removed. Variable "x" is already
472/// described as being mapped to the SSA value X1.
474/// Possible improvements:
475/// - Keep track of non-overlapping fragments.
477 bool RemovedAny =
false;
481 for (
auto &
I : *BB) {
487 DVR.getDebugLoc()->getInlinedAt());
489 // A dbg.assign with no linked instructions can be treated like a
490 // dbg.value (i.e. can be deleted).
491 bool IsDbgValueKind =
494 // Update the map if we found a new value/expression describing the
495 // variable, or if the variable wasn't mapped already.
497 if (Inserted || VMI->second.first != Values ||
498 VMI->second.second != DVR.getExpression()) {
500 VMI->second = {Values, DVR.getExpression()};
502 VMI->second = {Values,
nullptr};
505 // Don't delete dbg.assign intrinsics that are linked to instructions.
508 // Found an identical mapping. Remember the instruction for later removal.
509 DVR.eraseFromParent();
517/// Remove redundant undef dbg.assign intrinsic from an entry block using a
520/// ---------------------
521/// Scanning forward, delete dbg.assign intrinsics iff they are undef, not
522/// linked to an intrinsic, and don't share an aggregate variable with a debug
523/// intrinsic that didn't meet the criteria. In other words, undef dbg.assigns
524/// that come before non-undef debug intrinsics for the variable are
527/// dbg.assign undef, "x", FragmentX1 (*)
528/// <block of instructions, none being "dbg.value ..., "x", ...">
529/// dbg.value %V, "x", FragmentX2
530/// <block of instructions, none being "dbg.value ..., "x", ...">
531/// dbg.assign undef, "x", FragmentX1
533/// then (only) the instruction marked with (*) can be removed.
534/// Possible improvements:
535/// - Keep track of non-overlapping fragments.
538 bool RemovedAny =
false;
541 // Remove undef dbg.assign intrinsics that are encountered before
542 // any non-undef intrinsics from the entry block.
543 for (
auto &
I : *BB) {
546 if (!DVR.isDbgValue() && !DVR.isDbgAssign())
548 bool IsDbgValueKind =
552 if (!SeenDefForAggregate.
contains(Aggregate)) {
553 bool IsKill = DVR.isKillLocation() && IsDbgValueKind;
555 SeenDefForAggregate.
insert(Aggregate);
556 }
else if (DVR.isDbgAssign()) {
557 DVR.eraseFromParent();
568 bool MadeChanges =
false;
569 // By using the "backward scan" strategy before the "forward scan" strategy we
570 // can remove both dbg.value (2) and (3) in a situation like this:
572 // (1) dbg.value V1, "x", DIExpression()
574 // (2) dbg.value V2, "x", DIExpression()
575 // (3) dbg.value V1, "x", DIExpression()
577 // The backward scan will remove (2), it is made obsolete by (3). After
578 // getting (2) out of the way, the foward scan will remove (3) since "x"
579 // already is described as having the value V1 at (1).
594 // Replaces all of the uses of the instruction with uses of the value
595 I.replaceAllUsesWith(V);
597 // Make sure to propagate a name if there is one already.
598 if (
I.hasName() && !V->hasName())
601 // Delete the unnecessary instruction now...
602 BI = BI->eraseFromParent();
607 assert(
I->getParent() ==
nullptr &&
608 "ReplaceInstWithInst: Instruction already inserted into basic block!");
610 // Copy debug location to newly added instruction, if it wasn't already set
612 if (!
I->getDebugLoc())
613 I->setDebugLoc(BI->getDebugLoc());
615 // Insert the new instruction into the basic block...
618 // Replace all uses of the old instruction, and delete it.
621 // Move BI back to point to the newly inserted instruction
626 // Remember visited blocks to avoid infinite loop
646 const Twine &BBName) {
655 // If this is a critical edge, let SplitKnownCriticalEdge do it.
659 // If the edge isn't critical, then BB has a single successor or Succ has a
660 // single pred. Split the block.
662 // If the successor only has a single pred, split the top of the successor
664 assert(SP == BB &&
"CFG broken");
670 // Otherwise, if BB has a single successor, split it at the bottom of the
673 "Should have a single succ!");
677/// Helper function to update the cycle or loop information after inserting a
678/// new block between a callbr instruction and one of its target blocks. Adds
679/// the new block to the innermost cycle or loop that the callbr instruction and
680/// the original target block share.
681/// \p LCI cycle or loop information to update
682/// \p CallBrBlock block containing the callbr instruction
683/// \p CallBrTarget new target block of the callbr instruction
684/// \p Succ original target block of the callbr instruction
685template <
typename TI,
typename T>
688 static_assert(std::is_same_v<TI, CycleInfo> || std::is_same_v<TI, LoopInfo>,
689 "type must be CycleInfo or LoopInfo");
694 if constexpr (std::is_same_v<TI, CycleInfo>)
695 LC = LCI->getSmallestCommonCycle(CallBrBlock, Succ);
697 LC = LCI->getSmallestCommonLoop(CallBrBlock, Succ);
701 if constexpr (std::is_same_v<TI, CycleInfo>)
702 LCI->addBlockToCycle(CallBrTarget, LC);
704 LC->addBasicBlockToLoop(CallBrTarget, *LCI);
714 assert(CallBr &&
"expected callbr terminator");
715 assert(SuccIdx < CallBr->getNumSuccessors() &&
716 Succ == CallBr->
getSuccessor(SuccIdx) &&
"invalid successor index");
718 // Create a new block between callbr and the specified successor.
719 // splitBlockBefore cannot be re-used here since it cannot split if the split
720 // point is a PHI node (because BasicBlock::splitBasicBlockBefore cannot
721 // handle that). But we don't need to rewire every part of a potential PHI
722 // node. We only care about the edge between CallBrBlock and the original
728 // Rewire control flow from the new target block to the original successor.
730 // Rewire control flow from callbr to the new target block.
732 // Jump from the new target block to the original successor.
738 *UpdatedLI = Updated;
752 II->setUnwindDest(Succ);
754 CS->setUnwindDest(Succ);
756 CR->setUnwindDest(Succ);
765 // We manually update the LandingPadReplacement PHINode and it is the last
766 // PHI Node. So, if we find it, we are done.
770 // Reuse the previous value of BBIdx if it lines up. In cases where we
771 // have multiple phi nodes with *lots* of predecessors, this is a speed
772 // win because we don't have to scan the PHI looking for TIBB. This
773 // happens because the BB list of PHI nodes are usually in the same
775 if (PN.getIncomingBlock(BBIdx) != OldPred)
776 BBIdx = PN.getBasicBlockIndex(OldPred);
778 assert(BBIdx != -1 &&
"Invalid PHI Index!");
779 PN.setIncomingBlock(BBIdx, NewPred);
785 PHINode *LandingPadReplacement,
787 const Twine &BBName) {
790 if (!LandingPadReplacement && !PadInst->
isEHPad())
795 // Check if extra modifications will be required to preserve loop-simplify
796 // form after splitting. If it would require splitting blocks with IndirectBr
797 // terminators, bail out if preserving loop-simplify form is requested.
798 if (
Options.PreserveLoopSimplify && LI) {
799 if (
Loop *BBLoop = LI->getLoopFor(BB)) {
801 // The only way that we can break LoopSimplify form by splitting a
802 // critical edge is when there exists some edge from BBLoop to Succ *and*
803 // the only edge into Succ from outside of BBLoop is that of NewBB after
804 // the split. If the first isn't true, then LoopSimplify still holds,
805 // NewBB is the new exit block and it has no non-loop predecessors. If the
806 // second isn't true, then Succ was not in LoopSimplify form prior to
807 // the split as it had a non-loop predecessor. In both of these cases,
808 // the predecessor must be directly in BBLoop, not in a subloop, or again
809 // LoopSimplify doesn't hold.
812 continue;
// The new block is known.
813 if (LI->getLoopFor(
P) != BBLoop) {
814 // Loop is not in LoopSimplify form, no need to re simplify after
821 // Loop-simplify form can be preserved, if we can split all in-loop
836 if (LandingPadReplacement) {
837 auto *NewLP = OriginalPad->
clone();
839 NewLP->insertBefore(Terminator->getIterator());
842 Value *ParentPad =
nullptr;
844 ParentPad = FuncletPad->getParentPad();
846 ParentPad = CatchSwitch->getParentPad();
848 ParentPad = CleanupPad->getParentPad();
850 ParentPad = LandingPad->getParent();
875 MSSAU->applyUpdates(Updates, *DT);
877 MSSAU->getMemorySSA()->verifyMemorySSA();
882 if (
Loop *BBLoop = LI->getLoopFor(BB)) {
883 // If one or the other blocks were not in a loop, the new block is not
884 // either, and thus LI doesn't need to be updated.
885 if (
Loop *SuccLoop = LI->getLoopFor(Succ)) {
886 if (BBLoop == SuccLoop) {
887 // Both in the same loop, the NewBB joins loop.
888 SuccLoop->addBasicBlockToLoop(NewBB, *LI);
889 }
else if (BBLoop->contains(SuccLoop)) {
890 // Edge from an outer loop to an inner loop. Add to the outer loop.
891 BBLoop->addBasicBlockToLoop(NewBB, *LI);
892 }
else if (SuccLoop->contains(BBLoop)) {
893 // Edge from an inner loop to an outer loop. Add to the outer loop.
894 SuccLoop->addBasicBlockToLoop(NewBB, *LI);
896 // Edge from two loops with no containment relation. Because these
897 // are natural loops, we know that the destination block must be the
898 // header of its loop (adding a branch into a loop elsewhere would
899 // create an irreducible loop).
900 assert(SuccLoop->getHeader() == Succ &&
901 "Should not create irreducible loops!");
902 if (
Loop *
P = SuccLoop->getParentLoop())
903 P->addBasicBlockToLoop(NewBB, *LI);
907 // If BB is in a loop and Succ is outside of that loop, we may need to
908 // update LoopSimplify form and LCSSA form.
909 if (!BBLoop->contains(Succ)) {
910 assert(!BBLoop->contains(NewBB) &&
911 "Split point for loop exit is contained in loop!");
913 // Update LCSSA form in the newly created exit block.
918 if (!LoopPreds.
empty()) {
920 Succ, LoopPreds,
"split", DT, LI, MSSAU,
Options.PreserveLCSSA);
933 // SplitBB shouldn't have anything non-trivial in it yet.
936 "SplitBB has non-PHI nodes!");
938 // For each PHI in the destination block.
940 int Idx = PN.getBasicBlockIndex(SplitBB);
941 assert(Idx >= 0 &&
"Invalid Block Index");
942 Value *V = PN.getIncomingValue(Idx);
944 // If the input is a PHI which already satisfies LCSSA, don't create
947 if (VP->getParent() == SplitBB)
950 // Otherwise a new PHI is needed. Create one and populate it.
959 // Update the original PHI.
960 PN.setIncomingValue(Idx, NewPN);
967 unsigned NumBroken = 0;
981 const Twine &BBName,
bool Before) {
983 DomTreeUpdater LocalDTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
985 DTU ? DTU : (DT ? &LocalDTU :
nullptr), LI, MSSAU,
991 assert(SplitIt != SplitPt->getParent()->end());
993 std::string Name = BBName.
str();
995 SplitIt, Name.empty() ? Old->
getName() +
".split" : Name);
997 // The new block lives in whichever loop the old one did. This preserves
998 // LCSSA as well, because we force the split point to be after any PHI nodes.
1001 L->addBasicBlockToLoop(New, *LI);
1005 // Old dominates New. New node dominates all other nodes dominated by Old.
1010 if (UniqueSuccessorsOfOld.
insert(SuccessorOfOld).second) {
1017 // Old dominates New. New node dominates all other nodes dominated by Old.
1019 std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
1026 // Move MemoryAccesses still tracked in Old, but part of New now.
1027 // Update accesses in successor blocks accordingly.
1038 return SplitBlockImpl(Old, SplitPt,
/*DTU=*/nullptr, DT, LI, MSSAU, BBName,
1045 return SplitBlockImpl(Old, SplitPt, DTU,
/*DT=*/nullptr, LI, MSSAU, BBName,
1052 const Twine &BBName) {
1057 std::string Name = BBName.
str();
1059 SplitIt, Name.empty() ? Old->
getName() +
".split" : Name,
1062 // The new block lives in whichever loop the old one did. This preserves
1063 // LCSSA as well, because we force the split point to be after any PHI nodes.
1066 L->addBasicBlockToLoop(New, *LI);
1070 // New dominates Old. The predecessor nodes of the Old node dominate
1076 if (UniquePredecessorsOfOld.
insert(PredecessorOfOld).second) {
1083 // Move MemoryAccesses still tracked in Old, but part of New now.
1084 // Update accesses in successor blocks accordingly.
1094/// Update DominatorTree, LoopInfo, and LCCSA analysis information.
1095/// Invalidates DFS Numbering when DTU or DT is provided.
1100 bool PreserveLCSSA,
bool &HasLoopExit) {
1101 // Update dominator tree if available.
1103 // Recalculation of DomTree is needed when updating a forward DomTree and
1104 // the Entry BB is replaced.
1106 // The entry block was removed and there is no external interface for
1107 // the dominator tree to be notified of this change. In this corner-case
1108 // we recalculate the entire tree.
1111 // Split block expects NewBB to have a non-empty set of predecessors.
1116 for (
auto *Pred : Preds)
1117 if (UniquePreds.
insert(Pred).second) {
1128 // Split block expects NewBB to have a non-empty set of predecessors.
1133 // Update MemoryPhis after split if MemorySSA is available
1137 // The rest of the logic is only relevant for updating the loop structures.
1143 assert(DT &&
"DT should be available to update LoopInfo!");
1146 // If we need to preserve loop analyses, collect some information about how
1147 // this split will affect loops.
1148 bool IsLoopEntry = !!L;
1149 bool SplitMakesNewLoopHeader =
false;
1151 // Preds that are not reachable from entry should not be used to identify if
1152 // OldBB is a loop entry or if SplitMakesNewLoopHeader. Unreachable blocks
1153 // are not within any loops, so we incorrectly mark SplitMakesNewLoopHeader
1154 // as true and make the NewBB the header of some loop. This breaks LI.
1157 // If we need to preserve LCSSA, determine if any of the preds is a loop
1161 if (!PL->contains(OldBB))
1164 // If we need to preserve LoopInfo, note whether any of the preds crosses
1165 // an interesting loop boundary.
1168 if (L->contains(Pred))
1169 IsLoopEntry =
false;
1171 SplitMakesNewLoopHeader =
true;
1174 // Unless we have a loop for OldBB, nothing else to do here.
1179 // Add the new block to the nearest enclosing loop (and not an adjacent
1180 // loop). To find this, examine each of the predecessors and determine which
1181 // loops enclose them, and select the most-nested loop which contains the
1182 // loop containing the block being split.
1183 Loop *InnermostPredLoop =
nullptr;
1186 // Seek a loop which actually contains the block being split (to avoid
1188 while (PredLoop && !PredLoop->contains(OldBB))
1189 PredLoop = PredLoop->getParentLoop();
1191 // Select the most-nested of these loops which contains the block.
1192 if (PredLoop && PredLoop->contains(OldBB) &&
1193 (!InnermostPredLoop ||
1194 InnermostPredLoop->
getLoopDepth() < PredLoop->getLoopDepth()))
1195 InnermostPredLoop = PredLoop;
1199 if (InnermostPredLoop)
1202 L->addBasicBlockToLoop(NewBB, *LI);
1203 if (SplitMakesNewLoopHeader)
1204 L->moveToHeader(NewBB);
1208/// Update the PHI nodes in OrigBB to include the values coming from NewBB.
1209/// This also updates AliasAnalysis, if available.
1213 // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB.
1218 // Check to see if all of the values coming in are the same. If so, we
1219 // don't need to create a new PHI node, unless it's needed for LCSSA.
1220 Value *InVal =
nullptr;
1236 // If all incoming values for the new PHI would be the same, just don't
1237 // make a new PHI. Instead, just remove the incoming values from the old
1243 /* DeletePHIIfEmpty */ false);
1245 // Add an incoming value to the PHI node in the loop for the preheader
1251 // If the values coming into the block are not the same, we need a new
1253 // Create the new PHI node, insert it into NewBB at the end of the block
1257 // NOTE! This loop walks backwards for a reason! First off, this minimizes
1258 // the cost of removal if we end up removing a large number of values, and
1259 // second off, this ensures that the indices for the incoming values aren't
1260 // invalidated when we remove one.
1263 if (PredSet.
count(IncomingBB)) {
1284 // Do not attempt to split that which cannot be split.
1288 // For the landingpads we need to act a bit differently.
1289 // Delegate this work to the SplitLandingPadPredecessors.
1292 std::string NewName = std::string(Suffix) +
".split-lp";
1295 DTU, DT, LI, MSSAU, PreserveLCSSA);
1299 // Create new basic block, insert right before the original block.
1303 // The new block unconditionally branches to the old block.
1308 // Splitting the predecessors of a loop header creates a preheader block.
1311 // Using the loop start line number prevents debuggers stepping into the
1312 // loop body for this instruction.
1315 // If BB is the header of the Loop, it is possible that the loop is
1316 // modified, such that the current latch does not remain the latch of the
1317 // loop. If that is the case, the loop metadata from the current latch needs
1318 // to be applied to the new latch.
1319 OldLatch = L->getLoopLatch();
1323 // Move the edges from Preds to point to NewBB instead of BB.
1325 // This is slightly more strict than necessary; the minimum requirement
1326 // is that there be no more than one indirectbr branching to BB. And
1327 // all BlockAddress uses would need to be updated.
1329 "Cannot split an edge from an IndirectBrInst");
1330 Pred->getTerminator()->replaceSuccessorWith(BB, NewBB);
1333 // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
1334 // node becomes an incoming value for BB's phi node. However, if the Preds
1335 // list is empty, we need to insert dummy entries into the PHI nodes in BB to
1336 // account for the newly created predecessor.
1337 if (Preds.
empty()) {
1338 // Insert dummy values as the incoming value.
1343 // Update DominatorTree, LoopInfo, and LCCSA analysis information.
1344 bool HasLoopExit =
false;
1348 if (!Preds.
empty()) {
1349 // Update the PHI nodes in BB with the values coming from NewBB.
1355 if (NewLatch != OldLatch) {
1358 // It's still possible that OldLatch is the latch of another inner loop,
1359 // in which case we do not remove the metadata.
1373 bool PreserveLCSSA) {
1375 MSSAU, PreserveLCSSA);
1382 bool PreserveLCSSA) {
1384 /*DT=*/nullptr, LI, MSSAU, PreserveLCSSA);
1394 // Create a new basic block for OrigBB's predecessors listed in Preds. Insert
1395 // it right before the original block.
1401 // The new block unconditionally branches to the old block.
1405 // Move the edges from Preds to point to NewBB1 instead of OrigBB.
1407 // This is slightly more strict than necessary; the minimum requirement
1408 // is that there be no more than one indirectbr branching to BB. And
1409 // all BlockAddress uses would need to be updated.
1411 "Cannot split an edge from an IndirectBrInst");
1412 Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
1415 bool HasLoopExit =
false;
1417 PreserveLCSSA, HasLoopExit);
1419 // Update the PHI nodes in OrigBB with the values coming from NewBB1.
1422 // Move the remaining edges from OrigBB to point to NewBB2.
1427 if (Pred == NewBB1)
continue;
1429 "Cannot split an edge from an IndirectBrInst");
1435 if (!NewBB2Preds.
empty()) {
1436 // Create another basic block for the rest of OrigBB's predecessors.
1442 // The new block unconditionally branches to the old block.
1446 // Move the remaining edges from OrigBB to point to NewBB2.
1448 NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
1450 // Update DominatorTree, LoopInfo, and LCCSA analysis information.
1451 HasLoopExit =
false;
1453 PreserveLCSSA, HasLoopExit);
1455 // Update the PHI nodes in OrigBB with the values coming from NewBB2.
1469 // Create a PHI node for the two cloned landingpad instructions only
1470 // if the original landingpad instruction has some uses.
1473 "Split cannot be applied if LPad is token type. Otherwise an "
1474 "invalid PHINode of token type would be created.");
1482 // There is no second clone. Just replace the landing pad with the first
1491 const char *Suffix1,
const char *Suffix2,
1495 bool PreserveLCSSA) {
1497 NewBBs, DTU,
/*DT=*/nullptr, LI, MSSAU,
1504 Instruction *UncondBranch = Pred->getTerminator();
1505 // Clone the return and add it to the end of the predecessor.
1509 // If the return instruction returns a value, and if the value was a
1510 // PHI node in "BB", propagate the right value into the return.
1515 // Return value might be bitcasted. Clone and insert it before the
1516 // return instruction.
1517 V = BCI->getOperand(0);
1518 NewBC = BCI->
clone();
1525 V = EVI->getOperand(0);
1526 NewEV = EVI->
clone();
1537 if (PN->getParent() == BB) {
1539 NewEV->
setOperand(0, PN->getIncomingValueForBlock(Pred));
1541 NewBC->
setOperand(0, PN->getIncomingValueForBlock(Pred));
1543 Op = PN->getIncomingValueForBlock(Pred);
1548 // Update any PHI nodes in the returning block to realize that we no
1549 // longer branch to them.
1566 Cond, SplitBefore, &ThenBlock,
/* ElseBlock */ nullptr,
1567 /* UnreachableThen */ Unreachable,
1568 /* UnreachableElse */ false, BranchWeights, DTU, LI);
1579 Cond, SplitBefore,
/* ThenBlock */ nullptr, &ElseBlock,
1580 /* UnreachableThen */ false,
1581 /* UnreachableElse */ Unreachable, BranchWeights, DTU, LI);
1593 Cond, SplitBefore, &ThenBlock, &ElseBlock,
/* UnreachableThen */ false,
1594 /* UnreachableElse */ false, BranchWeights, DTU, LI);
1602 BasicBlock **ElseBlock,
bool UnreachableThen,
bool UnreachableElse,
1604 assert((ThenBlock || ElseBlock) &&
1605 "At least one branch block must be created");
1606 assert((!UnreachableThen || !UnreachableElse) &&
1607 "Split block tail must be reachable");
1614 Updates.
reserve(4 + 2 * UniqueOrigSuccessors.
size());
1621 bool ThenToTailEdge =
false;
1622 bool ElseToTailEdge =
false;
1624 // Encapsulate the logic around creation/insertion/etc of a new block.
1628 return;
// Do not create/insert a block.
1631 BB = *PBB;
// Caller supplied block, use it.
1633 // Create a new block.
1641 BB->getTerminator()->
setDebugLoc(SplitBefore->getDebugLoc());
1642 // Pass the new block back to the caller.
1647 handleBlock(ThenBlock, UnreachableThen, TrueBlock, ThenToTailEdge);
1648 handleBlock(ElseBlock, UnreachableElse, FalseBlock, ElseToTailEdge);
1653 HeadNewTerm->
setMetadata(LLVMContext::MD_prof, BranchWeights);
1663 for (
BasicBlock *UniqueOrigSuccessor : UniqueOrigSuccessors)
1665 for (
BasicBlock *UniqueOrigSuccessor : UniqueOrigSuccessors)
1673 L->addBasicBlockToLoop(TrueBlock, *LI);
1675 L->addBasicBlockToLoop(FalseBlock, *LI);
1676 L->addBasicBlockToLoop(
Tail, *LI);
1681std::pair<Instruction *, Value *>
1689 auto &
DL = SplitBefore->getDataLayout();
1690 const unsigned Bitwidth =
DL.getTypeSizeInBits(Ty);
1693 auto *
IV = Builder.CreatePHI(Ty, 2,
"iv");
1695 Builder.CreateAdd(
IV, ConstantInt::get(Ty, 1),
IV->getName() +
".next",
1696 /*HasNUW=*/true,
/*HasNSW=*/Bitwidth != 2);
1697 auto *IVCheck = Builder.CreateICmpEQ(IVNext, End,
1698 IV->getName() +
".check");
1699 Builder.CreateCondBr(IVCheck, LoopExit, LoopBody);
1702 // Populate the IV PHI.
1703 IV->addIncoming(ConstantInt::get(Ty, 0), LoopPred);
1704 IV->addIncoming(IVNext, LoopBody);
1713 IRBuilder<> IRB(InsertBefore->getParent(), InsertBefore);
1715 if (EC.isScalable()) {
1718 auto [BodyIP, Index] =
1726 unsigned Num = EC.getFixedValue();
1727 for (
unsigned Idx = 0; Idx < Num; ++Idx) {
1729 Func(IRB, ConstantInt::get(IndexTy, Idx));
1737 IRBuilder<> IRB(InsertBefore->getParent(), InsertBefore);
1748 for (
unsigned Idx = 0; Idx < Num; ++Idx) {
1750 Func(IRB, ConstantInt::get(Ty, Idx));
1767 if (PI == PE)
// No predecessor
1770 if (PI == PE)
// Only one predecessor
1773 if (PI != PE)
// More than two predecessors
1777 // We can only handle branches. Other control flow will be lowered to
1778 // branches if possible anyway.
1781 if (!Pred1Br || !Pred2Br)
1784 // Eliminate code duplication by ensuring that Pred1Br is conditional if
1787 // If both branches are conditional, we don't have an "if statement". In
1788 // reality, we could transform this case, but since the condition will be
1789 // required anyway, we stand no chance of eliminating it, so the xform is
1790 // probably not profitable.
1799 // The only thing we have to watch out for here is to make sure that Pred2
1800 // doesn't have incoming edges from other blocks. If it does, the condition
1801 // doesn't dominate BB.
1805 // If we found a conditional branch predecessor, make sure that it branches
1806 // to BB and Pred2Br. If it doesn't, this isn't an "if statement".
1816 // We know that one arm of the conditional goes to BB, so the other must
1817 // go somewhere unrelated, and this must not be an "if statement".
1824 // Ok, if we got here, both predecessors end with an unconditional branch to
1825 // BB. Don't panic! If both blocks only have a single (identical)
1826 // predecessor, and THAT is a conditional branch, then we're all ok!
1831 // Otherwise, if this is a conditional branch, then we can use it!
1833 if (!BI)
return nullptr;
1848 // If this is a "cmp" instruction, only used for branching (and nowhere
1849 // else), then we can simply invert the predicate.
1854 NewCond = Builder.CreateNot(NewCond, NewCond->
getName() +
".not");
1861 for (
auto &BB :
F) {
1862 auto *Term = BB.getTerminator();
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
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)
Remove redundant instructions within sequences of consecutive dbg.value instructions.
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 updateCycleLoopInfo(TI *LCI, BasicBlock *CallBrBlock, BasicBlock *CallBrTarget, BasicBlock *Succ)
Helper function to update the cycle or loop information after inserting a new block between a callbr ...
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 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"))
static void emptyAndDetachBlock(BasicBlock *BB, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs)
Zap all the instructions in the block and replace them with an unreachable instruction and notify the...
This file contains the declarations for the subclasses of Constant, which represent the different fla...
SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks
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
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.
LLVM_ABI const LandingPadInst * getLandingPadInst() const
Return the landingpad instruction associated with the landing pad.
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
const Instruction & back() const
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI bool isEntryBlock() const
Return true if this is the entry block of the containing function.
LLVM_ABI 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,...
LLVM_ABI BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
LLVM_ABI const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
LLVM_ABI void replacePhiUsesWith(BasicBlock *Old, BasicBlock *New)
Update all phi nodes in this basic block to refer to basic block New instead of basic block Old.
LLVM_ABI const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
LLVM_ABI const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
InstListType::iterator iterator
Instruction iterators...
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
LLVM_ABI bool isLandingPad() const
Return true if this basic block is a landing pad.
LLVM_ABI bool canSplitPredecessors() const
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...
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
LLVM_ABI 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)
LLVM_ABI 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
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
void setSuccessor(unsigned i, BasicBlock *NewSucc)
BasicBlock * getSuccessor(unsigned i) 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,...
Record of a variable value-assignment, aka a non instruction representation of the dbg....
Identifies a unique instance of a whole variable (discards/ignores fragment information).
Identifies a unique instance of a variable.
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
Implements a dense probed hash-table based set.
iterator_range< iterator > children()
LLVM_ABI 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.
static constexpr UpdateKind Delete
DomTreeNodeBase< NodeT > * setNewRoot(NodeT *BB)
Add a new node to the forward dominator tree and make it a new root.
static constexpr UpdateKind Insert
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.
LLVM_ABI bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
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.
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
LLVM_ABI Value * CreateElementCount(Type *Ty, ElementCount EC)
Create an expression which evaluates to the number of elements in EC at runtime.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
LLVM_ABI Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
LLVM_ABI void insertBefore(InstListType::iterator InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified position.
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
LLVM_ABI 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.
LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
LLVM_ABI void moveBeforePreserving(InstListType::iterator MovePos)
Perform a moveBefore operation, while signalling that the caller intends to preserve the original ord...
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
bool isSpecialTerminator() const
LLVM_ABI 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.
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.
LLVM_ABI void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was spliced into From and To.
LLVM_ABI void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT, bool UpdateDTFirst=false)
Apply CFG updates, analogous with the DT edge updates.
LLVM_ABI void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was merged into To.
LLVM_ABI void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
LLVM_ABI void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock * > Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
LLVM_ABI 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.
LLVM_ABI void removeIncomingValueIf(function_ref< bool(unsigned)> Predicate, bool DeletePHIIfEmpty=true)
Remove all incoming values for which the predicate returns true.
LLVM_ABI 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 LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Simple wrapper around std::function<void(raw_ostream&)>.
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.
void insert_range(Range &&R)
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...
LLVM_ABI 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.
LLVM_ABI 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.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVM_ABI void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI 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.
const ParentTy * getParent() const
self_iterator getIterator()
This class implements an extremely fast bulk output stream that can only output to a stream.
#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.
LLVM_ABI 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.
LLVM_ABI 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)
LLVM_ABI bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
bool succ_empty(const Instruction *I)
LLVM_ABI 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 @...
LLVM_ABI BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
LLVM_ABI 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)
LLVM_ABI void detachDeadBlocks(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs=false)
Replace contents of every block in BBs with single unreachable instruction.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI bool hasOnlySimpleTerminator(const Function &F)
auto successors(const MachineBasicBlock *BB)
LLVM_ABI 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...
constexpr from_range_t from_range
LLVM_ABI 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,...
LLVM_ABI 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.
LLVM_ABI 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.
LLVM_ABI BasicBlock * SplitCallBrEdge(BasicBlock *CallBrBlock, BasicBlock *Succ, unsigned SuccIdx, DomTreeUpdater *DTU=nullptr, CycleInfo *CI=nullptr, LoopInfo *LI=nullptr, bool *UpdatedLI=nullptr)
Create a new intermediate target block for a callbr edge.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
auto cast_or_null(const Y &Val)
auto pred_size(const MachineBasicBlock *BB)
LLVM_ABI void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
LLVM_ABI 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...
LLVM_ABI 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,...
DomTreeNodeBase< BasicBlock > DomTreeNode
auto dyn_cast_or_null(const Y &Val)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI 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)
LLVM_ABI void InvertBranch(BranchInst *PBI, IRBuilderBase &Builder)
LLVM_ABI bool EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete all basic blocks from F that are not reachable from its entry node.
LLVM_ABI bool MergeBlockSuccessorsIntoGivenBlocks(SmallPtrSetImpl< BasicBlock * > &MergeBlocks, Loop *L=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr)
Merge block(s) sucessors, if possible.
LLVM_ABI 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...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
LLVM_ABI 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...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ABI 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...
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
LLVM_ABI 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...
LLVM_ABI bool VerifyMemorySSA
Enables verification of MemorySSA.
LLVM_ABI 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.
LLVM_ABI 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.
LLVM_ABI bool isAssignmentTrackingEnabled(const Module &M)
Return true if assignment tracking is enabled for module M.
DWARFExpression::Operation Op
PredIterator< BasicBlock, Value::user_iterator > pred_iterator
LLVM_ABI 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.
LLVM_ABI bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
LLVM_ABI unsigned SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
Loop over all of the edges in the CFG, breaking critical edges as they are found.
LLVM_ABI 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.
LLVM_ABI Printable printBasicBlock(const BasicBlock *BB)
Print BasicBlock BB as an operand or print "<nullptr>" if BB is a nullptr.
auto pred_begin(const MachineBasicBlock *BB)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI 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)
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
LLVM_ABI 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...
LLVM_ABI 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 ...
LLVM_ABI void DeleteDeadBlocks(ArrayRef< BasicBlock * > BBs, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified blocks from BB.
LLVM_ABI 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...
LLVM_ABI 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.
LLVM_ABI 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.
GenericCycleInfo< SSAContext > CycleInfo
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Option class for critical edge splitting.
CriticalEdgeSplittingOptions & setPreserveLCSSA()