[WebAssembly] Remove loop's bottom label

[sunfish]

Summary

This removes loop's bottom label, per WebAssembly spec changes.

[dschuff]

LGTM. I guess we'll have to update https://github.com/WebAssembly/binaryen/blob/master/src/s2wasm.h#L1102 when it lands too.

[sunfish]

Committed as r283502.

lib/Target/WebAssembly/InstPrinter/WebAssemblyInstPrinter.cpp

void WebAssemblyInstPrinter::printInst(const MCInst *MI, raw_ostream &OS,
 
   if (CommentStream) {
     // Observe any effects on the control flow stack, for use in annotating
     // control flow label references.
     switch (MI->getOpcode()) {
     default:
       break;
     case WebAssembly::LOOP: {
-      // Grab the TopLabel value first so that labels print in numeric order.
-      uint64_t TopLabel = ControlFlowCounter++;
-      ControlFlowStack.push_back(std::make_pair(ControlFlowCounter++, false));
-      printAnnotation(OS, "label" + utostr(TopLabel) + ':');
-      ControlFlowStack.push_back(std::make_pair(TopLabel, true));
+      printAnnotation(OS, "label" + utostr(ControlFlowCounter) + ':');
+      ControlFlowStack.push_back(std::make_pair(ControlFlowCounter++, true));
       break;
     }
     case WebAssembly::BLOCK:
       ControlFlowStack.push_back(std::make_pair(ControlFlowCounter++, false));
       break;
     case WebAssembly::END_LOOP:
       ControlFlowStack.pop_back();
-      printAnnotation(
-          OS, "label" + utostr(ControlFlowStack.pop_back_val().first) + ':');
       break;
     case WebAssembly::END_BLOCK:
       printAnnotation(
           OS, "label" + utostr(ControlFlowStack.pop_back_val().first) + ':');
       break;
     }
 
     // Annotate any control flow label references.

lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

static bool IsChild(const MachineInstr &MI,
   if (!MO.isReg() || MO.isImplicit() || !MO.isDef())
     return false;
   unsigned Reg = MO.getReg();
   return TargetRegisterInfo::isVirtualRegister(Reg) &&
          MFI.isVRegStackified(Reg);
 }
 
 /// Insert a BLOCK marker for branches to MBB (if needed).
-static void PlaceBlockMarker(MachineBasicBlock &MBB, MachineFunction &MF,
-                             SmallVectorImpl<MachineBasicBlock *> &ScopeTops,
-                             const WebAssemblyInstrInfo &TII,
-                             const MachineLoopInfo &MLI,
-                             MachineDominatorTree &MDT,
-                             WebAssemblyFunctionInfo &MFI) {
+static void PlaceBlockMarker(
+    MachineBasicBlock &MBB, MachineFunction &MF,
+    DenseMap<const MachineInstr *, const MachineBasicBlock *> &LoopTops,
   // 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();
   for (MachineBasicBlock *Pred : MBB.predecessors())
     if (Pred->getNumber() < MBBNumber) {
if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
       } 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);
   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, after any END constructs.
     InsertPos = Header->begin();
-    while (InsertPos->getOpcode() != WebAssembly::LOOP)
+    while (InsertPos->getOpcode() == WebAssembly::END_BLOCK ||
+           InsertPos->getOpcode() == WebAssembly::END_LOOP)
       ++InsertPos;
   } else {
     // Otherwise, insert the BLOCK as late in Header as we can, but before the
     // beginning of the local expression tree and any nested BLOCKs.
     InsertPos = Header->getFirstTerminator();
     while (InsertPos != Header->begin() &&
            IsChild(*std::prev(InsertPos), MFI) &&
            std::prev(InsertPos)->getOpcode() != WebAssembly::LOOP &&
            std::prev(InsertPos)->getOpcode() != WebAssembly::END_BLOCK &&
            std::prev(InsertPos)->getOpcode() != WebAssembly::END_LOOP)
       --InsertPos;
   }
 
   // Add the BLOCK.
   BuildMI(*Header, InsertPos, DebugLoc(), TII.get(WebAssembly::BLOCK));
 
   // Mark the end of the block.
   InsertPos = MBB.begin();
   while (InsertPos != MBB.end() &&
-         InsertPos->getOpcode() == WebAssembly::END_LOOP)
+         InsertPos->getOpcode() == WebAssembly::END_LOOP &&
+         LoopTops[&*InsertPos]->getNumber() >= Header->getNumber())
     ++InsertPos;
   BuildMI(MBB, InsertPos, DebugLoc(), TII.get(WebAssembly::END_BLOCK));
 
   // 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;
static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI,
   // For eacn LOOP_END, the corresponding LOOP.
   DenseMap<const MachineInstr *, const MachineBasicBlock *> LoopTops;
 
   for (auto &MBB : MF) {
     // Place the LOOP for MBB if MBB is the header of a loop.
     PlaceLoopMarker(MBB, MF, ScopeTops, LoopTops, TII, MLI);
 
     // Place the BLOCK for MBB if MBB is branched to from above.
-    PlaceBlockMarker(MBB, MF, ScopeTops, TII, MLI, MDT, MFI);
+    PlaceBlockMarker(MBB, MF, ScopeTops, LoopTops, TII, MLI, MDT, MFI);
   }
 
   // Now rewrite references to basic blocks to be depth immediates.
   SmallVector<const MachineBasicBlock *, 8> Stack;
   for (auto &MBB : reverse(MF)) {
     for (auto &MI : reverse(MBB)) {
       switch (MI.getOpcode()) {
       case WebAssembly::BLOCK:
-        assert(ScopeTops[Stack.back()->getNumber()] == &MBB &&
+        assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <= MBB.getNumber() &&
                "Block should be balanced");
         Stack.pop_back();
         break;
       case WebAssembly::LOOP:
         assert(Stack.back() == &MBB && "Loop top should be balanced");
         Stack.pop_back();
-        Stack.pop_back();
         break;
       case WebAssembly::END_BLOCK:
         Stack.push_back(&MBB);
         break;
       case WebAssembly::END_LOOP:
-        Stack.push_back(&MBB);
         Stack.push_back(LoopTops[&MI]);
         break;
       default:
         if (MI.isTerminator()) {
           // Rewrite MBB operands to be depth immediates.
           SmallVector<MachineOperand, 4> Ops(MI.operands());
           while (MI.getNumOperands() > 0)
             MI.RemoveOperand(MI.getNumOperands() - 1);

test/CodeGen/WebAssembly/cfg-stackify.ll

 
 ; Test a case where the BLOCK needs to be placed before the LOOP in the
 ; same basic block.
 
 ; CHECK-LABEL: test5:
 ; CHECK:       .LBB14_1:
 ; CHECK-NEXT:  block{{$}}
 ; CHECK-NEXT:  loop{{$}}
-; CHECK:       br_if 2, {{[^,]+}}{{$}}
+; CHECK:       br_if 1, {{[^,]+}}{{$}}
 ; CHECK:       br_if 0, {{[^,]+}}{{$}}
 ; CHECK-NEXT:  end_loop{{$}}
 ; CHECK:       return{{$}}
 ; CHECK-NEXT:  .LBB14_4:
 ; CHECK:       return{{$}}
 ; OPT-LABEL: test5:
 ; OPT:       .LBB14_1:
 ; OPT-NEXT:  block{{$}}
 ; OPT-NEXT:  loop{{$}}
-; OPT:       br_if 2, {{[^,]+}}{{$}}
+; OPT:       br_if 1, {{[^,]+}}{{$}}
 ; OPT:       br_if 0, {{[^,]+}}{{$}}
 ; OPT-NEXT:  end_loop{{$}}
 ; OPT:       return{{$}}
 ; OPT-NEXT:  .LBB14_4:
 ; OPT:       return{{$}}
 define void @test5(i1 %p, i1 %q) {
 entry:
   br label %header

 ; which has another predecessor.
 
 ; CHECK-LABEL: test6:
 ; CHECK:       .LBB15_1:
 ; CHECK-NEXT:  block{{$}}
 ; CHECK-NEXT:  block{{$}}
 ; CHECK-NEXT:  loop{{$}}
 ; CHECK-NOT:   block
-; CHECK:       br_if 3, {{[^,]+}}{{$}}
-; CHECK-NOT:   block
 ; CHECK:       br_if 2, {{[^,]+}}{{$}}
 ; CHECK-NOT:   block
+; CHECK:       br_if 1, {{[^,]+}}{{$}}
+; CHECK-NOT:   block
 ; CHECK:       br_if 0, {{[^,]+}}{{$}}
 ; CHECK-NEXT:  end_loop{{$}}
 ; CHECK-NOT:   block
 ; CHECK:       return{{$}}
 ; CHECK-NEXT:  .LBB15_5:
 ; CHECK-NEXT:  end_block{{$}}
 ; CHECK-NOT:   block
 ; CHECK:       .LBB15_6:
 ; CHECK-NEXT:  end_block{{$}}
 ; CHECK-NOT:   block
 ; CHECK:       return{{$}}
 ; OPT-LABEL: test6:
 ; OPT:       .LBB15_1:
 ; OPT-NEXT:  block{{$}}
 ; OPT-NEXT:  block{{$}}
 ; OPT-NEXT:  loop{{$}}
 ; OPT-NOT:   block
-; OPT:       br_if 3, {{[^,]+}}{{$}}
-; OPT-NOT:   block
 ; OPT:       br_if 2, {{[^,]+}}{{$}}
 ; OPT-NOT:   block
+; OPT:       br_if 1, {{[^,]+}}{{$}}
+; OPT-NOT:   block
 ; OPT:       br_if 0, {{[^,]+}}{{$}}
 ; OPT-NEXT:  end_loop{{$}}
 ; OPT-NOT:   block
 ; OPT:       return{{$}}
 ; OPT-NEXT:  .LBB15_5:
 ; OPT-NEXT:  end_block{{$}}
 ; OPT-NOT:   block
 ; OPT:       .LBB15_6:

 ; OPT-NEXT:  block
 ; OPT-NEXT:  loop{{$}}
 ; OPT-NOT:   block
 ; OPT:       block{{$}}
 ; OPT-NOT:   block
 ; OPT:       br_if 0, {{[^,]+}}{{$}}
 ; OPT-NOT:   block
 ; OPT:       br_if 1, {{[^,]+}}{{$}}
-; OPT:       br 3{{$}}
+; OPT:       br 2{{$}}
 ; OPT-NEXT:  .LBB16_3:
 ; OPT-NEXT:  end_block
 ; OPT-NOT:   block
 ; OPT:       br_if 0, {{[^,]+}}{{$}}
 ; OPT-NEXT:  end_loop
 ; OPT-NOT:   block
 ; OPT:       unreachable
 ; OPT-NEXT:  .LBB16_5:
switch i8 undef, label %bb1 [
     i8 44, label %bb2
   ]
 }
 
 ; Test an interesting case using nested loops that share a bottom block.
 
 ; CHECK-LABEL: test9:
 ; CHECK:       .LBB18_1:
+; CHECK-NEXT:  block{{$}}
 ; CHECK-NEXT:  loop{{$}}
 ; CHECK-NOT:   block
 ; CHECK:       br_if     1, {{[^,]+}}{{$}}
 ; CHECK-NEXT:  .LBB18_2:
 ; CHECK-NEXT:  loop{{$}}
 ; CHECK-NOT:   block
 ; CHECK:       block{{$}}
 ; CHECK-NOT:   block
 ; CHECK:       br_if     0, {{[^,]+}}{{$}}
 ; CHECK-NOT:   block
-; CHECK:       br_if     3, {{[^,]+}}{{$}}
+; CHECK:       br_if     2, {{[^,]+}}{{$}}
 ; CHECK-NEXT:  br        1{{$}}
 ; CHECK-NEXT:  .LBB18_4:
 ; CHECK-NEXT:  end_block{{$}}
 ; CHECK-NOT:   block
-; CHECK:       br_if     2, {{[^,]+}}{{$}}
+; CHECK:       br_if     1, {{[^,]+}}{{$}}
 ; CHECK-NEXT:  br        0{{$}}
 ; CHECK-NEXT:  .LBB18_5:
 ; CHECK-NOT:   block
+; CHECK:       end_block
+; CHECK-NOT:   block
 ; CHECK:       return{{$}}
 ; OPT-LABEL: test9:
 ; OPT:       .LBB18_1:
+; OPT-NEXT:  block{{$}}
 ; OPT-NEXT:  loop{{$}}
 ; OPT-NOT:   block
 ; OPT:       br_if     1, {{[^,]+}}{{$}}
 ; OPT-NEXT:  .LBB18_2:
 ; OPT-NEXT:  loop{{$}}
 ; OPT-NOT:   block
 ; OPT:       block{{$}}
 ; OPT-NOT:   block
 ; OPT:       br_if     0, {{[^,]+}}{{$}}
 ; OPT-NOT:   block
 ; OPT:       br_if     1, {{[^,]+}}{{$}}
-; OPT-NEXT:  br        3{{$}}
+; OPT-NEXT:  br        2{{$}}
 ; OPT-NEXT:  .LBB18_4:
 ; OPT-NEXT:  end_block{{$}}
 ; OPT-NOT:   block
 ; OPT:       br_if     0, {{[^,]+}}{{$}}
-; OPT-NEXT:  br        2{{$}}
+; OPT-NEXT:  br        1{{$}}
 ; OPT-NEXT:  .LBB18_5:
 ; OPT-NOT:   block
+; OPT:       end_block
+; OPT-NOT:   block
 ; OPT:       return{{$}}
 declare i1 @a()
 define void @test9() {
 entry:
   store volatile i32 0, i32* null
   br label %header
 
 header:

 ; CHECK:       br_if    0, {{[^,]+}}{{$}}
 ; CHECK:       .LBB19_3:
 ; CHECK-NEXT:  block{{$}}
 ; CHECK-NEXT:  loop{{$}}
 ; CHECK-NOT:   block
 ; CHECK:       .LBB19_4:
 ; CHECK-NEXT:  loop{{$}}
 ; CHECK-NOT:   block
-; CHECK:       br_if    5, {{[^,]+}}{{$}}
-; CHECK-NOT:   block
-; CHECK:       br_table  {{[^,]+}}, 0, 1, 5, 2, 4, 0{{$}}
+; CHECK:       br_if    3, {{[^,]+}}{{$}}
+; CHECK:       block{{$}}
+; CHECK:       br_table  {{[^,]+}}, 1, 0, 4, 2, 3, 1{{$}}
 ; CHECK-NEXT:  .LBB19_6:
+; CHECK-NEXT:  end_block{{$}}
 ; CHECK-NEXT:  end_loop{{$}}
 ; CHECK-NEXT:  end_loop{{$}}
 ; CHECK-NEXT:  return{{$}}
 ; CHECK-NEXT:  .LBB19_7:
 ; CHECK-NEXT:  end_block{{$}}
 ; CHECK-NOT:   block
 ; CHECK:       br       0{{$}}
 ; CHECK-NEXT:  .LBB19_8:
 ; OPT-LABEL: test10:
 ; OPT:       .LBB19_1:
 ; OPT-NEXT:  loop{{$}}
 ; OPT-NOT:   block
 ; OPT:       br_if    0, {{[^,]+}}{{$}}
 ; OPT:       .LBB19_3:
 ; OPT-NEXT:  block{{$}}
 ; OPT-NEXT:  loop{{$}}
 ; OPT-NOT:   block
 ; OPT:       .LBB19_4:
 ; OPT-NEXT:  loop{{$}}
 ; OPT-NOT:   block
-; OPT:       br_if    5, {{[^,]+}}{{$}}
-; OPT-NOT:   block
-; OPT:       br_table  {{[^,]+}}, 0, 1, 5, 2, 4, 0{{$}}
+; OPT:       br_if    3, {{[^,]+}}{{$}}
+; OPT:       block
+; OPT:       br_table  {{[^,]+}}, 1, 0, 4, 2, 3, 1{{$}}
 ; OPT-NEXT:  .LBB19_6:
+; OPT-NEXT:  end_block{{$}}
 ; OPT-NEXT:  end_loop{{$}}
 ; OPT-NEXT:  end_loop{{$}}
 ; OPT-NEXT:  return{{$}}
 ; OPT-NEXT:  .LBB19_7:
 ; OPT-NEXT:  end_block{{$}}
 ; OPT-NOT:   block
 ; OPT:       br       0{{$}}
 ; OPT-NEXT:  .LBB19_8:
bb7:
   ret void
 bb8:
   store volatile i32 8, i32* null
   ret void
 }
 
 ; CHECK-LABEL: test12:
 ; CHECK:       .LBB21_1:
+; CHECK-NEXT:  block{{$}}
 ; CHECK-NEXT:  loop{{$}}
 ; CHECK-NOT:   block
 ; CHECK:       block{{$}}
 ; CHECK-NEXT:  block{{$}}
 ; CHECK:       br_if       0, {{[^,]+}}{{$}}
 ; CHECK-NOT:   block
 ; CHECK:       br_if       1, {{[^,]+}}{{$}}
 ; CHECK-NOT:   block
 ; CHECK:       br_if       1, {{[^,]+}}{{$}}
 ; CHECK-NEXT:  br          3{{$}}
 ; CHECK-NEXT:  .LBB21_4:
 ; CHECK-NEXT:  end_block{{$}}
 ; CHECK-NOT:   block
 ; CHECK:       br_if       0, {{[^,]+}}{{$}}
 ; CHECK-NOT:   block
 ; CHECK:       br_if       2, {{[^,]+}}{{$}}
 ; CHECK-NEXT:  .LBB21_6:
 ; CHECK-NEXT:  end_block{{$}}
 ; CHECK-NOT:   block
 ; CHECK:       br          0{{$}}
 ; CHECK-NEXT:  .LBB21_7:
 ; CHECK-NEXT:  end_loop{{$}}
+; CHECK-NEXT:  end_block{{$}}
 ; CHECK-NEXT:  return{{$}}
 ; OPT-LABEL: test12:
 ; OPT:       .LBB21_1:
+; OPT-NEXT:  block{{$}}
 ; OPT-NEXT:  loop{{$}}
 ; OPT-NOT:   block
 ; OPT:       block{{$}}
 ; OPT-NEXT:  block{{$}}
 ; OPT:       br_if       0, {{[^,]+}}{{$}}
 ; OPT-NOT:   block
 ; OPT:       br_if       1, {{[^,]+}}{{$}}
 ; OPT-NOT:   block
 ; OPT:       br_if       1, {{[^,]+}}{{$}}
 ; OPT-NEXT:  br          3{{$}}
 ; OPT-NEXT:  .LBB21_4:
 ; OPT-NEXT:  end_block{{$}}
 ; OPT-NOT:   block
 ; OPT:       br_if       0, {{[^,]+}}{{$}}
 ; OPT-NOT:   block
 ; OPT:       br_if       2, {{[^,]+}}{{$}}
 ; OPT-NEXT:  .LBB21_6:
 ; OPT-NEXT:  end_block{{$}}
 ; OPT:       br          0{{$}}
 ; OPT-NEXT:  .LBB21_7:
 ; OPT-NEXT:  end_loop{{$}}
+; OPT-NEXT:  end_block{{$}}
 ; OPT-NEXT:  return{{$}}
 define void @test12(i8* %arg) {
 bb:
   br label %bb1
 
 bb1:
   %tmp = phi i32 [ 0, %bb ], [ %tmp5, %bb4 ]
   %tmp2 = getelementptr i8, i8* %arg, i32 %tmp

 ; also begins a loop, has the markers placed in the correct order.
 
 ; CHECK-LABEL: test15:
 ; CHECK:        block
 ; CHECK-NEXT:   block
 ; CHECK:        br_if       0, $pop{{.*}}{{$}}
 ; CHECK:        .LBB24_2:
 ; CHECK-NEXT:   block{{$}}
+; CHECK-NEXT:   block{{$}}
 ; CHECK-NEXT:   loop{{$}}
 ; CHECK:        br_if       1, $pop{{.*}}{{$}}
 ; CHECK:        br_if       0, ${{.*}}{{$}}
 ; CHECK-NEXT:   br          2{{$}}
 ; CHECK-NEXT:   .LBB24_4:
 ; CHECK-NEXT:   end_loop{{$}}
 ; CHECK:        .LBB24_5:
 ; CHECK-NEXT:   end_block{{$}}

 ; OPT-NEXT:   br_if       0, $pop{{.*}}{{$}}
 ; OPT-NEXT:   call        test15_callee1@FUNCTION{{$}}
 ; OPT-NEXT:   br          1{{$}}
 ; OPT-NEXT: .LBB24_2:
 ; OPT-NEXT:   end_block
 ; OPT-NEXT:   i32.const
 ; OPT-NEXT: .LBB24_3:
 ; OPT-NEXT:   block
+; OPT-NEXT:   block
 ; OPT-NEXT:   loop
 %0 = type { i8, i32 }
 declare void @test15_callee0()
 declare void @test15_callee1()
 define void @test15() {
 bb:
   %tmp1 = icmp eq i8 1, 0
   br i1 %tmp1, label %bb2, label %bb14