fix an ssa bug: we can't assume that even if all set locations assign to the same local that it is ok to read that local, as locals may also be written elsewhere (#1423)

4 files changed, 154 insertions, 69 deletions

diff --git a/src/ir/local-graph.h b/src/ir/local-graph.h
index 6a8f1b2af..84be2a4c2 100644
--- a/src/ir/local-graph.h
+++ b/src/ir/local-graph.h
@@ -42,7 +42,7 @@ struct LocalGraph {
 
   // externally useful information
   GetSetses getSetses; // the sets affecting each get. a nullptr set means the initial
-                                       // value (0 for a var, the received value for a param)
+                       // value (0 for a var, the received value for a param)
   Locations locations; // where each get and set is (for easy replacing)
 
   // optional computation: compute the influence graphs between sets and gets
diff --git a/src/passes/SSAify.cpp b/src/passes/SSAify.cpp
index 9c680b942..a6127e4d6 100644
--- a/src/passes/SSAify.cpp
+++ b/src/passes/SSAify.cpp
@@ -99,68 +99,38 @@ struct SSAify : public Pass {
         continue;
       }
       // more than 1 set, need a phi: a new local written to at each of the sets
-      // if there is already a local with that property, reuse it
-      auto gatherIndexes = [](SetLocal* set) {
-        std::set<Index> ret;
-        while (set) {
-          ret.insert(set->index);
-          set = set->value->dynCast<SetLocal>();
-        }
-        return ret;
-      };
-      auto indexes = gatherIndexes(*sets.begin());
+      auto new_ = addLocal(get->type);
+      auto old = get->index;
+      get->index = new_;
+      Builder builder(*module);
+      // write to the local in each of our sets
       for (auto* set : sets) {
-        if (set == *sets.begin()) continue;
-        auto currIndexes = gatherIndexes(set);
-        std::vector<Index> intersection;
-        std::set_intersection(indexes.begin(), indexes.end(),
-                              currIndexes.begin(), currIndexes.end(),
-                              std::back_inserter(intersection));
-        indexes.clear();
-        if (intersection.empty()) break;
-        // TODO: or keep sorted vectors?
-        for (Index i : intersection) {
-          indexes.insert(i);
-        }
-      }
-      if (!indexes.empty()) {
-        // we found an index, use it
-        get->index = *indexes.begin();
-      } else {
-        // we need to create a local for this phi'ing
-        auto new_ = addLocal(get->type);
-        auto old = get->index;
-        get->index = new_;
-        Builder builder(*module);
-        // write to the local in each of our sets
-        for (auto* set : sets) {
-          if (set) {
-            // a set exists, just add a tee of its value
-            auto* value = set->value;
-            auto* tee = builder.makeTeeLocal(
+        if (set) {
+          // a set exists, just add a tee of its value
+          auto* value = set->value;
+          auto* tee = builder.makeTeeLocal(
+            new_,
+            value
+          );
+          set->value = tee;
+          // the value may have been something we tracked the location
+          // of. if so, update that, since we moved it into the tee
+          if (graph.locations.count(value) > 0) {
+            assert(graph.locations[value] == &set->value);
+            graph.locations[value] = &tee->value;
+          }
+        } else {
+          // this is a param or the zero init value.
+          if (func->isParam(old)) {
+            // we add a set with the proper
+            // param value at the beginning of the function
+            auto* set = builder.makeSetLocal(
               new_,
-              value
+              builder.makeGetLocal(old, func->getLocalType(old))
             );
-            set->value = tee;
-            // the value may have been something we tracked the location
-            // of. if so, update that, since we moved it into the tee
-            if (graph.locations.count(value) > 0) {
-              assert(graph.locations[value] == &set->value);
-              graph.locations[value] = &tee->value;
-            }
+            functionPrepends.push_back(set);
           } else {
-            // this is a param or the zero init value.
-            if (func->isParam(old)) {
-              // we add a set with the proper
-              // param value at the beginning of the function
-              auto* set = builder.makeSetLocal(
-                new_,
-                builder.makeGetLocal(old, func->getLocalType(old))
-              );
-              functionPrepends.push_back(set);
-            } else {
-              // this is a zero init, so we don't need to do anything actually
-            }
+            // this is a zero init, so we don't need to do anything actually
           }
         }
       }
diff --git a/test/passes/ssa.txt b/test/passes/ssa.txt
index 657ccc128..e6883c0f8 100644
--- a/test/passes/ssa.txt
+++ b/test/passes/ssa.txt
@@ -442,9 +442,12 @@
   (local $4 i32)
   (local $5 i32)
   (local $6 i32)
+  (local $7 i32)
   (set_local $3
-   (tee_local $6
-    (get_local $param)
+   (tee_local $7
+    (tee_local $6
+     (get_local $param)
+    )
    )
   )
   (loop $more
@@ -460,15 +463,17 @@
      )
     )
     (set_local $5
-     (tee_local $6
-      (get_local $4)
+     (tee_local $7
+      (tee_local $6
+       (get_local $4)
+      )
      )
     )
     (br $more)
    )
   )
   (drop
-   (get_local $6)
+   (get_local $7)
   )
  )
  (func $real-loop-outblock (; 9 ;) (type $0) (param $param i32)
@@ -478,9 +483,12 @@
   (local $4 i32)
   (local $5 i32)
   (local $6 i32)
+  (local $7 i32)
   (set_local $3
-   (tee_local $6
-    (get_local $param)
+   (tee_local $7
+    (tee_local $6
+     (get_local $param)
+    )
    )
   )
   (block $stop
@@ -496,15 +504,17 @@
      )
     )
     (set_local $5
-     (tee_local $6
-      (get_local $4)
+     (tee_local $7
+      (tee_local $6
+       (get_local $4)
+      )
      )
     )
     (br $more)
    )
   )
   (drop
-   (get_local $6)
+   (get_local $7)
   )
  )
  (func $loop-loop-param (; 10 ;) (type $0) (param $param i32)
@@ -726,4 +736,65 @@
    (br $label$1)
   )
  )
+ (func $ssa-merge-tricky (; 15 ;) (type $2) (result i32)
+  (local $var$0 i32)
+  (local $var$1 i32)
+  (local $2 i32)
+  (local $3 i32)
+  (local $4 i32)
+  (local $5 i32)
+  (local $6 i32)
+  (local $7 i32)
+  (local $8 i32)
+  (set_local $2
+   (tee_local $8
+    (tee_local $3
+     (tee_local $7
+      (i32.const 0)
+     )
+    )
+   )
+  )
+  (loop $label$1
+   (if
+    (i32.eqz
+     (get_global $global$0)
+    )
+    (return
+     (i32.const 12345)
+    )
+   )
+   (set_global $global$0
+    (i32.const 0)
+   )
+   (if
+    (i32.eqz
+     (get_local $7)
+    )
+    (br_if $label$1
+     (i32.eqz
+      (tee_local $4
+       (tee_local $7
+        (i32.const 1)
+       )
+      )
+     )
+    )
+   )
+   (br_if $label$1
+    (i32.eqz
+     (tee_local $5
+      (tee_local $8
+       (tee_local $6
+        (tee_local $7
+         (get_local $8)
+        )
+       )
+      )
+     )
+    )
+   )
+  )
+  (i32.const -54)
+ )
 )
diff --git a/test/passes/ssa.wast b/test/passes/ssa.wast
index e51189b5e..7c8617103 100644
--- a/test/passes/ssa.wast
+++ b/test/passes/ssa.wast
@@ -339,5 +339,49 @@
     (br $label$1) ;; back to the top, where we will return the zero
    )
   )
+  (func $ssa-merge-tricky (result i32)
+   (local $var$0 i32)
+   (local $var$1 i32)
+   (set_local $var$1
+    (tee_local $var$0
+     (i32.const 0) ;; both vars start out identical
+    )
+   )
+   (loop $label$1
+    (if
+     (i32.eqz
+      (get_global $global$0)
+     )
+     (return
+      (i32.const 12345)
+     )
+    )
+    (set_global $global$0
+     (i32.const 0)
+    )
+    (if
+     (i32.eqz
+      (get_local $var$0) ;; check $0 here. this will get a phi var
+     )
+     (br_if $label$1
+      (i32.eqz
+       (tee_local $var$0 ;; set $0 to 1. here the two diverge. for the phi, we'll get a set here and above
+        (i32.const 1)
+       )
+      )
+     )
+    )
+    (br_if $label$1
+     (i32.eqz ;; indeed equal, enter loop again, and then hang prevention kicks in
+      (tee_local $var$1 ;; set them all to 0
+       (tee_local $var$0
+        (get_local $var$1) ;; this must get $1, not the phis, as even though the sets appear in both sources, we only execute 1.
+       )
+      )
+     )
+    )
+   )
+   (i32.const -54)
+  )
 )