--simplify-locals moves side effects past stores

[sunfishcode]

Given the following input:

(module
  (memory 1)
  (export "memory" memory)
  (export "main" $main)
  (func $main (result i32) (param $x i32) (param $y i32)
    (local $z i32)
    (set_local $z (i32.div_s (get_local $x) (get_local $y)))
    (i32.store offset=0 (i32.const 0) (i32.const 0))
    (i32.store offset=4 (i32.const 0) (get_local $z))
    (i32.const 0)
  )
)

binaryen-shell with --simplify-locals produces this:

(module
  (memory 1)
  (export "memory" memory)
  (export "main" $main)
  (func $main (param $x i32) (param $y i32) (result i32)
    (local $z i32)
    (nop)
    (i32.store
      (i32.const 0)
      (i32.const 0)
    )
    (i32.store offset=4
      (i32.const 0)
      (i32.div_s
        (get_local $x)
        (get_local $y)
      )
    )
    (i32.const 0)
  )
)

The i32.div_s was moved past the first store. This is an observable change in behavior, because if $y is 0, the divide traps, and in the original program the first store doesn't happen. In the transformed code, the store does happen.

[kripken]

Thanks, interesting problem. Not sure what to do here. Maybe the two main options are

1. Consider potentially-trapping operations like div, some of the casts, etc., as having side effects, so the optimizer won't reorder them.
2. Add an option for imprecise optimizations. asm2wasm already has this. This would be a flag for the optimizer to be able to do things like assume math and conversions do not trap, so if they do, some reordering might occur.

What do you suggest? Is there a standard compiler behavior for stuff like this?

[sunfishcode]

An option for controlling imprecise optimizations sounds reasonable to me. I can see uses for optimizing arbitrary wasm without changing its behavior in any way; you could do things like run the spec tests with that optimization run on them, and they should all continue to pass. I can also see uses for developers who know they don't care about observing every last store in the event of a trap.

[kripken]

Ok, what's a conventional name for such a thing? --fast-math perhaps? Or should it be more specific like --assume-math-cannot-trap?

[sunfishcode]

--fast-math typically implies a lot of other things, like relaxed precision, so that doesn't seem quite right. I like --assume-math-cannot-trap. Or how about --assume-no-math-traps?

[titzer]

+1 to not changing the behavior in the default case and having a compiler option.

AFAIU, C undefined behavior would allow this reordering within the same control equivalence class; i.e. whenever undefined behavior becomes inevitable, that entire execution path becomes invalid and the compiler is free to do what it likes. So for producers coming from C, this optimization is OK (provided it doesn't lift across non-terminating calls). But from a pure WASM perspective this optimization is unsound.

[jfbastien]

Why even have the option? Is it useful?

[kripken]

@jfbastien The option would prevent disabling some code reduction optimizations, so it sounds useful. Or do you think it would be rare in practice to see such potentially-trapping operations be movable?

[jfbastien]

Right, I would just respect the compiler's output and not even try doing more. No need for the option, just don't do it.

[kripken]

I guess you're thinking of LLVM-generated code? But another use case is for a compiler to let Binaryen do optimization for it. It could then say, optimize under this assumption, or not.

[kripken]

On more thought, I'd like to generalize this to not just math. For example, it is nice if the optimizer can assume that loads do not trap unless told otherwise.

How about --assume-no-implicit-traps? (Implicit, since (unreachable) should still trap even in this case?)

[titzer]

One thing to watch out for is moving trapping operations themselves, since they may have a control condition that guards that they don't trap. (e.g. x != 0? 3 / x : 5)

[kripken]

898 tightens our handling of implicit traps, and in particular fixes the issue @titzer warned about in the previous comment here. Also adds more infrastructure that builds on #788 for allowing more detailed handling in the future.