B3 IntRange analysis should know more about shifting
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 28 Jan 2016 05:21:57 +0000 (05:21 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 28 Jan 2016 05:21:57 +0000 (05:21 +0000)
https://bugs.webkit.org/show_bug.cgi?id=153568

Reviewed by Benjamin Poulain.

This teaches the IntRange analysis that the result of a right shift is usually better than
the worst-case mask based on the shift amount. In fact, you can reach useful conclusions
from looking at the IntRange of the input. This helps because Octane/crypto does something
like:

    CheckMul((@x & $268435455) >> 14, @y >> 14, ...)

If you consider just the shifts, then this may overflow. But if you consider that @x is
first masked, then the IntRange coming out of the first shift is tight enough to prove that
the CheckMul cannot overflow.

* b3/B3ReduceStrength.cpp:
* b3/testb3.cpp:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@195728 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/b3/B3ReduceStrength.cpp
Source/JavaScriptCore/b3/testb3.cpp

index 9acd845..90c3833 100644 (file)
@@ -1,3 +1,24 @@
+2016-01-27  Filip Pizlo  <fpizlo@apple.com>
+
+        B3 IntRange analysis should know more about shifting
+        https://bugs.webkit.org/show_bug.cgi?id=153568
+
+        Reviewed by Benjamin Poulain.
+
+        This teaches the IntRange analysis that the result of a right shift is usually better than
+        the worst-case mask based on the shift amount. In fact, you can reach useful conclusions
+        from looking at the IntRange of the input. This helps because Octane/crypto does something
+        like:
+
+            CheckMul((@x & $268435455) >> 14, @y >> 14, ...)
+
+        If you consider just the shifts, then this may overflow. But if you consider that @x is
+        first masked, then the IntRange coming out of the first shift is tight enough to prove that
+        the CheckMul cannot overflow.
+
+        * b3/B3ReduceStrength.cpp:
+        * b3/testb3.cpp:
+
 2016-01-27  Benjamin Poulain  <bpoulain@apple.com>
 
         [JSC] adjustFrameAndStackInOSRExitCompilerThunk() can trash values in FTL
index 119b756..ed629e4 100644 (file)
@@ -88,6 +88,8 @@ namespace {
 
 bool verbose = false;
 
+// FIXME: This IntRange stuff should be refactored into a general constant propagator. It's weird
+// that it's just sitting here in this file.
 class IntRange {
 public:
     IntRange()
@@ -162,25 +164,6 @@ public:
         }
     }
 
-    template<typename T>
-    static IntRange rangeForSShr(int32_t shiftAmount)
-    {
-        return IntRange(top<T>().min() >> shiftAmount, top<T>().max() >> shiftAmount);
-    }
-
-    static IntRange rangeForSShr(int32_t shiftAmount, Type type)
-    {
-        switch (type) {
-        case Int32:
-            return rangeForSShr<int32_t>(shiftAmount);
-        case Int64:
-            return rangeForSShr<int64_t>(shiftAmount);
-        default:
-            RELEASE_ASSERT_NOT_REACHED();
-            return IntRange();
-        }
-    }
-
     int64_t min() const { return m_min; }
     int64_t max() const { return m_max; }
 
@@ -255,8 +238,8 @@ public:
     template<typename T>
     IntRange shl(int32_t shiftAmount)
     {
-        T newMin = static_cast<T>(m_min) << shiftAmount;
-        T newMax = static_cast<T>(m_max) << shiftAmount;
+        T newMin = static_cast<T>(m_min) << static_cast<T>(shiftAmount);
+        T newMax = static_cast<T>(m_max) << static_cast<T>(shiftAmount);
 
         if ((newMin >> shiftAmount) != static_cast<T>(m_min))
             newMin = std::numeric_limits<T>::min();
@@ -280,6 +263,61 @@ public:
     }
 
     template<typename T>
+    IntRange sShr(int32_t shiftAmount)
+    {
+        T newMin = static_cast<T>(m_min) >> static_cast<T>(shiftAmount);
+        T newMax = static_cast<T>(m_max) >> static_cast<T>(shiftAmount);
+
+        return IntRange(newMin, newMax);
+    }
+
+    IntRange sShr(int32_t shiftAmount, Type type)
+    {
+        switch (type) {
+        case Int32:
+            return sShr<int32_t>(shiftAmount);
+        case Int64:
+            return sShr<int64_t>(shiftAmount);
+        default:
+            RELEASE_ASSERT_NOT_REACHED();
+            return IntRange();
+        }
+    }
+
+    template<typename T>
+    IntRange zShr(int32_t shiftAmount)
+    {
+        // This is an awkward corner case for all of the other logic.
+        if (!shiftAmount)
+            return *this;
+
+        // If the input range may be negative, then all we can say about the output range is that it
+        // will be masked. That's because -1 right shifted just produces that mask.
+        if (m_min < 0)
+            return rangeForZShr<T>(shiftAmount);
+
+        // If the input range is non-negative, then this just brings the range closer to zero.
+        typedef typename std::make_unsigned<T>::type UnsignedT;
+        UnsignedT newMin = static_cast<UnsignedT>(m_min) >> static_cast<UnsignedT>(shiftAmount);
+        UnsignedT newMax = static_cast<UnsignedT>(m_max) >> static_cast<UnsignedT>(shiftAmount);
+        
+        return IntRange(newMin, newMax);
+    }
+
+    IntRange zShr(int32_t shiftAmount, Type type)
+    {
+        switch (type) {
+        case Int32:
+            return zShr<int32_t>(shiftAmount);
+        case Int64:
+            return zShr<int64_t>(shiftAmount);
+        default:
+            RELEASE_ASSERT_NOT_REACHED();
+            return IntRange();
+        }
+    }
+
+    template<typename T>
     IntRange add(const IntRange& other)
     {
         if (couldOverflowAdd<T>(other))
@@ -1955,19 +1993,24 @@ private:
             break;
 
         case SShr:
-            if (value->child(1)->hasInt32())
-                return IntRange::rangeForSShr(value->child(1)->asInt32(), value->type());
+            if (value->child(1)->hasInt32()) {
+                return rangeFor(value->child(0), timeToLive - 1).sShr(
+                    value->child(1)->asInt32(), value->type());
+            }
             break;
 
         case ZShr:
-            if (value->child(1)->hasInt32())
-                return IntRange::rangeForZShr(value->child(1)->asInt32(), value->type());
+            if (value->child(1)->hasInt32()) {
+                return rangeFor(value->child(0), timeToLive - 1).zShr(
+                    value->child(1)->asInt32(), value->type());
+            }
             break;
 
         case Shl:
-            if (value->child(1)->hasInt32())
+            if (value->child(1)->hasInt32()) {
                 return rangeFor(value->child(0), timeToLive - 1).shl(
                     value->child(1)->asInt32(), value->type());
+            }
             break;
 
         case Add:
index 1685f4a..b264e4f 100644 (file)
@@ -7908,6 +7908,45 @@ void testCheckMulFoldFail(int a, int b)
     CHECK(invoke<int>(*code) == 42);
 }
 
+void testCheckMul64SShr()
+{
+    Procedure proc;
+    BasicBlock* root = proc.addBlock();
+    Value* arg1 = root->appendNew<Value>(
+        proc, SShr, Origin(),
+        root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0),
+        root->appendNew<Const32Value>(proc, Origin(), 1));
+    Value* arg2 = root->appendNew<Value>(
+        proc, SShr, Origin(),
+        root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1),
+        root->appendNew<Const32Value>(proc, Origin(), 1));
+    CheckValue* checkMul = root->appendNew<CheckValue>(proc, CheckMul, Origin(), arg1, arg2);
+    checkMul->append(arg1);
+    checkMul->append(arg2);
+    checkMul->setGenerator(
+        [&] (CCallHelpers& jit, const StackmapGenerationParams& params) {
+            AllowMacroScratchRegisterUsage allowScratch(jit);
+            CHECK(params.size() == 2);
+            CHECK(params[0].isGPR());
+            CHECK(params[1].isGPR());
+            jit.convertInt64ToDouble(params[0].gpr(), FPRInfo::fpRegT0);
+            jit.convertInt64ToDouble(params[1].gpr(), FPRInfo::fpRegT1);
+            jit.mulDouble(FPRInfo::fpRegT1, FPRInfo::fpRegT0);
+            jit.emitFunctionEpilogue();
+            jit.ret();
+        });
+    root->appendNew<ControlValue>(
+        proc, Return, Origin(),
+        root->appendNew<Value>(proc, IToD, Origin(), checkMul));
+
+    auto code = compile(proc);
+
+    CHECK(invoke<double>(*code, 0ll, 42ll) == 0.0);
+    CHECK(invoke<double>(*code, 1ll, 42ll) == 0.0);
+    CHECK(invoke<double>(*code, 42ll, 42ll) == (42.0 / 2.0) * (42.0 / 2.0));
+    CHECK(invoke<double>(*code, 10000000000ll, 10000000000ll) == 25000000000000000000.0);
+}
+
 template<typename LeftFunctor, typename RightFunctor, typename InputType>
 void genericTestCompare(
     B3::Opcode opcode, const LeftFunctor& leftFunctor, const RightFunctor& rightFunctor,
@@ -11340,6 +11379,8 @@ void run(const char* filter)
     RUN(testSShrShl64(42000000000, 8, 8));
     RUN(testSShrShl64(-42000000000, 8, 8));
 
+    RUN(testCheckMul64SShr());
+
     if (tasks.isEmpty())
         usage();