DFG LICM needs to go all-in on the idea that some loops can't be LICMed
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 3 Jul 2016 17:46:39 +0000 (17:46 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 3 Jul 2016 17:46:39 +0000 (17:46 +0000)
https://bugs.webkit.org/show_bug.cgi?id=159388

Reviewed by Mark Lam.

Some time ago I acknowledged that LICM required loops to meet certain requirements that
may get broken by the time we do LICM, like that the terminal of the pre-header is ExitOK.
It used to be that we just ignored that requirement and would hoist anyway, but since
r189126 we've stopped hoisting out of loops that don't have ExitOK.  We also added tests
for the case that the pre-header doesn't exist or is invalid.

It turns out that this patch didn't go far enough: even though it made LICM avoid loops
that had an invalid pre-header, the part that updated the AI state in nested loops still
assumed that these loops had valid pre-headers.  We would crash in null dereference in
that loop if a nested loop had an invalid pre-header.

The fix is simple: don't update the AI state of nested loops that don't have pre-headers,
since we won't try to hoist out of those loops anyway.

* dfg/DFGLICMPhase.cpp:
(JSC::DFG::LICMPhase::attemptHoist):
* tests/stress/licm-no-pre-header-nested.js: Added. This would always crash before this fix.
(foo):
* tests/stress/licm-pre-header-cannot-exit-nested.js: Added. This was a failed attempt at a test, but I figure it's good to have weird code anyway.
(foo):
(valueOf):

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGLICMPhase.cpp
Source/JavaScriptCore/tests/stress/licm-no-pre-header-nested.js [new file with mode: 0644]
Source/JavaScriptCore/tests/stress/licm-pre-header-cannot-exit-nested.js [new file with mode: 0644]
Source/WTF/benchmarks/LockFairnessTest.cpp

index 92a08c433aff8757bfd6e5dd1f3c3a4dac53fd1d..17401a4482b4c6c616d17d445822cab54ac42ea5 100644 (file)
@@ -1,3 +1,32 @@
+2016-07-02  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG LICM needs to go all-in on the idea that some loops can't be LICMed
+        https://bugs.webkit.org/show_bug.cgi?id=159388
+
+        Reviewed by Mark Lam.
+        
+        Some time ago I acknowledged that LICM required loops to meet certain requirements that
+        may get broken by the time we do LICM, like that the terminal of the pre-header is ExitOK.
+        It used to be that we just ignored that requirement and would hoist anyway, but since
+        r189126 we've stopped hoisting out of loops that don't have ExitOK.  We also added tests
+        for the case that the pre-header doesn't exist or is invalid.
+
+        It turns out that this patch didn't go far enough: even though it made LICM avoid loops
+        that had an invalid pre-header, the part that updated the AI state in nested loops still
+        assumed that these loops had valid pre-headers.  We would crash in null dereference in
+        that loop if a nested loop had an invalid pre-header.
+
+        The fix is simple: don't update the AI state of nested loops that don't have pre-headers,
+        since we won't try to hoist out of those loops anyway.
+
+        * dfg/DFGLICMPhase.cpp:
+        (JSC::DFG::LICMPhase::attemptHoist):
+        * tests/stress/licm-no-pre-header-nested.js: Added. This would always crash before this fix.
+        (foo):
+        * tests/stress/licm-pre-header-cannot-exit-nested.js: Added. This was a failed attempt at a test, but I figure it's good to have weird code anyway.
+        (foo):
+        (valueOf):
+
 2016-06-30  Filip Pizlo  <fpizlo@apple.com>
 
         Scopes that are not under TDZ should still push their variables onto the TDZ stack so that lifting TDZ doesn't bypass that scope
index 86f4a6b91b67be3a7d75904aeabb84c0555442d6..deed20b1b30720c40dad480184cce7e2698f7946 100644 (file)
@@ -324,6 +324,12 @@ private:
             if (!subLoop)
                 continue;
             BasicBlock* subPreHeader = m_data[subLoop->index()].preHeader;
+            // We may not have given this loop a pre-header because either it didn't have exitOK
+            // or the header had multiple predecessors that it did not dominate. In that case the
+            // loop wouldn't be a hoisting candidate anyway, so we don't have to do anything.
+            if (!subPreHeader)
+                continue;
+            // The pre-header's tail may be unreachable, in which case we have nothing to do.
             if (!subPreHeader->cfaDidFinish)
                 continue;
             m_state.initializeTo(subPreHeader);
diff --git a/Source/JavaScriptCore/tests/stress/licm-no-pre-header-nested.js b/Source/JavaScriptCore/tests/stress/licm-no-pre-header-nested.js
new file mode 100644 (file)
index 0000000..73ca574
--- /dev/null
@@ -0,0 +1,23 @@
+//@ runMiscFTLNoCJITTest("--createPreHeaders=false")
+
+function foo(array, y) {
+    var x = 0;
+    var j = 0;
+    do {
+        x = y * 3;
+        var result = 0;
+        var i = 0;
+        if (!array.length)
+            array = [1];
+        do {
+            result += array[i++];
+        } while (i < array.length)
+        j++;
+    } while (j < 3);
+    return result + x;
+}
+
+noInline(foo);
+
+for (var i = 0; i < 10000; ++i)
+    foo([1, 2, 3], 42);
diff --git a/Source/JavaScriptCore/tests/stress/licm-pre-header-cannot-exit-nested.js b/Source/JavaScriptCore/tests/stress/licm-pre-header-cannot-exit-nested.js
new file mode 100644 (file)
index 0000000..be6a6b6
--- /dev/null
@@ -0,0 +1,21 @@
+//@ runMiscFTLNoCJITTest("--createPreHeaders=false")
+
+function foo(object, predicate) {
+    for (var j = 0; j < 10; ++j) {
+        var result = 0;
+        var i = 0;
+        if (DFGTrue())
+            predicate = 42;
+        while (predicate >= 42) {
+            result += object.array[i++];
+            if (i >= object.array.length)
+                break;
+        }
+    }
+    return result;
+}
+
+noInline(foo);
+
+for (var i = 0; i < 10000; ++i)
+    foo({array: [1, 2, 3]}, {valueOf: function() { return 42; }});
index e808908418cf150ad75eb35ab4a46b050875f1ab..f08321c0f68836535d83cb6bc7511848bb52d94f 100644 (file)
@@ -48,12 +48,13 @@ namespace {
 
 NO_RETURN void usage()
 {
-    printf("Usage: LockFairnessTest yieldspinlock|pausespinlock|wordlock|lock|barginglock|bargingwordlock|thunderlock|thunderwordlock|cascadelock|cascadewordlockhandofflock|mutex|all <num threads> <seconds per test>\n");
+    printf("Usage: LockFairnessTest yieldspinlock|pausespinlock|wordlock|lock|barginglock|bargingwordlock|thunderlock|thunderwordlock|cascadelock|cascadewordlockhandofflock|mutex|all <num threads> <seconds per test> <microseconds in critical section>\n");
     exit(1);
 }
 
 unsigned numThreads;
 double secondsPerTest;
+unsigned microsecondsInCriticalSection;
 
 struct Benchmark {
     template<typename LockType>
@@ -72,9 +73,19 @@ struct Benchmark {
             threads[threadIndex] = createThread(
                 "Benchmark Thread",
                 [&, threadIndex] () {
+                    if (!microsecondsInCriticalSection) {
+                        while (keepGoing) {
+                            lock.lock();
+                            counts[threadIndex]++;
+                            lock.unlock();
+                        }
+                        return;
+                    }
+                    
                     while (keepGoing) {
                         lock.lock();
                         counts[threadIndex]++;
+                        usleep(microsecondsInCriticalSection);
                         lock.unlock();
                     }
                 });
@@ -85,8 +96,8 @@ struct Benchmark {
     
         sleep(secondsPerTest);
     
-        lock.lock();
         keepGoing = false;
+        lock.lock();
     
         dataLog(name, ": ");
         CommaPrinter comma;
@@ -106,9 +117,10 @@ int main(int argc, char** argv)
 {
     WTF::initializeThreading();
     
-    if (argc != 4
+    if (argc != 5
         || sscanf(argv[2], "%u", &numThreads) != 1
-        || sscanf(argv[3], "%lf", &secondsPerTest) != 1)
+        || sscanf(argv[3], "%lf", &secondsPerTest) != 1
+        || sscanf(argv[4], "%u", &microsecondsInCriticalSection) != 1)
         usage();
     
     runEverything<Benchmark>(argv[1]);