568737 - Incorrect overflow tests generated for MIPS

Status: RESOLVED FIXED

(Tamarin Graveyard :: Baseline JIT (CodegenLIR), defect, P2)

Description

[William Maddox]

a = immi 2147483647
b = immi 1
c = addxovi a b	
reti c

The result should be an exit.  Instead, the result wraps around
to a negative value:

Output is: -2147483648

The culprit appears to be the following code generated for the
addition with overflow check:

      immi1 = immi 2147483647
  002aab7fb8   lui $v0, 0x8000
  002aab7fbc   addiu $v0, $v0, -1
      immi2 = immi 1
      addxovi1 = addxovi immi1/*2147483647*/, immi2/*1*/ -> line=3 (GuardID=000)
  002aab7fc0   addiu $v0, $v0, 1
  002aab7fc4   slt $at, $v0, $v0
  002aab7fc8   bne $zr, $at, 0x2aac7f98
  002aab7fcc   nop

See Assembler:asm_arith() [snippet below]:

            case LIR_addxovi:
                SLT(AT, rr, ra);
                ADDU(rr, ra, rb);

It appears that we are trying to generate code like this:

  addu $a0, $v0, $v1
  slt $at, $a0, $v0

Instead, because we are generating an addiu (with an immediate
operand), the register given the role 'ra' above is the same as
the result register, and not the first operand as expected.

Comment 1

[William Maddox]

Even if the apparently intended code were generated, the
test would not be correct, as (-2147483648) + (-1) wraps
around to a positive number, and would thus fail to be
detected.

Comment 2

[Chris Dearman]

Agreed on both counts.
I'll resync with the head of tree and submit a patch.

Comment 3

[William Maddox]

Assigning bug to Chris Dearman per his comment above.

Comment 4

[Chris Dearman]

Attachment: Reimplementation of overflow detection

This patch fixes the overflow detection code generation.
It's been tested in nanojit-central and tamarin-redux

Comment 5

[William Maddox]

Looking at register-to-register addition, I tabulated the relevant cases and
the code that would be generated:

r0 = r0 + r0    (ra == rb == rr)

move  $t,$r0
addu  $r0,$r0,$r0
xor   $at,$r0,$t
srl   $at,31

r0 = r0 + r1    (rr == ra != rb)

move  $t,$r0
addu  $r0,$r0,$r1
xor   $at,$r0,$t
xor   $t,$r0,$r1
and   $at,$t
srl   $at,31

r0 = r1 + r2    (rb != ra, ra != rr, rb != rr)

addu  $r0,$r1,$r2
xor   $at,$r0,$r1
xor   $t,$r0,$r2
and   $at,$t
srl   $at,31

r0 = r1 + r1    (ra == rb, ra != rr, rb != rr)

addu  $r0,$r1,$r1
xor   $at,$r0,$r1
xor   $t,$r0,$r1     # <-- not needed
and   $at,$t         # <-- not needed
srl   $at,31


# Hmm, this doesn't look right
r0 = r1 + r0    (rb == rr != ra)

addu  $r0,$r1,$r0
xor   $at,$r0,$r1
srl   $at,31

This last case appears incorrect.  Also, the code generated for r0 = r1 + r0 and the code for r0 = r0 + r1 should be duals of each other, due to the commutativity of addition.

It is possible that the expression has been previously canonicalized so that the r0 = r1 + r0 case does not occur, but it's not obvious to me where this would happen.  If this is indeed the case, and the code here is relying upon it, this fact needs to be clearly documented.

It may be cleaner to simply reorder the operands in asm_arith rather than attempting to extend the existing logic to handle this case as well.

It also looks like the code for the case ra == rb != rr can be improved
as well.

Comment 6

[Chris Dearman]

I don't think it is possible to get the case rr!=ra && rr==rb. If rr!=ra, rb is either a copy of ra or it is allocated using findRegFor with a mask that excludes rr and ra. In both cases rr!=rb

I'll add a comment about the assumptions made and remove the redundant code for the r0=r1+r1 case.

Thanks for looking at this.

Comment 7

[William Maddox]

(In reply to comment #6)

> I'll add a comment about the assumptions made and remove the redundant code
> for the r0=r1+r1 case.

You might want to add an assertion:  NanoAssert(ra == rb || rr != rb);

> Thanks for looking at this.

No problem.  Feel free to request a review when you are happy with the patch.

Comment 8

[Chris Dearman]

Attachment: Updated patch implementing suggested fixes

Additional comments and assertion to identify the cases that are handled
Removed redundant code generated by r0=r1+r1 case

Comment 9

[Dan Smith]

Chris, did these changes make their way into the Argo MIPS branch?

Comment 10

[Chris Dearman]

(In reply to comment #9)
> Chris, did these changes make their way into the Argo MIPS branch?

I tested this patch and https://bugzilla.mozilla.org/show_bug.cgi?id=570214 in the argo tree but didn't include them in the patches I sent to you. I thought they would be accepted into tamarin-redux and be pulled from there.
I'll send what I have to you and Rick separately.

Comment 11

[Chris Dearman]

Does anything else need to be done to get this patch committed?

Comment 12

[William Maddox]

Hi, Chris.  I can go ahead and commit this if you would like.  Generally, if you don't have committer privileges, you should explicitly ask for someone to commit your patch.  I presumed you had such access and would commit it yourself following a positive review.  Sorry about the confusion.

Comment 13

[William Maddox]

Pushed to nanojit-central:

http://hg.mozilla.org/projects/nanojit-central/rev/69bf0aeb6fda

Comment 14

[Chris Dearman]

Thanks for committing these changes and the clarification. I also made an assumption that the change would magically get committed :)

Comment 15

[Nicholas Nethercote [inactive]]

http://hg.mozilla.org/tracemonkey/rev/a228aed429c3

Comment 16

[Steven Johnson]

http://hg.mozilla.org/tamarin-redux/rev/f9451aec3c27