Closed Bug 678113 Opened 13 years ago Closed 13 years ago

IonMonkey: Implement Dead Code Elimination

Categories

(Core :: JavaScript Engine, defect)

x86_64
Linux
defect
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: sstangl, Unassigned)

Details

Attachments

(2 files)

The attached patch implements DCE by just blazing over unused instructions. This does not eliminate unused control flow or empty blocks, since those changes are significantly more invasive.

Unfortunately, we can't eliminate useless MPhi instructions -- it turns out that we still need their values around in case of bailout back to the interpreter. Fun fun fun.

The patch produces correct code with the GreedyAllocator, but fails with the standard live->empty() assertion with the LSRA. adrake: any idea why removing an unused instruction might have this effect?
Attached file Test case via rpearl.
Test case I've been working with. If you run it through iongraph, you should see DCE eliminating an instruction that has zero uses after GVN.
(In reply to Sean Stangl from comment #0)
> Unfortunately, we can't eliminate useless MPhi instructions -- it turns out
> that we still need their values around in case of bailout back to the
> interpreter.

I don't get it. Shouldn't any phi with such a requirement be used by a snapshot instruction?
(In reply to Chris Leary [:cdleary] from comment #2)
> I don't get it. Shouldn't any phi with such a requirement be used by a
> snapshot instruction?

Yeah. The snapshot tells the bailout code where the phi's value is stored -- memory, register, constant. But if we eliminated the phi, there is no location from which to reify the value, so it can't be passed to the interpreter. But the interpreter needs the value to continue executing from that point.
(In reply to Sean Stangl from comment #0)
> The patch produces correct code with the GreedyAllocator, but fails with the
> standard live->empty() assertion with the LSRA. adrake: any idea why
> removing an unused instruction might have this effect?

It triggers bug 678072. With the patch from that applied, it appears to do the right thing.
(In reply to Sean Stangl from comment #3)
> Yeah. The snapshot tells the bailout code where the phi's value is stored --
> memory, register, constant. But if we eliminated the phi, there is no
> location from which to reify the value, so it can't be passed to the
> interpreter. But the interpreter needs the value to continue executing from
> that point.

Chris and I talked a bit about this last night and it seems like, for this case, we would want a bytecode-level liveness analysis. The question we want to answer is: "Could this value in the snapshot be read at any point in the interpreter past this snapshot?" If the answer is no we can remove the def and replace it with undefined, saving ourselves a store.

LSRA's liveness pass might be able to give us that information, but we don't know how much this hurts generated code yet.
Also, Chris pointed out that right now, it would be safe to remove the phi anyway (replacing its entry in snapshots with undefined). This is because we capture the whole CFG of the method so if nothing uses a value we know it's totally dead.

But this wouldn't help us for the case where, for example:

   var a = ... something ....
   print(a);
    ....
   return 5;

|a| is held live by snapshots until the return but it's effectively dead after the print.
(In reply to David Anderson [:dvander] from comment #5) 
> Chris and I talked a bit about this last night and it seems like, for this
> case, we would want a bytecode-level liveness analysis.

No need for another pass: we already have that information! Just inspect the MPhi's use chain after SSA generation, before any optimizations are performed on the MIR.

In the case of the above testcase, it is used by a bitand (id# 36) that GVN eliminates. So we have to pass some value for the phi back to the interpreter.
Interesting, the point about GVN is really good. If we're eliminating pieces of the method then we lose information, even if it's not just control flow. I think that does work for eliminating totally dead values, but we'd still need liveness information for the full win.
Liveness information on the bytecode is implicit in the unoptimized SSA form. The problem is just that *everything* is used by the interpreter: we would not have emitted the phi unless it were required by the bytecode (and even if useless phis exist upon bytecode -> SSA conversion, then the problem is with the IonBuilder, and is not indicative of another optimization pass being required). The phi's value may not be necessary for all snapshots after its definition, but it will be required for at least one, and therefore cannot be eliminated.

Snapshots not being minimal is a separate issue, as far as I can tell.
Comment on attachment 552283 [details] [diff] [review]
Implements DCE, but dies with LSRA. (v1)

Requesting review of unused instruction elimination. If we're going to try to do phi elimination, that should be a different bug.
Attachment #552283 - Flags: review?(dvander)
Opened a new bug for elimination of unused phi nodes: Bug 678273.
I am still confused by the distinction for phis. As you say, the point of snapshots is to hold their uses live. If a phi is required in order to bail out, it should be held live by a snapshot--it will NOT be dead code, since it won't have zero uses.

Note that the UseDefIterator is used as a convenience method, because otherwise a lot of code would iterate through all uses, and check whether the use actually defines a value. Checking whether an instruction is dead should check whether the list of all uses--including those in snapshots--is empty. There are not two separate notions of "use" at work here.

So, while the issue of making snapshots minimal is separate, I don't know why the issue of not iterating through phi nodes is. Even if every phi is used in a snapshot and so thus can't be dead-code eliminated at this point, the issue is with snapshots, not with DCE itself. DCE should still iterate over phi nodes as well; for this particular pass there shouldn't be a distinction.
(In reply to Ryan Pearl [:rpearl] from comment #12)
> So, while the issue of making snapshots minimal is separate, I don't know
> why the issue of not iterating through phi nodes is. 

I agree - solving the snapshot issue automatically solves the DCE issue. The question is probably just which has more impact. Snapshots create useless stores and dead phis/locals create useless moves. Both can cause dead operations to be held live but purely dead user-code seems unimportant unless your benchmark is math-cordic.
(In reply to Ryan Pearl [:rpearl] from comment #12)
Yes, what you're saying is correct. As it stands now, though, we can't actually get a phi with a use count of 0. So although we could add the code to knock off unused phis, it would never actually do anything until we solve the problem with snapshots. I asked dvander, and he said he would rather have a patch without code that can't currently do anything.

It's really trivial to implement phi removal, though. We can do it in about 20 seconds once snapshotting is fixed.
Comment on attachment 552283 [details] [diff] [review]
Implements DCE, but dies with LSRA. (v1)

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

::: js/src/ion/IonAnalysis.cpp
@@ +81,5 @@
> +{
> +    // Traverse in postorder so that we hit uses before definitions.
> +    // Traverse instruction list backwards for the same reason.
> +    for (PostorderIterator block = graph.poBegin();
> +         block != graph.poEnd(); block++) {

Fits on one line

@@ +85,5 @@
> +         block != graph.poEnd(); block++) {
> +
> +        // Remove unused instructions.
> +        for (MInstructionReverseIterator inst = block->rbegin();
> +             inst != block->rend(); ) {

Ditto

@@ +88,5 @@
> +        for (MInstructionReverseIterator inst = block->rbegin();
> +             inst != block->rend(); ) {
> +            if (inst->isIdempotent() && !inst->hasUses())
> +                inst = block->removeAt(inst);
> +            }

Accidental }?

@@ +94,5 @@
> +                inst++;
> +        }
> +
> +        // Unused phi nodes cannot be eliminated, since their values are still
> +        // needed to recreate state in case of bailout to interpreter.

This is part of a larger problem, maybe we should cite the bug here or something.
Attachment #552283 - Flags: review?(dvander) → review+
http://hg.mozilla.org/projects/ionmonkey/rev/a0f88cdad5c9
Status: NEW → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.