Bug 239263 – [JSC] Add block suffix merging in B3/Air

• Component: JavaScriptCore
• Status: NEW

[Robin Morisset]

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.

[Radar WebKit Bug Importer]

<rdar://problem/91994834>