[B3] JetStream/quicksort.c fails/hangs on Linux with GCC
authorutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 30 Jan 2016 20:57:09 +0000 (20:57 +0000)
committerutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 30 Jan 2016 20:57:09 +0000 (20:57 +0000)
https://bugs.webkit.org/show_bug.cgi?id=153647

Reviewed by Filip Pizlo.

In B3ComputeDivisionMagic, we accidentally perform sub, add operation onto signed integer. (In this case, int32_t)
But integer overflow is undefined behavior in C![1][2]
As a result, in GCC 4.9 release build, computeDivisionMagic(2) returns unexpected value.
`divisor = 2`
`d = 2`
`signedMin = INT32_MIN = -2147483647 (-0x7fffffff)`
`t = signedMin`
`anc = t - 1 - (t % ad)` Oops, we performed overflow operation!

So, `anc` value becomes undefined.
In this patch, we first cast all the operated values to unsigned one.
Reading the code, there are no operations that depends on signedness. (For example, we used aboveEqual like unsigned operations for comparison.)

[1]: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html
[2]: http://dl.acm.org/citation.cfm?id=2522728

* b3/B3ComputeDivisionMagic.h:
(JSC::B3::computeDivisionMagic):
* b3/testb3.cpp:
(JSC::B3::testComputeDivisionMagic):
(JSC::B3::run):

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/b3/B3ComputeDivisionMagic.h
Source/JavaScriptCore/b3/testb3.cpp

index f75d725..fb55f23 100644 (file)
@@ -1,3 +1,32 @@
+2016-01-30  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        [B3] JetStream/quicksort.c fails/hangs on Linux with GCC
+        https://bugs.webkit.org/show_bug.cgi?id=153647
+
+        Reviewed by Filip Pizlo.
+
+        In B3ComputeDivisionMagic, we accidentally perform sub, add operation onto signed integer. (In this case, int32_t)
+        But integer overflow is undefined behavior in C![1][2]
+        As a result, in GCC 4.9 release build, computeDivisionMagic(2) returns unexpected value.
+        `divisor = 2`
+        `d = 2`
+        `signedMin = INT32_MIN = -2147483647 (-0x7fffffff)`
+        `t = signedMin`
+        `anc = t - 1 - (t % ad)` Oops, we performed overflow operation!
+
+        So, `anc` value becomes undefined.
+        In this patch, we first cast all the operated values to unsigned one.
+        Reading the code, there are no operations that depends on signedness. (For example, we used aboveEqual like unsigned operations for comparison.)
+
+        [1]: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html
+        [2]: http://dl.acm.org/citation.cfm?id=2522728
+
+        * b3/B3ComputeDivisionMagic.h:
+        (JSC::B3::computeDivisionMagic):
+        * b3/testb3.cpp:
+        (JSC::B3::testComputeDivisionMagic):
+        (JSC::B3::run):
+
 2016-01-30  Andreas Kling  <akling@apple.com>
 
         Shrink Heap::m_executables after cleaning it.
index 7647d97..cdaaacf 100644 (file)
@@ -89,64 +89,46 @@ struct DivisionMagic {
 template<typename T>
 DivisionMagic<T> computeDivisionMagic(T divisor)
 {
-    T d = divisor;
+    typedef typename std::make_unsigned<T>::type UnsignedT;
+    UnsignedT d = divisor;
     unsigned p;
-    T ad, anc, delta, q1, r1, q2, r2, t;
-    T signedMin = std::numeric_limits<T>::min();
+    UnsignedT ad, anc, delta, q1, r1, q2, r2, t;
+    UnsignedT signedMin = static_cast<UnsignedT>(std::numeric_limits<T>::min());
     DivisionMagic<T> mag;
     unsigned bitWidth = sizeof(divisor) * 8;
 
     // This code doesn't like to think of signedness as a type. Instead it likes to think that
     // operations have signedness. This is how we generally do it in B3 as well. For this reason,
-    // this provides helpers for unsigned operations on the signed type (T).
-    
-    auto zshr = [&] (T value, int amount) -> T {
-        return static_cast<typename std::make_unsigned<T>::type>(value) >> amount;
-    };
+    // we cast all the operated values once to unsigned. And later, we convert it to signed.
+    // Only `divisor` have signedness here.
 
-    auto udiv = [&] (T left, T right) -> T {
-        return static_cast<T>(static_cast<typename std::make_unsigned<T>::type>(left) / static_cast<typename std::make_unsigned<T>::type>(right));
-    };
-
-    auto urem = [&] (T left, T right) -> T {
-        return static_cast<T>(static_cast<typename std::make_unsigned<T>::type>(left) % static_cast<typename std::make_unsigned<T>::type>(right));
-    };
-
-    auto aboveEqual = [&] (T left, T right) -> bool {
-        return static_cast<typename std::make_unsigned<T>::type>(left) >= static_cast<typename std::make_unsigned<T>::type>(right);
-    };
-
-    auto below = [&] (T left, T right) -> bool {
-        return static_cast<typename std::make_unsigned<T>::type>(left) < static_cast<typename std::make_unsigned<T>::type>(right);
-    };
-
-    ad = d < 0 ? -d : d;
-    t = signedMin + zshr(d, bitWidth - 1);
-    anc = t - 1 - urem(t, ad);   // absolute value of nc
+    ad = divisor < 0 ? -divisor : divisor; // -(signed min value) < signed max value. So there is no loss.
+    t = signedMin + (d >> (bitWidth - 1));
+    anc = t - 1 - (t % ad);   // absolute value of nc
     p = bitWidth - 1;    // initialize p
-    q1 = udiv(signedMin, anc);   // initialize q1 = 2p/abs(nc)
+    q1 = signedMin / anc;   // initialize q1 = 2p/abs(nc)
     r1 = signedMin - q1*anc;    // initialize r1 = rem(2p,abs(nc))
-    q2 = udiv(signedMin, ad);    // initialize q2 = 2p/abs(d)
+    q2 = signedMin / ad;    // initialize q2 = 2p/abs(d)
     r2 = signedMin - q2*ad;     // initialize r2 = rem(2p,abs(d))
     do {
         p = p + 1;
         q1 = q1 << 1;          // update q1 = 2p/abs(nc)
         r1 = r1 << 1;          // update r1 = rem(2p/abs(nc))
-        if (aboveEqual(r1, anc)) {  // must be unsigned comparison
+        if (r1 >= anc) {  // must be unsigned comparison
             q1 = q1 + 1;
             r1 = r1 - anc;
         }
         q2 = q2 << 1;          // update q2 = 2p/abs(d)
         r2 = r2 << 1;          // update r2 = rem(2p/abs(d))
-        if (aboveEqual(r2,ad)) {   // must be unsigned comparison
+        if (r2 >= ad) {   // must be unsigned comparison
             q2 = q2 + 1;
             r2 = r2 - ad;
         }
         delta = ad - r2;
-    } while (below(q1, delta) || (q1 == delta && r1 == 0));
+    } while (q1 < delta || (q1 == delta && r1 == 0));
 
     mag.magicMultiplier = q2 + 1;
-    if (d < 0)
+    if (divisor < 0)
         mag.magicMultiplier = -mag.magicMultiplier;   // resulting magic number
     mag.shift = p - bitWidth;          // resulting shift
 
index b264e4f..85cf1ab 100644 (file)
@@ -30,6 +30,7 @@
 #include "B3BasicBlockInlines.h"
 #include "B3CCallValue.h"
 #include "B3Compilation.h"
+#include "B3ComputeDivisionMagic.h"
 #include "B3Const32Value.h"
 #include "B3ConstPtrValue.h"
 #include "B3ControlValue.h"
@@ -9983,6 +9984,14 @@ void testSShrShl64(int64_t value, int32_t sshrAmount, int32_t shlAmount)
         == ((value << (shlAmount & 63)) >> (sshrAmount & 63)));
 }
 
+template<typename T>
+void testComputeDivisionMagic(T value, T magicMultiplier, unsigned shift)
+{
+    DivisionMagic<T> magic = computeDivisionMagic(value);
+    CHECK(magic.magicMultiplier == magicMultiplier);
+    CHECK(magic.shift == shift);
+}
+
 // Make sure the compiler does not try to optimize anything out.
 NEVER_INLINE double zero()
 {
@@ -11381,6 +11390,8 @@ void run(const char* filter)
 
     RUN(testCheckMul64SShr());
 
+    RUN(testComputeDivisionMagic<int32_t>(2, -2147483647, 0));
+
     if (tasks.isEmpty())
         usage();