[Bug middle-end/65855] missing optimization: triangular numbers

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

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |spop at gcc dot gnu.org

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Looks like SCEV analysis is broken for this case.

  <bb 3>:
  # t_11 = PHI <0(5), t_5(7)>
  # i_13 = PHI <1(5), i_6(7)>
  t_5 = t_11 + i_13;
  i_6 = i_13 + 1;
  if (i_6 <= _10)
    goto <bb 7>;
  else
    goto <bb 8>;

  <bb 7>:
  goto <bb 3>;

  <bb 8>:
  # t_2 = PHI <t_5(3)>

t_11 = { 0, +, i_13 }_1  (ok)
i_13 = {1, +, 1}_1 (ok)

(instantiate_scev
  (instantiate_below = 5)
  (evolution_loop = 1)
  (chrec = {0, +, i_13}_1)
(analyze_scalar_evolution
  (loop_nb = 1)
  (scalar = i_13)
(get_scalar_evolution
  (scalar = i_13)
  (scalar_evolution = {1, +, 1}_1))
(set_scalar_evolution
  instantiated_below = 5
  (scalar = i_13)
  (scalar_evolution = {1, +, 1}_1))
)
  (res = {0, +, {1, +, 1}_1}_1))

(instantiate_scev
  (instantiate_below = 5)
  (evolution_loop = 1)
  (chrec = {1, +, 1}_1)
  (res = {1, +, 1}_1))
(set_scalar_evolution
  instantiated_below = 5
  (scalar = t_5)
  (scalar_evolution = {1, +, {2, +, 1}_1}_1))

not sure where the latter result comes from.  It comes from

#10 0x0000000000eac871 in scev_const_prop ()
    at /space/rguenther/src/svn/trunk/gcc/tree-scalar-evolution.c:3456
3456                                   NULL);
(gdb) l
3451              if (!POINTER_TYPE_P (type)
3452                  && !INTEGRAL_TYPE_P (type))
3453                continue;
3454
3455              ev = resolve_mixers (loop, analyze_scalar_evolution (loop,
name),
3456                                   NULL);

analyzing the evolution of t_2.

So we end up looking at t_5 = t_11 + i_13 which is {0, +, {1,+, 1}_1}_1 +
{1,+,1}_1 but that isn't {1, +, {2, +, 1}_1 }_1 as chrec_fold_plus_poly_poly
maintains?

But maybe this kind of CHREC is just ill-formed in the first place?

Sebastian, any ideas here?