Bug 995817 - Range Analysis: Truncate MDiv indirectly. r=sunfish, a=lsblakk
authorNicolas B. Pierron <nicolas.b.pierron@mozilla.com>
Wed, 16 Apr 2014 08:31:43 -0700
changeset 193142 1e0fac4a167bbc00c97b3649fd447949c83434e6
parent 193141 f238addfdac3ffdebd518a6d186734352572b1ce
child 193143 eaa87172af026c385d61d075cd9c3769e6f03c48
push id474
push userasasaki@mozilla.com
push dateMon, 02 Jun 2014 21:01:02 +0000
treeherdermozilla-release@967f4cf1b31c [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssunfish, lsblakk
bugs995817
milestone30.0a2
Bug 995817 - Range Analysis: Truncate MDiv indirectly. r=sunfish, a=lsblakk
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
@@ -4117,23 +4117,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)
@@ -4179,16 +4198,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
@@ -511,60 +511,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());
@@ -572,17 +571,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);
@@ -614,17 +613,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
@@ -922,17 +922,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;
@@ -940,46 +940,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);