Bug 111832

Summary: DFG overflow check elimination is too smart for its own good
Product: WebKit Reporter: Filip Pizlo <fpizlo>
Component: JavaScriptCoreAssignee: Filip Pizlo <fpizlo>
Status: RESOLVED FIXED    
Severity: Normal CC: barraclough, ggaren, gyuyoung.kim, mark.lam, mhahnenberg, msaboff, oliver, rakuco, sam, webkit-ews, webkit.review.bot
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: All   
OS: All   
Bug Depends on: 111928    
Bug Blocks:    
Attachments:
Description Flags
work in progress
none
the patch
oliver: review+, webkit-ews: commit-queue-
patch for landing none

Description Filip Pizlo 2013-03-08 01:21:03 PST
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);
Comment 1 Filip Pizlo 2013-03-08 01:21:26 PST
Created attachment 192175 [details]
work in progress
Comment 2 Filip Pizlo 2013-03-08 14:00:43 PST
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);
}
Comment 3 Filip Pizlo 2013-03-08 14:09:25 PST
Created attachment 192281 [details]
the patch
Comment 4 Early Warning System Bot 2013-03-08 14:14:12 PST
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
Comment 5 EFL EWS Bot 2013-03-08 14:54:11 PST
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
Comment 6 Early Warning System Bot 2013-03-08 14:57:55 PST
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
Comment 7 Filip Pizlo 2013-03-08 16:37:04 PST
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.
Comment 8 WebKit Review Bot 2013-03-08 16:39:22 PST
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.
Comment 9 Filip Pizlo 2013-03-08 18:53:26 PST
Landed in http://trac.webkit.org/changeset/145299
Comment 10 WebKit Review Bot 2013-03-09 14:43:13 PST
Re-opened since this is blocked by bug 111928
Comment 11 Filip Pizlo 2013-03-11 23:46:31 PDT
Landed in http://trac.webkit.org/changeset/145489