Add a get_value operator to duplicate a value from the expression stack.

[ghost]

Would there be any immediate interest in adding an operator, say get_value, to duplicate a value from the expression stack?

With the post-order encoding there is already the issue that expression results accumulate in blocks to be discarded at the block exits. It seems consistent with the SSA decoder to allow re-use of these, so why not take advantage of them. Each of these could be viewed as binding a block local variable that could be accessed. So rather than block we could effective have let:

(let (($v1 (f64.load ...))
      ($v2 (i32.load ...))
      (_ (f64.store :offset 8 (get_value $v2) (get_value $v1)))
      (_ (f64.store :offset 16 (get_value $v2) (get_value $v1))))
  ;; The fall through result.
  (get_value $v1))

Adding this now might allow some experimentation with the tooling, to take advantage of this.

It's not necessary to land this change, and it can be explored in local work, and local tools can rewrite the wast into this encoding, but might there happen to be any interesting in such an incremental change?

[ghost]

This extension might complement the text format being explored in https://github.com/sunfishcode/design/blob/text-syntax-strawman-proposal/TextFormat.md by allowing the naming of block top level expressions and their reuse.

This text format introduces push and pop text format annotations that allow an expression to be split into multiple lines. These may, or may not, be block top level expressions, and when they are popped they are not? It does not seem to be proposing an extension so I assume these annotated expressions still need to be used in the same stack order as for expressions - they just allow splitting an expression into multiple lines?

Personally I think it would be frustrating to write code using these annotations because there are still a lot of constraints on where they can be used and this would be a burden on the writer - a reader could assume the code is valid and I can see that help in the case of presentation.

This text format proposal gives this example:

   function $Q_rsqrt ($0:f32) : (f32) {
     var $1:f32
     $1 = f32.reinterpret/i32 (1597463007 - ((i32.reinterpret/f32 $0) >> 1))
     push:0 $0 = $0 * 0x1p-1
     $1 = $1 * (0x1.8p0 - $1 * pop:0 * $1)
     $1 * (0x1.8p0 - $1 * $0 * $1)
   }

Note this example looks wrong, or I don't understand the intention of the push and pop. I would have thought that the only valid place for a pop is the first value in an expression? At the point of the pop:0 there would be lots of other values on the stack between the expression above it.

Anyway, rewriting the example in this text format proposal to use the extension proposed here would give the following where the const is just a labelled block stack value, and a use of the local variables has been avoided. I think this would be far less frustrating for a human writer to work with, and probably easier for a reader too.

   function $Q_rsqrt ($0:f32) : (f32) {
     const $c1 = f32.reinterpret/i32 (1597463007 - ((i32.reinterpret/f32 $0) >> 1));
     const $c2 = $0 * 0x1p-1;
     const $c3 = $c1 * (0x1.8p0 - $c1 * $c2 * $c1);
     $c3 * (0x1.8p0 - $c3 * $c2 * $c3);
   }

I think that one of the ways that expressions help the reader is that they make it clear that the intermediate values have a single use and make the end of the definition live range clear. Unfortunately the proposal here only makes it clear that the definitions are used within the lexical scope of the block in which they are defined, and after their definition. It is sometimes possible to introduce extra blocks just to reduce the obvious live range of a definition, but this is not a comprehensive solution.

If finding the live ranges of definitions is a significant burden for the runtime compiler then there might be some merit in having the producer explicitly flag the last use, so the proposal here might also add a get_value_last_use operator (or some shorter name). This would be similar to an implicit pop operation which is the last use of a stack value, but it does not adjust the stack because the value might not be on the top of the stack and values on the stack might still be needed. The producer could just implicitly pop a value if the last use of a value happened to be on the top of the stack, but the producer would have get_value_last_use is case it was not at the top of the stack.

Lets say that in a text format get_value were represented by a name beginning with # rather than $, and get_value_last_use is the common case and uses the prefix $, then the above example would be:

   function $Q_rsqrt ($0:f32) : (f32) {
     const $c1 = f32.reinterpret/i32 (1597463007 - ((i32.reinterpret/f32 $0) >> 1));
     const $c2 = #0 * 0x1p-1;
     const $c3 = $c1 * (0x1.8p0 - $c1 * $c2 * #c1);
     $c3 * (0x1.8p0 - $c3 * #c2 * #c3);
   }

Now the reader can clearly see the last use of definitions and thus their live range, and does not need to scan forward over the lexical scope to search for other uses. The runtime compiler could flag the live ranges of these definitions in a single pass. I have no idea yet how this would increase the encoded file size, but the common case is a single use with an implicit pop so perhaps there is some hope.

[qwertie]

Funny, I posted #693 without having seen your recent comment. Isn't the proposal here simply to introduce a new kind of local variable - a block-scoped single-assignment variable? I had the impression that such variables had been proposed earlier - or do I misremember?

So what your latest comment is doing is just changing the syntax of your original proposal?

[ghost]

@qwertie The definitions are already on the values stack in a post-order decoder. All the block top level expression definitions are on the values stack at the end of the block. This proposal is to allow re-use of them, the get_value operator. These values might even be used by get_value and also later consumed by an implicit pop, so not only block top level expressions.

The const $c1 syntax is how it could look in an alternative text format such as https://github.com/sunfishcode/design/blob/text-syntax-strawman-proposal/TextFormat.md So these do not need a new type of local variable. It matches a functional style of programming, and looks subjectively more readable to me. A value that is not a block top-level expression might not look so pretty, but would read well in another block-like pattern, for example:

$l1 + {const $c1 = ...; call $fn($c1, $c1); $c1};

There may also be some utility in being able to explicitly declare the last use of these definitions. This happens implicitly when they are used as an expression argument and are popped from the top of the values stack. This could help a single pass compiler such as https://bugzilla.mozilla.org/show_bug.cgi?id=1232205 with register allocation, so it knows when a value in a register is no longer needed and can free up the register without flushing it to a memory stack.

[ghost]

Could this operator, get_value aka pick, land for the 0x0d roll?

The lack of this support appears to have stalled some areas of wasm developer for a good part of this year, and blocks the MVP. There appears to have been no tool development, and the text format appears stagnant on current limitations, and critical performance and implementation complexity and thus security issues remain unanswered blocking the MVP.

This is a trivial operator for implementations to add, and opens new paths for producers to explore, paths that may well lead to local variables being removed from wasm and wasm becoming SSA with a stack encoding. Even if this did not prove superior, there are immediate benefits that producers could explore such as using pick to reduce the use of local variables in patterns such as:

(call i32 ...)
(set_local $l0)
(get_local $l0)
(get_local $l0)
(i32.add)
=>
(call i32 ...)
(pick 0)
(i32.add)

Not only is this shorter, it leaves less live values which should help a simple compiler and should reduce the work for an optimizing compiler.

It also creates patterns in which multiple values need to be dropped out of stack order in blocks, showing clearly the efficiency of having block ends unwinding the stack. Producers could start inserting blocks to more efficiently clear the stack, leaving less live values.

Handling pick will also move the text format forward, creating more exploration in this area.

Should an SSA encoding prove competitive in terms of encoding efficiency then it will probably be compelling, and may well open new paths to explore.