[Bug middle-end/55555] [4.8 Regression] miscompilation at -O2 (number_of_iterations)

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

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55555

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-17 12:14:18 UTC ---
Ok, I'm confused by the following:

  <bb 3>: (loop 1 header)
  # lxp_1 = PHI <0(2), lxp_24(12)>
  t_9 = pol_x[lxp_1];
  _10 = (long int) lxp_1;
  _11 = _10 * 4;
  l_12 = _11 + -1;
  goto <bb 5>;


  <bb 4>:
  _15 = S_2 + l_12;
  _16 = coef_x[_15];
  _17 = S_2 + -1;
  _18 = s[_17];
  _19 = _18 * t_9;
  _20 = _16 + _19;
  coef_x[_15] = _20;
  S_22 = S_2 + 1;

  <bb 5>: (loop 2 header)
  # S_2 = PHI <1(3), S_22(4)>
  if (S_2 <= 4)
    goto <bb 4>;
  else
    goto <bb 6>;

  <bb 6>:
  lxp_24 = lxp_1 + 1;
  if (lxp_1 != 1)
    goto <bb 12>;
  else
    goto <bb 7>;

  <bb 12>:
  goto <bb 3>;

and SCEV says _15 is {l_12 + 1, +, 1}_2 which looks correct.  But then it
does

(chrec_apply
  (varying_loop = 2)
  (chrec = {l_12 + 1, +, 1}_2)
  (x = 4)
  (res = l_12 + 5))

and magically, via l_12 being {-1, +, 4}_1 (also correct) arrives at

(instantiate_scev
  (instantiate_below = 2)
  (evolution_loop = 1)
  (chrec = {4, +, 4}_1)
  (res = {4, +, 4}_1))

huh?  So to it _15 is {4, +, 4}_1 (not sure what is considered "initial"
in terms of scalar evolution with a value varying in an inner loop).

This is what infer_loop_bounds_from_undefined derives the bogus bound
for loop 1 from.  To my eyes _15 should be {0, + 4}_1!

Maybe it doesn't really make sense to ask for the evolution of something
defined in loop N with respect to an outer loop M?

If we change idx_infer_loop_bounds with

Index: tree-ssa-loop-niter.c
===================================================================
--- tree-ssa-loop-niter.c       (revision 194552)
+++ tree-ssa-loop-niter.c       (working copy)
@@ -2671,7 +2671,12 @@ idx_infer_loop_bounds (tree base, tree *
       upper = false;
     }

-  ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
+  struct loop *dloop = loop_containing_stmt (data->stmt);
+  if (!dloop)
+    return true;
+
+  ev = analyze_scalar_evolution (dloop, *idx);
+  ev = instantiate_parameters (loop, ev);
   init = initial_condition (ev);
   step = evolution_part_in_loop_num (ev, loop->num);

then we obtain via {l_12 + 1, +, 1}_2, {{0, +, 4}_1, +, 1}_2 the correct
solution (init == 0, step == 4).

I am going to bootstrap and regtest that.