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.
