RFC: WebAssembly Reference Types in Clang

Clang Frontend
, ,
1

Summary

This proposal describes the addition of WebAssembly Reference Types to Clang. This is largely specific to WebAssembly and I’m not aware of other use cases that might need similar functionality, but the hope of this RFC is to check that assumption and to ensure there are no objections to this approach.

It introduces one type __externref, one keyword __funcref for Function Pointers, and the ability to define arrays of these values with appropriate semantics.

Introduction

The WebAssembly Reference Types proposal introduces two new opaque types: externref and funcref, which are host managed. As such they do not have an in-memory representation, which means that they cannot be stored to WebAssembly linear memory (the default address space in LLVM) or have their address taken. They can however be stored in WebAssembly globals, locals, and used in function parameters and returns.

In the case of funcref, which represents an opaque reference to a function, the only thing we can do from WebAssembly is to call it.

Since reference types cannot be stored to linear memory there’s another structure allowing us to store these types: tables. Tables are the storage structure of reference types, indexed by an integer starting at zero. But they have a few more constraints than reference types. They are module-global objects, can’t be stored into the stack, locals, nor can they be arguments, or return values of functions.

This creates a challenging implementation given that both LLVM and Clang don’t necessarily have support for new types with these constraints and although there are some similarities to ARM SVE’s, they do not have exactly the same set of constraints.

There has been two presentations on this subject in LLVM meetups:

LLVM: Landed

Reference type support is already available in LLVM. Support for both externref, funcref and tables including respective builtins have been added.

LLVM defines 2 MVTs, funcref and externref. These are lowered to the appropriate types. Intrinsics are provided to obtain null reference types. At the LLVM IR level, an externref is a pointer to non-integral address space 10 and a funcref is a pointer to non-integral address space 20.

In LLVM funcrefs are defined as:

%externref = ptr addrspace(10)
%funcref = ptr addrspace(20)

Intrinsics:

  • %externref @llvm_wasm_ref_null_extern()
  • %funcref @llvm_wasm_ref_null_func()
  • i32 @llvm_wasm_is_null_extern(%externref)
  • i32 @llvm_wasm_is_null_func(%funcref)

Tables are global arrays and intrinsics are provided to set, get and operate on tables. Tables live in a different address space, non-integral address space 1. In LLVM IR a table is defined as:

@table = local_unnamed_addr addrspace(1) global [0 x %externref] undef

Intrinsics:

  • void @llvm_wasm_table_set_externref(table, i32, %externref)
  • void @llvm_wasm_table_set_funcref(table, i32, %funcref)
  • %externref @llvm_wasm_table_get_externref(table, i32)
  • %externref @llvm_wasm_table_get_funcref(table, i32)
  • i32 @llvm_wasm_table_size(table)
  • void @llvm_wasm_table_copy(table, table, i32, i32, i32)
  • int @llvm_wasm_table_grow_externref(table, externref, i32)
  • int @llvm_wasm_table_grow_funcref(table, funcref, i32)
  • void @llvm_wasm_table_fill_externref(table, i32, externref, i32)
  • void @llvm_wasm_table_fill_funcref(table, i32, funcref, i32)

Here’s an example of how code to expand/grow a table could be implemented in LLVM IR (for the complete example see Ref-Cpp on GitHub):

@objects = local_unnamed_addr addrspace(1) global [0 x %externref] undef

define void @expand_table() #3 {
  ; get current table size
  %sz = call i32 @llvm.wasm.table.size(i8 addrspace(1)* @objects)
  ; grow the table by (old_size >> 1) + 1.
  %shf = lshr i32 %sz, 1
  %incsize = add nuw i32 %shf, 1
  %null = call %externref @llvm.wasm.ref.null.extern()
  %ret = call i32 @llvm.wasm.table.grow.externref(i8 addrspace(1)* @objects, %externref %null, i32 %incsize)
  ; if growing the table failed, signal the runtime, then abort
  %failed = icmp eq i32 %ret, -1
  br i1 %failed, label %oom, label %good

oom:
  call void @out_of_memory()
  unreachable

good:
  %newsize = add i32 %sz, %incsize
  br label %loophd

loophd:
  %newi = phi i32 [ %newsize, %good ], [ %i, %loopbody]
  %done = icmp eq i32 %newi, %sz
  br i1 %done, label %end, label %loopbody

end:
  ret void

loopbody:
  %i = add i32 %newi, -1
  call void @freelist_push(i32 %i)
  br label %loophd
}

The relevant revisions are:

Clang

The goal has always been to bring this functionality to C/C++ users, i.e. to have WebAssembly Reference Types support in Clang. To implement this in Clang there’s the matter of how to represent these values as syntax to the user, but also how to represent them in the Clang AST and lower them to LLVM.

We propose an implementation available downstream in GitHub and explain some of the design decisions that were taken into consideration.

Surface Syntax

For externref, we have created a new types __externref_t which defines a new object of type externref. For funcref, although initially we had created a new type __funcref_t, from which we would cast, it would mean that the user would have to track the function type properly and do the proper casts. To ease the number of necessary casts, instead we decided to add a new keyword __funcref which is assigned to function pointers to define a new function pointer that’s actually a funcref on the WebAssembly side.

Regarding tables the initial choice and implementation was to have tables be seamless arrays and use subscripting for loads/stores, and builtins for the remaining operations. However, using subscripting for loads/stores turned out to be harder than initially thought (we will go into more details on this in the next section).

Current implementation just defines tables as static arrays of size 0, where the element type is a WebAssembly reference type. The WebAssembly specification allows tables to have a specified initial size and maximum size. This is not currently implemented in Clang or LLVM. We’ll add support for this in the future. Currently, therefore, tables start zero-sized (which means that you’ll need a call to __builtin_wasm_table_grow to add any elements to it) and with no specified maximum size.

An example implementation in C of the above LLVM IR code is (for a full example see Ref-Cpp on GitHub):

typedef __externref_t externref;
static externref objects[0];

static void expand_table (void) {
  size_t old_size = __builtin_wasm_table_size(objects);
  size_t grow = (old_size >> 1) + 1;
  if (__builtin_wasm_table_grow(objects, __builtin_wasm_ref_null_extern(), grow) == -1) {
    out_of_memory();
    __builtin_trap();
  }

  size_t end = __builtin_wasm_table_size(objects);
  while (end != old_size) {
    freelist_push (--end);
  }
}

Implementation

The new type __externref_t is passed through the frontend and lowered in LLVM IR to a ptr addrspace(10).

The __funcref keyword is transformed at parsing time into a QualType in address space 20 (the same as in LLVM IR). However, the downside of this is that to query if a type is a WebAssembly funcref, you need a QualType. A Type is not enough since it will only tell you it’s a function pointer. Otherwise the type is lowered into LLVM IR as a ptr addrspace(20).

Both of these have some semantic restrictions that have been implemented at the frontend level:

  • Can’t be stored to memory
  • Can’t be an argument to sizeof
  • Can’t have their address taken
  • Can’t be fields of structs, classes, etc.
    • Many of those are a consequence of the types not having an in-memory representation and being opaque both at compile and runtime.

Tables were harder to handle. As mentioned earlier the array surface syntax for a table makes sense as does the use of subscripting for load/store. We tried two different alternatives here:

  • Define tables as arrays and subscripting as ArraySubscript but lowering to table_get/set intrinsics in LLVM IR.The problem we faced was that, since the semantics of array subscripting differ in some ways to those of the table, in some cases over-optimization of ArraySubscript caused WebAssembly code to be broken.
  • We attempted then to instead keep the array surface syntax but generate a new AST node TableSubscript. This work is partially completed here. The downside is that the patch is extremely large as implementing a new node means implementing debug information for the node, lowering, implementing all visitor patterns etc.

In order to speed up upstream of reference types, we decided to start with a simpler alternative. Using builtins for table_get and table_set instead of subscripting. This turned out to be much easier to achieve and allowed us to reach a stage where the tests all pass and the patch is not very invasive. We therefore ended up with one builtin on the Clang per each intrinsic on the LLVM side.

Although there’s a large number of builtins, it is more ergonomic than writing inline assembly. It not only provides better integration with C++ but also enables future integrations with the C++ language, like using the array subscript surface syntax for table get/set.

A revision with the implementation can be found in D139010.

Future

We are currently working on the Garbage Collection WebAssembly proposal which added further reference types, besides externref and funcref. These will be host managed / garbage collected types. This will generalize the implementation of externref and funcref, and we see this patch as a step in the right direction. A future RFC will discuss generalizing the current RFC to handle GC types.

3 Likes
2

I’ve collaborated with Paulo on some of these patches so I have an obvious bias here. I did just want to add in a few additional thoughts that might be helpful for review.

  • Firstly, I’ll note that this RFC might at first seem a bit large and covering multiple concerns. I had tried to look at things in a more piecemeal way in my previous RFC on tables, but the feedback was that it’s necessary to see more of the end to end flow to properly comment.
  • I would of course be interested in feedback on any aspect of this, but to my mind the key bits that it would be great to get feedback on are:
    • The implementation approach to ensure further semantic restrictions on externref/funcref. This currently involves marking Wasm reference types as sizeless and adding additional checks for the extra restrictions (e.g. inability to take its address). i.e. right now no generic concept of a “sizeless type that can’t be stored to memory or have its address taken” has been added as it’s not clear it’s useful to generalise it beyond WebAssembly’s needs.
    • Any concerns about using the array surface syntax for declaring Wasm tables.
1 Like