Should locals be implicitly set to 0

[jcbeyler]

Dear all,

By design, locals have to be defined at 0. I understand that with a good compiler will remove unnecessary sets to 0 if the local variable is first defined and not used before.

However, in certain cases, this might be not trivial. Good compilers will be able to do it but not simple ones.

Are we doing this to try to reduce the binary size? The only case this helps is when you would use the variable as 0 for its first use. But how often does this occur?

Basically, just opening up a conversation about this "implicit set to 0".

Thanks!

[lukewagner]

I think the root motivation is avoiding a class of nondeterminism and the wasm-wide general goal of limiting nondeterminism.

[jfbastien]

Maybe we can leave this open for exploration once we have VMs which we can experiment on? It's useful to at least understand the cost of each non-determinism reduction mechanism.

[pizlonator]

Right. Also, I think that the zero-filling of locals would only have performance implications in a very special set of "perfectly mediocre” compilers, and it’s possible that this is actually the null set.

If the compiler is good enough, it will remove the zero initializations unless they are actually used (i.e. the program relies on the value being set to 0). This will happen in a compiler that does either of the following optimizations. It doesn’t have to do all of them; just one of them will do:

1. SSA conversion followed by a trivial use-count-based dead-code-elimination. In some compilers, the DCE will just fall out naturally from the SSA conversion.
2. Liveness-based dead code elimination. If you see a def to a variable that isn’t live, remove it.

If the compiler is bad enough, it will have too many other overheads for those zero-fills to matter. This will be the case in a compiler that fails to do register allocation. In that case, performance will be dominated by loads from spill slots, which will stall on the store that set the value. The zero initialization of variables will be dead stores to spill slot, so they will not cause any stalls. Storing to a memory location that won’t be read, or that will be overwritten by some other store prior to the read, are very cheap.

I’m having a hard time imagining what kind of compiler would fail to do SSA conversion or liveness analysis while also having register allocation. That would be quite weird, since register allocation usually requires liveness, and liveness makes it pretty easy to kill dead variable initializations.

-Filip

On Dec 16, 2015, at 11:39 AM, Luke Wagner [email protected] wrote:

I think the root motivation is avoiding a class of nondeterminism and the wasm-wide general goal https://github.com/WebAssembly/design/blob/master/Nondeterminism.md of limiting nondeterminism.

—
Reply to this email directly or view it on GitHub #504 (comment).

[lukewagner]

@pizlonator Agreed

[ghost]

@pizlonator I have seen some very poor code generated by compilers with SSA and DCE in this area! Perhaps there are some issues here. It might not just be that they have to be initialize to zero, but also that they all need to be initialized at the start of the function. Perhaps also a runtime needing debug support (probably most web browsers) might effectively add readers (and writers) even in these dead code ranges, forcing them to be kept alive or to mitigate this with some clever debug support - this might force them to the stack needing even smarter register allocation to manage. I have tried to suggest block local variables to help move some of this burden to the producer, and to allow them to be initialized with an expression.

Note sure but might irreducible CFG block some compiler reasoning in this area. The specification seems to not be assuming that compilers need not be smart enough to manage this case.

It might also have implications for type derivation as it forces the range of the variable to include zero. If the producer has to assume the consumer is smart enough to use SSA, and thus to use a write to kill the initialized value, then this needs to be noted in the specification.

[jcbeyler]

The problem I have is that I imagine WebAssembly being used in smaller, non web, devices where really we would want a very small, quick, and non-optimizing compiler. I worry in this case that we are adding more operations than we need.

I'm not trying to sway your minds, just wondering how often this is really relevant: ie a local variable's implicit 0 initial value is really useful and instead we could just explicit it.

[jcbeyler]

Well it is already there and in the design document. But I don' t like it for reasons I' ve said but I think I'll lose this conversation. I'll probably close this tomorrow and just be grudgingly kicking the dirt later on ;-)

Reference:
" Local variables have value types and are initialized to the appropriate zero value for their type at the beginning of the function, except parameters which are initialized to the values of the arguments passed to the function"
https://github.com/WebAssembly/design/blob/master/AstSemantics.md

[sunfishcode]

I'm sympathetic to the needs of simple fast JITs, so I'm open to suggestions of what we can do, and I think that JITs doing local (within a basic block) register allocation might have a chance of falling into the gap here where they'd be unable to do the DCE, while still being fast enough to need it.

The obvious solution, giving variables nondeterministic initial values, would be too high a price here, in my opinion.

A possible alternative would be to bring in scoped variable declarations (something that's been discussed in other contexts). To address concerns about JITs wanting to know the number of variables for a function up front, we could require functions to declare their maximum variable usage (per type). My initial guess is that this would have a little too much complexity for too little benefit, but if someone wanted to explore this approach, I'd be willing to consider it.

[sunfishcode]

Closing, as it isn't clear what else we should do here. If anyone wishes to propose a specific path forward, please re-open or file a new issue.