This is an archive of the discontinued LLVM Phabricator instance.

[clang][WebAssembly] Implement support for table types and builtins
ClosedPublic

Authored by pmatos on Nov 30 2022, 5:55 AM.

Details

Summary

This commit implements support for WebAssembly table types and
respective builtins. Table tables are WebAssembly objects to store
reference types. They have a large amount of semantic restrictions
including, but not limited to, only being allowed to be declared
at the top-level as static arrays of zero-length. Not being arguments
or result of functions, not being stored ot memory, etc.

This commit introduces the attribute((wasm_table)) to attach to
arrays of WebAssembly reference types. And the following builtins to
manage tables:

  • ref __builtin_wasm_table_get(table, idx)
  • void __builtin_wasm_table_set(table, idx, ref)
  • uint __builtin_wasm_table_size(table)
  • uint __builtin_wasm_table_grow(table, ref, uint)
  • void __builtin_wasm_table_fill(table, idx, ref, uint)
  • void __builtin_wasm_table_copy(table, table, uint, uint, uint)

This commit also enables reference-types feature at bleeding-edge.

This is joint work with Alex Bradbury (@asb).

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
aaron.ballman added inline comments.Jan 11 2023, 8:09 AM
clang/include/clang/Basic/DiagnosticSemaKinds.td
11869

This is untested. I'll stop commenting on those at this point, please ensure you're testing all diagnostics you've added.

clang/lib/AST/Type.cpp
2377–2382
pmatos updated this revision to Diff 489468.Jan 16 2023, 2:11 AM

Updating tests after some changes to previous diagnostics.

pmatos marked 5 inline comments as done.Jan 18 2023, 8:35 AM
pmatos added inline comments.
clang/include/clang/Basic/DiagnosticSemaKinds.td
2185–2189

Right - this is no longer needed.

3060–3065

Sigh - again. Apologies. This was an initial patch that used matrix subscript to create a table subscript patch but was dropped and therefore is unused.

pmatos marked 2 inline comments as done.Jan 18 2023, 8:36 AM
pmatos updated this revision to Diff 490208.Jan 18 2023, 9:52 AM

Remove some unnecessary diagnostics.

pmatos marked 2 inline comments as done.Jan 23 2023, 5:47 AM
pmatos added inline comments.
clang/include/clang/Basic/DiagnosticSemaKinds.td
11872

Yes, the next phase of this work is to implement this together with element section to initialize tables.

asb added inline comments.Jan 23 2023, 5:52 AM
clang/include/clang/Basic/DiagnosticSemaKinds.td
11902

The whack-a-mole aspect of disallowing table uses is something I'm not fond of either....but I'm not sure I see a better approach. Do you have any alternatives in mind?

pmatos updated this revision to Diff 491353.Jan 23 2023, 6:47 AM
pmatos marked 7 inline comments as done.

Address more comments.

pmatos updated this revision to Diff 491468.Jan 23 2023, 11:34 AM

Fix some tests whose diagnostics changed

pmatos updated this revision to Diff 491608.Jan 23 2023, 11:11 PM

Finish fixing tests after dianostic message changes

pmatos updated this revision to Diff 491707.Jan 24 2023, 4:01 AM

Further tests for use of tables in conditional branches.

pmatos updated this revision to Diff 491784.Jan 24 2023, 7:19 AM

Simplify and add tests for remaining diagnostics

pmatos marked an inline comment as done.Jan 24 2023, 7:19 AM
pmatos marked an inline comment as done.Jan 24 2023, 7:32 AM
pmatos added inline comments.
clang/include/clang/Basic/DiagnosticSemaKinds.td
11902

A couple concrete answers in addition to what @asb already said.

  • I don't think we can use tables at the moment in conditional explicit clause. Indeed it doesn't make sense since there's no what, at the moment, to statically initialize the table.
  • Tables are thread local. Indeed, threads in WebAssembly share only linear memory so anything that's not in linear memory is thread local. This is true for tables but also for all reference types.
pmatos updated this revision to Diff 491790.Jan 24 2023, 7:33 AM

Add missing newline at end of file.

@aaron.ballman Thanks for all the comments, I have now finished addressing those. What do you think of the current patch?

pmatos updated this revision to Diff 493264.Jan 30 2023, 3:32 AM

Rebase on main and fix a test diagnostic expectation.

pmatos updated this revision to Diff 497633.Feb 15 2023, 4:21 AM

Rebased on current HEAD.

aaron.ballman added inline comments.
clang/include/clang/AST/Stmt.h
456 ↗(On Diff #497633)

I am not certain what AMT stands for -- you might need some comments to explain what this stands for.

clang/include/clang/Basic/DiagnosticSemaKinds.td
11902

The whack-a-mole aspect of disallowing table uses is something I'm not fond of either....but I'm not sure I see a better approach. Do you have any alternatives in mind?

I don't have good ideas off the top of my head, but this is a lot of overhead for the feature so my default idea is "don't add this type to the compiler" which may not help all that much. Do you have evidence that this type is necessary, will have enough uses in the wild to justify adding it, and is not possible to make it more regular?

pmatos updated this revision to Diff 501110.Feb 28 2023, 5:47 AM
pmatos marked an inline comment as done.

Address the comments.

pmatos marked 3 inline comments as done.Feb 28 2023, 5:51 AM
pmatos added inline comments.
clang/include/clang/AST/Stmt.h
456 ↗(On Diff #497633)

Ah yes, somehow I missed this. I renamed this at some point with an application in mind and then didn't use it. So renamed back.

AMT was supposed to be Array / Matrix / Table.

clang/include/clang/Basic/DiagnosticSemaKinds.td
11902

The whack-a-mole aspect of disallowing table uses is something I'm not fond of either....but I'm not sure I see a better approach. Do you have any alternatives in mind?

I don't have good ideas off the top of my head, but this is a lot of overhead for the feature so my default idea is "don't add this type to the compiler" which may not help all that much. Do you have evidence that this type is necessary, will have enough uses in the wild to justify adding it, and is not possible to make it more regular?

A table is a container for reference types - i.e. externref, funcref and others in the future and an essential part of WebAssembly. I don't see how we can compile down to tables unless we enforce these constraints at this level. I wish there was a way of providing the same functionality without needing to add all these extra checks (and would welcome alternate suggestions!), but this is the only path forwards we've been able to find..

aaron.ballman added a subscriber: jfb.

Roping in @jfb because I know he's been heavily involve in WebAssembly in the past and he may have ideas/opinions.

High-level question: are externref, funcref, and table types all part of the WebAssembly standard, or are these extensions? (I wasn't aware that WebAssembly was a W3C standard or I'd have been asking this question much earlier -- sorry for that! I'm asking in regards to #4 in https://clang.llvm.org/get_involved.html#criteria)

pmatos updated this revision to Diff 501143.Feb 28 2023, 7:50 AM
pmatos marked an inline comment as done.

Address comments regarding tables and remove some unused code.

Roping in @jfb because I know he's been heavily involve in WebAssembly in the past and he may have ideas/opinions.

High-level question: are externref, funcref, and table types all part of the WebAssembly standard, or are these extensions? (I wasn't aware that WebAssembly was a W3C standard or I'd have been asking this question much earlier -- sorry for that! I'm asking in regards to #4 in https://clang.llvm.org/get_involved.html#criteria)

Yes, these features are all present in the WebAssembly standard: https://www.w3.org/TR/2022/WD-wasm-core-2-20220419/syntax/types.html#table-types

Roping in @jfb because I know he's been heavily involve in WebAssembly in the past and he may have ideas/opinions.

High-level question: are externref, funcref, and table types all part of the WebAssembly standard, or are these extensions? (I wasn't aware that WebAssembly was a W3C standard or I'd have been asking this question much earlier -- sorry for that! I'm asking in regards to #4 in https://clang.llvm.org/get_involved.html#criteria)

Yes, these features are all present in the WebAssembly standard: https://www.w3.org/TR/2022/WD-wasm-core-2-20220419/syntax/types.html#table-types

Thank you, that resolves any concerns I had about whether this met our usual extension criteria. I'm still uncomfortable with the type though because... it doesn't behave like anything else in the type system. I asked some questions on the test cases, and maybe knowing those answers will help me wrap my head around the design of the type.

clang/test/SemaCXX/wasm-refs-and-tables.cpp
17–18

This seems really... confused. We can't form a pointer to the type, but we can form an array of the type (which decays into a pointer when you sneeze near it, and it's not clear whether that should be allowed or not) so long as it's a zero-length array (which is an extension in C and C++, so do we need to silence pedantic warnings in WASM for this?).

89
96
103

This involves array to pointer decay, so we're forming a pointer to the table here. Why is this pointer fine but others are not?

pmatos updated this revision to Diff 506499.Mar 20 2023, 1:47 AM

Rebase on main.

pmatos updated this revision to Diff 506521.Mar 20 2023, 3:24 AM

Remove references to table subscript. Simplify patch.

pmatos updated this revision to Diff 506552.Mar 20 2023, 5:35 AM
pmatos marked 4 inline comments as done.

Address concerns about table subscripting. Add warnings for that.

Address a few other smaller comments like testing for table comparisons.

clang/test/SemaCXX/wasm-refs-and-tables.cpp
17–18

As it stands, tables are declared as static arrays of size zero. Then to access them we need to use builtins. No subscripting, no comparison, no pointer decay, etc. No passing into functions, returning from functions, etc. Nothing besides using them as arguments to wasm_table... builtins.

89

No comparisons are allowed - I have added a few tests to that effect.

96

(void)table; is allowed.

103

I have disallowed this to avoid the problems you mention. Table set happens only through the builtin wasm_table_set.

@aaron.ballman Any further comments on this?

This will also need someone from the LLVM side to look at the LLVM-specific changes. Most of my comments were focused on the behavior of test cases, but there may be more comments coming for the code changes once I've got a better handle on the test behavior.

clang/include/clang/Basic/BuiltinsWebAssembly.def
205–210

All of these should be documented in docs/LanguageExtensions.rst (you can make a Web Assembly section if one doesn't already exist; we've historically been bad about documenting our builtins).

clang/test/Sema/builtins-wasm.c
13–14

Instead of relying on assignment diagnostics to test the return type of the call, why not use the language? (Same can be used for the other, similar tests.)

#define EXPR_HAS_TYPE(expr, type) _Generic((expr), type : 1, default : 0)

_Static_assert(EXPR_HAS_TYPE(__builtin_wasm_table_size(table), int), "");
22

I can't make sense of this diagnostic -- what is the element type of the web assembly table in the 1st argument? Why is the second argument needed at all if it needs to be derived from the type of the first argument and these things don't represent values (due to being zero-sized)?

33

Similar question here about the third argument.

clang/test/Sema/wasm-refs-and-tables.c
18

So why is extern __externref_t r2; allowed? Is it because it's not an array declaration?

22–24

For completeness (should just work)

49

How about:

void foo(__externref_t table[0]);

I'd expect this to also not be allowed (that's just a fancy spelling for a weird pointer).

82

Shouldn't this be in builtins-wasm.c instead?

84–85

This needs some further test cases for situations where the declaration isn't at the top level of the function. e.g.,

void foo() {
  static __externref_t t[0]; // error
  {
    static __externref_t t2[0]; // error
    for (;;) {
      static __externref_t t3[0]; // error
    }
  }
  int i = ({ static __externref_t t4[0]; /* error, I presume? */ 1;});
}

and also a C++ test involving lambdas (we should probably also cover blocks in C, I suppose).

105

Please don't hate me, but... what about:

int i = 0;
__externref_t oh_no_vlas[i];
clang/test/SemaCXX/wasm-refs-and-tables.cpp
7–8

Much of this file is the same test coverage as in the C case; I'd recommend combining the .c and .cpp files into one test with two RUN lines, and use -verify=whatever to distinguish between C vs C++ vs both diagnostic behaviors. The C++ specific code can then be split into a much smaller .cpp-specific file.

15

Anywhere you'd testing pointer behavior for C++, you should have a test with an lvalue reference as well. I presume those will behave the same as pointers? It'd probably be wise to have tests for rvalue references as well.

17–18

Okay, that's less confused now, thank you! What should the -pedantic behavior be for this:

static __externref_t table[0];

I presume you don't want the usual "zero size arrays are an extension" warning?

119

We should probably have a test for co_return behavior as well?

pmatos marked an inline comment as done.Apr 21 2023, 5:23 AM
pmatos added inline comments.
clang/test/Sema/builtins-wasm.c
13–14

OK - I will apply those changes. I hadn't seen this way of doing this before. Thanks.

22

The element type needs to be a reference type. Either an externref or a funcref. So, if we have a table of externref, the second element needs to have that type because it's the element we are growing the table with. The element is needed because it's what we'll use to fill the table with.

Well... they do represent values, just not values that exist on webassembly module. They are host values. They are for example javascript strings, or numbers, or objects of any kind. They are just opaque in the webassembly module but if retrieved by the javascript side they are just normal sized objects.

33

Exactly the same story as above.

pmatos updated this revision to Diff 517166.Apr 26 2023, 7:32 AM
pmatos marked 3 inline comments as done.

Fix Wasm table tests.

Thanks for the comments - I am working on addressing these at the moment.
The LLVM part of the patch is just some refactoring and therefore should be pretty trivial, pinging @tlively in case he has some time.

clang/test/Sema/wasm-refs-and-tables.c
18

I am not sure I understand the question. The externref value can be declared in another module and here we just define that. Array declarations of externref just define tables of externref values.

49

That's correct, that's not allowed. Added the test case.

105

:) Test added.

pmatos updated this revision to Diff 517478.Apr 27 2023, 1:23 AM
pmatos marked 6 inline comments as done.

Complete fixing tests.

aaron.ballman added inline comments.Apr 27 2023, 4:53 AM
clang/test/Sema/wasm-refs-and-tables.c
18

Thanks, that helps explain my confusion (boy, I *really* do not like these types; they are quite unintuitive). What was confusing me here is that __externref_t t7[0]; fails because the declaration doesn't declare a static identifier (yet, in C, it doesn't declare *anything at all* because it an array of zero elements of a sizeless type) while extern __externref_t r2; is fine despite not declaring a static identifier (yet, in C, it also doesn't declare *anything at all* because it's a sizeless type). I don't think there's anything to be done about this, the design is what it is in the WebAssembly standard, but all of my discomfort stems around how deeply weird this design is (and it shows with just how much effort we have to go to in order to restrict all the various ways you can use these identifiers).

pmatos marked 2 inline comments as done.Apr 27 2023, 5:35 AM
pmatos added inline comments.
clang/include/clang/Basic/BuiltinsWebAssembly.def
205–210

Working on this - thanks for the reminder.

clang/test/SemaCXX/wasm-refs-and-tables.cpp
7–8

I have don't this know. I was not aware we could pass an argument to verify - thanks.

15

Here I guess you're talking about testing __externref_t &. However, this might be outside the scope of the patch which deals only with tables.

I could add further lvalue and rvalue reference tests to externref and funcref in another patch. What do you think?

17–18

I have fixed this but unsure how to best merge it with the remainder of the tests, so created a new test file.

pmatos updated this revision to Diff 517521.Apr 27 2023, 5:36 AM
pmatos marked 2 inline comments as done.

Update a few more tests.

pmatos marked an inline comment as done.Apr 27 2023, 5:38 AM
pmatos added inline comments.
clang/test/Sema/wasm-refs-and-tables.c
18

Yes, I understand.

pmatos updated this revision to Diff 517525.Apr 27 2023, 5:39 AM
pmatos marked an inline comment as done.

Quick fixup of test.

pmatos added inline comments.Apr 27 2023, 5:41 AM
clang/test/SemaCXX/wasm-refs-and-tables.cpp
36

@aaron.ballman I tried and failed to create a good testcase for co_return. However creating coroutines seems to be an stdlib thing which I am not sure how to test here. Do you have any suggestions here?

pmatos updated this revision to Diff 517535.Apr 27 2023, 6:13 AM

Add documentation for table builtins.

pmatos marked an inline comment as done.Apr 27 2023, 6:14 AM

I think we are almost there. @aaron.ballman what do you think?

clang/test/Sema/wasm-refs-and-tables.c
82

Moved.

pmatos marked an inline comment as done.May 15 2023, 6:52 AM

@tlively @aaron.ballman pinging both to get final reviews on the LLVM and Clang parts respectively. It would be great to have this merged soon.

Thanks for the ping, will take a look.

It looks like the LLVM-side changes are generally moving Wasm type classification functions to a more global location. Since no other backend should care about these things, it would be better if we could get away without these changes.

llvm/include/llvm/IR/Type.h
23 ↗(On Diff #517535)

I don't know if things in IR are supposed to depend on things in CodeGen. Is there precedent here?

220–232 ↗(On Diff #517535)

Do these need to be in Type.h? If not, it would be good to keep them in a more Wasm-specific location.

pmatos updated this revision to Diff 523741.May 19 2023, 5:31 AM

Remove modifications from Type.h and move them to WebAssembly files.

It looks like the LLVM-side changes are generally moving Wasm type classification functions to a more global location. Since no other backend should care about these things, it would be better if we could get away without these changes.

@tlively Fortunately, this is not needed anymore. Thanks for pointing it out. At some point it was due to dependencies from Clang code which used the predicates from LLVM and we couldn't include the WebAssembly backend there so it was easier to have them in llvm Type.h. But that code was refactored and I could move the LLVM predicates back to the backend files. How does it look like now?

aaron.ballman added inline comments.May 19 2023, 6:49 AM
clang/docs/LanguageExtensions.rst
2328

This sounds like any reference type will work, e.g.,

static __externref_t table[0];
void func(int i) {
  int &ref = i;
  __builtin_wasm_table_set(table, i, ref);
}

so might want to say "value of `_externref_t` type" instead?

2331–2332

Sphinx will bark otherwise.

2343
2349–2350

Sphinx will bark otherwise.

2361

Returns an int? size_t? Something else?

2364–2365
2380

Same suggestion here as above regarding arbitrary reference types.

2385–2386
2400–2401

Same suggestion here as above regarding arbitrary reference types.

2404–2405

What happens if the range is invalid for the table size? e.g., the user never called __builtin_wasm_table_grow before calling __builtin_wasm_table_fill?

2407–2408
2425

Similar question here as above -- what happens when the range given is invalid for either one or both of the table arguments?

clang/test/SemaCXX/wasm-refs-and-tables.cpp
36
#include "Inputs/std-coroutine.h"

using std::suspend_always;

struct promise_table {
  __externref_t[] get_return_object();
  suspend_always initial_suspend();
  suspend_always final_suspend() noexcept;
  void return_value(__externref_t[]);
  void unhandled_exception();
};

template <typename... T>
struct std::coroutine_traits<__externref_t[], T...> { using promise_type = promise_table; };

static __externref_t table[0];
__externref_t[] func() {
  co_return table; // Cannot return a WebAssembly table?
}

Perhaps something along these lines?

llvm/include/llvm/CodeGen/WasmAddressSpaces.h
49

Still need to add this newline back, btw.

pmatos updated this revision to Diff 524710.May 23 2023, 7:41 AM
pmatos marked 8 inline comments as done.

Address remaining comments.

Make table.size builtin return size_t.
Still remaining to be address is co_return on tables.

pmatos added inline comments.May 23 2023, 7:45 AM
clang/docs/LanguageExtensions.rst
2328

Any reference type will work, i.e. externref or funcref. You can also store funcrefs in a wasm table. But of course, it needs to be well-typed. You cannot store a funcref value in an externref table and vice-versa.

2361

Good point, should actually be size_t. Will change that and clarify in the documentation.

2380

Same situation as above. These builtins can get any reference type, as long as they match the table element type.

2400–2401

Same as above.

2404–2405

The host executing the WebAssembly instance will trap. This is part of the WebAssembly spec.

2425

Trap on the host.

clang/test/SemaCXX/wasm-refs-and-tables.cpp
36

But you cannot write promise_table because a table cannot be an argument in return_value. Also, you cannot return a table in get_return_object. Doesn't this invalidate straight away the use of a table with co-routines?

aaron.ballman added inline comments.May 25 2023, 6:09 AM
clang/docs/LanguageExtensions.rst
2328

My point is more that "any reference type" suggests you can use an arbitrary C++ reference type like int & and I think we mean something more specific than that, right?

2404–2405

Hmmm, do you think we should mention that here? Alternatively, should we have a link to other WebAssembly documentation so we can say "see <blah> for more details?" to avoid replicating docs too much?

clang/test/SemaCXX/wasm-refs-and-tables.cpp
36

Ah! Yeah, I think that does. Okay, let's punt on coroutines, that's turning out to be a slog.

pmatos marked 3 inline comments as done.May 29 2023, 4:30 AM
pmatos added inline comments.
clang/docs/LanguageExtensions.rst
2328

Yes, of course, I always mean a WebAssembly reference type in this context.

2404–2405

Good idea. I will handle that.

clang/test/SemaCXX/wasm-refs-and-tables.cpp
36

OK - thanks.

pmatos updated this revision to Diff 526436.May 29 2023, 6:20 AM
pmatos marked an inline comment as done.

Address the comments wrt the documentation. Added link to Wasm spec.

@aaron.ballman What do you think? I added the reference to the top level of the WebAssembly section, rather than to the documentation in each builtin since it makes more sense imo.

pmatos updated this revision to Diff 526539.May 30 2023, 12:54 AM

Remove test portion attempting to test coroutines.

pmatos updated this revision to Diff 526578.May 30 2023, 4:41 AM

Apply clang-format.

aaron.ballman accepted this revision.Jun 6 2023, 10:54 AM

Spotted a typo in the docs, but otherwise LGTM (thanks for your patience while I was out last week).

clang/docs/LanguageExtensions.rst
2321
2328

Thanks for the clarifying note!

This revision is now accepted and ready to land.Jun 6 2023, 10:54 AM

Spotted a typo in the docs, but otherwise LGTM (thanks for your patience while I was out last week).

Thanks for your time one this.

This revision was landed with ongoing or failed builds.Jun 10 2023, 6:53 AM
This revision was automatically updated to reflect the committed changes.
clang/test/SemaCXX/wasm-refs-and-tables.cpp