Bug 301564 – Improve block order in B3/Air

• Component: JavaScriptCore
• Status: RESOLVED FIXED

I was actually looking into loop unrolling, but I noticed somebody else already looking into it.
Though while looking at the Air CFG I often saw suboptimal block order.
Mostly because of the way the code iterates through the worklist.

We would always take the last (available) pushed successor.
This is good if a successor was pushed, since that would continue the chain (of non-jumps).
But when there are no successors, there are better solutions, like taking the first pushed successor.

This is better since:
1) Locality: we are iterating blocks "closer" to their predecessors and have smaller jumps.
2) Earlier blocks can still have longer chains. Instead of iterating successors where the predecessors might still not have been iterated. We will first iterate the predecessor, before a potential successor.
3) Keep closer to the original order of the blocks.

I have 2 improvements:
- Part 1 - The improvement I described before
- Part 2 - Detection of easy block structures and optimally layout them

I see the following numbers on JetStream:
Part 1 - 2% more fallthrough + 4% decrease in jump lengths
Part 2 - 2.7% more fallthrough + 11% decrease in jump lengths

Combined this gives:
4.6% more fallthrough + 14% decrease in jump lengths


It is possible to improve this even more if:
1) There are actual block frequencies, since now we assume all jumps are taken equally. We only keep track of loopdepth.
2) Use a dominator tree, which will be more compute intensive.

Pull request: https://github.com/WebKit/WebKit/pull/53081

[Radar WebKit Bug Importer]

<rdar://problem/164000333>

[EWS]

Committed 302875@main (01f7679257a5): <https://commits.webkit.org/302875@main>

Reviewed commits have been landed. Closing PR #53081 and removing active labels.