[WebAssembly] Fix block marker placing after fixUnwindMismatches

[aheejin]

Summary

This fixes a few things that are connected. It is very hard to provide
an independent test case for each of those fixes, because they are
interconnected and sometimes one masks another. The provided test case
triggers some of those bugs below but not all.

---

1. Background:

placeBlockMarker takes a BB, and if the BB is a destination of some
branch, it places end_block marker there, and computes the nearest
common dominator of all predecessors (what we call 'header') and places
a block marker there.

When we first place markers, we traverse BBs from top to bottom. For
example, when there are 5 BBs A, B, C, D, and E and B, D, and E are
branch destinations, if mark the BB given to placeBlockMarker with *
and draw a rectangle representing the border of block and end_block
markers, the process is going to look like

                      -------
          -----       |-----|
---       |---|       ||---||
|A|       ||A||       |||A|||
---  -->  |---|  -->  ||---||
*B        | B |       || B ||
 C        | C |       || C ||
 D        -----       |-----|
 E         *D         |  D  |
            E         -------
                        *E

which means when we first place markers, we go from inner to outer
scopes. So when we place a block marker, if the header already
contains other block or try marker, it has to belong to an inner
scope, so the existing block/try markers should go _after_ the new
marker. This was the assumption we had.

But after placing all markers we run fixUnwindMismatches function.
There we do some control flow transformation and create some branches,
and we call placeBlockMarker again to place block/end_block
markers for those newly created branches. We can't assume that we are
traversing branch destination BBs from top to bottom now because we are
basically inserting some new markers in the middle of existing markers.

Fix:
In placeBlockMarker, we don't have the assumption that the BB given is
in the order of top to bottom, and when placing block markers,
calculates whether existing block or try markers are inner or
outer scopes with respect to the current scope.

---

2. Background:

In fixUnwindMismatches, when there is a call whose correct unwind
destination mismatches the current destination after initially placing
try markers, we wrap that with a new nested try/catch/end and
jump to the correct handler within the new catch. The correct handler
code is split as a separate BB from its original EH pad so it can be
branched to. Here's an example:

• Before

mbb:
  call @foo       <- Unwind destination mismatch!
wrong-ehpad:
  catch
  ...
cont:
  end_try
  ...
correct-ehpad:
  catch
  [handler code]

• After

mbb:
  try                (new)
  call @foo
nested-ehpad:        (new)
  catch              (new)
  local.set n / drop (new)
  br %handleri       (new)
nested-end:          (new)
  end_try            (new)
wrong-ehpad:
  catch
  ...
cont:
  end_try
  ...
correct-ehpad:
  catch
  local.set n / drop (new)
handler:             (new)
  end_try
  [handler code]

Note that after this transformation, it is possible there are no calls
to actually unwind to correct-ehpad here. call @foo now
branches to handler, and there can be no other calls to unwind to
correct-ehpad. In this case correct-ehpad does not have any
predecessors anymore.

This can cause a bug in placeBlockMarker, because we may need to place
end_block marker in handler, and placeBlockMarker computes the
nearest common dominator of all predecessors. If one of handler's
predecessor (here correct-ehpad) does not have any predecessors, i.e.,
no way of reaching it, we cannot correctly compute the common dominator
of predecessors of handler, and end up placing no block/end
markers. This bug actually sometimes masks the bug 1.

Fix:
When we have an EH pad that does not have any predecessors after this
transformation, deletes all its successors, so that its successors don't
have any dangling predecessors.

---

3. Background:

Actually the handler BB in the example shown in bug 2 doesn't need
end_block marker, despite it being a new branch destination, because
it already has end_try marker which can serve the same purpose. I just
put that example there for an illustration purpose. There is a case we
actually need to place end_block marker: when the branch dest is the
appendix BB. The appendix BB is created when there is a call that is
supposed to unwind to the caller ends up unwinding to a wrong EH pad. In
this case we also wrap the call with a nested try/catch/end,
create an 'appendix' BB at the very end of the function, and branch to
that BB, where we rethrow the exception to the caller.

Fix:
When we don't actually need to place block markers, we don't.

---

4. In case we fall through to the continuation BB after the catch block,

after extracting handler code in fixUnwindMismatches (refer to bug 2
for an example), we now have to add a branch to it to bypass the
handler.

• Before

try
  ...
  (falls through to 'cont')
catch
  handler body
end
              <-- cont

• After

try
  ...
  br %cont    (new)
catch
end
handler body
              <-- cont

The problem is, we haven't been placing a new end_block marker in the
cont BB in this case. We should, and this fixes it. But it is hard to
provide a test case that triggers this bug, because the current
compilation pipeline from .ll to .s does not generate this kind of code;
we always have a br after invoke. But code without br is still
valid, and we can have that kind of code if we have some pipeline
changes or optimizations later. Even mir test cases cannot trigger this
part for now, because we don't encode auxiliary EH-related data
structures (such as [[ https://github.com/llvm/llvm-project/blob/19f5da9c1d698653f942b504544a73b85b1e703c/llvm/include/llvm/CodeGen/WasmEHFuncInfo.h#L29-L54 | WasmEHFuncInfo ]]) in mir now. Those functionalities
can be added later, but I don't think we should block this fix on that.

[aheejin]

llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

292

Fix for bug 1

1090

Fix for bug 4

1203

Fix for bug 2

1241

Fix for bug 3

[aheejin]

llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

879

This was preexisting but just hoisted, because in bugfix 4 we use it earlier.

[aheejin]

llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

1241

Before we add all branch dests in BrDestToTryRanges to BrDests so that block/end markers are placed for them, but actually we don't need the marker for non-appendix BB, because there is already an existing try/end pair that can serve the same purpose. Please refer to the CL description for bugfix 3.

[dschuff]

Wow, did our one external partner test case trigger all of these?

[aheejin]

No it's complicated... Adobe's case triggered bug 1 (placeBlockMarker bug). That can be solvable by either applying bugfix 1 or applying 2 and 3 together. Bugfix 3 means not placing block/end_block in that case bc it is not strictly necessary, and bugfix 1 means we place markers (even if it's unnecessary) that but correctly. But bugfix 3 requires bugfix 2 to work, because due to bug 2 placeBlockMarker does not find the 'header' in placeBlockMarker and just returns. The reason I put all 1~3 here is, even though the Adobe case can be fixed by 2 and 3, 1 is a good necessary caution too (actually it does the same check when it places end_block marker. It did not do that check when it placed block.)

Bugfix 4 is separate and is not triggered by the Adobe case, but I couldn't come up with a test case that triggers this because of the reason I stated in the CL description (it is valid code but is not generated by current wasm backend pipeline). The reason I included bugfix 4 here is 1. when I was fixing bug 3, which is we unnecessary place block/end_block marker sometimes, I accidentally found bug 4, which is the opposite - it does not place block/end_block when necessary, and 2. I can't come up with a separate test case for that anyway.

Our small test case here is not the same with Adobe case because it accidentally succeeds in the current code base, because bug 2 masks bug ... In the current codebase it tries to unnecessarily place block markers, but due to bug 2 it cannot find the header and doesn't end up triggering bug 1. but I couldn't come up with the test that has exactly the same properties with the Adobe one.

llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

if (MI.getOpcode() == WebAssembly::LOOP) {
       if (MBB.getNumber() > LoopBottom->getNumber())
         AfterSet.insert(&MI);
 #ifndef NDEBUG
       else
         BeforeSet.insert(&MI);
 #endif
     }
 
-    // All previously inserted BLOCK/TRY markers should be after the BLOCK
-    // because they are all nested blocks.
+    // If there is a previously placed BLOCK/TRY marker and its corresponding
+    // END marker is before the current BLOCK's END marker, that should be
+    // placed after this BLOCK. Otherwise it should be placed before this BLOCK
+    // marker.
     if (MI.getOpcode() == WebAssembly::BLOCK ||
-        MI.getOpcode() == WebAssembly::TRY)
+        MI.getOpcode() == WebAssembly::TRY) {
+      if (BeginToEnd[&MI]->getParent()->getNumber() <= MBB.getNumber())
         AfterSet.insert(&MI);
+#ifndef NDEBUG
+      else
+        BeforeSet.insert(&MI);
+#endif
+    }
 
 #ifndef NDEBUG
     // All END_(BLOCK|LOOP|TRY) markers should be before the BLOCK.
     if (MI.getOpcode() == WebAssembly::END_BLOCK ||
         MI.getOpcode() == WebAssembly::END_LOOP ||
         MI.getOpcode() == WebAssembly::END_TRY)
       BeforeSet.insert(&MI);
 #endif
bool WebAssemblyCFGStackify::fixUnwindMismatches(MachineFunction &MF) {
   using TryRange = std::pair<MachineInstr *, MachineInstr *>;
   // In original CFG, <unwind destination BB, a vector of try ranges>
   DenseMap<MachineBasicBlock *, SmallVector<TryRange, 4>> UnwindDestToTryRanges;
   // In new CFG, <destination to branch to, a vector of try ranges>
   DenseMap<MachineBasicBlock *, SmallVector<TryRange, 4>> BrDestToTryRanges;
   // In new CFG, <destination to branch to, register containing exnref>
   DenseMap<MachineBasicBlock *, unsigned> BrDestToExnReg;
 
+  // Destinations for branches that will be newly added, for which a new
+  // BLOCK/END_BLOCK markers are necessary.
+  SmallVector<MachineBasicBlock *, 8> BrDests;
+
   // Gather possibly throwing calls (i.e., previously invokes) whose current
   // unwind destination is not the same as the original CFG.
   for (auto &MBB : reverse(MF)) {
     bool SeenThrowableInstInBB = false;
     for (auto &MI : reverse(MBB)) {
       if (MI.getOpcode() == WebAssembly::TRY)
         EHPadStack.pop_back();
       else if (MI.getOpcode() == WebAssembly::CATCH)
for (auto &P : UnwindDestToTryRanges) {
     MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
     SmallVector<MachineOperand, 4> Cond;
     bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond);
     if (Analyzable && !TBB && !FBB) {
       DebugLoc DL = EHPadLayoutPred->empty()
                         ? DebugLoc()
                         : EHPadLayoutPred->rbegin()->getDebugLoc();
       BuildMI(EHPadLayoutPred, DL, TII.get(WebAssembly::BR)).addMBB(Cont);
+      BrDests.push_back(Cont);
     }
   }
 
   // For possibly throwing calls whose unwind destinations are currently
   // incorrect because of CFG linearization, we wrap them with a nested
   // try/catch/end_try, and within the new catch block, we branch to the correct
   // handler.
   // - Before
for (auto Range : TryRanges) {
       // new nested continuation BB.
       NestedCont->splice(NestedCont->end(), MBB,
                          std::next(RangeEnd->getIterator()), MBB->end());
       unstackifyVRegsUsedInSplitBB(*MBB, *NestedCont, MFI, MRI);
       registerTryScope(NestedTry, NestedEndTry, NestedEHPad);
 
       // Fix predecessor-successor relationship.
       NestedCont->transferSuccessors(MBB);
-      if (EHPad)
+      if (EHPad) {
         NestedCont->removeSuccessor(EHPad);
+        // If EHPad does not have any predecessors left after removing
+        // NextedCont predecessor, remove its successor too, because this EHPad
+        // is not reachable from the entry BB anyway. We can't remove EHPad BB
+        // itself because it can contain 'catch' or 'end', which are necessary
+        // for keeping try-catch-end structure.
+        if (EHPad->pred_empty())
+          EHPad->removeSuccessor(BrDest);
+      }
       MBB->addSuccessor(NestedEHPad);
       MBB->addSuccessor(NestedCont);
       NestedEHPad->addSuccessor(BrDest);
     }
   }
 
   // Renumber BBs and recalculate ScopeTop info because new BBs might have been
   // created and inserted above.
for (auto &MI : reverse(MBB)) {
         break;
       }
     }
   }
 
   // Recompute the dominator tree.
   getAnalysis<MachineDominatorTree>().runOnMachineFunction(MF);
 
-  // Place block markers for newly added branches.
-  SmallVector <MachineBasicBlock *, 8> BrDests;
-  for (auto &P : BrDestToTryRanges)
-    BrDests.push_back(P.first);
+  // Place block markers for newly added branches, if necessary.
+
+  // If we've created an appendix BB and a branch to it, place a block/end_block
+  // marker for that. For some new branches, those branch destination BBs start
+  // with a hoisted end_try marker, so we don't need a new marker there.
+  if (AppendixBB)
+    BrDests.push_back(AppendixBB);
+
   llvm::sort(BrDests,
              [&](const MachineBasicBlock *A, const MachineBasicBlock *B) {
                auto ANum = A->getNumber();
                auto BNum = B->getNumber();
                return ANum < BNum;
              });
   for (auto *Dest : BrDests)
     placeBlockMarker(*Dest);

llvm/test/CodeGen/WebAssembly/cfg-stackify-eh.ll

 
 terminate7:                                       ; preds = %ehcleanup
   %10 = cleanuppad within %9 []
   %11 = call i8* @llvm.wasm.get.exception(token %10)
   call void @__clang_call_terminate(i8* %11) #7 [ "funclet"(token %10) ]
   unreachable
 }
 
+; We don't need to call placeBlockMarker after fixUnwindMismatches unless the
+; destination is the appendix BB at the very end. This should not crash.
+define void @test16(i32* %p, i32 %a, i32 %b) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+entry:
+  br label %loop
+
+loop:
+  invoke void @foo()
+          to label %bb0 unwind label %catch.dispatch0
+
+bb0:
+  %cmp = icmp ne i32 %a, %b
+  br i1 %cmp, label %bb1, label %last
+
+bb1:                                              ; preds = %bb0
+  invoke void @bar()
+          to label %try.cont unwind label %catch.dispatch1
+
+catch.dispatch0:                                  ; preds = %loop
+  %0 = catchswitch within none [label %catch.start0] unwind to caller
+
+catch.start0:                                     ; preds = %catch.dispatch0
+  %1 = catchpad within %0 [i8* null]
+  %2 = call i8* @llvm.wasm.get.exception(token %1)
+  %3 = call i32 @llvm.wasm.get.ehselector(token %1)
+  catchret from %1 to label %try.cont
+
+catch.dispatch1:                                  ; preds = %bb1
+  %4 = catchswitch within none [label %catch.start1] unwind to caller
+
+catch.start1:                                     ; preds = %catch.dispatch1
+  %5 = catchpad within %4 [i8* null]
+  %6 = call i8* @llvm.wasm.get.exception(token %5)
+  %7 = call i32 @llvm.wasm.get.ehselector(token %5)
+  catchret from %5 to label %try.cont
+
+try.cont:                                         ; preds = %catch.start, %loop
+  br label %loop
+
+last:
+  ret void
+}
+
 ; Check if the unwind destination mismatch stats are correct
-; NOSORT-STAT: 15 wasm-cfg-stackify    - Number of EH pad unwind mismatches found
+; NOSORT-STAT: 16 wasm-cfg-stackify    - Number of EH pad unwind mismatches found
 
 declare void @foo()
 declare void @bar()
 declare i32 @baz()
 declare i32 @qux(i32)
 declare void @quux(i32)
 declare void @fun(i32)
 ; Function Attrs: nounwind