| Summary: | [JSC] Add block suffix merging in B3/Air | ||
|---|---|---|---|
| Product: | WebKit | Reporter: | Robin Morisset <rmorisset> |
| Component: | JavaScriptCore | Assignee: | Nobody <webkit-unassigned> |
| Status: | NEW --- | ||
| Severity: | Normal | CC: | webkit-bug-importer |
| Priority: | P2 | Keywords: | InRadar |
| Version: | WebKit Nightly Build | ||
| Hardware: | Unspecified | ||
| OS: | Unspecified | ||
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.