new copy elimination pass

The sparse data-flow analysis used for
copy elimination before this patch
could sometimes diverge.  The core
reason for this behavior is that the
visitphi() function was not monotonic
in the following copy-of lattice:

     top   (represented as the temp
    / | \   itself)
   x  y  z ...
    \ | /
     bot   (represented as R)

This monotonicity defect could be
fixed by reverting 2f41ff03, but
then the pass would end up missing
some redundant phis.

This patch re-implements the pass
from scratch using a different
approach.  The new algorithm should
get rid of all redundant copies.  On
the other hand, it can run slower
than the monotonic sparse data-flow
analysis because, in the worst case,
an instruction in a phi cluster can
be visited as many times as there
are phis in the input program.

Thanks to Michael Forney for reviewing
and testing the new pass.

0 files changed, 0 insertions, 0 deletions