Bug 194475 - B3ReduceStrength::simplifyCFG() could do a lot more on each iteration
Summary: B3ReduceStrength::simplifyCFG() could do a lot more on each iteration
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: 194222
  Show dependency treegraph
 
Reported: 2019-02-09 14:34 PST by Robin Morisset
Modified: 2019-02-19 12:02 PST (History)
7 users (show)

See Also:


Attachments
Patch (2.44 KB, patch)
2019-02-09 15:31 PST, Robin Morisset
no flags Details | Formatted Diff | Diff
Patch (2.35 KB, patch)
2019-02-11 10:23 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-09 14:34:21 PST
B3ReduceStrength::simplifyCFG() does three optimizations (which I will call CFGa, CFGb and CFGc):
- CFGa makes any terminal that points to a block empty except for a jump point to that jump instead.
- CFGb transforms any branch or switch that point to a single block into a jump
- CFGc inlines any block with a single predecessor that ends in a jump into the end of that predecessor.

It currently is limited in the following way:
- CFGa and CFGc can only fire once per block per iteration
- CFGb can create jumps that would trigger CFGa, but they may not be seen until the next iteration

I intend to fix the first problem simply by looping in CFGa and CFGc, and to mitigate the second problem by the simple expedient of optimizing the blocks in post-order, so when CFGa runs most successor blocks will already have been optimized (including by CFGb).
Comment 1 Robin Morisset 2019-02-09 15:25:24 PST
Iterating on the blocks in postOrder reduces the number of iterations on average on JetStream2 from 3.35 to 3.24:

Iterations	Baseline	PostOrder	+Loop CFGa/c
1	        164	        165	        167
2	        554	        557	        551
3	        1690	        1931	        1936
4	        1626	        1556	        1545
5	        309	        159	        167
6	        46              24	        26
7	        9	        7	        7
8	        1	        0	        0
9	        0	        0	        0
10	        0	        0	        0

On the other hand while looping CFGa and CFGc is profitable in isolation (numbers not shown above), the last column shows it brings nothing on top of iterating on the blocks in post-order.
Comment 2 Robin Morisset 2019-02-09 15:31:38 PST
Created attachment 361614 [details]
Patch
Comment 3 Saam Barati 2019-02-10 19:35:04 PST
Comment on attachment 361614 [details]
Patch

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

> Source/JavaScriptCore/ChangeLog:8
> +        B3ReduceStrength::simplifyCFG() does three optimizations (which I will call CFGa, CFGb and CFGc):

nit: just labeling these "A"/"B"/"C" is easier for readability IMO

> Source/JavaScriptCore/ChangeLog:9
> +        - CFGa makes any terminal that points to a block empty except for a jump point to that jump instead.

This sentence confuses me. What's making a terminal "empty"?

> Source/JavaScriptCore/ChangeLog:11
> +        - CFGc inlines any block with a single predecessor that ends in a jump into the end of that predecessor.

Doesn't this require the predecessor to have a single successor, and the successor to have a single predecessor? If I have a single predecessor, but that predecessor has two successors, I can't do this transformation.
Comment 4 Robin Morisset 2019-02-11 10:23:48 PST
Created attachment 361691 [details]
Patch
Comment 5 Robin Morisset 2019-02-11 10:26:58 PST
Thanks for the review.

(In reply to Saam Barati from comment #3)
> Comment on attachment 361614 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=361614&action=review
> 
> > Source/JavaScriptCore/ChangeLog:8
> > +        B3ReduceStrength::simplifyCFG() does three optimizations (which I will call CFGa, CFGb and CFGc):
> 
> nit: just labeling these "A"/"B"/"C" is easier for readability IMO

Done.

> > Source/JavaScriptCore/ChangeLog:9
> > +        - CFGa makes any terminal that points to a block empty except for a jump point to that jump instead.
> 
> This sentence confuses me. What's making a terminal "empty"?

Sorry, I meant "a block that is empty". I fixed it, and tried to clarify the rest of the sentence.

> 
> > Source/JavaScriptCore/ChangeLog:11
> > +        - CFGc inlines any block with a single predecessor that ends in a jump into the end of that predecessor.
> 
> Doesn't this require the predecessor to have a single successor, and the
> successor to have a single predecessor? If I have a single predecessor, but
> that predecessor has two successors, I can't do this transformation.

I did not realize that my sentence was ambiguous: "that ends in a jump" was meant to apply to the predecessor (so that it indeed has a single successor). I've reworded it, please tell me if it is clearer.
Comment 6 Saam Barati 2019-02-19 11:33:57 PST
Comment on attachment 361691 [details]
Patch

r=me
Comment 7 WebKit Commit Bot 2019-02-19 12:01:47 PST
Comment on attachment 361691 [details]
Patch

Clearing flags on attachment: 361691

Committed r241768: <https://trac.webkit.org/changeset/241768>
Comment 8 WebKit Commit Bot 2019-02-19 12:01:49 PST
All reviewed patches have been landed.  Closing bug.
Comment 9 Radar WebKit Bug Importer 2019-02-19 12:02:42 PST
<rdar://problem/48209346>