separate index space for parameters/locals?

[lukewagner]

A recent commit separated out parameters from locals, giving the two overlapping index spaces. This is fairly different than what's in the design repo (only locals) but not a huge fundamental design difference (both work), so I thought we should discuss it here.

[lukewagner]

My opinion is that it's simpler to have one index space (shared by paramters/locals) and one set of ops for reading/writing since, other than how they are initialized, locals/params aren't different. There may also be a size win from having less ops competing for the 1-byte space (which normally I wouldn't attempt to argue, but local access is ~40% of bytes in polyfill-prototype-1 output, so the difference might "show through" even with layer 1/2 compression).

[jfbastien]

I was thinking about going with separate index spaces, and start functions with (setlocal @0 param @0) and so on. That's kind-of what I have in LLVM now (of course we can change it).

It seems easier than having params factor into the coloring of locals?

But yeah I think space usage is what matters most here, so data would win.

[sunfishcode]

@jfbastien Would we require param nodes to appear only in the entry block? And would we prohibit any other code from appearing before them? If we don't, then wasm implementations will have to manage lifetimes for incoming parameters anyway. If we do, then these nodes are just boilerplate in every function that has parameters. I think a single index space makes sense.

[jfbastien]

Would params occupy the lower-numbers automatically, in this One Single Space?

[sunfishcode]

It wouldn't be hard to define a mechanism to put the params at a different place in the index space, to reserve the low indices for more commonly used variables. However, I suspect that params that aren't used frequently will usually be easy to color with other things, so it doesn't seem likely to be enough of a win to justify the extra complexity.

[lukewagner]

I don't think we need to worry about local index space order here:
We've already mostly agreed we won't have immediates-folded-into-ops at layer 0, which means that, at layer 0, get_local will be 2 bytes (one for op, one for immediate) for locals [0 - 128], depending on encoding scheme. IIRC, 99% of functions in Unity/Epic asm.js have <64 locals. But 2 bytes per get/set local is terrible for the by-far hottest opcodes and to do better, we'd want to lean on the macro layer to fold get_local and set_local with the hottest immediates into a single byte (I described a sketch in #58). Once we do this, though, the actual index doesn't matter.

[rossberg]

On 17 August 2015 at 23:11, Luke Wagner notifications@github.com wrote:

A recent commit
b223caf
separated out parameters from locals, giving the two overlapping index
spaces. This is fairly different than what's in the design repo (only
locals
https://github.com/WebAssembly/design/blob/master/AstSemantics.md#local-variables)
but not a huge fundamental design difference (both work), so I thought we
should discuss it here.

I would argue that this is an encoding concern. In terms of semantics,
parameters and locals are somewhat different, and tend to generate
different code as well. That doesn't preclude that a binary encoding could
overlay them into one opcode, by shifting the index space appropriately. I
would consider that a separate concern, though.

That was the thinking behind the commit, anyway (besides making the s-expr
code more readable and less brittle, given that it doesn't support names
yet).

/Andreas

[titzer]

It's quite convenient to have parameters and locals in the same index space
(and parameters at the beginning) in the decoder, because then the
environments carried for SSA renaming are just a simple array of the
current value of each local/param.

On Tue, Aug 18, 2015 at 9:05 AM, rossberg-chromium <notifications@github.com

wrote:

On 17 August 2015 at 23:11, Luke Wagner notifications@github.com wrote:

A recent commit
<
b223caf

separated out parameters from locals, giving the two overlapping index
spaces. This is fairly different than what's in the design repo (only
locals
<
https://github.com/WebAssembly/design/blob/master/AstSemantics.md#local-variables
)
but not a huge fundamental design difference (both work), so I thought we
should discuss it here.

I would argue that this is an encoding concern. In terms of semantics,
parameters and locals are somewhat different, and tend to generate
different code as well. That doesn't preclude that a binary encoding could
overlay them into one opcode, by shifting the index space appropriately. I
would consider that a separate concern, though.

That was the thinking behind the commit, anyway (besides making the s-expr
code more readable and less brittle, given that it doesn't support names
yet).

/Andreas

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

[lukewagner]

@rossberg-chromium I realize we're in pretty subjective territory here but, from discussions above, at least from a low-level perspective (which is generally the perspective we're taking with wasm ops), the only semantic difference between params/locals is how they are initialized which was more aptly captured by eval_func before GetParam was added. Also, the readonly GetParam that can be read anywhere in the body doesn't seem to capture anything essential.

[jfbastien]

It's quite convenient to have parameters and locals in the same index space (and parameters at the beginning) in the decoder, because then the environments carried for SSA renaming are just a simple array of the current value of each local/param.

That's a pretty convincing argument, I'm sold.

[lukewagner]

@rossberg-chromium Sound good to go back to only locals?

[rossberg]

Done. I still find it a bit unfortunate, e.g. it loses the 1-to-1 mapping between declaration forms and access forms.