1510807 - Lowering and Codegen for MModI

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, enhancement, P2)

Description

[Sean Stangl [:sstangl]]

Attachment: 0001-Lowering-and-Codegen-for-MModI.-r.patch

This implements lowering and codegen for MModI, which blocked a significant number of jit-tests.

The codegen is at least fairly difficult to read, but there are helpful comments. In particular visitModMaskI() is a compromise between the already-existing ARM and MIPS32/64 implementations, adapted to ARM64. I attempted to make it more readable for a reviewer.

The "Soft" LIR variants are not needed on ARM64 -- those are for systems that may not have a division instruction, but ARMv8 always has division.

The code appears to pass the sanity checks I've thrown at it.

Comment 1

[Sean Stangl [:sstangl]]

Comment on attachment 9028485 [details] [diff] [review]
0001-Lowering-and-Codegen-for-MModI.-r.patch

Redirecting review to nbp per his gracious request.

Comment 2

[Sean Stangl [:sstangl]]

Attachment: 0005-Bug-1510807-Lowering-and-Codegen-for-MModI.-r.patch

Rebased on top of Gecko style changes.

Comment 3

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

Comment on attachment 9028973 [details] [diff] [review]
0005-Bug-1510807-Lowering-and-Codegen-for-MModI.-r.patch

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

::: js/src/jit/arm64/CodeGenerator-arm64.cpp
@@ +459,5 @@
>    MOZ_CRASH("CodeGeneratorARM64::modICommon");
>  }
>  
> +void CodeGenerator::visitModI(LModI* ins) {
> +  MMod* mir = ins->mir();

nit: Add a MOZ_CRASH in case we are compiling for WASM.

@@ +483,5 @@
> +  masm.Msub(output, output, rhs, lhs);
> +
> +  if (mir->canBeNegativeDividend() && !mir->isTruncated()) {
> +    // If output == 0 and lhs < 0, then the result should be double -0.0.
> +    masm.Cbnz(output, &done);

nit: Add a comment that this also expected to catch the case where lhs == INT_MIN and rhs == -1:

  output = INT_MIN - ((INT_MIN / -1) * -1)
         = INT_MIN - (INT_MIN * -1)
         = INT_MIN - INT_MIN
         = 0

@@ +552,5 @@
> +
> +  // We wish to compute x % (1<<y) - 1 for a known constant, y.
> +  //
> +  // 1. Let b = (1<<y) and C = (1<<y)-1, then think of the 32 bit dividend as
> +  // a number in base b, namely c_0*1 + c_1*b + c_2*b^2 ... c_n*b^n

comment-nit: replace c_0 by x_0 to avoid confusion with C.

@@ +600,5 @@
> +    masm.Subs(scratch32, dest32, Operand(mask));
> +    // If (sum - C) > 0, store sum - C back into sum, thus performing a modulus.
> +    {
> +      Label sumSigned;
> +      masm.branch32(Assembler::Signed, scratch, scratch, &sumSigned);

nit: Move this out-side of this loop, if we consider random inputs, this branch would be taken only half of the time which is not great for branch prediction.  Moving it out of this bit-extracting loop will reduce the number of operation of the Mod-mask, and make this branch become more frequently taken.

before = (…(((0 + c_0) % C + c_1) % C + c_2) % C) … + c_n) % C
after = (c_0 + c_1 + c_2 + c_3 + … + c_n) - C - C

@@ +607,5 @@
> +    }
> +    // Get rid of the bits that we extracted before.
> +    masm.Lsr(remain32, remain32, shift);
> +    // If the shift produced zero, finish, otherwise, continue in the loop.
> +    masm.branchTest32(Assembler::NonZero, remain, remain, &loop);

nit: n of c_n is known ahead of time and it is limited to 16. Maybe we should unroll this loop at compile time and remove one register use, and compare instructions:

  // Compute: c_0 + c_1 + ... + c_n
  int32_t lsb = 0;
  while (lsb < 32) {
    masm.{ ubfx scratch32, src32, #%lsb, #%shift }
    masm.{ add dest32, dest32, scratch32 }
    lsb += shift;
  }
  masm.{ ubfx scratch32, src32, #%lsb, #%(32 - lsb) }
  masm.{ add dest32, dest32, scratch32 }

This code removes the LSR, CMP and B.nz instructions.

We can later specialize this instruction based on the range of the source operand as well.

@@ +618,5 @@
> +    // If the hold was non-zero, negate the result to match JS expectations.
> +    masm.branchTest32(Assembler::NotSigned, hold, hold, &done);
> +    if (mir->canBeNegativeDividend() && !mir->isTruncated()) {
> +      // Bail in case of negative zero.
> +      bailoutTest32(Assembler::Zero, hold, hold, ins->snapshot());

This should be "dest" instead of "hold".

@@ +1290,5 @@
> +  masm.Msub(output, output, rhs, lhs);
> +
> +  if (!mir->isTruncated()) {
> +    // Bail if the output would be negative.
> +    bailoutCmp32(Assembler::LessThan, output, Imm32(0), ins->snapshot());

comment-nit: Add comment that mod->unsigned() allow Uint32 to flow as input of visitUMod, and we should ensure that these are not converted into signed result.

Comment 4

[Sean Stangl [:sstangl]]

Attachment: 0001-Bug-1510807-Lowering-and-Codegen-for-MModI.-r-nbp.patch

Carrying r+. Applied comment changes.

I demurred from applying the code changes because the logic follows a well-tested pattern in the MIPS and X64 codebases. My personal greatest priority is to not spend time debugging mod operations, so I kept it the same as with the other codebases rather than introduce something novel that may have bugs I don't understand.

If in the future we want to make those changes, they are far-reaching across different targets.

Comment 5

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/f8aaaf974be9
Lowering and Codegen for MModI. r=nbp

Comment 6

[Razvan Maries]

https://hg.mozilla.org/mozilla-central/rev/f8aaaf974be9