xref: /freebsd-src/contrib/llvm-project/llvm/lib/Transforms/Utils/FixIrreducible.cpp (revision 5f757f3ff9144b609b3c433dfd370cc6bdc191ad)
15ffd83dbSDimitry Andric //===- FixIrreducible.cpp - Convert irreducible control-flow into loops ---===//
25ffd83dbSDimitry Andric //
35ffd83dbSDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
45ffd83dbSDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
55ffd83dbSDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
65ffd83dbSDimitry Andric //
75ffd83dbSDimitry Andric //===----------------------------------------------------------------------===//
85ffd83dbSDimitry Andric //
95ffd83dbSDimitry Andric // An irreducible SCC is one which has multiple "header" blocks, i.e., blocks
105ffd83dbSDimitry Andric // with control-flow edges incident from outside the SCC.  This pass converts a
115ffd83dbSDimitry Andric // irreducible SCC into a natural loop by applying the following transformation:
125ffd83dbSDimitry Andric //
135ffd83dbSDimitry Andric // 1. Collect the set of headers H of the SCC.
145ffd83dbSDimitry Andric // 2. Collect the set of predecessors P of these headers. These may be inside as
155ffd83dbSDimitry Andric //    well as outside the SCC.
165ffd83dbSDimitry Andric // 3. Create block N and redirect every edge from set P to set H through N.
175ffd83dbSDimitry Andric //
185ffd83dbSDimitry Andric // This converts the SCC into a natural loop with N as the header: N is the only
195ffd83dbSDimitry Andric // block with edges incident from outside the SCC, and all backedges in the SCC
205ffd83dbSDimitry Andric // are incident on N, i.e., for every backedge, the head now dominates the tail.
215ffd83dbSDimitry Andric //
225ffd83dbSDimitry Andric // INPUT CFG: The blocks A and B form an irreducible loop with two headers.
235ffd83dbSDimitry Andric //
245ffd83dbSDimitry Andric //                        Entry
255ffd83dbSDimitry Andric //                       /     \
265ffd83dbSDimitry Andric //                      v       v
275ffd83dbSDimitry Andric //                      A ----> B
285ffd83dbSDimitry Andric //                      ^      /|
295ffd83dbSDimitry Andric //                       `----' |
305ffd83dbSDimitry Andric //                              v
315ffd83dbSDimitry Andric //                             Exit
325ffd83dbSDimitry Andric //
335ffd83dbSDimitry Andric // OUTPUT CFG: Edges incident on A and B are now redirected through a
345ffd83dbSDimitry Andric // new block N, forming a natural loop consisting of N, A and B.
355ffd83dbSDimitry Andric //
365ffd83dbSDimitry Andric //                        Entry
375ffd83dbSDimitry Andric //                          |
385ffd83dbSDimitry Andric //                          v
395ffd83dbSDimitry Andric //                    .---> N <---.
405ffd83dbSDimitry Andric //                   /     / \     \
415ffd83dbSDimitry Andric //                  |     /   \     |
425ffd83dbSDimitry Andric //                  \    v     v    /
435ffd83dbSDimitry Andric //                   `-- A     B --'
445ffd83dbSDimitry Andric //                             |
455ffd83dbSDimitry Andric //                             v
465ffd83dbSDimitry Andric //                            Exit
475ffd83dbSDimitry Andric //
485ffd83dbSDimitry Andric // The transformation is applied to every maximal SCC that is not already
495ffd83dbSDimitry Andric // recognized as a loop. The pass operates on all maximal SCCs found in the
505ffd83dbSDimitry Andric // function body outside of any loop, as well as those found inside each loop,
515ffd83dbSDimitry Andric // including inside any newly created loops. This ensures that any SCC hidden
525ffd83dbSDimitry Andric // inside a maximal SCC is also transformed.
535ffd83dbSDimitry Andric //
545ffd83dbSDimitry Andric // The actual transformation is handled by function CreateControlFlowHub, which
555ffd83dbSDimitry Andric // takes a set of incoming blocks (the predecessors) and outgoing blocks (the
565ffd83dbSDimitry Andric // headers). The function also moves every PHINode in an outgoing block to the
575ffd83dbSDimitry Andric // hub. Since the hub dominates all the outgoing blocks, each such PHINode
585ffd83dbSDimitry Andric // continues to dominate its uses. Since every header in an SCC has at least two
595ffd83dbSDimitry Andric // predecessors, every value used in the header (or later) but defined in a
605ffd83dbSDimitry Andric // predecessor (or earlier) is represented by a PHINode in a header. Hence the
615ffd83dbSDimitry Andric // above handling of PHINodes is sufficient and no further processing is
625ffd83dbSDimitry Andric // required to restore SSA.
635ffd83dbSDimitry Andric //
645ffd83dbSDimitry Andric // Limitation: The pass cannot handle switch statements and indirect
655ffd83dbSDimitry Andric //             branches. Both must be lowered to plain branches first.
665ffd83dbSDimitry Andric //
675ffd83dbSDimitry Andric //===----------------------------------------------------------------------===//
685ffd83dbSDimitry Andric 
69e8d8bef9SDimitry Andric #include "llvm/Transforms/Utils/FixIrreducible.h"
705ffd83dbSDimitry Andric #include "llvm/ADT/SCCIterator.h"
7181ad6265SDimitry Andric #include "llvm/Analysis/DomTreeUpdater.h"
725ffd83dbSDimitry Andric #include "llvm/Analysis/LoopIterator.h"
735ffd83dbSDimitry Andric #include "llvm/InitializePasses.h"
745ffd83dbSDimitry Andric #include "llvm/Pass.h"
755ffd83dbSDimitry Andric #include "llvm/Transforms/Utils.h"
765ffd83dbSDimitry Andric #include "llvm/Transforms/Utils/BasicBlockUtils.h"
775ffd83dbSDimitry Andric 
785ffd83dbSDimitry Andric #define DEBUG_TYPE "fix-irreducible"
795ffd83dbSDimitry Andric 
805ffd83dbSDimitry Andric using namespace llvm;
815ffd83dbSDimitry Andric 
825ffd83dbSDimitry Andric namespace {
835ffd83dbSDimitry Andric struct FixIrreducible : public FunctionPass {
845ffd83dbSDimitry Andric   static char ID;
FixIrreducible__anon3f9427b10111::FixIrreducible855ffd83dbSDimitry Andric   FixIrreducible() : FunctionPass(ID) {
865ffd83dbSDimitry Andric     initializeFixIrreduciblePass(*PassRegistry::getPassRegistry());
875ffd83dbSDimitry Andric   }
885ffd83dbSDimitry Andric 
getAnalysisUsage__anon3f9427b10111::FixIrreducible895ffd83dbSDimitry Andric   void getAnalysisUsage(AnalysisUsage &AU) const override {
905ffd83dbSDimitry Andric     AU.addRequired<DominatorTreeWrapperPass>();
915ffd83dbSDimitry Andric     AU.addRequired<LoopInfoWrapperPass>();
925ffd83dbSDimitry Andric     AU.addPreserved<DominatorTreeWrapperPass>();
935ffd83dbSDimitry Andric     AU.addPreserved<LoopInfoWrapperPass>();
945ffd83dbSDimitry Andric   }
955ffd83dbSDimitry Andric 
965ffd83dbSDimitry Andric   bool runOnFunction(Function &F) override;
975ffd83dbSDimitry Andric };
985ffd83dbSDimitry Andric } // namespace
995ffd83dbSDimitry Andric 
1005ffd83dbSDimitry Andric char FixIrreducible::ID = 0;
1015ffd83dbSDimitry Andric 
createFixIrreduciblePass()1025ffd83dbSDimitry Andric FunctionPass *llvm::createFixIrreduciblePass() { return new FixIrreducible(); }
1035ffd83dbSDimitry Andric 
1045ffd83dbSDimitry Andric INITIALIZE_PASS_BEGIN(FixIrreducible, "fix-irreducible",
1055ffd83dbSDimitry Andric                       "Convert irreducible control-flow into natural loops",
1065ffd83dbSDimitry Andric                       false /* Only looks at CFG */, false /* Analysis Pass */)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)1075ffd83dbSDimitry Andric INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1085ffd83dbSDimitry Andric INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
1095ffd83dbSDimitry Andric INITIALIZE_PASS_END(FixIrreducible, "fix-irreducible",
1105ffd83dbSDimitry Andric                     "Convert irreducible control-flow into natural loops",
1115ffd83dbSDimitry Andric                     false /* Only looks at CFG */, false /* Analysis Pass */)
1125ffd83dbSDimitry Andric 
1135ffd83dbSDimitry Andric // When a new loop is created, existing children of the parent loop may now be
1145ffd83dbSDimitry Andric // fully inside the new loop. Reconnect these as children of the new loop.
1155ffd83dbSDimitry Andric static void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop,
1165ffd83dbSDimitry Andric                                 SetVector<BasicBlock *> &Blocks,
1175ffd83dbSDimitry Andric                                 SetVector<BasicBlock *> &Headers) {
1185ffd83dbSDimitry Andric   auto &CandidateLoops = ParentLoop ? ParentLoop->getSubLoopsVector()
1195ffd83dbSDimitry Andric                                     : LI.getTopLevelLoopsVector();
1205ffd83dbSDimitry Andric   // The new loop cannot be its own child, and any candidate is a
1215ffd83dbSDimitry Andric   // child iff its header is owned by the new loop. Move all the
1225ffd83dbSDimitry Andric   // children to a new vector.
1235ffd83dbSDimitry Andric   auto FirstChild = std::partition(
1245ffd83dbSDimitry Andric       CandidateLoops.begin(), CandidateLoops.end(), [&](Loop *L) {
125349cc55cSDimitry Andric         return L == NewLoop || !Blocks.contains(L->getHeader());
1265ffd83dbSDimitry Andric       });
1275ffd83dbSDimitry Andric   SmallVector<Loop *, 8> ChildLoops(FirstChild, CandidateLoops.end());
1285ffd83dbSDimitry Andric   CandidateLoops.erase(FirstChild, CandidateLoops.end());
1295ffd83dbSDimitry Andric 
130fe6060f1SDimitry Andric   for (Loop *Child : ChildLoops) {
1315ffd83dbSDimitry Andric     LLVM_DEBUG(dbgs() << "child loop: " << Child->getHeader()->getName()
1325ffd83dbSDimitry Andric                       << "\n");
1335ffd83dbSDimitry Andric     // TODO: A child loop whose header is also a header in the current
1345ffd83dbSDimitry Andric     // SCC gets destroyed since its backedges are removed. That may
1355ffd83dbSDimitry Andric     // not be necessary if we can retain such backedges.
1365ffd83dbSDimitry Andric     if (Headers.count(Child->getHeader())) {
137bdd1243dSDimitry Andric       for (auto *BB : Child->blocks()) {
13881ad6265SDimitry Andric         if (LI.getLoopFor(BB) != Child)
13981ad6265SDimitry Andric           continue;
1405ffd83dbSDimitry Andric         LI.changeLoopFor(BB, NewLoop);
1415ffd83dbSDimitry Andric         LLVM_DEBUG(dbgs() << "moved block from child: " << BB->getName()
1425ffd83dbSDimitry Andric                           << "\n");
1435ffd83dbSDimitry Andric       }
14481ad6265SDimitry Andric       std::vector<Loop *> GrandChildLoops;
14581ad6265SDimitry Andric       std::swap(GrandChildLoops, Child->getSubLoopsVector());
146bdd1243dSDimitry Andric       for (auto *GrandChildLoop : GrandChildLoops) {
14781ad6265SDimitry Andric         GrandChildLoop->setParentLoop(nullptr);
14881ad6265SDimitry Andric         NewLoop->addChildLoop(GrandChildLoop);
14981ad6265SDimitry Andric       }
1505ffd83dbSDimitry Andric       LI.destroy(Child);
1515ffd83dbSDimitry Andric       LLVM_DEBUG(dbgs() << "subsumed child loop (common header)\n");
1525ffd83dbSDimitry Andric       continue;
1535ffd83dbSDimitry Andric     }
1545ffd83dbSDimitry Andric 
1555ffd83dbSDimitry Andric     Child->setParentLoop(nullptr);
1565ffd83dbSDimitry Andric     NewLoop->addChildLoop(Child);
1575ffd83dbSDimitry Andric     LLVM_DEBUG(dbgs() << "added child loop to new loop\n");
1585ffd83dbSDimitry Andric   }
1595ffd83dbSDimitry Andric }
1605ffd83dbSDimitry Andric 
1615ffd83dbSDimitry Andric // Given a set of blocks and headers in an irreducible SCC, convert it into a
1625ffd83dbSDimitry Andric // natural loop. Also insert this new loop at its appropriate place in the
1635ffd83dbSDimitry Andric // hierarchy of loops.
createNaturalLoopInternal(LoopInfo & LI,DominatorTree & DT,Loop * ParentLoop,SetVector<BasicBlock * > & Blocks,SetVector<BasicBlock * > & Headers)1645ffd83dbSDimitry Andric static void createNaturalLoopInternal(LoopInfo &LI, DominatorTree &DT,
1655ffd83dbSDimitry Andric                                       Loop *ParentLoop,
1665ffd83dbSDimitry Andric                                       SetVector<BasicBlock *> &Blocks,
1675ffd83dbSDimitry Andric                                       SetVector<BasicBlock *> &Headers) {
1685ffd83dbSDimitry Andric #ifndef NDEBUG
1695ffd83dbSDimitry Andric   // All headers are part of the SCC
170bdd1243dSDimitry Andric   for (auto *H : Headers) {
1715ffd83dbSDimitry Andric     assert(Blocks.count(H));
1725ffd83dbSDimitry Andric   }
1735ffd83dbSDimitry Andric #endif
1745ffd83dbSDimitry Andric 
1755ffd83dbSDimitry Andric   SetVector<BasicBlock *> Predecessors;
176bdd1243dSDimitry Andric   for (auto *H : Headers) {
177bdd1243dSDimitry Andric     for (auto *P : predecessors(H)) {
1785ffd83dbSDimitry Andric       Predecessors.insert(P);
1795ffd83dbSDimitry Andric     }
1805ffd83dbSDimitry Andric   }
1815ffd83dbSDimitry Andric 
1825ffd83dbSDimitry Andric   LLVM_DEBUG(
1835ffd83dbSDimitry Andric       dbgs() << "Found predecessors:";
1845ffd83dbSDimitry Andric       for (auto P : Predecessors) {
1855ffd83dbSDimitry Andric         dbgs() << " " << P->getName();
1865ffd83dbSDimitry Andric       }
1875ffd83dbSDimitry Andric       dbgs() << "\n");
1885ffd83dbSDimitry Andric 
1895ffd83dbSDimitry Andric   // Redirect all the backedges through a "hub" consisting of a series
1905ffd83dbSDimitry Andric   // of guard blocks that manage the flow of control from the
1915ffd83dbSDimitry Andric   // predecessors to the headers.
1925ffd83dbSDimitry Andric   SmallVector<BasicBlock *, 8> GuardBlocks;
1935ffd83dbSDimitry Andric   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
1945ffd83dbSDimitry Andric   CreateControlFlowHub(&DTU, GuardBlocks, Predecessors, Headers, "irr");
1955ffd83dbSDimitry Andric #if defined(EXPENSIVE_CHECKS)
1965ffd83dbSDimitry Andric   assert(DT.verify(DominatorTree::VerificationLevel::Full));
1975ffd83dbSDimitry Andric #else
1985ffd83dbSDimitry Andric   assert(DT.verify(DominatorTree::VerificationLevel::Fast));
1995ffd83dbSDimitry Andric #endif
2005ffd83dbSDimitry Andric 
2015ffd83dbSDimitry Andric   // Create a new loop from the now-transformed cycle
2025ffd83dbSDimitry Andric   auto NewLoop = LI.AllocateLoop();
2035ffd83dbSDimitry Andric   if (ParentLoop) {
2045ffd83dbSDimitry Andric     ParentLoop->addChildLoop(NewLoop);
2055ffd83dbSDimitry Andric   } else {
2065ffd83dbSDimitry Andric     LI.addTopLevelLoop(NewLoop);
2075ffd83dbSDimitry Andric   }
2085ffd83dbSDimitry Andric 
2095ffd83dbSDimitry Andric   // Add the guard blocks to the new loop. The first guard block is
2105ffd83dbSDimitry Andric   // the head of all the backedges, and it is the first to be inserted
2115ffd83dbSDimitry Andric   // in the loop. This ensures that it is recognized as the
2125ffd83dbSDimitry Andric   // header. Since the new loop is already in LoopInfo, the new blocks
2135ffd83dbSDimitry Andric   // are also propagated up the chain of parent loops.
214bdd1243dSDimitry Andric   for (auto *G : GuardBlocks) {
2155ffd83dbSDimitry Andric     LLVM_DEBUG(dbgs() << "added guard block: " << G->getName() << "\n");
2165ffd83dbSDimitry Andric     NewLoop->addBasicBlockToLoop(G, LI);
2175ffd83dbSDimitry Andric   }
2185ffd83dbSDimitry Andric 
2195ffd83dbSDimitry Andric   // Add the SCC blocks to the new loop.
220bdd1243dSDimitry Andric   for (auto *BB : Blocks) {
2215ffd83dbSDimitry Andric     NewLoop->addBlockEntry(BB);
2225ffd83dbSDimitry Andric     if (LI.getLoopFor(BB) == ParentLoop) {
2235ffd83dbSDimitry Andric       LLVM_DEBUG(dbgs() << "moved block from parent: " << BB->getName()
2245ffd83dbSDimitry Andric                         << "\n");
2255ffd83dbSDimitry Andric       LI.changeLoopFor(BB, NewLoop);
2265ffd83dbSDimitry Andric     } else {
2275ffd83dbSDimitry Andric       LLVM_DEBUG(dbgs() << "added block from child: " << BB->getName() << "\n");
2285ffd83dbSDimitry Andric     }
2295ffd83dbSDimitry Andric   }
2305ffd83dbSDimitry Andric   LLVM_DEBUG(dbgs() << "header for new loop: "
2315ffd83dbSDimitry Andric                     << NewLoop->getHeader()->getName() << "\n");
2325ffd83dbSDimitry Andric 
2335ffd83dbSDimitry Andric   reconnectChildLoops(LI, ParentLoop, NewLoop, Blocks, Headers);
2345ffd83dbSDimitry Andric 
2355ffd83dbSDimitry Andric   NewLoop->verifyLoop();
2365ffd83dbSDimitry Andric   if (ParentLoop) {
2375ffd83dbSDimitry Andric     ParentLoop->verifyLoop();
2385ffd83dbSDimitry Andric   }
2395ffd83dbSDimitry Andric #if defined(EXPENSIVE_CHECKS)
2405ffd83dbSDimitry Andric   LI.verify(DT);
2415ffd83dbSDimitry Andric #endif // EXPENSIVE_CHECKS
2425ffd83dbSDimitry Andric }
2435ffd83dbSDimitry Andric 
2445ffd83dbSDimitry Andric namespace llvm {
2455ffd83dbSDimitry Andric // Enable the graph traits required for traversing a Loop body.
2465ffd83dbSDimitry Andric template <> struct GraphTraits<Loop> : LoopBodyTraits {};
2475ffd83dbSDimitry Andric } // namespace llvm
2485ffd83dbSDimitry Andric 
2495ffd83dbSDimitry Andric // Overloaded wrappers to go with the function template below.
unwrapBlock(BasicBlock * B)2505ffd83dbSDimitry Andric static BasicBlock *unwrapBlock(BasicBlock *B) { return B; }
unwrapBlock(LoopBodyTraits::NodeRef & N)2515ffd83dbSDimitry Andric static BasicBlock *unwrapBlock(LoopBodyTraits::NodeRef &N) { return N.second; }
2525ffd83dbSDimitry Andric 
createNaturalLoop(LoopInfo & LI,DominatorTree & DT,Function * F,SetVector<BasicBlock * > & Blocks,SetVector<BasicBlock * > & Headers)2535ffd83dbSDimitry Andric static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Function *F,
2545ffd83dbSDimitry Andric                               SetVector<BasicBlock *> &Blocks,
2555ffd83dbSDimitry Andric                               SetVector<BasicBlock *> &Headers) {
2565ffd83dbSDimitry Andric   createNaturalLoopInternal(LI, DT, nullptr, Blocks, Headers);
2575ffd83dbSDimitry Andric }
2585ffd83dbSDimitry Andric 
createNaturalLoop(LoopInfo & LI,DominatorTree & DT,Loop & L,SetVector<BasicBlock * > & Blocks,SetVector<BasicBlock * > & Headers)2595ffd83dbSDimitry Andric static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Loop &L,
2605ffd83dbSDimitry Andric                               SetVector<BasicBlock *> &Blocks,
2615ffd83dbSDimitry Andric                               SetVector<BasicBlock *> &Headers) {
2625ffd83dbSDimitry Andric   createNaturalLoopInternal(LI, DT, &L, Blocks, Headers);
2635ffd83dbSDimitry Andric }
2645ffd83dbSDimitry Andric 
2655ffd83dbSDimitry Andric // Convert irreducible SCCs; Graph G may be a Function* or a Loop&.
2665ffd83dbSDimitry Andric template <class Graph>
makeReducible(LoopInfo & LI,DominatorTree & DT,Graph && G)2675ffd83dbSDimitry Andric static bool makeReducible(LoopInfo &LI, DominatorTree &DT, Graph &&G) {
2685ffd83dbSDimitry Andric   bool Changed = false;
2695ffd83dbSDimitry Andric   for (auto Scc = scc_begin(G); !Scc.isAtEnd(); ++Scc) {
2705ffd83dbSDimitry Andric     if (Scc->size() < 2)
2715ffd83dbSDimitry Andric       continue;
2725ffd83dbSDimitry Andric     SetVector<BasicBlock *> Blocks;
2735ffd83dbSDimitry Andric     LLVM_DEBUG(dbgs() << "Found SCC:");
2745ffd83dbSDimitry Andric     for (auto N : *Scc) {
2755ffd83dbSDimitry Andric       auto BB = unwrapBlock(N);
2765ffd83dbSDimitry Andric       LLVM_DEBUG(dbgs() << " " << BB->getName());
2775ffd83dbSDimitry Andric       Blocks.insert(BB);
2785ffd83dbSDimitry Andric     }
2795ffd83dbSDimitry Andric     LLVM_DEBUG(dbgs() << "\n");
2805ffd83dbSDimitry Andric 
2815ffd83dbSDimitry Andric     // Minor optimization: The SCC blocks are usually discovered in an order
2825ffd83dbSDimitry Andric     // that is the opposite of the order in which these blocks appear as branch
2835ffd83dbSDimitry Andric     // targets. This results in a lot of condition inversions in the control
2845ffd83dbSDimitry Andric     // flow out of the new ControlFlowHub, which can be mitigated if the orders
2855ffd83dbSDimitry Andric     // match. So we discover the headers using the reverse of the block order.
2865ffd83dbSDimitry Andric     SetVector<BasicBlock *> Headers;
2875ffd83dbSDimitry Andric     LLVM_DEBUG(dbgs() << "Found headers:");
288bdd1243dSDimitry Andric     for (auto *BB : reverse(Blocks)) {
2895ffd83dbSDimitry Andric       for (const auto P : predecessors(BB)) {
2905ffd83dbSDimitry Andric         // Skip unreachable predecessors.
2915ffd83dbSDimitry Andric         if (!DT.isReachableFromEntry(P))
2925ffd83dbSDimitry Andric           continue;
2935ffd83dbSDimitry Andric         if (!Blocks.count(P)) {
2945ffd83dbSDimitry Andric           LLVM_DEBUG(dbgs() << " " << BB->getName());
2955ffd83dbSDimitry Andric           Headers.insert(BB);
2965ffd83dbSDimitry Andric           break;
2975ffd83dbSDimitry Andric         }
2985ffd83dbSDimitry Andric       }
2995ffd83dbSDimitry Andric     }
3005ffd83dbSDimitry Andric     LLVM_DEBUG(dbgs() << "\n");
3015ffd83dbSDimitry Andric 
3025ffd83dbSDimitry Andric     if (Headers.size() == 1) {
3035ffd83dbSDimitry Andric       assert(LI.isLoopHeader(Headers.front()));
3045ffd83dbSDimitry Andric       LLVM_DEBUG(dbgs() << "Natural loop with a single header: skipped\n");
3055ffd83dbSDimitry Andric       continue;
3065ffd83dbSDimitry Andric     }
3075ffd83dbSDimitry Andric     createNaturalLoop(LI, DT, G, Blocks, Headers);
3085ffd83dbSDimitry Andric     Changed = true;
3095ffd83dbSDimitry Andric   }
3105ffd83dbSDimitry Andric   return Changed;
3115ffd83dbSDimitry Andric }
3125ffd83dbSDimitry Andric 
FixIrreducibleImpl(Function & F,LoopInfo & LI,DominatorTree & DT)313e8d8bef9SDimitry Andric static bool FixIrreducibleImpl(Function &F, LoopInfo &LI, DominatorTree &DT) {
3145ffd83dbSDimitry Andric   LLVM_DEBUG(dbgs() << "===== Fix irreducible control-flow in function: "
3155ffd83dbSDimitry Andric                     << F.getName() << "\n");
3165ffd83dbSDimitry Andric 
317*5f757f3fSDimitry Andric   assert(hasOnlySimpleTerminator(F) && "Unsupported block terminator.");
318*5f757f3fSDimitry Andric 
3195ffd83dbSDimitry Andric   bool Changed = false;
3205ffd83dbSDimitry Andric   SmallVector<Loop *, 8> WorkList;
3215ffd83dbSDimitry Andric 
3225ffd83dbSDimitry Andric   LLVM_DEBUG(dbgs() << "visiting top-level\n");
3235ffd83dbSDimitry Andric   Changed |= makeReducible(LI, DT, &F);
3245ffd83dbSDimitry Andric 
3255ffd83dbSDimitry Andric   // Any SCCs reduced are now already in the list of top-level loops, so simply
3265ffd83dbSDimitry Andric   // add them all to the worklist.
327e8d8bef9SDimitry Andric   append_range(WorkList, LI);
3285ffd83dbSDimitry Andric 
3295ffd83dbSDimitry Andric   while (!WorkList.empty()) {
330e8d8bef9SDimitry Andric     auto L = WorkList.pop_back_val();
3315ffd83dbSDimitry Andric     LLVM_DEBUG(dbgs() << "visiting loop with header "
3325ffd83dbSDimitry Andric                       << L->getHeader()->getName() << "\n");
3335ffd83dbSDimitry Andric     Changed |= makeReducible(LI, DT, *L);
3345ffd83dbSDimitry Andric     // Any SCCs reduced are now already in the list of child loops, so simply
3355ffd83dbSDimitry Andric     // add them all to the worklist.
3365ffd83dbSDimitry Andric     WorkList.append(L->begin(), L->end());
3375ffd83dbSDimitry Andric   }
3385ffd83dbSDimitry Andric 
3395ffd83dbSDimitry Andric   return Changed;
3405ffd83dbSDimitry Andric }
341e8d8bef9SDimitry Andric 
runOnFunction(Function & F)342e8d8bef9SDimitry Andric bool FixIrreducible::runOnFunction(Function &F) {
343e8d8bef9SDimitry Andric   auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
344e8d8bef9SDimitry Andric   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
345e8d8bef9SDimitry Andric   return FixIrreducibleImpl(F, LI, DT);
346e8d8bef9SDimitry Andric }
347e8d8bef9SDimitry Andric 
run(Function & F,FunctionAnalysisManager & AM)348e8d8bef9SDimitry Andric PreservedAnalyses FixIrreduciblePass::run(Function &F,
349e8d8bef9SDimitry Andric                                           FunctionAnalysisManager &AM) {
350e8d8bef9SDimitry Andric   auto &LI = AM.getResult<LoopAnalysis>(F);
351e8d8bef9SDimitry Andric   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
352e8d8bef9SDimitry Andric   if (!FixIrreducibleImpl(F, LI, DT))
353e8d8bef9SDimitry Andric     return PreservedAnalyses::all();
354e8d8bef9SDimitry Andric   PreservedAnalyses PA;
355e8d8bef9SDimitry Andric   PA.preserve<LoopAnalysis>();
356e8d8bef9SDimitry Andric   PA.preserve<DominatorTreeAnalysis>();
357e8d8bef9SDimitry Andric   return PA;
358e8d8bef9SDimitry Andric }
359