Improve dead phi elimination....

Improve dead phi elimination.

This change splits the existing phi elimination into two phases:
1. Remove redundant phis
2. Remove dead phis with a fixed point iteration.

The new approach allows us to remove dead phis that are connected
in a cycle.


Committed: http://code.google.com/p/v8/source/detail?r=7085

[Kevin Millikin (Chromium), 2011-03-08 08:51:03]

LGTM.

We can optimize the phi GC to avoid extra data lists on the side, but let's do
that as a later optimization.

http://codereview.chromium.org/6624061/diff/1/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

http://codereview.chromium.org/6624061/diff/1/src/hydrogen-instructions.cc#ne...
src/hydrogen-instructions.cc:936: bool HPhi::HasRealUses() {
The boolean variable seems too much:

for (...) {
  if (!uses()->at(i)->IsPhi()) return true;
}
return false;

http://codereview.chromium.org/6624061/diff/1/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/6624061/diff/1/src/hydrogen.cc#newcode724
src/hydrogen.cc:724: for (int i = 0; i < uses->length(); ++i) {
This pair of loops that copies the uses off to the side drives me nuts.  I
wonder if we could just write

  while (!uses->is_empty()) {
    HValue* use = uses->RemoveLast();
    if (use != NULL) {
      phi->ReplaceAtUse(use, value);
      if (use->IsPhi()) worklist.Add(HPhi::cast(use));
    }
  }

http://codereview.chromium.org/6624061/diff/1/src/hydrogen.h
File src/hydrogen.h (right):

http://codereview.chromium.org/6624061/diff/1/src/hydrogen.h#newcode237
src/hydrogen.h:237: void EliminateDeadPhis();
"Dead" is ambiguous.  Maybe "Unreachable" is more accurate (that is, not
reachable in any use-def chain from the non-phi uses).

[fschneider, 2011-03-08 10:03:39]

http://codereview.chromium.org/6624061/diff/1/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

http://codereview.chromium.org/6624061/diff/1/src/hydrogen-instructions.cc#ne...
src/hydrogen-instructions.cc:936: bool HPhi::HasRealUses() {
On 2011/03/08 08:51:03, Kevin Millikin wrote:
> The boolean variable seems too much:
> 
> for (...) {
>   if (!uses()->at(i)->IsPhi()) return true;
> }
> return false;

Done.

http://codereview.chromium.org/6624061/diff/1/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/6624061/diff/1/src/hydrogen.cc#newcode724
src/hydrogen.cc:724: for (int i = 0; i < uses->length(); ++i) {
On 2011/03/08 08:51:03, Kevin Millikin wrote:
> This pair of loops that copies the uses off to the side drives me nuts.  I
> wonder if we could just write
> 
>   while (!uses->is_empty()) {
>     HValue* use = uses->RemoveLast();
>     if (use != NULL) {
>       phi->ReplaceAtUse(use, value);
>       if (use->IsPhi()) worklist.Add(HPhi::cast(use));
>     }
>   }

Done.

http://codereview.chromium.org/6624061/diff/1/src/hydrogen.h
File src/hydrogen.h (right):

http://codereview.chromium.org/6624061/diff/1/src/hydrogen.h#newcode237
src/hydrogen.h:237: void EliminateDeadPhis();
On 2011/03/08 08:51:03, Kevin Millikin wrote:
> "Dead" is ambiguous.  Maybe "Unreachable" is more accurate (that is, not
> reachable in any use-def chain from the non-phi uses).

Done.