Bug 869473 - Optimize DivI with a power of two divisor when the numerator is not negative. r=sunfish
authorDouglas Crosher <dtc-moz@scieneer.com>
Thu, 05 Dec 2013 07:34:29 +1100
changeset 174486 2eb5f81c77eccbae042fce77617629108ef4b5a5
parent 174485 8e1d2c3938492518fe59d70de5a035f4ed83213b
child 174487 48ee35b9297379163c103b220ca586c6263bd66d
push id445
push userffxbld
push dateMon, 10 Mar 2014 22:05:19 +0000
treeherdermozilla-release@dc38b741b04e [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssunfish
bugs869473
milestone28.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 869473 - Optimize DivI with a power of two divisor when the numerator is not negative. r=sunfish
js/src/jit-test/tests/asm.js/testExpressions.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
js/src/jit/shared/LIR-x86-shared.h
js/src/jit/shared/Lowering-x86-shared.cpp
--- a/js/src/jit-test/tests/asm.js/testExpressions.js
+++ b/js/src/jit-test/tests/asm.js/testExpressions.js
@@ -326,8 +326,35 @@ var f = asmLink(asmCompile(USE_ASM + "fu
 for (let i = 0; i < 31; i++) {
     assertEq(f(Math.pow(2,i)), (Math.pow(2,i) * 2)|0);
     assertEq(f(Math.pow(2,i) - 1), ((Math.pow(2,i) - 1) * 2)|0);
     assertEq(f(-Math.pow(2,i)), (-Math.pow(2,i) * 2)|0);
     assertEq(f(-Math.pow(2,i) - 1), ((-Math.pow(2,i) - 1) * 2)|0);
 }
 assertEq(f(INT32_MIN), (INT32_MIN * 2)|0);
 assertEq(f(INT32_MAX), (INT32_MAX * 2)|0);
+
+// Signed integer division by a power of two - with a non-negative numerator!
+var f = asmLink(asmCompile(USE_ASM + "function f(i) { i=i|0; i=(i&2147483647)|0; return ((i|0)/1)|0; } return f;"));
+for (let i = 0; i < 31; i++) {
+    assertEq(f(Math.pow(2,i)), Math.pow(2,i));
+    assertEq(f(Math.pow(2,i+1)-1), Math.pow(2,i+1)-1);
+}
+var f = asmLink(asmCompile(USE_ASM + "function f(i) { i=i|0; i=(i&2147483647)|0; return ((i|0)/2)|0; } return f;"));
+for (let i = 0; i < 31; i++) {
+    assertEq(f(Math.pow(2,i)), (Math.pow(2,i)/2)|0);
+    assertEq(f(Math.pow(2,i+1)-1), ((Math.pow(2,i+1)-1)/2)|0);
+}
+var f = asmLink(asmCompile(USE_ASM + "function f(i) { i=i|0; i=(i&2147483647)|0; return ((i|0)/4)|0; } return f;"));
+for (let i = 0; i < 31; i++) {
+    assertEq(f(Math.pow(2,i)), (Math.pow(2,i)/4)|0);
+    assertEq(f(Math.pow(2,i+1)-1), ((Math.pow(2,i+1)-1)/4)|0);
+}
+var f = asmLink(asmCompile(USE_ASM + "function f(i) { i=i|0; i=(i&2147483647)|0; return ((i|0)/1073741824)|0; } return f;"));
+for (let i = 0; i < 31; i++) {
+    assertEq(f(Math.pow(2,i)), (Math.pow(2,i)/Math.pow(2,30))|0);
+    assertEq(f(Math.pow(2,i+1)-1), ((Math.pow(2,i+1)-1)/Math.pow(2,30))|0);
+}
+var f = asmLink(asmCompile(USE_ASM + "function f(i) { i=i|0; i=(i&2147483647)|0; return ((((i|0)/1)|0)+i)|0; } return f;"));
+for (let i = 0; i < 31; i++) {
+    assertEq(f(Math.pow(2,i)), (Math.pow(2,i) * 2)|0);
+    assertEq(f(Math.pow(2,i+1) - 1), ((Math.pow(2,i+1) - 1) * 2)|0);
+}
--- a/js/src/jit/MIR.h
+++ b/js/src/jit/MIR.h
@@ -4090,23 +4090,25 @@ class MMul : public MBinaryArithInstruct
     Mode mode() { return mode_; }
 };
 
 class MDiv : public MBinaryArithInstruction
 {
     bool canBeNegativeZero_;
     bool canBeNegativeOverflow_;
     bool canBeDivideByZero_;
+    bool canBeNegativeDividend_;
     bool unsigned_;
 
     MDiv(MDefinition *left, MDefinition *right, MIRType type)
       : MBinaryArithInstruction(left, right),
         canBeNegativeZero_(true),
         canBeNegativeOverflow_(true),
         canBeDivideByZero_(true),
+        canBeNegativeDividend_(true),
         unsigned_(false)
     {
         if (type != MIRType_Value)
             specialization_ = type;
         setResultType(type);
     }
 
   public:
@@ -4145,25 +4147,30 @@ class MDiv : public MBinaryArithInstruct
     bool canBeNegativeOverflow() const {
         return canBeNegativeOverflow_;
     }
 
     bool canBeDivideByZero() const {
         return canBeDivideByZero_;
     }
 
+    bool canBeNegativeDividend() const {
+        return canBeNegativeDividend_;
+    }
+
     bool isUnsigned() const {
         return unsigned_;
     }
 
     bool isFloat32Commutative() const { return true; }
 
     void computeRange();
     bool fallible() const;
     bool truncate();
+    void collectRangeInfoPreTrunc();
 };
 
 class MMod : public MBinaryArithInstruction
 {
     bool unsigned_;
     bool canBeNegativeDividend_;
 
     MMod(MDefinition *left, MDefinition *right, MIRType type)
--- a/js/src/jit/RangeAnalysis.cpp
+++ b/js/src/jit/RangeAnalysis.cpp
@@ -2492,16 +2492,24 @@ void
 MLoadElementHole::collectRangeInfoPreTrunc()
 {
     Range indexRange(index());
     if (indexRange.isFiniteNonNegative())
         needsNegativeIntCheck_ = false;
 }
 
 void
+MDiv::collectRangeInfoPreTrunc()
+{
+    Range lhsRange(lhs());
+    if (lhsRange.isFiniteNonNegative())
+        canBeNegativeDividend_ = false;
+}
+
+void
 MMod::collectRangeInfoPreTrunc()
 {
     Range lhsRange(lhs());
     if (lhsRange.isFiniteNonNegative())
         canBeNegativeDividend_ = false;
 }
 
 void
--- a/js/src/jit/arm/CodeGenerator-arm.cpp
+++ b/js/src/jit/arm/CodeGenerator-arm.cpp
@@ -649,28 +649,33 @@ CodeGeneratorARM::visitSoftDivI(LSoftDiv
 bool
 CodeGeneratorARM::visitDivPowTwoI(LDivPowTwoI *ins)
 {
     Register lhs = ToRegister(ins->numerator());
     Register output = ToRegister(ins->output());
     int32_t shift = ins->shift();
 
     if (shift != 0) {
-        if (!ins->mir()->isTruncated()) {
+        MDiv *mir = ins->mir();
+        if (!mir->isTruncated()) {
             // If the remainder is != 0, bailout since this must be a double.
             masm.as_mov(ScratchRegister, lsl(lhs, 32 - shift), SetCond);
             if (!bailoutIf(Assembler::NonZero, ins->snapshot()))
                 return false;
         }
 
+        if (!mir->canBeNegativeDividend()) {
+            // Numerator is unsigned, so needs no adjusting. Do the shift.
+            masm.as_mov(output, asr(lhs, shift));
+            return true;
+        }
+
         // 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.
-        // Note that we wouldn't need to do this adjustment if we could use
-        // Range Analysis to find cases when the value is never negative.
         if (shift > 1) {
             masm.as_mov(ScratchRegister, asr(lhs, 31));
             masm.as_add(ScratchRegister, lhs, lsr(ScratchRegister, 32 - shift));
         } else
             masm.as_add(ScratchRegister, lhs, lsr(lhs, 32 - shift));
 
         // Do the shift.
         masm.as_mov(output, asr(ScratchRegister, shift));
--- a/js/src/jit/shared/CodeGenerator-x86-shared.cpp
+++ b/js/src/jit/shared/CodeGenerator-x86-shared.cpp
@@ -848,38 +848,43 @@ CodeGeneratorX86Shared::visitMulNegative
     masm.jmp(ool->rejoin());
     return true;
 }
 
 bool
 CodeGeneratorX86Shared::visitDivPowTwoI(LDivPowTwoI *ins)
 {
     Register lhs = ToRegister(ins->numerator());
-    Register lhsCopy = ToRegister(ins->numeratorCopy());
     mozilla::DebugOnly<Register> output = ToRegister(ins->output());
     int32_t shift = ins->shift();
 
     // We use defineReuseInput so these should always be the same, which is
     // convenient since all of our instructions here are two-address.
     JS_ASSERT(lhs == output);
 
     if (shift != 0) {
-        if (!ins->mir()->isTruncated()) {
+        MDiv *mir = ins->mir();
+        if (!mir->isTruncated()) {
             // If the remainder is != 0, bailout since this must be a double.
             masm.testl(lhs, Imm32(UINT32_MAX >> (32 - shift)));
             if (!bailoutIf(Assembler::NonZero, ins->snapshot()))
                 return false;
         }
 
+        if (!mir->canBeNegativeDividend()) {
+            // Numerator is unsigned, so needs no adjusting. Do the shift.
+            masm.sarl(Imm32(shift), lhs);
+            return true;
+        }
+
         // 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.
-        // Note that we wouldn't need to do this adjustment if we could use
-        // Range Analysis to find cases when the value is never negative. We
-        // wouldn't even need the lhsCopy either in that case.
+        Register lhsCopy = ToRegister(ins->numeratorCopy());
+        JS_ASSERT(lhsCopy != lhs);
         if (shift > 1)
             masm.sarl(Imm32(31), lhs);
         masm.shrl(Imm32(32 - shift), lhs);
         masm.addl(lhsCopy, lhs);
 
         // Do the shift.
         masm.sarl(Imm32(shift), lhs);
     }
--- a/js/src/jit/shared/LIR-x86-shared.h
+++ b/js/src/jit/shared/LIR-x86-shared.h
@@ -53,16 +53,22 @@ class LDivPowTwoI : public LBinaryMath<0
 
     LDivPowTwoI(const LAllocation &lhs, const LAllocation &lhsCopy, int32_t shift)
       : shift_(shift)
     {
         setOperand(0, lhs);
         setOperand(1, lhsCopy);
     }
 
+    LDivPowTwoI(const LAllocation &lhs, int32_t shift)
+      : shift_(shift)
+    {
+        setOperand(0, lhs);
+    }
+
     const LAllocation *numerator() {
         return getOperand(0);
     }
     const LAllocation *numeratorCopy() {
         return getOperand(1);
     }
     int32_t shift() const {
         return shift_;
--- a/js/src/jit/shared/Lowering-x86-shared.cpp
+++ b/js/src/jit/shared/Lowering-x86-shared.cpp
@@ -139,17 +139,26 @@ LIRGeneratorX86Shared::lowerDivI(MDiv *d
 
         // Check for division by a positive power of two, which is an easy and
         // important case to optimize. Note that other optimizations are also
         // possible; division by negative powers of two can be optimized in a
         // similar manner as positive powers of two, and division by other
         // constants can be optimized by a reciprocal multiplication technique.
         int32_t shift = FloorLog2(rhs);
         if (rhs > 0 && 1 << shift == rhs) {
-            LDivPowTwoI *lir = new LDivPowTwoI(useRegisterAtStart(div->lhs()), useRegister(div->lhs()), shift);
+            LAllocation lhs = useRegisterAtStart(div->lhs());
+            LDivPowTwoI *lir;
+            if (!div->canBeNegativeDividend()) {
+                // Numerator is unsigned, so does not need adjusting.
+                lir = new LDivPowTwoI(lhs, shift);
+            } else {
+                // Numerator is signed, and needs adjusting, and an extra
+                // lhs copy register is needed.
+                lir = new LDivPowTwoI(lhs, useRegister(div->lhs()), shift);
+            }
             if (div->fallible() && !assignSnapshot(lir, Bailout_BaselineInfo))
                 return false;
             return defineReuseInput(lir, div, 0);
         }
     }
 
     // Optimize x/x. This is quaint, but it also protects the LDivI code below.
     // Since LDivI requires lhs to be in %eax, and since the register allocator