1 //=- WebAssemblyFixIrreducibleControlFlow.cpp - Fix irreducible control flow -//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
10 /// This file implements a pass that removes irreducible control flow.
11 /// Irreducible control flow means multiple-entry loops, which this pass
14 /// Note that LLVM has a generic pass that lowers irreducible control flow, but
15 /// it linearizes control flow, turning diamonds into two triangles, which is
22 /// up multi-entry loops by adding a new block that can dispatch to each of the
44 ///  * The Relooper emits structured control flow (with ifs etc.), while we
47 /// [1] Alon Zakai. 2011. Emscripten: an LLVM-to-JavaScript compiler. In
50 /// New York, NY, USA, 301-312. DOI=10.1145/2048147.2048224
53 //===----------------------------------------------------------------------===//
63 #define DEBUG_TYPE "wasm-fix-irreducible-control-flow"
74                auto ANum = A->getNumber();  in getSortedEntries()
75                auto BNum = B->getNumber();  in getSortedEntries()
92         for (auto *Pred : MBB->predecessors()) {  in ReachabilityGraph()
106     return I->second.count(To);  in canReach()
121     return I->second;  in getLoopEnterers()
144       for (auto *Succ : MBB->successors()) {  in calculate()
159         for (auto *Pred : MBB->predecessors()) {  in calculate()
175     // Find the loop entries - loopers reachable from blocks not in that loop -  in calculate()
178       for (auto *Pred : Looper->predecessors()) {  in calculate()
190 // Finds the blocks in a single-entry loop, given the loop entry and the
213     for (auto *Pred : Entry->predecessors()) {  in calculate()
224         for (auto *Pred : MBB->predecessors()) {  in calculate()
235     return "WebAssembly Fix Irreducible Control Flow";  in getPassName()
262       // Find mutual entries - all entries which can reach this one, and  in processRegion()
265       // have irreducible control flow.  in processRegion()
282       // the case where the irreducibility is entirely nested - we would not  in processRegion()
305     // removing irreducible control flow and changing the graph. Modifying  in processRegion()
307     // the already-fixed loops again if we are careful, but all that is  in processRegion()
308     // complex and bug-prone. Since irreducible loops are rare, just starting  in processRegion()
332 // loop by creating a dispatch block for them, routing control flow using
347     assert(Block->getNumber() != -1);  in makeSingleEntryLoop()
349     for (auto I = SortedEntries.begin(), E = SortedEntries.end() - 1; I != E;  in makeSingleEntryLoop()
351       auto ANum = (*I)->getNumber();  in makeSingleEntryLoop()
352       auto BNum = (*(std::next(I)))->getNumber();  in makeSingleEntryLoop()
381     unsigned Index = MIB.getInstr()->getNumExplicitOperands() - 1;  in makeSingleEntryLoop()
382     Pair.first->second = Index;  in makeSingleEntryLoop()
385     Dispatch->addSuccessor(Entry);  in makeSingleEntryLoop()
394     for (auto *Pred : Entry->predecessors()) {  in makeSingleEntryLoop()
404     for (auto *Entry : Pred->successors()) {  in makeSingleEntryLoop()
420     for (auto *Entry : Pred->successors())  in makeSingleEntryLoop()
421       if (Entries.count(Entry) && Pred->isLayoutSuccessor(Entry))  in makeSingleEntryLoop()
433     for (auto *Entry : Pred->successors()) {  in makeSingleEntryLoop()
445       MF.insert(Pred->isLayoutSuccessor(Entry)  in makeSingleEntryLoop()
456       Routing->addSuccessor(Dispatch);  in makeSingleEntryLoop()
464     for (MachineInstr &Term : Pred->terminators())  in makeSingleEntryLoop()
469     for (auto *Succ : Pred->successors()) {  in makeSingleEntryLoop()
473       Pred->replaceSuccessor(Succ, Routing);  in makeSingleEntryLoop()
479                  ->getOperand(MIB.getInstr()->getNumExplicitOperands() - 1)  in makeSingleEntryLoop()
487                 "Removes irreducible control flow", false, false)
503 // TODO: This is fairly heavy-handed; find a better approach.
524   // liveness reflects the fact that these really are live-in values.  in addImplicitDefs()
535   LLVM_DEBUG(dbgs() << "********** Fixing Irreducible Control Flow **********\n"  in runOnMachineFunction()