[WebAssembly] Remove unnecessary instructions after TRY marker placement

[aheejin]

Summary

This removes unnecessary instructions after TRY marker placement. There
are two cases:

• end/end_block can be removed if they overlap with try/end_try and they have the same return types.
• br right before catch that branches to after end_try can be deleted.

[aheejin]

Deleted newlines

[aheejin]

Fix an indentation

[aheejin]

rebase

[aheejin]

Run removeUnnecessaryInstrs only when EH is used

[aheejin]

rebase

[aheejin]

Add annotations

[aheejin]

Add annotations to rethrow too

[dschuff]

lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

847 ↗

(On Diff #188125)

should this unconditional run still be here?

[aheejin]

Remove a stray redundant line

[aheejin]

lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

847 ↗

(On Diff #188125)

No. I forgot to delete it. Thanks for the catch.

[aheejin]

I should've unregister the scope before deleting MI

llvm/trunk/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

class WebAssemblyCFGStackify final : public MachineFunctionPass {
   // which holds the beginning of the scope. This will allow us to quickly skip
   // over scoped regions when walking blocks.
   SmallVector<MachineBasicBlock *, 8> ScopeTops;
 
   void placeMarkers(MachineFunction &MF);
   void placeBlockMarker(MachineBasicBlock &MBB);
   void placeLoopMarker(MachineBasicBlock &MBB);
   void placeTryMarker(MachineBasicBlock &MBB);
+  void removeUnnecessaryInstrs(MachineFunction &MF);
   void rewriteDepthImmediates(MachineFunction &MF);
   void fixEndsAtEndOfFunction(MachineFunction &MF);
 
   // For each BLOCK|LOOP|TRY, the corresponding END_(BLOCK|LOOP|TRY).
   DenseMap<const MachineInstr *, MachineInstr *> BeginToEnd;
   // For each END_(BLOCK|LOOP|TRY), the corresponding BLOCK|LOOP|TRY.
   DenseMap<const MachineInstr *, MachineInstr *> EndToBegin;
   // <TRY marker, EH pad> map
   DenseMap<const MachineInstr *, MachineBasicBlock *> TryToEHPad;
   // <EH pad, TRY marker> map
   DenseMap<const MachineBasicBlock *, MachineInstr *> EHPadToTry;
 
-  // Helper functions to register scope information created by marker
-  // instructions.
+  // Helper functions to register / unregister scope information created by
+  // marker instructions.
   void registerScope(MachineInstr *Begin, MachineInstr *End);
   void registerTryScope(MachineInstr *Begin, MachineInstr *End,
                         MachineBasicBlock *EHPad);
+  void unregisterScope(MachineInstr *Begin);
 
 public:
   static char ID; // Pass identification, replacement for typeid
   WebAssemblyCFGStackify() : MachineFunctionPass(ID) {}
   ~WebAssemblyCFGStackify() override { releaseMemory(); }
   void releaseMemory() override;
 };
 } // end anonymous namespace

 void WebAssemblyCFGStackify::registerTryScope(MachineInstr *Begin,
                                               MachineInstr *End,
                                               MachineBasicBlock *EHPad) {
   registerScope(Begin, End);
   TryToEHPad[Begin] = EHPad;
   EHPadToTry[EHPad] = Begin;
 }
 
+void WebAssemblyCFGStackify::unregisterScope(MachineInstr *Begin) {
+  assert(BeginToEnd.count(Begin));
+  MachineInstr *End = BeginToEnd[Begin];
+  assert(EndToBegin.count(End));
+  BeginToEnd.erase(Begin);
+  EndToBegin.erase(End);
+  MachineBasicBlock *EHPad = TryToEHPad.lookup(Begin);
+  if (EHPad) {
+    assert(EHPadToTry.count(EHPad));
+    TryToEHPad.erase(Begin);
+    EHPadToTry.erase(EHPad);
+  }
+}
+
 /// Insert a BLOCK marker for branches to MBB (if needed).
 void WebAssemblyCFGStackify::placeBlockMarker(MachineBasicBlock &MBB) {
   // This should have been handled in placeTryMarker.
   if (MBB.isEHPad())
     return;
 
   MachineFunction &MF = *MBB.getParent();
   auto &MDT = getAnalysis<MachineDominatorTree>();
#endif
 
   // Track the farthest-spanning scope that ends at this point.
   int Number = Cont->getNumber();
   if (!ScopeTops[Number] ||
       ScopeTops[Number]->getNumber() > Header->getNumber())
     ScopeTops[Number] = Header;
 }
 
+void WebAssemblyCFGStackify::removeUnnecessaryInstrs(MachineFunction &MF) {
+  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
+
+  // 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:
+  //   catch
+  //     ...
+  // bb2:
+  //   end
+  for (auto &MBB : MF) {
+    if (!MBB.isEHPad())
+      continue;
+
+    MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
+    SmallVector<MachineOperand, 4> Cond;
+    MachineBasicBlock *EHPadLayoutPred =
+        &*std::prev(MachineFunction::iterator(&MBB));
+    MachineBasicBlock *Cont = BeginToEnd[EHPadToTry[&MBB]]->getParent();
+    bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond);
+    if (Analyzable && ((Cond.empty() && TBB && TBB == Cont) ||
+                       (!Cond.empty() && FBB && FBB == Cont)))
+      TII.removeBranch(*EHPadLayoutPred);
+  }
+
+  // When there are block / end_block markers that overlap with try / end_try
+  // markers, and the block and try markers' return types are the same, the
+  // block /end_block markers are not necessary, because try / end_try markers
+  // also can serve as boundaries for branches.
+  // block         <- Not necessary
+  //   try
+  //     ...
+  //   catch
+  //     ...
+  //   end
+  // end           <- Not necessary
+  SmallVector<MachineInstr *, 32> ToDelete;
+  for (auto &MBB : MF) {
+    for (auto &MI : MBB) {
+      if (MI.getOpcode() != WebAssembly::TRY)
+        continue;
+
+      MachineInstr *Try = &MI, *EndTry = BeginToEnd[Try];
+      MachineBasicBlock *TryBB = Try->getParent();
+      MachineBasicBlock *Cont = EndTry->getParent();
+      int64_t RetType = Try->getOperand(0).getImm();
+      for (auto B = MachineBasicBlock::iterator(Try),
+                E = std::next(MachineBasicBlock::iterator(EndTry));
+           B != TryBB->begin() && E != Cont->end() &&
+           std::prev(B)->getOpcode() == WebAssembly::BLOCK &&
+           E->getOpcode() == WebAssembly::END_BLOCK &&
+           std::prev(B)->getOperand(0).getImm() == RetType;
+           --B, ++E) {
+        ToDelete.push_back(&*std::prev(B));
+        ToDelete.push_back(&*E);
+      }
+    }
+  }
+  for (auto *MI : ToDelete) {
+    if (MI->getOpcode() == WebAssembly::BLOCK)
+      unregisterScope(MI);
+    MI->eraseFromParent();
+  }
+}
+
 static unsigned
 getDepth(const SmallVectorImpl<const MachineBasicBlock *> &Stack,
          const MachineBasicBlock *MBB) {
   unsigned Depth = 0;
   for (auto X : reverse(Stack)) {
     if (X == MBB)
       break;
     ++Depth;
void WebAssemblyCFGStackify::releaseMemory() {
   TryToEHPad.clear();
   EHPadToTry.clear();
 }
 
 bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
   LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n"
                        "********** Function: "
                     << MF.getName() << '\n');
+  const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
 
   releaseMemory();
 
   // Liveness is not tracked for VALUE_STACK physreg.
   MF.getRegInfo().invalidateLiveness();
 
   // Place the BLOCK/LOOP/TRY markers to indicate the beginnings of scopes.
   placeMarkers(MF);
 
+  if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&
+      MF.getFunction().hasPersonalityFn())
+    // Remove unnecessary instructions.
+    removeUnnecessaryInstrs(MF);
+
   // Convert MBB operands in terminators to relative depth immediates.
   rewriteDepthImmediates(MF);
 
   // Fix up block/loop/try signatures at the end of the function to conform to
   // WebAssembly's rules.
   fixEndsAtEndOfFunction(MF);
 
   // Add an end instruction at the end of the function body.
   const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
   if (!MF.getSubtarget<WebAssemblySubtarget>()
            .getTargetTriple()
            .isOSBinFormatELF())
     appendEndToFunction(MF, TII);
 
   return true;
 }

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

 ;   try {
 ;     foo();
 ;   } catch (int) {
 ;   } catch (double) {
 ;   }
 ; }
 
 ; CHECK-LABEL: test0
-; CHECK: block
-; CHECK:   try
-; CHECK:     call      foo
-; CHECK:     br        0                               # 0: down to label1
-; CHECK:   catch
-; CHECK:     block
-; CHECK:       br_if     0, {{.*}}                     # 0: down to label3
-; CHECK:       i32.call  $drop=, __cxa_begin_catch
-; CHECK:       call      __cxa_end_catch
-; CHECK:       br        1                             # 1: down to label1
-; CHECK:     end_block                                 # label3:
-; CHECK:     block
-; CHECK:       br_if     0, {{.*}}                     # 0: down to label4
-; CHECK:       i32.call  $drop=, __cxa_begin_catch
-; CHECK:       call      __cxa_end_catch
-; CHECK:       br        1                             # 1: down to label1
-; CHECK:     end_block                                 # label4:
-; CHECK:     call      __cxa_rethrow
-; CHECK:   end_try                                     # label1:
-; CHECK: end_block
+; CHECK: try
+; CHECK:   call      foo
+; CHECK: catch
+; CHECK:   block
+; CHECK:     br_if     0, {{.*}}                       # 0: down to label2
+; CHECK:     i32.call  $drop=, __cxa_begin_catch
+; CHECK:     call      __cxa_end_catch
+; CHECK:     br        1                               # 1: down to label0
+; CHECK:   end_block                                   # label2:
+; CHECK:   block
+; CHECK:     br_if     0, {{.*}}                       # 0: down to label3
+; CHECK:     i32.call  $drop=, __cxa_begin_catch
+; CHECK:     call      __cxa_end_catch
+; CHECK:     br        1                               # 1: down to label0
+; CHECK:   end_block                                   # label3:
+; CHECK:   call      __cxa_rethrow
+; CHECK: end_try                                       # label0:
 define void @test0() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   invoke void @foo()
           to label %try.cont unwind label %catch.dispatch
 
 catch.dispatch:                                   ; preds = %entry
   %0 = catchswitch within none [label %catch.start] unwind to caller
 

 ;     foo();
 ;   } catch (...) {
 ;     for (int i = 0; i < 50; i++)
 ;       foo();
 ;   }
 ; }
 
 ; CHECK-LABEL: test2
-; CHECK: block
-; CHECK:   try
-; CHECK:     call      foo
-; CHECK:     br        0                               # 0: down to label17
-; CHECK:   catch
-; CHECK:     i32.call  $drop=, __cxa_begin_catch
-; CHECK:     loop                                      # label19:
-; CHECK:       block
-; CHECK:         block
-; CHECK:           br_if     0, {{.*}}                 # 0: down to label21
-; CHECK:           try
-; CHECK:             call      foo
-; CHECK:             br        2                       # 2: down to label20
-; CHECK:           catch
-; CHECK:             block
-; CHECK:               try
-; CHECK:                 call      __cxa_end_catch
-; CHECK:                 br        0                   # 0: down to label24
-; CHECK:               catch
-; CHECK:                 call      __clang_call_terminate
-; CHECK:                 unreachable
-; CHECK:               end_try                         # label24:
-; CHECK:             end_block
-; CHECK:             rethrow                           # to caller
-; CHECK:           end_try
-; CHECK:         end_block                             # label21:
-; CHECK:         call      __cxa_end_catch
-; CHECK:         br        2                           # 2: down to label17
-; CHECK:       end_block                               # label20:
-; CHECK:       br        0                             # 0: up to label19
-; CHECK:     end_loop
-; CHECK:   end_try                                     # label17:
-; CHECK: end_block
+; CHECK: try
+; CHECK:   call      foo
+; CHECK: catch
+; CHECK:   i32.call  $drop=, __cxa_begin_catch
+; CHECK:   loop                                        # label15:
+; CHECK:     block
+; CHECK:       block
+; CHECK:         br_if     0, {{.*}}                   # 0: down to label17
+; CHECK:         try
+; CHECK:           call      foo
+; CHECK:           br        2                         # 2: down to label16
+; CHECK:         catch
+; CHECK:           try
+; CHECK:             call      __cxa_end_catch
+; CHECK:           catch
+; CHECK:             call      __clang_call_terminate
+; CHECK:             unreachable
+; CHECK:           end_try
+; CHECK:           rethrow                             # to caller
+; CHECK:         end_try
+; CHECK:       end_block                               # label17:
+; CHECK:       call      __cxa_end_catch
+; CHECK:       br        2                             # 2: down to label13
+; CHECK:     end_block                                 # label16:
+; CHECK:     br        0                               # 0: up to label15
+; CHECK:   end_loop
+; CHECK: end_try                                       # label13:
 define void @test2() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   invoke void @foo()
           to label %try.cont unwind label %catch.dispatch
 
 catch.dispatch:                                   ; preds = %entry
   %0 = catchswitch within none [label %catch.start] unwind to caller
 

llvm/trunk/test/CodeGen/WebAssembly/exception.ll

 ;   try {
 ;     foo();
 ;   } catch (int) {
 ;   }
 ; }
 
 ; CHECK-LABEL: test_catch:
 ; CHECK:     global.get  ${{.+}}=, __stack_pointer
-; CHECK:     block
-; CHECK:       try
-; CHECK:         call      foo
-; CHECK:         br        0
-; CHECK:       catch     $[[EXCEPT_REF:[0-9]+]]=
-; CHECK:         global.set  __stack_pointer
-; CHECK:         block i32
-; CHECK:           br_on_exn 0, __cpp_exception, $[[EXCEPT_REF]]
-; CHECK:           rethrow
-; CHECK:         end_block
-; CHECK:         extract_exception $[[EXN:[0-9]+]]=
-; CHECK-DAG:     i32.store  __wasm_lpad_context
-; CHECK-DAG:     i32.store  __wasm_lpad_context+4
-; CHECK:         i32.call  $drop=, _Unwind_CallPersonality, $[[EXN]]
-; CHECK:         block
-; CHECK:           br_if     0
-; CHECK:           i32.call  $drop=, __cxa_begin_catch
-; CHECK:           call      __cxa_end_catch
-; CHECK:           br        1
-; CHECK:         end_block
-; CHECK:         call      __cxa_rethrow
-; CHECK:       end_try
-; CHECK:     end_block
+; CHECK:     try
+; CHECK:       call      foo
+; CHECK:     catch     $[[EXCEPT_REF:[0-9]+]]=
+; CHECK:       global.set  __stack_pointer
+; CHECK:       block i32
+; CHECK:         br_on_exn 0, __cpp_exception, $[[EXCEPT_REF]]
+; CHECK:         rethrow
+; CHECK:       end_block
+; CHECK:       extract_exception $[[EXN:[0-9]+]]=
+; CHECK-DAG:   i32.store  __wasm_lpad_context
+; CHECK-DAG:   i32.store  __wasm_lpad_context+4
+; CHECK:       i32.call  $drop=, _Unwind_CallPersonality, $[[EXN]]
+; CHECK:       block
+; CHECK:         br_if     0
+; CHECK:         i32.call  $drop=, __cxa_begin_catch
+; CHECK:         call      __cxa_end_catch
+; CHECK:         br        1
+; CHECK:       end_block
+; CHECK:       call      __cxa_rethrow
+; CHECK:     end_try
 define void @test_catch() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   invoke void @foo()
           to label %try.cont unwind label %catch.dispatch
 
 catch.dispatch:                                   ; preds = %entry
   %0 = catchswitch within none [label %catch.start] unwind to caller
 

 ;   ~Temp() {}
 ; };
 ; void test_cleanup() {
 ;   Temp t;
 ;   foo();
 ; }
 
 ; CHECK-LABEL: test_cleanup:
-; CHECK: block
-; CHECK:   try
-; CHECK:     call      foo
-; CHECK:     br        0
-; CHECK:   catch
-; CHECK:     global.set  __stack_pointer
-; CHECK:     i32.call  $drop=, _ZN4TempD2Ev
-; CHECK:     rethrow
-; CHECK:   end_try
-; CHECK: end_block
+; CHECK: try
+; CHECK:   call      foo
+; CHECK: catch
+; CHECK:   global.set  __stack_pointer
+; CHECK:   i32.call  $drop=, _ZN4TempD2Ev
+; CHECK:   rethrow
+; CHECK: end_try
 define void @test_cleanup() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   %t = alloca %struct.Temp, align 1
   invoke void @foo()
           to label %invoke.cont unwind label %ehcleanup
 
 invoke.cont:                                      ; preds = %entry
   %call = call %struct.Temp* @_ZN4TempD2Ev(%struct.Temp* %t)

 ;   try {
 ;     foo();
 ;   } catch (...) {
 ;     foo();
 ;   }
 ; }
 
 ; CHECK-LABEL: test_terminatepad
-; CHECK: block
-; CHECK:   try
-; CHECK:     call      foo
-; CHECK:     br        0
-; CHECK:   catch
-; CHECK:     i32.call  $drop=, __cxa_begin_catch
-; CHECK:     block
-; CHECK:       try
-; CHECK:         call      foo
-; CHECK:         br        0
-; CHECK:       catch
-; CHECK:         block
-; CHECK:           try
-; CHECK:             call      __cxa_end_catch
-; CHECK:             br        0
-; CHECK:           catch
-; CHECK:             block     i32
-; CHECK:               br_on_exn   0, __cpp_exception
-; CHECK:               call      __clang_call_terminate, 0
-; CHECK:               unreachable
-; CHECK:             end_block
-; CHECK:             call      __clang_call_terminate
-; CHECK:             unreachable
-; CHECK:           end_try
-; CHECK:         end_block
-; CHECK:         rethrow
-; CHECK:       end_try
-; CHECK:     end_block
-; CHECK:     call      __cxa_end_catch
-; CHECK:   end_try
-; CHECK: end_block
+; CHECK: try
+; CHECK:   call      foo
+; CHECK: catch
+; CHECK:   i32.call  $drop=, __cxa_begin_catch
+; CHECK:   try
+; CHECK:     call      foo
+; CHECK:   catch
+; CHECK:     try
+; CHECK:       call      __cxa_end_catch
+; CHECK:     catch
+; CHECK:       block     i32
+; CHECK:         br_on_exn   0, __cpp_exception
+; CHECK:         call      __clang_call_terminate, 0
+; CHECK:         unreachable
+; CHECK:       end_block
+; CHECK:       call      __clang_call_terminate
+; CHECK:       unreachable
+; CHECK:     end_try
+; CHECK:     rethrow
+; CHECK:   end_try
+; CHECK:   call      __cxa_end_catch
+; CHECK: end_try
 define void @test_terminatepad() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   invoke void @foo()
           to label %try.cont unwind label %catch.dispatch
 
 catch.dispatch:                                   ; preds = %entry
   %0 = catchswitch within none [label %catch.start] unwind to caller
 

 ;   try {
 ;     foo();
 ;   } catch (int) {
 ;     foo();
 ;   }
 ; }
 
 ; CHECK-LABEL: test_no_prolog_epilog_in_ehpad
-; CHECK:     block
-; CHECK:       try
-; CHECK:         call      foo
-; CHECK:         br        0
-; CHECK:       catch
-; CHECK-NOT:     global.get  $push{{.+}}=, __stack_pointer
-; CHECK:         global.set  __stack_pointer
-; CHECK:         block
-; CHECK:           block
-; CHECK:             br_if     0
-; CHECK:             i32.call  $drop=, __cxa_begin_catch
-; CHECK:             try
-; CHECK:               call      foo
-; CHECK:               br        2
-; CHECK:             catch
-; CHECK-NOT:           global.get  $push{{.+}}=, __stack_pointer
-; CHECK:               global.set  __stack_pointer
-; CHECK:               call      __cxa_end_catch
-; CHECK:               rethrow
-; CHECK-NOT:           global.set  __stack_pointer, $pop{{.+}}
-; CHECK:             end_try
-; CHECK:           end_block
-; CHECK:           call      __cxa_rethrow
-; CHECK:         end_block
-; CHECK-NOT:     global.set  __stack_pointer, $pop{{.+}}
-; CHECK:         call      __cxa_end_catch
-; CHECK:       end_try
-; CHECK:     end_block
+; CHECK:     try
+; CHECK:       call      foo
+; CHECK:     catch
+; CHECK-NOT:   global.get  $push{{.+}}=, __stack_pointer
+; CHECK:       global.set  __stack_pointer
+; CHECK:       block
+; CHECK:         block
+; CHECK:           br_if     0
+; CHECK:           i32.call  $drop=, __cxa_begin_catch
+; CHECK:           try
+; CHECK:             call      foo
+; CHECK:           catch
+; CHECK-NOT:         global.get  $push{{.+}}=, __stack_pointer
+; CHECK:             global.set  __stack_pointer
+; CHECK:             call      __cxa_end_catch
+; CHECK:             rethrow
+; CHECK-NOT:         global.set  __stack_pointer, $pop{{.+}}
+; CHECK:           end_try
+; CHECK:         end_block
+; CHECK:         call      __cxa_rethrow
+; CHECK:       end_block
+; CHECK-NOT:   global.set  __stack_pointer, $pop{{.+}}
+; CHECK:       call      __cxa_end_catch
+; CHECK:     end_try
 define void @test_no_prolog_epilog_in_ehpad() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   %stack_var = alloca i32, align 4
   call void @bar(i32* %stack_var)
   invoke void @foo()
           to label %try.cont unwind label %catch.dispatch
 
 catch.dispatch:                                   ; preds = %entry

 ; void test_no_sp_writeback() {
 ;   try {
 ;     foo();
 ;   } catch (...) {
 ;   }
 ; }
 
 ; CHECK-LABEL: test_no_sp_writeback
-; CHECK:     block
-; CHECK:       try
-; CHECK:         call      foo
-; CHECK:         br        0
-; CHECK:       catch
-; CHECK:         i32.call  $drop=, __cxa_begin_catch
-; CHECK:         call      __cxa_end_catch
-; CHECK:       end_try
-; CHECK:     end_block
+; CHECK:     try
+; CHECK:       call      foo
+; CHECK:     catch
+; CHECK:       i32.call  $drop=, __cxa_begin_catch
+; CHECK:       call      __cxa_end_catch
+; CHECK:     end_try
 ; CHECK-NOT: global.set  __stack_pointer
 ; CHECK:     return
 define void @test_no_sp_writeback() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   invoke void @foo()
           to label %try.cont unwind label %catch.dispatch
 
 catch.dispatch:                                   ; preds = %entry