[PATCH][GRAPHITE] Fix PR82525

[Richard Biener <rguenther at suse dot de>]

The following avoids code-generation errors for modulo operations 
resulting from our own constraints ending up as no-ops because
the type we code-generate in already imposes the modulo operation.

For the case in SPEC 2k6 triggering this we'd even know the
modulo constraint isn't necessary - we have

 int64_t lower, upper;
 if (lower < upper)
   uint64_t niter = (uint64_t)upper - (uint64_t)lower;

but there's no way to represent in GIMPLE that subtracting
the two signed values will yield a positive value fitting
in the corresponding unsigned type...  We'd need sth
like a MINUSU_EXPR (like the often proposed ABSU_EXPR or
the proposed POINTER_DIFF_EXPR).

This fixes the last code generation errors with SPEC CPU 2006
and -fgraphite-identity -floop-nest-optimize.

loop nest optimized: 483
loop nest not optimized, code generation error: 0
loop nest not optimized, optimized schedule is identical to original 
schedule: 173
loop nest not optimized, optimization timed out: 60
loop nest not optimized, ISL signalled an error: 9
loop nest: 725

Note that we still (with and without this patch) get miscompares
in 465.tonto, 416.gamess and 403.gcc (we have those "wrong"
constraint thing leading to empty domains if you remember).

Bootstrap and regtest running on x86_64-unknown-linux-gnu, ok?

Thanks,
Richard.

2017-10-12  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/82525
	* graphite-isl-ast-to-gimple.c
	(translate_isl_ast_to_gimple::widest_int_from_isl_expr_int): Split
	out from ...
	(translate_isl_ast_to_gimple::gcc_expression_from_isl_expr_int): Here.
	Fail code generation when we cannot represent the isl integer.
	(binary_op_to_tree): Elide modulo operations that are no-ops
	in the type we code generate.  Remove now superfluous code
	generation errors.

	* gcc.dg/graphite/id-30.c: New testcase.
	* gfortran.dg/graphite/id-28.f90: Likewise.

Index: gcc/graphite-isl-ast-to-gimple.c
===================================================================
--- gcc/graphite-isl-ast-to-gimple.c	(revision 253645)
+++ gcc/graphite-isl-ast-to-gimple.c	(working copy)
@@ -177,6 +177,7 @@ class translate_isl_ast_to_gimple
   tree gcc_expression_from_isl_ast_expr_id (tree type,
 					    __isl_keep isl_ast_expr *expr_id,
 					    ivs_params &ip);
+  widest_int widest_int_from_isl_expr_int (__isl_keep isl_ast_expr *expr);
   tree gcc_expression_from_isl_expr_int (tree type,
 					 __isl_take isl_ast_expr *expr);
   tree gcc_expression_from_isl_expr_op (tree type,
@@ -265,29 +266,46 @@ gcc_expression_from_isl_ast_expr_id (tre
   return fold_convert (type, *val);
 }
 
-/* Converts an isl_ast_expr_int expression E to a GCC expression tree of
-   type TYPE.  */
+/* Converts an isl_ast_expr_int expression E to a widest_int.
+   Raises a code generation error when the constant doesn't fit.  */
 
-tree translate_isl_ast_to_gimple::
-gcc_expression_from_isl_expr_int (tree type, __isl_take isl_ast_expr *expr)
+widest_int translate_isl_ast_to_gimple::
+widest_int_from_isl_expr_int (__isl_keep isl_ast_expr *expr)
 {
   gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int);
   isl_val *val = isl_ast_expr_get_val (expr);
   size_t n = isl_val_n_abs_num_chunks (val, sizeof (HOST_WIDE_INT));
   HOST_WIDE_INT *chunks = XALLOCAVEC (HOST_WIDE_INT, n);
-  tree res;
-  if (isl_val_get_abs_num_chunks (val, sizeof (HOST_WIDE_INT), chunks) == -1)
-    res = NULL_TREE;
-  else
+  if (n > WIDE_INT_MAX_ELTS
+      || isl_val_get_abs_num_chunks (val, sizeof (HOST_WIDE_INT), chunks) == -1)
     {
-      widest_int wi = widest_int::from_array (chunks, n, true);
-      if (isl_val_is_neg (val))
-	wi = -wi;
-      res = wide_int_to_tree (type, wi);
+      isl_val_free (val);
+      set_codegen_error ();
+      return 0;
     }
+  widest_int wi = widest_int::from_array (chunks, n, true);
+  if (isl_val_is_neg (val))
+    wi = -wi;
   isl_val_free (val);
+  return wi;
+}
+
+/* Converts an isl_ast_expr_int expression E to a GCC expression tree of
+   type TYPE.  Raises a code generation error when the constant doesn't fit.  */
+
+tree translate_isl_ast_to_gimple::
+gcc_expression_from_isl_expr_int (tree type, __isl_take isl_ast_expr *expr)
+{
+  widest_int wi = widest_int_from_isl_expr_int (expr);
   isl_ast_expr_free (expr);
-  return res;
+  if (codegen_error_p ())
+    return NULL_TREE;
+  if (wi::min_precision (wi, TYPE_SIGN (type)) > TYPE_PRECISION (type))
+    {
+      set_codegen_error ();
+      return NULL_TREE;
+    }
+  return wide_int_to_tree (type, wi);
 }
 
 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
@@ -296,14 +314,25 @@ gcc_expression_from_isl_expr_int (tree t
 tree translate_isl_ast_to_gimple::
 binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
 {
+  enum isl_ast_op_type expr_type = isl_ast_expr_get_op_type (expr);
   isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
   tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
   arg_expr = isl_ast_expr_get_op_arg (expr, 1);
-  tree tree_rhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
-
-  enum isl_ast_op_type expr_type = isl_ast_expr_get_op_type (expr);
   isl_ast_expr_free (expr);
 
+  /* From our constraint generation we may get modulo operations that
+     we cannot represent explicitely but that are no-ops for TYPE.
+     Elide those.  */
+  if (expr_type == isl_ast_op_pdiv_r
+      && isl_ast_expr_get_type (arg_expr) == isl_ast_expr_int
+      && (wi::exact_log2 (widest_int_from_isl_expr_int (arg_expr))
+	  >= TYPE_PRECISION (type)))
+    {
+      isl_ast_expr_free (arg_expr);
+      return tree_lhs_expr;
+    }
+
+  tree tree_rhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
   if (codegen_error_p ())
     return NULL_TREE;
 
@@ -319,44 +348,16 @@ binary_op_to_tree (tree type, __isl_take
       return fold_build2 (MULT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 
     case isl_ast_op_div:
-      /* As isl operates on arbitrary precision numbers, we may end up with
-	 division by 2^64 that is folded to 0.  */
-      if (integer_zerop (tree_rhs_expr))
-	{
-	  set_codegen_error ();
-	  return NULL_TREE;
-	}
       return fold_build2 (EXACT_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 
     case isl_ast_op_pdiv_q:
-      /* As isl operates on arbitrary precision numbers, we may end up with
-	 division by 2^64 that is folded to 0.  */
-      if (integer_zerop (tree_rhs_expr))
-	{
-	  set_codegen_error ();
-	  return NULL_TREE;
-	}
       return fold_build2 (TRUNC_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 
     case isl_ast_op_zdiv_r:
     case isl_ast_op_pdiv_r:
-      /* As isl operates on arbitrary precision numbers, we may end up with
-	 division by 2^64 that is folded to 0.  */
-      if (integer_zerop (tree_rhs_expr))
-	{
-	  set_codegen_error ();
-	  return NULL_TREE;
-	}
       return fold_build2 (TRUNC_MOD_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 
     case isl_ast_op_fdiv_q:
-      /* As isl operates on arbitrary precision numbers, we may end up with
-	 division by 2^64 that is folded to 0.  */
-      if (integer_zerop (tree_rhs_expr))
-	{
-	  set_codegen_error ();
-	  return NULL_TREE;
-	}
       return fold_build2 (FLOOR_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 
     case isl_ast_op_and:
Index: gcc/testsuite/gcc.dg/graphite/id-30.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/id-30.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/graphite/id-30.c	(working copy)
@@ -0,0 +1,16 @@
+/* The modulo constraints we generate for the niter expression
+     (unsinged long)ubound - (unsigned long)lbound
+   end up with a modulo that we cannot represent in the expression
+   type we are using (int64_t), so we run into the codegen error
+   where ISL generates a modulo/divide by sth that doesn't fit the
+   type we code-generate with.  Verify we properly elide those.  */
+
+void foo (double *a, long int lbound0, long int ubound0,
+	  long int lbound1, long int ubound1, long int stride1)
+{
+  if (lbound0 < ubound0)
+    for (long int i = lbound0; i <= ubound0; ++i)
+      if (lbound1 < ubound1)
+	for (long int j = lbound1; j <= ubound1; ++j)
+	  a[i*stride1 + j] = 0.;
+}
Index: gcc/testsuite/gfortran.dg/graphite/id-28.f90
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/id-28.f90	(nonexistent)
+++ gcc/testsuite/gfortran.dg/graphite/id-28.f90	(working copy)
@@ -0,0 +1,15 @@
+! Verify we elide modulo operations we cannot represent
+module OPMATRIX_MODULE
+   implicit none
+   type opmatrix_type
+   real(kind=kind(1.0d0)), dimension(:,:), pointer :: restricted
+   end type
+   interface zero_
+      module procedure zero
+   end interface
+contains
+   subroutine zero(self)
+      type(opmatrix_type) :: self
+      self%restricted = 0.0d0
+   end subroutine
+end