[Bug tree-optimization/66502] New: SCCVN can't handle PHIs optimistically optimally

["rguenth at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66502

            Bug ID: 66502
           Summary: SCCVN can't handle PHIs optimistically optimally
           Product: gcc
           Version: 6.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: rguenth at gcc dot gnu.org
  Target Milestone: ---

Currently FRE doesn't eliminate redundant IVs like in

int x[1024];
int foo (int a, int s, unsigned int k)
{
  int i = a, j = a;
  int sum = 0;
  do
    {
      sum += x[i];
      sum += x[j];
      i += s;
      j += s;
    }
  while (k--);
  return sum;
}

but it handles the following instead

int foo (int a, int s, unsigned int k)
{
  int i = a, j = a;
  do
    {
      i += s;
      j += j;
      j -= a;
    }
  while (k--);
  return j+i;
}

the difference is whether a PHI node with all but one non-VN_TOP argument
is optimistically value-numbered to that argument or to another PHI node
in the same BB with the same argument in its position (if existing).

If it were not SCCVN then if both PHIs are value-numbered together
value-numbering optimistically to the non-VN_TOP argument could catch
both cases, but only if we allow a questionable lattice-transition
from a final value (the non-VN_TOP argument) to a still optimistic
one (the other PHI nodes result).  That's of course exactly a transition
that we want to avoid because of lattice oscillations (well, if we
allow it in this one direction only and not back it might be fine).

To "fix" SCCVN we'd need to put any such PHI node candidates into the
same SCC and allow that lattice transition.