re PR middle-end/38492 ([graphite] segfaulting code when compiled with -fgraphite -fgraphite-identity)

2009-01-07  Jan Sjodin  <jan.sjodin@amd.com>

	PR tree-optimization/38492
	PR tree-optimization/38498
	* tree-check.c (operator_is_linear, scev_is_linear_expression): New.
	* tree-chrec.h (scev_is_linear_expression): Declared.
	* graphite.c (graphite_cannot_represent_loop_niter): New.
	(scopdet_basic_block_info): Call graphite_cannot_represent_loop_niter.
	(graphite_loop_normal_form): Use gcc_assert.
	(scan_tree_for_params): Use CASE_CONVERT.
	(phi_node_is_iv, bb_contains_non_iv_scalar_phi_nodes): New.
	(build_scop_conditions_1): Call bb_contains_non_iv_scalar_phi_nodes.
	Use gcc_assert.  Discard scops that contain unhandled cases.
	(build_scop_conditions): Return a boolean status for unhandled cases.
	(strip_mine_profitable_p): Print the loop number, not its depth.
	(is_interchange_valid): Pass the depth of the loop nest, don't
	recompute it wrongly.
	(graphite_trans_bb_block): Same.
	(graphite_trans_bb_block): Print tentative of loop blocking.
	(graphite_trans_scop_block): Do not print that the loop has been
	blocked.
	(graphite_transform_loops): Do not handle scops that contain condition
	scalar phi nodes.

	* testsuite/gcc.dg/graphite/pr38500.c: Fixed warning as committed
	in trunk.
	* testsuite/gcc.dg/graphite/block-0.c: Update test.
	* testsuite/gcc.dg/graphite/block-1.c: Same.
	* testsuite/gcc.dg/graphite/block-2.c: Remove xfail and test for blocking.
	* testsuite/gcc.dg/graphite/block-4.c: Remove test for strip mine.
	* testsuite/gcc.dg/graphite/block-3.c: New.
	* testsuite/gcc.dg/graphite/pr38498.c: New.

From-SVN: r143159

11 files changed, 280 insertions, 59 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 96013c1..b379b1b 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,27 @@
+2009-01-07  Jan Sjodin  <jan.sjodin@amd.com>
+
+	PR tree-optimization/38492
+	PR tree-optimization/38498
+	* tree-check.c (operator_is_linear, scev_is_linear_expression): New.
+	* tree-chrec.h (scev_is_linear_expression): Declared.
+	* graphite.c (graphite_cannot_represent_loop_niter): New.
+	(scopdet_basic_block_info): Call graphite_cannot_represent_loop_niter.
+	(graphite_loop_normal_form): Use gcc_assert.
+	(scan_tree_for_params): Use CASE_CONVERT.
+	(phi_node_is_iv, bb_contains_non_iv_scalar_phi_nodes): New.
+	(build_scop_conditions_1): Call bb_contains_non_iv_scalar_phi_nodes.
+	Use gcc_assert.  Discard scops that contain unhandled cases.
+	(build_scop_conditions): Return a boolean status for unhandled cases.
+	(strip_mine_profitable_p): Print the loop number, not its depth.
+	(is_interchange_valid): Pass the depth of the loop nest, don't
+	recompute it wrongly.
+	(graphite_trans_bb_block): Same.
+	(graphite_trans_bb_block): Print tentative of loop blocking.
+	(graphite_trans_scop_block): Do not print that the loop has been
+	blocked.
+	(graphite_transform_loops): Do not handle scops that contain condition
+	scalar phi nodes.
+
 2009-01-07  H.J. Lu  <hongjiu.lu@intel.com>
 
 	AVX Programming Reference (December, 2008)
diff --git a/gcc/graphite.c b/gcc/graphite.c
index b03e0619..645def2 100644
--- a/gcc/graphite.c
+++ b/gcc/graphite.c
@@ -1579,6 +1579,17 @@ move_sd_regions (VEC (sd_region, heap) **source, VEC (sd_region, heap) **target)
   VEC_free (sd_region, heap, *source);
 }
 
+/* Return true when it is not possible to represent the upper bound of
+   LOOP in the polyhedral representation.  */
+
+static bool
+graphite_cannot_represent_loop_niter (loop_p loop)
+{
+  tree niter = number_of_latch_executions (loop);
+
+  return chrec_contains_undetermined (niter)
+    || !scev_is_linear_expression (niter);
+}
 /* Store information needed by scopdet_* functions.  */
 
 struct scopdet_info
@@ -1650,8 +1661,7 @@ scopdet_basic_block_info (basic_block bb, VEC (sd_region, heap) **scops,
 	if (result.last->loop_father != loop)
 	  result.next = NULL;
 
-        if (TREE_CODE (number_of_latch_executions (loop))
-            == SCEV_NOT_KNOWN)
+        if (graphite_cannot_represent_loop_niter (loop))
           result.difficult = true;
 
         if (sinfo.difficult)
@@ -2350,9 +2360,7 @@ graphite_loop_normal_form (loop_p loop)
   gimple_seq stmts;
   edge exit = single_dom_exit (loop);
 
-  if (!number_of_iterations_exit (loop, exit, &niter, false))
-    gcc_unreachable ();
-
+  gcc_assert (number_of_iterations_exit (loop, exit, &niter, false));
   nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true,
 			      NULL_TREE);
   if (stmts)
@@ -2732,8 +2740,7 @@ scan_tree_for_params (scop_p s, tree e, CloogMatrix *c, int r, Value k,
 	}
       break;
 
-    case NOP_EXPR:
-    case CONVERT_EXPR:
+    CASE_CONVERT:
     case NON_LVALUE_EXPR:
       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
       break;
@@ -3278,13 +3285,63 @@ add_conditions_to_domain (graphite_bb_p gb)
     }
 }
 
-/* Helper recursive function.  */
+/* Returns true when PHI defines an induction variable in the loop
+   containing the PHI node.  */
 
-static void
+static bool
+phi_node_is_iv (gimple phi)
+{
+  loop_p loop = gimple_bb (phi)->loop_father;
+  tree scev = analyze_scalar_evolution (loop, gimple_phi_result (phi));
+
+  return tree_contains_chrecs (scev, NULL);
+}
+
+/* Returns true when BB contains scalar phi nodes that are not an
+   induction variable of a loop.  */
+
+static bool
+bb_contains_non_iv_scalar_phi_nodes (basic_block bb)
+{
+  gimple phi = NULL;
+  gimple_stmt_iterator si;
+
+  for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
+    if (is_gimple_reg (gimple_phi_result (gsi_stmt (si))))
+      {
+	/* Store the unique scalar PHI node: at this point, loops
+	   should be in cannonical form, so we expect to see at most
+	   one scalar phi node in the loop header.  */
+	if (phi
+	    || bb != bb->loop_father->header)
+	  return true;
+
+	phi = gsi_stmt (si);
+      }
+
+  if (!phi
+      || phi_node_is_iv (phi))
+    return false;
+
+  return true;
+}
+
+/* Helper recursive function.  Record in CONDITIONS and CASES all
+   conditions from 'if's and 'switch'es occurring in BB from SCOP.
+
+   Returns false when the conditions contain scalar computations that
+   depend on the condition, i.e. when there are scalar phi nodes on
+   the junction after the condition.  Only the computations occurring
+   on memory can be handled in the polyhedral model: operations that
+   define scalar evolutions in conditions, that can potentially be
+   used to index memory, can't be handled by the polyhedral model.  */
+
+static bool
 build_scop_conditions_1 (VEC (gimple, heap) **conditions,
 			 VEC (gimple, heap) **cases, basic_block bb,
 			 scop_p scop)
 {
+  bool res = true;
   int i, j;
   graphite_bb_p gbb;
   gimple_stmt_iterator gsi;
@@ -3293,9 +3350,11 @@ build_scop_conditions_1 (VEC (gimple, heap) **conditions,
   
   /* Make sure we are in the SCoP.  */
   if (!bb_in_scop_p (bb, scop))
-    return;
+    return true;
+
+  if (bb_contains_non_iv_scalar_phi_nodes (bb))
+    return false;
 
-  /* Record conditions in graphite_bb.  */
   gbb = gbb_from_bb (bb);
   if (gbb)
     {
@@ -3331,13 +3390,18 @@ build_scop_conditions_1 (VEC (gimple, heap) **conditions,
 		/* Recursively scan the then or else part.  */
 		if (e->flags & EDGE_TRUE_VALUE)
 		  VEC_safe_push (gimple, heap, *cases, stmt);
-		else if (e->flags & EDGE_FALSE_VALUE)
-		  VEC_safe_push (gimple, heap, *cases, NULL);
-		else
-		  gcc_unreachable ();
+		else 
+		  {
+		    gcc_assert (e->flags & EDGE_FALSE_VALUE);
+		    VEC_safe_push (gimple, heap, *cases, NULL);
+		  }
 
 		VEC_safe_push (gimple, heap, *conditions, stmt);
-		build_scop_conditions_1 (conditions, cases, e->dest, scop);
+		if (!build_scop_conditions_1 (conditions, cases, e->dest, scop))
+		  {
+		    res = false;
+		    goto done;
+		  }
 		VEC_pop (gimple, *conditions);
 		VEC_pop (gimple, *cases);
 	      }
@@ -3358,43 +3422,45 @@ build_scop_conditions_1 (VEC (gimple, heap) **conditions,
 		bb_child = label_to_block
 		  (CASE_LABEL (gimple_switch_label (stmt, i)));
 
-		/* Do not handle multiple values for the same block.  */
 		for (k = 0; k < n; k++)
 		  if (i != k
 		      && label_to_block 
 		      (CASE_LABEL (gimple_switch_label (stmt, k))) == bb_child)
 		    break;
 
-		if (k != n)
-		  continue;
-
-		/* Switch cases with more than one predecessor are not
-		   handled.  */
-		if (VEC_length (edge, bb_child->preds) != 1)
-		  continue;
+		/* Switches with multiple case values for the same
+		   block are not handled.  */
+		if (k != n
+		    /* Switch cases with more than one predecessor are
+		       not handled.  */
+		    || VEC_length (edge, bb_child->preds) != 1)
+		  {
+		    res = false;
+		    goto done;
+		  }
 
 		/* Recursively scan the corresponding 'case' block.  */
-
 		for (gsi_search_gimple_label = gsi_start_bb (bb_child);
 		     !gsi_end_p (gsi_search_gimple_label);
 		     gsi_next (&gsi_search_gimple_label))
 		  {
-		    gimple stmt_gimple_label 
-		      = gsi_stmt (gsi_search_gimple_label);
+		    gimple label = gsi_stmt (gsi_search_gimple_label);
 
-		    if (gimple_code (stmt_gimple_label) == GIMPLE_LABEL)
+		    if (gimple_code (label) == GIMPLE_LABEL)
 		      {
-			tree t = gimple_label_label (stmt_gimple_label);
+			tree t = gimple_label_label (label);
 
-			if (t == gimple_switch_label (stmt, i))
-			  VEC_replace (gimple, *cases, n_cases,
-				       stmt_gimple_label);
-			else
-			  gcc_unreachable ();
+			gcc_assert (t == gimple_switch_label (stmt, i));
+			VEC_replace (gimple, *cases, n_cases, label);
+			break;
 		      }
 		  }
 
-		build_scop_conditions_1 (conditions, cases, bb_child, scop);
+		if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
+		  {
+		    res = false;
+		    goto done;
+		  }
 
 		/* Remove the scanned block from the dominator successors.  */
 		for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
@@ -3402,13 +3468,14 @@ build_scop_conditions_1 (VEC (gimple, heap) **conditions,
 		    {
 		      VEC_unordered_remove (basic_block, dom, j);
 		      break;
-		    }  
+		    }
 	      }
 
 	    VEC_pop (gimple, *conditions);
 	    VEC_pop (gimple, *cases);
 	    break;
 	  }
+
 	default:
 	  break;
       }
@@ -3416,23 +3483,38 @@ build_scop_conditions_1 (VEC (gimple, heap) **conditions,
 
   /* Scan all immediate dominated successors.  */
   for (i = 0; VEC_iterate (basic_block, dom, i, bb_child); i++)
-    build_scop_conditions_1 (conditions, cases, bb_child, scop);
+    if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
+      {
+	res = false;
+	goto done;
+      }
 
+ done:
   VEC_free (basic_block, heap, dom);
+  return res;
 }
 
-/* Record all 'if' and 'switch' conditions in each gbb of SCOP.  */
+/* Record all conditions from SCOP.
 
-static void
+   Returns false when the conditions contain scalar computations that
+   depend on the condition, i.e. when there are scalar phi nodes on
+   the junction after the condition.  Only the computations occurring
+   on memory can be handled in the polyhedral model: operations that
+   define scalar evolutions in conditions, that can potentially be
+   used to index memory, can't be handled by the polyhedral model.  */
+
+static bool
 build_scop_conditions (scop_p scop)
 {
+  bool res;
   VEC (gimple, heap) *conditions = NULL;
   VEC (gimple, heap) *cases = NULL;
 
-  build_scop_conditions_1 (&conditions, &cases, SCOP_ENTRY (scop), scop);
+  res = build_scop_conditions_1 (&conditions, &cases, SCOP_ENTRY (scop), scop);
 
   VEC_free (gimple, heap, conditions);
   VEC_free (gimple, heap, cases);
+  return res;
 }
 
 /* Build the current domain matrix: the loops belonging to the current
@@ -4064,18 +4146,17 @@ expand_scalar_variables_expr (tree type, tree op0, enum tree_code code,
 	  expand_scalar_variables_stmt (def_stmt, bb, scop,
 					old_loop_father, map);
 	  return get_new_name_from_old_name (map, op0);
-	  
 	}
       else
 	{
 	  if (gimple_code (def_stmt) != GIMPLE_ASSIGN
 	      || !bb_in_scop_p (gimple_bb (def_stmt), scop))
 	    return get_new_name_from_old_name (map, op0);
-	  
+
 	  var0 = gimple_assign_rhs1 (def_stmt);
 	  subcode = gimple_assign_rhs_code (def_stmt);
 	  var1 = gimple_assign_rhs2 (def_stmt);
-	  
+
 	  return expand_scalar_variables_expr (type, var0, subcode, var1,
 					       bb, scop, old_loop_father, map);
 	}
@@ -4100,7 +4181,7 @@ expand_scalar_variables_stmt (gimple stmt, basic_block bb, scop_p scop,
     {
       tree use = USE_FROM_PTR (use_p);
       tree type = TREE_TYPE (use);
-      enum tree_code code  = TREE_CODE (use);
+      enum tree_code code = TREE_CODE (use);
       tree use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb,
 						    scop, old_loop_father, map);
       if (use_expr != use)
@@ -5607,7 +5688,7 @@ strip_mine_profitable_p (graphite_bb_p gb, int stride,
       if (dump_file && (dump_flags & TDF_DETAILS))
 	{
 	  fprintf (dump_file, "\nStrip Mining is not profitable for loop %d:",
-		   loop_index);
+		   loop->num);
 	  fprintf (dump_file, "number of iterations is too low.\n");
 	}
     }
@@ -5616,17 +5697,16 @@ strip_mine_profitable_p (graphite_bb_p gb, int stride,
 }
  
 /* Determines when the interchange of LOOP_A and LOOP_B belonging to
-   SCOP is legal.  */
+   SCOP is legal.  DEPTH is the number of loops around.  */
 
 static bool
-is_interchange_valid (scop_p scop, int loop_a, int loop_b)
+is_interchange_valid (scop_p scop, int loop_a, int loop_b, int depth)
 {
   bool res;
   VEC (ddr_p, heap) *dependence_relations;
   VEC (data_reference_p, heap) *datarefs;
 
   struct loop *nest = VEC_index (loop_p, SCOP_LOOP_NEST (scop), loop_a);
-  int depth = perfect_loop_nest_depth (nest);
   lambda_trans_matrix trans;
 
   gcc_assert (loop_a < loop_b);
@@ -5692,7 +5772,7 @@ graphite_trans_bb_block (graphite_bb_p gb, int stride, int loops)
 
   for (i = start ; i < nb_loops; i++)
     for (j = i + 1; j < nb_loops; j++)
-      if (!is_interchange_valid (scop, i, j))
+      if (!is_interchange_valid (scop, i, j, nb_loops))
 	{
 	  if (dump_file && (dump_flags & TDF_DETAILS))
 	    fprintf (dump_file,
@@ -5716,6 +5796,10 @@ graphite_trans_bb_block (graphite_bb_p gb, int stride, int loops)
   for (i = 1; i < nb_loops - start; i++)
     graphite_trans_bb_move_loop (gb, start + 2 * i, start + i);
 
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "\nLoops containing BB %d will be loop blocked.\n",
+	     GBB_BB (gb)->index);
+
   return true;
 }
 
@@ -5858,9 +5942,6 @@ graphite_trans_scop_block (scop_p scop)
     transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
   VEC_free (graphite_bb_p, heap, bbs);
 
-  if (dump_file && (dump_flags & TDF_DETAILS))
-    fprintf (dump_file, "\nLoop blocked.\n");
-
   return transform_done;
 }
 
@@ -5978,7 +6059,8 @@ graphite_transform_loops (void)
 
       build_scop_canonical_schedules (scop);
       build_bb_loops (scop);
-      build_scop_conditions (scop);
+      if (!build_scop_conditions (scop))
+	continue;
       find_scop_parameters (scop);
       build_scop_context (scop);
 
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 125ae61..4055cfc 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,16 @@
+2009-01-07  Jan Sjodin  <jan.sjodin@amd.com>
+
+	PR tree-optimization/38492
+	PR tree-optimization/38498
+	* testsuite/gcc.dg/graphite/pr38500.c: Fixed warning as committed
+	in trunk.
+	* testsuite/gcc.dg/graphite/block-0.c: Update test.
+	* testsuite/gcc.dg/graphite/block-1.c: Same.
+	* testsuite/gcc.dg/graphite/block-2.c: Remove xfail and test for blocking.
+	* testsuite/gcc.dg/graphite/block-4.c: Remove test for strip mine.
+	* testsuite/gcc.dg/graphite/block-3.c: New.
+	* testsuite/gcc.dg/graphite/pr38498.c: New.
+
 2009-01-07  H.J. Lu  <hongjiu.lu@intel.com>
 
 	AVX Programming Reference (December, 2008)
diff --git a/gcc/testsuite/gcc.dg/graphite/block-0.c b/gcc/testsuite/gcc.dg/graphite/block-0.c
index f277f05..627f044 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-0.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-0.c
@@ -21,5 +21,5 @@ main()
   return toto();
 }
 
-/* { dg-final { scan-tree-dump-times "Loop blocked" 1 "graphite"} } */ 
+/* { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite"} } */ 
 /* { dg-final { cleanup-tree-dump "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/block-1.c b/gcc/testsuite/gcc.dg/graphite/block-1.c
index 857f8d5..0a70e9e 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-1.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-1.c
@@ -36,5 +36,5 @@ int main()
   return sum;
 }
 
-/* { dg-final { scan-tree-dump-times "Loop blocked" 2 "graphite"} } */ 
+/* { dg-final { scan-tree-dump-times "will be loop blocked" 2 "graphite"} } */ 
 /* { dg-final { cleanup-tree-dump "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/block-2.c b/gcc/testsuite/gcc.dg/graphite/block-2.c
index cf0969b..fc4e889 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-2.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-2.c
@@ -28,5 +28,4 @@ void fallbackSort ( UInt32* fmap,
    }
    AssertH ( j < 256, 1005 );
 }
-/* { dg-final { scan-tree-dump-times "Loop blocked" 1 "graphite" { xfail *-*-* }} } */
 /* { dg-final { cleanup-tree-dump "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/block-3.c b/gcc/testsuite/gcc.dg/graphite/block-3.c
new file mode 100644
index 0000000..369df2f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/block-3.c
@@ -0,0 +1,25 @@
+/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */
+
+#define N 24
+#define M 1000
+
+float A[1000][1000][1000], B[1000][1000], C[1000][1000];
+
+void test (void)
+{
+  int i, j, k;
+
+  /* These loops contain too few iterations for being strip-mined by 64.  */
+  for (i = 0; i < 24; i++)
+    for (j = 0; j < 24; j++)
+      for (k = 0; k < 24; k++)
+        A[i][j][k] = B[i][k] * C[k][j];
+
+  /* These loops should still be strip mined.  */
+  for (i = 0; i < 1000; i++)
+    for (j = 0; j < 1000; j++)
+      for (k = 0; k < 1000; k++)
+        A[i][j][k] = B[i][k] * C[k][j];
+}
+
+/* { dg-final { cleanup-tree-dump "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/block-4.c b/gcc/testsuite/gcc.dg/graphite/block-4.c
index 4b550b4..e3649f0 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-4.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-4.c
@@ -9,18 +9,15 @@ void test (void)
 {
   int i, j, k;
 
-  /* These loops contain too few iterations for being strip-mined by 64.  */
   for (i = 0; i < 24; i++)
     for (j = 0; j < 24; j++)
       for (k = 0; k < 24; k++)
         A[i][j] = B[i][k] * C[k][j];
 
-  /* These loops should still be strip mined.  */
   for (i = 0; i < 1000; i++)
     for (j = 0; j < 1000; j++)
       for (k = 0; k < 1000; k++)
         A[i][j] = B[i][k] * C[k][j];
 }
 
-/* { dg-final { scan-tree-dump-times "Strip Mining is not profitable" 2 "graphite" } } */
 /* { dg-final { cleanup-tree-dump "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/pr38498.c b/gcc/testsuite/gcc.dg/graphite/pr38498.c
new file mode 100644
index 0000000..c79bbad
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/pr38498.c
@@ -0,0 +1,19 @@
+/* { dg-options "-O2 -floop-block" } */
+
+double test_vector (float **data, int rows, int cols, int vqrows,double epsilon, int maxiter,int **mean, int *map)
+{
+    int i, j, r, it;
+    double sqerr, prev_sqerr=0, t;
+    unsigned int *sel;
+    int *count;
+    for (it = 0;; it++) 
+    {
+        if ((sqerr == 0.0) || (it >= maxiter-1) ||((it > 0) && ( ((prev_sqerr - sqerr) / prev_sqerr) < epsilon )) )
+            for (i = 0; i < vqrows; i++) 
+            {
+                for (j = 0; j < cols; j++)
+                    mean[i][j] = 0.0;
+                count[i] = 0;
+            }
+    }
+}
diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c
index 26ae9b4..7a065b6 100644
--- a/gcc/tree-chrec.c
+++ b/gcc/tree-chrec.c
@@ -1430,3 +1430,64 @@ for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
     }
 }
 
+/* Returns true when the operation can be part of a linear
+   expression.  */
+
+static inline bool
+operator_is_linear (tree scev)
+{
+  switch (TREE_CODE (scev))
+    {
+    case INTEGER_CST:
+    case POLYNOMIAL_CHREC:
+    case PLUS_EXPR:
+    case POINTER_PLUS_EXPR:
+    case MULT_EXPR:
+    case MINUS_EXPR:
+    case NEGATE_EXPR:
+    case SSA_NAME:
+    case NON_LVALUE_EXPR:
+    CASE_CONVERT:
+      return true;
+
+    default:
+      return false;
+    }
+}
+
+/* Return true when SCEV is a linear expression.  Linear expressions
+   can contain additions, substractions and multiplications.
+   Multiplications are restricted to constant scaling: "cst * x".  */
+
+bool
+scev_is_linear_expression (tree scev)
+{
+  if (scev == NULL
+      || !operator_is_linear (scev))
+    return false;
+
+  if (TREE_CODE (scev) == MULT_EXPR)
+    return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
+	     && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
+
+  switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
+    {
+    case 3:
+      return scev_is_linear_expression (TREE_OPERAND (scev, 0))
+	&& scev_is_linear_expression (TREE_OPERAND (scev, 1))
+	&& scev_is_linear_expression (TREE_OPERAND (scev, 2));
+
+    case 2:
+      return scev_is_linear_expression (TREE_OPERAND (scev, 0))
+	&& scev_is_linear_expression (TREE_OPERAND (scev, 1));
+      
+    case 1:
+      return scev_is_linear_expression (TREE_OPERAND (scev, 0));
+
+    case 0:
+      return true;
+
+    default:
+      return false;
+    }
+}
diff --git a/gcc/tree-chrec.h b/gcc/tree-chrec.h
index d35dcd3..fa372a2 100644
--- a/gcc/tree-chrec.h
+++ b/gcc/tree-chrec.h
@@ -84,6 +84,7 @@ extern bool evolution_function_is_affine_multivariate_p (const_tree, int);
 extern bool evolution_function_is_univariate_p (const_tree);
 extern unsigned nb_vars_in_chrec (tree);
 extern bool evolution_function_is_invariant_p (tree, int);
+extern bool scev_is_linear_expression (tree);
 
 /* Determines whether CHREC is equal to zero.  */