881412 - Unsplit critical edges in codegen

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Dan Gohman [:sunfish]]

The Ion optimizer splits all critical edges, however currently such edges always remain split, so common loops such as the one in bug 876057 end up with an extra branch on their backedge.

Comment 1

[Dan Gohman [:sunfish]]

Attachment: a proposed fix

This patch adds a new pass which eliminates basic blocks containing nothing but unconditional branches. Note that this can re-introduce critical edges, so the pass runs very late, after register allocation, as many optimizations and register allocation assume that all critical edges are split.

It also introduces a new abstraction for working with successors of LInstructions in a generic way.

I'm quite open to organizing the code differently or taking a different approach, if you prefer.

Comment 2

[Brian Hackett [Laid off!]]

Comment on attachment 760541 [details] [diff] [review]
a proposed fix

Review of attachment 760541 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/ion/Ion.cpp
@@ +1166,5 @@
> +// often created by optimizer, which splits all critical edges. If these
> +// splits end up being unused after optimization and register allocation,
> +// fold them back away to avoid unnecessary branching.
> +static bool
> +UnsplitEdges(LIRGraph *lir) {

This pass should go in IonAnalysis.cpp I think, which is where the original critical edge splitting code is.  Ion.cpp is more for structural code and not analysis passes.  Also, the { here should be on a new line.

@@ +1180,5 @@
> +        // current as we modify the LIR, so only proceed if the MIR is simple.
> +        if (mirBlock->numPredecessors() == 0 || mirBlock->numSuccessors() != 1 ||
> +            !mirBlock->phisEmpty() || !mirBlock->resumePointsEmpty() ||
> +            !mirBlock->begin()->isGoto())
> +            continue;

Nit: multiline conditionals should read as:

if (...
    ...)
{
    ...
}

@@ +1205,5 @@
> +                    mirPred->replaceSuccessor(k, target);
> +                    if (!target->addPredecessorWithoutPhis(mirPred))
> +                        return false;
> +                    for (MPhiIterator phi = target->phisBegin(); phi != target->phisEnd(); ++phi)
> +                        if (!phi->addInputSlow(phi->getOperand(phi->numOperands() - 1)))

This looks strange, shouldn't the new input for the phi be mirPred->getSlot(phi->slot())?

It seems unfortunate to clean up the phis to be coherent when they won't be used anymore, as this might have a significant cost on large graphs with many variables.  Instead, maybe add some #ifdef DEBUG code in this method to poison the contents of all phis in the MIR graph?

@@ +1211,5 @@
> +                }
> +            }
> +
> +            LInstruction *predTerm = *mirPred->lir()->rbegin();
> +            for (size_t k = 0; k < predTerm->numSuccessors(); k++)

Nit: This 'for' loop should have {}

@@ +1222,5 @@
> +        lir->removeBlock(i);
> +        lir->mir().removeBlock(mirBlock);
> +        --i;
> +
> +        AssertBasicGraphCoherency(lir->mir());

This will be called afterwards by GenerateLIR, so I think this call should be removed to avoid pathological debug build behavior on large graphs.

Comment 3

[Dan Gohman [:sunfish]]

Attachment: an updated patch, following review feedback

This updated patch addresses your comments.

Instead of poisoning the phis, this patch just deletes them. The problem with poisoning them was that subsequent code gets confused if they are present but not in sync with the CFG. I'm not entirely happy with how this leaves the MIR somewhat inconsistent, but it's difficult to avoid since the MIR is the only level which carries the CFG edges, and that's what we're editing.

Comment 4

[Dan Gohman [:sunfish]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/ce49a3bc870c

Comment 5

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/ce49a3bc870c

Comment 6

[Alon Zakai (:azakai)]

Looks good! On awfy I see 10% win in memops, 8% in life, 5% in fannkuch, and 2% in fasta and some of the larger benchmarks.