Bug 194252 - B3ReduceStrength: missing peephole optimizations for binary operations
Summary: B3ReduceStrength: missing peephole optimizations for binary operations
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Robin Morisset
URL:
Keywords: InRadar
Depends on:
Blocks: 154319
  Show dependency treegraph
 
Reported: 2019-02-04 16:27 PST by Robin Morisset
Modified: 2019-02-22 14:55 PST (History)
7 users (show)

See Also:


Attachments
WIP_missing_tests (11.31 KB, patch)
2019-02-05 16:14 PST, Robin Morisset
no flags Details | Formatted Diff | Diff
Patch (22.02 KB, patch)
2019-02-06 12:12 PST, Robin Morisset
saam: review+
Details | Formatted Diff | Diff
Patch (24.47 KB, patch)
2019-02-22 14:16 PST, Robin Morisset
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Robin Morisset 2019-02-04 16:27:07 PST
BitAnd is distributive over both BitOr and BitXor. So the following should all work:
- Op(BitAnd(x1, x2), BitAnd(x1, x3)) => BitAnd(x1, Op(x2, x3))
- Op(BitAnd(x2, x1), BitAnd(x1, x3)) => BitAnd(x1, Op(x2, x3))
- Op(BitAnd(x1, x2), BitAnd(x3, x1)) => BitAnd(x1, Op(x2, x3))
- Op(BitAnd(x2, x1), BitAnd(x3, x1)) => BitAnd(x1, Op(x2, x3))
for Op in {BitOr, BitXor}

Similarily, we can use De Morgan laws to float binary not (represented as BitXor(x, allOnes)) outwards, and eliminate as many as possible:
- BitAnd(BitXor(x1, allOnes), BitXor(x2, allOnes)) => BitXor(BitOr(x1, x2), allOnes)
- BitOr(BitXor(x1, allOnes), BitXor(x2, allOnes) => BitXor(BitAnd(x1, x2), allOnes)
- BitAnd(BitXor(x, allOnes), c) => BitXor(BitOr(x, ~c))
- BitOr(BitXor(x, allOnes), c) => BitXor(BitAnd(x, ~c))

Like all other peephole optimizations, the performance benefit is probably too small to measure, but it is very low-hanging fruit.
Comment 1 Robin Morisset 2019-02-05 16:14:27 PST
Created attachment 361240 [details]
WIP_missing_tests
Comment 2 EWS Watchlist 2019-02-05 16:23:18 PST
Attachment 361240 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:999:  Multi line control clauses should use braces.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1002:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1003:  Boolean expressions that span multiple lines should have their operators on the left side of the line instead of the right side.  [whitespace/operators] [4]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1003:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1005:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1006:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1016:  Multi line control clauses should use braces.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1019:  Boolean expressions that span multiple lines should have their operators on the left side of the line instead of the right side.  [whitespace/operators] [4]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1019:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1021:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1022:  Missing space after ,  [whitespace/comma] [3]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1076:  Multi line control clauses should use braces.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1079:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1080:  Boolean expressions that span multiple lines should have their operators on the left side of the line instead of the right side.  [whitespace/operators] [4]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1080:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1082:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1083:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1093:  Multi line control clauses should use braces.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1096:  Boolean expressions that span multiple lines should have their operators on the left side of the line instead of the right side.  [whitespace/operators] [4]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1096:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1098:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1099:  Missing space after ,  [whitespace/comma] [3]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:2256:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 23 in 3 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 3 Robin Morisset 2019-02-06 12:12:12 PST
Created attachment 361312 [details]
Patch
Comment 4 EWS Watchlist 2019-02-06 12:17:35 PST
Attachment 361312 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1002:  When wrapping a line, only indent 4 spaces.  [whitespace/indent] [3]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1019:  When wrapping a line, only indent 4 spaces.  [whitespace/indent] [3]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1079:  When wrapping a line, only indent 4 spaces.  [whitespace/indent] [3]
ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1096:  When wrapping a line, only indent 4 spaces.  [whitespace/indent] [3]
Total errors found: 4 in 3 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 5 Robin Morisset 2019-02-07 10:13:29 PST
(In reply to Build Bot from comment #4)
> Attachment 361312 [details] did not pass style-queue:
> 
> 
> ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1002:  When wrapping a
> line, only indent 4 spaces.  [whitespace/indent] [3]
> ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1019:  When wrapping a
> line, only indent 4 spaces.  [whitespace/indent] [3]
> ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1079:  When wrapping a
> line, only indent 4 spaces.  [whitespace/indent] [3]
> ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1096:  When wrapping a
> line, only indent 4 spaces.  [whitespace/indent] [3]
> Total errors found: 4 in 3 files
> 
> 
> If any of these errors are false positives, please file a bug against
> check-webkit-style.

I don't see a way to solve these without making the condition unreadable.
Does it bother anybody if I keep it as is?
Comment 6 Saam Barati 2019-02-17 23:42:23 PST
Comment on attachment 361312 [details]
Patch

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

r=me

> Source/JavaScriptCore/ChangeLog:47
> +        I did not list every single reordering of the arguments as the test part of this patch is already significantly longer than the useful code, and this combination should sample all the relevant paths.

That’s not our criteria for adding tests. Why don’t you just make it so your test doesn’t hard code lhs/rhs to generate all combinations?

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1002
> +                        && m_value->child(0)->child(1)->isInt(0xffffffffffffffff)

maybe use numeric_limits here?

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:2242
> +    // Turn any of these:

You should say for op Or/Xor
Comment 7 Robin Morisset 2019-02-22 14:15:41 PST
Thanks for the review.

> > Source/JavaScriptCore/ChangeLog:47
> > +        I did not list every single reordering of the arguments as the test part of this patch is already significantly longer than the useful code, and this combination should sample all the relevant paths.
> 
> That’s not our criteria for adding tests. Why don’t you just make it so your
> test doesn’t hard code lhs/rhs to generate all combinations?

Done.

> > Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1002
> > +                        && m_value->child(0)->child(1)->isInt(0xffffffffffffffff)
> 
> maybe use numeric_limits here?

Done.

> > Source/JavaScriptCore/b3/B3ReduceStrength.cpp:2242
> > +    // Turn any of these:
> 
> You should say for op Or/Xor

Fixed.
Comment 8 Robin Morisset 2019-02-22 14:16:23 PST
Created attachment 362764 [details]
Patch
Comment 9 WebKit Commit Bot 2019-02-22 14:54:28 PST
Comment on attachment 362764 [details]
Patch

Clearing flags on attachment: 362764

Committed r241964: <https://trac.webkit.org/changeset/241964>
Comment 10 WebKit Commit Bot 2019-02-22 14:54:30 PST
All reviewed patches have been landed.  Closing bug.
Comment 11 Radar WebKit Bug Importer 2019-02-22 14:55:34 PST
<rdar://problem/48325164>