Skip to content

[Unhoisted] [Binary] [Might not fallthrough] load & store order affects the constant propagation in binaryOp #7489

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
xuruiyang2002 opened this issue Apr 12, 2025 · 3 comments · May be fixed by #7506
Open

[Unhoisted] [Binary] [Might not fallthrough] load & store order affects the constant propagation in binaryOp #7489

xuruiyang2002 opened this issue Apr 12, 2025 · 3 comments · May be fixed by #7506

Comments

@xuruiyang2002
Copy link
Contributor

Given the following code:

(module
  (import "External" "external_function" (func $external_function))
  (func $_start 
    i32.const 0
    i32.const 0
    call $foo)
  (func $foo (param $0 i32) (param $2 i32) 
    block ;; label = @1
      i32.const 0
      i32.load
      drop
      i32.const 1
      i32.load
      local.set $2
      i32.const 1
      local.set $0
      local.get $2
      br_if 0 (;@1;)
      i32.const 1
      local.set $0
      local.get $0
      br_if 0 (;@1;)
      i32.const 0
      local.set $0
    end
    block ;; label = @1
      local.get $0
      br_if 0 (;@1;)
      call $external_function
    end)
  (memory $0 258 258)
  (export "_start" (func $_start)))

wasm-opt (c528c7e) can deduce the condition of branch (in the second block) to true by -all -O2, but cannot by -all -O3.

Below is the optimized code by -all -O3:

  (if
   (i32.eqz
    (block $block (result i32)
     (drop
      (i32.load (i32.const 0))
     )
     (drop
      (br_if $block
       (i32.const 1)
       (i32.load (i32.const 1))
      )
     )
     (i32.const 1)
    )
   )
   (then (call $external_function))
  )

It appears that the constant 1 is "buried" within the blocks and should be hoisted out so it can be recognized by i32.eqz.

This is similar to #7455 (where a constant value should be hoisted out in a binary operation). The same principle could be apply to unary operations. However, the key difference here is that these blocks here have names thus preventing them from being "fallthrough".

Here is the relevant code in getImmediateFallthroughPtr:

binaryen/src/ir/properties.h

Lines 288 to 292 in 93c541d

} else if (auto* block = curr->dynCast<Block>()) {
// if no name, we can't be broken to, and then can look at the fallthrough
if (!block->name.is() && block->list.size() > 0) {
return &block->list.back();
}

What do you think? Is there any better way to resolve it?
@xuruiyang2002 xuruiyang2002 changed the title Unhoisted load or store in block prevents merge-blocks and constant propagation [Unhoisted] [Binary] [Might not fallthrough] load & store order affects the constant propagation in binaryOp Apr 14, 2025
@xuruiyang2002
Copy link
Contributor Author

Similar but different to #7455, #7491, which could be resolved by fallthrough, this issue is slightly more complex, I think it would be better to resolve them firstly and then return to this one.

@kripken
Copy link
Member

kripken commented Apr 14, 2025

Looks like we can't move the br_if $block out of the $block since it refers to it, and we can't use the fallthrough value of the block because the return value might be the br_if's value, not the final value.

However, the br_if's value is the same as the final value, so there is an optimization opportunity here,

(block $block (result i32)
 ..
 (drop
  (br_if $block
   (value)
   (condition)
  )
 )
 (value)
)

=>

(block $block (result i32)
 ..
 (drop
  (condition)
 )
 (value)
)

That is, when a block ends in a br_if and a value, if the br_if has the same value, and the value has no side effects, we don't need the br_if. This would go into RemoveUnusedBrs which has similar optimizations for the tails of blocks.

xuruiyang2002 added a commit to xuruiyang2002/binaryen that referenced this issue Apr 16, 2025
@xuruiyang2002
opt for WebAssembly#7489
2312382
@xuruiyang2002 xuruiyang2002 linked a pull request Apr 16, 2025 that will close this issue
Open
@xuruiyang2002
Copy link
Contributor Author

xuruiyang2002 commented Apr 16, 2025 •
edited
Loading

Thanks for guidance. I've tried to fix as you suggested.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Optimize block tails where a dropped br_if's value is redundant xuruiyang2002/binaryen
2 participants
@kripken @xuruiyang2002