Prototype GC instructions

[dcodeIO]

According to WebAssembly/gc#81 and the linked status document, there is early prototyping work of the GC proposal done in WABT and V8, and I'd love to start playing with it. Are there any plans on the Binaryen side already? I'd also be happy to help where I can, that is if there's anything I can do that doesn't hurt more to review than it helps. Just let me know :)

One interesting aspect also is that once the respective instructions are available in Binaryen, there also comes the opportunity to transform a GC-enabled module to a non-GC module by essentially polyfilling a runtime. I'd imagine that a transform pass like this would be useful for all sorts of tools and languages to ease the transition in the future (emit Wasm GC today, run without), and perhaps some bits of what we have at AS already can be used to make this possible.

[kripken]

I'm not aware of anyone planning to work on this. But I'm also not sure if it makes sense atm to experiment in multiple toolchain projects. cc @binji for thoughts.

I like the idea for a pass to lower GC to non-GC, yeah, that sounds like it could be useful for polyfilling etc.!

[binji]

@tlively Yeah, this would be another benefit of having shared parsing/loading code for wabt and binaryen :-) I'm still hoping to do this by using wasp as a long-term goal, but it seems I never have quite enough time. That said, it's definitely not dropped.

[tlively]

I also still hope to use wasp in Binaryen! We'll be in a good position to evaluate that project after the current Stack IR redesign/refactoring/replacement is done. That being said, GC support would require much more work in Binaryen than just the parsing that wasp would provide. If anyone from the wider community would be interested in taking a stab at implementing experimental GC support, I'd be happy help out with guidance and code reviews.

[dcodeIO]

So I took an initial stab at this and added the instruction classes StructNew, StructGet, StructSet, ArrayNew, ArrayGet, ArraySet and ArrayLen (ref: WebAssembly/wabt#1345) in a way that Binaryen compiles again. Anything touching RTTs is more in a stub/TODO state still and there is no text parsing yet.

Consequently, the next aspect to get right is how to represent struct and array types. One strategy might be to:

• Rename Signature to FunctionDefinition
• Add StructDefintion (has multiple FieldDefinitions with type and mutability)
• Add ArrayDefinition (has an element Type and mutability)
• Add TypeDefinition as a union of FunctionDefinition | StructDefinition | ArrayDefinition
• Fixup existing Signature usage accordingly
• Continue implementing the instructions above similar to CallIndirect, referencing either a StructDefinition or ArrayDefinition

Does this approach sound ok?

[binji]

I'm not sure exactly how binaryen does it, but the more invasive change (in my experience) is to ValueType, which now must also support an optional index (or optional name, for the text format).

[tlively]

@dcodeIO The recently-redesigned Type is meant to be extensible to these new kinds of complex types, just like it has been extended to handle tuples already. Currently all types are interned in the indices map in wasm-type.cpp. Right now the key to that map is std::vector<Type> because the only complex types are tuples. To support new kinds of types, we will need to have a more interesting interned type that can represent the new type structures as well. If we had C++17, this would probably be a std::variant, but since we're still on C++14, we will have to do something more ad hoc with a tagged union.

[dcodeIO]

I'm not sure exactly how binaryen does it, but the more invasive change (in my experience) is to ValueType, which now must also support an optional index (or optional name, for the text format).

Can you elaborate a bit why this information has to live on the types directly? So far I imagined that we'll need some sort of mapping of types (global to all modules in Binaryen, describing layouts of structs, arrays or functions) to the types section (local to each module, like function signatures) and that indices or names would be a property of the link from a global type to a
specific module's type section entry. Very likely that I'm overlooking something in the spec so far.

Currently all types are interned in the indices map in wasm-type.cpp.

I see, thanks, looking at it now. Hmm, perhaps separate indices, one for multi values, structs, arrays and signatures with a shared internal counter for the unique id? Structs can be keyed as a list of their fields (each field has a Type and a mutable flag) and arrays as a single field indicating their element type (unless arrays can have other fields?). Oh my.

[binji]

Can you elaborate a bit why this information has to live on the types directly?

There are (at least) two new value types: ref $t and ref null $t, where $t is a type index. These are actually first introduced in the function-references proposal, but are used in the gc proposal too. So you can use these types anywhere that i32 etc. were previously allowed, e.g.

(type $t ...)
(table 0 (ref $t))
(global (ref $t) ...)
(func (param (ref $t)) (result (ref null $t))
  (local (ref null $t))
  (block (param (ref null $t)) (result (ref $t))
    ...
  )
)
...

[tlively]

I see, thanks, looking at it now. Hmm, perhaps separate indices, one for multi values, structs, arrays and signatures with a shared internal counter for the unique id? Structs can be keyed as a list of their fields (each field has a Type and a mutable flag) and arrays as a single field indicating their element type (unless arrays can have other fields?). Oh my.

The map keys are used when creating a new Type to look up whether an instance of that type already exists. Since we know what kind of type we are trying to create, having separate maps for each type would work. However, a Type itself is just a pointer to richer interned data structure that describes the structure of the type, so the Type does not know what kind of type it is without looking at the interned data structure. That means that we still need a unified data type that can describe the layout of any kind of type. Given that, I'm not sure having separate maps buys us much.

[dcodeIO]

Thanks guys! So, would it be viable to establish something like

class Type {
  enum Kind {
    Default,
    Multi,
    Function,
    Struct,
    Array
  };
  uintptr_t id;
  Type::Kind kind;
  union {
    MultivalueDefinition multiDef;
    FunctionDefinition funcDef;
    StructDefinition structDef;
    ArrayDefinition arrayDef;
  };
  bool isStruct() { return kind == Type::Kind::Struct; }
  bool isNullable() {
    switch (kind) {
      ...
      case Type::Kind::Struct: return structDef.nullable;
      ...
      default: return false;
    }
  }
  ...
}

struct MultivalueDefinition {
  std::vector<Type> types;
};

struct FunctionDefinition {
  std::vector<Type> params;
  std::vector<Type> results;
  bool nullable;
};

struct Field {
  Type type;
  bool mutable_;
};

struct StructDefinition {
  std::vector<Field> fields;
  bool nullable;
};

struct ArrayDefinition {
  Field element;
  bool nullable;
};

with instances of MultivalueDefinition, FunctionDefinition, Field, StructDefinition and ArrayDefinition being globally deduplicated just like the types referencing them, and the $t in (ref $t ...) being represented by the per-module index of such a type in the module's type section array (inserted when reading / looked up when printing / otherwise mostly irrelevant)?

If not, what'd be a good alternative fitting into the existing code base?

[tlively]

Yeah, that's almost what I have in mind. The only difference is that your code snippet above adds a kind field to Type, which would increase the size of every Type in the IR. We definitely need a TypeKind somewhere, but I would put it into a new TypeDescription tagged union struct that is private to wasm-types.cpp rather than in Type itself. The TypeDescription would replace the std::vector<Type> as the thing that gets interned.

A few other notes so I don't have to repeat them later in code review:

• I think we should standardize on the "tuple" terminology for tuple types, rather than "multi."

• The Definition suffix on the structs seems unnecessary; I think it could be shortened to Def or omitted.

• Rather than defining a new struct MultivalueDefinition, I think it would be simpler for all the client code to just have using Tuple = std::vector<Type> (or just omit it entirely) to avoid a layer of type wrapping.

• Instead of having separate params and results fields, FunctionDefinition can just contain a Signature.

[binji]

I think this is a reasonable way to do it, though it ends up combining the two concepts of a "value type" and the "type definition". One concern is that a type definition has an explicit index space, but value types don't. Since this model compresses all types together, you would need to have a separate mapping from a type index to your Type struct, or you would need to fully remove all type indexes when parsing.

You'll need to be a bit careful when doing this too, since types can be recursive in different ways, but should be considered equivalent, e.g.

(module wat
  (type $t1 (func (param i32 (ref $t1))))
  (type $t2 (func (param i32 (ref $t3))))
  (type $t3 (func (param i32 (ref $t2))))
  ...
)

Here $t1, $t2, and $t3 are all equivalent.

[tlively]

Binaryen IR does not have a concept of type definitions or type indices, so I don't think this will be a problem. We reconstruct the type section and all type indices on demand when the module is emitted.

[dcodeIO]

So far I came up with these:

typedef std::vector<Type> Tuple;

struct Field {
  Type type;
  bool mutable_;
  Field(Type type, bool mutable_ = false) : type(type), mutable_(mutable_) {}
  bool operator==(const Field& other) const {
    return type == other.type && mutable_ == other.mutable_;
  }
  bool operator!=(const Field& other) const { return !(*this == other); }
};

typedef std::vector<Field> FieldList;

struct Struct {
  FieldList fields;
  bool nullable;
  Struct(FieldList fields, bool nullable = false)
    : fields(fields), nullable(nullable) {}
  bool operator==(const Struct& other) const {
    return fields == other.fields && nullable == other.nullable;
  }
  bool operator!=(const Struct& other) const { return !(*this == other); }
};

struct Array {
  Field element;
  bool nullable;
  Array(Field element, bool nullable = false)
    : element(element), nullable(nullable) {}
  bool operator==(const Array& other) const {
    return element == other.element && nullable == other.nullable;
  }
  bool operator!=(const Array& other) const { return !(*this == other); }
};

struct TypeDef { // move to wasm-type.cpp ?
  enum Kind { TupleKind, SignatureKind, StructKind, ArrayKind };

  Kind kind;
  union Def {
    Def(Tuple tuple) : tuple(tuple) {}
    Def(Signature signature) : signature(signature) {}
    Def(Struct struct_) : struct_(struct_) {}
    Def(Array array) : array(array) {}
    ~Def() {}
    Tuple tuple;
    Signature signature;
    Struct struct_;
    Array array;
  } def;

  TypeDef(Tuple tuple) : kind(TupleKind), def(tuple) {}
  TypeDef(Signature signature) : kind(SignatureKind), def(signature) {}
  TypeDef(Struct struct_) : kind(StructKind), def(struct_) {}
  TypeDef(Array array) : kind(ArrayKind), def(array) {}

  bool operator==(const TypeDef& other) const {
    if (kind != other.kind)
      return false;
    switch (kind) {
      case TupleKind:
        return def.tuple == other.def.tuple;
      case SignatureKind:
        return def.signature == other.def.signature;
      case StructKind:
        return def.struct_ == other.def.struct_;
      case ArrayKind:
        return def.array == other.def.array;
      default:
        WASM_UNREACHABLE("unexpected kind");
    }
  }
  bool operator!=(const TypeDef& other) const { return !(*this == other); }
};

reusing Signature the way it is and adding Tuple, Struct and Array descriptions. Looking at the hashing stuff etc. I'm worrying, however, that my C++ foo isn't sufficient yet to make the changes to wasm-type.cpp without significant reviewing overhead. I can try, if you like, or I can leave this particular change to someone with more experience and continue from there?