OptimizeInstructions does not optimize divide by zero

[xuruiyang2002]

Given the following code:

(module
  (import "External" "external_function" (func $external_function))
  (func $foo (result i32)
    (local i32)
    i32.const 0
    local.get 0 
    i32.div_u
    return)
  (func $_start
    block
      call $foo
      i32.eqz
      br_if 0
      call $external_function
    end)
  (export "_start" (func $_start)))

The -O2 produces

(module
 (type $0 (func))
 (export "_start" (func $_start))
 (func $_start
  (drop
   (i32.div_u
    (i32.const 0)
    (i32.const 0)
   )
  )
 )
)

The -O3 produces

(module
 (type $0 (func))
 (import "External" "external_function" (func $external_function))
 (export "_start" (func $_start))
 (func $_start
  (if
   (i32.div_u
    (i32.const 0)
    (i32.const 0)
   )
   (then
    (call $external_function)
   )
  )
 )
)

wasm-opt version: d0d970c

According to the spec, the result of i32.div_u(num, 0) is undefined, in this issue, the O2 deduces the result of i32.eqz (undefined) to be true thus eliminates the branch, which happens in the inlining-optimizing.

Since division always traps, is there any miscompliation in this O2 optimizing pipeline?

[kripken]

This isn't miscompiled, since it traps in all cases, before optimizations, -O2, and -O3.

The difference between 2 and 3 reduces to the difference between these:

(module
 (type $0 (func))
 (import "External" "external_function" (func $external_function))
 (export "_start" (func $_start))
 (func $_start
  (local $x i32)
  (if
   (i32.div_u
    (i32.const 0)
    (local.get $x)
   )
   (then
    (call $external_function)
   )
  )
 )
)

and

(module
 (type $0 (func))
 (import "External" "external_function" (func $external_function))
 (export "_start" (func $_start))
 (func $_start
  ;; the local vanished
  (if
   (i32.div_u
    (i32.const 0)
    (i32.const 0) ;; this changed
   )
   (then
    (call $external_function)
   )
  )
 )
)

--optimize-instructions handles the first but not the second. It should handle the second too. I'm not sure where in OptimizeInstructions that is handled.

[xuruiyang2002]

Yes, both of the two optimized results trap. But I am still confused that why O2 could eliminate the branch, because there must be an assumption here: wasm-opt knows the semantics of "i32.eqz (undefined)" is. As you can see in O2 result, it reduces the i32.eqz (undefined) to be true. Is this reasonable? Or maybe I still misunderstand what you mean, thus can you explain it more clearly?

[kripken]

-O2 manages to optimize because it ends up in the first case I showed: it has 0 / x where x is unknown. It optimizes that to zero, and keeps the division for the possible trap. The zero then lets us remove the if.

-O3 ends up in the second case I showed: it has 0 / 0, and it ignores that, so the if condition never gets simplified.

[kripken]

(-O3 ends up in the second case because it propagates constants better, so the 0 gets to that location.)

[xuruiyang2002]

I agree with you. In your provided two cases, the second case should be handled, since the condition is a trap. But I didn't seem to see any rule for handling this. Does there lack a rule for it?

[kripken]

Yes, this looks like a missing optimization.

[xuruiyang2002]

Since there is no rule for this case, would it be proper to add the fix like below in optimizeBoolean?

      } else if (binary->op == DivUInt32) {
        if (Match::matches(binary,
                           Match::binary(Abstract::DivU,
                                         Match::constant(0),
                                         Match::constant(0)))) {
          // Optimize later branch while still preserving trap
          return getDroppedChildrenAndAppend(
            binary, LiteralUtils::makeZero(Type::i32, *getModule()));
        }
      }

It fixes, however, I'm afraid it might be a bit awkward. Is there any better way?

[kripken]

I don't think we need to add a new rule for 0 / 0. There should already be a rule for 0 / x, which already works. We should find that case, and generalize it to also handle 0 on the bottom (and to drop the input in that case, as it must still trap). Searching for rules with "div" might be a good way to find it.

[xuruiyang2002]

There should already be a rule for 0 / x, which already works. ... Searching for rules with "div" might be a good way to find it.

Thanks for guidance. The directly issues lies in the following rule for checking whether binary operator emitting zero bits:

binaryen/src/passes/OptimizeInstructions.cpp

Lines 317 to 323 in e6f1c53

	Expression* replaceZeroBitsWithZero(Expression* curr) {
	// We should never be called with a constant.
	assert(!curr->is<Const>());
	if (!curr->type.isInteger() || Bits::getMaxBits(curr, this) != 0) {
	return nullptr;
	}

It treats (i32.div_u (i32.const 0) (local.get $x)) to be emitting zero, while does not for (i32.div_u (i32.const 0) (i32.const 0)).

In details, the getMaxBits doesn't treat (i32.div_u (i32.const 0) (i32.const 0)) to be emitting zero.

binaryen/src/ir/bits.h

Lines 194 to 201 in e6f1c53

	case DivUInt32: {
	int32_t maxBitsLeft = getMaxBits(binary->left, localInfoProvider);
	if (auto* c = binary->right->dynCast<Const>()) {
	int32_t bitsRight = getMaxBits(c);
	return std::max(0, maxBitsLeft - bitsRight + 1);
	}
	return maxBitsLeft;
	}

Is that a missing consideration for div _u(0, 0)? Or maybe this was intentional on the part of the developer?

[kripken]

Yes, that looks like the bug, good find. On line 198, the std::max should also do std::min with maxBitsLeft, since division can never increase the bits. Or we could special-case 0 max bits on the right, as those would be the same.

Would you like to open a PR with that?

[xuruiyang2002]

Yes, the result of division cannot have more bits than the dividend (maxBitsLeft).

I've opened a PR as you suggested (with the first solution).