[Bug tree-optimization/107822] [13 Regression] Dead Code Elimination Regression at -Os (trunk vs. 12.2.0)

["amacleod at redhat dot com" <gcc-bugzilla@gcc.gnu.org>]

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

--- Comment #2 from Andrew Macleod <amacleod at redhat dot com> ---
Sorry, I've been out for a few weeks.

This isn't an on-demand issue. All versions of VRP do a full walk and resolve
during the walk. This issue is a combination of lack of iteration and not
optimistic evaluations on back edges. 

We do use on-demand to query the back edge to alleviate a number of issues with
lack of iteration. The problem is that with a lack of iteration, we can't take
the fully optimistic approach and assume that the value of c_10 is [1, 1] for a
full iteration of the loop and then determine during the second iteration that
it is always either 1 or 2.

    <bb 3> [local count: 955630225]:
    _1 = c_10 ^ 3;

    <bb 4> [local count: 1073741824]:
    # c_10 = PHI <1(2), _1(3)>
    b.1_3 = b;
    if (b.1_3 <= 8)
      goto <bb 3>; [89.00%]
    else
      goto <bb 5>; [11.00%]

    <bb 5> [local count: 118111600]:
    # c_13 = PHI <c_10(4)>
    if (c_13 != 0)

When we first try to evaluate 
# c_10 = PHI <1(2), _1(3)>
the back edge 3->4 has not been processed, so it is evaluated and _1 needs to
be calculated. Unfortunately the value of c_10 has not been resolved yet, so it
defaults to something pessimistically safe and assumes it is varying and we get
the results you see.


We have a few possible approaches. In an ideal world, we could use the path
ranger to answer questions on the back edge instead of fully evaluating it. 
This would allow us to do a "pretend" first iteration and use the value of
[1,1] for c_10, and produce _1 =  result of [1,2], which in turn would then
cause us to evaluate c_10 as [1,2].  It is too late in the cycle to experiment
with that approach I think.

I have also (still am) experimented with changing that initial value to be more
optimistic.  When we first evaluate a statement, We store an initial value so
that if it is encountered again during evaluation, we can avoid a cycle. That
initial value is what gets used by any calculations along a back edge. When we
return from resolving all the inputs, we do a final evaluation of the statement
and store the real global value.

We have existing infrastructure which uses time stamps that should allow us to
calculate one value when doing the back edge, and then recalculate it for real
when we actually process that block.  I have not convinced myself that this is
100% safe yet.

A third option would be to recognize this is a fairly common pattern that we
have a 2 input PHI node like this. and before setting the initial value we
could walk the use-def chains and see if the PHI is feeding itself and make
some other determinations about the range (ie, increasing, decreasing, specific
values, etc) and use that for the initial estimate instead.   This would give
us similar results to what we did before and is likely safer than depending on
timestamps to do recalculations. It is just not quite as general.      

Im experimenting with the latter 2 approaches this week to determine what seems
safest at this point in the cycle.