Bug 194081

(In reply to Robin Morisset from comment #0) > Currently, it is only using associativity for Add (and not even that > comprehensively if I read the code correctly). So for example (3+x) + (y+4) > is correctly reduced to x+y+7, but (3*x)*(y*7) is not reduced to x*y*12. > It should apply to Mul, BitOr and BitAnd. That’s surprising.

Created attachment 361843 [details] Patch

Attachment 361843 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:648: One line control clauses should not use braces. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:934: An else should appear on the same line as the preceding } [whitespace/newline] [4] ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1043: An else should appear on the same line as the preceding } [whitespace/newline] [4] ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1096: An else should appear on the same line as the preceding } [whitespace/newline] [4] ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:2182: Place brace on its own line for function definitions. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:2270: One line control clauses should not use braces. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:2273: Missing space before { [whitespace/braces] [5] ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:2278: One line control clauses should not use braces. [whitespace/braces] [4] Total errors found: 8 in 2 files If any of these errors are false positives, please file a bug against check-webkit-style.

Created attachment 361846 [details] Patch Just fixed the style nits.

Comment on attachment 361846 [details] Patch Can you add testb3 tests for at least some cases of this?

(In reply to Filip Pizlo from comment #5) > Comment on attachment 361846 [details] > Patch > > Can you add testb3 tests for at least some cases of this? I did not add tests because several of the already existing tests stress this code (and found bugs in earlier versions of this patch), but sure I can add a few more. I looked a the performance impact of this patch: https://perf-safari.apple.com/v3/#/analysis/task/6346 It is quite variable, with some large wins and losses, but the overall result is neutral. After thinking some more about it, I can see several issues with my approach: - The compile time can be quadratic in pathological cases, due to walking the graph forward, it would be a lot better to walk it backwards. - We can accidentally duplicate quite a lot of code as we don't have use counts available - We make the depth of the expression depth (and thus the latency to get its result) linear in its size instead of logarithmic. In other words, we completely sacrifice all ILP. These problems combined have convinced me that putting this in B3ReduceStrength was the wrong approach. I should have a separate pass that does nothing but these associativity reorderings, trying to produce perfectly balanced expression trees, quickly and without code duplication. The fact that even the currently flawed approach got some serious speed-ups is encouraging that this would be a win.

Created attachment 366286 [details] Patch New approach as a new pass, and with some extra tests. I'll provide perf results as soon as I have them.

Created attachment 366288 [details] Patch This time with a patch file that actually applies cleanly (made from svn diff and not git diff that seems to make patch files for new files that svn cannot read).

Attachment 366288 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:81: Missing space before ( in switch( [whitespace/parens] [5] ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:87: 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/B3OptimizeAssociativeExpressionTrees.cpp:131: Non-label code inside switch statements should be indented. [whitespace/indent] [4] ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:130: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3] ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:131: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3] ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:136: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3] ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:137: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3] ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:138: When wrapping a line, only indent 4 spaces. [whitespace/indent] [3] ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:139: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3] ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:140: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3] ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:141: When wrapping a line, only indent 4 spaces. [whitespace/indent] [3] ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:142: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3] ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:143: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3] ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:144: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3] ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:145: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3] ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:186: More than one command on the same line [whitespace/newline] [4] ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:214: Missing space around : in range-based for statement [whitespace/colon] [4] ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:217: Missing space around : in range-based for statement [whitespace/colon] [4] ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:248: Missing space around : in range-based for statement [whitespace/colon] [4] ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:267: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3] ERROR: Source/JavaScriptCore/b3/B3OptimizeAssociativeExpressionTrees.cpp:268: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3] Total errors found: 21 in 10 files If any of these errors are false positives, please file a bug against check-webkit-style.

Created attachment 366294 [details] Patch Fix style nits and missing import in testB3, that for some reason only the gtk build complained about.

The missing import was visibly not enough to appease the gtk-wk2 bot.. I will have to look deeper into what the linker error message means.

The results from the bots on MacBookPro just came in and they are bad (overall neutral, but all of the subtests with highly significant changes were regressed). I should understand why before trying to land this.

Comment on attachment 366294 [details] Patch I've got the performance numbers from this patch on JetStream2 and they're overall neutral. So I looked in more detail at when this optimization fires in a non-trivial way on all of JetStream2, and there are only a few subtests where it triggers: - Unipoker: balances some BitOr trees (insignificant slowdown) - tsf-wasm: balances a ton of BitOr trees (insignificant 1.4% speedup) - stanford-crypto-sha256 and stanford-crypto-pbkdf2: balances a few BitXor trees (insignificant slowdown on first iteration, strongly significant 2% speedup on average iteration and 3.5% speedup on worst iteration) - octane-zlib: balances a couple huge Add trees (no change) - ML: balances one small BitXor tree (no change) - mandreel: balances a couple (Add/BitAnd) small trees (0.7% insignificant slowdown on first iteration, strongly significant 1% improvement on average iteration and 2% on worst-case iteration) - HashSet-wasm: balances a few BitOr trees (insignificant speedup) - base64-SP: only balances one tiny BitXor tree (significant 2% slowdown on average iteration(?), insignificant change otherwise) So at best we get a couple percent on three benchmarks, and are otherwise neutral. Most likely we are just seeing noise even in these benchmarks where it balances trees. Surprisingly (to me) it does not find simplification opportunities beyond simple balancing. I thus put this patch out-of-review, as it does not seem obviously worth it at this point. I plan to revisit it once we have better value analysis in B3. It should enable significantly more simplifications, and make more large trees appear by turning CheckAdd/Sub/Mul into their non-checked variants.

(In reply to Robin Morisset from comment #13) > Comment on attachment 366294 [details] > Patch > > I've got the performance numbers from this patch on JetStream2 and they're > overall neutral. > So I looked in more detail at when this optimization fires in a non-trivial > way on all of JetStream2, and there are only a few subtests where it > triggers: > - Unipoker: balances some BitOr trees (insignificant slowdown) > - tsf-wasm: balances a ton of BitOr trees (insignificant 1.4% speedup) > - stanford-crypto-sha256 and stanford-crypto-pbkdf2: balances a few BitXor > trees (insignificant slowdown on first iteration, strongly significant 2% > speedup on average iteration and 3.5% speedup on worst iteration) > - octane-zlib: balances a couple huge Add trees (no change) > - ML: balances one small BitXor tree (no change) > - mandreel: balances a couple (Add/BitAnd) small trees (0.7% insignificant > slowdown on first iteration, strongly significant 1% improvement on average > iteration and 2% on worst-case iteration) > - HashSet-wasm: balances a few BitOr trees (insignificant speedup) > - base64-SP: only balances one tiny BitXor tree (significant 2% slowdown on > average iteration(?), insignificant change otherwise) > > So at best we get a couple percent on three benchmarks, and are otherwise > neutral. > Most likely we are just seeing noise even in these benchmarks where it > balances trees. Surprisingly (to me) it does not find simplification > opportunities beyond simple balancing. > > I thus put this patch out-of-review, as it does not seem obviously worth it > at this point. I plan to revisit it once we have better value analysis in > B3. It should enable significantly more simplifications, and make more large > trees appear by turning CheckAdd/Sub/Mul into their non-checked variants. It's worth the benefit if you make a microbenchmark and it speeds up a lot (>=20%, say) and the rest of these results hold.

Created attachment 366657 [details] Patch I wrote three microbenchmarks. None of them had any speedups. Upon investigating, I found that CSE tends to leave around dead values that are only eliminated much further (in the ReduceStrength just after my optimizations). This was a problem, as my optimization pass gives up when a node got a use count greater than one, and these dead values were using various subtrees. So I ripped out killDeadCode from B3ReduceStrength, made it its own pass and added it after CSE. This worked: 2 of the three microbenchmarks now show wins of respectively 16% and 42%. More surprisingly and very happily, this dead code elimination by itself was a massive win on a few other microbenchmarks: 50% on instanceof-always-hit-two and 16% on two variations of licm-dragons. I suspect it is by enabling B3TailDuplication to do its work, as it runs after CSE, and needs tiny blocks to be able to do anything. I sent this patch to the bots for more serious performance results on JetStream2, I will update this bug as soon as the results come in. Beyond that the only difference with the previous patch, is that my pass now skips trees of size 3, as B3ReduceStrength can deal with them. This should help avoid a possible hit to compile time.

Comment on attachment 366657 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=366657&action=review r=me with the one nit that EliminateDeadCode doesn't need a class. > Source/JavaScriptCore/b3/B3EliminateDeadCode.h:46 > +// This class and its run function are public, so that they can be called directly from B3ReduceStrength > +class EliminateDeadCode { > +public: > + EliminateDeadCode(Procedure& proc) > + : m_proc(proc) > + { > + } > + > + bool run(); > + > +private: > + Procedure& m_proc; > +}; Seems like this should just be a function - maybe bool eliminateDeadCodeImpl(Procedure&).

Created attachment 366686 [details] Patch Thanks for the review! I replaced the class EliminateDeadCode by a function eliminateDeadCodeImpl as suggested, and fixed a dataLog that I had forgotten from debugging.

Created attachment 366687 [details] Patch Now without OOPS in changelog.

Comment on attachment 366687 [details] Patch Clearing flags on attachment: 366687 Committed r243851: <https://trac.webkit.org/changeset/243851>

All reviewed patches have been landed. Closing bug.

<rdar://problem/49590146>

What was the result on JetStream 2?

(In reply to Saam Barati from comment #22) > What was the result on JetStream 2? All bots failed :-( I am trying again with different configurations/machines, maybe I'll be more lucky this time.