You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
This repository was archived by the owner on Nov 3, 2021. It is now read-only.
Repository navigation
This repository was archived by the owner on Nov 3, 2021. It is now read-only.
Why is nullref not allowed in binary and text format? #60
This makes writing transformation passes in toolchain somewhat tricky. I'm not necessarily arguing for allowing it at this point, but I don't precisely remember what the reason for disallowing that was.
In the first version of the proposal nullref was available. Removing it was a form of compromise, because there was some dislike of having this type. I am not sure what the arguments were. If you have a good use case, we can discuss bringing it back. It would be an easy change.
It is mostly that block/loop/if/try doesn't have self-sufficient type information within itself. For example,
(block (type ???)
(ref.null)
)
When we create this block, we don't know which type to assign to this block, because we cannot assign nullref. We cannot arbitrarily promote this to exnref/funcref/anyref before we see the the parent node (in wast format) / the next instruction. In real transformations we wouldn't create a block like that out of nowhere, but transformations can split/merge blocks and create/delete instructions within them, and we don't have the ability to calculate the type of block/loop/... only by examining it and its child nodes anymore. It's not that this restriction makes transformations not possible, but they can be trickier.
For a number of tooling purposes, you should ensure that every instruction has a principal output type for any given input type. For ref.null, that seems to necessitate the nullref type. So the options seem to be either to add nullref or to parameterize ref.null with an argument that indicates which reference type the output type should be.
Some languages, among which Scala, even have a user-space Null type, which can be the declared result type of a function. For example in Scala the following code is valid:
When compiling giveMeNull() to wasm, the only valid result type for giveMeNull() would be nullref. If we cannot express it in the binary or text format, we have to resort to weird encodings.
Yep, though that's more relevant to the GC proposal (where it's planned to be addressed). Nonetheless, it's a good point that something like nullref will be needed eventually anyways, and the option to parameterize ref.null will likely be insuffucient down the line.
Just to clarify, the proposal already includes a nullref type, for the reasons @RossTate mentions. The question @aheejin is asking is whether it should be expressible in concrete syntax. As mentioned above, that was the case originally, but there was some resistance, so it was removed. I'm all for bringing it back if we can get consensus on that.
Reacted by Ross Tate, Derek Schuff, Thomas Lively, Heejin Ahn, Alon Zakai and Slava Kuzmich
I found some relevant previous discussion threads: thread1thread2
@lukewagner Are there advantages specific to allowing nullref but making it not representable in text or binary format? The threads discuss mostly about whether we need nullref or not and whether we should have a separate null instruction for each reference type, but I'm not sure if I fully understand the advantages of making nullref not writable while having it as a validation type.
Keeping nullref out of the binary format isn't really the goal; the goal was to avoid having to deal with the annoyance of having to add nullref support for locals, globals, params, returns, tables and, in the future, elems and fields. It's all doable, of course, but kindof annoying, especially if you start wondering whether we'll eventually need to "optimize" nullref (instead of simply representing it as a null pointer).
the goal was to avoid having to deal with the annoyance of having to add nullref support for locals, globals, params, returns, tables and, in the future, elems and fields.
I don't understand this part very well, maybe because I'm not familiar with VM implementations. Locals/globals/params/... can have all other types already, and why would allowing them to have nullref type be more work? Wouldn't categorizing types into two (one that can be local/global/... type and one that can't) rather be more work?
It's all doable, of course, but kindof annoying, especially if you start wondering whether we'll eventually need to "optimize" nullref (instead of simply representing it as a null pointer).
I don't understand what you mean by optimize nullref. Could you elaborate?
There tends to be case analysis (one case per type) for the operations on all these kinds of types (in codegen, in stub generation, in JS API, in the runtime functions). Again, it's not a ton, it's just annoying to have to add all these for a type that should never be meaningfully used in all these contexts.
The "optimization" for nulltype would be for it to take no space (and take no instructions when passing around) since it has only one value. Noone would do this initially, but maybe someone writes a silly benchmark one day and then someone does a silly optimization for it (e.g., as happened with the computation-on-undefined "optimizations" that arose b/c of Kraken back in the day).
I mean, it's not a big deal, but the origin for all this was that it seemed simpler to not have a ref.null that produced a new nullref type, but rather have a ref.null $T that produced a ref T, which would avoid having a nullref type altogether. The "nullref won't show up except during operand-stack validation" rule was a compromise to avoid (most of) the downsides of adding nullref.
I see. I understand there are many parts (codegen, in stub generation, in JS API, ...) in the VM that has to have handling routines for nullref. But for the optimization, I think it's OK to not have it at this point and we can consider adding it at some point later if it is really necessary.
I think at this point the problem is where we put the complexities. Currently in tools (specifically Binaryen) we can't figure out a node's type independently in some cases without looking at its parent node. Examples include
(block (type ???)
...
(ref.null)
)
(select (type ???)
(ref.null)
(ref.null)
)
So we either need to take special care in Binaryen not to produce those kind of code (which has been proven to be very difficult) or do a special separate transformation to remove nullref at the end of the pipeline. So I was wondering, if the complexity to handle nullref in the VM side is not too bad, would it be feasible to add back nullref as a normal type.
We can possibly hear more opinions in the CG meeting too.
I agree with @aheejin and @rossberg - it seems simplest to just consider nullref as a normal type. @lukewagner I get your point that special-casing it allows us to avoid some possible optimization work in the future, but the special-casing seems kind of awkward.
In particular, it just seems odd that nullref is special-cased to not be directly storeable to a local that has its own type:
(local$foo nullref)
(local.set$foo
(ref.null)
)
I think we should allow that. It makes the spec simpler, more regular, and easier to understand.
@aheejin Ah, that's a good point; I can see how that's problematic. If we consider changing the proposal to allow nullref in more places, I'd also like to consider not having nullref at all since I don't see how it's really buying us anything here.
I think the alternative would be just to have a different null-generating instruction for each nullable type, right? Just like i32.const 0 is different from f64.const 0
@lukewagner, to clarify, bullet 4 was alluding to possible examples like this:
type $dummy_vec = (array nullref)
global $dummy_vec : (ref $dummy_vec) = (array.new $dummy_array (i32.const 0))
...
type $s1_vec = (array (optref $type1))
type $s2_vec = (array (optref $type2))
global $vec1 : (ref $s1_vec) = (global.get $dummy_vec)
global $vec2 : (ref $s2_vec) = (global.get $dummy_vec)
Const-propagating null is unrelated. There is no actual null value, only an empty array that is shared across multiple types. (Perhaps not the most compelling example, but hopefully conveys the idea. Things like this pop up occasionally.)
It's also useful to avoid problems with compiling languages that indeed have the equivalent of a nullref type themselves, as @skuzmich pointed out above. That actually is a very strong point that hadn't even occurred to me.
(Of course, all this is primarily relevant in the presence of the GC proposal. But if the likelihood is that we're gonna want it anyway, then we should utilise it where we can.)
@skuzmich's example pertains more to the gc proposal, and actually I've found that, while the use case does need something like nullref, it actually needs a variant with an additional parameter. I've worked out detailed strategies for a number of languages, and I'm trying to write them up as fast as I can so that y'all can discuss.
Activity
rossberg commentedon Nov 14, 2019
In the first version of the proposal nullref was available. Removing it was a form of compromise, because there was some dislike of having this type. I am not sure what the arguments were. If you have a good use case, we can discuss bringing it back. It would be an easy change.
aheejin commentedon Nov 14, 2019
It is mostly that block/loop/if/try doesn't have self-sufficient type information within itself. For example,
When we create this block, we don't know which type to assign to this block, because we cannot assign
nullref. We cannot arbitrarily promote this toexnref/funcref/anyrefbefore we see the the parent node (in wast format) / the next instruction. In real transformations we wouldn't create a block like that out of nowhere, but transformations can split/merge blocks and create/delete instructions within them, and we don't have the ability to calculate the type of block/loop/... only by examining it and its child nodes anymore. It's not that this restriction makes transformations not possible, but they can be trickier.RossTate commentedon Nov 15, 2019
For a number of tooling purposes, you should ensure that every instruction has a principal output type for any given input type. For
ref.null, that seems to necessitate thenullreftype. So the options seem to be either to addnullrefor to parameterizeref.nullwith an argument that indicates which reference type the output type should be.sjrd commentedon Nov 15, 2019
Some languages, among which Scala, even have a user-space
Nulltype, which can be the declared result type of a function. For example in Scala the following code is valid:When compiling
giveMeNull()to wasm, the only valid result type forgiveMeNull()would benullref. If we cannot express it in the binary or text format, we have to resort to weird encodings.RossTate commentedon Nov 15, 2019
Yep, though that's more relevant to the GC proposal (where it's planned to be addressed). Nonetheless, it's a good point that something like
nullrefwill be needed eventually anyways, and the option to parameterizeref.nullwill likely be insuffucient down the line.rossberg commentedon Nov 15, 2019
Just to clarify, the proposal already includes a nullref type, for the reasons @RossTate mentions. The question @aheejin is asking is whether it should be expressible in concrete syntax. As mentioned above, that was the case originally, but there was some resistance, so it was removed. I'm all for bringing it back if we can get consensus on that.
aheejin commentedon Nov 16, 2019
I found some relevant previous discussion threads: thread1 thread2
@lukewagner Are there advantages specific to allowing
nullrefbut making it not representable in text or binary format? The threads discuss mostly about whether we neednullrefor not and whether we should have a separatenullinstruction for each reference type, but I'm not sure if I fully understand the advantages of makingnullrefnot writable while having it as a validation type.lukewagner commentedon Nov 18, 2019
Keeping
nullrefout of the binary format isn't really the goal; the goal was to avoid having to deal with the annoyance of having to addnullrefsupport for locals, globals, params, returns, tables and, in the future, elems and fields. It's all doable, of course, but kindof annoying, especially if you start wondering whether we'll eventually need to "optimize"nullref(instead of simply representing it as a null pointer).aheejin commentedon Nov 18, 2019
@lukewagner
I don't understand this part very well, maybe because I'm not familiar with VM implementations. Locals/globals/params/... can have all other types already, and why would allowing them to have
nullreftype be more work? Wouldn't categorizing types into two (one that can be local/global/... type and one that can't) rather be more work?I don't understand what you mean by optimize
nullref. Could you elaborate?lukewagner commentedon Nov 18, 2019
There tends to be case analysis (one case per type) for the operations on all these kinds of types (in codegen, in stub generation, in JS API, in the runtime functions). Again, it's not a ton, it's just annoying to have to add all these for a type that should never be meaningfully used in all these contexts.
The "optimization" for nulltype would be for it to take no space (and take no instructions when passing around) since it has only one value. Noone would do this initially, but maybe someone writes a silly benchmark one day and then someone does a silly optimization for it (e.g., as happened with the computation-on-
undefined"optimizations" that arose b/c of Kraken back in the day).I mean, it's not a big deal, but the origin for all this was that it seemed simpler to not have a
ref.nullthat produced a newnullreftype, but rather have aref.null $Tthat produced aref T, which would avoid having anullreftype altogether. The "nullrefwon't show up except during operand-stack validation" rule was a compromise to avoid (most of) the downsides of addingnullref.aheejin commentedon Nov 18, 2019
I see. I understand there are many parts (codegen, in stub generation, in JS API, ...) in the VM that has to have handling routines for
nullref. But for the optimization, I think it's OK to not have it at this point and we can consider adding it at some point later if it is really necessary.I think at this point the problem is where we put the complexities. Currently in tools (specifically Binaryen) we can't figure out a node's type independently in some cases without looking at its parent node. Examples include
So we either need to take special care in Binaryen not to produce those kind of code (which has been proven to be very difficult) or do a special separate transformation to remove
nullrefat the end of the pipeline. So I was wondering, if the complexity to handlenullrefin the VM side is not too bad, would it be feasible to add backnullrefas a normal type.We can possibly hear more opinions in the CG meeting too.
kripken commentedon Nov 19, 2019
I agree with @aheejin and @rossberg - it seems simplest to just consider
nullrefas a normal type. @lukewagner I get your point that special-casing it allows us to avoid some possible optimization work in the future, but the special-casing seems kind of awkward.In particular, it just seems odd that
nullrefis special-cased to not be directly storeable to a local that has its own type:I think we should allow that. It makes the spec simpler, more regular, and easier to understand.
lukewagner commentedon Nov 19, 2019
@aheejin Ah, that's a good point; I can see how that's problematic. If we consider changing the proposal to allow
nullrefin more places, I'd also like to consider not havingnullrefat all since I don't see how it's really buying us anything here.aheejin commentedon Nov 19, 2019
@lukewagner If we don't have
nullref, what do we initialize locals with reference types? And what should the result type ofref.nullbe?dschuff commentedon Nov 19, 2019
I think the alternative would be just to have a different
null-generating instruction for each nullable type, right? Just likei32.const 0is different fromf64.const 016 remaining items
rossberg commentedon Nov 22, 2019
@lukewagner, to clarify, bullet 4 was alluding to possible examples like this:
Const-propagating null is unrelated. There is no actual null value, only an empty array that is shared across multiple types. (Perhaps not the most compelling example, but hopefully conveys the idea. Things like this pop up occasionally.)
It's also useful to avoid problems with compiling languages that indeed have the equivalent of a
nullreftype themselves, as @skuzmich pointed out above. That actually is a very strong point that hadn't even occurred to me.(Of course, all this is primarily relevant in the presence of the GC proposal. But if the likelihood is that we're gonna want it anyway, then we should utilise it where we can.)
RossTate commentedon Nov 22, 2019
@skuzmich's example pertains more to the gc proposal, and actually I've found that, while the use case does need something like
nullref, it actually needs a variant with an additional parameter. I've worked out detailed strategies for a number of languages, and I'm trying to write them up as fast as I can so that y'all can discuss.lukewagner commentedon Nov 23, 2019
@rossberg Ah, I see. Sorry, I skimmed that bullet too quickly. Yes, I suppose as part of a compound type
nullrefcan be useful as well.So I suppose I'm fine with giving
nullrefa binary/text encoding and letting it show up everywhere.aheejin commentedon Nov 23, 2019
cc @gahaas for possible V8 implementation changes
For FF should I cc someone other than @lukewagner?
rossberg commentedon Nov 23, 2019
Thanks @lukewagner! In order to unblock @aheejin fast, I created #66.
lars-t-hansen commentedon Nov 25, 2019
@aheejin, yes, you should cc me :-)
Add support for reference types proposal
Add support for reference types proposal
Add support for reference types proposal
Add support for reference types proposal
Add support for reference types proposal
Add support for reference types proposal
Add support for reference types proposal
rossberg commentedon Jan 16, 2020
This has been fixed, though #69 may require revisiting it.