Lines Matching full:loop
1 ///===- SimpleLoopUnswitch.cpp - Hoist loop-invariant control flow ---------===//
69 #define DEBUG_TYPE "simple-loop-unswitch"
87 cl::desc("Forcibly enables non-trivial loop unswitching rather than "
92 cl::desc("The cost threshold for unswitching a loop."));
106 "simple-loop-unswitch-guards", cl::init(true), cl::Hidden,
107 cl::desc("If enabled, simple loop unswitching will also consider "
110 "simple-loop-unswitch-drop-non-trivial-implicit-null-checks",
115 MSSAThreshold("simple-loop-unswitch-memoryssa-threshold",
120 "freeze-loop-unswitch-cond", cl::init(true), cl::Hidden,
122 "of loop unswitch to prevent miscompilation."));
125 "simple-loop-unswitch-inject-invariant-conditions", cl::Hidden,
131 "simple-loop-unswitch-inject-invariant-condition-hotness-threshold",
132 cl::Hidden, cl::desc("Only try to inject loop invariant conditions and "
185 /// Collect all of the loop invariant input values transitively used by the
188 /// This essentially walks from a root recursively through loop variant operands
190 /// inputs which are loop invariant. For some operations these can be
191 /// re-associated and unswitched out of the loop entirely.
193 collectHomogenousInstGraphLoopInvariants(const Loop &L, Instruction &Root, in collectHomogenousInstGraphLoopInvariants()
214 // Add it to our result if loop invariant. in collectHomogenousInstGraphLoopInvariants()
235 static void replaceLoopInvariantUses(const Loop &L, Value *Invariant, in replaceLoopInvariantUses()
239 // Replace uses of LIC in the loop with the given constant. in replaceLoopInvariantUses()
244 // Replace this use within the loop body. in replaceLoopInvariantUses()
250 /// Check that all the LCSSA PHI nodes in the loop exit block have trivial
252 static bool areLoopExitPHIsLoopInvariant(const Loop &L, in areLoopExitPHIsLoopInvariant()
261 // If the incoming value for this edge isn't loop invariant the unswitch in areLoopExitPHIsLoopInvariant()
269 /// Copy a set of loop invariant values \p ToDuplicate and insert them at the
291 /// Copy a set of loop invariant values, and conditionally branch on them.
294 BasicBlock &UnswitchedSucc, BasicBlock &NormalSucc, Loop &L, in buildPartialInvariantUnswitchConditionalBranch()
312 // Get the first defining access before the loop. in buildPartialInvariantUnswitchConditionalBranch()
334 /// Rewrite the PHI nodes in an unswitched loop exit basic block.
336 /// Requires that the loop exit and unswitched basic block are the same, and
345 // When the loop exit is directly unswitched we just need to update the in rewritePHINodesForUnswitchedExitBlock()
346 // incoming basic block. We loop to handle weird cases with repeated in rewritePHINodesForUnswitchedExitBlock()
356 /// Rewrite the PHI nodes in the loop exit basic block and the split off
359 /// Because the exit block remains an exit from the loop, this rewrites the
362 /// old preheader and the loop exit.
369 "Must have different loop exit and unswitched blocks!"); in rewritePHINodesForExitAndUnswitchedBlocks()
377 // removing each one. We have to do this weird loop manually so that we in rewritePHINodesForExitAndUnswitchedBlocks()
404 /// Hoist the current loop up to the innermost loop containing a remaining exit.
406 /// Because we've removed an exit from the loop, we may have changed the set of
407 /// loops reachable and need to move the current loop up the loop nest or even
409 static void hoistLoopToNewParent(Loop &L, BasicBlock &Preheader, in hoistLoopToNewParent()
412 // If the loop is already at the top level, we can't hoist it anywhere. in hoistLoopToNewParent()
413 Loop *OldParentL = L.getParentLoop(); in hoistLoopToNewParent()
419 Loop *NewParentL = nullptr; in hoistLoopToNewParent()
421 if (Loop *ExitL = LI.getLoopFor(ExitBB)) in hoistLoopToNewParent()
428 // The new parent loop (if different) should always contain the old one. in hoistLoopToNewParent()
431 "Can only hoist this loop up the nest!"); in hoistLoopToNewParent()
433 // The preheader will need to move with the body of this loop. However, in hoistLoopToNewParent()
434 // because it isn't in this loop we also need to update the primary loop map. in hoistLoopToNewParent()
436 "Parent loop of this loop should contain this loop's preheader!"); in hoistLoopToNewParent()
439 // Remove this loop from its old parent. in hoistLoopToNewParent()
442 // Add the loop either to the new parent or as a top-level loop. in hoistLoopToNewParent()
448 // Remove this loops blocks from the old parent and every other loop up the in hoistLoopToNewParent()
451 for (Loop *OldContainingL = OldParentL; OldContainingL != NewParentL; in hoistLoopToNewParent()
462 // Because we just hoisted a loop out of this one, we have essentially in hoistLoopToNewParent()
464 // nodes for values used in the no-longer-nested loop. in hoistLoopToNewParent()
470 // loop so let's conservatively form dedicated exit blocks and figure out in hoistLoopToNewParent()
477 // Return the top-most loop containing ExitBB and having ExitBB as exiting block
478 // or the loop containing ExitBB, if there is no parent loop containing ExitBB
480 static Loop *getTopMostExitingLoop(const BasicBlock *ExitBB, in getTopMostExitingLoop()
482 Loop *TopMost = LI.getLoopFor(ExitBB); in getTopMostExitingLoop()
483 Loop *Current = TopMost; in getTopMostExitingLoop()
492 /// Unswitch a trivial branch if the condition is loop invariant.
494 /// This routine should only be called when loop code leading to the branch has
496 /// condition is invariant and one of the successors is a loop exit. This
497 /// allows us to unswitch without duplicating the loop, making it trivial.
502 /// hoists the branch above that split. Preserves loop simplified form
504 /// the loop to an unconditional branch but doesn't remove it entirely. Further
507 /// If `SE` is not null, it will be updated based on the potential loop SCEVs
509 static bool unswitchTrivialBranch(Loop &L, BranchInst &BI, DominatorTree &DT, in unswitchTrivialBranch()
515 // The loop invariant values that we want to unswitch. in unswitchTrivialBranch()
544 LLVM_DEBUG(dbgs() << " Branch doesn't exit the loop!\n"); in unswitchTrivialBranch()
551 LLVM_DEBUG(dbgs() << " Loop exit PHI's aren't loop-invariant!\n"); in unswitchTrivialBranch()
581 // loop, the loop containing the exit block and the topmost parent loop in unswitchTrivialBranch()
584 if (const Loop *ExitL = getTopMostExitingLoop(LoopExitBB, LI)) in unswitchTrivialBranch()
602 // to branch to: this is the exit block out of the loop that we are in unswitchTrivialBranch()
603 // unswitching. We need to split this if there are other loop predecessors. in unswitchTrivialBranch()
604 // Because the loop is in simplified form, *any* other predecessor is enough. in unswitchTrivialBranch()
633 // Create a new unconditional branch that will continue the loop as a new in unswitchTrivialBranch()
691 // The constant we can replace all of our invariants with inside the loop in unswitchTrivialBranch()
692 // body. If any of the invariants have a value other than this the loop won't in unswitchTrivialBranch()
699 // within the loop with a constant. in unswitchTrivialBranch()
704 // for this loop so hoist it to its correct parent if needed. in unswitchTrivialBranch()
717 /// Unswitch a trivial switch if the condition is loop invariant.
719 /// This routine should only be called when loop code leading to the switch has
721 /// condition is invariant and that at least one of the successors is a loop
722 /// exit. This allows us to unswitch without duplicating the loop, making it
731 /// and points the default at the preheader. It preserves loop simplified form
733 /// the loop by removing now-dead cases. If the default case is one of those
735 /// only unreachable. Such basic blocks, while technically loop exits, are not
738 /// in-loop successor, the switch is further simplified to an unconditional
741 /// If `SE` is not null, it will be updated based on the potential loop SCEVs
743 static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT, in unswitchTrivialSwitch()
761 // BBToCheck is not an exit block if it is inside loop L. in unswitchTrivialSwitch()
764 // BBToCheck is not trivial to unswitch if its phis aren't loop invariant. in unswitchTrivialSwitch()
794 // We may need to invalidate SCEVs for the outermost loop reached by any of in unswitchTrivialSwitch()
796 Loop *OuterL = &L; in unswitchTrivialSwitch()
799 // Check the loop containing this exit. in unswitchTrivialSwitch()
800 Loop *ExitL = getTopMostExitingLoop(DefaultExitBB, LI); in unswitchTrivialSwitch()
806 // Compute the outer loop from this exit. in unswitchTrivialSwitch()
807 Loop *ExitL = getTopMostExitingLoop(CaseI->getCaseSuccessor(), LI); in unswitchTrivialSwitch()
875 // First, we split any exit blocks with remaining in-loop predecessors. Then in unswitchTrivialSwitch()
883 // FIXME: It'd be great if we could merge this with the loop below but LLVM's in unswitchTrivialSwitch()
898 // Note that we must use a reference in the for loop so that we update the in unswitchTrivialSwitch()
905 // as it will no longer be a loop exit. No mapping necessary. in unswitchTrivialSwitch()
914 // block from the loop and a target for the unswitched condition. in unswitchTrivialSwitch()
937 // entering the loop. in unswitchTrivialSwitch()
1023 // We may have changed the nesting relationship for this loop so hoist it to in unswitchTrivialSwitch()
1036 /// This routine scans the loop to find a branch or switch which occurs before
1038 /// duplicating the loop. If a branch or switch is successfully unswitched the
1046 /// If `SE` is not null, it will be updated based on the potential loop SCEVs
1048 static bool unswitchAllTrivialConditions(Loop &L, DominatorTree &DT, in unswitchAllTrivialConditions()
1053 // If loop header has only one reachable successor we should keep looking for in unswitchAllTrivialConditions()
1055 // to constant fold conditions and merge successors into loop header (then we in unswitchAllTrivialConditions()
1058 // invariants. Folding dead branches could either eliminate the current loop in unswitchAllTrivialConditions()
1060 // after deleting branches. The following code keeps traversing loop header's in unswitchAllTrivialConditions()
1069 // volatile loads) in the part of the loop that the code *would* execute in unswitchAllTrivialConditions()
1136 // When continuing, if we exit the loop or reach a previous visited block, in unswitchAllTrivialConditions()
1144 /// Build the cloned blocks for an unswitched copy of the given loop.
1146 /// The cloned blocks are inserted before the loop preheader (`LoopPH`) and
1148 /// cloned and original loop.
1150 /// This routine handles cloning all of the necessary loop blocks and exit
1152 /// Any loop blocks or exit blocks which are dominated by a different successor
1153 /// than the one for this clone of the loop blocks can be trivially skipped. We
1168 Loop &L, BasicBlock *LoopPH, BasicBlock *SplitBB, in buildClonedLoopBlocks()
1203 // Then clone all the loop blocks, skipping the ones that aren't necessary. in buildClonedLoopBlocks()
1208 // Split all the loop exit edges so that when we clone the exit blocks, if in buildClonedLoopBlocks()
1209 // any of the exit blocks are *also* a preheader for some other loop, we in buildClonedLoopBlocks()
1210 // don't create multiple predecessors entering the loop header. in buildClonedLoopBlocks()
1218 // do because there cannot be any non-loop predecessors of a loop exit in in buildClonedLoopBlocks()
1219 // loop simplified form. in buildClonedLoopBlocks()
1333 // Loop over the incoming operands backwards so we can easily delete as we in buildClonedLoopBlocks()
1358 /// Recursively clone the specified loop and all of its children.
1360 /// The target parent loop for the clone should be provided, or can be null if
1361 /// the clone is a top-level loop. While cloning, all the blocks are mapped
1362 /// with the provided value map. The entire original loop must be present in
1363 /// the value map. The cloned loop is returned.
1364 static Loop *cloneLoopNest(Loop &OrigRootL, Loop *RootParentL, in cloneLoopNest()
1366 auto AddClonedBlocksToLoop = [&](Loop &OrigL, Loop &ClonedL) { in cloneLoopNest()
1367 assert(ClonedL.getBlocks().empty() && "Must start with an empty loop!"); in cloneLoopNest()
1377 // We specially handle the first loop because it may get cloned into in cloneLoopNest()
1379 Loop *ClonedRootL = LI.AllocateLoop(); in cloneLoopNest()
1389 // If we have a nest, we can quickly clone the entire loop nest using an in cloneLoopNest()
1392 SmallVector<std::pair<Loop *, Loop *>, 16> LoopsToClone; in cloneLoopNest()
1395 for (Loop *ChildL : llvm::reverse(OrigRootL)) in cloneLoopNest()
1398 Loop *ClonedParentL, *L; in cloneLoopNest()
1400 Loop *ClonedL = LI.AllocateLoop(); in cloneLoopNest()
1403 for (Loop *ChildL : llvm::reverse(*L)) in cloneLoopNest()
1410 /// Build the cloned loops of an original loop from unswitching.
1412 /// Because unswitching simplifies the CFG of the loop, this isn't a trivial
1413 /// operation. We need to re-verify that there even is a loop (as the backedge
1415 /// backedge set may be different. However, we know that each child loop is
1416 /// undisturbed, we only need to find where to place each child loop within
1417 /// either any parent loop or within a cloned version of the original loop.
1420 /// original loop, multiple cloned sibling loops may be created. All of them
1421 /// are returned so that the newly introduced loop nest roots can be
1423 static void buildClonedLoops(Loop &OrigL, ArrayRef<BasicBlock *> ExitBlocks, in buildClonedLoops()
1425 SmallVectorImpl<Loop *> &NonChildClonedLoops) { in buildClonedLoops()
1426 Loop *ClonedL = nullptr; in buildClonedLoops()
1435 // accurate parent loop. If we only clone exits to some parent of the in buildClonedLoops()
1436 // original parent, we want to clone into that outer loop. We also keep track in buildClonedLoops()
1438 Loop *ParentL = nullptr; in buildClonedLoops()
1440 SmallDenseMap<BasicBlock *, Loop *, 16> ExitLoopMap; in buildClonedLoops()
1444 if (Loop *ExitL = LI.getLoopFor(ExitBB)) { in buildClonedLoops()
1452 "The computed parent loop should always contain (or be) the parent of " in buildClonedLoops()
1453 "the original loop."); in buildClonedLoops()
1456 // cloned blocks out of the original loop. While not all of these will in buildClonedLoops()
1457 // necessarily be in the cloned loop, it is enough to establish that they in buildClonedLoops()
1464 // Rebuild the set of blocks that will end up in the cloned loop. We may have in buildClonedLoops()
1465 // skipped cloning some region of this loop which can in turn skip some of in buildClonedLoops()
1466 // the backedges so we have to rebuild the blocks in the loop based on the in buildClonedLoops()
1471 // The only possible non-loop header predecessor is the preheader because in buildClonedLoops()
1472 // we know we cloned the loop in simplified form. in buildClonedLoops()
1476 // Because the loop was in simplified form, the only non-loop predecessor in buildClonedLoops()
1478 assert(ClonedLoopBlocks.count(Pred) && "Found a predecessor of the loop " in buildClonedLoops()
1480 "that is not part of the loop!"); in buildClonedLoops()
1482 // Insert this block into the loop set and on the first visit (and if it in buildClonedLoops()
1489 // If we had any backedges then there *is* a cloned loop. Put the header into in buildClonedLoops()
1490 // the loop set and then walk the worklist backwards to find all the blocks in buildClonedLoops()
1491 // that remain within the loop after cloning. in buildClonedLoops()
1498 "Didn't put block into the loop set!"); in buildClonedLoops()
1503 // backedge to the loop header so we may prune out dead code within the in buildClonedLoops()
1504 // cloned loop. in buildClonedLoops()
1521 // We don't want to just add the cloned loop blocks based on how we in buildClonedLoops()
1525 // loops) and filter them as we add them into the cloned loop. in buildClonedLoops()
1531 // Directly add the blocks that are only in this loop. in buildClonedLoops()
1537 // We want to manually add it to this loop and parents. in buildClonedLoops()
1539 // loop for this block. in buildClonedLoops()
1540 for (Loop *PL = ClonedL; PL; PL = PL->getParentLoop()) in buildClonedLoops()
1544 // Now add each child loop whose header remains within the cloned loop. All in buildClonedLoops()
1545 // of the blocks within the loop must satisfy the same constraints as the in buildClonedLoops()
1547 // child loop nest. in buildClonedLoops()
1548 for (Loop *ChildL : OrigL) { in buildClonedLoops()
1555 // We should never have a cloned child loop header but fail to have in buildClonedLoops()
1556 // all of the blocks for that child loop. in buildClonedLoops()
1560 "Child cloned loop has a header within the cloned outer " in buildClonedLoops()
1561 "loop but not all of its blocks!"); in buildClonedLoops()
1568 // Now that we've handled all the components of the original loop that were in buildClonedLoops()
1569 // cloned into a new loop, we still need to handle anything from the original in buildClonedLoops()
1570 // loop that wasn't in a cloned loop. in buildClonedLoops()
1572 // Figure out what blocks are left to place within any loop nest containing in buildClonedLoops()
1573 // the unswitched loop. If we never formed a loop, the cloned PH is one of in buildClonedLoops()
1582 // Copy the cloned exits and sort them in ascending loop depth, we'll work in buildClonedLoops()
1598 Loop *ExitL = ExitLoopMap.lookup(ExitBB); in buildClonedLoops()
1601 // and in the unlooped set to this exit block's loop. in buildClonedLoops()
1611 // (inner) loop, no update needed. in buildClonedLoops()
1615 "Predecessor not mapped to a loop!"); in buildClonedLoops()
1619 // We just insert into the loop set here. We'll add these blocks to the in buildClonedLoops()
1620 // exit loop after we build up the set in an order that doesn't rely on in buildClonedLoops()
1634 // in their original order adding them to the correct loop. in buildClonedLoops()
1636 // We need a stable insertion order. We use the order of the original loop in buildClonedLoops()
1637 // order and map into the correct parent loop. in buildClonedLoops()
1640 if (Loop *OuterL = ExitLoopMap.lookup(BB)) in buildClonedLoops()
1652 // Now that all the blocks are placed into the correct containing loop in the in buildClonedLoops()
1654 // clone them into whatever outer loop we placed their header into. in buildClonedLoops()
1655 for (Loop *ChildL : OrigL) { in buildClonedLoops()
1664 "Cloned a child loop header but not all of that loops blocks!"); in buildClonedLoops()
1673 deleteDeadClonedBlocks(Loop &L, ArrayRef<BasicBlock *> ExitBlocks, in deleteDeadClonedBlocks()
1702 static void deleteDeadBlocksFromLoop(Loop &L, in deleteDeadBlocksFromLoop()
1708 // Find all the dead blocks tied to this loop, and remove them from their in deleteDeadBlocksFromLoop()
1712 // Start with loop/exit blocks and get a transitive closure of reachable dead in deleteDeadBlocksFromLoop()
1737 // Walk from this loop up through its parents removing all of the dead blocks. in deleteDeadBlocksFromLoop()
1738 for (Loop *ParentL = &L; ParentL; ParentL = ParentL->getParentLoop()) { in deleteDeadBlocksFromLoop()
1747 llvm::erase_if(L.getSubLoopsVector(), [&](Loop *ChildL) { in deleteDeadBlocksFromLoop()
1755 "If the child loop header is dead all blocks in the child loop must " in deleteDeadBlocksFromLoop()
1764 // Remove the loop mappings for the dead blocks and drop all the references in deleteDeadBlocksFromLoop()
1785 /// Recompute the set of blocks in a loop after unswitching.
1787 /// This walks from the original headers predecessors to rebuild the loop. We
1789 /// filter by the original loop's blocks. This also handles potentially
1793 /// If the original loop is no longer a loop, this will return an empty set. If
1794 /// it remains a loop, all the blocks within it will be added to the set
1796 static SmallPtrSet<const BasicBlock *, 16> recomputeLoopBlockSet(Loop &L, in recomputeLoopBlockSet()
1813 // Because the loop was in simplified form, the only non-loop predecessor in recomputeLoopBlockSet()
1815 assert(L.contains(Pred) && "Found a predecessor of the loop header other " in recomputeLoopBlockSet()
1817 "loop!"); in recomputeLoopBlockSet()
1819 // Insert this block into the loop set and on the first visit and, if it in recomputeLoopBlockSet()
1830 // We found backedges, recurse through them to identify the loop blocks. in recomputeLoopBlockSet()
1833 assert(LoopBlockSet.count(BB) && "Didn't put block into the loop set!"); in recomputeLoopBlockSet()
1839 // Because we know the inner loop structure remains valid we can use the in recomputeLoopBlockSet()
1840 // loop structure to jump immediately across the entire nested loop. in recomputeLoopBlockSet()
1841 // Further, because it is in loop simplified form, we can directly jump in recomputeLoopBlockSet()
1843 if (Loop *InnerL = LI.getLoopFor(BB)) in recomputeLoopBlockSet()
1846 "Should not reach a loop *outside* this loop!"); in recomputeLoopBlockSet()
1847 // The preheader is the only possible predecessor of the loop so in recomputeLoopBlockSet()
1850 assert(L.contains(InnerPH) && "Cannot contain an inner loop block " in recomputeLoopBlockSet()
1851 "but not contain the inner loop " in recomputeLoopBlockSet()
1854 // The only way to reach the preheader is through the loop body in recomputeLoopBlockSet()
1855 // itself so if it has been visited the loop is already handled. in recomputeLoopBlockSet()
1859 // the loop set. We expect at least the block that led us to find the in recomputeLoopBlockSet()
1860 // inner loop to be in the block set, but we may also have other loop in recomputeLoopBlockSet()
1862 // outer loop block. in recomputeLoopBlockSet()
1874 // loop body. in recomputeLoopBlockSet()
1879 // Insert any predecessors that were in the original loop into the new in recomputeLoopBlockSet()
1888 // We've found all the blocks participating in the loop, return our completed in recomputeLoopBlockSet()
1893 /// Rebuild a loop after unswitching removes some subset of blocks and edges.
1897 /// to the parent loop (or to be top-level loops). The original loop may be
1901 /// loop remains a valid loop, it will be the first entry in this list with all
1904 /// Returns true if the loop remains a loop after unswitching, and false if it
1905 /// is no longer a loop after unswitching (and should not continue to be
1907 static bool rebuildLoopAfterUnswitch(Loop &L, ArrayRef<BasicBlock *> ExitBlocks, in rebuildLoopAfterUnswitch()
1909 SmallVectorImpl<Loop *> &HoistedLoops, in rebuildLoopAfterUnswitch()
1913 // Compute the actual parent loop from the exit blocks. Because we may have in rebuildLoopAfterUnswitch()
1914 // pruned some exits the loop may be different from the original parent. in rebuildLoopAfterUnswitch()
1915 Loop *ParentL = nullptr; in rebuildLoopAfterUnswitch()
1916 SmallVector<Loop *, 4> ExitLoops; in rebuildLoopAfterUnswitch()
1920 if (Loop *ExitL = LI.getLoopFor(ExitBB)) { in rebuildLoopAfterUnswitch()
1927 // Recompute the blocks participating in this loop. This may be empty if it in rebuildLoopAfterUnswitch()
1928 // is no longer a loop. in rebuildLoopAfterUnswitch()
1931 // If we still have a loop, we need to re-set the loop's parent as the exit in rebuildLoopAfterUnswitch()
1932 // block set changing may have moved it within the loop nest. Note that this in rebuildLoopAfterUnswitch()
1933 // can only happen when this loop has a parent as it can only hoist the loop in rebuildLoopAfterUnswitch()
1936 // Remove this loop's (original) blocks from all of the intervening loops. in rebuildLoopAfterUnswitch()
1937 for (Loop *IL = L.getParentLoop(); IL != ParentL; in rebuildLoopAfterUnswitch()
1955 // Now we update all the blocks which are no longer within the loop. in rebuildLoopAfterUnswitch()
1969 // Now erase these blocks from the loop. in rebuildLoopAfterUnswitch()
1974 // Sort the exits in ascending loop depth, we'll work backwards across these in rebuildLoopAfterUnswitch()
1980 // We'll build up a set for each exit loop. in rebuildLoopAfterUnswitch()
1982 Loop *PrevExitL = L.getParentLoop(); // The deepest possible exit loop. in rebuildLoopAfterUnswitch()
1985 [](Loop &L, SmallPtrSetImpl<BasicBlock *> &UnloopedBlocks) { in rebuildLoopAfterUnswitch()
1996 assert(NewExitLoopBlocks.empty() && "Didn't clear loop set!"); in rebuildLoopAfterUnswitch()
1998 // Grab the next exit block, in decreasing loop depth order. in rebuildLoopAfterUnswitch()
2000 Loop &ExitL = *LI.getLoopFor(ExitBB); in rebuildLoopAfterUnswitch()
2001 assert(ExitL.contains(&L) && "Exit loop must contain the inner loop!"); in rebuildLoopAfterUnswitch()
2004 // exit loop and this exit loop. This works because the ExitInLoops list is in rebuildLoopAfterUnswitch()
2005 // sorted in increasing order of loop depth and thus we visit loops in in rebuildLoopAfterUnswitch()
2006 // decreasing order of loop depth. in rebuildLoopAfterUnswitch()
2011 // and in the unlooped set to this exit block's loop. in rebuildLoopAfterUnswitch()
2021 // (inner) loop, no update needed. in rebuildLoopAfterUnswitch()
2025 "Predecessor not in a nested loop (or already visited)!"); in rebuildLoopAfterUnswitch()
2029 // We just insert into the loop set here. We'll add these blocks to the in rebuildLoopAfterUnswitch()
2030 // exit loop after we build up the set in a deterministic order rather in rebuildLoopAfterUnswitch()
2041 // If blocks in this exit loop were directly part of the original loop (as in rebuildLoopAfterUnswitch()
2042 // opposed to a child loop) update the map to point to this exit loop. This in rebuildLoopAfterUnswitch()
2045 if (Loop *BBL = LI.getLoopFor(BB)) in rebuildLoopAfterUnswitch()
2049 // We will remove the remaining unlooped blocks from this loop in the next in rebuildLoopAfterUnswitch()
2054 // Any remaining unlooped blocks are no longer part of any loop unless they in rebuildLoopAfterUnswitch()
2055 // are part of some child loop. in rebuildLoopAfterUnswitch()
2059 if (Loop *BBL = LI.getLoopFor(BB)) in rebuildLoopAfterUnswitch()
2063 // Sink all the child loops whose headers are no longer in the loop set to in rebuildLoopAfterUnswitch()
2064 // the parent (or to be top level loops). We reach into the loop and directly in rebuildLoopAfterUnswitch()
2071 SubLoops.begin(), SubLoops.end(), [&](Loop *SubL) { in rebuildLoopAfterUnswitch()
2078 // To compute the new parent of this hoisted loop we look at where we in rebuildLoopAfterUnswitch()
2080 // retained the mapping from the header to the hoisted loop. But the in rebuildLoopAfterUnswitch()
2082 // based on the set of exit blocks from the original loop as the preheader in rebuildLoopAfterUnswitch()
2085 // hoisted loop can't be part of some *other* loop. in rebuildLoopAfterUnswitch()
2093 // Actually delete the loop if nothing remained within it. in rebuildLoopAfterUnswitch()
2096 "Failed to remove all subloops from the original loop!"); in rebuildLoopAfterUnswitch()
2097 if (Loop *ParentL = L.getParentLoop()) in rebuildLoopAfterUnswitch()
2139 void postUnswitch(Loop &L, LPMUpdater &U, StringRef LoopName, in postUnswitch()
2141 bool InjectedCondition, ArrayRef<Loop *> NewLoops) { in postUnswitch()
2146 // If the current loop remains valid, we should revisit it to catch any in postUnswitch()
2150 // Mark the new loop as partially unswitched, to avoid unswitching on in postUnswitch()
2155 MDString::get(Context, "llvm.loop.unswitch.partial.disable")); in postUnswitch()
2157 Context, L.getLoopID(), {"llvm.loop.unswitch.partial"}, in postUnswitch()
2165 MDString::get(Context, "llvm.loop.unswitch.injection.disable")); in postUnswitch()
2167 Context, L.getLoopID(), {"llvm.loop.unswitch.injection"}, in postUnswitch()
2177 Loop &L, Instruction &TI, ArrayRef<Value *> Invariants, in unswitchNontrivialInvariants()
2185 // Save the current loop name in a variable so that we can report it even in unswitchNontrivialInvariants()
2245 // The branch should be in this exact loop. Any inner loop's invariant branch in unswitchNontrivialInvariants()
2246 // should be handled by unswitching that inner loop. The caller of this in unswitchNontrivialInvariants()
2249 assert(LI.getLoopFor(ParentBB) == &L && "Branch in an inner loop!"); in unswitchNontrivialInvariants()
2251 // Compute the parent loop now before we start hacking on things. in unswitchNontrivialInvariants()
2252 Loop *ParentL = L.getParentLoop(); in unswitchNontrivialInvariants()
2258 // Compute the outer-most loop containing one of our exit blocks. This is the in unswitchNontrivialInvariants()
2261 Loop *OuterExitL = &L; in unswitchNontrivialInvariants()
2265 // ExitBB can be an exit block for several levels in the loop nest. Make in unswitchNontrivialInvariants()
2267 Loop *NewOuterExitL = getTopMostExitingLoop(ExitBB, LI); in unswitchNontrivialInvariants()
2278 // any cached information in ScalarEvolution for the outer most loop in unswitchNontrivialInvariants()
2309 // original loop. in unswitchNontrivialInvariants()
2316 // Clone the loop for each unswitched successor. in unswitchNontrivialInvariants()
2353 // Splice the terminator from the original loop and rewrite its in unswitchNontrivialInvariants()
2366 // BI (`dyn_cast<BranchInst>(TI)`) is an in-loop instruction hoisted in unswitchNontrivialInvariants()
2367 // out of the loop. in unswitchNontrivialInvariants()
2493 // not delete the blocks from the original loop yet because we still want to in unswitchNontrivialInvariants()
2494 // reference the original loop to understand the cloned loop's structure. in unswitchNontrivialInvariants()
2497 // Build the cloned loop structure itself. This may be substantially in unswitchNontrivialInvariants()
2500 SmallVector<Loop *, 4> NonChildClonedLoops; in unswitchNontrivialInvariants()
2504 // Now that our cloned loops have been built, we can update the original loop. in unswitchNontrivialInvariants()
2505 // First we delete the dead blocks from it and then we rebuild the loop in unswitchNontrivialInvariants()
2512 SmallVector<Loop *, 4> HoistedLoops; in unswitchNontrivialInvariants()
2520 // the below steps to rebuild loop structures will result in hard to debug in unswitchNontrivialInvariants()
2562 // Replace it with the 'continue' side if in the main loop body, and the in unswitchNontrivialInvariants()
2574 // loops, the current loop, and any parent loops which shared exit blocks in unswitchNontrivialInvariants()
2575 // with the current loop. As a consequence, we need to re-form LCSSA for in unswitchNontrivialInvariants()
2581 // loop nest and update every loop that could have had its exits changed. We in unswitchNontrivialInvariants()
2583 // a list and sort them by loop depth to achieve this without updating in unswitchNontrivialInvariants()
2585 auto UpdateLoop = [&](Loop &UpdateL) { in unswitchNontrivialInvariants()
2588 for (Loop *ChildL : UpdateL) { in unswitchNontrivialInvariants()
2591 "Perturbed a child loop's LCSSA form!"); in unswitchNontrivialInvariants()
2594 // First build LCSSA for this loop so that we can preserve it when in unswitchNontrivialInvariants()
2595 // forming dedicated exits. We don't want to perturb some other loop's in unswitchNontrivialInvariants()
2599 // For loops reached by this loop's original exit blocks we may in unswitchNontrivialInvariants()
2610 // as that will necessitate widening the outer loop scope. in unswitchNontrivialInvariants()
2611 for (Loop *UpdatedL : in unswitchNontrivialInvariants()
2612 llvm::concat<Loop *>(NonChildClonedLoops, HoistedLoops)) { in unswitchNontrivialInvariants()
2623 // If the original loop had exit blocks, walk up through the outer most loop in unswitchNontrivialInvariants()
2626 for (Loop *OuterL = ParentL; OuterL != OuterExitL; in unswitchNontrivialInvariants()
2631 // Verify the entire loop structure to catch any incorrect updates before we in unswitchNontrivialInvariants()
2638 // and check whether the original loop survived. in unswitchNontrivialInvariants()
2639 SmallVector<Loop *, 4> SibLoops; in unswitchNontrivialInvariants()
2640 for (Loop *UpdatedL : llvm::concat<Loop *>(NonChildClonedLoops, HoistedLoops)) in unswitchNontrivialInvariants()
2763 static BranchInst *turnGuardIntoBranch(IntrinsicInst *GI, Loop &L, in turnGuardIntoBranch()
2807 /// of loop-unswitch. Cost is multipied in proportion of 2^number of unswitch
2820 const Instruction &TI, const Loop &L, const LoopInfo &LI, in CalculateUnswitchCostMultiplier()
2827 // loop copy on unswitch). in CalculateUnswitchCostMultiplier()
2901 const Loop &L, const LoopInfo &LI, AAResults &AA, in collectUnswitchCandidates()
2922 // Whether or not we should also collect guards in the loop. in collectUnswitchCandidates()
2951 // We can only consider fully loop-invariant switch conditions as we need in collectUnswitchCandidates()
2967 if (MSSAU && !findOptionMDForLoop(&L, "llvm.loop.unswitch.partial.disable") && in collectUnswitchCandidates()
2974 dbgs() << "simple-loop-unswitch: Found partially invariant condition " in collectUnswitchCandidates()
2996 BasicBlock *&IfFalse, const Loop &L) { in canonicalizeForInvariantConditionInjection()
3002 // Move loop-invariant argument to RHS position. in canonicalizeForInvariantConditionInjection()
3019 /// injecting a loop-invariant condition.
3022 const BasicBlock *IfTrue, const BasicBlock *IfFalse, const Loop &L) { in shouldTryInjectInvariantCondition()
3028 // TODO: Support non-loop-exiting branches? in shouldTryInjectInvariantCondition()
3064 /// injected loop-invariant condition implies the original loop-variant branch
3082 injectPendingInvariantConditions(NonTrivialUnswitchCandidate Candidate, Loop &L, in injectPendingInvariantConditions()
3087 assert(Preheader && "Loop is not in simplified form?"); in injectPendingInvariantConditions()
3089 "Unswitching branch of inner loop!"); in injectPendingInvariantConditions()
3162 LLVM_DEBUG(dbgs() << "Injected a new loop-invariant branch " << *InvariantBr in injectPendingInvariantConditions()
3169 /// Given chain of loop branch conditions looking like:
3181 SmallVectorImpl<NonTrivialUnswitchCandidate> &UnswitchCandidates, Loop &L, in insertCandidatesWithPendingInjections()
3204 /// present in the loop. However, they can be injected into the code if we
3217 /// loop-variant checks in unswitched loop version.
3220 IVConditionInfo &PartialIVInfo, Instruction *&PartialIVCondBranch, Loop &L, in collectUnswitchCandidatesWithInjections()
3273 static bool isSafeForNoNTrivialUnswitching(Loop &L, LoopInfo &LI) { in isSafeForNoNTrivialUnswitching()
3287 // Check if there are irreducible CFG cycles in this loop. If so, we cannot in isSafeForNoNTrivialUnswitching()
3288 // easily unswitch non-trivial edges out of the loop. Doing so might turn the in isSafeForNoNTrivialUnswitching()
3291 // this, we can add support to loop unswitch, but it is a lot of complexity in isSafeForNoNTrivialUnswitching()
3317 ArrayRef<NonTrivialUnswitchCandidate> UnswitchCandidates, const Loop &L, in findBestNonTrivialUnswitchCandidate()
3321 // the loop, so we need to be able to model that cost. Compute the ephemeral in findBestNonTrivialUnswitchCandidate()
3324 // subsets of the loop for duplication during unswitching. in findBestNonTrivialUnswitchCandidate()
3329 // Compute the cost of each block, as well as the total loop cost. Also, bail in findBestNonTrivialUnswitchCandidate()
3330 // out if we see instructions which are incompatible with loop unswitching in findBestNonTrivialUnswitchCandidate()
3348 assert(LoopCost >= 0 && "Must not have negative loop costs!"); in findBestNonTrivialUnswitchCandidate()
3351 LLVM_DEBUG(dbgs() << " Total loop cost: " << LoopCost << "\n"); in findBestNonTrivialUnswitchCandidate()
3372 // Unswitching selects unswitches the entire loop. in findBestNonTrivialUnswitchCandidate()
3409 // subtree and so it will end up live in only one clone of the loop. in findBestNonTrivialUnswitchCandidate()
3416 "Non-duplicated cost should never exceed total loop cost!"); in findBestNonTrivialUnswitchCandidate()
3422 // loop. This is computing the new cost of unswitching a condition. in findBestNonTrivialUnswitchCandidate()
3442 // exponential behavior of loop-unswitch. in findBestNonTrivialUnswitchCandidate()
3468 // 1. freeze-loop-unswitch-cond option is true
3469 // 2. The branch may not execute in the loop pre-transformation. If a branch may
3471 // of the loop. Insert a freeze to prevent this case.
3473 static bool shouldInsertFreeze(Loop &L, Instruction &TI, DominatorTree &DT, in shouldInsertFreeze()
3493 static bool unswitchBestCondition(Loop &L, DominatorTree &DT, LoopInfo &LI, in unswitchBestCondition()
3498 // Collect all invariant conditions within this loop (as opposed to an inner in unswitchBestCondition()
3499 // loop which would be handled when visiting that inner loop). in unswitchBestCondition()
3505 if (!findOptionMDForLoop(&L, "llvm.loop.unswitch.injection.disable")) in unswitchBestCondition()
3515 << " non-trivial loop invariant conditions for unswitching.\n"); in unswitchBestCondition()
3520 assert(Best.TI && "Failed to find loop unswitch candidate"); in unswitchBestCondition()
3565 /// Unswitch control flow predicated on loop invariant conditions.
3568 /// require duplicating any part of the loop) out of the loop body. It then
3569 /// looks at other loop invariant control flows and tries to unswitch those as
3570 /// well by cloning the loop if the result is small enough.
3581 /// with information on whether or not the provided loop remains a loop and
3586 static bool unswitchLoop(Loop &L, DominatorTree &DT, LoopInfo &LI, in unswitchLoop()
3595 // Must be in loop simplified form: we need a preheader and dedicated exits. in unswitchLoop()
3599 // Try trivial unswitch first before loop over other basic blocks in the loop. in unswitchLoop()
3601 // If we unswitched successfully we will want to clean up the loop before in unswitchLoop()
3618 // FIXME: If divergence analysis becomes available to a loop in unswitchLoop()
3631 // Returns true if Loop L's loop nest is cold, i.e. if the headers of L, in unswitchLoop()
3633 auto IsLoopNestCold = [&](const Loop *L) { in unswitchLoop()
3642 SmallVector<const Loop *, 4> Worklist; in unswitchLoop()
3655 // Skip cold loops in cold loop nests, as unswitching them brings little in unswitchLoop()
3658 LLVM_DEBUG(dbgs() << " Skip cold loop: " << L << "\n"); in unswitchLoop()
3681 PreservedAnalyses SimpleLoopUnswitchPass::run(Loop &L, LoopAnalysisManager &AM, in run()
3691 LLVM_DEBUG(dbgs() << "Unswitching loop in " << F.getName() << ": " << L in run()