Bug 194252 – B3ReduceStrength: missing peephole optimizations for binary operations

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Robin Morisset]

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.

[Robin Morisset]

Created attachment 361240 [details]
WIP_missing_tests

[EWS Watchlist]

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.

[Robin Morisset]

Created attachment 361312 [details]
Patch

[EWS Watchlist]

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.

[Robin Morisset]

(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?

[Saam Barati]

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

[Robin Morisset]

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.

[Robin Morisset]

Created attachment 362764 [details]
Patch

[WebKit Commit Bot]

Comment on attachment 362764 [details]
Patch

Clearing flags on attachment: 362764

Committed r241964: <https://trac.webkit.org/changeset/241964>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Radar WebKit Bug Importer]

<rdar://problem/48325164>