From 60bd610acaa91cab538497342eb06e3b50d2fac9 Mon Sep 17 00:00:00 2001
From: Alon Zakai <azakai@google.com>
Date: Wed, 21 Aug 2024 16:12:42 -0700
Subject: [NFC] Avoid quadratic time in
 StackIROptimizer::removeUnneededBlocks() (#6859)

This is in quite ancient code, so it's a long-standing issue, but it got worse
when we enabled StackIR in more situations (#6568), which made it more
noticeable, I think.

For example, testing on test_biggerswitch in Emscripten, the LLVM part
is pretty slow too so the Binaryen slowdown didn't stand out hugely, but
just doing

wasm-opt --optimize-level=2 input.wasm -o output.wasm

(that is, do no work, but set the optimize level to 2 so that StackIR opts
are run) used to take 28 seconds (!). With this PR that goes down to less
than 1.
---
 src/wasm/wasm-stack-opts.cpp | 20 +++++++++++++++-----
 1 file changed, 15 insertions(+), 5 deletions(-)

(limited to 'src')

diff --git a/src/wasm/wasm-stack-opts.cpp b/src/wasm/wasm-stack-opts.cpp
index 5e18cf26f..cf4c094b5 100644
--- a/src/wasm/wasm-stack-opts.cpp
+++ b/src/wasm/wasm-stack-opts.cpp
@@ -18,6 +18,7 @@
 // Operations on Stack IR.
 //
 
+#include "ir/branch-utils.h"
 #include "ir/iteration.h"
 #include "ir/local-graph.h"
 #include "pass.h"
@@ -269,17 +270,26 @@ void StackIROptimizer::local2Stack() {
   }
 }
 
-// There may be unnecessary blocks we can remove: blocks
-// without branches to them are always ok to remove.
-// TODO: a branch to a block in an if body can become
-//       a branch to that if body
+// There may be unnecessary blocks we can remove: blocks without arriving
+// branches are always ok to remove.
+// TODO: A branch to a block in an if body can become a branch to that if body.
 void StackIROptimizer::removeUnneededBlocks() {
+  // First, find all branch targets.
+  std::unordered_set<Name> targets;
+  for (auto*& inst : insts) {
+    if (inst) {
+      BranchUtils::operateOnScopeNameUses(
+        inst->origin, [&](Name& name) { targets.insert(name); });
+    }
+  }
+
+  // Remove untargeted blocks.
   for (auto*& inst : insts) {
     if (!inst) {
       continue;
     }
     if (auto* block = inst->origin->dynCast<Block>()) {
-      if (!BranchUtils::BranchSeeker::has(block, block->name)) {
+      if (!block->name.is() || !targets.count(block->name)) {
         // TODO optimize, maybe run remove-unused-names
         inst = nullptr;
       }
-- 
cgit v1.2.3