Remove dead phis as soon as they are discovered.

Remove dead phis as soon as they are discovered.

Previously we removed dead phis late, in the register allocator.  This
change removes them as soon as they are discovered to be dead and packs the
phi array to squeeze out NULLs.  This speeds iteration but doesn't save
space because the phi array is zone-allocated.

The PhiIterator is used everywhere to iterate phis except a few places that
need to know the phi index (e.g., SSA construction, phi elimination).

R=vegorov@google.com

Committed: https://code.google.com/p/dart/source/detail?r=19206

[Vyacheslav Egorov (Google), 2013-02-27 21:53:02]

lgtm

https://codereview.chromium.org/12340108/diff/1/runtime/vm/flow_graph_allocat...
File runtime/vm/flow_graph_allocator.cc (left):

https://codereview.chromium.org/12340108/diff/1/runtime/vm/flow_graph_allocat...
runtime/vm/flow_graph_allocator.cc:112:
it.SetCurrentValue(push_argument->value()->Copy());
What happened to this special PushArgument handling? Are we relying on the fact
that push argument removal does this substitution? Can we assert that
environment contains no PushArguments.

https://codereview.chromium.org/12340108/diff/1/runtime/vm/flow_graph_optimiz...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/12340108/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:4281: if (FLAG_remove_redundant_phis &&
(live_count == 1)) {
Do we have any code that kills truly redundant phis of form phi(x,x)?

(not related to this CL but might be a good follow up)

[Kevin Millikin (Google), 2013-02-28 08:12:02]

https://codereview.chromium.org/12340108/diff/1/runtime/vm/flow_graph_allocat...
File runtime/vm/flow_graph_allocator.cc (left):

https://codereview.chromium.org/12340108/diff/1/runtime/vm/flow_graph_allocat...
runtime/vm/flow_graph_allocator.cc:112:
it.SetCurrentValue(push_argument->value()->Copy());
On 2013/02/27 21:53:02, Vyacheslav Egorov (Google) wrote:
> What happened to this special PushArgument handling? Are we relying on the
fact
> that push argument removal does this substitution? Can we assert that
> environment contains no PushArguments.

It was already obsolete after a previous change, where they were removed eagerly
from environments.

We can add an assert, but it seemed to me that it was just asserting a negative
property of the old implementation.  

Presumably, any removed value turning up in an environment would end up with an
unallocated value and an assertion failure later.  So we can actually assert a
stronger property here if we want, or rely on the later assert.

https://codereview.chromium.org/12340108/diff/1/runtime/vm/flow_graph_optimiz...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/12340108/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:4281: if (FLAG_remove_redundant_phis &&
(live_count == 1)) {
On 2013/02/27 21:53:02, Vyacheslav Egorov (Google) wrote:
> Do we have any code that kills truly redundant phis of form phi(x,x)?
> 
> (not related to this CL but might be a good follow up)

I don't think so.  I wonder, do they arise?

[Kevin Millikin (Google), 2013-02-28 08:26:09]

Committed patchset #1 manually as r19206 (presubmit successful).