Update Precompute to handle tuples (#2687)

This involves replacing `Literal::makeZero` with `Literal::makeZeroes`
and `Literal::makeSingleZero` and updating `isConstantExpression` to
handle constant tuples as well. Also makes `Literals` its own struct
and adds convenience methods on it.

17 files changed, 206 insertions, 67 deletions

diff --git a/check.py b/check.py
index f48671825..7f17522e7 100755
--- a/check.py
+++ b/check.py
@@ -461,12 +461,12 @@ TEST_SUITES = OrderedDict([
     ('wasm-metadce', run_wasm_metadce_tests),
     ('wasm-reduce', run_wasm_reduce_tests),
     ('spec', run_spec_tests),
-    ('binaryenjs', binaryenjs.test_binaryen_js),
     ('lld', lld.test_wasm_emscripten_finalize),
     ('wasm2js', wasm2js.test_wasm2js),
     ('validator', run_validator_tests),
     ('gcc', run_gcc_tests),
     ('unit', run_unittest),
+    ('binaryenjs', binaryenjs.test_binaryen_js),
 ])
 
 
diff --git a/src/asm2wasm.h b/src/asm2wasm.h
index 95a5ba481..5fdb5f364 100644
--- a/src/asm2wasm.h
+++ b/src/asm2wasm.h
@@ -457,7 +457,7 @@ private:
   void allocateGlobal(IString name, Type type, Literal value = Literal()) {
     assert(mappedGlobals.find(name) == mappedGlobals.end());
     if (value.type == Type::none) {
-      value = Literal::makeZero(type);
+      value = Literal::makeSingleZero(type);
     }
     mappedGlobals.emplace(name, MappedGlobal(type));
     wasm.addGlobal(builder.makeGlobal(
diff --git a/src/dataflow/graph.h b/src/dataflow/graph.h
index 02679995b..6a984ad72 100644
--- a/src/dataflow/graph.h
+++ b/src/dataflow/graph.h
@@ -157,7 +157,9 @@ struct Graph : public UnifiedExpressionVisitor<Graph, Node*> {
     return ret;
   }
 
-  Node* makeZero(wasm::Type type) { return makeConst(Literal::makeZero(type)); }
+  Node* makeZero(wasm::Type type) {
+    return makeConst(Literal::makeSingleZero(type));
+  }
 
   // Add a new node to our list of owned nodes.
   Node* addNode(Node* node) {
diff --git a/src/ir/hashed.h b/src/ir/hashed.h
index 3068966c5..563e3abfe 100644
--- a/src/ir/hashed.h
+++ b/src/ir/hashed.h
@@ -66,7 +66,7 @@ struct FunctionHasher : public WalkerPass<PostWalker<FunctionHasher>> {
     ret = rehash(ret, (HashType)func->sig.params.getID());
     ret = rehash(ret, (HashType)func->sig.results.getID());
     for (auto type : func->vars) {
-      ret = rehash(ret, (HashType)type.getSingle());
+      ret = rehash(ret, (HashType)type.getID());
     }
     ret = rehash(ret, (HashType)ExpressionAnalyzer::hash(func->body));
     return ret;
diff --git a/src/ir/properties.h b/src/ir/properties.h
index 1dbb0e096..b14910c5b 100644
--- a/src/ir/properties.h
+++ b/src/ir/properties.h
@@ -71,7 +71,18 @@ inline bool isNamedControlFlow(Expression* curr) {
 }
 
 inline bool isConstantExpression(const Expression* curr) {
-  return curr->is<Const>() || curr->is<RefNull>() || curr->is<RefFunc>();
+  if (curr->is<Const>() || curr->is<RefNull>() || curr->is<RefFunc>()) {
+    return true;
+  }
+  if (auto* tuple = curr->dynCast<TupleMake>()) {
+    for (auto* op : tuple->operands) {
+      if (!op->is<Const>() && !op->is<RefNull>() && !op->is<RefFunc>()) {
+        return false;
+      }
+    }
+    return true;
+  }
+  return false;
 }
 
 // Check if an expression is a sign-extend, and if so, returns the value
diff --git a/src/literal.h b/src/literal.h
index 0b87cd189..df087214a 100644
--- a/src/literal.h
+++ b/src/literal.h
@@ -29,6 +29,8 @@
 
 namespace wasm {
 
+class Literals;
+
 class Literal {
   // store only integers, whose bits are deterministic. floats
   // can have their signalling bit set, for example.
@@ -44,7 +46,9 @@ public:
 
 public:
   Literal() : v128(), type(Type::none) {}
-  explicit Literal(Type type) : v128(), type(type) {}
+  explicit Literal(Type type) : v128(), type(type) {
+    assert(type != Type::unreachable);
+  }
   explicit Literal(int32_t init) : i32(init), type(Type::i32) {}
   explicit Literal(uint32_t init) : i32(init), type(Type::i32) {}
   explicit Literal(int64_t init) : i64(init), type(Type::i64) {}
@@ -62,8 +66,8 @@ public:
   explicit Literal(const std::array<Literal, 2>&);
   explicit Literal(Name func) : func(func), type(Type::funcref) {}
 
-  bool isConcrete() { return type != Type::none; }
-  bool isNone() { return type == Type::none; }
+  bool isConcrete() const { return type != Type::none; }
+  bool isNone() const { return type == Type::none; }
 
   static Literal makeFromInt32(int32_t x, Type type) {
     switch (type.getSingle()) {
@@ -95,12 +99,8 @@ public:
     WASM_UNREACHABLE("unexpected type");
   }
 
-  static Literal makeZero(Type type) {
-    if (type.isRef()) {
-      return makeNullref();
-    }
-    return makeFromInt32(0, type);
-  }
+  static Literals makeZero(Type type);
+  static Literal makeSingleZero(Type type);
 
   static Literal makeNullref() { return Literal(Type(Type::nullref)); }
   static Literal makeFuncref(Name func) { return Literal(func.c_str()); }
@@ -444,7 +444,27 @@ private:
   Literal avgrUInt(const Literal& other) const;
 };
 
-using Literals = SmallVector<Literal, 1>;
+class Literals : public SmallVector<Literal, 1> {
+public:
+  Literals() = default;
+  Literals(std::initializer_list<Literal> init)
+    : SmallVector<Literal, 1>(init) {
+#ifndef NDEBUG
+    for (auto& lit : init) {
+      assert(lit.isConcrete());
+    }
+#endif
+  };
+  Type getType() {
+    std::vector<Type> types;
+    for (auto& val : *this) {
+      types.push_back(val.type);
+    }
+    return Type(types);
+  }
+  bool isNone() { return size() == 0; }
+  bool isConcrete() { return size() != 0; }
+};
 
 std::ostream& operator<<(std::ostream& o, wasm::Literal literal);
 std::ostream& operator<<(std::ostream& o, wasm::Literals literals);
@@ -463,6 +483,15 @@ template<> struct hash<wasm::Literal> {
                         uint64_t(hash<int64_t>()(chunks[1])));
   }
 };
+template<> struct hash<wasm::Literals> {
+  size_t operator()(const wasm::Literals& a) const {
+    size_t h = wasm::rehash(uint64_t(0), uint64_t(a.size()));
+    for (const auto& lit : a) {
+      h = wasm::rehash(uint64_t(h), uint64_t(hash<wasm::Literal>{}(lit)));
+    }
+    return h;
+  }
+};
 template<> struct less<wasm::Literal> {
   bool operator()(const wasm::Literal& a, const wasm::Literal& b) const {
     if (a.type < b.type) {
diff --git a/src/passes/MemoryPacking.cpp b/src/passes/MemoryPacking.cpp
index 640207fc7..c6b8a281a 100644
--- a/src/passes/MemoryPacking.cpp
+++ b/src/passes/MemoryPacking.cpp
@@ -595,7 +595,8 @@ void MemoryPacking::createReplacements(Module* module,
 
       // Create new memory.init or memory.fill
       if (range.isZero) {
-        Expression* value = builder.makeConst(Literal::makeZero(Type::i32));
+        Expression* value =
+          builder.makeConst(Literal::makeSingleZero(Type::i32));
         appendResult(builder.makeMemoryFill(dest, value, size));
       } else {
         size_t offsetBytes = std::max(start, range.start) - range.start;
diff --git a/src/passes/Precompute.cpp b/src/passes/Precompute.cpp
index 176642fd6..0a4a691f2 100644
--- a/src/passes/Precompute.cpp
+++ b/src/passes/Precompute.cpp
@@ -47,7 +47,7 @@ static const Name NOTPRECOMPUTABLE_FLOW("Binaryen|notprecomputable");
 // helpful to avoid platform differences in native stack sizes.
 static const Index MAX_DEPTH = 50;
 
-typedef std::unordered_map<LocalGet*, Literal> GetValues;
+typedef std::unordered_map<LocalGet*, Literals> GetValues;
 
 // Precomputes an expression. Errors if we hit anything that can't be
 // precomputed.
@@ -89,9 +89,9 @@ public:
   Flow visitLocalGet(LocalGet* curr) {
     auto iter = getValues.find(curr);
     if (iter != getValues.end()) {
-      auto value = iter->second;
-      if (value.isConcrete()) {
-        return Flow(value);
+      auto values = iter->second;
+      if (values.isConcrete()) {
+        return Flow(std::move(values));
       }
     }
     return Flow(NOTPRECOMPUTABLE_FLOW);
@@ -188,10 +188,6 @@ struct Precompute
     }
     // try to evaluate this into a const
     Flow flow = precomputeExpression(curr);
-    if (flow.values.size() > 1) {
-      // TODO: handle multivalue types
-      return;
-    }
     if (flow.getType().hasVector()) {
       return;
     }
@@ -203,7 +199,7 @@ struct Precompute
         // this expression causes a return. if it's already a return, reuse the
         // node
         if (auto* ret = curr->dynCast<Return>()) {
-          if (flow.values.size() > 0) {
+          if (flow.values.isConcrete()) {
             // reuse a const value if there is one
             if (ret->value && flow.values.size() == 1) {
               if (auto* value = ret->value->dynCast<Const>()) {
@@ -219,8 +215,8 @@ struct Precompute
         } else {
           Builder builder(*getModule());
           replaceCurrent(builder.makeReturn(
-            flow.values.size() > 0 ? flow.getConstExpression(*getModule())
-                                   : nullptr));
+            flow.values.isConcrete() ? flow.getConstExpression(*getModule())
+                                     : nullptr));
         }
         return;
       }
@@ -229,7 +225,7 @@ struct Precompute
       if (auto* br = curr->dynCast<Break>()) {
         br->name = flow.breakTo;
         br->condition = nullptr;
-        if (flow.values.size() > 0) {
+        if (flow.values.isConcrete()) {
           // reuse a const value if there is one
           if (br->value && flow.values.size() == 1) {
             if (auto* value = br->value->dynCast<Const>()) {
@@ -248,13 +244,13 @@ struct Precompute
         Builder builder(*getModule());
         replaceCurrent(builder.makeBreak(
           flow.breakTo,
-          flow.values.size() > 0 ? flow.getConstExpression(*getModule())
-                                 : nullptr));
+          flow.values.isConcrete() ? flow.getConstExpression(*getModule())
+                                   : nullptr));
       }
       return;
     }
     // this was precomputed
-    if (flow.getType().isConcrete()) {
+    if (flow.values.isConcrete()) {
       replaceCurrent(flow.getConstExpression(*getModule()));
       worked = true;
     } else {
@@ -287,14 +283,14 @@ private:
   //  (local.tee (i32.const 1))
   // will have value 1 which we can optimize here, but in precomputeExpression
   // we could not do anything.
-  Literal precomputeValue(Expression* curr) {
+  Literals precomputeValue(Expression* curr) {
     // Note that we set replaceExpression to false, as we just care about
     // the value here.
     Flow flow = precomputeExpression(curr, false /* replaceExpression */);
     if (flow.breaking()) {
-      return Literal();
+      return {};
     }
-    return flow.getSingleValue();
+    return flow.values;
   }
 
   // Propagates values around. Returns whether we propagated.
@@ -315,7 +311,7 @@ private:
       work.insert(curr);
     }
     // the constant value, or none if not a constant
-    std::unordered_map<LocalSet*, Literal> setValues;
+    std::unordered_map<LocalSet*, Literals> setValues;
     // propagate constant values
     while (!work.empty()) {
       auto iter = work.begin();
@@ -328,30 +324,30 @@ private:
         if (setValues[set].isConcrete()) {
           continue; // already known constant
         }
-        auto value = setValues[set] =
+        auto values = setValues[set] =
           precomputeValue(Properties::getFallthrough(
             set->value, getPassOptions(), getModule()->features));
-        if (value.isConcrete()) {
+        if (values.isConcrete()) {
           for (auto* get : localGraph.setInfluences[set]) {
             work.insert(get);
           }
         }
       } else {
         auto* get = curr->cast<LocalGet>();
-        if (getValues[get].isConcrete()) {
+        if (getValues[get].size() >= 1) {
           continue; // already known constant
         }
         // for this get to have constant value, all sets must agree
-        Literal value;
+        Literals values;
         bool first = true;
         for (auto* set : localGraph.getSetses[get]) {
-          Literal curr;
+          Literals curr;
           if (set == nullptr) {
             if (getFunction()->isVar(get->index)) {
               curr = Literal::makeZero(getFunction()->getLocalType(get->index));
             } else {
               // it's a param, so it's hopeless
-              value = Literal();
+              values = {};
               break;
             }
           } else {
@@ -359,25 +355,25 @@ private:
           }
           if (curr.isNone()) {
             // not a constant, give up
-            value = Literal();
+            values = {};
             break;
           }
           // we found a concrete value. compare with the current one
           if (first) {
-            value = curr; // this is the first
+            values = curr; // this is the first
             first = false;
           } else {
-            if (value != curr) {
+            if (values != curr) {
               // not the same, give up
-              value = Literal();
+              values = {};
               break;
             }
           }
         }
         // we may have found a value
-        if (value.isConcrete()) {
+        if (values.isConcrete()) {
           // we did!
-          getValues[get] = value;
+          getValues[get] = values;
           for (auto* set : localGraph.getInfluences[get]) {
             work.insert(set);
           }
diff --git a/src/passes/RedundantSetElimination.cpp b/src/passes/RedundantSetElimination.cpp
index d881bd9e2..ab052853c 100644
--- a/src/passes/RedundantSetElimination.cpp
+++ b/src/passes/RedundantSetElimination.cpp
@@ -92,11 +92,13 @@ struct RedundantSetElimination
   // numbering
 
   Index nextValue = 1; // 0 is reserved for the "unseen value"
-  std::unordered_map<Literal, Index> literalValues; // each constant has a value
-  std::unordered_map<Expression*, Index>
-    expressionValues; // each value can have a value
+  // each constant has a value
+  std::unordered_map<Literals, Index> literalValues;
+  // each value can have a value
+  std::unordered_map<Expression*, Index> expressionValues;
+  // each block has values for each merge
   std::unordered_map<BasicBlock*, std::unordered_map<Index, Index>>
-    blockMergeValues; // each block has values for each merge
+    blockMergeValues;
 
   Index getUnseenValue() { // we haven't seen this location yet
     return 0;
@@ -108,7 +110,7 @@ struct RedundantSetElimination
     return nextValue++;
   }
 
-  Index getLiteralValue(Literal lit) {
+  Index getLiteralValue(Literals lit) {
     auto iter = literalValues.find(lit);
     if (iter != literalValues.end()) {
       return iter->second;
@@ -159,7 +161,7 @@ struct RedundantSetElimination
   Index getValue(Expression* value, LocalValues& currValues) {
     if (auto* c = value->dynCast<Const>()) {
       // a constant
-      return getLiteralValue(c->value);
+      return getLiteralValue({c->value});
     } else if (auto* get = value->dynCast<LocalGet>()) {
       // a copy of whatever that was
       return currValues[get->index];
diff --git a/src/tools/execution-results.h b/src/tools/execution-results.h
index 8e7371c5f..23b565082 100644
--- a/src/tools/execution-results.h
+++ b/src/tools/execution-results.h
@@ -147,7 +147,7 @@ struct ExecutionResults {
       // call the method
       for (Type param : func->sig.params.expand()) {
         // zeros in arguments TODO: more?
-        arguments.push_back(Literal::makeZero(param));
+        arguments.push_back(Literal::makeSingleZero(param));
       }
       return instance.callFunction(func->name, arguments);
     } catch (const TrapException&) {
diff --git a/src/tools/wasm-ctor-eval.cpp b/src/tools/wasm-ctor-eval.cpp
index 2d0ef1ab4..512c47396 100644
--- a/src/tools/wasm-ctor-eval.cpp
+++ b/src/tools/wasm-ctor-eval.cpp
@@ -193,12 +193,12 @@ struct CtorEvalExternalInterface : EvallingModuleInstance::ExternalInterface {
     // fill in fake values for everything else, which is dangerous to use
     ModuleUtils::iterDefinedGlobals(wasm_, [&](Global* defined) {
       if (globals.find(defined->name) == globals.end()) {
-        globals[defined->name] = Literal::makeZero(defined->type);
+        globals[defined->name] = Literal::makeSingleZero(defined->type);
       }
     });
     ModuleUtils::iterImportedGlobals(wasm_, [&](Global* import) {
       if (globals.find(import->name) == globals.end()) {
-        globals[import->name] = Literal::makeZero(import->type);
+        globals[import->name] = Literal::makeSingleZero(import->type);
       }
     });
   }
diff --git a/src/wasm-interpreter.h b/src/wasm-interpreter.h
index 2b8fa479a..9508acbfc 100644
--- a/src/wasm-interpreter.h
+++ b/src/wasm-interpreter.h
@@ -64,13 +64,7 @@ public:
     return values[0];
   }
 
-  Type getType() {
-    std::vector<Type> types;
-    for (auto& val : values) {
-      types.push_back(val.type);
-    }
-    return Type(types);
-  }
+  Type getType() { return values.getType(); }
 
   Expression* getConstExpression(Module& module) {
     assert(values.size() > 0);
@@ -1573,7 +1567,7 @@ private:
           locals[i] = arguments[i];
         } else {
           assert(function->isVar(i));
-          locals[i] = Literal::makeZero(function->getLocalType(i));
+          locals[i] = Literal::makeSingleZero(function->getLocalType(i));
         }
       }
     }
diff --git a/src/wasm/literal.cpp b/src/wasm/literal.cpp
index 1cf867cdd..aa2acdcc1 100644
--- a/src/wasm/literal.cpp
+++ b/src/wasm/literal.cpp
@@ -66,6 +66,24 @@ Literal::Literal(const LaneArray<2>& lanes) : type(Type::v128) {
   extractBytes<uint64_t, 2>(v128, lanes);
 }
 
+Literals Literal::makeZero(Type type) {
+  assert(type.isConcrete());
+  Literals zeroes;
+  for (auto t : type.expand()) {
+    zeroes.push_back(makeSingleZero(t));
+  }
+  return zeroes;
+}
+
+Literal Literal::makeSingleZero(Type type) {
+  assert(type.isSingle());
+  if (type.isRef()) {
+    return makeNullref();
+  } else {
+    return makeFromInt32(0, type);
+  }
+}
+
 std::array<uint8_t, 16> Literal::getv128() const {
   assert(type == Type::v128);
   std::array<uint8_t, 16> ret;
@@ -1483,7 +1501,7 @@ template<int Lanes, LaneArray<Lanes> (Literal::*IntoLanes)() const>
 static Literal any_true(const Literal& val) {
   LaneArray<Lanes> lanes = (val.*IntoLanes)();
   for (size_t i = 0; i < Lanes; ++i) {
-    if (lanes[i] != Literal::makeZero(lanes[i].type)) {
+    if (lanes[i] != Literal::makeSingleZero(lanes[i].type)) {
       return Literal(int32_t(1));
     }
   }
@@ -1494,7 +1512,7 @@ template<int Lanes, LaneArray<Lanes> (Literal::*IntoLanes)() const>
 static Literal all_true(const Literal& val) {
   LaneArray<Lanes> lanes = (val.*IntoLanes)();
   for (size_t i = 0; i < Lanes; ++i) {
-    if (lanes[i] == Literal::makeZero(lanes[i].type)) {
+    if (lanes[i] == Literal::makeSingleZero(lanes[i].type)) {
       return Literal(int32_t(0));
     }
   }
diff --git a/test/passes/precompute-propagate_all-features.txt b/test/passes/precompute-propagate_all-features.txt
index 5a0b7b3a5..ead4bb084 100644
--- a/test/passes/precompute-propagate_all-features.txt
+++ b/test/passes/precompute-propagate_all-features.txt
@@ -2,6 +2,7 @@
  (type $i32_=>_none (func (param i32)))
  (type $i32_=>_i32 (func (param i32) (result i32)))
  (type $i32_i32_=>_i32 (func (param i32 i32) (result i32)))
+ (type $none_=>_i32_i64 (func (result i32 i64)))
  (type $i32_i32_i32_=>_i32 (func (param i32 i32 i32) (result i32)))
  (type $none_=>_v128 (func (result v128)))
  (memory $0 10 10)
@@ -264,4 +265,24 @@
   )
   (local.get $x)
  )
+ (func $tuple-local (; 18 ;) (result i32 i64)
+  (local $i32s (i32 i32))
+  (local $i64s (i64 i64))
+  (local.set $i32s
+   (tuple.make
+    (i32.const 42)
+    (i32.const 0)
+   )
+  )
+  (local.set $i64s
+   (tuple.make
+    (i64.const 42)
+    (i64.const 0)
+   )
+  )
+  (tuple.make
+   (i32.const 42)
+   (i64.const 0)
+  )
+ )
 )
diff --git a/test/passes/precompute-propagate_all-features.wast b/test/passes/precompute-propagate_all-features.wast
index 169337fc3..f866c0ea8 100644
--- a/test/passes/precompute-propagate_all-features.wast
+++ b/test/passes/precompute-propagate_all-features.wast
@@ -175,4 +175,28 @@
    (local.set $x (v8x16.load_splat (i32.const 0)))
    (local.get $x)
   )
+  (func $tuple-local (result i32 i64)
+   (local $i32s (i32 i32))
+   (local $i64s (i64 i64))
+   (local.set $i32s
+    (tuple.make
+     (i32.const 42)
+     (i32.const 0)
+    )
+   )
+   (local.set $i64s
+    (tuple.make
+     (i64.const 42)
+     (i64.const 0)
+    )
+   )
+   (tuple.make
+    (tuple.extract 0
+     (local.get $i32s)
+    )
+    (tuple.extract 1
+     (local.get $i64s)
+    )
+   )
+  )
 )
diff --git a/test/passes/precompute_all-features.txt b/test/passes/precompute_all-features.txt
index b24c96159..4d613f06f 100644
--- a/test/passes/precompute_all-features.txt
+++ b/test/passes/precompute_all-features.txt
@@ -4,6 +4,7 @@
  (type $none_=>_f64 (func (result f64)))
  (type $none_=>_v128 (func (result v128)))
  (type $i32_=>_none (func (param i32)))
+ (type $none_=>_i32_i64 (func (result i32 i64)))
  (type $none_=>_nullref (func (result nullref)))
  (memory $0 512 512)
  (data (i32.const 0) "passive")
@@ -23,6 +24,7 @@
   (nop)
   (nop)
   (nop)
+  (nop)
   (loop $in
    (br $in)
   )
@@ -250,7 +252,13 @@
    (i32.const 12)
   )
  )
- (func $reftype-test (; 17 ;) (result nullref)
+ (func $tuple-precompute (; 17 ;) (result i32 i64)
+  (tuple.make
+   (i32.const 42)
+   (i64.const 42)
+  )
+ )
+ (func $reftype-test (; 18 ;) (result nullref)
   (ref.null)
  )
 )
diff --git a/test/passes/precompute_all-features.wast b/test/passes/precompute_all-features.wast
index 74b8f1317..da755bde6 100644
--- a/test/passes/precompute_all-features.wast
+++ b/test/passes/precompute_all-features.wast
@@ -48,6 +48,22 @@
         (i32.const 1)
       )
     )
+    (drop
+     (tuple.make
+      (tuple.extract 0
+       (tuple.make
+        (i32.const 42)
+        (i32.const 0)
+       )
+      )
+      (tuple.extract 1
+       (tuple.make
+        (i64.const 0)
+        (i64.const 42)
+       )
+      )
+     )
+    )
     (loop $in
       (br $in)
     )
@@ -344,6 +360,23 @@
     (i32.const 12)
    )
   )
+  (func $tuple-precompute (result i32 i64)
+   (tuple.make
+    (tuple.extract 0
+     (tuple.make
+      (i32.const 42)
+      (i32.const 0)
+     )
+    )
+    (tuple.extract 1
+     (tuple.make
+      (i64.const 0)
+      (i64.const 42)
+     )
+    )
+   )
+  )
+
   ;; Check if Precompute pass does not crash on reference types
   (func $reftype-test (result nullref)
     (ref.null)