Incomplete implementation of explicit-drop

[sunfishcode]

As stated in #694, the intention of the explicit-drop rules is that:

Values can no longer be discarded implicitly.

The stack branch of ml-proto currently accepts this:

(module
  (func
    block $end
      i32.const 0
      br 0 1
    end
  )
)

The current design states:

In all constructs containing block-like sequences of expressions, all expressions but the last must not yield a value.

This is using pre-stack-machine terminology, but in those terms, the example above shows a code sequence in which an expression appears in a block-like sequence of expressions, is not the last expression in the block, and yet does yield a value.

[titzer]

On Thu, Sep 1, 2016 at 5:51 PM, Dan Gohman [email protected] wrote:

As stated in #694, the intention of the explicit-drop rules is that:

Values can no longer be discarded implicitly.

The stack branch of ml-proto currently accepts this:

(module
(func
block $end
i32.const 0
br 0 1
end
)
)

The current design states
https://github.com/WebAssembly/design/blob/master/AstSemantics.md#yielding-values-from-control-constructs
:

In all constructs containing block-like sequences of expressions, all
expressions but the last must not yield a value.

I think this sentence is now obsolete.

This is using pre-stack-machine terminology, but in those terms, the
example above shows a code sequence in which an expression appears in a
block-like sequence of expressions, is not the last expression in the
block, and yet does yield a value.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
#326, or mute the thread
https://github.com/notifications/unsubscribe-auth/ALnq1Nyv70Fy0xB8prSeGE57IrN4jk9Iks5qlvSegaJpZM4Jy2Nj
.

[sunfishcode]

At the moment, it's the only mention of the explicit-drop requirement in the design repo, and the wording is clear, even if it does need to to be updated for the new stack-machine terminology.

[rossberg]

On 1 September 2016 at 17:57, titzer [email protected] wrote:

On Thu, Sep 1, 2016 at 5:51 PM, Dan Gohman [email protected]
wrote:

As stated in #694, the intention of the explicit-drop rules is that:

Values can no longer be discarded implicitly.

Obviously, this was meant up to unwinds, otherwise the sentence wouldn't
make any sense.

The stack branch of ml-proto currently accepts this:

(module
(func
block $end
i32.const 0
br 0 1
end
)
)

The current design states
<https://github.com/WebAssembly/design/blob/master/
AstSemantics.md#yielding-values-from-control-constructs>
:

In all constructs containing block-like sequences of expressions, all
expressions but the last must not yield a value.

I think this sentence is now obsolete.

Right, this sentence obviously makes no sense anymore in the stack machine
context (which design/master does not have yet). With the stack machine,
arbitrary many instructions can produce values that are pending
consumption, which wasn't the case with nested expressions.

All values still have to be consumed "explicitly" either as operand or by
an unwind. Branches unwind, so the example works as intended.

block-like sequence of expressions, is not the last expression in the

block, and yet does yield a value.

[sunfishcode]

This change wasn't discussed in the stack-machine documents, and isn't mentioned explicitly in the stack PR. It's an interesting decision, and I'm seeking rationale material, regardless of the outcome.

The argument against considering an unconditional branch to be a use of excess values in its block is that the values aren't actually being used. Explicit drops help simple consumers avoid allocating resources up front for values that have no actual uses, and if there's a motivation for an enforced rule to encourage this in some contexts, then there's a motivation for it in all contexts (even if there are also motivations for other considerations).

Would you mind stating the argument in favor?

Alternatively, would it make sense to drop (;-)) the explicit-drop rule altogether and just let consumersproducers insert explicit drops as an optional optimization?

[drom]

Agree with @sunfishcode -- explicit drop is more universal.

[rossberg]

It's not really a separate change or decision, it's just a consequence of the stack machine, which naturally is more lenient than structured expressions. Branches always unwind in Wasm, and I don't have a good idea on what grounds this corner case should be ruled out. Or what the typing rules to achieve that would be. It would be introducing a special case.

As for implementations, breaks have to unwind in general, and operationally there is nothing special about this case in particular. All consumers will need to implement the mechanics anyway. Your argument seems to be that it helps to discover some trivial cases of redundant code, but why would simple consumers care about identifying redundant code, and why are these corner cases more relevant than others?

Concretely, how's their effort any different from the following example, which is obviously legal?

(block $out
  (block
    (i32.const 0)
    (br_if $out (i32.const 1))
    (drop)
  )
)

[ghost]

@drom The discussion is getting rather confusing. There is an 'explict-drop' rule versus an 'explict drops as optional'. Which one of these do you agree with?

The unwinding rules will make it much more efficient to code up patterns using pick because their source can be left on the block values stack and removed in the unwinding on exit from the block and it gives them block scope which fits well with a structured presentation format.

• I think the values stack resource usage is a minor matter now. The change to have void operators not push to the values stack addressed most of the excess values stack resource usage, along with the change to not have the store operators and set_local push results. It's just calls that need push unused values now, and if that is a problem then that could be addressed in the call operator by specifying which result values are used. Thus producers are not going to be leaving values on the stack that are not used, they can, but they have a motivation for not doing this as it compromises performance on a simple compiler (higher register pressure, more spills etc).
• Values that are used out of stack order or used multiple times currently need to be stored in local variables to be loaded back when needed. These might alternatively be left on the stack and loaded from the stack when needed using pick and the last use might consume the value in stack order. This may leave values on the stack and the unwinding can usefully remove these when a block is exited.
• If values are in local variables then the variable might be reused marking the end of the live range of the previous definition but this might not occur until well after the end of the block. The live range could be ended explicitly with get_and_zero_value.
• On the values stack, remaining values are still live at the end of the block but not beyond the end of the block, but here a pick_and_void operator might help if that is a significant performance matter for a simple compiler.
• The drop rule does not play well with pick, it requires values to be stored to local variables or dropped if used out of stack order.
• Operators that modify the values stack might frustrate the SSA decoder performance and seem unnecessary. The design should not depend on swap to allow dropping arbitrary values up the stack.

If performance of a simple compiler is a key design goal then we need to explore that, need to consider register pressure, need to consider get_and_zero_value and pick_and_void. This will also need a producer that champions and optimizes for this, but with binaryen marching elsewhere some more work may be needed here.

[sunfishcode]

It's not really a separate change or decision, it's just a consequence of the stack machine, which naturally is more lenient than structured expressions. Branches always unwind in Wasm, and I don't have a good idea on what grounds this corner case should be ruled out. Or what the typing rules to achieve that would be. It would be introducing a special case.

Why would it be a special case? We already have a place in the language where validation requires that there not be excess elements on the stack, at an end. This would just be applying the same rule in more places.

Or from the opposite direction: why does end not perform an unwind, and ignore excesss elements on the stack, just as branch does?

As for implementations, breaks have to unwind in general, and operationally there is nothing special about this case in particular. All consumers will need to implement the mechanics anyway. Your argument seems to be that it helps to discover some trivial cases of redundant code, but why would simple consumers care about identifying redundant code, and why are these corner cases more relevant than others?

The explicit-drop rules are concerned with dead definitions, which are not always caused by redundant code.

Concretely, how's their effort any different from the following example, which is obviously legal?

(block $out
(block
(i32.const 0)
(br_if $out (i32.const 1))
(drop)
)
)

In my original example, the i32.const's value has no users anywhere in the program. In this example here, the i32.const's value has a use in the program -- the drop (which we've defined to be a use).

[titzer]

On Fri, Sep 2, 2016 at 7:10 PM, Dan Gohman [email protected] wrote:

It's not really a separate change or decision, it's just a consequence of
the stack machine, which naturally is more lenient than structured
expressions. Branches always unwind in Wasm, and I don't have a good idea
on what grounds this corner case should be ruled out. Or what the typing
rules to achieve that would be. It would be introducing a special case.

Why would it be a special case? We already have a place in the language
where validation requires that there not be excess elements on the stack,
and an end. This would just be applying the same rule in more places.

Or from the opposite direction: why does end not perform an unwind, and
ignore excesss elements on the stack, just as branch does?

As for implementations, breaks have to unwind in general, and
operationally there is nothing special about this case in particular. All
consumers will need to implement the mechanics anyway. Your argument seems
to be that it helps to discover some trivial cases of redundant code, but
why would simple consumers care about identifying redundant code, and why
are these corner cases more relevant than others?

The explicit-drop rules are concerned with dead definitions, which are
not always caused by redundant code.

It's never been design constraint that single-pass compilers do not
encounter redundant code, and it'd be decidedly inconvenient to add further
requirements for producers. Producers can always choose to add explicit
drops before branches.

Concretely, how's their effort any different from the following example,
which is obviously legal?

(block $out
(block
(i32.const 0)
(br_if $out (i32.const 1))
(drop)
)
)

In my original example, the i32.const's value has no users anywhere in the
program. In this example here, the i32.const's value has a use in the
program -- the drop (which we've defined to be a use).

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
#326 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/ALnq1GwJDwDQ7S4FJQuA2ASyQ0N3wnoTks5qmFhugaJpZM4Jy2Nj
.

[ghost]

@sunfishcode Or from the opposite direction: why does end not perform an unwind, and ignore excesss elements on the stack, just as branch does?

I think it would help if this were the case, certainly good for pick as it cleans up the block local constants. With the signatures on blocks this is very practical. See also WebAssembly/design#778 where it seems it might be possible to define end as br 0 and there are other ideas there too.

[rossberg]

@sunfishcode, how do you envision distinguishing the example in question,

(block $out
  (block
    (i32.const 0) (br $out)
  )
)

from a case like

(block $out
  (block
    (i32.const 0) (br $out) (i32.add)
  )
)

that has to remain valid? Without requiring implementations to type-check
dead code, which IIRC you did not want?

Moreover, branches are just one case of unwinding. If you replace (br $out) with (return)then the same situation arises. Do you propose the
same restriction there? AFAICT, no comparable stack language has such a
restriction; certainly not the JVM or the CLR.

Or from the opposite direction: why does end not perform an unwind, and

ignore excesss elements on the stack, just as branch does?

Because our blocks are (scoped) labels, not branches. They are not intended
to have an operational effect on their own. That would be conflating two
completely different concepts.

That was the point of the explicit drop change anyway, which you were
lobbying for IIRC. This idea would basically undo that whole change.

[ghost]

@rossberg-chromium With the change discussed in WebAssembly/design#778 the unconditional branch would end the block, so (block (i32.const 0) (br $out) (i32.add)) would not be valid, or the i32.add would be part of the parent block. Then any unconditional branch out of a block would be the end, and it might be possible to require the block stack to be empty here apart from the values passed out (I do not support doing this, just noting it).

Because our blocks are (scoped) labels, not branches. They are not intended to have an operational effect on their own. That would be conflating two completely different concepts.

If blocks were just scoped labels then there would be no restriction on popping values past their boundary, so I don't see that as a useful or familiar interpretation.

We don't need the end to be semantically different to a br 0. Introducting an end with a 'completely different concept' is not necessary. When end == br 0 there is no 'conflating two completely different concepts'.

That was the point of the explicit drop change anyway, which you were lobbying for IIRC. This idea would basically undo that whole change.

It was not the only point. There were other related changes. We had a deep values stack due to the 'every operation is an expression' design, so lots of values remaining on the values stack and still potentially live as seen by a single pass compiler. Also because values were AST nodes, even void nodes took a slot. This problem has been large addressed, without drop.

A design that prohibits excess values on the stack at a block exit is not compatible with pick, and drop did not help with live values up the stack. If we need to address the problem of live values then get_and_zero_local and pick_and_void are potential general solutions.

There is little remaining technical case for the explicit-drop restrictions, and it has a very significant negative impact on the wasm design. Lets just move on please. Lets not kick this another six months down the path unresolved.

A plausible design is within sight. Lets have block ends unwind too which clears excess values, have blocks return the number of values in their block signature, adopt the changes in WebAssembly/design#778 and adopt pick to make the benefits clear and to get representative statistics and then revisit how it's going to do some fine tuning.

[rossberg]

On 5 September 2016 at 23:07, JSStats [email protected] wrote:

@rossberg-chromium https://github.com/rossberg-chromium With the change
discussed in WebAssembly/design#778
WebAssembly/design#778 the unconditional
branch would end the block, so (block (i32.const 0) (br $out) (i32.add))
would not be valid, or the i32.add would be part of the parent block.

Any design ruling out dead code has no precedent in other stack VMs, and
that's because it makes life much harder for simple producers, especially
compilers that don't want to build a CFG, like 1-pass compilers. Wasm is
not a CFG either, and that's intentional.

If blocks were just scoped labels then there would be no restriction on

popping values past their boundary, so I don't see that as a useful or
familiar interpretation.

It's a purely static MVP restriction (remnant of the expression language)
that we might lift later. It imposes no operational behaviour.

A design that prohibits excess values on the stack at a block exit is not

compatible with pick, and drop did not help with live values up the stack.

It is perfectly compatible with a "deep" pick if you lift the restriction I
just mentioned.

A plausible design is within sight. Lets have block ends unwind too which

clears excess values, have blocks return the number of values in their
block signature, adopt the changes in WebAssembly/design#778
WebAssembly/design#778 and adopt pick to make
the benefits clear and to get representative statistics and then revisit
how it's going to do some fine tuning.

Oh, if that's all... ;)

[ghost]

@rossberg-chromium Any design ruling out dead code has no precedent in other stack VMs, and that's because it makes life much harder for simple producers, especially compilers that don't want to build a CFG, like 1-pass compilers.

The discussion in WebAssembly/design#778 does not rule out dead code - I thought it did too initially, but see the clarification from @sunfishcode What it does seem to do is allow type validation of all code, so we don't have some blobs of code that are not type valid. Could you please take a closer look. We have been going over this part of the design again and again, it's been tough, and I do see some light in this area. Do you understand my proposal, do you see any problems with it?

Examples are good, so here's one to illustrate the problem for pick:

block : (i32)
  call $give_me_i32  // c1
  i32.const 2
  pick c1
  i32.sub
  pick c1
  i32.div
end

The above would be invalid because there are values left on the values stack that can not be dropped. It would help me understand your proposal if you could illustrate how it solves this?

[rossberg]

On 6 September 2016 at 08:52, JSStats [email protected] wrote:

@rossberg-chromium https://github.com/rossberg-chromium Any design
ruling out dead code has no precedent in other stack VMs, and that's
because it makes life much harder for simple producers, especially
compilers that don't want to build a CFG, like 1-pass compilers.

The discussion in WebAssembly/design#778
WebAssembly/design#778 does not rule out dead
code

Yes, but only by requiring each such compiler to wrap every branch into its
own block, which is not much better -- and btw not always possible in the
presence of the aforementioned current block typing restriction.

Examples are good, so here's one to illustrate the problem for pick:

block : (i32)
call $give_me_i32 // c1
i32.const 2
pick c1
i32.sub
pick c1
i32.div
end

The above would be invalid because there are values left on the values
stack that can not be dropped. It would help me understand your proposal if
you could illustrate how it solves this?

I see, interesting point. However, to me this example rather shows that
pick is inferior to a let-like construct, which is more structured and
would not create that problem:

(call $f)
(let $x  ;; pops $x
    (i32.const 2)
    (get_local $x)
    (i32.sub)
    (get_local $x)
    (i32.div)
)

No magic block needed.

[ghost]

@rossberg-chromium Scoped let blocks would also be able to represent the semantics, but they are not necessary, and they require opcodes for the start and end, and they still leave the values on the values stack so the let-block needs to be able to discard excess values anyway, so they are just not as efficient. All they do is add an extra control block.

Your proposal in stack machine code:

block : (i32)
  call $give_me_i32
  block (i32) : i32  // c1. aka let block
    i32.const 2
    pick c1
    i32.sub
    pick c1
    i32.div
  end  // Still has to discard the let value
end

There is one benefit in using this style. The live range on the let values might end sooner. But this can be done by adding regular blocks anyway. For example:

block : (i32)
  block : i32
    call $give_me_i32 // c1
    i32.const 2
    pick c1
    i32.sub
    pick c1
    i32.div
  end
end

Are there any benefits of your proposal that I have missed?

[sunfishcode]

@rossberg-chromium Your explanations here have been helpful for me to understand your perspective; thanks.

I agree that return should behave as br, given how the rest of the language works.

It is fascinating that there have been numerous ideas floating around for how unreachable code could be handled:

• unreachable code is a validation error
• merge end into terminators
• disable type checking in unreachable code
• unconditional branches return void
• unconditional branches have an immediate which describes the stack after them

and the example you show here is easy to understand what I'm talking about in all of the above, and hard to understand in the following:

• polymorphic type checking after unconditional branches
• optionally-enforced polymorphic type checking after unconditional branches

Do you propose the same restriction there? AFAICT, no comparable stack language has such a restriction; certainly not the JVM or the CLR.

ECMA 335 (the CLR), I.12.4 Control flow, "The evaluation stack shall be empty after the return value is popped by a ret instruction."