Repository navigation
Alternatives to let? #44
Description
Activity
About (3) (local initializers that are similar to global initializers), I think that could be simplified to just referring to an immutable global. That is, in global initializers we need a lot of generality, but here we just need to avoid a null value, and the default value will in most cases not be used and so not matter. So in a module each GC type could have a singleton immutable global containing a "dummy" instance of that type which locals would refer to.
A more compact encoding of that could be to define types with default values. Such types would be defined after the global section, and just pair a type with an immutable global. This would avoid any extra bytes in functions. And such types with custom defaults may have other uses than this.
I like (4) because it has the best ratio of simplification to change, but I would be happy to consider larger changes as well.
Taking @kripken's line of thought a step in the opposite direction that @00ff0000red took it, if every non-nullable type would have a dummy global default value that is never used in normal execution, then why waste code size and tool effort on defining those globals? Instead we could just have the engine generate a meaningless default value for each non-nullable type. The only difference between these dummy values and null values are that dereferencing the dummy values does not trap, but rather does nothing or yields another dummy value.
The benefit of non-nullable values is that you know that there is always meaningful data in them, so I think any solution that involves global default values for non-nullable types somewhat diminishes their benefit to the point where we might as well not have them.
Do we still want
letinstruction, if we were to go with (4) ?Instead,
local.setcould form a scope till the end of the current block, where you can safelylocal.getnon-nullable variable.I think engines would have to validate that every
local.getfrom a non-nullable local is dominated by alocal.setto the same local. It looks like there are efficient algorithms for this, but it would certainly add validation complexity.Speaking of domination, another option might be
(6) Trap at runtime if a non-nullable local is used before being assigned to. I know that sounds bad, but in an optimizing tier SSA analysis will anyhow prove that uses are dominated by values (always the case unless the wasm emitter has a bug), so it has no overhead to either compile time or runtime. Of course, in a baseline compiler this will mean null checks on
local.get. But it's simple and has no code size overhead.@skuzmich I don't think I understood your suggestion, then. Right now
local.setinstructions do not introduce new block scopes. Are you suggesting that we have a version oflocal.setthat does introduce a new scope? If so, how would that be different fromlet?@tlively Please, allow me to clarify. In my suggestion
local.setwould not form a proper Wasm block, it would not have a dedicatedendinstruction. Instead, it would merely create a variable scope fromlocal.setinstructions till the end of the current block it is in.Benefits of this approach:
- No
letinstruction in spec. No need to support it in decoder and execution. New rules forlocal.setapply only to validation phase and are as complex asletinstruction rules. - No code size overhead for
blocktypeandend.
As far as I remember,
letwas designed as it is to simplify function inlining. You would want a proper branch target for inlined returns, andlocaldefsection with relative indexing for inlined locals. But since (4) removes relative indexing from locals defined inlet, this is no longer the case, and we might not need this extra instruction.- No
In WebAssembly/design#1381, I did an analysis of initialization and of
let. I found thatletwas not well-suited for initialization. One example I gave is where a local is initialized on separate paths that join together. Many of the suggestions above would also have problems with that case. At the time I had considered a variety of other fixes to locals/let, but they all made the type system more complicated and without solving more advanced cases like type refinement. The simplest and most expressive solution by far was to just use the stack and add these four simple stack instructions: WebAssembly/design#1381 (comment).The parts of the discussion in WebAssembly/design#796 regarding register allocation and this article make me think that such an approach could be easier for engines, though others here are better equipped to speak to this. The fact that there's a straightforward way to translate from using locals to using stack instructions makes me suspect it could be easier to generate, but that translation does require tracking more information about the current stack state, so I defer that judgement to others as well.
Oh, I forgot, regarding dummy values, that approach might not always be possible. For example, in the presence of polymorphism, you might not be able to construct a dummy value of a type ahead of time because you might not know what that type is. That is, of course, unless all value types are defaultable, which is a viable option but one that brings us back to #40.
Unfortunately stack manipulation instructions won't help in Binaryen because of its expression-based IR, but if they would be helpful in other contexts, I don't think that should be a big blocker. We're already hacking around things like multivalue results, block parameters, and
letin Binaryen IR, so we would just hack around stack manipulation instructions as well. That being said, it would be nice if we had a solution that fit nicely into Binaryen IR.Hmm, I feel like an expression-based IR shouldn't be a big problem. I would suspect this would only affect the serialization phase. That is, you're free to use (your own notion of) locals in your IR, but when you serialize your IR to WebAssembly, rather than emitting
local.get/set $index_of_local_in_your_IRyou emitget/set $index_of_local_on_stack. The complication is that$index_of_local_on_stackdepends on$index_of_local_in_your_IR, which locals are currently initialized (as the uninitialized ones are not on the stack), and how many temporaries are currently on the stack, so your emitter would have to track that as it recurses through your expressions.Reacted by Thomas Lively413 remaining items
It looks like we have a consensus coalescing around 1a (resetting initialization state at the end of every block) for the MVP. Let's try to resolve this discussion right now.
Official online unanimous consensus vote
React to this comment with a 👎 to object to the proposed resolution. If we have any 👎 by the end of day on Thursday this week, we will discuss this at the next meeting and resolve this conversation then instead. If there are no 👎 at the end of day Thursday, we will adopt 1a as the solution for the MVP.
Reacted by jakobkummerow, Thomas Lively, Alon Zakai, Ben L. Titzer, Conrad Watt, Aske Simon Christensen and Andreas RossbergReacted by Ross TateExcellent, we will go with option 1a for the MVP.
Reacted by Conrad Watt, Aske Simon Christensen, jakobkummerow and Andy WingoIt's great to finally have a solution here! @askeksa-google raised one detail a couple of days ago: we still have a choice to make regarding
loop.Contrary to
block, there is no way to reach theendof aloopwithout executing all of its body at least once; so we could maximise applicability of "option 1a" by not resetting initialization status at theendofloops; in other words the rule would be "NNL initialization status is reset at theendof anyblock,if,try, as well as anyelse/catch/catch_all".The alternative is to reset NNL initialization status at every
end(andelse/catch/catch_all). Looking at #63, this might make the formulation of the formal spec a bit easier. It provides no meaningful simplification for engines. In theory, this option is wasteful (we'd be throwing out perfectly good initialized-ness information); in practice the difference is probably insignificant (because the situation of initializing an NNL in aloopand then using it afterwards is likely very rare).Regarding forward compatibility: we cannot change our minds and go from "not resetting" to "resetting". Changing behavior in the opposite direction is not a problem. This is independent of whether we eventually adopt "1b", "1c", or neither, or something else entirely. In particular, if we go with "not resetting" now, we can still do "1b" or "1c" later, we'll just have to maintain "not resetting" at that time (which is not a problem for "1b" and "1c").
I think either option is better than spending another two years debating this, but we should pin it down one way or the other.
I'm going to try an unofficial poll about this to see where we stand as a group. Please 👍 one of the next five posts:
Reacted by Aske Simon Christensen"I strongly believe that we should not reset NNL initialization status at the
endof aloop, and would rather argue about it than be outvoted.""If it was up to me, I'd say we should not reset NNL initialization status at the
endof aloop, but I'd rather be outvoted than spend time arguing about it."Reacted by jakobkummerow"I totally don't care one way or the other."
Reacted by Alon Zakai and Thomas Lively"If it was up to me, I'd say we should reset NNL initialization status at the
endof aloop, but I'd rather be outvoted than spend time arguing about it."Reacted by Aske Simon Christensen"I strongly believe that we should reset NNL initialization status at the
endof aloop, and would rather argue about it than be outvoted."Reacted by Conrad Watt and Andreas RossbergIt's sounds OK to me at first blush to not reset at loop ends, because the only way to get there is falling through.
@titzer this would mean that we break forwards compatibility with the version of
1bthat @rossberg and I advocated for (recall the whole "local reasoning" debate). As @jakobkummerow mentioned, we can go from resetting now to not resetting later, so resetting is the most conservative choice in terms of future plans.The current PR does "reset". Frankly, I don't think there is much of a choice here, since not resetting is incompatible with a uniform interpretation of block types under 1b and thus not really conservative, as we intended to be.
Ok, fair points. I agree that resetting is the conservative choice.
FYI, this has been implemented in V8.
Reacted by Conrad Watt, Aske Simon Christensen and Alon Zakai- added a commit that references this issue
on Jul 27, 2022
We have heard from multiple directions (interpreters, toolchains, debuggers) that
letis (surprisingly) hard to implement/use. As I am looking into implementingletin V8's non-optimizing compiler, add my name to that list. It's certainly all doable, but it's quite involved. And it would be sad if engine/interpreter implementors had to spend particular implementation effort (as well as runtime CPU+memory cost) on a feature that toolchains then barely use.So I was wondering whether the
letinstruction as currently proposed really is the best solution we can collectively come up with.IIUC, its primary purpose is to provide a way to have non-defaultable locals (in particular: non-nullable reference type locals) in a function. Please do point out if it has additional important use cases.
In the spirit of brainstorming, here are some alternatives that would solve that problem too:
(1) A "locals_initialized_barrier" instruction with semantics: before the barrier, locals may be uninitialized/null, and reading from them incurs the cost of a check; after the barrier, such checks are dropped as all locals are guaranteed to be initialized. Execution of the barrier checks that all non-defaultable locals have been initialized.
(2) A scope that indicates "within this scope, the given locals are non-null". Entering the scope performs null checks on the specified locals. Accessing these locals within the scope needs no null checks.
(3) Introduce "local initializers" modeled after the existing global initializers (which are solving the same problem). We'd need to figure out how exactly to encode these in the text and binary formats. Execution of a function would begin with evaluating these local initializers; afterwards all locals are guaranteed to be initialized. Similar to globals, the rules would be something like: only constant instructions are allowed as local initializers; they can read other locals but only those with lower indices.
(4) Require all locals to be pre-declared (at least by count, maybe also by type). Their initialization then still happens with
letas currently proposed. That would prevent the size of the locals list/array/stack from changing dynamically, and would also keep each local's index constant throughout the entire function.(5) Drop
letentirely, at least for now. We can always add it later if we have enough evidence of a concrete need for it. In the meantime, a workaround is to factor out the body of what would have been alet-block as a function, and call that. A JIT might still decide to inline that function. (This would limit Wasm module's ability to fine-tune for maximum performance; but based on binaryen's feedback it's unclear to what extent they'd do that anyway. This is not my preferred solution, just mentioning it here for completeness.)(I realize that there is a lot of conceptual overlap between these ideas -- which is unsurprising given that they're all solving the same problem, just with slightly different approaches.)
I'm sure there are other possibilities, please suggest them!
If the ideas above have critical flaws making them unsuitable, please point them out! And if you have a favorite among them, please say so as well.
As I wrote above, this issue is meant to be a collective brainstorming (and maybe eventually decision-making) effort.
We don't have to change anything; I just wanted to make sure that this design has received sufficient contemplation before we set it in stone. Especially in light of the feedback we've been getting so far.