Make constant expression validation stricter (#5557)

Previously we treated global.get as a constant expression and only
additionally verified that the target globals were immutable in some cases. But
global.get of a mutable global is never a constant expression, and further,
only imported globals are available in constant expressions unless GC is
enabled.

Fix constant expression validation to only allow global.get of immutable,
imported globals, and fix all the invalid tests.

6 files changed, 100 insertions, 79 deletions

diff --git a/src/ir/global-utils.h b/src/ir/global-utils.h
index ca00047a0..d5aaa9dd3 100644
--- a/src/ir/global-utils.h
+++ b/src/ir/global-utils.h
@@ -53,24 +53,16 @@ getGlobalInitializedToImport(Module& wasm, Name module, Name base) {
   return ret;
 }
 
-inline bool canInitializeGlobal(Expression* curr, FeatureSet features) {
+inline bool canInitializeGlobal(Module& wasm, Expression* curr) {
   if (auto* tuple = curr->dynCast<TupleMake>()) {
     for (auto* op : tuple->operands) {
-      if (!canInitializeGlobal(op, features)) {
+      if (!Properties::isValidConstantExpression(wasm, op)) {
         return false;
       }
     }
     return true;
   }
-  if (Properties::isValidInConstantExpression(curr, features)) {
-    for (auto* child : ChildIterator(curr)) {
-      if (!canInitializeGlobal(child, features)) {
-        return false;
-      }
-    }
-    return true;
-  }
-  return false;
+  return Properties::isValidConstantExpression(wasm, curr);
 }
 
 } // namespace wasm::GlobalUtils
diff --git a/src/ir/properties.cpp b/src/ir/properties.cpp
index 8aef0baaa..4ade8aa10 100644
--- a/src/ir/properties.cpp
+++ b/src/ir/properties.cpp
@@ -36,4 +36,54 @@ bool isGenerative(Expression* curr, FeatureSet features) {
   return scanner.generative;
 }
 
+static bool isValidInConstantExpression(Module& wasm, Expression* expr) {
+  if (isSingleConstantExpression(expr) || expr->is<StructNew>() ||
+      expr->is<ArrayNew>() || expr->is<ArrayNewFixed>() || expr->is<I31New>() ||
+      expr->is<StringConst>()) {
+    return true;
+  }
+
+  if (auto* get = expr->dynCast<GlobalGet>()) {
+    auto* g = wasm.getGlobalOrNull(get->name);
+    // This is called from the validator, so we have to handle non-existent
+    // globals gracefully.
+    if (!g) {
+      return false;
+    }
+    // Only gets of immutable globals are constant.
+    if (g->mutable_) {
+      return false;
+    }
+    // Only imported globals are available in constant expressions unless GC is
+    // enabled.
+    return g->imported() || wasm.features.hasGC();
+    // TODO: Check that there are no cycles between globals.
+  }
+
+  if (wasm.features.hasExtendedConst()) {
+    if (auto* bin = expr->dynCast<Binary>()) {
+      if (bin->op == AddInt64 || bin->op == SubInt64 || bin->op == MulInt64 ||
+          bin->op == AddInt32 || bin->op == SubInt32 || bin->op == MulInt32) {
+        return true;
+      }
+    }
+  }
+
+  return false;
+}
+
+bool isValidConstantExpression(Module& wasm, Expression* expr) {
+  struct Walker : public PostWalker<Walker, UnifiedExpressionVisitor<Walker>> {
+    bool valid = true;
+    void visitExpression(Expression* curr) {
+      if (!isValidInConstantExpression(*getModule(), curr)) {
+        valid = false;
+      }
+    }
+  } walker;
+  walker.setModule(&wasm);
+  walker.walk(expr);
+  return walker.valid;
+}
+
 } // namespace wasm::Properties
diff --git a/src/ir/properties.h b/src/ir/properties.h
index 43f74ceb8..0fee67ad2 100644
--- a/src/ir/properties.h
+++ b/src/ir/properties.h
@@ -453,26 +453,9 @@ inline bool canEmitSelectWithArms(Expression* ifTrue, Expression* ifFalse) {
 //
 bool isGenerative(Expression* curr, FeatureSet features);
 
-inline bool isValidInConstantExpression(Expression* expr, FeatureSet features) {
-  if (isSingleConstantExpression(expr) || expr->is<GlobalGet>() ||
-      expr->is<StructNew>() || expr->is<ArrayNew>() ||
-      expr->is<ArrayNewFixed>() || expr->is<I31New>() ||
-      expr->is<StringConst>()) {
-    return true;
-  }
-
-  if (features.hasExtendedConst()) {
-    if (expr->is<Binary>()) {
-      auto bin = static_cast<Binary*>(expr);
-      if (bin->op == AddInt64 || bin->op == SubInt64 || bin->op == MulInt64 ||
-          bin->op == AddInt32 || bin->op == SubInt32 || bin->op == MulInt32) {
-        return true;
-      }
-    }
-  }
-
-  return false;
-}
+// Whether this expression is valid in a context where WebAssembly requires a
+// constant expression, such as a global initializer.
+bool isValidConstantExpression(Module& wasm, Expression* expr);
 
 } // namespace wasm::Properties
 
diff --git a/src/passes/I64ToI32Lowering.cpp b/src/passes/I64ToI32Lowering.cpp
index dfcc65a51..eababc549 100644
--- a/src/passes/I64ToI32Lowering.cpp
+++ b/src/passes/I64ToI32Lowering.cpp
@@ -118,7 +118,8 @@ struct I64ToI32Lowering : public WalkerPass<PostWalker<I64ToI32Lowering>> {
       auto high = builder->makeGlobal(makeHighName(curr->name),
                                       Type::i32,
                                       builder->makeConst(int32_t(0)),
-                                      Builder::Mutable);
+                                      curr->mutable_ ? Builder::Mutable
+                                                     : Builder::Immutable);
       if (curr->imported()) {
         Fatal() << "TODO: imported i64 globals";
       } else {
diff --git a/src/passes/MultiMemoryLowering.cpp b/src/passes/MultiMemoryLowering.cpp
index 5414f2f99..08e1622d5 100644
--- a/src/passes/MultiMemoryLowering.cpp
+++ b/src/passes/MultiMemoryLowering.cpp
@@ -413,6 +413,14 @@ struct MultiMemoryLowering : public Pass {
     return offsetGlobalNames[idx - 1];
   }
 
+  size_t getInitialOffset(Index idx) {
+    if (idx == 0) {
+      return 0;
+    }
+    auto* g = wasm->getGlobal(getOffsetGlobal(idx));
+    return g->init->cast<Const>()->value.getUnsigned();
+  }
+
   // Whether the idx represents the last memory. Since there is no offset global
   // for the first memory, the last memory is represented by the size of
   // offsetGlobalNames
@@ -509,17 +517,11 @@ struct MultiMemoryLowering : public Pass {
     ModuleUtils::iterActiveDataSegments(*wasm, [&](DataSegment* dataSegment) {
       auto idx = memoryIdxMap.at(dataSegment->memory);
       dataSegment->memory = combinedMemory;
-      // No need to update the offset of data segments for the first memory
-      if (idx != 0) {
-        assert(dataSegment->offset->is<Const>() &&
-               "TODO: handle non-const segment offsets");
-        assert(wasm->features.hasExtendedConst());
-        auto offsetGlobalName = getOffsetGlobal(idx);
-        dataSegment->offset = builder.makeBinary(
-          Abstract::getBinary(pointerType, Abstract::Add),
-          builder.makeGlobalGet(offsetGlobalName, pointerType),
-          dataSegment->offset);
-      }
+      auto* offset = dataSegment->offset->dynCast<Const>();
+      assert(offset && "TODO: handle non-const segment offsets");
+      size_t originalOffset = offset->value.getUnsigned();
+      auto memOffset = getInitialOffset(idx);
+      offset->value = Literal(int32_t(originalOffset + memOffset));
     });
   }
 
diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp
index 33e737ae1..e0391a73d 100644
--- a/src/wasm/wasm-validator.cpp
+++ b/src/wasm/wasm-validator.cpp
@@ -21,6 +21,7 @@
 
 #include "ir/eh-utils.h"
 #include "ir/features.h"
+#include "ir/find_all.h"
 #include "ir/global-utils.h"
 #include "ir/intrinsics.h"
 #include "ir/local-graph.h"
@@ -3017,13 +3018,6 @@ void FunctionValidator::visitFunction(Function* curr) {
   }
 }
 
-static bool checkSegmentOffset(Expression* curr,
-                               Address add,
-                               Address max,
-                               FeatureSet features) {
-  return Properties::isValidInConstantExpression(curr, features);
-}
-
 void FunctionValidator::validateAlignment(
   size_t align, Type type, Index bytes, bool isAtomic, Expression* curr) {
   if (isAtomic) {
@@ -3235,6 +3229,7 @@ static void validateExports(Module& module, ValidationInfo& info) {
 }
 
 static void validateGlobals(Module& module, ValidationInfo& info) {
+  std::unordered_set<Global*> seen;
   ModuleUtils::iterDefinedGlobals(module, [&](Global* curr) {
     info.shouldBeTrue(curr->type.getFeatures() <= module.features,
                       curr->name,
@@ -3242,10 +3237,9 @@ static void validateGlobals(Module& module, ValidationInfo& info) {
     info.shouldBeTrue(
       curr->init != nullptr, curr->name, "global init must be non-null");
     assert(curr->init);
-    info.shouldBeTrue(
-      GlobalUtils::canInitializeGlobal(curr->init, module.features),
-      curr->name,
-      "global init must be valid");
+    info.shouldBeTrue(GlobalUtils::canInitializeGlobal(module, curr->init),
+                      curr->name,
+                      "global init must be constant");
 
     if (!info.shouldBeSubType(curr->init->type,
                               curr->type,
@@ -3255,6 +3249,18 @@ static void validateGlobals(Module& module, ValidationInfo& info) {
       info.getStream(nullptr) << "(on global " << curr->name << ")\n";
     }
     FunctionValidator(module, &info).validate(curr->init);
+    // If GC is enabled (which means globals can refer to other non-imported
+    // globals), check that globals only refer to preceeding globals.
+    if (module.features.hasGC() && curr->init) {
+      for (auto* get : FindAll<GlobalGet>(curr->init).list) {
+        auto* global = module.getGlobalOrNull(get->name);
+        info.shouldBeTrue(
+          global && (seen.count(global) || global->imported()),
+          curr->init,
+          "global initializer should only refer to previous globals");
+      }
+      seen.insert(curr);
+    }
   });
 }
 
@@ -3327,12 +3333,10 @@ static void validateDataSegments(Module& module, ValidationInfo& info) {
           continue;
         }
       }
-      info.shouldBeTrue(checkSegmentOffset(segment->offset,
-                                           segment->data.size(),
-                                           memory->initial * Memory::kPageSize,
-                                           module.features),
-                        segment->offset,
-                        "memory segment offset should be reasonable");
+      info.shouldBeTrue(
+        Properties::isValidConstantExpression(module, segment->offset),
+        segment->offset,
+        "memory segment offset should be constant");
       FunctionValidator(module, &info).validate(segment->offset);
       // If the memory is imported we don't actually know its initial size.
       // Specifically wasm dll's import a zero sized memory which is perfectly
@@ -3425,12 +3429,10 @@ static void validateTables(Module& module, ValidationInfo& info) {
                          Type(Type::i32),
                          segment->offset,
                          "element segment offset should be i32");
-      info.shouldBeTrue(checkSegmentOffset(segment->offset,
-                                           segment->data.size(),
-                                           table->initial * Table::kPageSize,
-                                           module.features),
-                        segment->offset,
-                        "table segment offset should be reasonable");
+      info.shouldBeTrue(
+        Properties::isValidConstantExpression(module, segment->offset),
+        segment->offset,
+        "table segment offset should be constant");
       info.shouldBeTrue(
         Type::isSubType(segment->type, table->type),
         "elem",
@@ -3444,22 +3446,13 @@ static void validateTables(Module& module, ValidationInfo& info) {
     // Avoid double checking items
     if (module.features.hasReferenceTypes()) {
       for (auto* expr : segment->data) {
-        if (auto* globalExpr = expr->dynCast<GlobalGet>()) {
-          auto* global = module.getGlobal(globalExpr->name);
-          info.shouldBeFalse(
-            global->mutable_, expr, "expected a constant expression");
-        } else {
-          info.shouldBeTrue(expr->is<RefFunc>() || expr->is<RefNull>() ||
-                              expr->is<GlobalGet>(),
-                            expr,
-                            "element segment items must be one of global.get, "
-                            "ref.func, ref.null func");
-        }
+        info.shouldBeTrue(Properties::isValidConstantExpression(module, expr),
+                          expr,
+                          "element must be a constant expression");
         info.shouldBeSubType(expr->type,
                              segment->type,
                              expr,
-                             "element segment item expressions must return a "
-                             "subtype of the segment type");
+                             "element must be a subtype of the segment type");
         validator.validate(expr);
       }
     }