[Bug tree-optimization/107176] [10/11/12/13 Regression] Wrong code at -Os on x86_64-pc-linux-gnu since r7-2012-g43aabfcfd4139e4c

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

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
<bb 4> [local count: 1073741824]:
# b_lsm.8_15 = PHI <0(2), _3(3)>
# b_lsm_flag.9_17 = PHI <0(2), 1(3)>
if (b_lsm.8_15 <= 0)
  goto <bb 3>; [89.00%]
else
  goto <bb 5>; [11.00%]

<bb 3> [local count: 955630225]:
_1 = (unsigned int) b_lsm.8_15;
_2 = _1 + 4294967206;
_12 = (long int) _2;
_3 = _12 + 91;
goto <bb 4>;

for this loop we get

(number_of_iterations_in_loop =
(analyze_scalar_evolution
  (loop_nb = 1)
  (scalar = b_lsm.8_15)
(get_scalar_evolution
  (scalar = b_lsm.8_15)
  (scalar_evolution = ))
(analyze_initial_condition
  (loop_phi_node =
b_lsm.8_15 = PHI <0(2), _3(3)>
)
  (init_cond = 0))
(analyze_evolution_in_loop
  (loop_phi_node = b_lsm.8_15 = PHI <0(2), _3(3)>
)
(add_to_evolution
  (loop_nb = 1)
  (chrec_before = 0)
  (to_add = 91)
  (res = {0, +, 91}_1))
(add_to_evolution
  (loop_nb = 1)
  (chrec_before = {0, +, 91}_1)
  (to_add = 4294967206)
  (res = {0, +, 1}_1))
Estimating # of iterations of loop 1
(number_of_iterations_in_loop =
(analyze_scalar_evolution
  (loop_nb = 1)
  (scalar = b_lsm.8_15)
(get_scalar_evolution
  (scalar = b_lsm.8_15)
  (scalar_evolution = ))
(analyze_initial_condition
  (loop_phi_node =
b_lsm.8_15 = PHI <0(2), _3(3)>
)
  (init_cond = 0))
(analyze_evolution_in_loop
  (loop_phi_node = b_lsm.8_15 = PHI <0(2), _3(3)>
)
(add_to_evolution
  (loop_nb = 1)
  (chrec_before = 0)
  (to_add = 91)
  (res = {0, +, 91}_1))
(add_to_evolution
  (loop_nb = 1)
  (chrec_before = {0, +, 91}_1)
  (to_add = 4294967206)
  (res = {0, +, 1}_1))
  (evolution_function = (long int) {0, +, 1}_1))
(set_scalar_evolution
  instantiated_below = 2
  (scalar = b_lsm.8_15)
  (scalar_evolution = (long int) {0, +, 1}_1))
)

and that's wrong I think.  (long int)((unsigned int)b + -90u) + 91 isn't
the same as (long int) {0, +, 1} with the evolution in unsigned int.
It's the evolution of the value in _unsigned int_.

The key somehow happens in follow_ssa_edge_expr where we do

          /* Match an assignment under the form:
             "a = b +- ...". 
             Use tail-recursion for the simple case.  */
          *evolution_of_loop = add_to_evolution
              (loop->num, chrec_convert (type, *evolution_of_loop,
                                         at_stmt),
               code, rhs1, at_stmt);
          expr = rhs0;
          goto tail_recurse; 

which converts the long int { 0, +, 91 }_1 to unsigned int and will
then add -90u to that.

We are building the CHREC "backwards", we start with '(long)0', the initial
condition but then build the CHREC from the backedge def, first
{(long)0, +, 91}, then upon _12 = (long int)_2 we're feeding the
{(long)0, +, 91} to the _2 = _1 + -90u handler above which simply
truncates the "current" CHREC and the outer recursion will simply
convert that back.  But that's not how the CHREC expression build and
simplification should work?

The most significant hint is probably that when reaching the initial
truncation '_1 = (unsigned int) b_lsm.8_15;' we get there with a
CHREC that is unsigned int already!

So it's possibly wrong to "post-recurse" to rhs0 here.  Doing

diff --git a/gcc/tree-scalar-evolution.cc b/gcc/tree-scalar-evolution.cc
index 9f30f78cb5d..b481c488ca8 100644
--- a/gcc/tree-scalar-evolution.cc
+++ b/gcc/tree-scalar-evolution.cc
@@ -1265,6 +1265,9 @@ tail_recurse:
       if (TREE_CODE (rhs0) == SSA_NAME
          && (TREE_CODE (rhs1) != SSA_NAME || code == MINUS_EXPR))
        {
+
+       t_bool res = follow_ssa_edge_expr (loop, at_stmt, rhs0, halting_phi,
+                                          evolution_of_loop, limit);
          /* Match an assignment under the form:
             "a = b +- ...".
             Use tail-recursion for the simple case.  */
@@ -1272,8 +1275,9 @@ tail_recurse:
              (loop->num, chrec_convert (type, *evolution_of_loop,
                                         at_stmt),
               code, rhs1, at_stmt);
-         expr = rhs0;
-         goto tail_recurse;
+         //expr = rhs0;
+         //goto tail_recurse;
+         return res;
        }
       /* Else search for the SCC in both rhs0 and rhs1.  */
       return follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,

fixes the testcase.