Unsplit critical edges in codegen

RESOLVED FIXED in mozilla24



JavaScript Engine
5 years ago
5 years ago


(Reporter: sunfish, Unassigned)


(Blocks: 1 bug)

Dependency tree / graph

Firefox Tracking Flags

(Not tracked)



(1 attachment, 1 obsolete attachment)



5 years ago
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.


5 years ago
Blocks: 876057
Depends on: 881409

Comment 1

5 years ago
Created attachment 760541 [details] [diff] [review]
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.
Attachment #760541 - Flags: review?(bhackett1024)
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.
Attachment #760541 - Flags: review?(bhackett1024) → review+

Comment 3

5 years ago
Created attachment 762887 [details] [diff] [review]
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.
Attachment #760541 - Attachment is obsolete: true
Attachment #762887 - Flags: review?(bhackett1024)
Attachment #762887 - Flags: review?(bhackett1024) → review+
Last Resolved: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla24

Comment 6

5 years ago
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.
You need to log in before you can comment on or make changes to this bug.