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.
<rdar://problem/29057323>
I'm investigating the issue.
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.
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.
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.
(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.
(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.
(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.
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.
Created attachment 293741 [details] it's a start
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?
(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.
Created attachment 293766 [details] this might even work
Created attachment 293769 [details] even more things compile
Created attachment 293770 [details] it compiles!
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.
Created attachment 293783 [details] the patch I'm hoping that this is the one!
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.
> 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
(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.
Looks like your patch might also be making EWS a little flakey... hard to tell though.
(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.
Comment on attachment 293783 [details] the patch I'm seeing perf regressions. Investigating.
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();
(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();
The reason for the perf regressions is that I forgot to fix IntegerRangeOptimizationPhase. That's also a flow-sensitive analysis.
Created attachment 293818 [details] possibly better patch I think I figured out most of the remaining perf regression. I will retest now.
Created attachment 293829 [details] the patch
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.
This looks to be perf-neutral now.
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.
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
Created attachment 293836 [details] the patch Fixed a bug in LivenessAnalysis.
(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!
(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!
Created attachment 293837 [details] the patch More fixes.
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.
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.
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"; }
(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.
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?
(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!
Landed in https://trac.webkit.org/changeset/208364
Re-opened since this is blocked by bug 164402
Created attachment 293861 [details] patch for relanding
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.
Landed in https://trac.webkit.org/changeset/208373