Bug 194475 – B3ReduceStrength::simplifyCFG() could do a lot more on each iteration

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Robin Morisset]

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).

[Robin Morisset]

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.

[Robin Morisset]

Created attachment 361614 [details]
Patch

[Saam Barati]

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.

[Robin Morisset]

Created attachment 361691 [details]
Patch

[Robin Morisset]

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.

[Saam Barati]

Comment on attachment 361691 [details]
Patch

r=me

[WebKit Commit Bot]

Comment on attachment 361691 [details]
Patch

Clearing flags on attachment: 361691

Committed r241768: <https://trac.webkit.org/changeset/241768>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Radar WebKit Bug Importer]

<rdar://problem/48209346>