[RFC] WebAssembly tables in Clang

[asb]

Summary and general background

This RFC is intended to build consensus on how WebAssembly tables are represented in C/C++, aiming to expose the underlying platform capabilities (and to be explicit, the scope of this functionality is limited to the WebAssembly target). The proposal in short is to expose tables as arrays of references which will be lowered appropriately by the backend. This intends to expose the basic functionality in a straightforward manner, leaving space for later experimentation. See below for more background on WebAssembly tables and reference types, and options that have been considered.

WebAssembly (abbreviated as Wasm) is a stack-based virtual machine that has support shipping in all the major browser engines. LLVM has a WebAssembly backend as one of its default targets.

Reference types and tables were introduced into the Wasm spec in order to allow more efficient interoperation with the host environment (e.g. garbage-collected JavaScript).

Thank you to Thomas Lively, Paulo Matos, and Andy Wingo for comments on a draft of this RFC or related documents.

Background on WebAssembly reference types

Values in early versions of the WebAssembly specification only had numeric types: either i32, i64, f32, or f64. The reference type specification later added a new kind of value type, for opaque host-managed values.

In contrast to the other value types, reference types are opaque types for which it is impossible to observe their size or their bit pattern. Reference-typed values can’t be stored in linear memory (i.e. used with WebAssembly load/store instructions). Instead these values can be stored in tables, which can be thought of as linear memory for reference types.

Currently there are two concrete reference types in WebAssembly: funcref (reference to a function), and externref (a reference to an object owned by an embedder). LLVM already supports them both. At the IR level, these are modelled as pointers to specific non-default address spaces (10 and 20, respectively), with appropriate WebAssembly instructions being selected during lowering (MVT::externref/MVT::funcref types). A patch for supporting them in Clang is under review, exposing __externref_t and representing function pointers with the __funcref attribute as funcrefs. These are modelled as sizeless types (much like scalable vectors are), with the additional semantic restriction that you can’t take the address of an externref or funcref.

Though there are only two reference types currently, in the future this set will become unbounded. For example the typed function references proposal will allow WebAssembly modules to declare funcref values with a specific type (parameters and results). Other proposals will allow WebAssembly modules to declare host-managed aggregate types (garbage-collected structs and arrays). Any proposed design for how to represent WebAssembly tables in Clang should take these future developments into account.

Background on WebAssembly tables

As it isn’t possible to load/store reference types to WebAssembly memory (which corresponds to the default address space in LLVM), a new datatype was introduced that is able to hold them - the table (or arguably just exposed/generalised tables: WebAssembly modules did have the indirect function table, but there was no ability to directly manipulate it or define new tables).

A WebAssembly module has some number of tables, each referred to by an integer index (tableidx) and having a type (currently either externref or funcref, but in future a WebAssembly module will be able to declare a table containing any reference type in the module). Although the tableidx is a plain integer, the instructions to manipulate tables in Wasm take the tableidx as an immediate operand, meaning code generation isn’t possible unless the specific tableidx is a known constant. This implies additional semantic restrictions on any representation of tableidx in a source language.

You might, for instance, use a table of externrefs in order to track objects managed by the host environment but referenced from WebAssembly.

Support for tables is already present in LLVM IR, where they are represented as global arrays of addrspace 10/20 pointers (with the array itself in address space 1, the ‘wasm_var’ address space used for Wasm locals/globals). Appropriate table declarations are created during lowering, and loads/stores to these tables at the IR level are converted to table.get and table.set instructions.

WebAssembly tables in Clang

My current patch under review allows the declaration of arrays of reftypes (e.g. __externref_t table[0];), which lowers to IR that is already recognised as a table type. rjmccall quite rightly suggested an RFC on this approach would be helpful, hence this document.

In summary:

• Tables are declared like __externref_t table[0]; (static, default storage class, or extern)
  • Initialising the table is not currently allowed as the WebAssembly table initialization mechanism (element segments) isn’t currently supported in LLVM WebAssembly. This can be added later.
  • The current iteration of the patch conservatively disallows extern due to lack of test coverage, but this is expected to work.
  • It is likely we will later want to allow something along the lines of the import_name attribute to allow importing tables under a certain name.
• Array operations on these arrays will be lowered to table.set and table.get by the backend.
• Builtins are exposed for table.size, table.grow, table.fill, and table.copy.

Because the integer tableidx must be used as an immediate operand to the Wasm table instructions, a range of semantic restrictions on use of tables is necessary. Tables may only be used as the operand to a table builtin, or when indexing it as an array (i.e. table[idx] or table[idx] = foo).

Implementing these semantic restrictions requires:

• Making an exception to the usual restrictions on sizeless types to allow the array representing a table to be declared since the reference type table elements are themselves sizeless types.
• Modifying a number of other parts of Sema to produce appropriate errors if tables are used in a context where they are not supported.

Potential positives of this representation:

• Provides a clear path forward for declaring tables of different types as the set of reference types increases.
• Aligns to the current IR representation, meaning codegen is straightforward.
• Syntax is familiar and ergonomic (though this is largely a matter of taste)

Possible negatives:

• There’s a lot of overlap with semantic restrictions on sizeless types, but new diagnostics must be implemented for tables (even if isSizelessType were modified to return true for tables, the current code paths for sizeless type diagnostics may not be hit because of other tests like isArrayType returning true.

The main alternative approach I can think of would be to introduce a new sizeless type for each table type and to use builtins for table.get and table.set. This would be straightforward initially with __externref_t_table and __funcref_t_table, but once the typed function references spec is introduced it would require a way to generate a table type for a given reference type. A few ways this might be achieved:

• Possibly there’s a way this could be done with a builtin to create the type (if anyone knows of examples of something similar, that would be helpful)
• Something long the lines of __attribute__(__table_type__(__externref_t)) __table_t
• Following along the lines of Altivec (which introduces the vector keyword) and adding a new keyword for tables (mentioning for completeness, not actually proposing this)

I haven’t pushed much in these directions as they didn’t seem to have any real advantages over the approach currently being used. I’d welcome feedback to the contrary of course!

Conclusion

In summary:

• References and tables in WebAssembly are supported at the IR level and the
  WebAssembly backend (codegen and MC layer), but not currently exposed to
  C/C++ in Clang.
• This RFC details the approach currently being used to expose tables to
  C/C++.
• I’d really welcome feedback, suggestions, and questions. Thank you in
  advance.

[rjmccall]

Thanks for writing this up.

I think you will need a JumpDiagnostics restriction on local reference variables so that code can’t jump past the initialization. And reference types will be highly restricted; you won’t be able to put them in normal structs or take the address of them.

The restrictions here on what you can do with a table are very strict; basically, you can’t do anything with the table except use it as the immediate operand to a small number of operations. It’s pretty un-C-like, but that’s the world you’re in, I suppose.

I have a lot of questions about the future directions, especially the structs and arrays proposal; they seem to profoundly affect the necessary design.

• I take it the suggestion here is that you will have tables of structs and arrays, and there will be operations to extract the ith struct element of table element j.
• These structs are basically not usable elsewhere in the program because they contain reference types, right?
• I assume the access restrictions for arrays are basically the same as for tables, except that there’s an access path leading to the array being accessed.
• How much are arrays basically just tables in nested positions? Are they fixed size or resizable, or can they be either?

How do external-linkage tables work? Are you relying on statically resolving the table to an index at link time?

I haven’t looked at your patch yet, but you might find placeholder types and l-value object kinds useful tools for implementing the sorts of restrictions you need on tables:

• Type-checking a DRE for a table as actually having array type seems like it’s going to betray you a lot, because so many things in C and C++ want to decay arrays into pointers. But if you give the DRE a placeholder type instead, you’ll automatically diagnose most uses as failures, and you can selectively handle the cases you want to handle.
• Similarly, you can give table references and subscript expressions on a table a special l-value object kind, and that’ll be useful both in IRGen (when you want to compile them differently) and in Sema (when you want to disallow things like the & operator).
• In your future world with structs and arrays, you can also type-check nested references to arrays and structs using the placeholder type, and accesses into them will also have the special object kind.

[asb]

@rjmccall

Thanks for writing this up.

Thanks for your detailed response and apologies for being slow to get back to you - holidays and a work trip last week intervened.

I think you will need a JumpDiagnostics restriction on local reference variables so that code can’t jump past the initialization. And reference types will be highly restricted; you won’t be able to put them in normal structs or take the address of them.

For JumpDiagnostics - thanks for the pointer. I’m not sure it would be strictly required for support for the initial set of Wasm reftypes, as externref and funcref are both nullable. You’re correct about needing those restrictions in general for reftypes - helpfully marking them as sizeless and adding the additional restriction that you can’t take their address enforces most of the necessary limitations.

The restrictions here on what you can do with a table are very strict; basically, you can’t do anything with the table except use it as the immediate operand to a small number of operations. It’s pretty un-C-like, but that’s the world you’re in, I suppose.

I have a lot of questions about the future directions, especially the structs and arrays proposal; they seem to profoundly affect the necessary design.

• I take it the suggestion here is that you will have tables of structs and arrays, and there will be operations to extract the i th struct element of table element j .

I think there might be some confusion here. The only operations you need to perform on a table directly are get, set, and grow. When WebAssembly gains GC-managed structs and arrays, you will be able to declare that a table can only contain structs/arrays of a given type, but the table get/set/grow operations are the same; struct/array accessors these instructions operate directly on the struct/array in question rather than on a table.

• These struct s are basically not usable elsewhere in the program because they contain reference types, right?

The semantic restrictions stemming from the fact they can’t be stored in linear memory definitely impose a lot of restrictions. But far fewer than for tables. Reftypes can still be passed to or returned from functions, or stored in locals or globals for instance.

• I assume the access restrictions for arrays are basically the same as for tables, except that there’s an access path leading to the array being accessed.

Wasm arrays have the same restrictions as externref and funcref - i.e. can’t store them in linear memory, but can use in function args and store to locals/globals. So much less restricted than tables, that basically need to be converted to fixed integer index (or relocation) for codegen.

Don’t take this analogy too literally, but maybe it helps if you think of tables not so much as a data structure but rather an address space. Like address spaces, the set of tables that a program uses is a compile-time/link-time property of the program. Compare to arrays, where the set of arrays a program might use at run-time is unbounded. Like an address space, a table is memory, but for references (pointers) to externally managed values. While a table is a place you can put a reference to a struct or an array, the struct/array doesn’t live in the table: just the reference to the struct is stored in the table. One struct can be in many tables.

• How much are arrays basically just tables in nested positions? Are they fixed size or resizable, or can they be either?

That’s a really good question that gave me some thought. If you have array types, is it possible you’d look to use them as an alternative to tables? I think the main barriers to this would be:

• The current GC MVP spec doesn’t provide instructions for growing arrays dynamically.
• Code size would be worse, as you’d need to use global.get to first load the array before manipulating it.

How do external-linkage tables work? Are you relying on statically resolving the table to an index at link time?

Yes, the table must be statically resolved at final link time. The linker supports table references, so I’m expecting being able to use relocations for extern tables.

I haven’t looked at your patch yet, but you might find placeholder types and l-value object kinds useful tools for implementing the sorts of restrictions you need on tables:

• Type-checking a DRE for a table as actually having array type seems like it’s going to betray you a lot, because so many things in C and C++ want to decay arrays into pointers. But if you give the DRE a placeholder type instead, you’ll automatically diagnose most uses as failures, and you can selectively handle the cases you want to handle.

Thanks for the suggestion, I’d thought that arrays decaying to pointers would be more of an issue for me, but in practice it wasn’t too bad. Possibly the code could be cleaned up further with a placeholder type though.

• Similarly, you can give table references and subscript expressions on a table a special l-value object kind, and that’ll be useful both in IRGen (when you want to compile them differently) and in Sema (when you want to disallow things like the & operator).

I’ll have to think about this one more. The IR codegen path for tables is actually the same as for C arrays - the backend can determine a table operand is required based on the address spaces used used in the generated IR. Disallowing & on the table itself just required a fairly simple modification to CheckAddressOfOperand.

• In your future world with structs and arrays, you can also type-check nested references to arrays and structs using the placeholder type, and accesses into them will also have the special object kind.

There’s more work to be done on fleshing out handling all the future wasm types in C/C++. It’s relevant to the discussion on tables, but I think somewhat separable due to the fact tables are only used as a simple container. Right now, a new __externref_t type is introduced and funcrefs are represented by C function pointers with a specific attribute.

Does the relationship between tables and reftypes make more sense now? Does that impact any of your suggestions?

Many thanks again for all the input.

[rjmccall]

@asb

For JumpDiagnostics - thanks for the pointer. I’m not sure it would be strictly required for support for the initial set of Wasm reftypes, as externref and funcref are both nullable.

I don’t think we actually have code to insert null initializations on jumps into scopes, but maybe I’m misremembering.

@asb

I think there might be some confusion here. The only operations you need to perform on a table directly are get, set, and grow. When WebAssembly gains GC-managed structs and arrays, you will be able to declare that a table can only contain structs/arrays of a given type, but the table get/set/grow operations are the same; struct/array accessors these instructions operate directly on the struct/array in question rather than on a table.

I see. So you’ll be manipulating these aggregates as first-class values, which presumably means they’ll be fixed size?

@asb

Don’t take this analogy too literally, but maybe it helps if you think of tables not so much as a data structure but rather an address space. Like address spaces, the set of tables that a program uses is a compile-time/link-time property of the program. Compare to arrays, where the set of arrays a program might use at run-time is unbounded. Like an address space, a table is memory, but for references (pointers) to externally managed values. While a table is a place you can put a reference to a struct or an array, the struct/array doesn’t live in the table: just the reference to the struct is stored in the table. One struct can be in many tables.

Er. Are you suggesting that these structs and arrays are stored by reference in the table? And if so, then as references to what? The statement “one struct can be in many tables” is actually very confusing, because it suggests that the struct has some sort of persistent identity — you wouldn’t need to clarify that struct values without identity and with identical components could be stored in multiple tables, because of course they can.

@asb

Thanks for the suggestion, I’d thought that arrays decaying to pointers would be more of an issue for me, but in practice it wasn’t too bad.

There are a lot of corner cases that do this — variadic arguments, that sort of thing.

@asb

I’ll have to think about this one more. The IR codegen path for tables is actually the same as for C arrays - the backend can determine a table operand is required based on the address spaces used used in the generated IR. Disallowing & on the table itself just required a fairly simple modification to CheckAddressOfOperand .

In C++, you can bind references to it, too.

Perhaps the bigger problem is that, if you generate these accesses as just loads from a pointer in LLVM that happens to be a GlobalVariable* in a special address space, you might find yourself fighting LLVM to ensure that it doesn’t optimize things in a way that messes up your ability to do that def analysis on the pointer. I believe there are LLVM optimizations that will do things like merge blocks with a phi if it sees that they differ only by which global variable they use.

@asb

There’s more work to be done on fleshing out handling all the future wasm types in C/C++. It’s relevant to the discussion on tables, but I think somewhat separable due to the fact tables are only used as a simple container. Right now, a new __externref_t type is introduced and funcrefs are represented by C function pointers with a specific attribute.

Well, if you present these as ordinary structs in C, programmers will be able to do things like myTable[i].point.x = 5.0, and you’ll have to compile that. So I want to make sure you’ve thought of what that will look like, in both the AST and in LLVM IR, and are setting the compiler up with representations that don’t have to be completely reworked when you get around to these coming generalizations.

[asb]

@rjmccall

I don’t think we actually have code to insert null initializations on jumps into scopes, but maybe I’m misremembering.

I think for the Wasm case we’re OK here when dealing with nullable references. If a local is allocated for a reference it is initialised to NULL implicitly.

I see. So you’ll be manipulating these aggregates as first-class values, which presumably means they’ll be fixed size?

The structs and arrays introduced by the Wasm GC proposal are types intended to allow you to manipulate structs and arrays stored outside of Wasm’s linear memory (main memory). For instance, they might be stored on the heap of a JS runtime. The precise layout of the struct/array will be opaque to Wasm, hence the new instructions to access fields and indices in these structs and arrays.

Er. Are you suggesting that these structs and arrays are stored by reference in the table? And if so, then as references to what? The statement “one struct can be in many tables” is actually very confusing, because it suggests that the struct has some sort of persistent identity — you wouldn’t need to clarify that struct values without identity and with identical components could be stored in multiple tables, because of course they can.

Hopefully the comment above about these being values on an external heap helps to clarify.

@asb

Thanks for the suggestion, I’d thought that arrays decaying to pointers would be more of an issue for me, but in practice it wasn’t too bad.

There are a lot of corner cases that do this — variadic arguments, that sort of thing.

So, to make sure I’m understanding correctly, the suggestion is to keep the surface syntax of tables as arrays, but introduce a new DeclRefExpr type and handle that in case. I can try that out to see how it works. All the checking I’ve added so far has come down to checking the Type, which presumably would be unmodified?

In C++, you can bind references to it, too.

Yes, the latest revision of the patch adds all the C++ specific semantic restrictions, including references.

Perhaps the bigger problem is that, if you generate these accesses as just loads from a pointer in LLVM that happens to be a GlobalVariable* in a special address space, you might find yourself fighting LLVM to ensure that it doesn’t optimize things in a way that messes up your ability to do that def analysis on the pointer. I believe there are LLVM optimizations that will do things like merge blocks with a phi if it sees that they differ only by which global variable they use.

I could certainly see LLVM passes stripping the addrspace due to a bug, but to do so otherwise would surely be semantically incorrect? It would require changing the clang IR generation codepath, but I don’t think there’s anything stopping us using table.get and table.set intrinsics instead, and therefore never loading/storing to the table “pointer” at the IR level.

@asb

There’s more work to be done on fleshing out handling all the future wasm types in C/C++. It’s relevant to the discussion on tables, but I think somewhat separable due to the fact tables are only used as a simple container. Right now, a new __externref_t type is introduced and funcrefs are represented by C function pointers with a specific attribute.

Well, if you present these as ordinary structs in C, programmers will be able to do things like myTable[i].point.x = 5.0 , and you’ll have to compile that. So I want to make sure you’ve thought of what that will look like, in both the AST and in LLVM IR, and are setting the compiler up with representations that don’t have to be completely reworked when you get around to these coming generalizations.

That’s definitely a fair concern. I’m currently working to flesh out a proposal for representing GC types in IR (and the backend, and to a degree the frontend). The current thought is to do some more extensive downstream experimentation on that work in order to ensure the complete story fits together and avoid the kind of rewriting you point out would be undesirable.

It’s not really ready for full discussion yet (and this thread might not be the best place), but here’s a rough sketch of how the IR could look, assuming the introduction of a wasm_ref type with an associated typeid (or alternatively, further (ab)use of ASIDs on pointers). Fundamentally, there’s a need to provide typeids in a way that survive through to the backend, which uses them to look up full Wasm type data (assumed to be stored in the LLVM module in this case) in order to use it to emit appropriately typed locals, globals, functions etc. An approach that doesn’t require adding another type would involve passing the typeid explicitly as an i32 to any builtins, and storing it as metadata in other places where it’s needed (e.g. globals, function arguments/returns).

@myTable = internal addrspace(1) global [0 x wasm_ref typeid(123)]

define void @example(i32 %i) {
  %p = getelementptr [0 x wasm_ref typeid(123)], [0 x wasm_ref typeid(123] addrspace (1)* @myTable, i32 0, i32 %i
  %struct1 = load wasm_ref typeid(123), wasm_ref typeid(123) addrspace(1)* %p
  %struct2_bare = call wasm_ref @llvm.wasm.struct.get_ref(wasm_ref typeid(123) %struct1, i32 /*fieldidx*/ 3)
  %struct2 = bitcast wasm_ref %struct2_bare to wasm_ref typeid(456)
  call void @llvm.wasm.struct.set_double(wasm_ref typeid(456) %struct2, i32 /*fieldidx*/ 1)
  ret void
}

[rjmccall]

@asb

I think for the Wasm case we’re OK here when dealing with nullable references. If a local is allocated for a reference it is initialised to NULL implicitly.

Okay, so you’re saying that Wasm will implicitly null-initialize the local reference, so you don’t have a specific representational requirement to run initialization code before you access it — the access might fail or go to a stale value (if e.g. the local reference variable is declared within a loop), but that’s not worse than anything else in C.

@asb

The structs and arrays introduced by the Wasm GC proposal are types intended to allow you to manipulate structs and arrays stored outside of Wasm’s linear memory (main memory). For instance, they might be stored on the heap of a JS runtime. The precise layout of the struct/array will be opaque to Wasm, hence the new instructions to access fields and indices in these structs and arrays.

Okay, I think I’m starting to understand what you’re saying here. You have these strongly-typed GC references. Under the base tables proposal, these references are always either to opaque objects (__externref_t) or functions (__funcref). The struct/array proposal adds references to structs (with fixed components) or (dynamically-sized?) arrays, but they’re still just strongly-typed GC references.

@asb

So, to make sure I’m understanding correctly, the suggestion is to keep the surface syntax of tables as arrays, but introduce a new DeclRefExpr type and handle that in case. I can try that out to see how it works. All the checking I’ve added so far has come down to checking the Type , which presumably would be unmodified?

I wouldn’t advise adding a new expression type. I think you should consider using a placeholder type (the type of the reference expression) so that you can very carefully constrain how the resulting value is used.

@asb

I could certainly see LLVM passes stripping the addrspace due to a bug, but to do so otherwise would surely be semantically incorrect?

I’m not talking about stripping the addrspace; as you say, that would be a bug. But the address space number is the same for all references, right? Your code generation relies on being able to track a load or store down back to a specific global variable, not just knowing the address space. So I think you do need to take some level of precaution against optimizations that assume that they can introduce abstraction. Emitting loads and stores with an intrinsic would probably be enough.