1 files changed, 144 insertions, 67 deletions

diff --git a/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp b/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp
index 110316ba57b..6412442176d 100644
--- a/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp
+++ b/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp
@@ -29,6 +29,7 @@
 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
 #include "WebAssemblySubtarget.h"
 #include "llvm/ADT/SCCIterator.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
@@ -152,8 +153,23 @@ POStackEntry::POStackEntry(MachineBasicBlock *MBB, MachineFunction &MF,
       });
 }
 
+/// Return the "bottom" block of a loop. This differs from
+/// MachineLoop::getBottomBlock in that it works even if the loop is
+/// discontiguous.
+static MachineBasicBlock *LoopBottom(const MachineLoop *Loop) {
+  MachineBasicBlock *Bottom = Loop->getHeader();
+  for (MachineBasicBlock *MBB : Loop->blocks())
+    if (MBB->getNumber() > Bottom->getNumber())
+      Bottom = MBB;
+  return Bottom;
+}
+
 /// Sort the blocks in RPO, taking special care to make sure that loops are
 /// contiguous even in the case of split backedges.
+///
+/// TODO: Determine whether RPO is actually worthwhile, or whether we should
+/// move to just a stable-topological-sort-based approach that would preserve
+/// more of the original order.
 static void SortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI) {
   // Note that we do our own RPO rather than using
   // "llvm/ADT/PostOrderIterator.h" because we want control over the order that
@@ -198,40 +214,52 @@ static void SortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI) {
   MF.RenumberBlocks();
 
 #ifndef NDEBUG
-  for (auto &MBB : MF)
-    if (MachineLoop *Loop = MLI.getLoopFor(&MBB)) {
-      // Assert that all containing loops are contiguous.
-      for (MachineLoop *L = Loop; L; L = L->getParentLoop()) {
-        if (&MBB == L->getHeader()) {
-          assert(&MBB == L->getTopBlock());
-        } else {
-          assert(&MBB != L->getTopBlock());
-          assert(L->contains(
-                     MLI.getLoopFor(&*prev(MachineFunction::iterator(&MBB)))) &&
-                 "Loop isn't contiguous");
-        }
-      }
+  SmallSetVector<MachineLoop *, 8> OnStack;
+
+  // Insert a sentinel representing the degenerate loop that starts at the
+  // function entry block and includes the entire function as a "loop" that
+  // executes once.
+  OnStack.insert(nullptr);
+
+  for (auto &MBB : MF) {
+    assert(MBB.getNumber() >= 0 && "Renumbered blocks should be non-negative.");
+
+    MachineLoop *Loop = MLI.getLoopFor(&MBB);
+    if (Loop && &MBB == Loop->getHeader()) {
+      // Loop header. The loop predecessor should be sorted above, and the other
+      // predecessors should be backedges below.
+      for (auto Pred : MBB.predecessors())
+        assert(
+            (Pred->getNumber() < MBB.getNumber() || Loop->contains(Pred)) &&
+            "Loop header predecessors must be loop predecessors or backedges");
+      assert(OnStack.insert(Loop) && "Loops should be declared at most once.");
     } else {
-      // Assert that non-loops have no backedge predecessors.
+      // Not a loop header. All predecessors should be sorted above.
       for (auto Pred : MBB.predecessors())
         assert(Pred->getNumber() < MBB.getNumber() &&
-               "CFG still has multiple-entry loops");
+               "Non-loop-header predecessors should be topologically sorted");
+      assert(OnStack.count(MLI.getLoopFor(&MBB)) &&
+             "Blocks must be nested in their loops");
     }
+    while (OnStack.size() > 1 && &MBB == LoopBottom(OnStack.back()))
+      OnStack.pop_back();
+  }
+  assert(OnStack.pop_back_val() == nullptr &&
+         "The function entry block shouldn't actually be a loop header");
+  assert(OnStack.empty() &&
+         "Control flow stack pushes and pops should be balanced.");
 #endif
 }
 
-static unsigned GetLoopDepth(const MachineLoop *Loop) {
-  return Loop ? Loop->getLoopDepth() : 0;
-}
-
 /// Insert a BLOCK marker for branches to MBB (if needed).
-static void PlaceBlockMarkers(MachineBasicBlock &MBB,
-                              const WebAssemblyInstrInfo &TII,
-                              MachineDominatorTree &MDT,
-                              const MachineLoopInfo &MLI) {
-  // Place the BLOCK for forward non-fallthrough branches. Put it at the nearest
-  // common dominator of all preceding predecesors so that we minimize the time
-  // that it's on the stack, which reduces overall stack height.
+static void PlaceBlockMarker(MachineBasicBlock &MBB, MachineFunction &MF,
+                             SmallVectorImpl<MachineBasicBlock *> &ScopeTops,
+                             const WebAssemblyInstrInfo &TII,
+                             const MachineLoopInfo &MLI,
+                             MachineDominatorTree &MDT) {
+  // First compute the nearest common dominator of all forward non-fallthrough
+  // predecessors so that we minimize the time that the BLOCK is on the stack,
+  // which reduces overall stack height.
   MachineBasicBlock *Header = nullptr;
   bool IsBranchedTo = false;
   int MBBNumber = MBB.getNumber();
@@ -247,67 +275,112 @@ static void PlaceBlockMarkers(MachineBasicBlock &MBB,
   if (!IsBranchedTo)
     return;
 
+  assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors");
+  MachineBasicBlock *LayoutPred = &*prev(MachineFunction::iterator(&MBB));
+
+  // If the nearest common dominator is inside a more deeply nested context,
+  // walk out to the nearest scope which isn't more deeply nested.
+  for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) {
+    if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
+      if (ScopeTop->getNumber() > Header->getNumber()) {
+        // Skip over an intervening scope.
+        I = next(MachineFunction::iterator(ScopeTop));
+      } else {
+        // We found a scope level at an appropriate depth.
+        Header = ScopeTop;
+        break;
+      }
+    }
+  }
+
+  // If there's a loop which ends just before MBB which contains Header, we can
+  // reuse its label instead of inserting a new BLOCK.
+  for (MachineLoop *Loop = MLI.getLoopFor(LayoutPred);
+       Loop && Loop->contains(LayoutPred); Loop = Loop->getParentLoop())
+    if (Loop && LoopBottom(Loop) == LayoutPred && Loop->contains(Header))
+      return;
+
+  // Decide where in Header to put the BLOCK.
   MachineBasicBlock::iterator InsertPos;
   MachineLoop *HeaderLoop = MLI.getLoopFor(Header);
-  unsigned MBBLoopDepth = GetLoopDepth(MLI.getLoopFor(&MBB));
-  unsigned HeaderLoopDepth = GetLoopDepth(HeaderLoop);
-  if (HeaderLoopDepth > MBBLoopDepth) {
-    // The nearest common dominating point is more deeply nested. Insert the
-    // BLOCK just above the LOOP.
-    for (unsigned i = 0; i < HeaderLoopDepth - 1 - MBBLoopDepth; ++i)
-      HeaderLoop = HeaderLoop->getParentLoop();
-    Header = HeaderLoop->getHeader();
+  if (HeaderLoop && MBB.getNumber() > LoopBottom(HeaderLoop)->getNumber()) {
+    // Header is the header of a loop that does not lexically contain MBB, so
+    // the BLOCK needs to be above the LOOP.
     InsertPos = Header->begin();
-    // Don't insert a BLOCK if we can reuse a loop exit label though.
-    if (InsertPos != Header->end() &&
-        InsertPos->getOpcode() == WebAssembly::LOOP &&
-        InsertPos->getOperand(0).getMBB() == &MBB)
-      return;
   } else {
-    // Insert the BLOCK as late in the block as we can, but before any existing
-    // BLOCKs.
+    // Otherwise, insert the BLOCK as late in Header as we can, but before any
+    // existing BLOCKs.
     InsertPos = Header->getFirstTerminator();
     while (InsertPos != Header->begin() &&
-           std::prev(InsertPos)->getOpcode() == WebAssembly::BLOCK)
+           prev(InsertPos)->getOpcode() == WebAssembly::BLOCK)
       --InsertPos;
   }
 
+  // Add the BLOCK.
   BuildMI(*Header, InsertPos, DebugLoc(), TII.get(WebAssembly::BLOCK))
       .addMBB(&MBB);
+
+  // Track the farthest-spanning scope that ends at this point.
+  int Number = MBB.getNumber();
+  if (!ScopeTops[Number] ||
+      ScopeTops[Number]->getNumber() > Header->getNumber())
+    ScopeTops[Number] = Header;
+}
+
+/// Insert a LOOP marker for a loop starting at MBB (if it's a loop header).
+static void PlaceLoopMarker(MachineBasicBlock &MBB, MachineFunction &MF,
+                            SmallVectorImpl<MachineBasicBlock *> &ScopeTops,
+                            const WebAssemblyInstrInfo &TII,
+                            const MachineLoopInfo &MLI) {
+  MachineLoop *Loop = MLI.getLoopFor(&MBB);
+  if (!Loop || Loop->getHeader() != &MBB)
+    return;
+
+  // The operand of a LOOP is the first block after the loop. If the loop is the
+  // bottom of the function, insert a dummy block at the end.
+  MachineBasicBlock *Bottom = LoopBottom(Loop);
+  auto Iter = next(MachineFunction::iterator(Bottom));
+  if (Iter == MF.end()) {
+    MachineBasicBlock *Label = MF.CreateMachineBasicBlock();
+    // Give it a fake predecessor so that AsmPrinter prints its label.
+    Label->addSuccessor(Label);
+    MF.push_back(Label);
+    Iter = next(MachineFunction::iterator(Bottom));
+  }
+  MachineBasicBlock *AfterLoop = &*Iter;
+  BuildMI(MBB, MBB.begin(), DebugLoc(), TII.get(WebAssembly::LOOP))
+      .addMBB(AfterLoop);
+
+  // Emit a special no-op telling the asm printer that we need a label to close
+  // the loop scope, even though the destination is only reachable by
+  // fallthrough.
+  if (!Bottom->back().isBarrier())
+    BuildMI(*Bottom, Bottom->end(), DebugLoc(), TII.get(WebAssembly::LOOP_END));
+
+  assert((!ScopeTops[AfterLoop->getNumber()] ||
+          ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) &&
+         "With RPO we should visit the outer-most loop for a block first.");
+  if (!ScopeTops[AfterLoop->getNumber()])
+    ScopeTops[AfterLoop->getNumber()] = &MBB;
 }
 
 /// Insert LOOP and BLOCK markers at appropriate places.
 static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI,
                          const WebAssemblyInstrInfo &TII,
                          MachineDominatorTree &MDT) {
+  // For each block whose label represents the end of a scope, record the block
+  // which holds the beginning of the scope. This will allow us to quickly skip
+  // over scoped regions when walking blocks. We allocate one more than the
+  // number of blocks in the function to accommodate for the possible fake block
+  // we may insert at the end.
+  SmallVector<MachineBasicBlock *, 8> ScopeTops(MF.getNumBlockIDs() + 1);
+
   for (auto &MBB : MF) {
     // Place the LOOP for MBB if MBB is the header of a loop.
-    if (MachineLoop *Loop = MLI.getLoopFor(&MBB))
-      if (Loop->getHeader() == &MBB) {
-        // The operand of a LOOP is the first block after the loop. If the loop
-        // is the bottom of the function, insert a dummy block at the end.
-        MachineBasicBlock *Bottom = Loop->getBottomBlock();
-        auto Iter = next(MachineFunction::iterator(Bottom));
-        if (Iter == MF.end()) {
-          MachineBasicBlock *Label = MF.CreateMachineBasicBlock();
-          // Give it a fake predecessor so that AsmPrinter prints its label.
-          Label->addSuccessor(Label);
-          MF.push_back(Label);
-          Iter = next(MachineFunction::iterator(Bottom));
-        }
-        BuildMI(MBB, MBB.begin(), DebugLoc(), TII.get(WebAssembly::LOOP))
-            .addMBB(&*Iter);
-
-        // Emit a special no-op telling the asm printer that we need a label
-        // to close the loop scope, even though the destination is only
-        // reachable by fallthrough.
-        if (!Bottom->back().isBarrier())
-          BuildMI(*Bottom, Bottom->end(), DebugLoc(),
-                  TII.get(WebAssembly::LOOP_END));
-      }
+    PlaceLoopMarker(MBB, MF, ScopeTops, TII, MLI);
 
     // Place the BLOCK for MBB if MBB is branched to from above.
-    PlaceBlockMarkers(MBB, TII, MDT, MLI);
+    PlaceBlockMarker(MBB, MF, ScopeTops, TII, MLI, MDT);
   }
 }
 
@@ -365,8 +438,12 @@ bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
         Stack.push_back(std::make_pair(MI.getOperand(0).getMBB(), false));
         break;
       default:
+        // Verify that all referenced blocks are in scope. A reference to a
+        // block with a negative number is invalid, but can happen with inline
+        // asm, so we shouldn't assert on it, but instead let CodeGen properly
+        // fail on it.
         for (const MachineOperand &MO : MI.explicit_operands())
-          if (MO.isMBB())
+          if (MO.isMBB() && MO.getMBB()->getNumber() >= 0)
             assert(IsOnStack(Stack, MO.getMBB()));
         break;
       }