[Wasm GC] wasm-ctor-eval: Handle cycles of data (#5685)

A cycle of data is something we can't just naively emit as wasm globals. If
at runtime we end up, for example, with an object A that refers to itself,
then we can't just emit

(global $A
  (struct.new $A
    (global.get $A)))

The struct.get is of this very global, and such a self-reference is invalid. So
we need to break such cycles as we emit them. The simple idea used here
is to find paths in the cycle that are nullable and mutable, and replace the
initial value with a null that is fixed up later in the start function:

(global $A
  (struct.new $A
    (ref.null $A)))

(func $start
  (struct.set
    (global.get $A)
    (global.get $A)))
)

This is not optimal in terms of breaking cycles, but it is fast (linear time)
and simple, and does well in practice on j2wasm (where cycles in fact
occur).

7 files changed, 1867 insertions, 67 deletions

diff --git a/src/tools/wasm-ctor-eval.cpp b/src/tools/wasm-ctor-eval.cpp
index 5e1bf6b22..a935475ff 100644
--- a/src/tools/wasm-ctor-eval.cpp
+++ b/src/tools/wasm-ctor-eval.cpp
@@ -25,6 +25,7 @@
 #include <memory>
 
 #include "asmjs/shared-constants.h"
+#include "ir/gc-type-utils.h"
 #include "ir/global-utils.h"
 #include "ir/import-utils.h"
 #include "ir/literal-utils.h"
@@ -33,8 +34,10 @@
 #include "pass.h"
 #include "support/colors.h"
 #include "support/file.h"
+#include "support/insert_ordered.h"
 #include "support/small_set.h"
 #include "support/string.h"
+#include "support/topological_sort.h"
 #include "tool-options.h"
 #include "wasm-builder.h"
 #include "wasm-interpreter.h"
@@ -50,6 +53,15 @@ struct FailToEvalException {
   FailToEvalException(std::string why) : why(why) {}
 };
 
+// Check whether a field is both nullable and mutable. This is a useful
+// property for breaking cycles of GC data, see below.
+bool isNullableAndMutable(Expression* ref, Index fieldIndex) {
+  // Find the field for the given reference, and check its properties.
+  auto field = GCTypeUtils::getField(ref->type, fieldIndex);
+  assert(field);
+  return field->type.isNullable() && field->mutable_ == Mutable;
+}
+
 // The prefix for a recommendation, so it is aligned properly with the rest of
 // the output.
 #define RECOMMENDATION "\n       recommendation: "
@@ -470,9 +482,10 @@ private:
     // each time (things live before may no longer be).
     definingGlobals.clear();
 
-    // When we start to apply the state there should be no previous state left
-    // over.
-    assert(seenDataStack.empty());
+    // Clear any startup operations as well (which may apply to globals that
+    // become no longer live; we'll create new start operations as we need
+    // them).
+    clearStartBlock();
   }
 
   void applyMemoryToModule() {
@@ -510,8 +523,6 @@ private:
   // data in the interpreter's memory can then be serialized by simply emitting
   // a global.get of that defining global.
   void applyGlobalsToModule() {
-    Builder builder(*wasm);
-
     if (!wasm->features.hasGC()) {
       // Without GC, we can simply serialize the globals in place as they are.
       for (const auto& [name, values] : instance->globals) {
@@ -528,6 +539,7 @@ private:
     // and refer to it. Put another way, we place the existing globals back into
     // the module one at a time, adding their dependencies as we go.
     auto oldGlobals = std::move(wasm->globals);
+    // After clearing the globals vector, clear the map as well.
     wasm->updateMaps();
 
     for (auto& oldGlobal : oldGlobals) {
@@ -553,21 +565,245 @@ private:
       // Add the global back to the module.
       wasm->addGlobal(std::move(oldGlobal));
     }
+
+    // Finally, we need to fix up cycles. The serialization we just emitted
+    // ignores them, so we can end up with things like this:
+    //
+    //  (global $a (struct.new $A (global.get $a)))
+    //
+    // That global refers to an object that should have a self-reference, and
+    // the serialization logic simply emits global.gets for all references, so
+    // we end up with a situation like this where a global.get refers to a
+    // global before it is valid to do so. To fix this up, we can reorder
+    // globals as needed, and break up cycles by writing a null in the initial
+    // struct.new in the global's definition, and later in the start function we
+    // can perform additional struct.sets that cause cycles to form.
+    //
+    // The existing algorithm here is rather simple: we find things that
+    // definitely force a certain order and sort according to them. Then in that
+    // order we break forward references with fixups as described above. This is
+    // not always the best, as there may be a more optimal order, and we may end
+    // up doing more fixups than are absolutely necessary, but this algorithm is
+    // simple and works in linear time (or nlogn including the sort). The
+    // general problem here is NP-hard (the maximum acyclic subgraph problem),
+    // but there are probably greedy algorithms we could consider if we need to
+    // do better.
+
+    Builder builder(*wasm);
+
+    // First, find what constraints we have on the ordering of the globals. We
+    // will build up a map of each global to the globals it must be after.
+    using MustBeAfter = InsertOrderedMap<Name, InsertOrderedSet<Name>>;
+    MustBeAfter mustBeAfter;
+
+    for (auto& global : wasm->globals) {
+      if (!global->init) {
+        continue;
+      }
+
+      struct InitScanner : PostWalker<InitScanner> {
+        // All the global.gets that we can't fix up by replacing the value with
+        // a null and adding a set in the start function. These will be hard
+        // constraints on our sorting (if we could fix things up with a null +
+        // set then we would not need to reorder).
+        InsertOrderedSet<GlobalGet*> unfixableGets;
+
+        void visitGlobalGet(GlobalGet* curr) {
+          // Assume this is unfixable, unless we reach the parent and see that
+          // it is.
+          unfixableGets.insert(curr);
+        }
+
+        // Checks if a child is a global.get that we need to handle, and if we
+        // can fix it if so. The index is the position of the child in the
+        // parent (which is 0 for all array children, as their position does not
+        // matter, they all have the same field info).
+        void handleChild(Expression* child,
+                         Expression* parent,
+                         Index fieldIndex = 0) {
+          if (!child) {
+            return;
+          }
+
+          if (auto* get = child->dynCast<GlobalGet>()) {
+            if (isNullableAndMutable(parent, fieldIndex)) {
+              // We can replace the child with a null, and set the value later
+              // (in the start function), so this is not a constraint on our
+              // sorting - we'll just fix it up later, and the order won't be
+              // an issue.
+              unfixableGets.erase(get);
+            }
+          }
+        }
+
+        void visitStructNew(StructNew* curr) {
+          Index i = 0;
+          for (auto* child : curr->operands) {
+            handleChild(child, curr, i++);
+          }
+        }
+        void visitArrayNew(ArrayNew* curr) { handleChild(curr->init, curr); }
+        void visitArrayNewFixed(ArrayNewFixed* curr) {
+          for (auto* child : curr->values) {
+            handleChild(child, curr);
+          }
+        }
+      };
+
+      InitScanner scanner;
+      scanner.walk(global->init);
+
+      // Any global.gets that cannot be fixed up are constraints.
+      for (auto* get : scanner.unfixableGets) {
+        mustBeAfter[global->name].insert(get->name);
+      }
+    }
+
+    if (!mustBeAfter.empty()) {
+      // We found constraints that require reordering, so do so.
+      struct MustBeAfterSort : TopologicalSort<Name, MustBeAfterSort> {
+        MustBeAfter& mustBeAfter;
+
+        MustBeAfterSort(MustBeAfter& mustBeAfter) : mustBeAfter(mustBeAfter) {
+          for (auto& [global, _] : mustBeAfter) {
+            push(global);
+          }
+        }
+
+        void pushPredecessors(Name global) {
+          auto iter = mustBeAfter.find(global);
+          if (iter != mustBeAfter.end()) {
+            for (auto other : iter->second) {
+              push(other);
+            }
+          }
+        }
+      };
+
+      auto oldGlobals = std::move(wasm->globals);
+      // After clearing the globals vector, clear the map as well.
+      wasm->updateMaps();
+
+      std::unordered_map<Name, Index> globalIndexes;
+      for (Index i = 0; i < oldGlobals.size(); i++) {
+        globalIndexes[oldGlobals[i]->name] = i;
+      }
+      // Add the globals that had an important ordering, in the right order.
+      for (auto global : MustBeAfterSort(mustBeAfter)) {
+        wasm->addGlobal(std::move(oldGlobals[globalIndexes[global]]));
+      }
+      // Add all other globals after them.
+      for (auto& global : oldGlobals) {
+        if (global) {
+          wasm->addGlobal(std::move(global));
+        }
+      }
+    }
+
+    // After sorting (*), perform the fixups that we need, that is, replace the
+    // relevant fields in cycles with a null and prepare a set in the start
+    // function.
+    //
+    // We'll track the set of readable globals as we go (which are the globals
+    // we've seen already, and fully finished processing).
+    //
+    // (*) Note that we may need these fixups even if we didn't need to do any
+    //     sorting. There may be a single global with a cycle in it, for
+    //     example.
+    std::unordered_set<Name> readableGlobals;
+
+    for (auto& global : wasm->globals) {
+      if (!global->init) {
+        continue;
+      }
+
+      struct InitFixer : PostWalker<InitFixer> {
+        CtorEvalExternalInterface& evaller;
+        std::unique_ptr<Global>& global;
+        std::unordered_set<Name>& readableGlobals;
+
+        InitFixer(CtorEvalExternalInterface& evaller,
+                  std::unique_ptr<Global>& global,
+                  std::unordered_set<Name>& readableGlobals)
+          : evaller(evaller), global(global), readableGlobals(readableGlobals) {
+        }
+
+        // Handles a child by fixing things up if needed. Returns true if we
+        // did in fact fix things up.
+        bool handleChild(Expression*& child,
+                         Expression* parent,
+                         Index fieldIndex = 0) {
+          if (!child) {
+            return false;
+          }
+
+          if (auto* get = child->dynCast<GlobalGet>()) {
+            if (!readableGlobals.count(get->name)) {
+              // This get cannot be read - it is a global that appears after
+              // us - and so we must fix it up, using the method mentioned
+              // before (setting it to null now, and later in the start
+              // function writing to it).
+              assert(isNullableAndMutable(parent, fieldIndex));
+              evaller.addStartFixup(
+                {global->name, global->type}, fieldIndex, get);
+              child =
+                Builder(*getModule()).makeRefNull(get->type.getHeapType());
+              return true;
+            }
+          }
+
+          return false;
+        }
+
+        // This code will need to be updated for all new GC-creating
+        // instructions that we use when serializing GC data, that is, things we
+        // put in defining globals. (All other instructions, even constant ones
+        // in globals, will simply end up referring to them using a global.get,
+        // but will not be referred to. That is, cycles will only appear in
+        // defining globals.)
+
+        void visitStructNew(StructNew* curr) {
+          Index i = 0;
+          for (auto*& child : curr->operands) {
+            handleChild(child, curr, i++);
+          }
+        }
+        void visitArrayNew(ArrayNew* curr) {
+          if (handleChild(curr->init, curr)) {
+            // Handling array.new is tricky as the number of items may be
+            // unknown at compile time, so we'd need to loop at runtime. But,
+            // in practice we emit an array.new_fixed anyhow, so this should
+            // not be needed for now.
+            WASM_UNREACHABLE("TODO: ArrayNew in ctor-eval cycles");
+          }
+        }
+        void visitArrayNewFixed(ArrayNewFixed* curr) {
+          Index i = 0;
+          for (auto*& child : curr->values) {
+            handleChild(child, curr, i++);
+          }
+        }
+      };
+
+      InitFixer fixer(*this, global, readableGlobals);
+      fixer.setModule(wasm);
+      fixer.walk(global->init);
+
+      // Only after we've fully processed this global is it ok to be read from
+      // by later globals.
+      readableGlobals.insert(global->name);
+    }
   }
 
 public:
   // Maps each GC data in the interpreter to its defining global: the global in
   // which it is created, and then all other users of it can just global.get
-  // that.
-  std::unordered_map<GCData*, Name> definingGlobals;
-
-  // The data we have seen so far on the stack. This is used to guard against
-  // infinite recursion, which would otherwise happen if there is a cycle among
-  // the live objects, which we don't handle yet.
-  //
-  // Pick a constant of 2 here to handle the common case of an object with a
-  // reference to another object that is already in a defining global.
-  SmallSet<GCData*, 2> seenDataStack;
+  // that. For each such global we track its name and type.
+  struct DefiningGlobalInfo {
+    Name name;
+    Type type;
+  };
+  std::unordered_map<GCData*, DefiningGlobalInfo> definingGlobals;
 
   // If |possibleDefiningGlobal| is provided, it is the name of a global that we
   // are in the init expression of, and which can be reused as defining global,
@@ -600,27 +836,40 @@ public:
     auto* data = value.getGCData().get();
     assert(data);
 
-    // There was actual GC data allocated here.
     auto type = value.type;
-    auto& definingGlobal = definingGlobals[data];
-    if (!definingGlobal.is()) {
-      // This is the first usage of this allocation. Generate a struct.new /
+    Name definingGlobalName;
+
+    if (auto it = definingGlobals.find(data); it != definingGlobals.end()) {
+      // Use the existing defining global.
+      definingGlobalName = it->second.name;
+    } else {
+      // This is the first usage of this data. Generate a struct.new /
       // array.new for it.
       auto& values = value.getGCData()->values;
       std::vector<Expression*> args;
 
       // The initial values for this allocation may themselves be GC
-      // allocations. Recurse and add globals as necessary.
-      // TODO: Handle cycles. That will require code in the start function. For
-      //       now, just error if we detect an infinite recursion.
-      if (seenDataStack.count(data)) {
-        Fatal() << "Cycle in live GC data, which we cannot serialize yet.";
+      // allocations. Recurse and add globals as necessary. First, pick the
+      // global name (note that we must do so first, as we may need to read from
+      // definingGlobals to find where this global will be, in the case of a
+      // cycle; see below).
+      if (possibleDefiningGlobal.is()) {
+        // No need to allocate a new global, as we are in the definition of
+        // one, which will be the defining global.
+        definingGlobals[data] =
+          DefiningGlobalInfo{possibleDefiningGlobal, type};
+        definingGlobalName = possibleDefiningGlobal;
+      } else {
+        // Allocate a new defining global.
+        definingGlobalName =
+          Names::getValidNameGivenExisting("ctor-eval$global", usedGlobalNames);
+        usedGlobalNames.insert(definingGlobalName);
+        definingGlobals[data] = DefiningGlobalInfo{definingGlobalName, type};
       }
-      seenDataStack.insert(data);
+
       for (auto& value : values) {
         args.push_back(getSerialization(value));
       }
-      seenDataStack.erase(data);
 
       Expression* init;
       auto heapType = type.getHeapType();
@@ -634,25 +883,23 @@ public:
       }
 
       if (possibleDefiningGlobal.is()) {
-        // No need to allocate a new global, as we are in the definition of
-        // one. Just return the initialization expression, which will be
-        // placed in that global's |init| field, and first note this as the
-        // defining global.
-        definingGlobal = possibleDefiningGlobal;
+        // We didn't need to allocate a new global, as we are in the definition
+        // of one, so just return the initialization expression, which will be
+        // placed in that global's |init| field.
         return init;
       }
 
-      // Allocate a new defining global.
-      auto name =
-        Names::getValidNameGivenExisting("ctor-eval$global", usedGlobalNames);
-      usedGlobalNames.insert(name);
-      wasm->addGlobal(builder.makeGlobal(name, type, init, Builder::Immutable));
-      definingGlobal = name;
+      // There is no existing defining global, so we must allocate a new one.
+      //
+      // We set the global's init to null temporarily, and we'll fix it up
+      // later down after we create the init expression.
+      wasm->addGlobal(
+        builder.makeGlobal(definingGlobalName, type, init, Builder::Immutable));
     }
 
     // Refer to this GC allocation by reading from the global that is
     // designated to contain it.
-    Expression* ret = builder.makeGlobalGet(definingGlobal, value.type);
+    Expression* ret = builder.makeGlobalGet(definingGlobalName, value.type);
     if (original != value) {
       // The original is externalized.
       assert(original.type.getHeapType() == HeapType::ext);
@@ -675,6 +922,70 @@ public:
     assert(values.size() == 1);
     return getSerialization(values[0], possibleDefiningGlobal);
   }
+
+  // This is called when we hit a cycle in setting up defining globals. For
+  // example, if the data we want to emit is
+  //
+  //    global globalA = new A{ field = &A }; // A has a reference to itself
+  //
+  // then we'll emit
+  //
+  //    global globalA = new A{ field = null };
+  //
+  // and put this in the start function:
+  //
+  //   globalA.field = globalA;
+  //
+  // The parameters here are a global and a field index to that global, and the
+  // global we want to assign to it, that is, our goal is to have
+  //
+  //  global[index] = valueGlobal
+  //
+  // run during the start function.
+  void addStartFixup(DefiningGlobalInfo global, Index index, GlobalGet* value) {
+    if (!startBlock) {
+      createStartBlock();
+    }
+
+    Builder builder(*wasm);
+    auto* getGlobal = builder.makeGlobalGet(global.name, global.type);
+
+    Expression* set;
+    if (global.type.isStruct()) {
+      set = builder.makeStructSet(index, getGlobal, value);
+    } else {
+      set = builder.makeArraySet(
+        getGlobal, builder.makeConst(int32_t(index)), value);
+    }
+
+    (*startBlock)->list.push_back(set);
+  }
+
+  // A block in the start function where we put the operations we need to occur
+  // during startup.
+  std::optional<Block*> startBlock;
+
+  void createStartBlock() {
+    Builder builder(*wasm);
+    startBlock = builder.makeBlock();
+    if (wasm->start.is()) {
+      // Put our block before any user start code.
+      auto* existingStart = wasm->getFunction(wasm->start);
+      existingStart->body =
+        builder.makeSequence(*startBlock, existingStart->body);
+    } else {
+      // Make a new start function.
+      wasm->start = Names::getValidFunctionName(*wasm, "start");
+      wasm->addFunction(builder.makeFunction(
+        wasm->start, Signature{Type::none, Type::none}, {}, *startBlock));
+    }
+  }
+
+  void clearStartBlock() {
+    if (startBlock) {
+      (*startBlock)->list.clear();
+    }
+  }
 };
 
 // Whether to emit informative logging to stdout about the eval process.
@@ -754,14 +1065,18 @@ EvalCtorOutcome evalCtor(EvallingModuleRunner& instance,
     // in a single function scope for all the executions.
     EvallingModuleRunner::FunctionScope scope(func, params, instance);
 
-    // After we successfully eval a line we will apply the changes here. This is
-    // the same idea as applyToModule() - we must only do it after an entire
-    // atomic "chunk" has been processed, we do not want partial updates from
-    // an item in the block that we only partially evalled.
-    std::vector<Literals> appliedLocals;
+    // After we successfully eval a line we will store the operations to set up
+    // the locals here. That is, we need to save the local state in the
+    // function, which we do by setting up at the entry. We update this list of
+    // local.sets at the same time as applyToModule() - we must only do it after
+    // an entire atomic "chunk" has been processed succesfully, we do not want
+    // partial updates from an item in the block that we only partially evalled.
+    std::vector<Expression*> localSets;
 
+    Builder builder(wasm);
     Literals results;
     Index successes = 0;
+
     for (auto* curr : block->list) {
       Flow flow;
       try {
@@ -780,9 +1095,25 @@ EvalCtorOutcome evalCtor(EvallingModuleRunner& instance,
         break;
       }
 
-      // So far so good! Apply the results.
+      // So far so good! Serialize the values of locals, and apply to the
+      // module. Note that we must serialize the locals now as doing so may
+      // cause changes that must be applied to the module (e.g. GC data may
+      // cause globals to be added). And we must apply to the module now, and
+      // not later, as we must do so right after a successfull partial eval
+      // (after any failure to eval, the global state is no long valid to be
+      // applied to the module, as incomplete changes may have occurred).
+      //
+      // Note that we make no effort to optimize locals: we just write out all
+      // of them, and leave it to the optimizer to remove redundant or
+      // unnecessary operations. We just recompute the entire local
+      // serialization sets from scratch each time here, for all locals.
+      localSets.clear();
+      for (Index i = 0; i < func->getNumLocals(); i++) {
+        auto value = scope.locals[i];
+        localSets.push_back(
+          builder.makeLocalSet(i, interface.getSerialization(value)));
+      }
       interface.applyToModule();
-      appliedLocals = scope.locals;
       successes++;
 
       // Note the values here, if any. If we are exiting the function now then
@@ -818,23 +1149,11 @@ EvalCtorOutcome evalCtor(EvallingModuleRunner& instance,
       wasm.getExport(exportName)->value = copyName;
 
       // Remove the items we've evalled.
-      Builder builder(wasm);
       auto* copyBlock = copyFunc->body->cast<Block>();
       for (Index i = 0; i < successes; i++) {
         copyBlock->list[i] = builder.makeNop();
       }
 
-      // Write out the values of locals, that is the local state after evalling
-      // the things we've just nopped. For simplicity we just write out all of
-      // locals, and leave it to the optimizer to remove redundant or
-      // unnecessary operations.
-      std::vector<Expression*> localSets;
-      for (Index i = 0; i < copyFunc->getNumLocals(); i++) {
-        auto value = appliedLocals[i];
-        localSets.push_back(
-          builder.makeLocalSet(i, interface.getSerialization(value)));
-      }
-
       // Put the local sets at the front of the block. We know there must be a
       // nop in that position (since we've evalled at least one item in the
       // block, and replaced it with a nop), so we can overwrite it.
diff --git a/src/wasm/literal.cpp b/src/wasm/literal.cpp
index 230eeae66..53740c773 100644
--- a/src/wasm/literal.cpp
+++ b/src/wasm/literal.cpp
@@ -618,6 +618,7 @@ std::ostream& operator<<(std::ostream& o, Literal literal) {
       assert(literal.isData());
       auto data = literal.getGCData();
       assert(data);
+      // TODO: infinite recursion is possible here, if the data is cyclic
       o << "[ref " << data->type << ' ' << data->values << ']';
     }
   }
diff --git a/test/ctor-eval/gc-2.wast.out b/test/ctor-eval/gc-2.wast.out
index 5d91ca7d3..370faec16 100644
--- a/test/ctor-eval/gc-2.wast.out
+++ b/test/ctor-eval/gc-2.wast.out
@@ -1,15 +1,15 @@
 (module
  (type $struct (struct (field i32)))
  (type $none_=>_i32 (func (result i32)))
- (global $ctor-eval$global (ref $struct) (struct.new $struct
-  (i32.const 1337)
- ))
- (global $global1 (ref any) (global.get $ctor-eval$global))
  (global $ctor-eval$global_4 (ref $struct) (struct.new $struct
   (i32.const 9999)
  ))
- (global $global2 (mut (ref null $struct)) (global.get $ctor-eval$global_4))
  (global $global3 (ref $struct) (global.get $ctor-eval$global_4))
+ (global $global2 (mut (ref null $struct)) (global.get $ctor-eval$global_4))
+ (global $ctor-eval$global (ref $struct) (struct.new $struct
+  (i32.const 1337)
+ ))
+ (global $global1 (ref any) (global.get $ctor-eval$global))
  (export "keepalive" (func $1))
  (func $1 (type $none_=>_i32) (result i32)
   (select
diff --git a/test/ctor-eval/gc.wast.out b/test/ctor-eval/gc.wast.out
index 2995f84ba..3d99199be 100644
--- a/test/ctor-eval/gc.wast.out
+++ b/test/ctor-eval/gc.wast.out
@@ -4,14 +4,14 @@
  (type $none_=>_i32 (func (result i32)))
  (type $none_=>_none (func))
  (import "import" "import" (func $import (param anyref)))
+ (global $ctor-eval$global_5 (ref $struct) (struct.new $struct
+  (i32.const 42)
+ ))
+ (global $global2 (mut (ref null $struct)) (global.get $ctor-eval$global_5))
  (global $global1 (ref $struct) (struct.new $struct
   (i32.const 1337)
  ))
  (global $ctor-eval$global_4 (ref $struct) (struct.new $struct
-  (i32.const 42)
- ))
- (global $global2 (mut (ref null $struct)) (global.get $ctor-eval$global_4))
- (global $ctor-eval$global_5 (ref $struct) (struct.new $struct
   (i32.const 99)
  ))
  (export "test1" (func $0_3))
@@ -29,7 +29,7 @@
  (func $0_3 (type $none_=>_none)
   (local $0 (ref $struct))
   (local.set $0
-   (global.get $ctor-eval$global_5)
+   (global.get $ctor-eval$global_4)
   )
   (call $import
    (ref.null none)
diff --git a/test/lit/ctor-eval/gc-cycle-multi.wast b/test/lit/ctor-eval/gc-cycle-multi.wast
new file mode 100644
index 000000000..62a888dbd
--- /dev/null
+++ b/test/lit/ctor-eval/gc-cycle-multi.wast
@@ -0,0 +1,144 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+;; RUN: foreach %s %t wasm-ctor-eval --ctors=test1,test2,test3 --kept-exports=test1,test2,test3 --quiet -all -S -o - | filecheck %s
+
+;; Similar to gc-cycle.wast, but now there are three exported ctors that we
+;; call.
+
+(module
+ ;; Multiple independent cycles.
+ ;; CHECK:      (type $A (struct (field (mut (ref null $A))) (field i32)))
+ (type $A (struct (field (mut (ref null $A))) (field i32)))
+
+ ;; CHECK:      (type $none_=>_none (func))
+
+ ;; CHECK:      (type $none_=>_i32 (func (result i32)))
+
+ ;; CHECK:      (global $ctor-eval$global_8 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (i32.const 30)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $c (mut (ref null $A)) (global.get $ctor-eval$global_8))
+
+ ;; CHECK:      (global $ctor-eval$global_7 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (i32.const 10)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $a (mut (ref null $A)) (global.get $ctor-eval$global_7))
+ (global $a (mut (ref null $A)) (ref.null $A))
+ ;; CHECK:      (global $ctor-eval$global_6 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (i32.const 20)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $b (mut (ref null $A)) (global.get $ctor-eval$global_6))
+ (global $b (mut (ref null $A)) (ref.null $A))
+ (global $c (mut (ref null $A)) (ref.null $A))
+
+ (func $makeCycle (param $i i32) (result (ref $A))
+  (local $x (ref $A))
+  (local.set $x
+   (struct.new $A
+    (ref.null $A)
+    (local.get $i)
+   )
+  )
+  (struct.set $A 0
+   (local.get $x)
+   (local.get $x)
+  )
+  (local.get $x)
+ )
+
+ (func $test1 (export "test1")
+  (global.set $a
+   (call $makeCycle
+    (i32.const 10)
+   )
+  )
+ )
+
+ (func $test2 (export "test2")
+  (global.set $b
+   (call $makeCycle
+    (i32.const 20)
+   )
+  )
+ )
+
+ (func $test3 (export "test3")
+  (global.set $c
+   (call $makeCycle
+    (i32.const 30)
+   )
+  )
+ )
+
+ ;; CHECK:      (export "test1" (func $test1_6))
+
+ ;; CHECK:      (export "test2" (func $test2_7))
+
+ ;; CHECK:      (export "test3" (func $test3_8))
+
+ ;; CHECK:      (export "keepalive" (func $keepalive))
+
+ ;; CHECK:      (start $start)
+
+ ;; CHECK:      (func $keepalive (type $none_=>_i32) (result i32)
+ ;; CHECK-NEXT:  (i32.add
+ ;; CHECK-NEXT:   (struct.get $A 1
+ ;; CHECK-NEXT:    (global.get $a)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (i32.add
+ ;; CHECK-NEXT:    (struct.get $A 1
+ ;; CHECK-NEXT:     (global.get $b)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:    (struct.get $A 1
+ ;; CHECK-NEXT:     (global.get $c)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $keepalive (export "keepalive") (result i32)
+  (i32.add
+   (struct.get $A 1
+    (global.get $a)
+   )
+   (i32.add
+    (struct.get $A 1
+     (global.get $b)
+    )
+    (struct.get $A 1
+     (global.get $c)
+    )
+   )
+  )
+ )
+)
+;; CHECK:      (func $start (type $none_=>_none)
+;; CHECK-NEXT:  (struct.set $A 0
+;; CHECK-NEXT:   (global.get $ctor-eval$global_8)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_8)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (struct.set $A 0
+;; CHECK-NEXT:   (global.get $ctor-eval$global_7)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_7)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (struct.set $A 0
+;; CHECK-NEXT:   (global.get $ctor-eval$global_6)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_6)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $test1_6 (type $none_=>_none)
+;; CHECK-NEXT:  (nop)
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $test2_7 (type $none_=>_none)
+;; CHECK-NEXT:  (nop)
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $test3_8 (type $none_=>_none)
+;; CHECK-NEXT:  (nop)
+;; CHECK-NEXT: )
diff --git a/test/lit/ctor-eval/gc-cycle.wast b/test/lit/ctor-eval/gc-cycle.wast
new file mode 100644
index 000000000..a6edc28aa
--- /dev/null
+++ b/test/lit/ctor-eval/gc-cycle.wast
@@ -0,0 +1,1297 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+;; RUN: foreach %s %t wasm-ctor-eval --ctors=test --kept-exports=test --quiet -all -S -o - | filecheck %s
+
+(module
+ ;; CHECK:      (type $A (struct (field (mut (ref null $A))) (field i32)))
+ (type $A (struct (field (mut (ref null $A))) (field i32)))
+
+ ;; CHECK:      (type $none_=>_none (func))
+
+ ;; CHECK:      (type $none_=>_i32 (func (result i32)))
+
+ ;; CHECK:      (global $ctor-eval$global_3 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (i32.const 42)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $a (mut (ref null $A)) (global.get $ctor-eval$global_3))
+ (global $a (mut (ref null $A)) (ref.null $A))
+
+ (func $test (export "test")
+  (local $a (ref $A))
+  ;; This generates a self-cycle where the global $a's ref field points to
+  ;; itself. To handle this, wasm-ctor-eval will emit a new global with a null
+  ;; in the ref field, and add a start function that adds the self-reference.
+  (global.set $a
+   (local.tee $a
+    (struct.new $A
+     (ref.null $A)
+     (i32.const 42)
+    )
+   )
+  )
+  (struct.set $A 0
+   (local.get $a)
+   (local.get $a)
+  )
+ )
+
+ ;; CHECK:      (export "test" (func $test_3))
+
+ ;; CHECK:      (export "keepalive" (func $keepalive))
+
+ ;; CHECK:      (start $start)
+
+ ;; CHECK:      (func $keepalive (type $none_=>_i32) (result i32)
+ ;; CHECK-NEXT:  (struct.get $A 1
+ ;; CHECK-NEXT:   (struct.get $A 0
+ ;; CHECK-NEXT:    (global.get $a)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $keepalive (export "keepalive") (result i32)
+  ;; Getting $A.0.1 (reading from the reference in the global's first field)
+  ;; checks that we have a proper reference there. If we could do --fuzz-exec
+  ;; here we could validate that (but atm we can't use --output=fuzz-exec at the
+  ;; same time as --all-items in the update_lit_checks.py note).
+  (struct.get $A 1
+   (struct.get $A 0
+    (global.get $a)
+   )
+  )
+ )
+)
+
+;; CHECK:      (func $start (type $none_=>_none)
+;; CHECK-NEXT:  (struct.set $A 0
+;; CHECK-NEXT:   (global.get $ctor-eval$global_3)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_3)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $test_3 (type $none_=>_none)
+;; CHECK-NEXT:  (local $a (ref $A))
+;; CHECK-NEXT:  (nop)
+;; CHECK-NEXT: )
+(module
+ ;; As above, but with $A's fields reversed. This verifies we use the right
+ ;; field index in the start function.
+
+ ;; CHECK:      (type $A (struct (field i32) (field (mut (ref null $A)))))
+ (type $A (struct (field i32) (field (mut (ref null $A)))))
+
+ ;; CHECK:      (type $none_=>_none (func))
+
+ ;; CHECK:      (type $none_=>_i32 (func (result i32)))
+
+ ;; CHECK:      (global $ctor-eval$global_3 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (i32.const 42)
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $a (mut (ref null $A)) (global.get $ctor-eval$global_3))
+ (global $a (mut (ref null $A)) (ref.null $A))
+
+ (func $test (export "test")
+  (local $a (ref $A))
+  (global.set $a
+   (local.tee $a
+    (struct.new $A
+     (i32.const 42)
+     (ref.null $A)
+    )
+   )
+  )
+  (struct.set $A 1
+   (local.get $a)
+   (local.get $a)
+  )
+ )
+
+ ;; CHECK:      (export "test" (func $test_3))
+
+ ;; CHECK:      (export "keepalive" (func $keepalive))
+
+ ;; CHECK:      (start $start)
+
+ ;; CHECK:      (func $keepalive (type $none_=>_i32) (result i32)
+ ;; CHECK-NEXT:  (struct.get $A 0
+ ;; CHECK-NEXT:   (struct.get $A 1
+ ;; CHECK-NEXT:    (global.get $a)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $keepalive (export "keepalive") (result i32)
+  (struct.get $A 0
+   (struct.get $A 1
+    (global.get $a)
+   )
+  )
+ )
+)
+
+;; CHECK:      (func $start (type $none_=>_none)
+;; CHECK-NEXT:  (struct.set $A 1
+;; CHECK-NEXT:   (global.get $ctor-eval$global_3)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_3)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $test_3 (type $none_=>_none)
+;; CHECK-NEXT:  (local $a (ref $A))
+;; CHECK-NEXT:  (nop)
+;; CHECK-NEXT: )
+(module
+ ;; A cycle between two globals.
+
+ ;; CHECK:      (type $A (struct (field (mut (ref null $A))) (field i32)))
+ (type $A (struct (field (mut (ref null $A))) (field i32)))
+
+ ;; CHECK:      (type $none_=>_none (func))
+
+ ;; CHECK:      (type $none_=>_i32 (func (result i32)))
+
+ ;; CHECK:      (global $ctor-eval$global_8 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (i32.const 42)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $a (mut (ref null $A)) (global.get $ctor-eval$global_8))
+ (global $a (mut (ref null $A)) (ref.null $A))
+
+ ;; CHECK:      (global $ctor-eval$global_7 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_8)
+ ;; CHECK-NEXT:  (i32.const 1337)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $b (mut (ref null $A)) (global.get $ctor-eval$global_7))
+ (global $b (mut (ref null $A)) (ref.null $A))
+
+ (func $test (export "test")
+  (local $a (ref $A))
+  (local $b (ref $A))
+  (global.set $a
+   (local.tee $a
+    (struct.new $A
+     (ref.null $A)
+     (i32.const 42)
+    )
+   )
+  )
+  (global.set $b
+   (local.tee $b
+    (struct.new $A
+     (global.get $a)  ;; $b can refer to $a since we've created $a already.
+     (i32.const 1337)
+    )
+   )
+  )
+  ;; $a needs a set to allow us to create the cycle.
+  (struct.set $A 0
+   (local.get $a)
+   (local.get $b)
+  )
+ )
+
+ ;; CHECK:      (export "test" (func $test_3))
+
+ ;; CHECK:      (export "keepalive" (func $keepalive))
+
+ ;; CHECK:      (start $start)
+
+ ;; CHECK:      (func $keepalive (type $none_=>_i32) (result i32)
+ ;; CHECK-NEXT:  (i32.add
+ ;; CHECK-NEXT:   (struct.get $A 1
+ ;; CHECK-NEXT:    (global.get $a)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (struct.get $A 1
+ ;; CHECK-NEXT:    (global.get $b)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $keepalive (export "keepalive") (result i32)
+  (i32.add
+   (struct.get $A 1
+    (global.get $a)
+   )
+   (struct.get $A 1
+    (global.get $b)
+   )
+  )
+ )
+)
+
+;; CHECK:      (func $start (type $none_=>_none)
+;; CHECK-NEXT:  (struct.set $A 0
+;; CHECK-NEXT:   (global.get $ctor-eval$global_8)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_7)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $test_3 (type $none_=>_none)
+;; CHECK-NEXT:  (local $a (ref $A))
+;; CHECK-NEXT:  (local $b (ref $A))
+;; CHECK-NEXT:  (nop)
+;; CHECK-NEXT: )
+(module
+ ;; A cycle between two globals of different types. One of them has an
+ ;; immutable field in the cycle.
+
+ (rec
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $A (struct (field (mut (ref null $B))) (field i32)))
+  (type $A (struct (field (mut (ref null $B))) (field i32)))
+
+  ;; CHECK:       (type $B (struct (field (ref null $A)) (field i32)))
+  (type $B (struct (field (ref null $A)) (field i32)))
+ )
+
+ ;; CHECK:      (type $none_=>_none (func))
+
+ ;; CHECK:      (type $none_=>_i32 (func (result i32)))
+
+ ;; CHECK:      (global $ctor-eval$global_8 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (i32.const 42)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $a (mut (ref null $A)) (global.get $ctor-eval$global_8))
+ (global $a (mut (ref null $A)) (ref.null $A))
+
+ ;; CHECK:      (global $ctor-eval$global_7 (ref $B) (struct.new $B
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_8)
+ ;; CHECK-NEXT:  (i32.const 1337)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $b (mut (ref null $B)) (global.get $ctor-eval$global_7))
+ (global $b (mut (ref null $B)) (ref.null $B))
+
+ (func $test (export "test")
+  (local $a (ref $A))
+  (local $b (ref $B))
+  (global.set $a
+   (local.tee $a
+    (struct.new $A
+     (ref.null $A)
+     (i32.const 42)
+    )
+   )
+  )
+  (global.set $b
+   (local.tee $b
+    (struct.new $B
+     (global.get $a)
+     (i32.const 1337)
+    )
+   )
+  )
+  (struct.set $A 0
+   (local.get $a)
+   (local.get $b)
+  )
+ )
+
+ ;; CHECK:      (export "test" (func $test_3))
+
+ ;; CHECK:      (export "keepalive" (func $keepalive))
+
+ ;; CHECK:      (start $start)
+
+ ;; CHECK:      (func $keepalive (type $none_=>_i32) (result i32)
+ ;; CHECK-NEXT:  (i32.add
+ ;; CHECK-NEXT:   (struct.get $A 1
+ ;; CHECK-NEXT:    (global.get $a)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (struct.get $B 1
+ ;; CHECK-NEXT:    (global.get $b)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $keepalive (export "keepalive") (result i32)
+  (i32.add
+   (struct.get $A 1
+    (global.get $a)
+   )
+   (struct.get $B 1
+    (global.get $b)
+   )
+  )
+ )
+)
+
+;; CHECK:      (func $start (type $none_=>_none)
+;; CHECK-NEXT:  (struct.set $A 0
+;; CHECK-NEXT:   (global.get $ctor-eval$global_8)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_7)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $test_3 (type $none_=>_none)
+;; CHECK-NEXT:  (local $a (ref $A))
+;; CHECK-NEXT:  (local $b (ref $B))
+;; CHECK-NEXT:  (nop)
+;; CHECK-NEXT: )
+(module
+ ;; As above, but with the order of globals reversed.
+
+ (rec
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $A (struct (field (mut (ref null $B))) (field i32)))
+  (type $A (struct (field (mut (ref null $B))) (field i32)))
+
+  ;; CHECK:       (type $B (struct (field (ref null $A)) (field i32)))
+  (type $B (struct (field (ref null $A)) (field i32)))
+ )
+
+
+ ;; CHECK:      (type $none_=>_none (func))
+
+ ;; CHECK:      (type $none_=>_i32 (func (result i32)))
+
+ ;; CHECK:      (global $ctor-eval$global_8 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (i32.const 42)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $a (mut (ref null $A)) (global.get $ctor-eval$global_8))
+
+ ;; CHECK:      (global $ctor-eval$global_7 (ref $B) (struct.new $B
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_8)
+ ;; CHECK-NEXT:  (i32.const 1337)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $b (mut (ref null $B)) (global.get $ctor-eval$global_7))
+ (global $b (mut (ref null $B)) (ref.null $B))
+
+ (global $a (mut (ref null $A)) (ref.null $A))
+
+ (func $test (export "test")
+  (local $a (ref $A))
+  (local $b (ref $B))
+  (global.set $a
+   (local.tee $a
+    (struct.new $A
+     (ref.null $A)
+     (i32.const 42)
+    )
+   )
+  )
+  (global.set $b
+   (local.tee $b
+    (struct.new $B
+     (global.get $a)
+     (i32.const 1337)
+    )
+   )
+  )
+  (struct.set $A 0
+   (local.get $a)
+   (local.get $b)
+  )
+ )
+
+ ;; CHECK:      (export "test" (func $test_3))
+
+ ;; CHECK:      (export "keepalive" (func $keepalive))
+
+ ;; CHECK:      (start $start)
+
+ ;; CHECK:      (func $keepalive (type $none_=>_i32) (result i32)
+ ;; CHECK-NEXT:  (i32.add
+ ;; CHECK-NEXT:   (struct.get $A 1
+ ;; CHECK-NEXT:    (global.get $a)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (struct.get $B 1
+ ;; CHECK-NEXT:    (global.get $b)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $keepalive (export "keepalive") (result i32)
+  (i32.add
+   (struct.get $A 1
+    (global.get $a)
+   )
+   (struct.get $B 1
+    (global.get $b)
+   )
+  )
+ )
+)
+
+;; CHECK:      (func $start (type $none_=>_none)
+;; CHECK-NEXT:  (struct.set $A 0
+;; CHECK-NEXT:   (global.get $ctor-eval$global_8)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_7)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $test_3 (type $none_=>_none)
+;; CHECK-NEXT:  (local $a (ref $A))
+;; CHECK-NEXT:  (local $b (ref $B))
+;; CHECK-NEXT:  (nop)
+;; CHECK-NEXT: )
+(module
+  ;; A cycle as above, but with non-nullability rather than immutability.
+
+ (rec
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $A (struct (field (mut (ref null $B))) (field i32)))
+  (type $A (struct (field (mut (ref null $B))) (field i32)))
+
+  ;; CHECK:       (type $B (struct (field (mut (ref $A))) (field i32)))
+  (type $B (struct (field (mut (ref $A))) (field i32)))
+ )
+
+ ;; CHECK:      (type $none_=>_none (func))
+
+ ;; CHECK:      (type $none_=>_i32 (func (result i32)))
+
+ ;; CHECK:      (global $ctor-eval$global_8 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (i32.const 42)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $a (mut (ref null $A)) (global.get $ctor-eval$global_8))
+ (global $a (mut (ref null $A)) (ref.null $A))
+
+ (global $b (mut (ref null $B)) (ref.null $B))
+
+ (func $test (export "test")
+  (local $a (ref $A))
+  (local $b (ref $B))
+  (global.set $a
+   (local.tee $a
+    (struct.new $A
+     (ref.null $A)
+     (i32.const 42)
+    )
+   )
+  )
+  (global.set $b
+   (local.tee $b
+    (struct.new $B
+     (local.get $a)
+     (i32.const 1337)
+    )
+   )
+  )
+  (struct.set $A 0
+   (local.get $a)
+   (local.get $b)
+  )
+ )
+
+ ;; CHECK:      (global $ctor-eval$global_7 (ref $B) (struct.new $B
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_8)
+ ;; CHECK-NEXT:  (i32.const 1337)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (export "test" (func $test_3))
+
+ ;; CHECK:      (export "keepalive" (func $keepalive))
+
+ ;; CHECK:      (start $start)
+
+ ;; CHECK:      (func $keepalive (type $none_=>_i32) (result i32)
+ ;; CHECK-NEXT:  (struct.get $A 1
+ ;; CHECK-NEXT:   (global.get $a)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $keepalive (export "keepalive") (result i32)
+  (struct.get $A 1
+   (global.get $a)
+  )
+ )
+)
+
+;; CHECK:      (func $start (type $none_=>_none)
+;; CHECK-NEXT:  (struct.set $A 0
+;; CHECK-NEXT:   (global.get $ctor-eval$global_8)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_7)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $test_3 (type $none_=>_none)
+;; CHECK-NEXT:  (local $a (ref $A))
+;; CHECK-NEXT:  (local $b (ref $B))
+;; CHECK-NEXT:  (nop)
+;; CHECK-NEXT: )
+(module
+  ;; A cycle as above, but with globals in reverse order and with both non-
+  ;; nullability and immutability.
+
+ (rec
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $A (struct (field (mut (ref null $B))) (field i32)))
+  (type $A (struct (field (mut (ref null $B))) (field i32)))
+
+  ;; CHECK:       (type $B (struct (field (ref $A)) (field i32)))
+  (type $B (struct (field (ref $A)) (field i32)))
+ )
+
+
+ (global $b (mut (ref null $B)) (ref.null $B))
+
+ ;; CHECK:      (type $none_=>_none (func))
+
+ ;; CHECK:      (type $none_=>_i32 (func (result i32)))
+
+ ;; CHECK:      (global $ctor-eval$global_8 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (i32.const 42)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $a (mut (ref null $A)) (global.get $ctor-eval$global_8))
+ (global $a (mut (ref null $A)) (ref.null $A))
+
+ (func $test (export "test")
+  (local $a (ref $A))
+  (local $b (ref $B))
+  (global.set $a
+   (local.tee $a
+    (struct.new $A
+     (ref.null $A)
+     (i32.const 42)
+    )
+   )
+  )
+  (global.set $b
+   (local.tee $b
+    (struct.new $B
+     (local.get $a)
+     (i32.const 1337)
+    )
+   )
+  )
+  (struct.set $A 0
+   (local.get $a)
+   (local.get $b)
+  )
+ )
+
+ ;; CHECK:      (global $ctor-eval$global_7 (ref $B) (struct.new $B
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_8)
+ ;; CHECK-NEXT:  (i32.const 1337)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (export "test" (func $test_3))
+
+ ;; CHECK:      (export "keepalive" (func $keepalive))
+
+ ;; CHECK:      (start $start)
+
+ ;; CHECK:      (func $keepalive (type $none_=>_i32) (result i32)
+ ;; CHECK-NEXT:  (struct.get $A 1
+ ;; CHECK-NEXT:   (global.get $a)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $keepalive (export "keepalive") (result i32)
+  (struct.get $A 1
+   (global.get $a)
+  )
+ )
+)
+
+;; CHECK:      (func $start (type $none_=>_none)
+;; CHECK-NEXT:  (struct.set $A 0
+;; CHECK-NEXT:   (global.get $ctor-eval$global_8)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_7)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $test_3 (type $none_=>_none)
+;; CHECK-NEXT:  (local $a (ref $A))
+;; CHECK-NEXT:  (local $b (ref $B))
+;; CHECK-NEXT:  (nop)
+;; CHECK-NEXT: )
+(module
+ ;; A cycle between three globals.
+
+ ;; CHECK:      (type $A (struct (field (mut (ref null $A))) (field i32)))
+ (type $A (struct (field (mut (ref null $A))) (field i32)))
+
+ ;; CHECK:      (type $none_=>_none (func))
+
+ ;; CHECK:      (type $none_=>_i32 (func (result i32)))
+
+ ;; CHECK:      (global $ctor-eval$global_13 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (i32.const 1337)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $ctor-eval$global_14 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (i32.const 42)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $a (mut (ref null $A)) (global.get $ctor-eval$global_14))
+ (global $a (mut (ref null $A)) (ref.null $A))
+
+ (global $b (mut (ref null $A)) (ref.null $A))
+
+ (global $c (mut (ref null $A)) (ref.null $A))
+
+ (func $test (export "test")
+  (local $a (ref $A))
+  (local $b (ref $A))
+  (local $c (ref $A))
+  (global.set $a
+   (local.tee $a
+    (struct.new $A
+     (ref.null $A)
+     (i32.const 42)
+    )
+   )
+  )
+  (global.set $b
+   (local.tee $b
+    (struct.new $A
+     (global.get $a)
+     (i32.const 1337)
+    )
+   )
+  )
+  (global.set $c
+   (local.tee $c
+    (struct.new $A
+     (global.get $b)
+     (i32.const 99999)
+    )
+   )
+  )
+  (struct.set $A 0
+   (local.get $a)
+   (local.get $c)
+  )
+ )
+
+ ;; CHECK:      (global $ctor-eval$global_12 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_13)
+ ;; CHECK-NEXT:  (i32.const 99999)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (export "test" (func $test_3))
+
+ ;; CHECK:      (export "keepalive" (func $keepalive))
+
+ ;; CHECK:      (start $start)
+
+ ;; CHECK:      (func $keepalive (type $none_=>_i32) (result i32)
+ ;; CHECK-NEXT:  (struct.get $A 1
+ ;; CHECK-NEXT:   (global.get $a)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $keepalive (export "keepalive") (result i32)
+  (struct.get $A 1
+   (global.get $a)
+  )
+ )
+)
+
+;; CHECK:      (func $start (type $none_=>_none)
+;; CHECK-NEXT:  (struct.set $A 0
+;; CHECK-NEXT:   (global.get $ctor-eval$global_13)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_14)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (struct.set $A 0
+;; CHECK-NEXT:   (global.get $ctor-eval$global_14)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_12)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $test_3 (type $none_=>_none)
+;; CHECK-NEXT:  (local $a (ref $A))
+;; CHECK-NEXT:  (local $b (ref $A))
+;; CHECK-NEXT:  (local $c (ref $A))
+;; CHECK-NEXT:  (nop)
+;; CHECK-NEXT: )
+(module
+ ;; A cycle between three globals as above, but now using different types and
+ ;; also both structs and arrays. Also reverse the order of globals, make
+ ;; one array immutable and one non-nullable, and make one array refer to the
+ ;; other two.
+
+ (rec
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $A (struct (field (mut (ref null $C))) (field i32)))
+  (type $A (struct (field (mut (ref null $C))) (field i32)))
+  ;; CHECK:       (type $B (array (ref null $A)))
+  (type $B (array (ref null $A)))
+  ;; CHECK:       (type $C (array (mut (ref any))))
+  (type $C (array (mut (ref any))))
+ )
+
+ (global $c (mut (ref null $C)) (ref.null $C))
+
+ (global $b (mut (ref null $B)) (ref.null $B))
+
+ ;; CHECK:      (type $none_=>_none (func))
+
+ ;; CHECK:      (type $none_=>_i32 (func (result i32)))
+
+ ;; CHECK:      (global $ctor-eval$global_14 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (i32.const 42)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $ctor-eval$global_13 (ref $B) (array.new_fixed $B
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $a (mut (ref null $A)) (global.get $ctor-eval$global_14))
+ (global $a (mut (ref null $A)) (ref.null $A))
+
+ (func $test (export "test")
+  (local $a (ref $A))
+  (local $b (ref $B))
+  (local $c (ref $C))
+  (global.set $a
+   (local.tee $a
+    (struct.new $A
+     (ref.null $C)
+     (i32.const 42)
+    )
+   )
+  )
+  (global.set $b
+   (local.tee $b
+    (array.new $B
+     (global.get $a)
+     (i32.const 10)
+    )
+   )
+  )
+  (global.set $c
+   (local.tee $c
+    (array.new_fixed $C
+     (local.get $b)
+     (local.get $a)
+    )
+   )
+  )
+  (struct.set $A 0
+   (local.get $a)
+   (global.get $c)
+  )
+ )
+
+ ;; CHECK:      (global $ctor-eval$global_12 (ref $C) (array.new_fixed $C
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_13)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (export "test" (func $test_3))
+
+ ;; CHECK:      (export "keepalive" (func $keepalive))
+
+ ;; CHECK:      (start $start)
+
+ ;; CHECK:      (func $keepalive (type $none_=>_i32) (result i32)
+ ;; CHECK-NEXT:  (struct.get $A 1
+ ;; CHECK-NEXT:   (global.get $a)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $keepalive (export "keepalive") (result i32)
+  (struct.get $A 1
+   (global.get $a)
+  )
+ )
+)
+
+;; CHECK:      (func $start (type $none_=>_none)
+;; CHECK-NEXT:  (struct.set $A 0
+;; CHECK-NEXT:   (global.get $ctor-eval$global_14)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_12)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $test_3 (type $none_=>_none)
+;; CHECK-NEXT:  (local $a (ref $A))
+;; CHECK-NEXT:  (local $b (ref $B))
+;; CHECK-NEXT:  (local $c (ref $C))
+;; CHECK-NEXT:  (nop)
+;; CHECK-NEXT: )
+(module
+ ;; As above but with the order of globals reversed once more.
+
+ (rec
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $A (struct (field (mut (ref null $C))) (field i32)))
+  (type $A (struct (field (mut (ref null $C))) (field i32)))
+  ;; CHECK:       (type $B (array (ref null $A)))
+  (type $B (array (ref null $A)))
+  ;; CHECK:       (type $C (array (mut (ref any))))
+  (type $C (array (mut (ref any))))
+ )
+
+ ;; CHECK:      (type $none_=>_none (func))
+
+ ;; CHECK:      (type $none_=>_i32 (func (result i32)))
+
+ ;; CHECK:      (global $ctor-eval$global_14 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (i32.const 42)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $ctor-eval$global_13 (ref $B) (array.new_fixed $B
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $a (mut (ref null $A)) (global.get $ctor-eval$global_14))
+ (global $a (mut (ref null $A)) (ref.null $A))
+
+ (global $b (mut (ref null $B)) (ref.null $B))
+
+ (global $c (mut (ref null $C)) (ref.null $C))
+
+ (func $test (export "test")
+  (local $a (ref $A))
+  (local $b (ref $B))
+  (local $c (ref $C))
+  (global.set $a
+   (local.tee $a
+    (struct.new $A
+     (ref.null $C)
+     (i32.const 42)
+    )
+   )
+  )
+  (global.set $b
+   (local.tee $b
+    (array.new $B
+     (global.get $a)
+     (i32.const 10)
+    )
+   )
+  )
+  (global.set $c
+   (local.tee $c
+    (array.new_fixed $C
+     (local.get $b)
+     (local.get $a)
+    )
+   )
+  )
+  (struct.set $A 0
+   (local.get $a)
+   (global.get $c)
+  )
+ )
+
+ ;; CHECK:      (global $ctor-eval$global_12 (ref $C) (array.new_fixed $C
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_13)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_14)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (export "test" (func $test_3))
+
+ ;; CHECK:      (export "keepalive" (func $keepalive))
+
+ ;; CHECK:      (start $start)
+
+ ;; CHECK:      (func $keepalive (type $none_=>_i32) (result i32)
+ ;; CHECK-NEXT:  (struct.get $A 1
+ ;; CHECK-NEXT:   (global.get $a)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $keepalive (export "keepalive") (result i32)
+  (struct.get $A 1
+   (global.get $a)
+  )
+ )
+)
+
+;; CHECK:      (func $start (type $none_=>_none)
+;; CHECK-NEXT:  (struct.set $A 0
+;; CHECK-NEXT:   (global.get $ctor-eval$global_14)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_12)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $test_3 (type $none_=>_none)
+;; CHECK-NEXT:  (local $a (ref $A))
+;; CHECK-NEXT:  (local $b (ref $B))
+;; CHECK-NEXT:  (local $c (ref $C))
+;; CHECK-NEXT:  (nop)
+;; CHECK-NEXT: )
+(module
+ ;; A cycle between two globals, where some of the fields participate in the
+ ;; cycle and some do not.
+
+ (rec
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $A (struct (field (mut (ref null $B))) (field (mut (ref null $B))) (field (mut (ref null $B)))))
+  (type $A (struct (field (mut (ref null $B))) (field (mut (ref null $B))) (field (mut (ref null $B)))))
+  ;; CHECK:       (type $B (array (ref null $A)))
+  (type $B (array (ref null $A)))
+ )
+
+ ;; CHECK:      (type $none_=>_none (func))
+
+ ;; CHECK:      (type $none_=>_anyref (func (result anyref)))
+
+ ;; CHECK:      (global $ctor-eval$global_16 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $a (mut (ref null $A)) (global.get $ctor-eval$global_16))
+ (global $a (mut (ref null $A)) (ref.null $A))
+ (global $b (mut (ref null $B)) (ref.null $B))
+
+ (func $test (export "test")
+  (local $a (ref $A))
+  (global.set $a
+   (local.tee $a
+    (struct.new $A
+     (array.new_default $B
+      (i32.const 0)
+     )
+     (ref.null $B)
+     (array.new_default $B
+      (i32.const 0)
+     )
+    )
+   )
+  )
+  (global.set $b
+   (array.new_fixed $B
+    (struct.new_default $A)
+    (global.get $a)
+    (struct.new_default $A)
+   )
+  )
+  (struct.set $A 1
+   (local.get $a)
+   (global.get $b)
+  )
+ )
+
+ ;; CHECK:      (global $ctor-eval$global_19 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $ctor-eval$global_15 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $ctor-eval$global_14 (ref $B) (array.new_fixed $B
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_15)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_16)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_19)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $ctor-eval$global_17 (ref $B) (array.new_fixed $B))
+
+ ;; CHECK:      (global $ctor-eval$global_18 (ref $B) (array.new_fixed $B))
+
+ ;; CHECK:      (export "test" (func $test_3))
+
+ ;; CHECK:      (export "keepalive" (func $keepalive))
+
+ ;; CHECK:      (start $start)
+
+ ;; CHECK:      (func $keepalive (type $none_=>_anyref) (result anyref)
+ ;; CHECK-NEXT:  (struct.get $A 1
+ ;; CHECK-NEXT:   (global.get $a)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $keepalive (export "keepalive") (result (ref null any))
+  (struct.get $A 1
+   (global.get $a)
+  )
+ )
+)
+
+;; CHECK:      (func $start (type $none_=>_none)
+;; CHECK-NEXT:  (struct.set $A 0
+;; CHECK-NEXT:   (global.get $ctor-eval$global_16)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_17)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (struct.set $A 1
+;; CHECK-NEXT:   (global.get $ctor-eval$global_16)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_14)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (struct.set $A 2
+;; CHECK-NEXT:   (global.get $ctor-eval$global_16)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_18)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $test_3 (type $none_=>_none)
+;; CHECK-NEXT:  (local $a (ref $A))
+;; CHECK-NEXT:  (nop)
+;; CHECK-NEXT: )
+(module
+ ;; As above, with the cycle creation logic reversed.
+
+ (rec
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $A (struct (field (ref null $B)) (field (ref null $B)) (field (ref null $B))))
+  (type $A (struct (field (ref null $B)) (field (ref null $B)) (field (ref null $B))))
+  ;; CHECK:       (type $B (array (mut (ref null $A))))
+  (type $B (array (mut (ref null $A))))
+ )
+
+ ;; CHECK:      (type $none_=>_none (func))
+
+ ;; CHECK:      (type $none_=>_anyref (func (result anyref)))
+
+ ;; CHECK:      (global $ctor-eval$global_16 (ref $B) (array.new_fixed $B
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $ctor-eval$global_19 (ref $B) (array.new_fixed $B))
+
+ ;; CHECK:      (global $ctor-eval$global_15 (ref $B) (array.new_fixed $B))
+
+ ;; CHECK:      (global $ctor-eval$global_14 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_15)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_16)
+ ;; CHECK-NEXT:  (global.get $ctor-eval$global_19)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $a (mut (ref null $A)) (global.get $ctor-eval$global_14))
+ (global $a (mut (ref null $A)) (ref.null $A))
+ (global $b (mut (ref null $B)) (ref.null $B))
+
+ (func $test (export "test")
+  (local $b (ref $B))
+  (global.set $b
+   (local.tee $b
+    (array.new_fixed $B
+     (struct.new_default $A)
+     (ref.null $A)
+     (struct.new_default $A)
+    )
+   )
+  )
+  (global.set $a
+   (struct.new $A
+    (array.new_default $B
+     (i32.const 0)
+    )
+    (global.get $b)
+    (array.new_default $B
+     (i32.const 0)
+    )
+   )
+  )
+  (array.set $B
+   (local.get $b)
+   (i32.const 1)
+   (global.get $a)
+  )
+ )
+
+ ;; CHECK:      (global $ctor-eval$global_17 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $ctor-eval$global_18 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (export "test" (func $test_3))
+
+ ;; CHECK:      (export "keepalive" (func $keepalive))
+
+ ;; CHECK:      (start $start)
+
+ ;; CHECK:      (func $keepalive (type $none_=>_anyref) (result anyref)
+ ;; CHECK-NEXT:  (struct.get $A 1
+ ;; CHECK-NEXT:   (global.get $a)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $keepalive (export "keepalive") (result (ref null any))
+  (struct.get $A 1
+   (global.get $a)
+  )
+ )
+)
+
+;; CHECK:      (func $start (type $none_=>_none)
+;; CHECK-NEXT:  (array.set $B
+;; CHECK-NEXT:   (global.get $ctor-eval$global_16)
+;; CHECK-NEXT:   (i32.const 0)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_17)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (array.set $B
+;; CHECK-NEXT:   (global.get $ctor-eval$global_16)
+;; CHECK-NEXT:   (i32.const 1)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_14)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (array.set $B
+;; CHECK-NEXT:   (global.get $ctor-eval$global_16)
+;; CHECK-NEXT:   (i32.const 2)
+;; CHECK-NEXT:   (global.get $ctor-eval$global_18)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $test_3 (type $none_=>_none)
+;; CHECK-NEXT:  (local $b (ref $B))
+;; CHECK-NEXT:  (nop)
+;; CHECK-NEXT: )
+(module
+ ;; The start function already exists here. We must prepend to it.
+
+ ;; CHECK:      (type $A (struct (field (mut (ref null $A))) (field i32)))
+ (type $A (struct (field (mut (ref null $A))) (field i32)))
+
+ ;; CHECK:      (type $none_=>_none (func))
+
+ ;; CHECK:      (type $none_=>_i32 (func (result i32)))
+
+ ;; CHECK:      (global $ctor-eval$global_4 (ref $A) (struct.new $A
+ ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (i32.const 42)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (global $a (mut (ref null $A)) (global.get $ctor-eval$global_4))
+ (global $a (mut (ref null $A)) (ref.null $A))
+
+ ;; CHECK:      (global $b (mut (ref null $A)) (ref.null none))
+ (global $b (mut (ref null $A)) (ref.null $A))
+
+ ;; CHECK:      (export "test" (func $test_3))
+
+ ;; CHECK:      (export "keepalive" (func $keepalive))
+
+ ;; CHECK:      (start $start)
+ (start $start)
+
+ (func $test (export "test")
+  (local $a (ref $A))
+  (global.set $a
+   (local.tee $a
+    (struct.new $A
+     (ref.null $A)
+     (i32.const 42)
+    )
+   )
+  )
+  (struct.set $A 0
+   (local.get $a)
+   (local.get $a)
+  )
+ )
+
+ ;; CHECK:      (func $keepalive (type $none_=>_i32) (result i32)
+ ;; CHECK-NEXT:  (i32.add
+ ;; CHECK-NEXT:   (struct.get $A 1
+ ;; CHECK-NEXT:    (global.get $a)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (struct.get $A 1
+ ;; CHECK-NEXT:    (global.get $b)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $keepalive (export "keepalive") (result i32)
+  (i32.add
+   (struct.get $A 1
+    (global.get $a)
+   )
+   (struct.get $A 1
+    (global.get $b)
+   )
+  )
+ )
+
+ ;; CHECK:      (func $start (type $none_=>_none)
+ ;; CHECK-NEXT:  (struct.set $A 0
+ ;; CHECK-NEXT:   (global.get $ctor-eval$global_4)
+ ;; CHECK-NEXT:   (global.get $ctor-eval$global_4)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (global.set $b
+ ;; CHECK-NEXT:   (global.get $a)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $start
+  (global.set $b
+   (global.get $a)
+  )
+ )
+)
+
+;; CHECK:      (func $test_3 (type $none_=>_none)
+;; CHECK-NEXT:  (local $a (ref $A))
+;; CHECK-NEXT:  (nop)
+;; CHECK-NEXT: )
+(module
+ ;; CHECK:      (type $A (struct (field (mut (ref null $A)))))
+ (type $A (struct (field (mut (ref null $A)))))
+
+ ;; CHECK:      (type $none_=>_none (func))
+
+ ;; CHECK:      (type $anyref_=>_none (func (param anyref)))
+
+ ;; CHECK:      (import "a" "b" (func $import (param anyref)))
+ (import "a" "b" (func $import (param anyref)))
+
+ (func $test (export "test")
+  (local $a (ref $A))
+  (struct.set $A 0
+   (local.tee $a
+    (struct.new_default $A)
+   )
+   (local.get $a)
+  )
+  ;; The previous instructions created a cycle, which we now send to an import.
+  ;; The import will block us from evalling the entire function, and we will
+  ;; only partially eval it, removing the statements before the call. Note that
+  ;; the cycle only exists in local state - there is no global it is copied to -
+  ;; and so this test verifies that we handle cycles in local state.
+  (call $import
+   (local.get $a)
+  )
+ )
+)
+;; CHECK:      (global $ctor-eval$global (ref $A) (struct.new $A
+;; CHECK-NEXT:  (ref.null none)
+;; CHECK-NEXT: ))
+
+;; CHECK:      (export "test" (func $test_3))
+
+;; CHECK:      (start $start)
+
+;; CHECK:      (func $start (type $none_=>_none)
+;; CHECK-NEXT:  (struct.set $A 0
+;; CHECK-NEXT:   (global.get $ctor-eval$global)
+;; CHECK-NEXT:   (global.get $ctor-eval$global)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $test_3 (type $none_=>_none)
+;; CHECK-NEXT:  (call $import
+;; CHECK-NEXT:   (global.get $ctor-eval$global)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
diff --git a/test/lit/ctor-eval/partial-global.wat b/test/lit/ctor-eval/partial-global.wat
new file mode 100644
index 000000000..fdd196d02
--- /dev/null
+++ b/test/lit/ctor-eval/partial-global.wat
@@ -0,0 +1,39 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+;; RUN: wasm-ctor-eval %s --ctors=test --kept-exports=test --quiet -all -S -o - | filecheck %s
+
+(module
+ ;; CHECK:      (type $none_=>_none (func))
+
+ ;; CHECK:      (global $global (mut i32) (i32.const 0))
+ (global $global (mut i32) (i32.const 0))
+
+ (func $test (export "test")
+  ;; The nop can be evalled away, but not the loop. We should not apply any
+  ;; partial results from the loop - in particular, the global must remain at
+  ;; 0. That is, the global.set of 999 below must not be applied to the global.
+  ;;
+  ;; (It is true that in this simple module it would be ok to set 999 to the
+  ;; global, but if the global were exported for example then that would not
+  ;; be the case, nor would it be the case if the code did $global = $global + 1
+  ;; or such. That is, since the global.set is not evalled away, its effects
+  ;; must not be applied; we do both atomically or neither, so that the
+  ;; global.set's execution only happens once.)
+
+  (nop)
+  (loop
+   (global.set $global
+    (i32.const 999)
+   )
+   (unreachable)
+  )
+ )
+)
+
+;; CHECK:      (export "test" (func $test_1))
+
+;; CHECK:      (func $test_1 (type $none_=>_none)
+;; CHECK-NEXT:  (global.set $global
+;; CHECK-NEXT:   (i32.const 999)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (unreachable)
+;; CHECK-NEXT: )