Add support for WebAssembly GC recursion groups

[takikawa]

5f38595

Add support for WebAssembly GC recursion groups
https://bugs.webkit.org/show_bug.cgi?id=239666

Reviewed by Justin Michaud.

Add support for the Wasm GC proposal's recursion groups. These are
a new kind of TypeDefinition that allows for recursive type
definitions. Recursive type index references are only allowed with
recursion group definitions.

Recursion groups can be stored hash-consed like other type
definitions, but to successfully compare them they must store several
definitions in the type store:

  - The recursion group itself (rec (type ...) ...)
  - Each type component in the group (type ...), where any potential
    recursive references are represented as a special value type.
  - Projections into the recursion group ((rec ...).<i>)

Projections can be expanded into the underlying function/struct/etc
type when the validator needs to examine the structure of the type.
This operation exposes the type component in the group, and replaces
recursive references with the appropriate projection (which can then
be expanded if required, and so on).

If expansion becomes a bottleneck, it is easy to memoize it with the
addition of a TypeIndex to TypeIndex mapping in the type store.

Generally, the expansion operation is needed when code relies on the
structure of the underlying type. For functions, these uses usually
look like `signature.as<FunctionSignature>()`. The signature *must* be
expanded before such a conversion is called.

When signatures need to be compared for equality, such as for
call_indirect or for matching function import/export, the comparison
should generally be done by the type index of the projection. That is,
*not* by equality of the underlying/expanded type.

Recursive references are not represented in the binary format and are
internal to the semantics and implementation. To avoid using extra
opcodes, they are internally represented as a type that uses the
opcode for recursion group (TypeKind::Rec), which cannot normally be
used for value types in the binary format, with a heap type that
encodes the index into the recursion group's type list.

* JSTests/wasm/gc/rec.js: Added.
(module):
(testRecDeclaration):
* JSTests/wasm/wasm.json:
* Source/JavaScriptCore/wasm/WasmAirIRGenerator.cpp:
(JSC::Wasm::AirIRGenerator::AirIRGenerator):
(JSC::Wasm::AirIRGenerator::addCallIndirect):
* Source/JavaScriptCore/wasm/WasmB3IRGenerator.cpp:
(JSC::Wasm::B3IRGenerator::addCallIndirect):
* Source/JavaScriptCore/wasm/WasmBBQPlan.cpp:
(JSC::Wasm::BBQPlan::work):
(JSC::Wasm::BBQPlan::compileFunction):
* Source/JavaScriptCore/wasm/WasmCallee.h:
* Source/JavaScriptCore/wasm/WasmFormat.h:
(JSC::Wasm::isValueType):
* Source/JavaScriptCore/wasm/WasmFunctionCodeBlockGenerator.cpp:
(JSC::Wasm::FunctionCodeBlockGenerator::addSignature):
* Source/JavaScriptCore/wasm/WasmFunctionCodeBlockGenerator.h:
* Source/JavaScriptCore/wasm/WasmFunctionParser.h:
(JSC::Wasm::splitStack):
(JSC::Wasm::FunctionParser<Context>::FunctionParser):
(JSC::Wasm::FunctionParser<Context>::parse):
(JSC::Wasm::FunctionParser<Context>::parseExpression):
(JSC::Wasm::FunctionParser<Context>::parseUnreachableExpression):
* Source/JavaScriptCore/wasm/WasmInstance.cpp:
(JSC::Wasm::Instance::initElementSegment):
* Source/JavaScriptCore/wasm/WasmLLIntGenerator.cpp:
(JSC::Wasm::LLIntGenerator::callInformationForCaller):
(JSC::Wasm::LLIntGenerator::callInformationForCallee):
(JSC::Wasm::LLIntGenerator::addArguments):
(JSC::Wasm::LLIntGenerator::addCallIndirect):
(JSC::Wasm::LLIntGenerator::addCallRef):
* Source/JavaScriptCore/wasm/WasmLLIntPlan.cpp:
(JSC::Wasm::LLIntPlan::didCompleteCompilation):
* Source/JavaScriptCore/wasm/WasmLimits.h:
* Source/JavaScriptCore/wasm/WasmParser.h:
(JSC::Wasm::Parser<SuccessType>::Parser):
(JSC::Wasm::Parser<SuccessType>::parseHeapType):
(JSC::Wasm::Parser<SuccessType>::parseValueType):
* Source/JavaScriptCore/wasm/WasmSectionParser.cpp:
(JSC::Wasm::SectionParser::parseType):
(JSC::Wasm::SectionParser::parseElement):
(JSC::Wasm::SectionParser::parseRecursionGroup):
* Source/JavaScriptCore/wasm/WasmSectionParser.h:
* Source/JavaScriptCore/wasm/WasmSlowPaths.cpp:
(JSC::LLInt::doWasmCallIndirect):
(JSC::LLInt::doWasmCallRef):
* Source/JavaScriptCore/wasm/WasmTypeDefinition.cpp:
(JSC::Wasm::TypeDefinition::dump const):
(JSC::Wasm::RecursionGroup::toString const):
(JSC::Wasm::RecursionGroup::dump const):
(JSC::Wasm::Projection::toString const):
(JSC::Wasm::Projection::dump const):
(JSC::Wasm::computeRecursionGroupHash):
(JSC::Wasm::computeProjectionHash):
(JSC::Wasm::TypeDefinition::hash const):
(JSC::Wasm::TypeDefinition::tryCreateFunctionSignature):
(JSC::Wasm::TypeDefinition::tryCreateStructType):
(JSC::Wasm::TypeDefinition::tryCreateRecursionGroup):
(JSC::Wasm::TypeDefinition::tryCreateProjection):
(JSC::Wasm::TypeDefinition::substitute):
(JSC::Wasm::TypeDefinition::replacePlaceholders const):
(JSC::Wasm::TypeDefinition::expand const):
(JSC::Wasm::FunctionParameterTypes::equal):
(JSC::Wasm::StructParameterTypes::equal):
(JSC::Wasm::RecursionGroupParameterTypes::hash):
(JSC::Wasm::RecursionGroupParameterTypes::equal):
(JSC::Wasm::RecursionGroupParameterTypes::translate):
(JSC::Wasm::ProjectionParameterTypes::hash):
(JSC::Wasm::ProjectionParameterTypes::equal):
(JSC::Wasm::ProjectionParameterTypes::translate):
(JSC::Wasm::TypeInformation::typeDefinitionForRecursionGroup):
(JSC::Wasm::TypeInformation::typeDefinitionForProjection):
* Source/JavaScriptCore/wasm/WasmTypeDefinition.h:
(JSC::Wasm::RecursionGroup::RecursionGroup):
(JSC::Wasm::RecursionGroup::typeCount const):
(JSC::Wasm::RecursionGroup::type const):
(JSC::Wasm::RecursionGroup::getType):
(JSC::Wasm::RecursionGroup::storage):
(JSC::Wasm::RecursionGroup::storage const):
(JSC::Wasm::Projection::Projection):
(JSC::Wasm::Projection::recursionGroup const):
(JSC::Wasm::Projection::index const):
(JSC::Wasm::Projection::getRecursionGroup):
(JSC::Wasm::Projection::getIndex):
(JSC::Wasm::Projection::storage):
(JSC::Wasm::Projection::storage const):
(JSC::Wasm::TypeDefinition::TypeDefinition):
(JSC::Wasm::TypeDefinition::allocatedRecursionGroupSize):
(JSC::Wasm::TypeDefinition::allocatedProjectionSize):
* Source/JavaScriptCore/wasm/WasmTypeDefinitionInlines.h:
(JSC::Wasm::TypeInformation::getFunctionSignature):
* Source/JavaScriptCore/wasm/js/WasmToJS.cpp:
(JSC::Wasm::wasmToJS):
* Source/JavaScriptCore/wasm/js/WebAssemblyModuleRecord.cpp:
(JSC::WebAssemblyModuleRecord::initializeExports):
* Source/JavaScriptCore/wasm/wasm.json:

Canonical link: https://commits.webkit.org/253491@main

[kmiller68]

Still reviewing but here are some initial comments

[kmiller68]

I think this is wrong. I believe all wasm callees are still FunctionSignatures.

[takikawa]

AFAICT this is required due to the semantics of recursion groups. The reason is that with the addition of recursion groups, in general all type signatures have to be compared by projection, even if you know it will be a function signature underneath.

The reason is you may have function types like the following:

(rec (type (func $f1)) (type (struct ...)))

(rec (type (func $f2)))

Even though $f1 and $f2 look the same, and are indeed the same if you unfold the projections, they are not equal types because they are in different recursion groups.

(it seems a bit silly in this very simple case, but you can construct more interesting examples where $f1 and $f2 would unfold to the same type that, say, reference another member of the recursion group. And where these other members are not equal types.)

[justinmichaud]

@kmiller68 was trying to explain this to me, so I am wondering if I can ask few clarifying questions:

(rec $r1
    (type $tree (struct (field i32) (field (ref $forest))))
    (type $forest (struct (field (ref $tree)) (field (ref $forest)))))
 
(type $s1 (struct (field (ref $tree))))

1. Types are stored as instances of TypeInformation, and expanded to produce a FunctionSignature (including for struct types)?

2. Projection in this case means taking a TypeDefinition, and selecting an element of it without any substitution? So:

$r1 is given a type index
$s1 is represented by TypeDefinition(StructType(Projection($r1, 0)))
$tree is TypeDefinition(Projection($r1, 0))

1. Expanding replaces a projection with a new projection that has had one step of unrolling applied, with the recursion group as the target of the unrolling

2. Unrolling is applying one step of substitution, replacing references to the recursion group with its expansion. So:

expand($tree) <=>
unroll(Projection($r1, 0) with respect to $r1) <=>
TypeDefinition(StructType(i32), TypeDefinition(Projection($r1, 0)))

This new expansion is given its own type index, and comparisons are made by type index?

We need to compare types by type index because the type definitions are iso-recursive? So a TypeDefinition and its .expand() are not the same type?

If they were equirecursive, then we would have to perform a dfs expanding until we could prove that the types did/did not match?

Sorry to bug you with all these questions, I will continue playing with this patch to see how many of these questions I can answer by myself.

[takikawa]

Thanks for the comments so far! I think I've addressed the current feedback in the new commit.

[takikawa]

Just wanted to provide a friendly ping on this @kmiller68. Let me know if there's anything I can do to clarify the code or anything like that, would be happy to help out.

I'll rebase this patch and re-push soon as well.

[takikawa]

(Replying here instead of in the comment thread above because Github is erroring when I try to add comments there)

@justinmichaud Sorry for not seeing your comment earlier! Github didn't ping me about it.

Types are stored as instances of TypeInformation, and expanded to produce a FunctionSignature (including for struct types)?

For structs, they should get expanded to a StructType. When array types are added, they would get expanded to ArrayType and so on.

Projection in this case means taking a TypeDefinition, and selecting an element of it without any substitution? So:

Yes that's right, though projection is specifically about selecting an element from a recursion group (though all type defs are technically in a recursion group in the GC proposal, we can normalize simple cases as not being in one).

This new expansion is given its own type index, and comparisons are made by type index?

Yes, the expansion will have its own type index, but generally the expansion's type index shouldn't matter very much. When checking equality, the unexpanded projection's index will matter more.

e.g., if you are importing a function into another Wasm module, then the check that that the function has the same type is done with the projection's type index.

We need to compare types by type index because the type definitions are iso-recursive? So a TypeDefinition and its .expand() are not the same type?

I think we would want to compare them by type index even in an equi-recursive setting too, but how we canonicalize types to type indices would be different in that world.

If the TypeDefinition is a projection for a recursion group, then yes the definition and its .expand() are not the same type.

Right now, types are aren't explicitly declared with rec are stored as before without recursion groups, so their expansion are the same type. Technically the GC proposal considers single type definitions like these to be recursion groups with only one element, but we can normalize these to be a plain type definition as long as it doesn't contain a recursive reference.

(I think this patch doesn't handle all of these corner cases completely correctly, but I was planning to address them in follow-ups)

If they were equirecursive, then we would have to perform a dfs expanding until we could prove that the types did/did not match?

Yes, we would need a different algorithm that iterates over the types. The equirecursive case would be more difficult to engineer as I think it's not possible to do the bottom-up type hash-consing that JSC currently does for the type definitions.

Sorry to bug you with all these questions, I will continue playing with this patch to see how many of these questions I can answer by myself.

No problem, I'm happy to answer any additional questions too or clarify anything I've written here too!

[justinmichaud]

Hmm, I wish these cases both acted the same way.

Consider

(struct $a i32)
(rec (struct $b i32))
(struct $c i32)

Is it the case that $a != $b != $c, since they are all defined in separate recursion groups? In the parlance of the spec draft, they have different tied context types?

[justinmichaud]

Either way, it would be nice for all the cases to act the same way.

[takikawa]

These should actually all be equivalent, I think it's just an oversight/bug in this patch. You can verify this by trying this example in the reference interpreter:

(module 
  (type $a (struct (field i32)))
  (rec (type $b (struct (field i32))))
  (type $c (struct (field i32)))

  (func (result (ref null $a)) (ref.null $b))
  (func (result (ref null $a)) (ref.null $c))
  (func (result (ref null $b)) (ref.null $a))
  (func (result (ref null $b)) (ref.null $c))
  (func (result (ref null $c)) (ref.null $a))
  (func (result (ref null $c)) (ref.null $b)))

which should validate AFAICT.

The issue in the code is that either we have to normalize structs without a recursion group to be represented with a singleton recursion group, or we have to normalize non-recursive, single-member recursion groups into just a struct definition.

I think the latter approach is probably better, as it avoids the need to unroll projections when they're not needed. I did something similar for normalizing subtyping declarations (the spec says types without an explicit sub declaration are treated as having a sub with empty parents, just like how types without an explicit rec are treated as being wrapped with a rec).

[takikawa]

I just fixed this case in the latest push, and added a test case for the above example. It normalizes non-recursive, single recursion groups as being just the underlying type definition.

Parsing still has multiple code paths for this though, because the binary shorthand may or may not be used.

[justinmichaud]

I am confused about the logic here, but also the message is wrong?

[takikawa]

Yeah, this is unfortunately a bit confusing.

When the typed function references proposal is fully fleshed out, it will support both tables and element sections with concrete function types (as described in https://github.com/WebAssembly/function-references/blob/main/proposals/function-references/Overview.md#summary). But right now, it's restricted to funcref.

The confusing thing is that the representation of funcref changes a bit between Wasm with reference types and Wasm with typed function references. In the former, it was always a type with TypeKind::Funcref. In the latter, it is a TypeKind::Ref with a heap type of func and the other form becomes a shorthand for this.

The old code !refType.isFuncref() is only checking for the shorthand form. This causes some of the tests in this patch to fail, because some of the binary modules use the new form (there is otherwise no connections to recursion groups). The new code is doing the equivalent check but allowing for the non-shorthand Ref type form. So there is no change in functionality here; the code is just accounting for a change in representation caused by typed function references.

[justinmichaud]

The original check should never find that the modules aren't the same, right?

[takikawa]

Did you mean the function signatures aren't the same? In that case, no, the check could fail because a Wasm table could be initialized with type funcref and the table contents matching the call's function type wouldn't be enforced statically.

(but you're right that it cannot fail if typed function references are used and the table is declared with a concrete function type, as in the examples at https://github.com/WebAssembly/function-references/blob/main/proposals/function-references/Overview.md#examples)

[justinmichaud]

How do we pick these?

[takikawa]

I've been picking by generating a random hex number, but if there is a more principled way to do it I would be happy to change this.

[takikawa]

I pushed a new version of the patch that rebases to accommodate recent changes. The tests now use the text format except in cases where the details of the binary encoding matters for the test. It also addresses some review comments from above.

The previous version of this patch also had a change in WasmToJS.cpp related to how reftype outputs get converted for use in JS. I've removed that change because it's logically a separate bug to do with typed function references, so I will file a separate bug and patch for that (it was only included here because a test exercised that path, I've modified the test instead).

[justinmichaud]

r=me modulo comment nits

[takikawa]

Thanks for the review! The latest push addressed the remaining nits (added more comments, also renamed a function to be clearer) and CI looks all green, so I'll apply the merge queue label now.

[takikawa]

Oh hmm, I thought that since I now have permissions to label my PR it might let me merge but probably not:

Note that Merge-Queue will reject pull requests that are labeled by contributors who are not committers.

@justinmichaud if you wouldn't mind applying the label instead, that would be great. :)

[webkit-commit-queue]

@takikawa does not have committer permissions according to https://raw.githubusercontent.com/WebKit/WebKit/main/metadata/contributors.json.

If you do have committer permmissions, please ensure that your GitHub username is added to contributors.json.

Rejecting 8785e28077c9277cdde7e330b900f25066408aa1 from merge queue.

[webkit-commit-queue]

Committed 253491@main (5f38595): https://commits.webkit.org/253491@main

Reviewed commits have been landed. Closing PR #740 and removing active labels.