[WebAssembly] Remove more unnecessary brs in CFGStackify

[aheejin]

Summary

After placing markers, we removed some unnecessary branches, but it only
handled the simplest case. This makes more unnecessary branches to be
removed.

[tlively]

llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

662

Should "ehd_try" be "end_try"?

[dschuff]

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

1019

could add a CHECK-LABEL: test18 here

[aheejin]

Address comments

llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

void WebAssemblyCFGStackify::removeUnnecessaryInstrs(MachineFunction &MF) {
 
   // When there is an unconditional branch right before a catch instruction and
   // it branches to the end of end_try marker, we don't need the branch, because
   // it there is no exception, the control flow transfers to that point anyway.
   // bb0:
   //   try
   //     ...
   //     br bb2      <- Not necessary
-  // bb1:
+  // bb1 (ehpad):
   //   catch
   //     ...
-  // bb2:
+  // bb2:            <- Continuation BB
   //   end
+  //
+  // A more involved case: When the BB where 'end' is located is an another EH
+  // pad, the Cont (= continuation) BB is that EH pad's 'end' BB. For example,
+  // bb0:
+  //   try
+  //     try
+  //       ...
+  //       br bb3      <- Not necessary
+  // bb1 (ehpad):
+  //     catch
+  // bb2 (ehpad):
+  //     end
+  //   catch
+  //     ...
+  // bb3:            <- Continuation BB
+  //   end
+  //
+  // When the EH pad at hand is bb1, its matching ehd_try is in bb2. But it is
+  // another EH pad, so bb0's continuation BB becomes bb3. So 'br bb3' in the
+  // code can be deleted. This is why we run 'while' until 'Cont' is not an EH
+  // pad.
   for (auto &MBB : MF) {
     if (!MBB.isEHPad())
       continue;
 
     MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
     SmallVector<MachineOperand, 4> Cond;
     MachineBasicBlock *EHPadLayoutPred = MBB.getPrevNode();
-    MachineBasicBlock *Cont = BeginToEnd[EHPadToTry[&MBB]]->getParent();
+
+    MachineBasicBlock *Cont = &MBB;
+    while (Cont->isEHPad()) {
+      MachineInstr *Try = EHPadToTry[Cont];
+      MachineInstr *EndTry = BeginToEnd[Try];
+      Cont = EndTry->getParent();
+    }
+
     bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond);
     // This condition means either
     // 1. This BB ends with a single unconditional branch whose destinaion is
     //    Cont.
     // 2. This BB ends with a conditional branch followed by an unconditional
     //    branch, and the unconditional branch's destination is Cont.
     // In both cases, we want to remove the last (= unconditional) branch.
     if (Analyzable && ((Cond.empty() && TBB && TBB == Cont) ||

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

 try.cont:                                         ; preds = %catch.start1, %catch.start0, %bb1
   br label %loop
 
 last:                                             ; preds = %bb0
   ret void
 }
 
 ; Tests if CFGStackify's removeUnnecessaryInstrs() removes unnecessary branches
-; correctly.
+; correctly. The code is in the form below, where 'br' is unnecessary because
+; after running the 'try' body the control flow will fall through to bb2 anyway.
+
+; bb0:
+;   try
+;     ...
+;     br bb2      <- Not necessary
+; bb1 (ehpad):
+;   catch
+;     ...
+; bb2:            <- Continuation BB
+;   end
 ; CHECK-LABEL: test17
 define void @test17(i32 %n) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   invoke void @foo()
           to label %for.body unwind label %catch.dispatch
 
 for.body:                                         ; preds = %for.end, %entry
   %i = phi i32 [ %inc, %for.end ], [ 0, %entry ]
catch.start:                                      ; preds = %catch.dispatch
   %4 = call i8* @__cxa_begin_catch(i8* %2) #2 [ "funclet"(token %1) ]
   call void @__cxa_end_catch() [ "funclet"(token %1) ]
   catchret from %1 to label %try.cont
 
 try.cont:                                         ; preds = %catch.start, %for.end
   ret void
 }
 
+; void foo();
+; void test18() {
+;   try {
+;     foo();
+;     try {
+;       foo();
+;     } catch (...) {
+;     }
+;   } catch (...) {
+;   }
+; }
+;
+; This tests whether the 'br' can be removed in code in the form as follows.
+; Here 'br' is inside an inner try, whose 'end' is in another EH pad. In this
+; case, after running an inner try body, the control flow should fall through to
+; bb3, so the 'br' in the code is unnecessary.
+
+; bb0:
+;   try
+;     try
+;       ...
+;       br bb3      <- Not necessary
+; bb1:
+;     catch
+; bb2:
+;     end_try
+;   catch
+;     ...
+; bb3:            <- Continuation BB
+;   end
+;
+define void @test18() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+; CHECK: call foo
+entry:
+  invoke void @foo()
+          to label %invoke.cont unwind label %catch.dispatch3
+
+; CHECK: call foo
+; CHECK-NOT: br
+invoke.cont:                                      ; preds = %entry
+  invoke void @foo()
+          to label %try.cont8 unwind label %catch.dispatch
+
+catch.dispatch:                                   ; preds = %invoke.cont
+  %0 = catchswitch within none [label %catch.start] unwind label %catch.dispatch3
+
+; CHECK: catch
+catch.start:                                      ; preds = %catch.dispatch
+  %1 = catchpad within %0 [i8* null]
+  %2 = call i8* @llvm.wasm.get.exception(token %1)
+  %3 = call i32 @llvm.wasm.get.ehselector(token %1)
+  %4 = call i8* @__cxa_begin_catch(i8* %2) #2 [ "funclet"(token %1) ]
+  invoke void @__cxa_end_catch() [ "funclet"(token %1) ]
+          to label %invoke.cont2 unwind label %catch.dispatch3
+
+catch.dispatch3:                                  ; preds = %catch.start, %catch.dispatch, %entry
+  %5 = catchswitch within none [label %catch.start4] unwind to caller
+
+catch.start4:                                     ; preds = %catch.dispatch3
+  %6 = catchpad within %5 [i8* null]
+  %7 = call i8* @llvm.wasm.get.exception(token %6)
+  %8 = call i32 @llvm.wasm.get.ehselector(token %6)
+  %9 = call i8* @__cxa_begin_catch(i8* %7) #2 [ "funclet"(token %6) ]
+  call void @__cxa_end_catch() [ "funclet"(token %6) ]
+  catchret from %6 to label %try.cont8
+
+try.cont8:                                        ; preds = %invoke.cont, %invoke.cont2, %catch.start4
+  ret void
+
+invoke.cont2:                                     ; preds = %catch.start
+  catchret from %1 to label %try.cont8
+}
+
 ; Here an exception is semantically contained in a loop. 'ehcleanup' BB belongs
 ; to the exception, but does not belong to the loop (because it does not have a
 ; path back to the loop header), and is placed after the loop latch block
 ; 'invoke.cont' intentionally. This tests if 'end_loop' marker is placed
 ; correctly not right after 'invoke.cont' part but after 'ehcleanup' part,
-; NOSORT-LABEL: test18
+; NOSORT-LABEL: test19
 ; NOSORT: loop
 ; NOSORT: try
 ; NOSORT: end_try
 ; NOSORT: end_loop
-define void @test18(i32 %n) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+define void @test19(i32 %n) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   br label %while.cond
 
 while.cond:                                       ; preds = %invoke.cont, %entry
   %n.addr.0 = phi i32 [ %n, %entry ], [ %dec, %invoke.cont ]
   %tobool = icmp ne i32 %n.addr.0, 0
   br i1 %tobool, label %while.body, label %while.end
 

 
 ; When the function return type is non-void and 'end' instructions are at the
 ; very end of a function, CFGStackify's fixEndsAtEndOfFunction function fixes
 ; the corresponding block/loop/try's type to match the function's return type.
 ; But when a `try`'s type is fixed, we should also check `end` instructions
 ; before its corresponding `catch`, because both `try` and `catch` body should
 ; satisfy the return type requirements.
 
-; NOSORT-LABEL: test19
+; NOSORT-LABEL: test20
 ; NOSORT: try i32
 ; NOSORT: loop i32
 ; NOSORT: end_loop
 ; NOSORT: catch
 ; NOSORT: end_try
 ; NOSORT-NEXT: end_function
-define i32 @test19(i32 %n) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+define i32 @test20(i32 %n) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   %t = alloca %class.Object, align 1
   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, %n
   br label %for.body