O3 fails to const propagation & folding but O2 can

[xuruiyang2002]

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]

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]

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]

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.