Open Bug 1959091 Opened 1 year ago Updated 5 months ago

MIR loop unroller: generalise AddClosingPhisForLoop to handle loops with multiple exits.

Categories

(Core :: JavaScript: WebAssembly, enhancement, P3)

enhancement

Tracking

()

People

(Reporter: jseward, Unassigned)

References

(Blocks 1 open bug)

Details

The MIR loop unroller in bug 1950284 can unroll loops with multiple exits but
no exiting values, or loops with a single exit and any number of exiting
values. But it can't handle loops that have both multiple exits and exiting
values. In testing, that shows we skip perhaps 15%-20% of loops that could
otherwise have been unrolled.

This is because of limitations in AddClosingPhisForLoop, which transforms
selected loops into so-called Loop-Closed SSA form (LCSSA). If a loop has a
single exit then transforming in into LCSSA form is simple, and that is the
case that AddClosingPhisForLoop currently handles.

Dealing with multiple exits would require generalising the routine, to compute
iterated dominance frontiers for the exiting values, and placing phis
accordingly. It should be possible to do this without changing the signature
of AddClosingPhisForLoop.

Severity: -- → N/A

It looks like it would be possible to generate these closing phis, for the
general case, using a two-step approach:

(1) given the set T of exit target blocks of the loop, compute the iterated
dominance frontier for T using the method described in [1]. This has the
critical advantage, compared to other schemes for computing dominance
frontiers, that it does not require computing those frontiers for the
entire function merely in order to find the dominance frontiers of some
(presumably small) subset of nodes in the graph. In other words, it's
big-O feasible for us, whereas computing frontiers for the whole function
just to support unrolling of a single loop isn't.

(2) For each exiting value for which we need to add phi nodes, visit all uses
of that value. This is easy since each SSA value has a list of its uses.
Then (and this is the bit I am vague about), at each use, walk back up the
dominator tree from the use-point node. If we arrive at a node in the
dominance frontier as computed by (1), we need to insert a phi node there.
That in turn generates more uses which are effectively in the predecessors
of said node (because they are phi-arg uses), and we need to use the same
walk-up-the-dom-tree procedure for these too.

That all said .. it sounds like a lot of complexity to facilitate unrolling the
perhaps 20% of loops that we currently cannot.

[1] "A Linear Time Algorithm for Placing phi-Nodes" Vugranam C. Sreedhar and
Guang R. Gao, School of Computer Science, McGill University, Montreal.
(It's an exposition of their D-J-Tree idea)

https://bernsteinbear.com/assets/img/sreedhar-ssa.pdf
See Also: → 2045494
You need to log in before you can comment on or make changes to this bug.