LocalCSE: Fix regression from #6587 by accumulating generativity (#6591)

#6587 was incorrect: It checked generativity early in an incremental manner, but
it did not accumulate that information as we do with hashes. As a result we
could end up optimizing something with a generative child, and sadly we lacked
testing for that case.

This adds incremental generativity computation alongside hashes. It also splits
out this check from isRelevant.

Also add a test for nested effects (as opposed to generativity), but that already
worked before this PR (as we compute effects and invalidation as we go, already).

2 files changed, 69 insertions, 5 deletions

diff --git a/test/lit/passes/local-cse.wast b/test/lit/passes/local-cse.wast
index 8b0f51a7c..4f6156dba 100644
--- a/test/lit/passes/local-cse.wast
+++ b/test/lit/passes/local-cse.wast
@@ -11,7 +11,9 @@
 
   ;; CHECK:      (type $2 (func (param i32)))
 
-  ;; CHECK:      (type $3 (func (result i64)))
+  ;; CHECK:      (type $3 (func (result i32)))
+
+  ;; CHECK:      (type $4 (func (result i64)))
 
   ;; CHECK:      (memory $0 100 100)
 
@@ -356,6 +358,38 @@
     )
   )
 
+  ;; CHECK:      (func $nested-calls (result i32)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i32.add
+  ;; CHECK-NEXT:    (call $nested-calls)
+  ;; CHECK-NEXT:    (call $nested-calls)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i32.add
+  ;; CHECK-NEXT:    (call $nested-calls)
+  ;; CHECK-NEXT:    (call $nested-calls)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (unreachable)
+  ;; CHECK-NEXT: )
+  (func $nested-calls (result i32)
+    ;; Operations that include nested effects are ignored.
+    (drop
+      (i32.add
+        (call $nested-calls)
+        (call $nested-calls)
+      )
+    )
+    (drop
+      (i32.add
+        (call $nested-calls)
+        (call $nested-calls)
+      )
+    )
+    (unreachable)
+  )
+
   ;; CHECK:      (func $many-sets (result i64)
   ;; CHECK-NEXT:  (local $temp i64)
   ;; CHECK-NEXT:  (local $1 i64)
diff --git a/test/lit/passes/local-cse_all-features.wast b/test/lit/passes/local-cse_all-features.wast
index d943b940f..368936ae9 100644
--- a/test/lit/passes/local-cse_all-features.wast
+++ b/test/lit/passes/local-cse_all-features.wast
@@ -67,13 +67,13 @@
 
   ;; CHECK:      (type $2 (func (param (ref $A))))
 
-  ;; CHECK:      (type $3 (func (param (ref null $A))))
+  ;; CHECK:      (type $3 (func))
 
-  ;; CHECK:      (type $4 (func))
+  ;; CHECK:      (type $4 (func (param (ref null $A))))
 
   ;; CHECK:      (type $5 (func (param (ref null $B) (ref $A))))
 
-  ;; CHECK:      (func $struct-gets-nullable (type $3) (param $ref (ref null $A))
+  ;; CHECK:      (func $struct-gets-nullable (type $4) (param $ref (ref null $A))
   ;; CHECK-NEXT:  (local $1 i32)
   ;; CHECK-NEXT:  (drop
   ;; CHECK-NEXT:   (local.tee $1
@@ -182,7 +182,7 @@
     )
   )
 
-  ;; CHECK:      (func $creations (type $4)
+  ;; CHECK:      (func $creations (type $3)
   ;; CHECK-NEXT:  (drop
   ;; CHECK-NEXT:   (struct.new $A
   ;; CHECK-NEXT:    (i32.const 1)
@@ -233,6 +233,36 @@
     )
   )
 
+  ;; CHECK:      (func $nested-generativity (type $3)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (ref.eq
+  ;; CHECK-NEXT:    (struct.new_default $A)
+  ;; CHECK-NEXT:    (struct.new_default $A)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (ref.eq
+  ;; CHECK-NEXT:    (struct.new_default $A)
+  ;; CHECK-NEXT:    (struct.new_default $A)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $nested-generativity
+    ;; Operations that include nested generativity are ignored.
+    (drop
+      (ref.eq
+        (struct.new_default $A)
+        (struct.new_default $A)
+      )
+    )
+    (drop
+      (ref.eq
+        (struct.new_default $A)
+        (struct.new_default $A)
+      )
+    )
+  )
+
   ;; CHECK:      (func $structs-and-arrays-do-not-alias (type $5) (param $array (ref null $B)) (param $struct (ref $A))
   ;; CHECK-NEXT:  (local $2 i32)
   ;; CHECK-NEXT:  (array.set $B