Bug 153200

Created attachment 269210 [details] it's a start

Created attachment 269229 [details] it is written

Created attachment 269232 [details] it specialized a check

Created attachment 269239 [details] starting to run real tests

Wow, this is actually a regression! The conditional move is profitable even though it looks super ugly.

I'm going to try this again.

Created attachment 269300 [details] more

Created attachment 269306 [details] even more Making it even more of a rampage by implementing SSA demotion and SSA fixup. 'Cause, you know, you can't really do taildup without those things.

Created attachment 269317 [details] it made deltablue faster in FTL B3 than FTL LLVM

Created attachment 269328 [details] and now with a changelog Still testing this.

Wow, this is kind of a big deal. Benchmark report for Octane on shakezilla (MacBookPro11,3). VMs tested: "B3ToT" at /Volumes/Data/quartary/OpenSource/WebKitBuild/Release/jsc (r195308) "NewB3" at /Volumes/Data/quinary/OpenSource/WebKitBuild/Release/jsc (r195308) Collected 6 samples per benchmark/VM, with 6 VM invocations per benchmark. Emitted a call to gc() between sample measurements. 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. B3ToT NewB3 encrypt 0.16682+-0.00770 0.16669+-0.00421 decrypt 2.87488+-0.06210 2.80440+-0.04123 might be 1.0251x faster deltablue x2 0.15536+-0.00832 ^ 0.13717+-0.00227 ^ definitely 1.1326x faster earley 0.27949+-0.00372 ? 0.28423+-0.00505 ? might be 1.0169x slower boyer 4.64508+-0.13043 4.63469+-0.17908 navier-stokes x2 4.81913+-0.02791 4.81354+-0.02552 raytrace x2 0.88046+-0.00661 ^ 0.86766+-0.00188 ^ definitely 1.0148x faster richards x2 0.09873+-0.00083 ^ 0.08979+-0.00096 ^ definitely 1.0996x faster splay x2 0.35560+-0.00450 0.35486+-0.00485 regexp x2 24.51355+-0.42627 ? 24.77818+-0.61266 ? might be 1.0108x slower pdfjs x2 37.48547+-0.14231 ? 37.60167+-0.15585 ? mandreel x2 48.95878+-0.33221 ^ 47.71011+-0.76387 ^ definitely 1.0262x faster gbemu x2 32.26218+-2.17414 31.54580+-0.23149 might be 1.0227x faster closure 0.57923+-0.00442 ? 0.58585+-0.00514 ? might be 1.0114x slower jquery 7.39526+-0.09223 7.36854+-0.03890 box2d x2 9.09089+-0.06643 9.07152+-0.07851 zlib x2 392.30406+-7.29783 ? 399.72401+-7.35874 ? might be 1.0189x slower typescript x2 667.76811+-18.52387 665.96224+-11.20068 <geometric> 5.50762+-0.03977 ^ 5.41406+-0.03001 ^ definitely 1.0173x faster

Comment on attachment 269328 [details] and now with a changelog It's ready for review.

Attachment 269328 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3Value.h:219: The parameter name "functor" adds no information, so it should be removed. [readability/parameter_name] [5] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9091: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9105: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9106: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9106: Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons. [readability/comparison_to_zero] [5] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9107: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9134: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9162: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9176: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9177: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9178: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9178: Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons. [readability/comparison_to_zero] [5] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9179: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9180: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/B3ValueKey.h:88: The parameter name "type" adds no information, so it should be removed. [readability/parameter_name] [5] ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1598: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/B3FixSSA.cpp:141: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/B3FixSSA.cpp:146: Place brace on its own line for function definitions. [whitespace/braces] [4] Total errors found: 18 in 66 files If any of these errors are false positives, please file a bug against check-webkit-style.

Created attachment 269332 [details] latest standings against LLVM

Comment on attachment 269328 [details] and now with a changelog Attachment 269328 [details] did not pass mac-debug-ews (mac): Output: http://webkit-queues.webkit.org/results/715396 New failing tests: js/regress/fold-multi-put-by-offset-to-replace-or-transition-put-by-offset.html js/regress/fold-multi-put-by-offset-to-put-by-offset.html js/regress/polymorphic-put-by-val-with-string.html js/regress/polymorphic-put-by-val-with-symbol.html js/regress/polymorphic-put-by-id.html js/regress/fold-multi-put-by-offset-to-poly-put-by-offset.html

Created attachment 269337 [details] Archive of layout-test-results from ews116 for mac-yosemite The attached test failures were seen while running run-webkit-tests on the mac-debug-ews. Bot: ews116 Port: mac-yosemite Platform: Mac OS X 10.10.5

Comment on attachment 269328 [details] and now with a changelog View in context: https://bugs.webkit.org/attachment.cgi?id=269328&action=review > Source/JavaScriptCore/dfg/DFGCommon.h:41 > +#define FTL_USES_B3 1 Please remove it before landing.

Regressions: Unexpected crashes (8) imported/w3c/web-platform-tests/streams-api/readable-streams/count-queuing-strategy-integration.html [ Crash ] js/regress/fold-multi-get-by-offset-to-get-by-offset.html [ Crash ] js/regress/fold-multi-put-by-offset-to-poly-put-by-offset.html [ Crash ] js/regress/fold-multi-put-by-offset-to-put-by-offset.html [ Crash ] js/regress/fold-multi-put-by-offset-to-replace-or-transition-put-by-offset.html [ Crash ] js/regress/polymorphic-put-by-id.html [ Crash ] js/regress/polymorphic-put-by-val-with-string.html [ Crash ] js/regress/polymorphic-put-by-val-with-symbol.html [ Crash ]

Comment on attachment 269328 [details] and now with a changelog View in context: https://bugs.webkit.org/attachment.cgi?id=269328&action=review > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:72 > + // and they much not have too many successors. must

Comment on attachment 269328 [details] and now with a changelog View in context: https://bugs.webkit.org/attachment.cgi?id=269328&action=review > Source/JavaScriptCore/b3/B3ArgumentRegValue.h:47 > + Value* cloneImpl() const override; Shouldn't all the cloneImpl() be private? > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:105 > + ControlValue* jump = block->last()->as<ControlValue>(); > + if (jump->opcode() != Jump) It would be more generic to test block->numSuccessors() == 1. We don't really care about the kind of ControlValue for changing the flow graph. > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:146 > + fixSSA(m_proc); If I am not mistaken: This is only called if (changed == true). If all the blocks in "candidates" are reached by a branch instead of a jump, their values would be demoted but never put back in SSA. > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:202 > + void foldPathConstants() Clever. Shouldn't it have its own phase? It seems unrelated to tail duplication. > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:221 > + if (override.block->predecessor(0) != from) That's odd. I would think this does not happen since the previous phase does resetReachability(). > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:235 > + if (value->index() >= 150) > + return; > + if (value->index() < 50) > + return; You are losing me there. Why does this depends on the index? > Source/JavaScriptCore/b3/B3FixSSA.cpp:248 > + mapping.clear(); Why not declare mapping in the loop? > Source/JavaScriptCore/b3/air/AirCode.h:317 > + void forAllTmps(Arg::Type type, const Callback& callback) const This does not seem used anywhere. > Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:104 > + if (m_unspillableTmps.contains(toSpill)) Are you sure that's not a regression? Adding to the m_spillWorklist is not uncommon. I fixed the same bug today, somewhat differently.

(In reply to comment #20) > > Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:104 > > + if (m_unspillableTmps.contains(toSpill)) > > Are you sure that's not a regression? Adding to the m_spillWorklist is not > uncommon. > > I fixed the same bug today, somewhat differently. That's probably okay actually. I think combine() is unlikely to modify the spill worklist since we use conservative heuristics.

(In reply to comment #20) > Comment on attachment 269328 [details] > and now with a changelog > > View in context: > https://bugs.webkit.org/attachment.cgi?id=269328&action=review > > > Source/JavaScriptCore/b3/B3ArgumentRegValue.h:47 > > + Value* cloneImpl() const override; > > Shouldn't all the cloneImpl() be private? Maybe? So far all of the methods in Value that are primarily for overriding in subclasses are protected. > > > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:105 > > + ControlValue* jump = block->last()->as<ControlValue>(); > > + if (jump->opcode() != Jump) > > It would be more generic to test block->numSuccessors() == 1. > We don't really care about the kind of ControlValue for changing the flow > graph. Currently it doesn't matter - the only other way to get one successor is to have a Switch with no cases and just a fall-through, but the solution there is to make strength-reduction fix those. As for future opcodes, testing for one successor is more generic but maybe less safe. Probably if we added a new opcode that had a single successor it would only be because that opcode did something special, which would make it illegal to do what this phase does. I mean, I guess we could test if numSuccessors is 1 and effects() is empty, but that feels like a bit much. > > > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:146 > > + fixSSA(m_proc); > > If I am not mistaken: > > This is only called if (changed == true). If all the blocks in "candidates" > are reached by a branch instead of a jump, their values would be demoted but > never put back in SSA. D'oh! Good catch. Obviously, after we call demoteValues() we need to commit to calling fixSSA(). > > > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:202 > > + void foldPathConstants() > > Clever. > > Shouldn't it have its own phase? It seems unrelated to tail duplication. That's a good idea. I'll do that. > > > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:221 > > + if (override.block->predecessor(0) != from) > > That's odd. I would think this does not happen since the previous phase does > resetReachability(). Yeah, this should be an assertion. > > > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:235 > > + if (value->index() >= 150) > > + return; > > + if (value->index() < 50) > > + return; > > You are losing me there. Why does this depends on the index? Ha! This was debug code. This machinery was failing some test. This would explain why my deltablue speed-up went down from 20% to 13%. ;-) I'll retest everything after removing this garbage. > > > Source/JavaScriptCore/b3/B3FixSSA.cpp:248 > > + mapping.clear(); > > Why not declare mapping in the loop? Because I'm fantasizing about a future utopia where HashMap::clear() doesn't always free the backing store. > > > Source/JavaScriptCore/b3/air/AirCode.h:317 > > + void forAllTmps(Arg::Type type, const Callback& callback) const > > This does not seem used anywhere. I'll kill it. > > > Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:104 > > + if (m_unspillableTmps.contains(toSpill)) > > Are you sure that's not a regression? Adding to the m_spillWorklist is not > uncommon. > > I fixed the same bug today, somewhat differently. I'll revert my changes to IRC so long as doing so doesn't break anything. This change did speed up testComplex with taildup.

(In reply to comment #22) > (In reply to comment #20) > > Comment on attachment 269328 [details] > > and now with a changelog > > > > View in context: > > https://bugs.webkit.org/attachment.cgi?id=269328&action=review > > > > > Source/JavaScriptCore/b3/B3ArgumentRegValue.h:47 > > > + Value* cloneImpl() const override; > > > > Shouldn't all the cloneImpl() be private? > > Maybe? So far all of the methods in Value that are primarily for overriding > in subclasses are protected. > > > > > > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:105 > > > + ControlValue* jump = block->last()->as<ControlValue>(); > > > + if (jump->opcode() != Jump) > > > > It would be more generic to test block->numSuccessors() == 1. > > We don't really care about the kind of ControlValue for changing the flow > > graph. > > Currently it doesn't matter - the only other way to get one successor is to > have a Switch with no cases and just a fall-through, but the solution there > is to make strength-reduction fix those. > > As for future opcodes, testing for one successor is more generic but maybe > less safe. Probably if we added a new opcode that had a single successor it > would only be because that opcode did something special, which would make it > illegal to do what this phase does. I mean, I guess we could test if > numSuccessors is 1 and effects() is empty, but that feels like a bit much. > > > > > > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:146 > > > + fixSSA(m_proc); > > > > If I am not mistaken: > > > > This is only called if (changed == true). If all the blocks in "candidates" > > are reached by a branch instead of a jump, their values would be demoted but > > never put back in SSA. > > D'oh! Good catch. Obviously, after we call demoteValues() we need to > commit to calling fixSSA(). Fixed. > > > > > > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:202 > > > + void foldPathConstants() > > > > Clever. > > > > Shouldn't it have its own phase? It seems unrelated to tail duplication. > > That's a good idea. I'll do that. Done. > > > > > > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:221 > > > + if (override.block->predecessor(0) != from) > > > > That's odd. I would think this does not happen since the previous phase does > > resetReachability(). > > Yeah, this should be an assertion. Fixed. > > > > > > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:235 > > > + if (value->index() >= 150) > > > + return; > > > + if (value->index() < 50) > > > + return; > > > > You are losing me there. Why does this depends on the index? > > Ha! This was debug code. This machinery was failing some test. This would > explain why my deltablue speed-up went down from 20% to 13%. ;-) > > I'll retest everything after removing this garbage. Removed. Haven't tested it yet, though. > > > > > > Source/JavaScriptCore/b3/B3FixSSA.cpp:248 > > > + mapping.clear(); > > > > Why not declare mapping in the loop? > > Because I'm fantasizing about a future utopia where HashMap::clear() doesn't > always free the backing store. > > > > > > Source/JavaScriptCore/b3/air/AirCode.h:317 > > > + void forAllTmps(Arg::Type type, const Callback& callback) const > > > > This does not seem used anywhere. > > I'll kill it. Dead. > > > > > > Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:104 > > > + if (m_unspillableTmps.contains(toSpill)) > > > > Are you sure that's not a regression? Adding to the m_spillWorklist is not > > uncommon. > > > > I fixed the same bug today, somewhat differently. > > I'll revert my changes to IRC so long as doing so doesn't break anything. > This change did speed up testComplex with taildup. Part of that was to actually fix a bug - selectSpill() would sometimes crash in score() if it was passed an unspillable. I'm fine with you basically rolling out my version of this and doing your change instead.

> > > > > > > > > Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:104 > > > > + if (m_unspillableTmps.contains(toSpill)) > > > > > > Are you sure that's not a regression? Adding to the m_spillWorklist is not > > > uncommon. > > > > > > I fixed the same bug today, somewhat differently. > > > > I'll revert my changes to IRC so long as doing so doesn't break anything. > > This change did speed up testComplex with taildup. > > Part of that was to actually fix a bug - selectSpill() would sometimes crash > in score() if it was passed an unspillable. I'm fine with you basically > rolling out my version of this and doing your change instead. I take this back. Yours already landed. I *think* that my solution is a bit better, see https://bugs.webkit.org/show_bug.cgi?id=153287#c9

(In reply to comment #24) > > > > > > > > > > > > Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp:104 > > > > > + if (m_unspillableTmps.contains(toSpill)) > > > > > > > > Are you sure that's not a regression? Adding to the m_spillWorklist is not > > > > uncommon. > > > > > > > > I fixed the same bug today, somewhat differently. > > > > > > I'll revert my changes to IRC so long as doing so doesn't break anything. > > > This change did speed up testComplex with taildup. > > > > Part of that was to actually fix a bug - selectSpill() would sometimes crash > > in score() if it was passed an unspillable. I'm fine with you basically > > rolling out my version of this and doing your change instead. > > I take this back. Yours already landed. I *think* that my solution is a > bit better, see https://bugs.webkit.org/show_bug.cgi?id=153287#c9 Okay with me if you want to revert my fix and land yours. I think your fix is cleaner. I am very very paranoid about the perf of IRC but I am not sure which version is best. My assumption was that selectSpill() is uncommon and take more cost if it make hot code simpler. Your version will make the spillWorklist smaller which may be more beneficial since most elements of spillWorklist are removed without ever going to selectSpill().

> > > > > > > > > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:235 > > > > + if (value->index() >= 150) > > > > + return; > > > > + if (value->index() < 50) > > > > + return; > > > > > > You are losing me there. Why does this depends on the index? > > > > Ha! This was debug code. This machinery was failing some test. This would > > explain why my deltablue speed-up went down from 20% to 13%. ;-) > > > > I'll retest everything after removing this garbage. > > Removed. Haven't tested it yet, though. Ha! It's an even bigger speed-up! 2.2% faster on Octane.

Created attachment 269412 [details] patch for landing

Attachment 269412 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3Value.h:219: The parameter name "functor" adds no information, so it should be removed. [readability/parameter_name] [5] ERROR: Source/JavaScriptCore/b3/B3ValueKey.h:88: The parameter name "type" adds no information, so it should be removed. [readability/parameter_name] [5] ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1598: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/B3FixSSA.cpp:141: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/B3FixSSA.cpp:146: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9091: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9105: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9106: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9106: Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons. [readability/comparison_to_zero] [5] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9107: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9134: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9162: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9176: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9177: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9178: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9178: Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons. [readability/comparison_to_zero] [5] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9179: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] ERROR: Source/JavaScriptCore/b3/testb3.cpp:9180: Consider using CHECK_EQ instead of CHECK(a == b) [readability/check] [2] Total errors found: 18 in 67 files If any of these errors are false positives, please file a bug against check-webkit-style.

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

> > > > > Source/JavaScriptCore/b3/B3DuplicateTails.cpp:235 > > > > > + if (value->index() >= 150) > > > > > + return; > > > > > + if (value->index() < 50) > > > > > + return; > > > > > > > > You are losing me there. Why does this depends on the index? > > > > > > Ha! This was debug code. This machinery was failing some test. This would > > > explain why my deltablue speed-up went down from 20% to 13%. ;-) > > > > > > I'll retest everything after removing this garbage. > > > > Removed. Haven't tested it yet, though. > > Ha! It's an even bigger speed-up! 2.2% faster on Octane. LOL, patch review for the win.