Add EH support for CFGWalker (#2597)

This adds EH instruction support for `CFGWalker`. This also implements
`call` instruction handling within a try-catch; every call can possibly
throw and unwind to the innermost catch block.

This adds tests for RedundantSetElimination pass, which uses
`CFGWalker`.

3 files changed, 288 insertions, 0 deletions

diff --git a/src/cfg/cfg-traversal.h b/src/cfg/cfg-traversal.h
index 8693831ad..647b795a4 100644
--- a/src/cfg/cfg-traversal.h
+++ b/src/cfg/cfg-traversal.h
@@ -64,8 +64,15 @@ struct CFGWalker : public ControlFlowWalker<SubType, VisitorType> {
   BasicBlock* currBasicBlock;
   // a block or loop => its branches
   std::map<Expression*, std::vector<BasicBlock*>> branches;
+  // stack of the last blocks of if conditions + the last blocks of if true
+  // bodies
   std::vector<BasicBlock*> ifStack;
+  // stack of the first blocks of loops
   std::vector<BasicBlock*> loopStack;
+  // stack of the last blocks of try bodies
+  std::vector<BasicBlock*> tryStack;
+  // stack of the first blocks of catch bodies
+  std::vector<BasicBlock*> catchStack;
 
   void startBasicBlock() {
     currBasicBlock = ((SubType*)this)->makeBasicBlock();
@@ -198,6 +205,59 @@ struct CFGWalker : public ControlFlowWalker<SubType, VisitorType> {
     self->startUnreachableBlock();
   }
 
+  static void doEndCall(SubType* self, Expression** currp) {
+    // Every call can possibly throw, but we don't end the current basic block
+    // unless the call is within a try-catch, because the CFG will have too many
+    // blocks that way, and if an exception is thrown, the function will be
+    // exited anyway.
+    if (!self->catchStack.empty()) {
+      auto* last = self->currBasicBlock;
+      self->startBasicBlock();
+      self->link(last, self->currBasicBlock);    // exception not thrown
+      self->link(last, self->catchStack.back()); // exception thrown
+    }
+  }
+
+  static void doStartTry(SubType* self, Expression** currp) {
+    auto* last = self->currBasicBlock;
+    self->startBasicBlock(); // catch body's first block
+    self->catchStack.push_back(self->currBasicBlock);
+    self->currBasicBlock = last; // reset to the current block
+  }
+
+  static void doStartCatch(SubType* self, Expression** currp) {
+    self->tryStack.push_back(self->currBasicBlock); // last block of try body
+    self->currBasicBlock = self->catchStack.back();
+    self->catchStack.pop_back();
+  }
+
+  static void doEndTry(SubType* self, Expression** currp) {
+    auto* last = self->currBasicBlock;
+    self->startBasicBlock(); // continuation block after try-catch
+    // catch body's last block -> continuation block
+    self->link(last, self->currBasicBlock);
+    // try body's last block -> continuation block
+    self->link(self->tryStack.back(), self->currBasicBlock);
+    self->tryStack.pop_back();
+  }
+
+  static void doEndThrow(SubType* self, Expression** currp) {
+    // We unwind to the innermost catch, if any
+    if (!self->catchStack.empty()) {
+      self->link(self->currBasicBlock, self->catchStack.back());
+    }
+    self->startUnreachableBlock();
+  }
+
+  static void doEndBrOnExn(SubType* self, Expression** currp) {
+    auto* curr = (*currp)->cast<BrOnExn>();
+    self->branches[self->findBreakTarget(curr->name)].push_back(
+      self->currBasicBlock); // branch to the target
+    auto* last = self->currBasicBlock;
+    self->startBasicBlock();
+    self->link(last, self->currBasicBlock); // we might fall through
+  }
+
   static void scan(SubType* self, Expression** currp) {
     Expression* curr = *currp;
 
@@ -238,6 +298,28 @@ struct CFGWalker : public ControlFlowWalker<SubType, VisitorType> {
         self->pushTask(SubType::doStartUnreachableBlock, currp);
         break;
       }
+      case Expression::Id::CallId:
+      case Expression::Id::CallIndirectId: {
+        self->pushTask(SubType::doEndCall, currp);
+        break;
+      }
+      case Expression::Id::TryId: {
+        self->pushTask(SubType::doEndTry, currp);
+        self->pushTask(SubType::scan, &curr->cast<Try>()->catchBody);
+        self->pushTask(SubType::doStartCatch, currp);
+        self->pushTask(SubType::scan, &curr->cast<Try>()->body);
+        self->pushTask(SubType::doStartTry, currp);
+        return; // don't do anything else
+      }
+      case Expression::Id::ThrowId:
+      case Expression::Id::RethrowId: {
+        self->pushTask(SubType::doEndThrow, currp);
+        break;
+      }
+      case Expression::Id::BrOnExnId: {
+        self->pushTask(SubType::doEndBrOnExn, currp);
+        break;
+      }
       default: {}
     }
 
@@ -263,6 +345,8 @@ struct CFGWalker : public ControlFlowWalker<SubType, VisitorType> {
     assert(branches.size() == 0);
     assert(ifStack.size() == 0);
     assert(loopStack.size() == 0);
+    assert(tryStack.size() == 0);
+    assert(catchStack.size() == 0);
   }
 
   std::unordered_set<BasicBlock*> findLiveBlocks() {
diff --git a/test/passes/rse.txt b/test/passes/rse_all-features.txt
index 6eb7996bf..82dc115ac 100644
--- a/test/passes/rse.txt
+++ b/test/passes/rse_all-features.txt
@@ -3,6 +3,7 @@
  (type $i32_=>_none (func (param i32)))
  (type $i32_i32_=>_none (func (param i32 i32)))
  (type $i32_f64_=>_none (func (param i32 f64)))
+ (event $e (attr 0) (param i32))
  (func $basic (; 0 ;) (param $x i32) (param $y f64)
   (local $a f32)
   (local $b i64)
@@ -459,4 +460,128 @@
    )
   )
  )
+ (func $try1 (; 19 ;)
+  (local $x i32)
+  (try
+   (nop)
+   (catch
+    (drop
+     (exnref.pop)
+    )
+    (local.set $x
+     (i32.const 1)
+    )
+   )
+  )
+  (local.set $x
+   (i32.const 1)
+  )
+ )
+ (func $try2 (; 20 ;)
+  (local $x i32)
+  (try
+   (block $block
+    (throw $e
+     (i32.const 0)
+    )
+    (local.set $x
+     (i32.const 1)
+    )
+   )
+   (catch
+    (drop
+     (exnref.pop)
+    )
+   )
+  )
+  (local.set $x
+   (i32.const 1)
+  )
+ )
+ (func $try3 (; 21 ;)
+  (local $x i32)
+  (try
+   (throw $e
+    (i32.const 0)
+   )
+   (catch
+    (drop
+     (exnref.pop)
+    )
+    (local.set $x
+     (i32.const 1)
+    )
+   )
+  )
+  (drop
+   (i32.const 1)
+  )
+ )
+ (func $foo (; 22 ;)
+  (nop)
+ )
+ (func $try4 (; 23 ;)
+  (local $x i32)
+  (try
+   (block $block
+    (call $foo)
+    (local.set $x
+     (i32.const 1)
+    )
+   )
+   (catch
+    (drop
+     (exnref.pop)
+    )
+   )
+  )
+  (local.set $x
+   (i32.const 1)
+  )
+ )
+ (func $try5 (; 24 ;)
+  (local $x i32)
+  (try
+   (block $block
+    (local.set $x
+     (i32.const 1)
+    )
+    (call $foo)
+   )
+   (catch
+    (drop
+     (exnref.pop)
+    )
+   )
+  )
+  (drop
+   (i32.const 1)
+  )
+ )
+ (func $nested-try (; 25 ;)
+  (local $x i32)
+  (try
+   (try
+    (throw $e
+     (i32.const 0)
+    )
+    (catch
+     (rethrow
+      (exnref.pop)
+     )
+    )
+   )
+   (catch
+    (drop
+     (exnref.pop)
+    )
+    (local.set $x
+     (i32.const 1)
+    )
+   )
+  )
+  (drop
+   (i32.const 1)
+  )
+ )
 )
diff --git a/test/passes/rse.wast b/test/passes/rse_all-features.wast
index 22d13c491..09b0d720d 100644
--- a/test/passes/rse.wast
+++ b/test/passes/rse_all-features.wast
@@ -277,5 +277,84 @@
     )
    )
   )
+
+  (event $e (attr 0) (param i32))
+  (func $try1
+    (local $x i32)
+    (try
+      (catch
+        (drop (exnref.pop))
+        (local.set $x (i32.const 1))
+      )
+    )
+    (local.set $x (i32.const 1)) ;; should NOT be dropped
+  )
+  (func $try2
+    (local $x i32)
+    (try
+      (block
+        (throw $e (i32.const 0))
+        (local.set $x (i32.const 1))
+      )
+      (catch
+        (drop (exnref.pop))
+      )
+    )
+    (local.set $x (i32.const 1)) ;; should NOT be dropped
+  )
+  (func $try3
+    (local $x i32)
+    (try
+      (throw $e (i32.const 0))
+      (catch
+        (drop (exnref.pop))
+        (local.set $x (i32.const 1))
+      )
+    )
+    (local.set $x (i32.const 1)) ;; should be dropped
+  )
+  (func $foo)
+  (func $try4
+    (local $x i32)
+    (try
+      (block
+        (call $foo)
+        (local.set $x (i32.const 1))
+      )
+      (catch
+        (drop (exnref.pop))
+      )
+    )
+    (local.set $x (i32.const 1)) ;; should NOT be dropped
+  )
+  (func $try5
+    (local $x i32)
+    (try
+      (block
+        (local.set $x (i32.const 1))
+        (call $foo)
+      )
+      (catch
+        (drop (exnref.pop))
+      )
+    )
+    (local.set $x (i32.const 1)) ;; should be dropped
+  )
+  (func $nested-try
+    (local $x i32)
+    (try
+      (try
+        (throw $e (i32.const 0))
+        (catch
+          (rethrow (exnref.pop))
+        )
+      )
+      (catch
+        (drop (exnref.pop))
+        (local.set $x (i32.const 1))
+      )
+    )
+    (local.set $x (i32.const 1)) ;; should be dropped
+  )
 )