JavaScriptCore does not have speculative->baseline OSR

[Filip Pizlo]

The DFG JIT handles speculation failures by always generating a non-speculative version of the same optimized code, and then emitting jumps and recoveries between the speculative and non-speculative path.  This has a number of issues:

1) It means that when doing tiered compilation, we have three copies of the same code: old JIT, DFG speculative, and DFG non-speculative.  Since the DFG non-speculative path ends up doing more-or-less the same things as the code emitted by the old JIT, it would be nice if we could skip emitting the non-speculative path.

2) It means maintaining two paths for the DFG JIT.  A lot of logic gets duplicated, and maintenance effort is increased, by the presence of two DFG back-ends.

3) It complicates the development of speculative optimizations that rely on mutating the DFG graph.  The speculative->non-speculative jump relies on both backends using the same graph.

All of these problems can be eliminated if the speculative JIT can bail out by performing OSR to the old JIT.

[Filip Pizlo]

Created attachment 106827 [details]
work in progress

This is an early-stage work-in-progress and does not yet work, but I figured I'd back it up and allow others to take a peek.

[Filip Pizlo]

Created attachment 106925 [details]
work in progress - so far it appears to work, sort of

This patch still needs some love, but it's getting there!

Here's a synopsis of how this works:

1) We already had the policy of storing the bytecode index from which a DFG node originated in the node itself.  I made this policy more official by changing the name of the relevant field to CodeOrigin.  When we have inlining, the CodeOrigin class will be able to also hold the CodeBlock* from which the code originated, or more likely a pointer to an inlining stack.

2) The CodeBlock now stores a mapping between bytecode indices and machine code offsets, for each instruction, for code compiled with the old JIT.  This information is stored in using a fairly compact and fairly efficient entropy encoding, assuming that distances between adjacent indices and offsets will be small.  The DFG decodes this information when generating OSR exit code.

3) We already had the policy of emitting SetLocal nodes in the DFG flow at exactly the points where the old JIT would have mutated a virtual register.  These almost always get killed by our ref-count based DCE, but even then they remain in the IR - they're just marked dead.  This information is now used heavily by the OSR code, which performs an abstract interpretation of SetLocals in tandem with speculative compilation.  The abstract state is just a mapping between bytecode operands and the DFG nodes that hold (or held) the value that the virtual register for that bytecode operand would have held if we were executing with the old JIT.  At OSR points, we use this to figure out a strategy for recovering the value of each old JIT virtual register based on the nodes that are currently live.  In some cases, this node will be dead, which means that the old JIT would not have needed the value anyway, and so we store Undefined into the virtual register.  In other cases, there is some other node that holds an equivalent value; if this is proven by the OSR recovery calculator, then that node's value is used.  In all, four cases exist: (i) the virtual register already contains the right value because the relevant SetLocal was emitted by the DFG backend, (ii) there is some physical register that contains either the value we want or a value that can be converted into the one we want, (iii) the virtual register would have held a constant at this point and we know the constant's value, or (iv) there is some other virtual register that currently holds the value that we want, so we need to shuffle the virtual register file.

4) The old JIT register allocates the result of the last operation.  Luckily, SetLocals come to the rescue once more - so the SetLocal abstract interpreter tracks the virtual register operand of the last SetLocal executed.  The OSR exit code simply loads this virtual register into the cachedResultRegister prior to jumping.

5) When all of this is enabled, we skip emitting the non-speculative code.

Work remaining:

1) Fix at least one known bug: the OSR exit code sometimes underestimates the size of the old JIT's register file (omitting temporaries that are not yet set).  Currently it does nothing for these temporaries, but it should probably set them to undefined.

2) Test, test, test.

3) Benchmark.

[Filip Pizlo]

Created attachment 106931 [details]
work in progress - passes run-javascriptcore-tests and runs both SunSpider and V8

Still running webkit-tests and then will do some performance measuring.

[Filip Pizlo]

Created attachment 106941 [details]
the patch

When enabled, this breaks some sites.  Still working on it.  But I think fundamentally the patch is correct; it's just a matter of ensuring that we have all of the dead-node recoveries that we ought to have.

[WebKit Review Bot]

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

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/ChangeLog', u'Source..." exit_code: 1

Source/JavaScriptCore/dfg/DFGJITCompiler.cpp:209:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Source/JavaScriptCore/dfg/DFGJITCompiler.cpp:229:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Source/JavaScriptCore/dfg/DFGNode.h:29:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.h:295:  The parameter name "jit" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.h:455:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.h:475:  The parameter name "valueSource" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:1569:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:1572:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:1582:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Source/JavaScriptCore/jit/CompactJITCodeMap.h:34:  Alphabetical sorting problem.  [build/include_order] [4]
Source/JavaScriptCore/jit/CompactJITCodeMap.h:36:  Alphabetical sorting problem.  [build/include_order] [4]
Source/JavaScriptCore/jit/CompactJITCodeMap.h:220:  Missing spaces around <<  [whitespace/operators] [3]
Total errors found: 12 in 20 files


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

[Filip Pizlo]

Created attachment 106943 [details]
the patch - fix style

[WebKit Review Bot]

Comment on attachment 106943 [details]
the patch - fix style

Attachment 106943 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/9626801

[Filip Pizlo]

Looks like the mac-ews fail is just a matter of #ifdef'ing some debug stuff, which can't (and shouldn't) compile under release build.

I've also found the reason why OSR breaks the web.  The OSR algorithm was playing fast and loose with virtual registers.  For efficiency, it first dumps state in physical registers into the bytecode register file, and then it shuffles virtual registers that were displaced.  But this is wrong.  There may be a value stored in a virtual register by the DFG JIT, where that same virtual register is in use by the old JIT, and the value for that virtual register is currently held by the DFG JIT in a physical register.  Then the OSR code will clobber its own virtual register with a different value stored in a physical register, and then shuffle that virtual register to a different virtual register location.  And so the world breaks.  On bing it means that 'this' gets clobbered with a double, resulting in humorous fails.

This is relatively easy to fix.  In most code, the DFG does not use its virtual registers very much, since physical register allocation does its job.  So we just have to special-case the situation where the OSR would want to dump a physical register into an old-JIT virtual register slot that still holds another live value from DFG state.  In that case, the physical register can be dumped to on-the-side scratch storage.

[WebKit Review Bot]

Comment on attachment 106943 [details]
the patch - fix style

Attachment 106943 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/9628580

[Filip Pizlo]

Created attachment 106979 [details]
the patch - fix build, fix web

This fixes build errors in release builds.  It also fixed websites that were broken (bing, gmail).  The fix for the latter involved dumping registers to scratch storage, if the destination in the register file for those registers overlapped virtual registers used by the DFG.  This is probably a rare case, so the cost of dumping to scratch storage in that case is unlikely to be high.

[WebKit Review Bot]

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

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/ChangeLog', u'Source..." exit_code: 1

Source/JavaScriptCore/dfg/DFGJITCompiler.cpp:149:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Total errors found: 1 in 22 files


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

[Filip Pizlo]

Created attachment 106980 [details]
the patch - fix style

[Early Warning System Bot]

Comment on attachment 106980 [details]
the patch - fix style

Attachment 106980 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/9639108

[WebKit Review Bot]

Comment on attachment 106980 [details]
the patch - fix style

Attachment 106980 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/9634272

[Filip Pizlo]

OSR now works!  It passes all of our regressions.  It works with major websites.  And it runs all benchmarks, resulting in slight progressions on SunSpider and V8 and regressions in Kraken (that are slight in the average).  It's probably wise to ignore the Kraken regressions for now since we know that (a) we won't have loop entry OSR so most Kraken benchmarks are not benefiting from tiered compilation at all and (b) we don't have reoptimization (the ability to recompile a function with DFG if it fails speculation, and do so that takes into account new statistics gathered from the failing speculations).


Benchmark report for SunSpider, V8, and Kraken.

VMs tested:
"TipOfTreeDyn" at /Volumes/Data/pizlo/quinary/OpenSource/WebKitBuild/Release/jsc
"OSRExit" at /Volumes/Data/pizlo/OpenSource/WebKitBuild/Release/jsc

Collected 12 samples per benchmark/VM, with 4 VM invocations per benchmark. Used 1 benchmark iteration per VM
invocation for warm-up. Used the jsc-specific preciseTime() function to get microsecond-level timing. Reporting
benchmark execution times with 95% confidence intervals in milliseconds.

                                           TipOfTreeDyn              OSRExit                                     
SunSpider:
   3d-cube                               11.8832+-0.2440    ^     9.6681+-0.2282       ^ definitely 1.2291x faster
   3d-morph                               7.5369+-0.1762          7.5046+-0.1925       
   3d-raytrace                            8.2394+-0.1283          8.0395+-0.1619         might be 1.0249x faster
   access-binary-trees                    3.3760+-0.0722          3.3533+-0.0849       
   access-fannkuch                       11.5918+-0.2447    ?    11.7146+-0.2238       ? might be 1.0106x slower
   access-nbody                           4.1826+-0.0680    ?     4.2478+-0.1147       ? might be 1.0156x slower
   access-nsieve                          2.7102+-0.0361          2.6831+-0.0614         might be 1.0101x faster
   bitops-3bit-bits-in-byte               1.9729+-0.0687          1.9283+-0.0496         might be 1.0231x faster
   bitops-bits-in-byte                    4.7115+-0.3020    ?     4.9152+-0.4484       ? might be 1.0432x slower
   bitops-bitwise-and                     3.5941+-0.1131    ?     3.6054+-0.0694       ?
   bitops-nsieve-bits                     5.5131+-0.1956    ?     5.6360+-0.1615       ? might be 1.0223x slower
   controlflow-recursive                  2.1050+-0.0730          2.0301+-0.0388         might be 1.0369x faster
   crypto-aes                             7.9979+-0.2643          7.9918+-0.3528       
   crypto-md5                             2.8790+-0.1230          2.7342+-0.0698         might be 1.0530x faster
   crypto-sha1                            2.1352+-0.0247    ?     2.1696+-0.0406       ? might be 1.0161x slower
   date-format-tofte                     12.3450+-0.3264         12.3119+-0.2721       
   date-format-xparb                     11.1114+-0.2952    ?    11.3000+-0.4858       ? might be 1.0170x slower
   math-cordic                            6.1643+-0.0821    ?     6.4060+-0.1900       ? might be 1.0392x slower
   math-partial-sums                      7.5603+-0.1425          7.4775+-0.1516         might be 1.0111x faster
   math-spectral-norm                     2.6445+-0.0780          2.6129+-0.0761         might be 1.0121x faster
   regexp-dna                            10.4181+-0.2266         10.1898+-0.2301         might be 1.0224x faster
   string-base64                          8.0985+-0.2298          7.8634+-0.2040         might be 1.0299x faster
   string-fasta                           8.3157+-0.2385          8.2553+-0.2073       
   string-tagcloud                       12.8542+-0.3710    ?    12.9207+-0.3654       ?
   string-unpack-code                    20.6737+-0.5416    ?    20.7743+-0.5640       ?
   string-validate-input                  9.0153+-0.3631    ?     9.0196+-0.2562       ?

   <arithmetic>                           7.2934+-0.0483    ^     7.2059+-0.0333       ^ definitely 1.0122x faster
   <geometric>                            6.0034+-0.0370    ^     5.9398+-0.0252       ^ definitely 1.0107x faster
   <harmonic>                             4.8565+-0.0415          4.8061+-0.0255         might be 1.0105x faster

                                           TipOfTreeDyn              OSRExit                                     
V8:
   crypto                                86.3151+-0.3629         86.1764+-0.3105       
   deltablue                            266.6833+-1.5991    ?   269.2468+-1.1473       ?
   earley-boyer                         107.8270+-0.5498        107.7879+-0.5193       
   raytrace                              88.5111+-0.5719         86.7848+-1.5351         might be 1.0199x faster
   regexp                               118.9526+-0.5743    ^   117.8709+-0.3367       ^ definitely 1.0092x faster
   richards                             216.6778+-1.3869    ?   217.1691+-0.9882       ?
   splay                                187.5032+-0.6330    ^   174.7040+-6.9140       ^ definitely 1.0733x faster

   <arithmetic>                         153.2100+-0.2259    ^   151.3914+-1.0179       ^ definitely 1.0120x faster
   <geometric>                          140.1392+-0.2406    ^   138.3215+-0.8440       ^ definitely 1.0131x faster
   <harmonic>                           128.9961+-0.2924    ^   127.3734+-0.7018       ^ definitely 1.0127x faster

                                           TipOfTreeDyn              OSRExit                                     
Kraken:
   ai-astar                            1128.6180+-7.1150       1127.4359+-7.7371       
   audio-beat-detection                 472.8197+-1.2062        472.3424+-2.9160       
   audio-dft                            423.6761+-2.3933    ?   426.5928+-3.3890       ?
   audio-fft                            362.2386+-1.2123    ?   364.0392+-1.1656       ?
   audio-oscillator                     352.5599+-0.5061        349.6026+-3.8875       
   imaging-darkroom                     538.6404+-7.8410        532.3047+-1.5578         might be 1.0119x faster
   imaging-desaturate                   592.7078+-0.9541    ^   570.8482+-6.6708       ^ definitely 1.0383x faster
   imaging-gaussian-blur               2278.5075+-5.4647       2274.8347+-6.5982       
   json-parse-financial                  54.9914+-0.2639    ?    55.7274+-0.7098       ? might be 1.0134x slower
   json-stringify-tinderbox              68.9338+-0.2610         68.6296+-0.3315       
   stanford-crypto-aes                  152.0854+-1.0092        151.8612+-1.0505       
   stanford-crypto-ccm                  126.4553+-0.9482    ^   124.4325+-0.9059       ^ definitely 1.0163x faster
   stanford-crypto-pbkdf2               355.3449+-0.6106    !   412.1360+-3.4859       ! definitely 1.1598x slower
   stanford-crypto-sha256-iterative     138.7477+-1.3769    !   152.6267+-0.2970       ! definitely 1.1000x slower

   <arithmetic>                         503.3090+-0.9085    !   505.9581+-0.7395       ! definitely 1.0053x slower
   <geometric>                          309.9293+-0.5830    !   314.0504+-0.7148       ! definitely 1.0133x slower
   <harmonic>                           194.0622+-0.4802    !   196.7704+-0.8967       ! definitely 1.0140x slower

                                           TipOfTreeDyn              OSRExit                                     
All benchmarks:
   <arithmetic>                         176.7750+-0.2894    ?   177.2448+-0.3249       ?
   <geometric>                           31.0725+-0.1029         30.9515+-0.0943       
   <harmonic>                             8.5764+-0.0714          8.4901+-0.0443         might be 1.0102x faster

[Filip Pizlo]

Created attachment 106986 [details]
the patch - disable tiering, which the last patch accidentally enabled

This is now passing all tests.  It's ready for review.

[Filip Pizlo]

Created attachment 106987 [details]
the patch - fix conflict

[Filip Pizlo]

Created attachment 106988 [details]
the patch - once again, changed Platform.h

In the previous patch I once again left tiering enabled.

[Filip Pizlo]

Created attachment 106992 [details]
the patch - fix broken assert

This now passes tests with tiering turned both on and off.  It's lucky that tiering turned off still leads to the OSR exit analysis running, since it revealed breakeage in an ASSERT statement for SetLocals.  It turns out that synthetic SetLocals (like the ones that initialize variables to undefined) are sufficiently special that the ASSERT about the bytecode index of the node following the SetLocal was wrong.  The ASSERT just needed to be made a slight bit more lenient.

[WebKit Review Bot]

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

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/ChangeLog', u'Source..." exit_code: 1

Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:754:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
Total errors found: 1 in 21 files


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

[Filip Pizlo]

Created attachment 107000 [details]
the patch - fix style

[Oliver Hunt]

Comment on attachment 107000 [details]
the patch - fix style

View in context: https://bugs.webkit.org/attachment.cgi?id=107000&action=review

> Source/JavaScriptCore/dfg/DFGDriver.cpp:47
> +    if (false) {
> +        switch (codeBlock->instructions().size() * sizeof(Instruction)) {
> +        case 11176:
> +            return false;
> +        default:
> +            break;
> +        }
> +    }

please to be removing the debugging code? :D

> Source/JavaScriptCore/dfg/DFGJITCompiler.cpp:103
> +#if DFG_OSR

I'd prefer we used the ENABLE() style macros, e.g. ENABLE(DFG_OSR)

> Source/JavaScriptCore/dfg/DFGJITCompiler.cpp:109
> +#if DFG_DEBUG_VERBOSE

ENABLE() again

> Source/JavaScriptCore/dfg/DFGJITCompiler.cpp:113
> +#if DFG_JIT_BREAK_ON_SPECULATION_FAILURE

and again

> Source/JavaScriptCore/dfg/DFGJITCompiler.cpp:117
> +#if DFG_VERBOSE_SPECULATION_FAILURE

...

> Source/JavaScriptCore/dfg/DFGJITCompiler.cpp:1184
> +#if DFG_OSR

ENABLE()

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:176
> +#ifndef NDEBUG

This seems more related to the presence or absence of VERBOSE logging rather than debug build vs. not debug build -- perhaps it should be 
#if ENABLE(....) || !defined(NDEBUG) 
?

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.h:219
> +    JSValue constant() const
> +    {
> +        ASSERT(m_technique == Constant);
> +        return JSValue::decode(m_source.constant);
> +    }

Just for reference can a constant be a JSString?  Does this end up relying on the containing code block for marking?

> Source/JavaScriptCore/runtime/JSGlobalData.h:239
> +        Vector<int64_t*> osrScratchBuffers;

Honestly I think i'd prefer a Vector of vectors here -- If we really felt it would be beneficial we could come up with a more sensible "Array" class -> the absence of range checking in debug builds and the need to manually free the arrays is just a little icky to me.

[Filip Pizlo]

> > Source/JavaScriptCore/dfg/DFGJITCompiler.cpp:103
> > +#if DFG_OSR
> 
> I'd prefer we used the ENABLE() style macros, e.g. ENABLE(DFG_OSR)
> 
> > Source/JavaScriptCore/dfg/DFGJITCompiler.cpp:109
> > +#if DFG_DEBUG_VERBOSE
> 
> ENABLE() again
> 
> > Source/JavaScriptCore/dfg/DFGJITCompiler.cpp:113
> > +#if DFG_JIT_BREAK_ON_SPECULATION_FAILURE
> 
> and again
> 
> > Source/JavaScriptCore/dfg/DFGJITCompiler.cpp:117
> > +#if DFG_VERBOSE_SPECULATION_FAILURE
> 
> ...
> 

I've filed a bug against this: https://bugs.webkit.org/show_bug.cgi?id=67907

> This seems more related to the presence or absence of VERBOSE logging rather than debug build vs. not debug build -- perhaps it should be 
> #if ENABLE(....) || !defined(NDEBUG) 
> ?

The goal there was to enable us to plant dump() statements wherever necessary when debugging, without having to enable DFG_DEBUG_VERBOSE, since in some (admittedly rare) situations DFG_DEBUG_VERBOSE causes too much output.

This isn't a big deal since I've happily browsed the interwebs with DFG_DEBUG_VERBOSE and was reasonably happy.

> 
> > Source/JavaScriptCore/dfg/DFGSpeculativeJIT.h:219
> > +    JSValue constant() const
> > +    {
> > +        ASSERT(m_technique == Constant);
> > +        return JSValue::decode(m_source.constant);
> > +    }
> 
> Just for reference can a constant be a JSString?  Does this end up relying on the containing code block for marking?

All constants come from the CodeBlock's constant pool, so yes.

> 
> > Source/JavaScriptCore/runtime/JSGlobalData.h:239
> > +        Vector<int64_t*> osrScratchBuffers;
> 
> Honestly I think i'd prefer a Vector of vectors here -- If we really felt it would be beneficial we could come up with a more sensible "Array" class -> the absence of range checking in debug builds and the need to manually free the arrays is just a little icky to me.

Vector<void*> it is for now, as per our discussions on IRC.

[Filip Pizlo]

Created attachment 107077 [details]
the patch - fix review

[WebKit Review Bot]

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

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/ChangeLog', u'Source..." exit_code: 1

Source/JavaScriptCore/dfg/DFGJITCodeGenerator.h:36:  Alphabetical sorting problem.  [build/include_order] [4]
Total errors found: 1 in 21 files


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

[Filip Pizlo]

Created attachment 107079 [details]
the patch - fix style

[Oliver Hunt]

Comment on attachment 107079 [details]
the patch - fix style

View in context: https://bugs.webkit.org/attachment.cgi?id=107079&action=review

> Source/JavaScriptCore/dfg/DFGDriver.cpp:47
> +    if (false) {
> +        switch (codeBlock->instructions().size() * sizeof(Instruction)) {
> +        case 11176:
> +            return false;
> +        default:
> +            break;
> +        }
> +    }

DIE!!!!!!1111!!!!11!!!1!1111!!!!oneoneone!!!!onehundredandeleven!!

[Filip Pizlo]

Created attachment 107085 [details]
the patch - fix review

[Filip Pizlo]

Comment on attachment 107085 [details]
the patch - fix review

Committing manually.

[Filip Pizlo]

Landed in r94996.