ConstantFieldPropagation: Fully handle copies (#5969)

If we see A->f0 = A->f0 then we might be copying fields not only between
instances of A but also of any subtypes of A, and so if some subtype has
value x then that x might now have reached any other subtype of A
(even in a sibling type, so long as A is their parent).

We already thought we were handling that, but the mechanism we used to
do so (copying New info to Set info, and letting Set info propagate) was not
enough.

Also add a small constructor to save the work of computing subTypes again.

Add TODOs for some cases that we could optimize regarding copies but
do not, yet.

2 files changed, 21 insertions, 9 deletions

diff --git a/src/ir/struct-utils.h b/src/ir/struct-utils.h
index 667c9ed55..4e24aacf4 100644
--- a/src/ir/struct-utils.h
+++ b/src/ir/struct-utils.h
@@ -119,7 +119,9 @@ struct FunctionStructValuesMap
 //   void noteDefault(Type fieldType, HeapType type, Index index, T& info);
 //
 // * Note a copied value (read from this field and written to the same, possibly
-//   in another object).
+//   in another object). Note that we require that the two types (the one read
+//   from, and written to) are identical; allowing subtyping is possible, but
+//   would add complexity amid diminishing returns.
 //
 //   void noteCopy(HeapType type, Index index, T& info);
 //
@@ -232,8 +234,13 @@ struct StructScanner
 // if we changed something.
 template<typename T> class TypeHierarchyPropagator {
 public:
+  // Constructor that gets a module and computes subtypes.
   TypeHierarchyPropagator(Module& wasm) : subTypes(wasm) {}
 
+  // Constructor that gets subtypes and uses them, avoiding a scan of a
+  // module. TODO: avoid a copy here?
+  TypeHierarchyPropagator(const SubTypes& subTypes) : subTypes(subTypes) {}
+
   SubTypes subTypes;
 
   void propagateToSuperTypes(StructValuesMap<T>& infos) {
diff --git a/src/passes/ConstantFieldPropagation.cpp b/src/passes/ConstantFieldPropagation.cpp
index 61e06ea35..2b7dae147 100644
--- a/src/passes/ConstantFieldPropagation.cpp
+++ b/src/passes/ConstantFieldPropagation.cpp
@@ -56,7 +56,7 @@ struct Bool {
 
   operator bool() const { return value; }
 
-  void combine(bool other) { value = value || other; }
+  bool combine(bool other) { return value = value || other; }
 };
 
 using BoolStructValuesMap = StructUtils::StructValuesMap<Bool>;
@@ -185,10 +185,6 @@ struct PCVScanner
     // Note copies, as they must be considered later. See the comment on the
     // propagation of values below.
     functionCopyInfos[getFunction()][type][index] = true;
-
-    // TODO: This may be extensible to a copy from a subtype, and not just the
-    //       exact type (but this is already entering the realm of diminishing
-    //       returns).
   }
 
   void noteRead(HeapType type, Index index, PossibleConstantValues& info) {
@@ -223,6 +219,8 @@ struct ConstantFieldPropagation : public Pass {
     BoolStructValuesMap combinedCopyInfos;
     functionCopyInfos.combineInto(combinedCopyInfos);
 
+    SubTypes subTypes(*module);
+
     // Handle subtyping. |combinedInfo| so far contains data that represents
     // each struct.new and struct.set's operation on the struct type used in
     // that instruction. That is, if we do a struct.set to type T, the value was
@@ -264,10 +262,17 @@ struct ConstantFieldPropagation : public Pass {
     //   ..
     //   A1->f0 = A2->f0; // Either of these might refer to an A, B, or C.
     //   ..
-    //   foo(C->f0);      // This can contain 20, if the copy involved a C.
+    //   foo(A->f0);      // These can contain 20,
+    //   foo(C->f0);      // if the copy read from B.
     //
     // To handle that, copied fields are treated like struct.set ones (by
-    // copying the struct.new data to struct.set).
+    // copying the struct.new data to struct.set). Note that we must propagate
+    // copying to subtypes first, as in the example above the struct.new values
+    // of subtypes must be taken into account (that is, A or a subtype is being
+    // copied, so we want to do the same thing for B and C as well as A, since
+    // a copy of A means it could be a copy of B or C).
+    StructUtils::TypeHierarchyPropagator<Bool> boolPropagator(subTypes);
+    boolPropagator.propagateToSubTypes(combinedCopyInfos);
     for (auto& [type, copied] : combinedCopyInfos) {
       for (Index i = 0; i < copied.size(); i++) {
         if (copied[i]) {
@@ -277,7 +282,7 @@ struct ConstantFieldPropagation : public Pass {
     }
 
     StructUtils::TypeHierarchyPropagator<PossibleConstantValues> propagator(
-      *module);
+      subTypes);
     propagator.propagateToSuperTypes(combinedNewInfos);
     propagator.propagateToSuperAndSubTypes(combinedSetInfos);