From f7be757a71e5562afad898992574681d50a67dbf Mon Sep 17 00:00:00 2001
From: Alon Zakai <azakai@google.com>
Date: Wed, 8 Dec 2021 11:22:03 -0800
Subject: SimplifyGlobals: Handle nested read-only-to-write patterns (#4365)

The general pattern is

if (!global) { global = 1 }

This PR generalizes that to handle nested appearances,

if ({
  if (!global) { global = 1 }
  !global
}) {
  global = 1
}

With this I can finally see no more "once" global operations on the hottest
function in the currently slowest j2wasm benchmark ("filter").

Also added a failing testcase for something we do not handle yet.
---
 src/passes/SimplifyGlobals.cpp | 26 +++++++++++++++++++++-----
 1 file changed, 21 insertions(+), 5 deletions(-)

(limited to 'src')

diff --git a/src/passes/SimplifyGlobals.cpp b/src/passes/SimplifyGlobals.cpp
index 9730400d6..daaa82447 100644
--- a/src/passes/SimplifyGlobals.cpp
+++ b/src/passes/SimplifyGlobals.cpp
@@ -193,12 +193,17 @@ struct GlobalUseScanner : public WalkerPass<PostWalker<GlobalUseScanner>> {
     struct FlowScanner
       : public ExpressionStackWalker<FlowScanner,
                                      UnifiedExpressionVisitor<FlowScanner>> {
+      GlobalUseScanner& globalUseScanner;
       Name writtenGlobal;
       PassOptions& passOptions;
       Module& wasm;
 
-      FlowScanner(Name writtenGlobal, PassOptions& passOptions, Module& wasm)
-        : writtenGlobal(writtenGlobal), passOptions(passOptions), wasm(wasm) {}
+      FlowScanner(GlobalUseScanner& globalUseScanner,
+                  Name writtenGlobal,
+                  PassOptions& passOptions,
+                  Module& wasm)
+        : globalUseScanner(globalUseScanner), writtenGlobal(writtenGlobal),
+          passOptions(passOptions), wasm(wasm) {}
 
       bool ok = true;
 
@@ -208,7 +213,7 @@ struct GlobalUseScanner : public WalkerPass<PostWalker<GlobalUseScanner>> {
             // We found the get of the global. Check where its value flows to,
             // and how it is used there.
             assert(expressionStack.back() == get);
-            for (Index i = 0; i < expressionStack.size() - 1; i++) {
+            for (int i = int(expressionStack.size()) - 2; i >= 0; i--) {
               // Consider one pair of parent->child, and check if the parent
               // causes any problems when the child's value reaches it.
               auto* parent = expressionStack[i];
@@ -225,7 +230,18 @@ struct GlobalUseScanner : public WalkerPass<PostWalker<GlobalUseScanner>> {
               if (auto* iff = parent->dynCast<If>()) {
                 if (iff->condition == child) {
                   // The child is used to decide what code to run, which is
-                  // dangerous.
+                  // dangerous: check what effects it causes. If it is a nested
+                  // appearance of the pattern, that is one case that we know is
+                  // actually safe.
+                  if (!iff->ifFalse &&
+                      globalUseScanner.readsGlobalOnlyToWriteIt(
+                        iff->condition, iff->ifTrue) == writtenGlobal) {
+                    // This is safe, and we can stop here: the value does not
+                    // flow any further.
+                    break;
+                  }
+
+                  // Otherwise, we found a problem, and can stop.
                   ok = false;
                   break;
                 }
@@ -236,7 +252,7 @@ struct GlobalUseScanner : public WalkerPass<PostWalker<GlobalUseScanner>> {
       }
     };
 
-    FlowScanner scanner(writtenGlobal, getPassOptions(), *getModule());
+    FlowScanner scanner(*this, writtenGlobal, getPassOptions(), *getModule());
     scanner.walk(condition);
     return scanner.ok ? writtenGlobal : Name();
   }
-- 
cgit v1.2.3