1331346 - Add support for unsigned division and comparison

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine: JIT, defect, P3)

Description

[Sander Mathijs van Veen]

Attachment: support-unsigned-division-and-comparison.patch

Use unsigned division and unsigned comparison when the operands are uint32.

Comment 1

[Sander Mathijs van Veen]

Comment on attachment 8827105 [details] [diff] [review]
support-unsigned-division-and-comparison.patch

Since this patch touches range analysis, I'll ask for two reviews.

Comment 2

[Nicolas B. Pierron [:nbp] {away}]

Comment on attachment 8827105 [details] [diff] [review]
support-unsigned-division-and-comparison.patch

Review of attachment 8827105 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/MIR.cpp
@@ +2841,5 @@
> +            hasOnlyUnsignedUses = false;
> +            break;
> +        }
> +
> +        if (hasOnlyUnsignedUses)

nit: consider removed uses as not having only unsigned uses.  This is also true for observable slots.

Comment 3

[Nicolas B. Pierron [:nbp] {away}]

Comment on attachment 8827105 [details] [diff] [review]
support-unsigned-division-and-comparison.patch

Review of attachment 8827105 [details] [diff] [review]:
-----------------------------------------------------------------

Add tests cases, and fix the following comments.

::: js/src/jit/RangeAnalysis.cpp
@@ +1683,5 @@
> +
> +        // Unsigned division by a non-zero rhs will return a uint32 value.
> +        // If the RHS is zero, a bailout will happen and the result becomes
> +        // a double value.
> +        unsigned_ = true;

This should be moved to MDiv::collectRangeInfoPreTrunc.

@@ +1684,5 @@
> +        // Unsigned division by a non-zero rhs will return a uint32 value.
> +        // If the RHS is zero, a bailout will happen and the result becomes
> +        // a double value.
> +        unsigned_ = true;
> +        setRange(Range::NewUInt32Range(alloc, 0, UINT32_MAX));

Not having an early return here means that if the range of lhs nor rhs are wrapped around, then we will attempt to call setRange twice, which will assert.

Add a test case to catch this issue, and add an early return to fix it.

Comment 4

[Sander Mathijs van Veen]

Attachment: support-unsigned-division-and-comparison.patch

I've moved |unsigned_ = true| to |MDiv::collectRangeInfoPreTrunc|.

I've added the early return. Without the early return and with |MOZ_ASSERT(!range())| before the following setRange() calls in |MDiv::computeRange()|, I've verified that the test |jit-test/tests/asm.js/testExpressions.js| covers the path where two setRange calls are performed. With the early return, this test does not fail anymore. The test did not fail before because there was no assertion that verified that setRange() should only be called once. 

I think that adding |MOZ_ASSERT(!range())| to |setRange()| is useful to prevent allocating more memory than necessary, but it is better to do it in a separate bug because it is unrelated to udiv and ucmp. Therefore, I've removed the |MOZ_ASSERT(!range())| lines from this patch, to avoid asserting this twice.

Comment 5

[Jan de Mooij [:jandem]]

Comment on attachment 8834455 [details] [diff] [review]
support-unsigned-division-and-comparison.patch

Review of attachment 8834455 [details] [diff] [review]:
-----------------------------------------------------------------

sunfish and nbp are probably better reviewers for this patch.

(I'm also wondering if at some point it would be better to add MIRType::Uint32 instead of working around it.)

Comment 6

[Dan Gohman [:sunfish]]

Comment on attachment 8834455 [details] [diff] [review]
support-unsigned-division-and-comparison.patch

Review of attachment 8834455 [details] [diff] [review]:
-----------------------------------------------------------------

I agree that adding a MIRType::Uint32 is an appealing direction to head in, as the current system with IsUint32Type and friends is difficult to reason about.

::: js/src/jit/IonAnalysis.cpp
@@ +573,5 @@
>      if (def->type() != MIRType::Int32)
>          return false;
>  
> +    if (def->isConstant())
> +        return def->toConstant()->toInt32() >= 0;

Changing IsUint32Type is a little tricky, because it's also used in subtle ways in MTruncateToInt32::foldsTo and MToInt32::foldsTo. It looks like this change would mean that MTruncateToInt32::foldsTo wouldn't fold when the operand is a non-negative constant, which would seem to be unintended. Is that true?

::: js/src/jit/MIR.cpp
@@ +1779,5 @@
> +      case Compare_DoubleMaybeCoerceRHS:
> +        out.printf(" [double]");
> +        break;
> +      case Compare_Float32:
> +        out.printf(" [float]");

For consistency with SM's naming and avoidance of ambiguity, this should say "float32".

Comment 7

[Sander Mathijs van Veen]

Attachment: support-unsigned-division-and-comparison.patch

Removed changes to IsUint32Type(), and used 'float32' instead.

Comment 8

[Lars T Hansen [:lth]]

FWIW, there's a discussion going on over in bug 1343007 that is somewhat related to this.  The conclusion there is *probably* going to be that MMod, which now has the single 'isUnsigned' flag that has slightly unclear semantics, will acquire two new flags called something like 'alwaysSigned' and 'alwaysUnsigned', which will be required to support WebAssembly properly without introducing new nodes for Div and Mod just for that purpose.  If MDiv acquires the same optimization as MMod around sniffing unsignedness of the operand, it will need a similar fix.

Comment 9

[Dan Gohman [:sunfish]]

Comment on attachment 8844156 [details] [diff] [review]
support-unsigned-division-and-comparison.patch

Review of attachment 8844156 [details] [diff] [review]:
-----------------------------------------------------------------

Looks good to me.

Comment 10

[Nicolas B. Pierron [:nbp] {away}]

Comment on attachment 8844156 [details] [diff] [review]
support-unsigned-division-and-comparison.patch

Review of attachment 8844156 [details] [diff] [review]:
-----------------------------------------------------------------

Sorry for the late reply.

UInt types provided by range analysis is ok-ish but the lack of consistency in the rest of the engine already caused us issues in the past.
For safety and performance reasons, I prefer to decline this work unless there is a good performance win in some actual website. In which case I should probably re-evaluate this issue.

::: js/src/jit/RangeAnalysis.cpp
@@ +1690,5 @@
> +
> +        // Unsigned division by a non-zero rhs will return a uint32 value.
> +        // If the RHS is zero, a bailout will happen and the result becomes
> +        // a double value.
> +        setRange(Range::NewUInt32Range(alloc, 0, UINT32_MAX));

`3/2` is composed of 2 unsigned integers, but would not result in an unsigned result.
It sounds to me that this a greedy optimization which is more likely to backfire by addings tons of bailout (at the time), and cause a recompilation without much guarantees that this would not be the case.