[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;
}