Bug 164309 – DFG plays fast and loose with the shadow values of a Phi

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[David I. Lehn]

Summary: JavaScriptCore appears to incorrectly optimize variable assignment in hot loops on x86-64 builds resulting in eventual incorrect behavior.

I work on a JS library called forge that has many hashing and crypto functions.  Recent Safari 10.0.1 and iOS have had problems with the SHA-1 and SHA-256 implementations.  They could sometimes produce incorrect results for deterministic inputs.  We found a workaround for a company that needed these to work specifically on Safari 10.0.1 and iOS.  It involved adding some ">>> 0" in the middle of short shuffling loops (see patch links in the github issue).

After further exploration, this has been narrowed down to likely be in JavaScriptCore x86-64 builds on mac or linux.  i386 works fine.  It appears hot loops doing shuffling of variables can result in errors.  It was reduced down to a test case that just swaps two variables in a loop.  Sometimes they do not get swapped and one value is overwritten.  Adding a ">>> 0" or similar can fix this possibly due to changing how the optimizer works.

https://github.com/digitalbazaar/forge/issues/428

In particular, short web page and jsc tests cases are here:
https://github.com/digitalbazaar/forge/issues/428#issuecomment-257652657

For fun I reduced the test case to ES2015 code that could fit in a tweet:
var i;for(;;)(()=>{var a=1,b;for(i=0;i<2;++i){[a,b]=[b,a]}if(!a^b))throw 0})()

If you want some debugging to know how many swaps it takes, here's the "long" version:
var i,c=0;for(;;)(()=>{var a=1,b;for(i=0;i<2;++i){[a,b]=[b,a];c++}if(!a^b)throw c})()

Run the above in jsc and it will throw 0.  Which means it failed to swap a and b properly.  In i386 builds or node it will run forever.

[Radar WebKit Bug Importer]

<rdar://problem/29057323>

[Mark Lam]

I'm investigating the issue.

[Filip Pizlo]

Looks fun, I'll take this.  Here's the reduced test case that would work as a JSC stress test:

var i,c=0;
function foo()
{
    var a=1,b;for(i=0;i<2;++i){[a,b]=[b,a];c++}if(!a^b)throw c
}
noInline(foo);
for(var k = 0; k < 10000; ++k)
    foo()

This fails when running with --useConcurrentJIT=false --useFTLJIT=true.  It passes with --useConcurrentJIT=false --useFTLJIT=false.

[David I. Lehn]

There are clearer ways to write that test than the silly minimal version I did for fun. Like format it, and set b to 0 vs undefined. :-)  Can also do "var t=b;b=a;a=t;" vs the destructuring style in case this was a problem before ES2015 features were added to the code.

I also realized saying this was only on x86-64 may not be true.  In this particular case it worked but without knowing the cause of the issue, it could be a problem on other platforms.

Since there's a easy to run test case, it may be possible to narrow it down using 'git bisect' or similar.  I started to do so with a partial git checkout (the history is huge!).  Fails at least back on 2016-03-13 (when the build-jsc --jsc-only flag was added).  So need to check earlier than that.

[Filip Pizlo]

This is a liveness analysis bug.  There's a basic block like this:

Block #2 (bc#42):
 124:<!0:->	ExitOK(MustGen, W:SideState, bc#42)
 113:< 1:->	Upsilon(Check:Untyped:@40, ^65, W:SideState, bc#42)
 111:< 1:->	Upsilon(Check:Untyped:@65, ^40, W:SideState, bc#42)
  96:<!0:->	Jump(MustGen, T:#3, W:SideState, bc#42)

Clearly, @65 is live at the head of the block.  But liveness analysis reports this as live at the head: @1, @24, @27, @40, @43

Note that @65 is omitted.

[Filip Pizlo]

(In reply to comment #4)
> There are clearer ways to write that test than the silly minimal version I
> did for fun. Like format it, and set b to 0 vs undefined. :-)  Can also do
> "var t=b;b=a;a=t;" vs the destructuring style in case this was a problem
> before ES2015 features were added to the code.
> 
> I also realized saying this was only on x86-64 may not be true.  In this
> particular case it worked but without knowing the cause of the issue, it
> could be a problem on other platforms.
> 
> Since there's a easy to run test case, it may be possible to narrow it down
> using 'git bisect' or similar.  I started to do so with a partial git
> checkout (the history is huge!).  Fails at least back on 2016-03-13 (when
> the build-jsc --jsc-only flag was added).  So need to check earlier than
> that.

It's OK, I got this.

[Filip Pizlo]

(In reply to comment #5)
> This is a liveness analysis bug.  There's a basic block like this:
> 
> Block #2 (bc#42):
>  124:<!0:->	ExitOK(MustGen, W:SideState, bc#42)
>  113:< 1:->	Upsilon(Check:Untyped:@40, ^65, W:SideState, bc#42)
>  111:< 1:->	Upsilon(Check:Untyped:@65, ^40, W:SideState, bc#42)
>   96:<!0:->	Jump(MustGen, T:#3, W:SideState, bc#42)
> 
> Clearly, @65 is live at the head of the block.  But liveness analysis
> reports this as live at the head: @1, @24, @27, @40, @43
> 
> Note that @65 is omitted.

Oh wait, no.  It's not live.  It's killed by the other Upsilon.  Huh.

This looks like a classic swap bug.  Our SSA conversion strategy nominally works in the face of swaps.  I'll have to think about this a bit more.

[Filip Pizlo]

(In reply to comment #7)
> (In reply to comment #5)
> > This is a liveness analysis bug.  There's a basic block like this:
> > 
> > Block #2 (bc#42):
> >  124:<!0:->	ExitOK(MustGen, W:SideState, bc#42)
> >  113:< 1:->	Upsilon(Check:Untyped:@40, ^65, W:SideState, bc#42)
> >  111:< 1:->	Upsilon(Check:Untyped:@65, ^40, W:SideState, bc#42)
> >   96:<!0:->	Jump(MustGen, T:#3, W:SideState, bc#42)
> > 
> > Clearly, @65 is live at the head of the block.  But liveness analysis
> > reports this as live at the head: @1, @24, @27, @40, @43
> > 
> > Note that @65 is omitted.
> 
> Oh wait, no.  It's not live.  It's killed by the other Upsilon.  Huh.
> 
> This looks like a classic swap bug.  Our SSA conversion strategy nominally
> works in the face of swaps.  I'll have to think about this a bit more.

Ah!

The problem is that we're playing fast and loose with Upsilon/Phi semantics.  What we should be doing is saying that the Phi node is Upsilon-live between the point when the Upsilon assigns to it and the point where the Phi lives.  Separately, the Phi itself is live like any other node would be.

Just as we do this for liveness, we need to do this for forward flow.  Phis have a separate shadow variable that represents what the Upsilon stored, and we load from that shadow variable once we define the Phi.

Interestingly, B3 gets this completely right, but we forgot to port that intelligence to DFG.

[Filip Pizlo]

Obviously, this quirk of Phi is not relevant to flow-insensitive analyses.

It's interesting to wonder if it's relevant to flow-sensitive analyses.  I think that it is, but as a hack, we could make flow-sensitive analysis behave conservatively right by having Phi itself not be flow-sensitive: i.e. have Upsilon merge rather than setting.  I think you could do like a pseudo-flow-sensitivity.

Seems like while that's intellectually interesting, we probably just want to have AI do the more precise thing.

I think that we want to use the following strategy:

1) Phis have a secondary index in liveness analysis for their shadow value.
2) InPlaceAbstractState can have a second vector for shadow values.
3) BasicBlock can have a NodeProjection that wraps a Node* and adds a bit to say if this is the primary value or the shadow value.  Then, liveAtHead, valuesAtHead, and all of their friends don't have to change significantly.

[Filip Pizlo]

Created attachment 293741 [details]
it's a start

[Saam Barati]

Comment on attachment 293741 [details]
it's a start

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

> Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp:-124
> -            //    p: Phi()

Maybe this is too simplistic, but why can't we just solve the liveness bug by saying:

p: Phi() => defs p

n: Upsilon(@x, ^p) => defs n, uses x

Maybe I'm not completely understanding the implications of such a rule?

[Filip Pizlo]

(In reply to comment #11)
> Comment on attachment 293741 [details]
> it's a start
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=293741&action=review
> 
> > Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp:-124
> > -            //    p: Phi()
> 
> Maybe this is too simplistic, but why can't we just solve the liveness bug
> by saying:
> 
> p: Phi() => defs p
> 
> n: Upsilon(@x, ^p) => defs n, uses x
> 
> Maybe I'm not completely understanding the implications of such a rule?

I don't see how your rule works. Upsilon is void so I don't know what it means to def it. Also in your rule nobody uses the upsilon.

[Filip Pizlo]

Created attachment 293766 [details]
this might even work

[Filip Pizlo]

Created attachment 293769 [details]
even more things compile

[Filip Pizlo]

Created attachment 293770 [details]
it compiles!

[Filip Pizlo]

Created attachment 293773 [details]
it passes the test

It passes the test, but I don't know if it passes any other tests.  I'll find out soon.

[Filip Pizlo]

Created attachment 293783 [details]
the patch

I'm hoping that this is the one!

[WebKit Commit Bot]

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


ERROR: Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h:33:  Alphabetical sorting problem.  [build/include_order] [4]
Total errors found: 1 in 29 files


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

[Keith Miller]

> ERROR: Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h:33:  Alphabetical
> sorting problem.  [build/include_order] [4]
> Total errors found: 1 in 29 files
> 

You should probably fix this

[Filip Pizlo]

(In reply to comment #19)
> > ERROR: Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h:33:  Alphabetical
> > sorting problem.  [build/include_order] [4]
> > Total errors found: 1 in 29 files
> > 
> 
> You should probably fix this

Ooops.  Fixed.

[Keith Miller]

Looks like your patch might also be making EWS a little flakey... hard to tell though.

[Filip Pizlo]

(In reply to comment #21)
> Looks like your patch might also be making EWS a little flakey... hard to
> tell though.

EWS has been flakey for my last ~5 patches.

[Filip Pizlo]

Comment on attachment 293783 [details]
the patch

I'm seeing perf regressions.  Investigating.

[David I. Lehn]

How about updating the stress test code style and readability?  May also need a comment to note you need the --useConcurrentJIT=false --useFTLJIT=true flags for it to fail with just 10000 iterations.  Without those I need 500000 on my machine.  Might just want to set it at 500000+ always just to make sure.

var count = 0;
function foo() {
    var a=1, b=0;
    for (var i = 0; i < 2; ++i){
        [a, b] = [b, a];
        count++;
    }
    if (a !== 1 || b !== 0)
        throw "Error: bad result at swap count: " + count;
}
noInline(foo);

for (var k = 0; k < 10000; ++k)
    foo();

[Filip Pizlo]

(In reply to comment #24)
> How about updating the stress test code style and readability?  

We don't usually worry about the style of regression test code.

> May also
> need a comment to note you need the --useConcurrentJIT=false
> --useFTLJIT=true flags for it to fail with just 10000 iterations.  Without
> those I need 500000 on my machine.  Might just want to set it at 500000+
> always just to make sure.

This is an invariant of almost all of our optimizing compiler tests.  JSC developers already know this.

> 
> var count = 0;
> function foo() {
>     var a=1, b=0;
>     for (var i = 0; i < 2; ++i){
>         [a, b] = [b, a];
>         count++;
>     }
>     if (a !== 1 || b !== 0)
>         throw "Error: bad result at swap count: " + count;
> }
> noInline(foo);
> 
> for (var k = 0; k < 10000; ++k)
>     foo();

[Filip Pizlo]

The reason for the perf regressions is that I forgot to fix IntegerRangeOptimizationPhase.  That's also a flow-sensitive analysis.

[Filip Pizlo]

Created attachment 293818 [details]
possibly better patch

I think I figured out most of the remaining perf regression.  I will retest now.

[Filip Pizlo]

Created attachment 293829 [details]
the patch

[WebKit Commit Bot]

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


ERROR: Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp:1532:  When wrapping a line, only indent 4 spaces.  [whitespace/indent] [3]
Total errors found: 1 in 30 files


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

[Filip Pizlo]

This looks to be perf-neutral now.

[Keith Miller]

Comment on attachment 293829 [details]
the patch

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

I'll look further later. Something came up and I have to go.

> JSTests/stress/dfg-ssa-swap.js:4
> +    var a=1,b;for(i=0;i<2;++i){[a,b]=[b,a];c++}if(!a^b)throw c

why? my eyes...

> Source/JavaScriptCore/dfg/DFGCombinedLiveness.h:42
> +// values if you treat Upsilon as an opaque escape, and all of the clinets of CombinedLiveness do so.

clients.

[Saam Barati]

Comment on attachment 293829 [details]
the patch

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

> Source/JavaScriptCore/ChangeLog:28
> +        Unfortunately, DFG'a liveness analysis, abstract interpreter, and integer range optimization

DFG'a => DFG's

[Filip Pizlo]

Created attachment 293836 [details]
the patch

Fixed a bug in LivenessAnalysis.

[Filip Pizlo]

(In reply to comment #31)
> Comment on attachment 293829 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=293829&action=review
> 
> I'll look further later. Something came up and I have to go.
> 
> > JSTests/stress/dfg-ssa-swap.js:4
> > +    var a=1,b;for(i=0;i<2;++i){[a,b]=[b,a];c++}if(!a^b)throw c
> 
> why? my eyes...

Just copy-pasted the crashing code.

> 
> > Source/JavaScriptCore/dfg/DFGCombinedLiveness.h:42
> > +// values if you treat Upsilon as an opaque escape, and all of the clinets of CombinedLiveness do so.
> 
> clients.

Fixed!

[Filip Pizlo]

(In reply to comment #32)
> Comment on attachment 293829 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=293829&action=review
> 
> > Source/JavaScriptCore/ChangeLog:28
> > +        Unfortunately, DFG'a liveness analysis, abstract interpreter, and integer range optimization
> 
> DFG'a => DFG's

Fixed!

[Filip Pizlo]

Created attachment 293837 [details]
the patch

More fixes.

[WebKit Commit Bot]

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


ERROR: Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp:1532:  When wrapping a line, only indent 4 spaces.  [whitespace/indent] [3]
Total errors found: 1 in 30 files


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

[WebKit Commit Bot]

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


ERROR: Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp:1532:  When wrapping a line, only indent 4 spaces.  [whitespace/indent] [3]
Total errors found: 1 in 30 files


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

[Mark Lam]

Comment on attachment 293829 [details]
the patch

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

>>> JSTests/stress/dfg-ssa-swap.js:4
>>> +    var a=1,b;for(i=0;i<2;++i){[a,b]=[b,a];c++}if(!a^b)throw c
>> 
>> why? my eyes...
> 
> Just copy-pasted the crashing code.

Here's a version that won't hurt your eyes:

function foo() {
	var a = 1, b = 0;
	var i = 2;
	do {
		var c = a;
		a = b;
		b = c;
	} while (--i);
        if (!a)
	    throw "Error";
}

[David I. Lehn]

(In reply to comment #34)
> (In reply to comment #31)
> > Comment on attachment 293829 [details]
> > > JSTests/stress/dfg-ssa-swap.js:4
> > > +    var a=1,b;for(i=0;i<2;++i){[a,b]=[b,a];c++}if(!a^b)throw c
> > 
> > why? my eyes...
> 
> Just copy-pasted the crashing code.
> 

Sorry I posted the crazy code without a sane version!  Test code style may not matter but readability does.  Please consider using the comment #24 version or similar so other eyes stay safe.  Thanks.

[Saam Barati]

Comment on attachment 293837 [details]
the patch

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

r=me

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:2820
> +        forNode(node) = forNode(NodeFlowProjection(node, NodeFlowProjection::Shadow));

Nice

> Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp:87
> +                const Vector<unsigned, 0, UnsafeVectorOverflow, 1>&
> +                    liveAtHeadIndices = m_liveAtHead[blockIndex];

Style nit: I feel like this should go on one line.

> Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp:96
> +                const HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>&
> +                    liveAtTailIndices = m_liveAtTail[blockIndex];

Ditto

> Source/JavaScriptCore/dfg/DFGNodeFlowProjection.h:46
> +    {

Maybe worth an assert that kind()==Primary?

> Source/JavaScriptCore/dfg/DFGNodeFlowProjection.h:51
> +    {

Maybe worth an assert that kind()==kind?

[Filip Pizlo]

(In reply to comment #41)
> Comment on attachment 293837 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=293837&action=review
> 
> r=me
> 
> > Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:2820
> > +        forNode(node) = forNode(NodeFlowProjection(node, NodeFlowProjection::Shadow));
> 
> Nice
> 
> > Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp:87
> > +                const Vector<unsigned, 0, UnsafeVectorOverflow, 1>&
> > +                    liveAtHeadIndices = m_liveAtHead[blockIndex];
> 
> Style nit: I feel like this should go on one line.

OK.

> 
> > Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp:96
> > +                const HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>&
> > +                    liveAtTailIndices = m_liveAtTail[blockIndex];
> 
> Ditto

Fixed.

> 
> > Source/JavaScriptCore/dfg/DFGNodeFlowProjection.h:46
> > +    {
> 
> Maybe worth an assert that kind()==Primary?

Fixed!

> 
> > Source/JavaScriptCore/dfg/DFGNodeFlowProjection.h:51
> > +    {
> 
> Maybe worth an assert that kind()==kind?

Fixed!

[Filip Pizlo]

Landed in https://trac.webkit.org/changeset/208364

[WebKit Commit Bot]

Re-opened since this is blocked by bug 164402

[Filip Pizlo]

Created attachment 293861 [details]
patch for relanding

[WebKit Commit Bot]

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


ERROR: Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp:1532:  When wrapping a line, only indent 4 spaces.  [whitespace/indent] [3]
Total errors found: 1 in 30 files


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

[Filip Pizlo]

Landed in https://trac.webkit.org/changeset/208373