Initial multivalue support by tlively · Pull Request #2675 · WebAssembly/binaryen

tlively · 2020-02-29T00:09:02Z

Adds binary and s-expression parsing and printing for first-class tuple types for representing multivalue constructs. Tuples are created with the new tuple.make pseudoinstruction and their elements can be extracted with the new tuple.extract pseudoinstruction. They can also be stored in locals, which are declared with a new nonstandard type syntax.

Simple multivalue functions can be round-tripped between binary and text formats, although the number of locals increases on each trip. Future work includes Stack IR optimizations to reduce the number of locals emitted, more robust tests, and C/JS API inclusion.

TODO: - Add feature flag - Extend interpreter to handle tuple values - Validation - Check whether implemented for Precompute - C and JS API support/testing - Test parsing and printing Follow ups: - Figure out how to lower in stack IR - Multivalue decoding support - Fuzzing

kripken

Nice work!

kripken · 2020-03-02T19:56:01Z

src/ir/module-utils.h

      TypeCounter(Counts& counts) : counts(counts) {}

      void visitCallIndirect(CallIndirect* curr) { counts[curr->sig]++; }
+      void visitBlock(Block* curr) {


why not loops and ifs? and is this necessary for tuples?

It is possibly also needed for loops and ifs. I'll have to do more extensive testing of those.

Is your second question referring to tuple-typed locals? Those don't need a signature in the type section for either binaries or the text format.

I'd guess loops and ifs are needed - would be odd if there's an asymmetry there, but i might be missing something...

The second question was just that I wasn't sure if this PR was just tuples or not, but I guess not?

Is the reason if and loop were omitted that because loops and ifs contain an internal block whose signature will be the same as that of loop or if's?

Yes, although now that I think about it, there could be loops or ifs that contain single expressions that are not blocks.

This PR previously made a half-hearted attempt at supporting multivalue control flow, but now I'm going all in on it.

kripken · 2020-03-02T20:00:15Z

src/passes/Print.cpp

  return printName(name, o);
 }

+struct LocalType {


it's not obvious to me how printing a local's type differs from a type in general - perhaps add a comment?

No commas in s-expressions. I'll add a comment.

Is there a reason local types should be printed without commas, unlike other types? Not against it, but curious.

The s-expression parser doesn't interpret commas, so after parsing we would end up with individual type strings with commas in them, which would be annoying. It's also better not to have commas for consistency with the rest of the text format.

Sorry, then what is the 'default format' that's with commas and where is it used?

The default format looks like (i32, i64) and it's used for printing types in debugging messages and similar things. We could change the default format to get rid of the comma, but I like having the comma.

src/wasm-interpreter.h

kripken · 2020-03-02T20:08:36Z

src/passes/Precompute.cpp

    // try to evaluate this into a const
    Flow flow = precomputeExpression(curr);
-    if (flow.value.type.isVector()) {
+    if (flow.getValue().type.isVector()) {


Would a multivalue instruction trap in the call to precomputeExpression? If yes, maybe we can add a TODO to optimize those in this pass. If no, these getValue()s might fail?

No, a multivalue instruction wouldn't necessarily trap. I'll add a check and a TODO for handling multivalues here in the future.

src/wasm-stack.h

kripken · 2020-03-02T23:32:47Z

src/wasm/wasm-stack.cpp


 namespace wasm {

+void BinaryInstWriter::emitBlockType(Type type) {


the name suggests it's just for Blocks, how about emitControlFlowType? or maybe emitGeneralType? (but not sure that's a good name for "might be non-single")

How about emitResultType?

sgtm, better than the others for sure.

src/wasm/wasm-stack.cpp

src/wasm/wasm.cpp

aheejin

Nice! Haven't read until the end yet, but some comments:

aheejin · 2020-03-03T01:50:40Z

src/ir/module-utils.h

      void visitCallIndirect(CallIndirect* curr) { counts[curr->sig]++; }
+      void visitBlock(Block* curr) {
+        if (curr->type.isMulti()) {
+          counts[Signature(Type::none, curr->type)]++;


So basically this assumes currently blocks cannot take values yet and only return multivalues, right? It would be clearer to say that in the comment.

I'll add a TODO for this.

src/passes/Print.cpp

aheejin · 2020-03-03T02:18:46Z

src/passes/Print.cpp

  return printName(name, o);
 }

+struct LocalType {


Is there a reason local types should be printed without commas, unlike other types? Not against it, but curious.

src/wasm-interpreter.h

aheejin · 2020-03-03T02:22:39Z

src/wasm-interpreter.h

  Name breakTo; // if non-null, a break is going on

+  Literal& getValue() {
+    assert(values.size() == 1);


In which case do we need multiple values in values? Why is it restricted to size 1? A TODO comment or something can be helpful.

We need multiple values in the flow to handle the case where a tuple.make or a multivalue function call is interpreted. For most cases, the interpreter can assume due to validation that there is only a single value in the flow, so those cases can use this helper function instead of having to examine values directly. I'm open to other opinions on how this could be made cleaner.

I see. How about getSingleValue? I've seen this naming several times in LLVM, e.g. getSinglePredecessor, that returns a meaningful value only when there is a single value. And also a comment will be helpful, saying that this function is a helper function that only works when there is a single value.

src/wasm-stack.h

aheejin · 2020-03-03T22:29:54Z

src/ir/module-utils.h

      TypeCounter(Counts& counts) : counts(counts) {}

      void visitCallIndirect(CallIndirect* curr) { counts[curr->sig]++; }
+      void visitBlock(Block* curr) {


Is the reason if and loop were omitted that because loops and ifs contain an internal block whose signature will be the same as that of loop or if's?

aheejin · 2020-03-03T23:04:56Z

src/passes/Print.cpp

  return printName(name, o);
 }

+struct LocalType {


Sorry, then what is the 'default format' that's with commas and where is it used?

aheejin · 2020-03-03T23:15:13Z

src/wasm-interpreter.h

  Name breakTo; // if non-null, a break is going on

+  Literal& getValue() {
+    assert(values.size() == 1);


I see. How about getSingleValue? I've seen this naming several times in LLVM, e.g. getSinglePredecessor, that returns a meaningful value only when there is a single value. And also a comment will be helpful, saying that this function is a helper function that only works when there is a single value.

aheejin · 2020-03-03T23:19:07Z

src/wasm/wasm-binary.cpp


 Type WasmBinaryBuilder::getType() {
  int type = getS32LEB();
+  if (type >= 0) {


Maybe then a comment saying all single type immediates are negative will be good enough.

aheejin · 2020-03-04T00:39:54Z

src/wasm/wasm-s-parser.cpp

-      results.push_back(parseResults(curr));
+      for (auto result : parseResults(curr)) {
+        results.push_back(result);
+      }


I wonder why we need an extra inner for loop here? I think this is the same situation as params, which also can have multiple types, and parseParamOfLocal call above does not need one.

You're right, I can use insert here as well 👍

aheejin · 2020-03-04T00:44:59Z

test/binaryen.js/event.js


 var module = new binaryen.Module();
-module.setFeatures(binaryen.Features.ExceptionHandling);
+module.setFeatures(binaryen.Features.ExceptionHandling | binaryen.Features.Multivalue);


Why? If it's because the EH proposal depends on multivalue, that's the same for the reference types I think. This file only tests events (not EH instructions) so this uses neither though.

I made it so that multivalue events specifically require multivalue to be enabled in addition to exceptions. This file does have a multivalue event type, even though it is not used.

aheejin · 2020-03-04T01:16:56Z

src/wasm/wasm-validator.cpp

+  if (curr->ifFalse->type != Type::unreachable) {
+    shouldBeTrue(
+      curr->ifFalse->type.isSingle(), curr, "select value may not be a tuple");
+  }


What are the complexities for multivalue select that's not the case for ifs? Then do we have a plan to support multivalue select later? Their encoding is different, i.e., a vector of types, but technically it support multivalue right? If we have a plan to support that how about adding a TODO comment?

I do not plan to support tuples with the MVP select. (Although I think the new type-parameterized select will be able to handle them). The lowering would require scratch registers for the condition and for almost all elements of each tuple, so I think it's just not worth it.

aheejin · 2020-03-04T01:22:20Z

src/wasm/wasm-validator.cpp

+    shouldBeTrue(!curr->sig.results.isMulti(),
+                 curr->body,
+                 "Multivalue function results (multivalue is not enabled)");
+  }


This can be written without double negatives:

if (curr->sig.results.isMulti()) { shouldBeTrue(getModule()->features.hasMultiValue(), ...); }

which seems to be the way other functions are written.

aheejin · 2020-03-04T01:35:33Z

src/wasm/wasm-stack.cpp

 void BinaryInstWriter::visitLocalSet(LocalSet* curr) {
-  o << int8_t(curr->isTee() ? BinaryConsts::LocalTee : BinaryConsts::LocalSet)
-    << U32LEB(mappedLocals[std::make_pair(curr->index, 0)]);
+  size_t numLocals = func->getLocalType(curr->index).size();


Nit: How about numValues? This is one local and you used numValues in visitLocalGet above.

aheejin · 2020-03-04T10:04:50Z

test/unit/test_features.py


 class FeatureValidationTest(utils.BinaryenTestCase):
-    def check_feature(self, module, error, flag):
+    def check_feature(self, module, error, flag, const_flags=[]):


What is const_flags?

flags that are present whether or not the feature under test is turned on. Another name might be invariable_flags, but that's kind of long.

Oh, good idea.

aheejin · 2020-03-04T17:34:25Z

Oh btw does this support emission of stack IR? I don't see that part of the code, so.. (not optimization but just emission)

tlively · 2020-03-05T00:41:21Z

Oh btw does this support emission of stack IR? I don't see that part of the code, so.. (not optimization but just emission)

It does not. I wanted to get basic binary emitting working first. I suspect that I will have to move the lowering logic for drops, local.get, etc. in order to get it working for Stack IR as well.

aheejin · 2020-03-05T07:49:39Z

src/wasm/wasm-s-parser.cpp

-    results.push_back(parseResults(*s[i++]));
+    for (auto result : parseResults(*s[i++])) {
+      results.push_back(result);
+    }


I guess we don't need a inner loop here either because parseResults returns a vector? (The loop above for newParams also can use insert I think)

I'll remove this loop, but the loop above projects p.type before pushing, so it can't easily be removed.

aheejin · 2020-03-05T08:40:18Z

test/unit/test_features.py


 class FeatureValidationTest(utils.BinaryenTestCase):
-    def check_feature(self, module, error, flag):
+    def check_feature(self, module, error, flag, const_flags=[]):


Oh, good idea.

tlively · 2020-03-05T21:36:10Z

Thanks, @aheejin! @kripken, do you want to take another look before I merge this?

kripken · 2020-03-05T22:31:25Z

src/wasm/wasm-binary.cpp

      BYN_TRACE("== popping unreachable from polymorphic stack" << std::endl);
      return allocator.alloc<Unreachable>();
    }
+    assert(false);


old debugging code that needs to be removed?

tlively added 6 commits February 28, 2020 15:48

Handle tuples in interpreter

e40df26

multivalue binary reading and writing

1c1c9c7

Printing and sexp parsing

065d36f

misc fixes and tests

ec09c72

Format

8883e96

tlively requested review from aheejin and kripken February 29, 2020 00:09

tlively added 4 commits February 28, 2020 16:27

Make test more interesting, remove stale todo

d99dc40

Remove obsolete spec test

7adb7f3

Fix and test multivalue block type parsing

f85c0b0

Add multivalue feature to event.js

5f7558a

kripken reviewed Mar 2, 2020

View reviewed changes

Address comments

bd11c3d

aheejin reviewed Mar 3, 2020

View reviewed changes

tlively added 2 commits March 3, 2020 11:31

Refactor wasm-binary.cpp changes

0dadc53

Address more comments and fix bugs

977e99e

aheejin reviewed Mar 4, 2020

View reviewed changes

tlively added 2 commits March 4, 2020 16:42

Address comments and fix/test control flow

fdbdf2b

Finish rename getValue => getSingleValue

fbe4807

aheejin approved these changes Mar 5, 2020

View reviewed changes

Remove loop

98833bc

kripken approved these changes Mar 5, 2020

View reviewed changes

Remove old debug assert

316b680

tlively merged commit 9e3dbb1 into WebAssembly:master Mar 5, 2020

tlively deleted the tuples branch March 5, 2020 23:52

aheejin mentioned this pull request Jan 7, 2021

[GC] Fix parsing/printing of ref types using i31 #3469

Merged


		namespace wasm {

		void BinaryInstWriter::emitBlockType(Type type) {

Conversation

tlively commented Feb 29, 2020

Uh oh!

kripken left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

aheejin left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!