Bug 1160911 - JIT: precise shift right derived result range for all int32 input ranges. r=sunfish
authorDouglas Crosher <dtc-moz@scieneer.com>
Sun, 10 May 2015 15:42:23 +1000
changeset 243342 a5401e748b13276db9be4e577654d67f142db5f7
parent 243341 39c35b0c2e04ccdbf8c91e9e35d84218c4c98c0b
child 243343 bc7b2813eb3b00e960100c1fab8660e6e2f5443f
push id28738
push usercbook@mozilla.com
push dateTue, 12 May 2015 14:11:31 +0000
treeherdermozilla-central@bedce1b405a3 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssunfish
bugs1160911
milestone40.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 1160911 - JIT: precise shift right derived result range for all int32 input ranges. r=sunfish
js/src/jit/RangeAnalysis.cpp
js/src/jsapi-tests/testJitRangeAnalysis.cpp
--- a/js/src/jit/RangeAnalysis.cpp
+++ b/js/src/jit/RangeAnalysis.cpp
@@ -1030,17 +1030,42 @@ Range::lsh(TempAllocator& alloc, const R
     return Range::NewInt32Range(alloc, INT32_MIN, INT32_MAX);
 }
 
 Range*
 Range::rsh(TempAllocator& alloc, const Range* lhs, const Range* rhs)
 {
     MOZ_ASSERT(lhs->isInt32());
     MOZ_ASSERT(rhs->isInt32());
-    return Range::NewInt32Range(alloc, Min(lhs->lower(), 0), Max(lhs->upper(), 0));
+
+    // Canonicalize the shift range to 0 to 31.
+    int32_t shiftLower = rhs->lower();
+    int32_t shiftUpper = rhs->upper();
+    if ((int64_t(shiftUpper) - int64_t(shiftLower)) >= 31) {
+        shiftLower = 0;
+        shiftUpper = 31;
+    } else {
+        shiftLower &= 0x1f;
+        shiftUpper &= 0x1f;
+        if (shiftLower > shiftUpper) {
+            shiftLower = 0;
+            shiftUpper = 31;
+        }
+    }
+    MOZ_ASSERT(shiftLower >= 0 && shiftUpper <= 31);
+
+    // The lhs bounds are signed, thus the minimum is either the lower bound
+    // shift by the smallest shift if negative or the lower bound shifted by the
+    // biggest shift otherwise.  And the opposite for the maximum.
+    int32_t lhsLower = lhs->lower();
+    int32_t min = lhsLower < 0 ? lhsLower >> shiftLower : lhsLower >> shiftUpper;
+    int32_t lhsUpper = lhs->upper();
+    int32_t max = lhsUpper >= 0 ? lhsUpper >> shiftLower : lhsUpper >> shiftUpper;
+
+    return Range::NewInt32Range(alloc, min, max);
 }
 
 Range*
 Range::ursh(TempAllocator& alloc, const Range* lhs, const Range* rhs)
 {
     // ursh's left operand is uint32, not int32, but for range analysis we
     // currently approximate it as int32. We assume here that the range has
     // already been adjusted accordingly by our callers.
--- a/js/src/jsapi-tests/testJitRangeAnalysis.cpp
+++ b/js/src/jsapi-tests/testJitRangeAnalysis.cpp
@@ -272,8 +272,64 @@ BEGIN_TEST(testJitRangeAnalysis_StrictCo
     if (!func.runRangeAnalysis())
         return false;
     CHECK(EquivalentRanges(thenAdd->range(),
                            Range::NewDoubleRange(func.alloc, 0.0, 0.0)));
 
     return true;
 }
 END_TEST(testJitRangeAnalysis_StrictCompareBeta)
+
+
+static void
+deriveShiftRightRange(int32_t lhsLower, int32_t lhsUpper,
+                      int32_t rhsLower, int32_t rhsUpper,
+                      int32_t* min, int32_t* max)
+{
+    // This is the reference algorithm and should be verifiable by inspection.
+    int64_t i, j;
+    *min = INT32_MAX; *max = INT32_MIN;
+    for (i = lhsLower; i <= lhsUpper; i++) {
+        for (j = rhsLower; j <= rhsUpper; j++) {
+            int32_t r = int32_t(i) >> (int32_t(j) & 0x1f);
+            if (r > *max) *max = r;
+            if (r < *min) *min = r;
+        }
+    }
+}
+
+static bool
+checkShiftRightRange(int32_t lhsLow, int32_t lhsHigh, int32_t lhsInc,
+                     int32_t rhsLow, int32_t rhsHigh, int32_t rhsInc)
+{
+    MinimalAlloc func;
+    int64_t lhsLower, lhsUpper, rhsLower, rhsUpper;
+
+    for (lhsLower = lhsLow; lhsLower <= lhsHigh; lhsLower += lhsInc) {
+        for (lhsUpper = lhsLower; lhsUpper <= lhsHigh; lhsUpper += lhsInc) {
+            Range* lhsRange = Range::NewInt32Range(func.alloc, lhsLower, lhsUpper);
+            for (rhsLower = rhsLow; rhsLower <= rhsHigh; rhsLower += rhsInc) {
+                for (rhsUpper = rhsLower; rhsUpper <= rhsHigh; rhsUpper += rhsInc) {
+                    Range* rhsRange = Range::NewInt32Range(func.alloc, rhsLower, rhsUpper);
+                    Range* result = Range::rsh(func.alloc, lhsRange, rhsRange);
+                    int32_t min, max;
+                    deriveShiftRightRange(lhsLower, lhsUpper,
+                                          rhsLower, rhsUpper,
+                                          &min, &max);
+                    if (!result->isInt32() ||
+                        result->lower() != min ||
+                        result->upper() != max) {
+                        return false;
+                    }
+                }
+            }
+        }
+    }
+    return true;
+}
+
+BEGIN_TEST(testJitRangeAnalysis_shiftRight)
+{
+    CHECK(checkShiftRightRange(-16, 15, 1,   0, 31, 1));
+    CHECK(checkShiftRightRange( -8,  7, 1, -64, 63, 1));
+    return true;
+}
+END_TEST(testJitRangeAnalysis_shiftRight)