1303231Sdim//=- WebAssemblyFixIrreducibleControlFlow.cpp - Fix irreducible control flow -// 2303231Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6303231Sdim// 7303231Sdim//===----------------------------------------------------------------------===// 8303231Sdim/// 9303231Sdim/// \file 10353358Sdim/// This file implements a pass that removes irreducible control flow. 11353358Sdim/// Irreducible control flow means multiple-entry loops, which this pass 12353358Sdim/// transforms to have a single entry. 13303231Sdim/// 14303231Sdim/// Note that LLVM has a generic pass that lowers irreducible control flow, but 15303231Sdim/// it linearizes control flow, turning diamonds into two triangles, which is 16303231Sdim/// both unnecessary and undesirable for WebAssembly. 17303231Sdim/// 18353358Sdim/// The big picture: We recursively process each "region", defined as a group 19353358Sdim/// of blocks with a single entry and no branches back to that entry. A region 20353358Sdim/// may be the entire function body, or the inner part of a loop, i.e., the 21353358Sdim/// loop's body without branches back to the loop entry. In each region we fix 22353358Sdim/// up multi-entry loops by adding a new block that can dispatch to each of the 23353358Sdim/// loop entries, based on the value of a label "helper" variable, and we 24353358Sdim/// replace direct branches to the entries with assignments to the label 25353358Sdim/// variable and a branch to the dispatch block. Then the dispatch block is the 26353358Sdim/// single entry in the loop containing the previous multiple entries. After 27353358Sdim/// ensuring all the loops in a region are reducible, we recurse into them. The 28353358Sdim/// total time complexity of this pass is: 29303231Sdim/// 30353358Sdim/// O(NumBlocks * NumNestedLoops * NumIrreducibleLoops + 31353358Sdim/// NumLoops * NumLoops) 32353358Sdim/// 33353358Sdim/// This pass is similar to what the Relooper [1] does. Both identify looping 34353358Sdim/// code that requires multiple entries, and resolve it in a similar way (in 35353358Sdim/// Relooper terminology, we implement a Multiple shape in a Loop shape). Note 36344779Sdim/// also that like the Relooper, we implement a "minimal" intervention: we only 37344779Sdim/// use the "label" helper for the blocks we absolutely must and no others. We 38353358Sdim/// also prioritize code size and do not duplicate code in order to resolve 39353358Sdim/// irreducibility. The graph algorithms for finding loops and entries and so 40353358Sdim/// forth are also similar to the Relooper. The main differences between this 41353358Sdim/// pass and the Relooper are: 42344779Sdim/// 43353358Sdim/// * We just care about irreducibility, so we just look at loops. 44353358Sdim/// * The Relooper emits structured control flow (with ifs etc.), while we 45353358Sdim/// emit a CFG. 46344779Sdim/// 47344779Sdim/// [1] Alon Zakai. 2011. Emscripten: an LLVM-to-JavaScript compiler. In 48344779Sdim/// Proceedings of the ACM international conference companion on Object oriented 49344779Sdim/// programming systems languages and applications companion (SPLASH '11). ACM, 50344779Sdim/// New York, NY, USA, 301-312. DOI=10.1145/2048147.2048224 51344779Sdim/// http://doi.acm.org/10.1145/2048147.2048224 52344779Sdim/// 53303231Sdim//===----------------------------------------------------------------------===// 54303231Sdim 55321369Sdim#include "MCTargetDesc/WebAssemblyMCTargetDesc.h" 56303231Sdim#include "WebAssembly.h" 57303231Sdim#include "WebAssemblySubtarget.h" 58303231Sdim#include "llvm/CodeGen/MachineInstrBuilder.h" 59360784Sdim#include "llvm/Support/Debug.h" 60303231Sdimusing namespace llvm; 61303231Sdim 62303231Sdim#define DEBUG_TYPE "wasm-fix-irreducible-control-flow" 63303231Sdim 64303231Sdimnamespace { 65303231Sdim 66353358Sdimusing BlockVector = SmallVector<MachineBasicBlock *, 4>; 67353358Sdimusing BlockSet = SmallPtrSet<MachineBasicBlock *, 4>; 68353358Sdim 69353358Sdim// Calculates reachability in a region. Ignores branches to blocks outside of 70353358Sdim// the region, and ignores branches to the region entry (for the case where 71353358Sdim// the region is the inner part of a loop). 72353358Sdimclass ReachabilityGraph { 73303231Sdimpublic: 74353358Sdim ReachabilityGraph(MachineBasicBlock *Entry, const BlockSet &Blocks) 75353358Sdim : Entry(Entry), Blocks(Blocks) { 76353358Sdim#ifndef NDEBUG 77353358Sdim // The region must have a single entry. 78353358Sdim for (auto *MBB : Blocks) { 79353358Sdim if (MBB != Entry) { 80353358Sdim for (auto *Pred : MBB->predecessors()) { 81353358Sdim assert(inRegion(Pred)); 82353358Sdim } 83353358Sdim } 84353358Sdim } 85353358Sdim#endif 86353358Sdim calculate(); 87353358Sdim } 88303231Sdim 89353358Sdim bool canReach(MachineBasicBlock *From, MachineBasicBlock *To) const { 90353358Sdim assert(inRegion(From) && inRegion(To)); 91353358Sdim auto I = Reachable.find(From); 92353358Sdim if (I == Reachable.end()) 93353358Sdim return false; 94353358Sdim return I->second.count(To); 95353358Sdim } 96341825Sdim 97353358Sdim // "Loopers" are blocks that are in a loop. We detect these by finding blocks 98353358Sdim // that can reach themselves. 99353358Sdim const BlockSet &getLoopers() const { return Loopers; } 100353358Sdim 101353358Sdim // Get all blocks that are loop entries. 102353358Sdim const BlockSet &getLoopEntries() const { return LoopEntries; } 103353358Sdim 104353358Sdim // Get all blocks that enter a particular loop from outside. 105353358Sdim const BlockSet &getLoopEnterers(MachineBasicBlock *LoopEntry) const { 106353358Sdim assert(inRegion(LoopEntry)); 107353358Sdim auto I = LoopEnterers.find(LoopEntry); 108353358Sdim assert(I != LoopEnterers.end()); 109353358Sdim return I->second; 110353358Sdim } 111353358Sdim 112344779Sdimprivate: 113353358Sdim MachineBasicBlock *Entry; 114353358Sdim const BlockSet &Blocks; 115303231Sdim 116353358Sdim BlockSet Loopers, LoopEntries; 117353358Sdim DenseMap<MachineBasicBlock *, BlockSet> LoopEnterers; 118303231Sdim 119353358Sdim bool inRegion(MachineBasicBlock *MBB) const { return Blocks.count(MBB); } 120353358Sdim 121353358Sdim // Maps a block to all the other blocks it can reach. 122344779Sdim DenseMap<MachineBasicBlock *, BlockSet> Reachable; 123303231Sdim 124353358Sdim void calculate() { 125353358Sdim // Reachability computation work list. Contains pairs of recent additions 126353358Sdim // (A, B) where we just added a link A => B. 127353358Sdim using BlockPair = std::pair<MachineBasicBlock *, MachineBasicBlock *>; 128353358Sdim SmallVector<BlockPair, 4> WorkList; 129303231Sdim 130353358Sdim // Add all relevant direct branches. 131353358Sdim for (auto *MBB : Blocks) { 132353358Sdim for (auto *Succ : MBB->successors()) { 133353358Sdim if (Succ != Entry && inRegion(Succ)) { 134353358Sdim Reachable[MBB].insert(Succ); 135353358Sdim WorkList.emplace_back(MBB, Succ); 136353358Sdim } 137344779Sdim } 138344779Sdim } 139303231Sdim 140353358Sdim while (!WorkList.empty()) { 141353358Sdim MachineBasicBlock *MBB, *Succ; 142353358Sdim std::tie(MBB, Succ) = WorkList.pop_back_val(); 143353358Sdim assert(inRegion(MBB) && Succ != Entry && inRegion(Succ)); 144353358Sdim if (MBB != Entry) { 145353358Sdim // We recently added MBB => Succ, and that means we may have enabled 146353358Sdim // Pred => MBB => Succ. 147353358Sdim for (auto *Pred : MBB->predecessors()) { 148353358Sdim if (Reachable[Pred].insert(Succ).second) { 149353358Sdim WorkList.emplace_back(Pred, Succ); 150353358Sdim } 151353358Sdim } 152353358Sdim } 153344779Sdim } 154303231Sdim 155353358Sdim // Blocks that can return to themselves are in a loop. 156353358Sdim for (auto *MBB : Blocks) { 157353358Sdim if (canReach(MBB, MBB)) { 158353358Sdim Loopers.insert(MBB); 159344779Sdim } 160344779Sdim } 161353358Sdim assert(!Loopers.count(Entry)); 162353358Sdim 163353358Sdim // Find the loop entries - loopers reachable from blocks not in that loop - 164353358Sdim // and those outside blocks that reach them, the "loop enterers". 165353358Sdim for (auto *Looper : Loopers) { 166353358Sdim for (auto *Pred : Looper->predecessors()) { 167353358Sdim // Pred can reach Looper. If Looper can reach Pred, it is in the loop; 168353358Sdim // otherwise, it is a block that enters into the loop. 169353358Sdim if (!canReach(Looper, Pred)) { 170353358Sdim LoopEntries.insert(Looper); 171353358Sdim LoopEnterers[Looper].insert(Pred); 172353358Sdim } 173353358Sdim } 174353358Sdim } 175303231Sdim } 176303231Sdim}; 177303231Sdim 178353358Sdim// Finds the blocks in a single-entry loop, given the loop entry and the 179353358Sdim// list of blocks that enter the loop. 180353358Sdimclass LoopBlocks { 181353358Sdimpublic: 182353358Sdim LoopBlocks(MachineBasicBlock *Entry, const BlockSet &Enterers) 183353358Sdim : Entry(Entry), Enterers(Enterers) { 184353358Sdim calculate(); 185344779Sdim } 186303231Sdim 187353358Sdim BlockSet &getBlocks() { return Blocks; } 188303231Sdim 189353358Sdimprivate: 190353358Sdim MachineBasicBlock *Entry; 191353358Sdim const BlockSet &Enterers; 192303231Sdim 193353358Sdim BlockSet Blocks; 194353358Sdim 195353358Sdim void calculate() { 196353358Sdim // Going backwards from the loop entry, if we ignore the blocks entering 197353358Sdim // from outside, we will traverse all the blocks in the loop. 198353358Sdim BlockVector WorkList; 199353358Sdim BlockSet AddedToWorkList; 200353358Sdim Blocks.insert(Entry); 201353358Sdim for (auto *Pred : Entry->predecessors()) { 202353358Sdim if (!Enterers.count(Pred)) { 203353358Sdim WorkList.push_back(Pred); 204353358Sdim AddedToWorkList.insert(Pred); 205344779Sdim } 206344779Sdim } 207303231Sdim 208353358Sdim while (!WorkList.empty()) { 209353358Sdim auto *MBB = WorkList.pop_back_val(); 210353358Sdim assert(!Enterers.count(MBB)); 211353358Sdim if (Blocks.insert(MBB).second) { 212353358Sdim for (auto *Pred : MBB->predecessors()) { 213353358Sdim if (!AddedToWorkList.count(Pred)) { 214353358Sdim WorkList.push_back(Pred); 215353358Sdim AddedToWorkList.insert(Pred); 216353358Sdim } 217353358Sdim } 218344779Sdim } 219344779Sdim } 220344779Sdim } 221353358Sdim}; 222303231Sdim 223353358Sdimclass WebAssemblyFixIrreducibleControlFlow final : public MachineFunctionPass { 224353358Sdim StringRef getPassName() const override { 225353358Sdim return "WebAssembly Fix Irreducible Control Flow"; 226344779Sdim } 227303231Sdim 228353358Sdim bool runOnMachineFunction(MachineFunction &MF) override; 229353358Sdim 230353358Sdim bool processRegion(MachineBasicBlock *Entry, BlockSet &Blocks, 231353358Sdim MachineFunction &MF); 232353358Sdim 233353358Sdim void makeSingleEntryLoop(BlockSet &Entries, BlockSet &Blocks, 234353358Sdim MachineFunction &MF, const ReachabilityGraph &Graph); 235353358Sdim 236353358Sdimpublic: 237353358Sdim static char ID; // Pass identification, replacement for typeid 238353358Sdim WebAssemblyFixIrreducibleControlFlow() : MachineFunctionPass(ID) {} 239353358Sdim}; 240353358Sdim 241353358Sdimbool WebAssemblyFixIrreducibleControlFlow::processRegion( 242353358Sdim MachineBasicBlock *Entry, BlockSet &Blocks, MachineFunction &MF) { 243353358Sdim bool Changed = false; 244353358Sdim 245353358Sdim // Remove irreducibility before processing child loops, which may take 246353358Sdim // multiple iterations. 247353358Sdim while (true) { 248353358Sdim ReachabilityGraph Graph(Entry, Blocks); 249353358Sdim 250353358Sdim bool FoundIrreducibility = false; 251353358Sdim 252353358Sdim for (auto *LoopEntry : Graph.getLoopEntries()) { 253353358Sdim // Find mutual entries - all entries which can reach this one, and 254353358Sdim // are reached by it (that always includes LoopEntry itself). All mutual 255353358Sdim // entries must be in the same loop, so if we have more than one, then we 256353358Sdim // have irreducible control flow. 257353358Sdim // 258353358Sdim // Note that irreducibility may involve inner loops, e.g. imagine A 259353358Sdim // starts one loop, and it has B inside it which starts an inner loop. 260353358Sdim // If we add a branch from all the way on the outside to B, then in a 261353358Sdim // sense B is no longer an "inner" loop, semantically speaking. We will 262353358Sdim // fix that irreducibility by adding a block that dispatches to either 263353358Sdim // either A or B, so B will no longer be an inner loop in our output. 264353358Sdim // (A fancier approach might try to keep it as such.) 265353358Sdim // 266353358Sdim // Note that we still need to recurse into inner loops later, to handle 267353358Sdim // the case where the irreducibility is entirely nested - we would not 268353358Sdim // be able to identify that at this point, since the enclosing loop is 269353358Sdim // a group of blocks all of whom can reach each other. (We'll see the 270353358Sdim // irreducibility after removing branches to the top of that enclosing 271353358Sdim // loop.) 272353358Sdim BlockSet MutualLoopEntries; 273353358Sdim MutualLoopEntries.insert(LoopEntry); 274353358Sdim for (auto *OtherLoopEntry : Graph.getLoopEntries()) { 275353358Sdim if (OtherLoopEntry != LoopEntry && 276353358Sdim Graph.canReach(LoopEntry, OtherLoopEntry) && 277353358Sdim Graph.canReach(OtherLoopEntry, LoopEntry)) { 278353358Sdim MutualLoopEntries.insert(OtherLoopEntry); 279353358Sdim } 280353358Sdim } 281353358Sdim 282353358Sdim if (MutualLoopEntries.size() > 1) { 283353358Sdim makeSingleEntryLoop(MutualLoopEntries, Blocks, MF, Graph); 284353358Sdim FoundIrreducibility = true; 285353358Sdim Changed = true; 286344779Sdim break; 287303231Sdim } 288303231Sdim } 289353358Sdim // Only go on to actually process the inner loops when we are done 290353358Sdim // removing irreducible control flow and changing the graph. Modifying 291353358Sdim // the graph as we go is possible, and that might let us avoid looking at 292353358Sdim // the already-fixed loops again if we are careful, but all that is 293353358Sdim // complex and bug-prone. Since irreducible loops are rare, just starting 294353358Sdim // another iteration is best. 295353358Sdim if (FoundIrreducibility) { 296353358Sdim continue; 297353358Sdim } 298353358Sdim 299353358Sdim for (auto *LoopEntry : Graph.getLoopEntries()) { 300353358Sdim LoopBlocks InnerBlocks(LoopEntry, Graph.getLoopEnterers(LoopEntry)); 301353358Sdim // Each of these calls to processRegion may change the graph, but are 302353358Sdim // guaranteed not to interfere with each other. The only changes we make 303353358Sdim // to the graph are to add blocks on the way to a loop entry. As the 304353358Sdim // loops are disjoint, that means we may only alter branches that exit 305353358Sdim // another loop, which are ignored when recursing into that other loop 306353358Sdim // anyhow. 307353358Sdim if (processRegion(LoopEntry, InnerBlocks.getBlocks(), MF)) { 308353358Sdim Changed = true; 309353358Sdim } 310353358Sdim } 311353358Sdim 312353358Sdim return Changed; 313303231Sdim } 314353358Sdim} 315303231Sdim 316353358Sdim// Given a set of entries to a single loop, create a single entry for that 317353358Sdim// loop by creating a dispatch block for them, routing control flow using 318353358Sdim// a helper variable. Also updates Blocks with any new blocks created, so 319353358Sdim// that we properly track all the blocks in the region. But this does not update 320353358Sdim// ReachabilityGraph; this will be updated in the caller of this function as 321353358Sdim// needed. 322353358Sdimvoid WebAssemblyFixIrreducibleControlFlow::makeSingleEntryLoop( 323353358Sdim BlockSet &Entries, BlockSet &Blocks, MachineFunction &MF, 324353358Sdim const ReachabilityGraph &Graph) { 325353358Sdim assert(Entries.size() >= 2); 326303231Sdim 327344779Sdim // Sort the entries to ensure a deterministic build. 328353358Sdim BlockVector SortedEntries(Entries.begin(), Entries.end()); 329344779Sdim llvm::sort(SortedEntries, 330344779Sdim [&](const MachineBasicBlock *A, const MachineBasicBlock *B) { 331344779Sdim auto ANum = A->getNumber(); 332344779Sdim auto BNum = B->getNumber(); 333344779Sdim return ANum < BNum; 334344779Sdim }); 335303231Sdim 336344779Sdim#ifndef NDEBUG 337344779Sdim for (auto Block : SortedEntries) 338344779Sdim assert(Block->getNumber() != -1); 339344779Sdim if (SortedEntries.size() > 1) { 340353358Sdim for (auto I = SortedEntries.begin(), E = SortedEntries.end() - 1; I != E; 341353358Sdim ++I) { 342344779Sdim auto ANum = (*I)->getNumber(); 343344779Sdim auto BNum = (*(std::next(I)))->getNumber(); 344344779Sdim assert(ANum != BNum); 345344779Sdim } 346344779Sdim } 347344779Sdim#endif 348344779Sdim 349344779Sdim // Create a dispatch block which will contain a jump table to the entries. 350303231Sdim MachineBasicBlock *Dispatch = MF.CreateMachineBasicBlock(); 351303231Sdim MF.insert(MF.end(), Dispatch); 352353358Sdim Blocks.insert(Dispatch); 353303231Sdim 354303231Sdim // Add the jump table. 355303231Sdim const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 356353358Sdim MachineInstrBuilder MIB = 357353358Sdim BuildMI(Dispatch, DebugLoc(), TII.get(WebAssembly::BR_TABLE_I32)); 358303231Sdim 359303231Sdim // Add the register which will be used to tell the jump table which block to 360303231Sdim // jump to. 361303231Sdim MachineRegisterInfo &MRI = MF.getRegInfo(); 362360784Sdim Register Reg = MRI.createVirtualRegister(&WebAssembly::I32RegClass); 363303231Sdim MIB.addReg(Reg); 364303231Sdim 365344779Sdim // Compute the indices in the superheader, one for each bad block, and 366344779Sdim // add them as successors. 367303231Sdim DenseMap<MachineBasicBlock *, unsigned> Indices; 368353358Sdim for (auto *Entry : SortedEntries) { 369353358Sdim auto Pair = Indices.insert(std::make_pair(Entry, 0)); 370353358Sdim assert(Pair.second); 371303231Sdim 372303231Sdim unsigned Index = MIB.getInstr()->getNumExplicitOperands() - 1; 373303231Sdim Pair.first->second = Index; 374303231Sdim 375353358Sdim MIB.addMBB(Entry); 376353358Sdim Dispatch->addSuccessor(Entry); 377344779Sdim } 378303231Sdim 379353358Sdim // Rewrite the problematic successors for every block that wants to reach 380353358Sdim // the bad blocks. For simplicity, we just introduce a new block for every 381353358Sdim // edge we need to rewrite. (Fancier things are possible.) 382344779Sdim 383353358Sdim BlockVector AllPreds; 384353358Sdim for (auto *Entry : SortedEntries) { 385353358Sdim for (auto *Pred : Entry->predecessors()) { 386344779Sdim if (Pred != Dispatch) { 387344779Sdim AllPreds.push_back(Pred); 388344779Sdim } 389344779Sdim } 390303231Sdim } 391303231Sdim 392353358Sdim // This set stores predecessors within this loop. 393353358Sdim DenseSet<MachineBasicBlock *> InLoop; 394353358Sdim for (auto *Pred : AllPreds) { 395353358Sdim for (auto *Entry : Pred->successors()) { 396353358Sdim if (!Entries.count(Entry)) 397303231Sdim continue; 398353358Sdim if (Graph.canReach(Entry, Pred)) { 399353358Sdim InLoop.insert(Pred); 400353358Sdim break; 401344779Sdim } 402353358Sdim } 403353358Sdim } 404303231Sdim 405353358Sdim // Record if each entry has a layout predecessor. This map stores 406353358Sdim // <<Predecessor is within the loop?, loop entry>, layout predecessor> 407353358Sdim std::map<std::pair<bool, MachineBasicBlock *>, MachineBasicBlock *> 408353358Sdim EntryToLayoutPred; 409353358Sdim for (auto *Pred : AllPreds) 410353358Sdim for (auto *Entry : Pred->successors()) 411353358Sdim if (Entries.count(Entry) && Pred->isLayoutSuccessor(Entry)) 412353358Sdim EntryToLayoutPred[std::make_pair(InLoop.count(Pred), Entry)] = Pred; 413353358Sdim 414353358Sdim // We need to create at most two routing blocks per entry: one for 415353358Sdim // predecessors outside the loop and one for predecessors inside the loop. 416353358Sdim // This map stores 417353358Sdim // <<Predecessor is within the loop?, loop entry>, routing block> 418353358Sdim std::map<std::pair<bool, MachineBasicBlock *>, MachineBasicBlock *> Map; 419353358Sdim for (auto *Pred : AllPreds) { 420353358Sdim bool PredInLoop = InLoop.count(Pred); 421353358Sdim for (auto *Entry : Pred->successors()) { 422353358Sdim if (!Entries.count(Entry) || 423353358Sdim Map.count(std::make_pair(InLoop.count(Pred), Entry))) 424353358Sdim continue; 425353358Sdim // If there exists a layout predecessor of this entry and this predecessor 426353358Sdim // is not that, we rather create a routing block after that layout 427353358Sdim // predecessor to save a branch. 428353358Sdim if (EntryToLayoutPred.count(std::make_pair(PredInLoop, Entry)) && 429353358Sdim EntryToLayoutPred[std::make_pair(PredInLoop, Entry)] != Pred) 430353358Sdim continue; 431353358Sdim 432344779Sdim // This is a successor we need to rewrite. 433353358Sdim MachineBasicBlock *Routing = MF.CreateMachineBasicBlock(); 434353358Sdim MF.insert(Pred->isLayoutSuccessor(Entry) 435353358Sdim ? MachineFunction::iterator(Entry) 436353358Sdim : MF.end(), 437353358Sdim Routing); 438353358Sdim Blocks.insert(Routing); 439303231Sdim 440303231Sdim // Set the jump table's register of the index of the block we wish to 441303231Sdim // jump to, and jump to the jump table. 442353358Sdim BuildMI(Routing, DebugLoc(), TII.get(WebAssembly::CONST_I32), Reg) 443353358Sdim .addImm(Indices[Entry]); 444353358Sdim BuildMI(Routing, DebugLoc(), TII.get(WebAssembly::BR)).addMBB(Dispatch); 445353358Sdim Routing->addSuccessor(Dispatch); 446353358Sdim Map[std::make_pair(PredInLoop, Entry)] = Routing; 447303231Sdim } 448353358Sdim } 449353358Sdim 450353358Sdim for (auto *Pred : AllPreds) { 451353358Sdim bool PredInLoop = InLoop.count(Pred); 452303231Sdim // Remap the terminator operands and the successor list. 453353358Sdim for (MachineInstr &Term : Pred->terminators()) 454303231Sdim for (auto &Op : Term.explicit_uses()) 455303231Sdim if (Op.isMBB() && Indices.count(Op.getMBB())) 456353358Sdim Op.setMBB(Map[std::make_pair(PredInLoop, Op.getMBB())]); 457353358Sdim 458353358Sdim for (auto *Succ : Pred->successors()) { 459353358Sdim if (!Entries.count(Succ)) 460353358Sdim continue; 461353358Sdim auto *Routing = Map[std::make_pair(PredInLoop, Succ)]; 462353358Sdim Pred->replaceSuccessor(Succ, Routing); 463353358Sdim } 464303231Sdim } 465303231Sdim 466303231Sdim // Create a fake default label, because br_table requires one. 467303231Sdim MIB.addMBB(MIB.getInstr() 468303231Sdim ->getOperand(MIB.getInstr()->getNumExplicitOperands() - 1) 469303231Sdim .getMBB()); 470303231Sdim} 471303231Sdim 472344779Sdim} // end anonymous namespace 473344779Sdim 474344779Sdimchar WebAssemblyFixIrreducibleControlFlow::ID = 0; 475344779SdimINITIALIZE_PASS(WebAssemblyFixIrreducibleControlFlow, DEBUG_TYPE, 476344779Sdim "Removes irreducible control flow", false, false) 477344779Sdim 478344779SdimFunctionPass *llvm::createWebAssemblyFixIrreducibleControlFlow() { 479344779Sdim return new WebAssemblyFixIrreducibleControlFlow(); 480344779Sdim} 481344779Sdim 482303231Sdimbool WebAssemblyFixIrreducibleControlFlow::runOnMachineFunction( 483303231Sdim MachineFunction &MF) { 484341825Sdim LLVM_DEBUG(dbgs() << "********** Fixing Irreducible Control Flow **********\n" 485341825Sdim "********** Function: " 486341825Sdim << MF.getName() << '\n'); 487303231Sdim 488353358Sdim // Start the recursive process on the entire function body. 489353358Sdim BlockSet AllBlocks; 490353358Sdim for (auto &MBB : MF) { 491353358Sdim AllBlocks.insert(&MBB); 492353358Sdim } 493303231Sdim 494353358Sdim if (LLVM_UNLIKELY(processRegion(&*MF.begin(), AllBlocks, MF))) { 495353358Sdim // We rewrote part of the function; recompute relevant things. 496303231Sdim MF.getRegInfo().invalidateLiveness(); 497303231Sdim MF.RenumberBlocks(); 498353358Sdim return true; 499303231Sdim } 500303231Sdim 501353358Sdim return false; 502303231Sdim} 503