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.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@143159 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 96013c1..b379b1b 100644 (file)
--- 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)
 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 b03e061..645def2 100644 (file)
--- 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);
 }
 
   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
 /* 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 (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)
           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);
 
   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)
   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;
 
        }
       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;
     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)
 {
 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;
   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))
   
   /* 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)
     {
   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);
                /* 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);
 
                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);
              }
                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)));
 
                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;
 
                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.  */
 
                /* 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))
                  {
                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++)
 
                /* 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_unordered_remove (basic_block, dom, j);
                      break;

-                   }  
+                   }

              }
 
            VEC_pop (gimple, *conditions);
            VEC_pop (gimple, *cases);
            break;
          }
              }
 
            VEC_pop (gimple, *conditions);
            VEC_pop (gimple, *cases);
            break;
          }

+

        default:
          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++)
 
   /* 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);
   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)
 {
 build_scop_conditions (scop_p scop)
 {

+  bool res;

   VEC (gimple, heap) *conditions = NULL;
   VEC (gimple, heap) *cases = NULL;
 
   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);
 
   VEC_free (gimple, heap, conditions);
   VEC_free (gimple, heap, cases);

+  return res;

 }
 
 /* Build the current domain matrix: the loops belonging to the current
 }
 
 /* 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);
          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);
        }
       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);
          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);
        }
          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);
     {
       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)
       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:",
       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");
        }
     }
          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
 }
  
 /* 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
 
 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);
 {
   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);
   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++)
 
   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,
        {
          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);
 
   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;
 }
 
   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);
 
     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;
 }
 
   return transform_done;
 }
 


@@ -5978,7 +6059,8 @@ graphite_transform_loops (void)
 
       build_scop_canonical_schedules (scop);
       build_bb_loops (scop);
 
       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);
 
       find_scop_parameters (scop);
       build_scop_context (scop);
 

diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 125ae61..4055cfc 100644 (file)
--- 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)
 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 (file)
--- 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();
 }
 
   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" } } */
 /* { 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 (file)
--- 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;
 }
 
   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" } } */
 /* { 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 (file)
--- 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 );
 }
    }
    AssertH ( j < 256, 1005 );
 }

-/* { dg-final { scan-tree-dump-times "Loop blocked" 1 "graphite" { xfail *-*-* }} } */

 /* { dg-final { cleanup-tree-dump "graphite" } } */
 /* { 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 (file)
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 (file)
--- 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;
 
 {
   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];
 
   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];
 }
 
   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" } } */
 /* { 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 (file)
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 (file)
--- 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 (file)
--- 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 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.  */
 
 
 /* Determines whether CHREC is equal to zero.  */