DFG overflow check elimination is too smart for its own good

[Filip Pizlo]

I've learned that:

1) It's unsound, see test case below.

2) It takes up too much compile time while trying to be too smart.



function foo(a, b, o) {
    return (a + b + o.f) | 0;
}

eval("");

var array = [];
for (var i = 0; i < 10000; ++i) {
    var a, b, c;
    if (i < 100) {
        a = 1;
        b = 2;
        c = 3;
    } else {
        var j = i - 100;
        a = 2147483647 - ((j + 0) / 3) | 0;
        b = 2147483647 - ((j + 1) / 3) | 0;
        c = 4503599627370495 * Math.pow(2, (((j / 3) % 1000) | 0) - 1);
    }
    var result = foo(a, b, {f:c});
    if (i >= 100)
        array.push(result);
}

print(array);

[Filip Pizlo]

Created attachment 192175 [details]
work in progress

[Filip Pizlo]

Better test:



function foo(a, b, o) {
    return (a + b + o.f) | 0;
}

function bar(a, b, o) {
    eval(""); // Prevent this function from being compiled.
    return foo(a, b, o);
}

var badCases = [
    {a:2147483645, b:2147483644, c:9007199254740990, expected:-8},
    {a:2147483643, b:2147483643, c:18014398509481980, expected:-16},
    {a:2147483643, b:2147483642, c:36028797018963960, expected:-16},
    {a:2147483642, b:2147483642, c:36028797018963960, expected:-16},
    {a:2147483641, b:2147483640, c:144115188075855840, expected:-32},
    {a:2147483640, b:2147483640, c:144115188075855840, expected:-64},
    {a:2147483640, b:2147483639, c:288230376151711680, expected:-64},
    {a:2147483639, b:2147483639, c:288230376151711680, expected:-64}
];

var warmup = 100;

for (var i = 0; i < warmup + badCases.length; ++i) {
    var a, b, c;
    var expected;
    if (i < warmup) {
        a = 1;
        b = 2;
        c = 3;
        expected = 6;
    } else {
        var current = badCases[i - warmup];
        a = current.a;
        b = current.b;
        c = current.c;
        expected = current.expected;
    }
    var result = bar(a, b, {f:c});
    if (result != expected)
        print("Bad result: a = " + a + ", b = " + b + ", c = " + c + ": expected = " + expected + ", but got: " + result);
}

[Filip Pizlo]

Created attachment 192281 [details]
the patch

[Early Warning System Bot]

Comment on attachment 192281 [details]
the patch

Attachment 192281 [details] did not pass qt-ews (qt):
Output: http://webkit-commit-queue.appspot.com/results/17109221

[EFL EWS Bot]

Comment on attachment 192281 [details]
the patch

Attachment 192281 [details] did not pass efl-ews (efl):
Output: http://webkit-commit-queue.appspot.com/results/17050668

[Early Warning System Bot]

Comment on attachment 192281 [details]
the patch

Attachment 192281 [details] did not pass qt-wk2-ews (qt):
Output: http://webkit-commit-queue.appspot.com/results/17113204

[Filip Pizlo]

Created attachment 192307 [details]
patch for landing

The actual patch will also have two test cases, but I haven't built the expectations files for those yet.

[WebKit Review Bot]

Attachment 192307 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/CMakeLists.txt', u'Source/JavaScriptCore/ChangeLog', u'Source/JavaScriptCore/GNUmakefile.list.am', u'Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj', u'Source/JavaScriptCore/Target.pri', u'Source/JavaScriptCore/dfg/DFGArrayMode.cpp', u'Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp', u'Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.h', u'Source/JavaScriptCore/dfg/DFGCPSRethreadingPhase.cpp', u'Source/JavaScriptCore/dfg/DFGDriver.cpp', u'Source/JavaScriptCore/dfg/DFGGraph.cpp', u'Source/JavaScriptCore/dfg/DFGNodeFlags.cpp', u'Source/JavaScriptCore/dfg/DFGNodeFlags.h', u'Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp', u'Source/JavaScriptCore/dfg/DFGUnificationPhase.cpp', u'Source/JavaScriptCore/dfg/DFGVariableAccessData.h']" exit_code: 1
Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp:54:  Missing spaces around <<  [whitespace/operators] [3]
Total errors found: 1 in 16 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Filip Pizlo]

Landed in http://trac.webkit.org/changeset/145299

[WebKit Review Bot]

Re-opened since this is blocked by bug 111928

[Filip Pizlo]

Landed in http://trac.webkit.org/changeset/145489