Bug 995817 - Range Analysis: Truncate MDiv indirectly. r=sunfish
authorNicolas B. Pierron <nicolas.b.pierron@mozilla.com>
Wed, 16 Apr 2014 08:31:43 -0700
changeset 197323 35e57f348ddf33b3197266d05b1e4eacaae9e7cf
parent 197322 bfb975c73a502373bfc1da2916b633bdc89a38ea
child 197324 311a1e912f6b5f5ea0e430f147e1b9b70bd66e8c
push id3624
push userasasaki@mozilla.com
push dateMon, 09 Jun 2014 21:49:01 +0000
treeherdermozilla-beta@b1a5da15899a [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssunfish
bugs995817
milestone31.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 995817 - Range Analysis: Truncate MDiv indirectly. r=sunfish
js/src/jit-test/tests/ion/bug995817.js
js/src/jit/MIR.h
js/src/jit/RangeAnalysis.cpp
js/src/jit/arm/CodeGenerator-arm.cpp
js/src/jit/shared/CodeGenerator-x86-shared.cpp
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/ion/bug995817.js
@@ -0,0 +1,17 @@
+setJitCompilerOption('baseline.usecount.trigger', 1);
+let r;
+(function() {
+     function f() {
+         return (1 + -1 / 0) << null;
+     }
+     assertEq(f(), 0);
+     assertEq(f(), 0);
+
+     function g(x,y) {
+         var a = x|0;
+         var b = y|0;
+         return (a / b + a / b) | 0;
+     }
+     assertEq(g(3,4), 1);
+     assertEq(g(3,4), 1);
+})();
--- a/js/src/jit/MIR.h
+++ b/js/src/jit/MIR.h
@@ -4066,23 +4066,42 @@ class MMul : public MBinaryArithInstruct
 class MDiv : public MBinaryArithInstruction
 {
     bool canBeNegativeZero_;
     bool canBeNegativeOverflow_;
     bool canBeDivideByZero_;
     bool canBeNegativeDividend_;
     bool unsigned_;
 
+    // A Division can be truncated in 4 differents ways:
+    //   1. Ignore Infinities (x / 0 --> 0).
+    //   2. Ignore overflow (INT_MIN / -1 == (INT_MAX + 1) --> INT_MIN)
+    //   3. Ignore negative zeros. (-0 --> 0)
+    //   4. Ignore remainder. (3 / 4 --> 0)
+    //
+    // isTruncatedIndirectly is used to represent that we are interested in the
+    // truncated result, but only if they it can safely flow in operations which
+    // are computed modulo 2^32, such as (2) and (3).
+    //
+    // A division can return either Infinities (1) or a remainder (4) when both
+    // operands are integers. Infinities are not safe, as they would have
+    // absorbed other math operations. Remainders are not safe, as multiple can
+    // add up to integers. This implies that we need to distinguish between a
+    // division which is truncated directly (isTruncated) or which flow into
+    // truncated operations (isTruncatedIndirectly).
+    bool isTruncatedIndirectly_;
+
     MDiv(MDefinition *left, MDefinition *right, MIRType type)
       : MBinaryArithInstruction(left, right),
         canBeNegativeZero_(true),
         canBeNegativeOverflow_(true),
         canBeDivideByZero_(true),
         canBeNegativeDividend_(true),
-        unsigned_(false)
+        unsigned_(false),
+        isTruncatedIndirectly_(false)
     {
         if (type != MIRType_Value)
             specialization_ = type;
         setResultType(type);
     }
 
   public:
     INSTRUCTION_HEADER(Div)
@@ -4128,16 +4147,36 @@ class MDiv : public MBinaryArithInstruct
     bool canBeNegativeDividend() const {
         return canBeNegativeDividend_;
     }
 
     bool isUnsigned() const {
         return unsigned_;
     }
 
+    bool isTruncatedIndirectly() const {
+        return isTruncatedIndirectly_;
+    }
+    void setTruncatedIndirectly(bool truncate) {
+        isTruncatedIndirectly_ = truncate;
+    }
+
+    bool canTruncateInfinities() const {
+        return isTruncated();
+    }
+    bool canTruncateRemainder() const {
+        return isTruncated();
+    }
+    bool canTruncateOverflow() const {
+        return isTruncated() || isTruncatedIndirectly();
+    }
+    bool canTruncateNegativeZero() const {
+        return isTruncated() || isTruncatedIndirectly();
+    }
+
     bool isFloat32Commutative() const { return true; }
 
     void computeRange(TempAllocator &alloc);
     bool fallible() const;
     bool truncate();
     void collectRangeInfoPreTrunc();
 };
 
--- a/js/src/jit/RangeAnalysis.cpp
+++ b/js/src/jit/RangeAnalysis.cpp
@@ -2212,17 +2212,38 @@ MMul::truncate()
 
     return false;
 }
 
 bool
 MDiv::truncate()
 {
     // Remember analysis, needed to remove negative zero checks.
-    setTruncated(true);
+    setTruncatedIndirectly(true);
+
+    // Check if this division only flows in bitwise instructions.
+    if (!isTruncated()) {
+        bool allUsesExplictlyTruncate = true;
+        for (MUseDefIterator use(this); allUsesExplictlyTruncate && use; use++) {
+            switch (use.def()->op()) {
+              case MDefinition::Op_BitAnd:
+              case MDefinition::Op_BitOr:
+              case MDefinition::Op_BitXor:
+              case MDefinition::Op_Lsh:
+              case MDefinition::Op_Rsh:
+              case MDefinition::Op_Ursh:
+                break;
+              default:
+                allUsesExplictlyTruncate = false;
+            }
+        }
+
+        if (allUsesExplictlyTruncate)
+            setTruncated(true);
+    }
 
     // Divisions where the lhs and rhs are unsigned and the result is
     // truncated can be lowered more efficiently.
     if (specialization() == MIRType_Int32 && tryUseUnsignedOperands()) {
         unsigned_ = true;
         return true;
     }
 
--- a/js/src/jit/arm/CodeGenerator-arm.cpp
+++ b/js/src/jit/arm/CodeGenerator-arm.cpp
@@ -519,60 +519,59 @@ bool
 CodeGeneratorARM::divICommon(MDiv *mir, Register lhs, Register rhs, Register output,
                              LSnapshot *snapshot, Label &done)
 {
     if (mir->canBeNegativeOverflow()) {
         // Handle INT32_MIN / -1;
         // The integer division will give INT32_MIN, but we want -(double)INT32_MIN.
         masm.ma_cmp(lhs, Imm32(INT32_MIN)); // sets EQ if lhs == INT32_MIN
         masm.ma_cmp(rhs, Imm32(-1), Assembler::Equal); // if EQ (LHS == INT32_MIN), sets EQ if rhs == -1
-        if (mir->isTruncated()) {
+        if (mir->canTruncateOverflow()) {
             // (-INT32_MIN)|0 = INT32_MIN
             Label skip;
             masm.ma_b(&skip, Assembler::NotEqual);
             masm.ma_mov(Imm32(INT32_MIN), output);
             masm.ma_b(&done);
             masm.bind(&skip);
         } else {
             JS_ASSERT(mir->fallible());
             if (!bailoutIf(Assembler::Equal, snapshot))
                 return false;
         }
     }
 
-    // 0/X (with X < 0) is bad because both of these values *should* be doubles, and
-    // the result should be -0.0, which cannot be represented in integers.
-    // X/0 is bad because it will give garbage (or abort), when it should give
-    // either \infty, -\infty or NAN.
-
-    // Prevent 0 / X (with X < 0) and X / 0
-    // testing X / Y.  Compare Y with 0.
-    // There are three cases: (Y < 0), (Y == 0) and (Y > 0)
-    // If (Y < 0), then we compare X with 0, and bail if X == 0
-    // If (Y == 0), then we simply want to bail.  Since this does not set
-    // the flags necessary for LT to trigger, we don't test X, and take the
-    // bailout because the EQ flag is set.
-    // if (Y > 0), we don't set EQ, and we don't trigger LT, so we don't take the bailout.
-    if (mir->canBeDivideByZero() || mir->canBeNegativeZero()) {
+    // Handle divide by zero.
+    if (mir->canBeDivideByZero()) {
         masm.ma_cmp(rhs, Imm32(0));
-        masm.ma_cmp(lhs, Imm32(0), Assembler::LessThan);
-        if (mir->isTruncated()) {
-            // Infinity|0 == 0 and -0|0 == 0
+        if (mir->canTruncateInfinities()) {
+            // Infinity|0 == 0
             Label skip;
             masm.ma_b(&skip, Assembler::NotEqual);
             masm.ma_mov(Imm32(0), output);
             masm.ma_b(&done);
             masm.bind(&skip);
         } else {
             JS_ASSERT(mir->fallible());
             if (!bailoutIf(Assembler::Equal, snapshot))
                 return false;
         }
     }
 
+    // Handle negative 0.
+    if (!mir->canTruncateNegativeZero() && mir->canBeNegativeZero()) {
+        Label nonzero;
+        masm.ma_cmp(lhs, Imm32(0));
+        masm.ma_b(&nonzero, Assembler::NotEqual);
+        masm.ma_cmp(rhs, Imm32(0));
+        JS_ASSERT(mir->fallible());
+        if (!bailoutIf(Assembler::LessThan, snapshot))
+            return false;
+        masm.bind(&nonzero);
+    }
+
     return true;
 }
 
 bool
 CodeGeneratorARM::visitDivI(LDivI *ins)
 {
     // Extract the registers from this instruction
     Register lhs = ToRegister(ins->lhs());
@@ -580,17 +579,17 @@ CodeGeneratorARM::visitDivI(LDivI *ins)
     Register temp = ToRegister(ins->getTemp(0));
     Register output = ToRegister(ins->output());
     MDiv *mir = ins->mir();
 
     Label done;
     if (!divICommon(mir, lhs, rhs, output, ins->snapshot(), done))
         return false;
 
-    if (mir->isTruncated()) {
+    if (mir->canTruncateRemainder()) {
         masm.ma_sdiv(lhs, rhs, output);
     } else {
         masm.ma_sdiv(lhs, rhs, ScratchRegister);
         masm.ma_mul(ScratchRegister, rhs, temp);
         masm.ma_cmp(lhs, temp);
         if (!bailoutIf(Assembler::NotEqual, ins->snapshot()))
             return false;
         masm.ma_mov(ScratchRegister, output);
@@ -622,17 +621,17 @@ CodeGeneratorARM::visitSoftDivI(LSoftDiv
     masm.setupAlignedABICall(2);
     masm.passABIArg(lhs);
     masm.passABIArg(rhs);
     if (gen->compilingAsmJS())
         masm.callWithABI(AsmJSImm_aeabi_idivmod);
     else
         masm.callWithABI(JS_FUNC_TO_DATA_PTR(void *, __aeabi_idivmod));
     // idivmod returns the quotient in r0, and the remainder in r1.
-    if (!mir->isTruncated()) {
+    if (!mir->canTruncateRemainder()) {
         JS_ASSERT(mir->fallible());
         masm.ma_cmp(r1, Imm32(0));
         if (!bailoutIf(Assembler::NonZero, ins->snapshot()))
             return false;
     }
 
     masm.bind(&done);
 
--- a/js/src/jit/shared/CodeGenerator-x86-shared.cpp
+++ b/js/src/jit/shared/CodeGenerator-x86-shared.cpp
@@ -928,17 +928,17 @@ CodeGeneratorX86Shared::visitDivI(LDivI 
     // Put the lhs in eax, for either the negative overflow case or the regular
     // divide case.
     if (lhs != eax)
         masm.mov(lhs, eax);
 
     // Handle divide by zero.
     if (mir->canBeDivideByZero()) {
         masm.testl(rhs, rhs);
-        if (mir->isTruncated()) {
+        if (mir->canTruncateInfinities()) {
             // Truncated division by zero is zero (Infinity|0 == 0)
             if (!ool)
                 ool = new(alloc()) ReturnZero(output);
             masm.j(Assembler::Zero, ool->entry());
         } else {
             JS_ASSERT(mir->fallible());
             if (!bailoutIf(Assembler::Zero, ins->snapshot()))
                 return false;
@@ -946,46 +946,46 @@ CodeGeneratorX86Shared::visitDivI(LDivI 
     }
 
     // Handle an integer overflow exception from -2147483648 / -1.
     if (mir->canBeNegativeOverflow()) {
         Label notmin;
         masm.cmpl(lhs, Imm32(INT32_MIN));
         masm.j(Assembler::NotEqual, &notmin);
         masm.cmpl(rhs, Imm32(-1));
-        if (mir->isTruncated()) {
+        if (mir->canTruncateOverflow()) {
             // (-INT32_MIN)|0 == INT32_MIN and INT32_MIN is already in the
             // output register (lhs == eax).
             masm.j(Assembler::Equal, &done);
         } else {
             JS_ASSERT(mir->fallible());
             if (!bailoutIf(Assembler::Equal, ins->snapshot()))
                 return false;
         }
         masm.bind(&notmin);
     }
 
     // Handle negative 0.
-    if (!mir->isTruncated() && mir->canBeNegativeZero()) {
+    if (!mir->canTruncateNegativeZero() && mir->canBeNegativeZero()) {
         Label nonzero;
         masm.testl(lhs, lhs);
         masm.j(Assembler::NonZero, &nonzero);
         masm.cmpl(rhs, Imm32(0));
         if (!bailoutIf(Assembler::LessThan, ins->snapshot()))
             return false;
         masm.bind(&nonzero);
     }
 
     // Sign extend the lhs into edx to make (edx:eax), since idiv is 64-bit.
     if (lhs != eax)
         masm.mov(lhs, eax);
     masm.cdq();
     masm.idiv(rhs);
 
-    if (!mir->isTruncated()) {
+    if (!mir->canTruncateRemainder()) {
         // If the remainder is > 0, bailout since this must be a double.
         masm.testl(remainder, remainder);
         if (!bailoutIf(Assembler::NonZero, ins->snapshot()))
             return false;
     }
 
     masm.bind(&done);