Bug 194252

Summary: B3ReduceStrength: missing peephole optimizations for binary operations
Product: WebKit Reporter: Robin Morisset <rmorisset>
Component: JavaScriptCoreAssignee: Robin Morisset <rmorisset>
Status: RESOLVED FIXED    
Severity: Normal CC: commit-queue, ews-watchlist, keith_miller, mark.lam, msaboff, saam, webkit-bug-importer
Priority: P2 Keywords: InRadar
Version: WebKit Nightly Build   
Hardware: Unspecified   
OS: Unspecified   
Bug Depends on:    
Bug Blocks: 154319    
Attachments:
Description Flags
WIP_missing_tests
none
Patch
saam: review+
Patch none

Robin Morisset
Reported 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.
Attachments
WIP_missing_tests (11.31 KB, patch)
2019-02-05 16:14 PST, Robin Morisset 		no flags
DetailsFormatted DiffDiff
Patch (22.02 KB, patch)
2019-02-06 12:12 PST, Robin Morisset 		saam: review+
DetailsFormatted DiffDiff
Patch (24.47 KB, patch)
2019-02-22 14:16 PST, Robin Morisset 		no flags
DetailsFormatted DiffDiff
Show Obsolete (2) View All Add attachment proposed patch, testcase, etc.
Robin Morisset
Comment 1 2019-02-05 16:14:27 PST
Created attachment 361240 [details] WIP_missing_tests
EWS Watchlist
Comment 2 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.
Robin Morisset
Comment 3 2019-02-06 12:12:12 PST
Created attachment 361312 [details] Patch
EWS Watchlist
Comment 4 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.
Robin Morisset
Comment 5 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?
Saam Barati
Comment 6 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
Robin Morisset
Comment 7 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.
Robin Morisset
Comment 8 2019-02-22 14:16:23 PST
Created attachment 362764 [details] Patch
WebKit Commit Bot
Comment 9 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>
WebKit Commit Bot
Comment 10 2019-02-22 14:54:30 PST
All reviewed patches have been landed. Closing bug.
Radar WebKit Bug Importer
Comment 11 2019-02-22 14:55:34 PST
<rdar://problem/48325164>
Note You need to log in before you can comment on or make changes to this bug.