Skip to content

O3 fails to const propagation & folding but O2 can #7481

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 10, 2025 · 3 comments · May be fixed by #7505
Open

O3 fails to const propagation & folding but O2 can #7481

xuruiyang2002 opened this issue Apr 10, 2025 · 3 comments · May be fixed by #7505

Comments

@xuruiyang2002
Copy link
Contributor

Given the following code:

(module
  (import "External" "external_function" (func $external_function))
  (func $_start (param $0 i32) (param $1 i32) (param $2 i32) (param $3 i32) (result i32)
    (local $4 i32) (local $5 i32) (local $6 i32) (local $9 i32) (local $10 i32) (local $11 i32) (local $12 i32) (local $13 i32) (local $14 i32) (local $15 i32) (local $16 i32) (local $7 i32) (local $8 i32)
    i32.const 0
    i32.load
    local.set $7
    i32.const 0
    call $foo
    local.set $8
    local.get $7
    local.get $8
    i32.le_u
    local.set $9
    i32.const 1
    local.set $10
    local.get $9
    local.get $10
    i32.and
    local.set $11
    i32.const 4
    local.set $12
    local.get $11
    local.get $12
    i32.and
    local.set $13
    i32.const 0
    local.set $4
    block  ;; label = @1
      local.get $13
      i32.eqz
      br_if 0 (;@1;)
      call $external_function
      i32.const 0
      local.set $4
    end
    local.get $4
    call $bar)
  (func $foo (param $0 i32) (result i32) i32.const 0)
  (func $bar (param $0 i32) (result i32) i32.const 1)
  (memory $0 258 258)
  (export "_start" (func $_start)))

wasm-opt can deduce the condition of the br_if to be true by -all -O2 but cannot by -all -O3.

Analysis

The following is result of -all -O3:

 (func $_start (param $0 i32) (param $1 i32) (param $2 i32) (param $3 i32) (result i32)
  (drop
   (if (result i32)
    (i32.and
     (i32.eqz
      (i32.load
       (i32.const 0)
      )
     )
     (i32.const 4)
    )
    (then
     (call $external_function)
     (i32.const 0)
    )
    (else
     (i32.const 0)
    )
   )
  )
  (i32.const 1)
 )
)

The condition above is not deduced to zero, but it should be. This issue is somewhat similar to #7455. However, we may not be able to use fallthrough to optimize x && 0 ==> 0, as the fallthrough property doesn't deduce the value of:

    (i32.and
     (i32.eqz
      (i32.load
       (i32.const 0)
      )
     )

to

i32.const 0

This is problematic. Is there any other ways to resolve it?
@kripken
Copy link
Member

kripken commented Apr 10, 2025

I don't think the fallthrough is needed here. -O3 ends up with this condition:

  (if
   (i32.and
    (i32.eqz
     (i32.load
      (i32.const 0)
     )
    )
    (i32.const 4)
   )

That is false because eqz returns at most one bit, and (at most one bit) & 4 is always 0. That is, the left has too few bits for anything to remain after the mask on the right.

I believe this is the right area in OptimizeInstructions to add such an optimization, either right before or after these:

binaryen/src/passes/OptimizeInstructions.cpp

Lines 4667 to 4673 in 93c541d

// Comparisons can sometimes be simplified depending on the number of
// bits, e.g. (unsigned)x > y must be true if x has strictly more bits.
// A common case is a constant on the right, e.g. (x & 255) < 256 must be
// true.
// TODO: use getMinBits in more places, see ideas in
// https://github.com/WebAssembly/binaryen/issues/2898
{

@xuruiyang2002
Copy link
Contributor Author

xuruiyang2002 commented Apr 12, 2025 •
edited
Loading

I understand what you mean, that is:

any boolean & (No overlap with boolean's LSB) ==> 0:

            if (curr->op == Abstract::getBinary(type, And)) {
              if (leftMaxBits == 1) {
                // boolean & (No overlap with boolean's LSB)  ==> 0
                if (auto* c = curr->right->dynCast<Const>()) {
                  if ((1 & c->value.getInteger()) == 0) {
                    replaceCurrent(getDroppedChildrenAndAppend(
                      curr, LiteralUtils::makeZero(c->value.type, *getModule())));
                  }
                }
              }
            }

However, I am afraid that

(i32.and
 (i32.eqz
  (i32.load $0
   (i32.const 0)
  )
 )
 (i32.const 4)
)

(And) is not relational, which means we may couldn't add new rule above to fix this issue.

Should we make the And relational (in isRelational)? Or what other ways can we take to fix this issue?

@kripken
Copy link
Member

kripken commented Apr 15, 2025 •
edited
Loading

Good point, I didn't notice that that was inside optimizeRelational. And is indeed not relational, so let's not put it there.

Adding it alongside other And-related rules would make more sense. Probably near the end of OptimizeInstructions::visitBinary.

xuruiyang2002 added a commit to xuruiyang2002/binaryen that referenced this issue Apr 16, 2025
@xuruiyang2002
opt for WebAssembly#7481
b67c4ac
@xuruiyang2002 xuruiyang2002 linked a pull request Apr 16, 2025 that will close this issue
Open
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
2 participants
@kripken @xuruiyang2002