1 files changed, 0 insertions, 501 deletions

diff --git a/contrib/llvm/lib/Target/WebAssembly/WebAssemblyFixIrreducibleControlFlow.cpp b/contrib/llvm/lib/Target/WebAssembly/WebAssemblyFixIrreducibleControlFlow.cpp
deleted file mode 100644
index 7d8e86d9b2c0..000000000000
--- a/contrib/llvm/lib/Target/WebAssembly/WebAssemblyFixIrreducibleControlFlow.cpp
+++ /dev/null
@@ -1,501 +0,0 @@
-//=- WebAssemblyFixIrreducibleControlFlow.cpp - Fix irreducible control flow -//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-///
-/// \file
-/// This file implements a pass that removes irreducible control flow.
-/// Irreducible control flow means multiple-entry loops, which this pass
-/// transforms to have a single entry.
-///
-/// Note that LLVM has a generic pass that lowers irreducible control flow, but
-/// it linearizes control flow, turning diamonds into two triangles, which is
-/// both unnecessary and undesirable for WebAssembly.
-///
-/// The big picture: We recursively process each "region", defined as a group
-/// of blocks with a single entry and no branches back to that entry. A region
-/// may be the entire function body, or the inner part of a loop, i.e., the
-/// loop's body without branches back to the loop entry. In each region we fix
-/// up multi-entry loops by adding a new block that can dispatch to each of the
-/// loop entries, based on the value of a label "helper" variable, and we
-/// replace direct branches to the entries with assignments to the label
-/// variable and a branch to the dispatch block. Then the dispatch block is the
-/// single entry in the loop containing the previous multiple entries. After
-/// ensuring all the loops in a region are reducible, we recurse into them. The
-/// total time complexity of this pass is:
-///
-///   O(NumBlocks * NumNestedLoops * NumIrreducibleLoops +
-///     NumLoops * NumLoops)
-///
-/// This pass is similar to what the Relooper [1] does. Both identify looping
-/// code that requires multiple entries, and resolve it in a similar way (in
-/// Relooper terminology, we implement a Multiple shape in a Loop shape). Note
-/// also that like the Relooper, we implement a "minimal" intervention: we only
-/// use the "label" helper for the blocks we absolutely must and no others. We
-/// also prioritize code size and do not duplicate code in order to resolve
-/// irreducibility. The graph algorithms for finding loops and entries and so
-/// forth are also similar to the Relooper. The main differences between this
-/// pass and the Relooper are:
-///
-///  * We just care about irreducibility, so we just look at loops.
-///  * The Relooper emits structured control flow (with ifs etc.), while we
-///    emit a CFG.
-///
-/// [1] Alon Zakai. 2011. Emscripten: an LLVM-to-JavaScript compiler. In
-/// Proceedings of the ACM international conference companion on Object oriented
-/// programming systems languages and applications companion (SPLASH '11). ACM,
-/// New York, NY, USA, 301-312. DOI=10.1145/2048147.2048224
-/// http://doi.acm.org/10.1145/2048147.2048224
-///
-//===----------------------------------------------------------------------===//
-
-#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
-#include "WebAssembly.h"
-#include "WebAssemblySubtarget.h"
-#include "llvm/CodeGen/MachineInstrBuilder.h"
-using namespace llvm;
-
-#define DEBUG_TYPE "wasm-fix-irreducible-control-flow"
-
-namespace {
-
-using BlockVector = SmallVector<MachineBasicBlock *, 4>;
-using BlockSet = SmallPtrSet<MachineBasicBlock *, 4>;
-
-// Calculates reachability in a region. Ignores branches to blocks outside of
-// the region, and ignores branches to the region entry (for the case where
-// the region is the inner part of a loop).
-class ReachabilityGraph {
-public:
-  ReachabilityGraph(MachineBasicBlock *Entry, const BlockSet &Blocks)
-      : Entry(Entry), Blocks(Blocks) {
-#ifndef NDEBUG
-    // The region must have a single entry.
-    for (auto *MBB : Blocks) {
-      if (MBB != Entry) {
-        for (auto *Pred : MBB->predecessors()) {
-          assert(inRegion(Pred));
-        }
-      }
-    }
-#endif
-    calculate();
-  }
-
-  bool canReach(MachineBasicBlock *From, MachineBasicBlock *To) const {
-    assert(inRegion(From) && inRegion(To));
-    auto I = Reachable.find(From);
-    if (I == Reachable.end())
-      return false;
-    return I->second.count(To);
-  }
-
-  // "Loopers" are blocks that are in a loop. We detect these by finding blocks
-  // that can reach themselves.
-  const BlockSet &getLoopers() const { return Loopers; }
-
-  // Get all blocks that are loop entries.
-  const BlockSet &getLoopEntries() const { return LoopEntries; }
-
-  // Get all blocks that enter a particular loop from outside.
-  const BlockSet &getLoopEnterers(MachineBasicBlock *LoopEntry) const {
-    assert(inRegion(LoopEntry));
-    auto I = LoopEnterers.find(LoopEntry);
-    assert(I != LoopEnterers.end());
-    return I->second;
-  }
-
-private:
-  MachineBasicBlock *Entry;
-  const BlockSet &Blocks;
-
-  BlockSet Loopers, LoopEntries;
-  DenseMap<MachineBasicBlock *, BlockSet> LoopEnterers;
-
-  bool inRegion(MachineBasicBlock *MBB) const { return Blocks.count(MBB); }
-
-  // Maps a block to all the other blocks it can reach.
-  DenseMap<MachineBasicBlock *, BlockSet> Reachable;
-
-  void calculate() {
-    // Reachability computation work list. Contains pairs of recent additions
-    // (A, B) where we just added a link A => B.
-    using BlockPair = std::pair<MachineBasicBlock *, MachineBasicBlock *>;
-    SmallVector<BlockPair, 4> WorkList;
-
-    // Add all relevant direct branches.
-    for (auto *MBB : Blocks) {
-      for (auto *Succ : MBB->successors()) {
-        if (Succ != Entry && inRegion(Succ)) {
-          Reachable[MBB].insert(Succ);
-          WorkList.emplace_back(MBB, Succ);
-        }
-      }
-    }
-
-    while (!WorkList.empty()) {
-      MachineBasicBlock *MBB, *Succ;
-      std::tie(MBB, Succ) = WorkList.pop_back_val();
-      assert(inRegion(MBB) && Succ != Entry && inRegion(Succ));
-      if (MBB != Entry) {
-        // We recently added MBB => Succ, and that means we may have enabled
-        // Pred => MBB => Succ.
-        for (auto *Pred : MBB->predecessors()) {
-          if (Reachable[Pred].insert(Succ).second) {
-            WorkList.emplace_back(Pred, Succ);
-          }
-        }
-      }
-    }
-
-    // Blocks that can return to themselves are in a loop.
-    for (auto *MBB : Blocks) {
-      if (canReach(MBB, MBB)) {
-        Loopers.insert(MBB);
-      }
-    }
-    assert(!Loopers.count(Entry));
-
-    // Find the loop entries - loopers reachable from blocks not in that loop -
-    // and those outside blocks that reach them, the "loop enterers".
-    for (auto *Looper : Loopers) {
-      for (auto *Pred : Looper->predecessors()) {
-        // Pred can reach Looper. If Looper can reach Pred, it is in the loop;
-        // otherwise, it is a block that enters into the loop.
-        if (!canReach(Looper, Pred)) {
-          LoopEntries.insert(Looper);
-          LoopEnterers[Looper].insert(Pred);
-        }
-      }
-    }
-  }
-};
-
-// Finds the blocks in a single-entry loop, given the loop entry and the
-// list of blocks that enter the loop.
-class LoopBlocks {
-public:
-  LoopBlocks(MachineBasicBlock *Entry, const BlockSet &Enterers)
-      : Entry(Entry), Enterers(Enterers) {
-    calculate();
-  }
-
-  BlockSet &getBlocks() { return Blocks; }
-
-private:
-  MachineBasicBlock *Entry;
-  const BlockSet &Enterers;
-
-  BlockSet Blocks;
-
-  void calculate() {
-    // Going backwards from the loop entry, if we ignore the blocks entering
-    // from outside, we will traverse all the blocks in the loop.
-    BlockVector WorkList;
-    BlockSet AddedToWorkList;
-    Blocks.insert(Entry);
-    for (auto *Pred : Entry->predecessors()) {
-      if (!Enterers.count(Pred)) {
-        WorkList.push_back(Pred);
-        AddedToWorkList.insert(Pred);
-      }
-    }
-
-    while (!WorkList.empty()) {
-      auto *MBB = WorkList.pop_back_val();
-      assert(!Enterers.count(MBB));
-      if (Blocks.insert(MBB).second) {
-        for (auto *Pred : MBB->predecessors()) {
-          if (!AddedToWorkList.count(Pred)) {
-            WorkList.push_back(Pred);
-            AddedToWorkList.insert(Pred);
-          }
-        }
-      }
-    }
-  }
-};
-
-class WebAssemblyFixIrreducibleControlFlow final : public MachineFunctionPass {
-  StringRef getPassName() const override {
-    return "WebAssembly Fix Irreducible Control Flow";
-  }
-
-  bool runOnMachineFunction(MachineFunction &MF) override;
-
-  bool processRegion(MachineBasicBlock *Entry, BlockSet &Blocks,
-                     MachineFunction &MF);
-
-  void makeSingleEntryLoop(BlockSet &Entries, BlockSet &Blocks,
-                           MachineFunction &MF, const ReachabilityGraph &Graph);
-
-public:
-  static char ID; // Pass identification, replacement for typeid
-  WebAssemblyFixIrreducibleControlFlow() : MachineFunctionPass(ID) {}
-};
-
-bool WebAssemblyFixIrreducibleControlFlow::processRegion(
-    MachineBasicBlock *Entry, BlockSet &Blocks, MachineFunction &MF) {
-  bool Changed = false;
-
-  // Remove irreducibility before processing child loops, which may take
-  // multiple iterations.
-  while (true) {
-    ReachabilityGraph Graph(Entry, Blocks);
-
-    bool FoundIrreducibility = false;
-
-    for (auto *LoopEntry : Graph.getLoopEntries()) {
-      // Find mutual entries - all entries which can reach this one, and
-      // are reached by it (that always includes LoopEntry itself). All mutual
-      // entries must be in the same loop, so if we have more than one, then we
-      // have irreducible control flow.
-      //
-      // Note that irreducibility may involve inner loops, e.g. imagine A
-      // starts one loop, and it has B inside it which starts an inner loop.
-      // If we add a branch from all the way on the outside to B, then in a
-      // sense B is no longer an "inner" loop, semantically speaking. We will
-      // fix that irreducibility by adding a block that dispatches to either
-      // either A or B, so B will no longer be an inner loop in our output.
-      // (A fancier approach might try to keep it as such.)
-      //
-      // Note that we still need to recurse into inner loops later, to handle
-      // the case where the irreducibility is entirely nested - we would not
-      // be able to identify that at this point, since the enclosing loop is
-      // a group of blocks all of whom can reach each other. (We'll see the
-      // irreducibility after removing branches to the top of that enclosing
-      // loop.)
-      BlockSet MutualLoopEntries;
-      MutualLoopEntries.insert(LoopEntry);
-      for (auto *OtherLoopEntry : Graph.getLoopEntries()) {
-        if (OtherLoopEntry != LoopEntry &&
-            Graph.canReach(LoopEntry, OtherLoopEntry) &&
-            Graph.canReach(OtherLoopEntry, LoopEntry)) {
-          MutualLoopEntries.insert(OtherLoopEntry);
-        }
-      }
-
-      if (MutualLoopEntries.size() > 1) {
-        makeSingleEntryLoop(MutualLoopEntries, Blocks, MF, Graph);
-        FoundIrreducibility = true;
-        Changed = true;
-        break;
-      }
-    }
-    // Only go on to actually process the inner loops when we are done
-    // removing irreducible control flow and changing the graph. Modifying
-    // the graph as we go is possible, and that might let us avoid looking at
-    // the already-fixed loops again if we are careful, but all that is
-    // complex and bug-prone. Since irreducible loops are rare, just starting
-    // another iteration is best.
-    if (FoundIrreducibility) {
-      continue;
-    }
-
-    for (auto *LoopEntry : Graph.getLoopEntries()) {
-      LoopBlocks InnerBlocks(LoopEntry, Graph.getLoopEnterers(LoopEntry));
-      // Each of these calls to processRegion may change the graph, but are
-      // guaranteed not to interfere with each other. The only changes we make
-      // to the graph are to add blocks on the way to a loop entry. As the
-      // loops are disjoint, that means we may only alter branches that exit
-      // another loop, which are ignored when recursing into that other loop
-      // anyhow.
-      if (processRegion(LoopEntry, InnerBlocks.getBlocks(), MF)) {
-        Changed = true;
-      }
-    }
-
-    return Changed;
-  }
-}
-
-// Given a set of entries to a single loop, create a single entry for that
-// loop by creating a dispatch block for them, routing control flow using
-// a helper variable. Also updates Blocks with any new blocks created, so
-// that we properly track all the blocks in the region. But this does not update
-// ReachabilityGraph; this will be updated in the caller of this function as
-// needed.
-void WebAssemblyFixIrreducibleControlFlow::makeSingleEntryLoop(
-    BlockSet &Entries, BlockSet &Blocks, MachineFunction &MF,
-    const ReachabilityGraph &Graph) {
-  assert(Entries.size() >= 2);
-
-  // Sort the entries to ensure a deterministic build.
-  BlockVector SortedEntries(Entries.begin(), Entries.end());
-  llvm::sort(SortedEntries,
-             [&](const MachineBasicBlock *A, const MachineBasicBlock *B) {
-               auto ANum = A->getNumber();
-               auto BNum = B->getNumber();
-               return ANum < BNum;
-             });
-
-#ifndef NDEBUG
-  for (auto Block : SortedEntries)
-    assert(Block->getNumber() != -1);
-  if (SortedEntries.size() > 1) {
-    for (auto I = SortedEntries.begin(), E = SortedEntries.end() - 1; I != E;
-         ++I) {
-      auto ANum = (*I)->getNumber();
-      auto BNum = (*(std::next(I)))->getNumber();
-      assert(ANum != BNum);
-    }
-  }
-#endif
-
-  // Create a dispatch block which will contain a jump table to the entries.
-  MachineBasicBlock *Dispatch = MF.CreateMachineBasicBlock();
-  MF.insert(MF.end(), Dispatch);
-  Blocks.insert(Dispatch);
-
-  // Add the jump table.
-  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
-  MachineInstrBuilder MIB =
-      BuildMI(Dispatch, DebugLoc(), TII.get(WebAssembly::BR_TABLE_I32));
-
-  // Add the register which will be used to tell the jump table which block to
-  // jump to.
-  MachineRegisterInfo &MRI = MF.getRegInfo();
-  unsigned Reg = MRI.createVirtualRegister(&WebAssembly::I32RegClass);
-  MIB.addReg(Reg);
-
-  // Compute the indices in the superheader, one for each bad block, and
-  // add them as successors.
-  DenseMap<MachineBasicBlock *, unsigned> Indices;
-  for (auto *Entry : SortedEntries) {
-    auto Pair = Indices.insert(std::make_pair(Entry, 0));
-    assert(Pair.second);
-
-    unsigned Index = MIB.getInstr()->getNumExplicitOperands() - 1;
-    Pair.first->second = Index;
-
-    MIB.addMBB(Entry);
-    Dispatch->addSuccessor(Entry);
-  }
-
-  // Rewrite the problematic successors for every block that wants to reach
-  // the bad blocks. For simplicity, we just introduce a new block for every
-  // edge we need to rewrite. (Fancier things are possible.)
-
-  BlockVector AllPreds;
-  for (auto *Entry : SortedEntries) {
-    for (auto *Pred : Entry->predecessors()) {
-      if (Pred != Dispatch) {
-        AllPreds.push_back(Pred);
-      }
-    }
-  }
-
-  // This set stores predecessors within this loop.
-  DenseSet<MachineBasicBlock *> InLoop;
-  for (auto *Pred : AllPreds) {
-    for (auto *Entry : Pred->successors()) {
-      if (!Entries.count(Entry))
-        continue;
-      if (Graph.canReach(Entry, Pred)) {
-        InLoop.insert(Pred);
-        break;
-      }
-    }
-  }
-
-  // Record if each entry has a layout predecessor. This map stores
-  // <<Predecessor is within the loop?, loop entry>, layout predecessor>
-  std::map<std::pair<bool, MachineBasicBlock *>, MachineBasicBlock *>
-      EntryToLayoutPred;
-  for (auto *Pred : AllPreds)
-    for (auto *Entry : Pred->successors())
-      if (Entries.count(Entry) && Pred->isLayoutSuccessor(Entry))
-        EntryToLayoutPred[std::make_pair(InLoop.count(Pred), Entry)] = Pred;
-
-  // We need to create at most two routing blocks per entry: one for
-  // predecessors outside the loop and one for predecessors inside the loop.
-  // This map stores
-  // <<Predecessor is within the loop?, loop entry>, routing block>
-  std::map<std::pair<bool, MachineBasicBlock *>, MachineBasicBlock *> Map;
-  for (auto *Pred : AllPreds) {
-    bool PredInLoop = InLoop.count(Pred);
-    for (auto *Entry : Pred->successors()) {
-      if (!Entries.count(Entry) ||
-          Map.count(std::make_pair(InLoop.count(Pred), Entry)))
-        continue;
-      // If there exists a layout predecessor of this entry and this predecessor
-      // is not that, we rather create a routing block after that layout
-      // predecessor to save a branch.
-      if (EntryToLayoutPred.count(std::make_pair(PredInLoop, Entry)) &&
-          EntryToLayoutPred[std::make_pair(PredInLoop, Entry)] != Pred)
-        continue;
-
-      // This is a successor we need to rewrite.
-      MachineBasicBlock *Routing = MF.CreateMachineBasicBlock();
-      MF.insert(Pred->isLayoutSuccessor(Entry)
-                    ? MachineFunction::iterator(Entry)
-                    : MF.end(),
-                Routing);
-      Blocks.insert(Routing);
-
-      // Set the jump table's register of the index of the block we wish to
-      // jump to, and jump to the jump table.
-      BuildMI(Routing, DebugLoc(), TII.get(WebAssembly::CONST_I32), Reg)
-          .addImm(Indices[Entry]);
-      BuildMI(Routing, DebugLoc(), TII.get(WebAssembly::BR)).addMBB(Dispatch);
-      Routing->addSuccessor(Dispatch);
-      Map[std::make_pair(PredInLoop, Entry)] = Routing;
-    }
-  }
-
-  for (auto *Pred : AllPreds) {
-    bool PredInLoop = InLoop.count(Pred);
-    // Remap the terminator operands and the successor list.
-    for (MachineInstr &Term : Pred->terminators())
-      for (auto &Op : Term.explicit_uses())
-        if (Op.isMBB() && Indices.count(Op.getMBB()))
-          Op.setMBB(Map[std::make_pair(PredInLoop, Op.getMBB())]);
-
-    for (auto *Succ : Pred->successors()) {
-      if (!Entries.count(Succ))
-        continue;
-      auto *Routing = Map[std::make_pair(PredInLoop, Succ)];
-      Pred->replaceSuccessor(Succ, Routing);
-    }
-  }
-
-  // Create a fake default label, because br_table requires one.
-  MIB.addMBB(MIB.getInstr()
-                 ->getOperand(MIB.getInstr()->getNumExplicitOperands() - 1)
-                 .getMBB());
-}
-
-} // end anonymous namespace
-
-char WebAssemblyFixIrreducibleControlFlow::ID = 0;
-INITIALIZE_PASS(WebAssemblyFixIrreducibleControlFlow, DEBUG_TYPE,
-                "Removes irreducible control flow", false, false)
-
-FunctionPass *llvm::createWebAssemblyFixIrreducibleControlFlow() {
-  return new WebAssemblyFixIrreducibleControlFlow();
-}
-
-bool WebAssemblyFixIrreducibleControlFlow::runOnMachineFunction(
-    MachineFunction &MF) {
-  LLVM_DEBUG(dbgs() << "********** Fixing Irreducible Control Flow **********\n"
-                       "********** Function: "
-                    << MF.getName() << '\n');
-
-  // Start the recursive process on the entire function body.
-  BlockSet AllBlocks;
-  for (auto &MBB : MF) {
-    AllBlocks.insert(&MBB);
-  }
-
-  if (LLVM_UNLIKELY(processRegion(&*MF.begin(), AllBlocks, MF))) {
-    // We rewrote part of the function; recompute relevant things.
-    MF.getRegInfo().invalidateLiveness();
-    MF.RenumberBlocks();
-    return true;
-  }
-
-  return false;
-}