[Webkit-unassigned] [Bug 239263] New: [JSC] Add block suffix merging in B3/Air

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=239263

            Bug ID: 239263
           Summary: [JSC] Add block suffix merging in B3/Air
           Product: WebKit
           Version: WebKit Nightly Build
          Hardware: Unspecified
                OS: Unspecified
            Status: NEW
          Severity: Normal
          Priority: P2
         Component: JavaScriptCore
          Assignee: webkit-unassigned at lists.webkit.org
          Reporter: rmorisset at apple.com

Currently we have a phase called B3DuplicateTail that duplicates code in cases where a small block has multiple predecessors.
It unlocks several optimizations opportunities at the code of some code bloat.

We should also have a phase doing the reverse, merging the shared suffixes of basic blocks that share the same successors.
This would grant some significant code size win from a quick look at the code that B3 generate. Possibly more importantly, it would allow us to make the heuristics of B3DuplicateTail a lot more aggressive without exploding code size. Our pipeline would be DuplicateTails -> optimizations that it may unlocks -> MergeTails -> Air

Here is a rough algorithm for tail merging that I thought of and that should work (but never got the time to implement):
- Sort all BBs
    First by their successors
    Then by their last opcode
    Then by their next-to-last opcode
    etc..
- Search for sequences of BBs in that sorted list that all share a tail of size at least N (some constant to be decided, e.g. 3 or 4).
    Try to merge them into a new BB, going backwards from the end, keeping track of mappings for each variable
    (e.g. if a BB has x3 <- x1 + x2, and another one has x5 <- x4 + x4 at the same position, remember that (x1, x2, x3) in the first one is mapped to (x4, x4, x5) in the second one.
    If you can merge a sufficiently big sequence, then make it a new BB, and add the necessary Phis/Upsilons to make it work.

-- 
You are receiving this mail because:
You are the assignee for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.webkit.org/pipermail/webkit-unassigned/attachments/20220413/b0a47f87/attachment.htm>