[Bug c/65855] New: missing optimization: triangular numbers

[Bug c/65855] New: missing optimization: triangular numbers

[shawn at churchofgit dot com]

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

            Bug ID: 65855
           Summary: missing optimization: triangular numbers
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: shawn at churchofgit dot com

Created attachment 35388
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35388&action=edit
triangle.c

If a register mode is available to avoid multiplication overflow, a loop that
is calculating triangular numbers could be optimized to a multiplication:

uint64_t triangle(uint32_t n) {
uint64_t t = 0;
for (uint64_t i=1;i<=n;i++) t += i;
return t;
}

=>

uint64_t triangle_fast(uint32_t _n) {
uint64_t t, n = _n;
t = (n * (n + 1)) / 2;
return t;
}

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

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
            Version|5.0                         |5.1.0
           Severity|normal                      |enhancement

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

[shawn at churchofgit dot com]

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

--- Comment #2 from Shawn Landden <shawn at churchofgit dot com> ---
Created attachment 35399
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35399&action=edit
triange, 64-bit version

This can also work with 128-bit multiple of course as well.

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

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ktietz at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
shorten_compare in the C frontend family performs the (long unsigned int)
n_3(D) != 18446744073709551615 simplification.  Nothing in fold-const.c or
match.pd does.

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

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
match.pd now has the desired simplification.  So we run into

(chrec_apply
  (varying_loop = 1
)
  (chrec = {1, +, {2, +, 1}_1}_1)
  (x = (long unsigned int) n_3(D) + 18446744073709551615)
  (res = scev_not_known))

the question is if we can handle this kind of CHREC in chrec_apply generally
or not.

{ x, +, { y, +, C}_N }_N

specifically. I suppose it's simply x + y*X + C*X*(X+1)/2.

Now the question is whether it's generally profitable to handle this.  We'll
see.

I have a patch that produces

(chrec_apply
  (varying_loop = 1
)
  (chrec = {1, +, {2, +, 1}_1}_1)
  (x = (long unsigned int) n_3(D) + 18446744073709551615)
  (res = (((long unsigned int) n_3(D) * ((long unsigned int) n_3(D) +
18446744073709551615)) /[ex] 2 + (uint64_t) n_3(D) * 2) +
18446744073709551615))

but that's somehow off.

Index: gcc/tree-chrec.c
===================================================================
--- gcc/tree-chrec.c    (revision 229233)
+++ gcc/tree-chrec.c    (working copy)
@@ -602,19 +602,37 @@ chrec_apply (unsigned var,
   switch (TREE_CODE (chrec))
     {
     case POLYNOMIAL_CHREC:
-      if (evolution_function_is_affine_p (chrec))
+      if (CHREC_VARIABLE (chrec) != var)
+       return build_polynomial_chrec
+           (CHREC_VARIABLE (chrec),
+            chrec_apply (var, CHREC_LEFT (chrec), x),
+            chrec_apply (var, CHREC_RIGHT (chrec), x));
+      else if (evolution_function_is_affine_p (chrec))
        {
-         if (CHREC_VARIABLE (chrec) != var)
-           return build_polynomial_chrec
-             (CHREC_VARIABLE (chrec),
-              chrec_apply (var, CHREC_LEFT (chrec), x),
-              chrec_apply (var, CHREC_RIGHT (chrec), x));
-
          /* "{a, +, b} (x)"  ->  "a + b*x".  */
          x = chrec_convert_rhs (type, x, NULL);
          res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x);
          res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
        }
+      else if (evolution_function_is_affine_p (CHREC_RIGHT (chrec))
+              && CHREC_VARIABLE (CHREC_RIGHT (chrec)) == var)
+       {
+         /* "{a, +, {b, +, c} } (x)" -> "a + b*x + c*x*(x+1)/2".  */
+         tree chrecr = CHREC_RIGHT (chrec);
+         x = chrec_convert_rhs (type, x, NULL);
+         /* c*x*(x+1)/2  */
+         res = chrec_fold_plus (type, x, build_int_cst (type, 1));
+         res = chrec_fold_multiply (type, res, x);
+         res = fold_build2 (EXACT_DIV_EXPR, type, res,
+                            build_int_cst (type, 2));
+         res = chrec_fold_multiply (type, CHREC_RIGHT (chrecr), res);
+         /* + b*x  */
+         res = chrec_fold_plus (type, res,
+                                chrec_fold_multiply (type, x,
+                                                     CHREC_LEFT (chrecr)));
+         /* + a  */
+         res = chrec_fold_plus (type, res, CHREC_LEFT (chrec));
+       }
       else if (TREE_CODE (x) == INTEGER_CST
               && tree_int_cst_sgn (x) == 1)
        /* testsuite/.../ssa-chrec-38.c.  */


produces 76 for n == 11 and 298 for n == 23.  Testcase that works with SCCP
disabled:

extern void abort (void);

typedef __UINT64_TYPE__ uint64_t;
typedef __UINT32_TYPE__ uint32_t;
uint64_t __attribute__((noinline,noclone))
triangle(uint32_t n)
{
  uint64_t t = 0;
  for (uint64_t i=1;i<=n;i++) t += i;
  return t;
}

int main()
{
  uint64_t t11 = triangle (11);
  uint64_t t23 = triangle (23);
  if (t11 != 66 || t23 != 276)
    abort ();
  return 0;
}

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

[rguenth at gcc dot gnu.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?

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

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

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

--- Comment #10 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 82519 has been marked as a duplicate of this bug. ***

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

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jak@jak-linux.org

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 46186 has been marked as a duplicate of this bug. ***

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

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |gabravier at gmail dot com

--- Comment #12 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 98960 has been marked as a duplicate of this bug. ***

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

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |goon.pri.low at gmail dot com

--- Comment #13 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 112663 has been marked as a duplicate of this bug. ***