Merging CCP and VRP?

[Kazu Hirata <kazu at cs dot umass dot edu>]

Hi Diego,

Have you considered merging CCP and VRP (as suggested by Kenny last
year at the summit)?

Originally I was thinking that ASSERT_EXPRs, or ranges gathered by VRP
rather, were very useful for jump threading, but they seem to be
useful for constant propagation, too.  Consider

void bar (int);

void
foo (int a)
{
  if (a == 0)
    bar (a);
}

At the end of VRP we still have

<bb 0>:
  if (a_1 == 0) goto <L0>; else goto <L2>;

<L0>:;
  a_2 = 0;
  bar (a_2);  <-- a_2 isn't replaced with 0 yet!

Note that we don't have bar (0) at the end.  This is because currently
VRP does not have the equivalent of substitute_and_fold.  We just use
the range information to fold COND_EXPR; we don't fold each statement
using constants and ranges gathered by VRP.

We could have VRP call substitute_and_fold, but then once we do that,
the distinction between CCP and VRP would become less clear.  Plus,
propagating conditional equivalences may have a chain effect on
simplification, especially with inlining.  That is, an equivalence
like "a = 0" above may end up massively simplifying the code.  For the
obvious reason, we don't want to do

  do
    {
      Run CCP;
      Insert ASSERT_EXPRs.
      Run VRP;
      Remove ASSERT_EXPRs.
    }
  while (something changes)

So I am thinking about inserting ASSERT_EXPRs up front *before* going
into SSA, without much of pruning, and then run an enhanced version of
CCP, which includes ranges and anti-ranges in the lattice, which are
all suggested by Kenny last year.  I'm thinking about keeping
ASSERT_EXPRs until it's difficult to keep them.  I don't know much
about loop optimizers, so if I were to write code to keep
ASSERT_EXPRs, I might give up by turning ASSERT_EXPRs into copy
statements just before hitting loop optimizers.  :-) I have not
figured out how to deal with ASSERT_EXPRs in FRE, but Daniel Berlin
says I just have to teach tree-vn.c how to deal with it.

One note about the order of optimizations.  I think it's a good idea
to run an enhanced version of CCP before copy-prop because the
propagation engine can deal with presence of copies very well, whether
copy statements or PHI nodes.  If we run copy prop after an enhanced
version of CCP, we would still have useful information in
SSA_NAME_VALUE_RANGE at the end.  Copy prop only kills newer copies;
it doesn't even touch SSA_NAME_VALUE_RANGE stored in older copies.

Last but not least, I'm willing to do the work, but I'd like to be
more or less on the same page with other people hacking these scalar
optimizations before I do any significant work.

Thoughts?

p.s.
By the way, looking at Kenny's slides from last year, one thing we
have not implemented in our propagation engine is to process the CFG
worklist in the DFS order of a dominator tree.  I haven't looked
closely at this, but if the speed of propagation is a concern, we
should come back to this.

Kazu Hirata