Closed Bug 678273 Opened 13 years ago Closed 13 years ago

IonMonkey: Eliminate unused phi nodes.

Categories

(Core :: JavaScript Engine, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: sstangl, Assigned: dvander)

Details

Attachments

(3 files)

This bug is a result of discussion in Bug 678113, which implements dead code elimination. cdleary pointed out a case where we construct an MPhi even when its value is disregarded by the bytecode.

For purposes of this bug, a phi is 'unused' if it exists in the MIR, but its value is discarded by the bytecode (not just by the SSA-form!). Since the phi is unused, we want to eliminate it from the MIR.

If you currently ask an unused phi how many uses it has, it will tell you 1, referring to a snapshot that keeps it alive. Note that the JSON output will tell you that the phi has 0 uses, since it only iterates over MDefinitions.

So we need to detect unused phi nodes. The idea is simple: after SSA translation, before optimization, walk over the MPhis and for each, check the number of uses that are not snapshots. If none, then the bytecode does not need the value, so remove the phi from the graph and from snapshots.
This could be interleaved with TypeAnalysis (which also removes copies), and does not apply just to phis but to any local variable, though it seems more likely to have unused phis due to JavaScript's scoping rules.

(In reply to Sean Stangl from bug 678113 comment #9)
> Liveness information on the bytecode is implicit in the unoptimized SSA
> form. 
>  ...
> Snapshots not being minimal is a separate issue, as far as I can tell.

Yes, the liveness information is implicit in our original SSA, but using it would solve both problems: eliminating unnecessary snapshot uses would make use counts drop to 0. Once we're running major benchmarks we should see if removing these useless stores is worth it, and if so, whether we should do the simple or advanced thing.
Whelp, removing these stores is absolutely worth it. A simple benchmark that has variables scoped inside a loop has tons of useless stack->stack moves. A few options:

(1) Perform a DCE pass that treats MResumePoint-only uses as dead. This works provided the SSA precisely captures the original bytecode, so before any control-flow or code elimination. This would eliminate phis and variables that are never read.

(2) Perform (1) only on phis, which would be a much faster algorithm and catch the really bad common cases.

(3) Use bytecode-level liveness information to precisely eliminate snapshot uses.

Brian, is (3) easily available from type inference?
Assignee: general → dvander
Status: NEW → ASSIGNED
(In reply to David Anderson [:dvander] from comment #2)
> Whelp, removing these stores is absolutely worth it. A simple benchmark that
> has variables scoped inside a loop has tons of useless stack->stack moves. A
> few options:
> 
> (1) Perform a DCE pass that treats MResumePoint-only uses as dead. This
> works provided the SSA precisely captures the original bytecode, so before
> any control-flow or code elimination. This would eliminate phis and
> variables that are never read.
> 
> (2) Perform (1) only on phis, which would be a much faster algorithm and
> catch the really bad common cases.
> 
> (3) Use bytecode-level liveness information to precisely eliminate snapshot
> uses.
> 
> Brian, is (3) easily available from type inference?

(3) is available from the lifetime analysis used to support LSRA in JM+TI (see ScriptAnalysis::liveness), but TI does not need it and I'm hoping it can be removed once JM+TI becomes obsolete.  Removing stack stores of dead variables is very important for good loop perf.
Attached patch patchSplinter Review
This patch eliminates phis which cannot be observed by the interpreter. The snapshot uses are left in-place, and are just ignored when traversing snapshots.

I ran into a few typos in the greedy allocator, as well as a very nasty bug in the stack slot allocator.

On a test case derived from a Mandelbrot benchmark:
 --ion -n (before): 44ms
 --ion -n (after):  18ms
 crankshaft:        17ms
 -m -n:             33ms
Attachment #559678 - Flags: review?(sstangl)
Can you paste the testcase you used?
Attached file benchmark
This was it, though the loop counts are different now
Comment on attachment 559678 [details] [diff] [review]
patch

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

::: js/src/ion/C1Spewer.cpp
@@ +210,5 @@
>          fprintf(fp, "%d ", i);
> +        if (ins->isUnused())
> +            fprintf(fp, "unused");
> +        else
> +            ins->printName(fp);

JSONSpewer.cpp could use the equivalent change.

::: js/src/ion/MIR.h
@@ +90,5 @@
>      _(Idempotent)    /* The instruction has no side-effects. */                 \
>      _(NeverHoisted)  /* Don't hoist, even if loop invariant */                  \
> +    _(Lowered)       /* (Debug only) has a virtual register */                  \
> +                                                                                \
> +    /* The instruction has been marked dead for lazy removal from resume

This seems very specific. Could this flag be hijacked for regular DCE as well?

::: js/src/ion/shared/CodeGenerator-shared.cpp
@@ +103,5 @@
>          MDefinition *mir = snapshot->mir()->getOperand(i);
>  
> +        MIRType type = mir->isUnused()
> +                       ? MIRType_Undefined
> +                       : mir->type();

Does mir->isUnused() imply that a later optimization (say, GVN) can't reuse this value after the isUnused() flag has been set?
Attachment #559678 - Flags: review?(sstangl) → review+
JSON Spewer doesn't appear to read entry snapshots. The Unused flag implies that the node does not exist. It's not anywhere in the graph. We just didn't sweep them from snapshots aggressively because snapshots are only lowered on demand.

http://hg.mozilla.org/projects/ionmonkey/rev/c11c77e73480
Status: ASSIGNED → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.