869473 - Optimize DivI with a power of two divisor when the numerator is positive.

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Douglas Crosher [:dougc]]

Bug 868535 and Bug 868708 optimized DivI for a power of two divisor.  When the numerator is positive these can be further optimized to a single instruction shift and this can be done using type range information.

Comment 1

[Douglas Crosher [:dougc]]

Attachment: Optimize DivI with a power of two divisor when the numerator is not negative.

For the x86 and x64 the existing DivPowTwoI LIR OP needs a LHS Copy register, but this is not needed in the optimized case handled here so the LHS register is simply copied to this slot rather that creating a new OP.  Let me know if an additional OP is preferred.

The ARM implementation does not have this issue as it uses the Scratch register.

The code generator uses the range information directly.  If it is preferred to abstract the use of the range information differently then let me know and it can be reworked.

Tests have been added to cover the new code paths.

Comment 2

[Douglas Crosher [:dougc]]

Attachment: Optimize DivI with a power of two divisor when the numerator is not negative.

Remove an obsolete comment that had been missed.

Comment 3

[Dan Gohman [:sunfish]]

Comment on attachment 746775 [details] [diff] [review]
Optimize DivI with a power of two divisor when the numerator is not negative.

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

Would it make sense to have Lowering just create an LShiftI object instead, since it's already doing a range check? That would avoid the need for a mandatory range check in LDivPowTwoI Codegen.

Comment 4

[Douglas Crosher [:dougc]]

Comment on attachment 746775 [details] [diff] [review]
Optimize DivI with a power of two divisor when the numerator is not negative.

Let me explore this further. The negative case might also be handled,
better, and it might be better to split it into separate patches for
the ARM and x86.  Any further feedback would be welcomed.

Comment 5

[Douglas Crosher [:dougc]]

Attachment: Optimize DivI with a power of two divisor when the numerator is not negative

Rebased. It now uses the collectRangeInfoPreTrunc infastructure.

Comment 6

[Dan Gohman [:sunfish]]

Comment on attachment 8339745 [details] [diff] [review]
Optimize DivI with a power of two divisor when the numerator is not negative

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

::: js/src/jit/shared/CodeGenerator-x86-shared.cpp
@@ +878,4 @@
>          // Adjust the value so that shifting produces a correctly rounded result
>          // when the numerator is negative. See 10-1 "Signed Division by a Known
>          // Power of 2" in Henry S. Warren, Jr.'s Hacker's Delight.
> +        Register lhsCopy = ToRegister(ins->numeratorCopy());

While you're here, could you add a JS_ASSERT(lhsCopy != lhs)? The code depends on this assumption, and the way it gets implemented turns out to be fairly subtle, so it'd be good to have the extra sanity check.

::: js/src/jit/shared/LIR-x86-shared.h
@@ +61,5 @@
> +    LDivPowTwoI(const LAllocation &lhs, int32_t shift)
> +      : shift_(shift)
> +    {
> +        setOperand(0, lhs);
> +        setOperand(1, lhs);

Since operand 1 is not actually used in this case, can you omit the second setOperand here?

Comment 7

[Douglas Crosher [:dougc]]

Attachment: Optimize DivI with a power of two divisor when the numerator is not negative

Thank you for the quick review.

Address reviewer feedback. Carrying forward r+.

Comment 8

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/2eb5f81c77ec

Comment 9

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/2eb5f81c77ec