Aggressive optimization of `unreachable`s?

[juj]

I have written a Binaryen pass that emits unreachables into the wasm tree. That produces something like this:

 (func $17 (param $0 i32) (param $1 i32)
  (block $label$1
   (br_if $label$1
    (i32.eqz
     (local.get $1)
    )
   )
   (br_if $label$1
    (call $26
     (local.get $1)
     (i32.load offset=32
      (i32.load
       (local.get $0)
      )
     )
    )
   )
   (drop
    (i32.load
     (i32.const 3308276)
    )
   )
   (unreachable)                 # Added by my pass
  )
 )

Since the end of the function $17 is unreachable, I'd like an optimizer to realize that all the preceding statements are then unreachable as well since the control unconditionally flows to that unreachable. So the function could be collapsed into a single

 (func $17 (param $0 i32) (param $1 i32)
   (unreachable)
  )

and then further inlined into its callers, and the unreachable propagated that way to their callers and their callers, as efficiently as is possible.

I was trying to run different optimization passes in wasm-opt, ranging from --dce, --inlining-optimizing, --O4 and -Oz and pretty much anything else that had a summary description that it might optimize something,

--inlining-optimizing --dce --coalesce-locals --code-folding --code-pushing --const-hoisting --dae-optimizing --duplicate-function-elimination --local-cse --once-reduction --optimize-for-js --optimize-instructions --optimize-stack-ir --post-emscripten --merge-blocks --merge-locals --merge-similar-functions --remove-unused-brs --remove-unused-names --remove-unused-module-elements --remove-unused-nonfunction-module-elements --reorder-locals --rse

to see if one of the existing passes would get aggressive with throwing code away when there is an unreachable on a potentially critical path. Reading the code in dead-code-elimination pass seems like it would do something like this, however I find it being unsuccessful with modifying func $17 above.

Is there a way with Binaryen to have func $17 get nuked from orbit altogether due to its unreachable, and everything that would ripple to?

Attached the .wasm file that contains func $17 if it is interesting to take a hands on peek: ozm.zip.

[kripken]

The traps-never-happen option is meant to do this:

https://github.com/WebAssembly/binaryen/blob/6f37355ae24449c178abcdb08294d0fb3ef5f50c/src/pass.h#L119-L121

So in principle wasm-opt -tnh should do this. However, the part about removing code that must reach an unreachable has not been implemented yet.

[juj]

Thanks - gave --traps-never-happen a try, though indeed looks like that does not help the other optimization passes to reduce either.

I'll see if I can develop some pruning myself as part of when I emit the unreachables, seems like I should be able to walk back the Block I emit the unreachable in and nuke the preceding instructions - inside a single Block all the code should always be linear?

[kripken]

Where do those Blocks come from? If there are no branches in them that sounds good, but in general they can contain anything:

(block
  ;; not removable
  (br_if ..)
  ;; removable
  (unreachable)
)

For the general solution I think we need CFGWalker. The BasicBlocks there do contain linear control flow without branches. This would be good to look into I think!

[juj]

Where do those Blocks come from?

The blocks might be emitted generally from LLVM as part of the C/C++ program codegen.

For the general solution I think we need CFGWalker. The BasicBlocks there do contain linear control flow without branches. This would be good to look into I think!

Gotcha - btw I wonder if there would be a description/doc somewhere about the different walkers - I am still a bit hazy on when to utilize which, trying to monkey code off existing passes but it can be a bit hard :)

I think Clang/LLVM in general interprets __builtin_unreachable() to mean code that can be optimized as if the producer statically knows that code will never be reached, hence it will eagerly delete everything that will unconditionally lead to an unreachable(?)

I thought the semantics of the Wasm unreachable instruction would be the same? Even without needing to annotate/configure wasm-opt to run with --traps-never-happen?

For some reason when I was trying these optimizations yesterday, I found I was unable to get wasm-opt to optimize away a function

 (func $17 (param $0 i32) (param $1 i32)
   (unreachable)
  )

via inlining to callers. Though not completely sure if that function was an export (it turns out really hard to search through a wast in my text editor since the "search whole words" feature breaks on $ signs, so finding all references to a func $17 is getting swamped - I'll need to rerun these with -g to retain identifiers)

I'm heading off on midsummer vacation for July, will be back in August, keen to pick up on this train of investigation once I get back.

[kripken]

Gotcha - btw I wonder if there would be a description/doc somewhere about the different walkers - I am still a bit hazy on when to utilize which, trying to monkey code off existing passes but it can be a bit hard :)

Good point... we should probably write that up. I can look into it.

I think Clang/LLVM in general interprets __builtin_unreachable() to mean code that can be optimized as if the producer statically knows that code will never be reached, hence it will eagerly delete everything that will unconditionally lead to an unreachable(?) I thought the semantics of the Wasm unreachable instruction would be the same? Even without needing to annotate/configure wasm-opt to run with --traps-never-happen?

LLVM works that way, correct, but in wasm unreachable just means trap. I'm not sure why it was named unreachable actually - kind of unfortunate... For example, print("foo"); unreachable must print "foo" before trapping in a wasm VM. So this has to be an unsafe opt-in flag.

For some reason when I was trying these optimizations yesterday, I found I was unable to get wasm-opt to optimize away a function

Hmm, probably it was either exported or called indirectly. But direct calls should still get it inlined.

I'm heading off on midsummer vacation for July, will be back in August, keen to pick up on this train of investigation once I get back.

Sounds good! Yeah, there might be large opportunities here. We've focused on traps-never-happen in wasm GC so far, and it helps a lot there already.

[kripken]

(wrote up some quick docs here: https://github.com/WebAssembly/binaryen/wiki/Walking-and-Visiting-in-Binaryen-IR)