[WebAssembly] Fix try placement in fixing unwind mismatches

[aheejin]

Summary

In CFGStackify, fixUnwindMismatches function fixes unwind destination
mismatches created by try marker placement. For example,

try
  ...
  call @qux  ;; This should throw to the caller!
catch
  ...
end

When call @qux is supposed to throw to the caller, it is possible that
it is wrapped inside a catch so in case it throws it ends up unwinding
there incorrectly. (Also it is possible call @qux is supposed to
unwind to another catch within the same function.)

To fix this, we wrap this inner call @qux with a nested
try-catch-end sequence, and within the nested catch body, branch
to the right destination:

block $l0
  try
    ...
    try                 ;; new nested try
      call @qux
    catch               ;; new nested catch
      local.set n       ;; store exnref to a local
      br $l0
    end
  catch
    ...
  end
end
local.get n             ;; retrieve exnref back
rethrow                 ;; rethrow to the caller

The previous algorithm placed the nested try right before the call.
But it is possible that there are stackified instructions before the
call from which the call takes arguments.

try
  ...
  i32.const 5
  call @qux  ;; This should throw to the caller!
catch
  ...
end

In this case we have to place try before those stackified
instructions.

block $l0
  try
    ...
    try                 ;; this should go *before* 'i32.const 5'
      i32.const 5
      call @qux
    catch
      local.set n
      br $l0
    end
  catch
    ...
  end
end
local.get n
rethrow

We correctly handle this in the first normal try placement phase
(placeTryMarker function), but failed to handle this in this
fixUnwindMismatches.

[aheejin]

rebase

[aheejin]

• Delete debug print

llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

for (auto &P : BrDestToTryRanges) {
     MachineBasicBlock *BrDest = P.first;
     auto &TryRanges = P.second;
     unsigned ExnReg = BrDestToExnReg[BrDest];
 
     for (auto Range : TryRanges) {
       MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr;
       std::tie(RangeBegin, RangeEnd) = Range;
       auto *MBB = RangeBegin->getParent();
+      // Store the first function call from this range, because RangeBegin can
+      // be moved to point EH_LABEL before the call
+      MachineInstr *RangeBeginCall = RangeBegin;
 
       // Include possible EH_LABELs in the range
       if (RangeBegin->getIterator() != MBB->begin() &&
           std::prev(RangeBegin->getIterator())->isEHLabel())
         RangeBegin = &*std::prev(RangeBegin->getIterator());
       if (std::next(RangeEnd->getIterator()) != MBB->end() &&
           std::next(RangeEnd->getIterator())->isEHLabel())
         RangeEnd = &*std::next(RangeEnd->getIterator());
 
       MachineBasicBlock *EHPad = nullptr;
       for (auto *Succ : MBB->successors()) {
         if (Succ->isEHPad()) {
           EHPad = Succ;
           break;
         }
       }
 
+      // Local expression tree before the first call of this range should go
+      // after the nested TRY.
+      SmallPtrSet<const MachineInstr *, 4> AfterSet;
+      AfterSet.insert(RangeBegin);
+      AfterSet.insert(RangeBeginCall);
+      for (auto I = MachineBasicBlock::iterator(RangeBeginCall),
+                E = MBB->begin();
+           I != E; --I) {
+        if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
+          continue;
+        if (WebAssembly::isChild(*std::prev(I), MFI))
+          AfterSet.insert(&*std::prev(I));
+        else
+          break;
+      }
+
       // Create the nested try instruction.
+      auto InsertPos = getLatestInsertPos(
+          MBB, SmallPtrSet<const MachineInstr *, 4>(), AfterSet);
       MachineInstr *NestedTry =
-          BuildMI(*MBB, *RangeBegin, RangeBegin->getDebugLoc(),
+          BuildMI(*MBB, InsertPos, RangeBegin->getDebugLoc(),
                   TII.get(WebAssembly::TRY))
               .addImm(int64_t(WebAssembly::BlockType::Void));
 
       // Create the nested EH pad and fill instructions in.
       MachineBasicBlock *NestedEHPad = MF.CreateMachineBasicBlock();
       MF.insert(std::next(MBB->getIterator()), NestedEHPad);
       NestedEHPad->setIsEHPad();
       NestedEHPad->setIsEHScopeEntry();

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

catch.start0:                                     ; preds = %catch.dispatch0
   %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
 
 try.cont:                                         ; preds = %catch.start0
   ret void
 }
 
+; Similar situation as @test6. Here 'call @qux''s original unwind destination
+; was the caller, but after control flow linearization, their unwind destination
+; incorrectly becomes another catch within the function. We fix this by wrapping
+; the call with a nested try/catch/end_try and branching to the right
+; destination, from which we rethrow the exception to the caller.
+
+; Because 'call @qux' pops an argument pushed by 'i32.const 5' from stack, the
+; nested 'try' should be placed before `i32.const 5', not between 'i32.const 5'
+; and 'call @qux'.
+
+; NOSORT-LABEL: test7
+; NOSORT:   try
+; NOSORT:     call      foo
+; --- Nested try/catch/end_try starts
+; NOSORT:     try
+; NOSORT-NEXT:  i32.const $push{{[0-9]+}}=, 5
+; NOSORT-NEXT:  call      ${{[0-9]+}}=, qux
+; NOSORT:     catch     $[[REG:[0-9]+]]=
+; NOSORT:       br        1                            # 1: down to label37
+; NOSORT:     end_try
+; --- Nested try/catch/end_try ends
+; NOSORT:     return
+; NOSORT:   catch     $drop=                           # catch19:
+; NOSORT:     return
+; NOSORT:   end_try                                    # label37:
+; NOSORT:   rethrow   $[[REG]]                         # to caller
+
+define i32 @test7() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+bb0:
+  invoke void @foo()
+          to label %bb1 unwind label %catch.dispatch0
+
+bb1:                                              ; preds = %bb0
+  %0 = call i32 @qux(i32 5)
+  ret i32 %0
+
+catch.dispatch0:                                  ; preds = %bb0
+  %1 = catchswitch within none [label %catch.start0] unwind to caller
+
+catch.start0:                                     ; preds = %catch.dispatch0
+  %2 = catchpad within %1 [i8* null]
+  %3 = call i8* @llvm.wasm.get.exception(token %2)
+  %j = call i32 @llvm.wasm.get.ehselector(token %2)
+  catchret from %2 to label %try.cont
+
+try.cont:                                         ; preds = %catch.start0
+  ret i32 0
+}
+
 ; If not for the unwind destination mismatch, the LOOP marker here would have an
 ; i32 signature. But because we add a rethrow instruction at the end of the
 ; appendix block, now the LOOP marker does not have a signature (= has a void
 ; signature). Here the two calls two 'bar' are supposed to throw up to the
 ; caller, but incorrectly unwind to 'catch19' after linearizing the CFG.
 
-; NOSORT-LABEL: test7
+; NOSORT-LABEL: test8
 ; NOSORT: block
 ; NOSORT-NOT: loop      i32
-; NOSORT:   loop                                       # label38:
+; NOSORT:   loop                                       # label40:
 ; NOSORT:     try
 ; NOSORT:       call      foo
 ; --- Nested try/catch/end_try starts
 ; NOSORT:       try
 ; NOSORT:         call      bar
 ; NOSORT:         call      bar
 ; NOSORT:       catch     $[[REG:[0-9]+]]=
-; NOSORT:         br        1                          # 1: down to label39
+; NOSORT:         br        1                          # 1: down to label41
 ; NOSORT:       end_try
 ; --- Nested try/catch/end_try ends
 ; NOSORT:       return    {{.*}}
-; NOSORT:     catch     $drop=                         # catch19:
-; NOSORT:       br        1                            # 1: up to label38
-; NOSORT:     end_try                                  # label39:
+; NOSORT:     catch     $drop=                         # catch21:
+; NOSORT:       br        1                            # 1: up to label40
+; NOSORT:     end_try                                  # label41:
 ; NOSORT:   end_loop
 ; NOSORT: end_block
 ; NOSORT: rethrow   $[[REG]]                           # to caller
 
-define i32 @test7(i32* %p) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+define i32 @test8(i32* %p) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   store volatile i32 0, i32* %p
   br label %loop
 
 loop:                                             ; preds = %try.cont, %entry
   store volatile i32 1, i32* %p
   invoke void @foo()
           to label %bb unwind label %catch.dispatch

 }
 
 ; When we have both kinds of EH pad unwind mismatches:
 ; - A may-throw instruction unwinds to an incorrect EH pad after linearizing the
 ;   CFG, when it is supposed to unwind to another EH pad.
 ; - A may-throw instruction unwinds to an incorrect EH pad after linearizing the
 ;   CFG, when it is supposed to unwind to the caller.
 
-; NOSORT-LABEL: test8
+; NOSORT-LABEL: test9
 ; NOSORT: block
 ; NOSORT:   block
 ; NOSORT:     try
 ; NOSORT:       try
 ; NOSORT:         call      foo
 ; --- Nested try/catch/end_try starts
 ; NOSORT:         try
 ; NOSORT:           call      bar
 ; NOSORT:         catch     $[[REG0:[0-9]+]]=
-; NOSORT:           br        2                        # 2: down to label43
+; NOSORT:           br        2                        # 2: down to label45
 ; NOSORT:         end_try
 ; --- Nested try/catch/end_try ends
-; NOSORT:         br        2                          # 2: down to label42
+; NOSORT:         br        2                          # 2: down to label44
 ; NOSORT:       catch     {{.*}}
 ; NOSORT:         block     i32
-; NOSORT:           br_on_exn   0, {{.*}}              # 0: down to label46
+; NOSORT:           br_on_exn   0, {{.*}}              # 0: down to label48
 ; --- Nested try/catch/end_try starts
 ; NOSORT:           try
-; NOSORT:             rethrow   {{.*}}                 # down to catch24
-; NOSORT:           catch     $[[REG1:[0-9]+]]=        # catch24:
-; NOSORT:             br        5                      # 5: down to label41
+; NOSORT:             rethrow   {{.*}}                 # down to catch26
+; NOSORT:           catch     $[[REG1:[0-9]+]]=        # catch26:
+; NOSORT:             br        5                      # 5: down to label43
 ; NOSORT:           end_try
 ; --- Nested try/catch/end_try ends
-; NOSORT:         end_block                            # label46:
+; NOSORT:         end_block                            # label48:
 ; NOSORT:         call      $drop=, __cxa_begin_catch
 ; --- Nested try/catch/end_try starts
 ; NOSORT:         try
 ; NOSORT:           call      __cxa_end_catch
 ; NOSORT:         catch     $[[REG1]]=
-; NOSORT:           br        4                        # 4: down to label41
+; NOSORT:           br        4                        # 4: down to label43
 ; NOSORT:         end_try
 ; --- Nested try/catch/end_try ends
-; NOSORT:         br        2                          # 2: down to label42
+; NOSORT:         br        2                          # 2: down to label44
 ; NOSORT:       end_try
 ; NOSORT:     catch     $[[REG0]]=
-; NOSORT:     end_try                                  # label43:
+; NOSORT:     end_try                                  # label45:
 ; NOSORT:     call      $drop=, __cxa_begin_catch
 ; NOSORT:     call      __cxa_end_catch
-; NOSORT:   end_block                                  # label42:
+; NOSORT:   end_block                                  # label44:
 ; NOSORT:   return
-; NOSORT: end_block                                    # label41:
+; NOSORT: end_block                                    # label43:
 ; NOSORT: rethrow   $[[REG1]]                          # to caller
-define void @test8() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+define void @test9() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 bb0:
   invoke void @foo()
           to label %bb1 unwind label %catch.dispatch0
 
 bb1:                                              ; preds = %bb0
   invoke void @bar()
           to label %try.cont unwind label %catch.dispatch1
 

 ; NOOPT: block
 ; NOOPT:   try
 ; NOOPT:     call      foo
 ; NOOPT:   catch
 ; NOOPT:   end_try
 ; NOOPT:   call      foo
 ; NOOPT: end_block
 ; NOOPT: return
-define void @test9(i32 %arg) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+define void @test10(i32 %arg) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   %tobool = icmp ne i32 %arg, 0
   br i1 %tobool, label %if.then, label %if.end
 
 catch.dispatch:                                   ; preds = %if.then
   %0 = catchswitch within none [label %catch.start] unwind to caller
 
 catch.start:                                      ; preds = %catch.dispatch

 
 ; Intrinsics like memcpy, memmove, and memset don't throw and are lowered into
 ; calls to external symbols (not global addresses) in instruction selection,
 ; which will be eventually lowered to library function calls.
 ; Because this test runs with -wasm-disable-ehpad-sort, these library calls in
 ; invoke.cont BB fall within try~end_try, but they shouldn't cause crashes or
 ; unwinding destination mismatches in CFGStackify.
 
-; NOSORT-LABEL: test10
+; NOSORT-LABEL: test11
 ; NOSORT: try
 ; NOSORT:   call  foo
 ; NOSORT:   call {{.*}} memcpy
 ; NOSORT:   call {{.*}} memmove
 ; NOSORT:   call {{.*}} memset
 ; NOSORT:   return
 ; NOSORT: catch
 ; NOSORT:   rethrow
 ; NOSORT: end_try
-define void @test10(i8* %a, i8* %b) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+define void @test11(i8* %a, i8* %b) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   %o = alloca %class.Object, align 1
   invoke void @foo()
           to label %invoke.cont unwind label %ehcleanup
 
 invoke.cont:                                      ; preds = %entry
   call void @llvm.memcpy.p0i8.p0i8.i32(i8* %a, i8* %b, i32 100, i1 false)
   call void @llvm.memmove.p0i8.p0i8.i32(i8* %a, i8* %b, i32 100, i1 false)
   call void @llvm.memset.p0i8.i32(i8* %a, i8 0, i32 100, i1 false)
   %call = call %class.Object* @_ZN6ObjectD2Ev(%class.Object* %o) #1
   ret void
 
 ehcleanup:                                        ; preds = %entry
   %0 = cleanuppad within none []
   %call2 = call %class.Object* @_ZN6ObjectD2Ev(%class.Object* %o) #1 [ "funclet"(token %0) ]
   cleanupret from %0 unwind to caller
 }
 
 ; Tests if 'try' marker is placed correctly. In this test, 'try' should be
 ; placed before the call to 'nothrow_i32' and not between the call to
 ; 'nothrow_i32' and 'fun', because the return value of 'nothrow_i32' is
 ; stackified and pushed onto the stack to be consumed by the call to 'fun'.
 
-; CHECK-LABEL: test11
+; CHECK-LABEL: test12
 ; CHECK: try
 ; CHECK: call      $push{{.*}}=, nothrow_i32
 ; CHECK: call      fun, $pop{{.*}}
-define void @test11() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+define void @test12() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   %call = call i32 @nothrow_i32()
   invoke void @fun(i32 %call)
           to label %invoke.cont unwind label %terminate
 
 invoke.cont:                                      ; preds = %entry
   ret void
 
 terminate:                                        ; preds = %entry
   %0 = cleanuppad within none []
   %1 = tail call i8* @llvm.wasm.get.exception(token %0)
   call void @__clang_call_terminate(i8* %1) [ "funclet"(token %0) ]
   unreachable
 }
 
 %class.MyClass = type { i32 }
 
 ; This crashed on debug mode (= when NDEBUG is not defined) when the logic for
 ; computing the innermost region was not correct, in which a loop region
 ; contains an exception region. This should pass CFGSort without crashing.
-define void @test12() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+define void @test13() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   %e = alloca %class.MyClass, align 4
   br label %for.cond
 
 for.cond:                                         ; preds = %for.inc, %entry
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
   %cmp = icmp slt i32 %i.0, 9
   br i1 %cmp, label %for.body, label %for.end

 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
 }
 
 ; Check if the unwind destination mismatch stats are correct
-; NOSORT-STAT: 14 wasm-cfg-stackify    - Number of EH pad unwind mismatches found
+; NOSORT-STAT: 15 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
 declare void @nothrow(i32) #0
 declare i32 @nothrow_i32() #0
 
 ; Function Attrs: nounwind
 declare %class.Object* @_ZN6ObjectD2Ev(%class.Object* returned) #0