[PATCH 5/7] Protect loops that might be executed zero times.

[Tobias Grosser <grosser@fim.uni-passau.de>]

From: grosser <grosser@138bc75d-0d04-0410-961f-82ee72b054a4>

2009-11-23  Tobias Grosser  <grosser@fim.uni-passau.de>

	PR middle-end/42130
	* graphite-clast-to-gimple.c (graphite_create_new_loop_guard,
	translate_clast_for_loop): New.
	(translate_clast_for): Add a condition around the loop, to do not
	execute loops with zero iterations.
	* testsuite/g++.dg/graphite/pr42130.C: New.
	* testsuite/gcc.dg/graphite/pr35356-2.c: Adapt.
---
 gcc/ChangeLog.graphite                    |   10 ++++
 gcc/graphite-clast-to-gimple.c            |   84 ++++++++++++++++++++++++++++-
 gcc/testsuite/g++.dg/graphite/pr42130.C   |   18 ++++++
 gcc/testsuite/gcc.dg/graphite/pr35356-2.c |   16 +++++-
 4 files changed, 124 insertions(+), 4 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/graphite/pr42130.C

diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index c705cbd..863b0be 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,15 @@
 2009-11-23  Tobias Grosser  <grosser@fim.uni-passau.de>
 
+	PR middle-end/42130
+	* graphite-clast-to-gimple.c (graphite_create_new_loop_guard,
+	translate_clast_for_loop): New.
+	(translate_clast_for): Add a condition around the loop, to do not
+	execute loops with zero iterations.
+	* testsuite/g++.dg/graphite/pr42130.C: New.
+	* testsuite/gcc.dg/graphite/pr35356-2.c: Adapt.
+
+2009-11-23  Tobias Grosser  <grosser@fim.uni-passau.de>
+
 	* graphite-clast-to-gimple.c (try_mark_loop_parallel): New.
 	(translate_clast_for, translate_clast_guard, translate_clast, gloog):
 	Remove context_loop and level.
diff --git a/gcc/graphite-clast-to-gimple.c b/gcc/graphite-clast-to-gimple.c
index 4f45708..3795f6f 100644
--- a/gcc/graphite-clast-to-gimple.c
+++ b/gcc/graphite-clast-to-gimple.c
@@ -768,8 +768,47 @@ try_mark_loop_parallel (sese region, loop_p loop, htab_t bb_pbb_mapping)
     loop->can_be_parallel = true;
 }
 
+static tree gcc_type_for_iv_of_clast_loop (struct clast_for *);
 
-/* Translates a clast for statement STMT to gimple.
+
+/* Creates a new if region protecting the loop to be executed, if the execution
+ * count is zero (lb > ub).  */
+static edge
+graphite_create_new_loop_guard (sese region, edge entry_edge,
+				struct clast_for *stmt,
+				VEC (tree, heap) *newivs,
+				htab_t newivs_index, htab_t params_index)
+{
+  tree cond_expr;
+  edge exit_edge;
+  tree type = gcc_type_for_iv_of_clast_loop (stmt);
+  tree lb = clast_to_gcc_expression (type, stmt->LB, region, newivs,
+				     newivs_index, params_index);
+  tree ub = clast_to_gcc_expression (type, stmt->UB, region, newivs,
+				     newivs_index, params_index);
+
+  /* XXX: Adding +1 and using LT_EXPR helps with loop latches that have a
+   * loop iteration count of "PARAMETER - 1".  For PARAMETER == 0 this becomes
+   * 2^{32|64}, and the condition lb <= ub is true, even if we do not want this.
+   * However lb < ub + 1 is false, as expected.
+   * There might be a problem with cases where ub is 2^32.  */
+  tree one;
+  Value gmp_one;
+  value_init (gmp_one);
+  value_set_si (gmp_one, 1);
+  one = gmp_cst_to_tree (type, gmp_one);
+  value_clear (gmp_one);
+
+  ub = fold_build2 (PLUS_EXPR, type, ub, one);
+  cond_expr = fold_build2 (LT_EXPR, boolean_type_node, lb, ub);
+
+  exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
+
+  return exit_edge;
+}
+
+
+/* Create the loop for a clast for statement.
 
    - REGION is the sese region we used to generate the scop.
    - NEXT_E is the edge where new generated code should be attached.
@@ -779,7 +818,7 @@ try_mark_loop_parallel (sese region, loop_p loop, htab_t bb_pbb_mapping)
    - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
      the sese region.  */
 static edge
-translate_clast_for (sese region, struct clast_for *stmt, edge next_e,
+translate_clast_for_loop (sese region, struct clast_for *stmt, edge next_e,
 		     htab_t rename_map, VEC (tree, heap) **newivs,
 		     htab_t newivs_index, htab_t bb_pbb_mapping,
 		     htab_t params_index)
@@ -802,6 +841,47 @@ translate_clast_for (sese region, struct clast_for *stmt, edge next_e,
   return last_e;
 }
 
+/* Translates a clast for statement STMT to gimple.  First a guard is created
+ * protecting the loop, if it is executed zero times.  In this guard we create
+ * the real loop structure.
+
+   - REGION is the sese region we used to generate the scop.
+   - NEXT_E is the edge where new generated code should be attached.
+   - RENAME_MAP contains a set of tuples of new names associated to
+     the original variables names.
+   - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
+   - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
+     the sese region.  */
+static edge
+translate_clast_for (sese region, struct clast_for *stmt, edge next_e,
+		     htab_t rename_map, VEC (tree, heap) **newivs,
+		     htab_t newivs_index, htab_t bb_pbb_mapping,
+		     htab_t params_index)
+{
+  edge last_e = graphite_create_new_loop_guard (region, next_e, stmt, *newivs,
+					   newivs_index, params_index);
+
+  edge true_e = get_true_edge_from_guard_bb (next_e->dest);
+  edge false_e = get_false_edge_from_guard_bb (next_e->dest);
+  edge exit_true_e = single_succ_edge (true_e->dest);
+  edge exit_false_e = single_succ_edge (false_e->dest);
+
+  htab_t before_guard = htab_create (10, rename_map_elt_info,
+				     eq_rename_map_elts, free);
+  htab_traverse (rename_map, copy_renames, before_guard);
+
+  next_e = translate_clast_for_loop (region, stmt, true_e, rename_map, newivs,
+				     newivs_index, bb_pbb_mapping,
+				     params_index);
+
+  insert_guard_phis (last_e->src, exit_true_e, exit_false_e,
+		     before_guard, rename_map);
+
+  htab_delete (before_guard);
+
+  return last_e;
+}
+
 /* Translates a clast guard statement STMT to gimple.
 
    - REGION is the sese region we used to generate the scop.
diff --git a/gcc/testsuite/g++.dg/graphite/pr42130.C b/gcc/testsuite/g++.dg/graphite/pr42130.C
new file mode 100644
index 0000000..92d3bd8
--- /dev/null
+++ b/gcc/testsuite/g++.dg/graphite/pr42130.C
@@ -0,0 +1,18 @@
+/* { dg-options "-O2 -fno-tree-ch" } */
+#include <vector>
+
+using std::vector;
+
+vector<unsigned> & __attribute__((noinline)) foo(unsigned n, unsigned k)
+{
+  vector<unsigned> *vv = new vector<unsigned>(n, 0u);
+  return *vv;
+}
+
+
+int main()
+{
+  foo(0, 1);
+}
+/* { dg-do run  } */
+
diff --git a/gcc/testsuite/gcc.dg/graphite/pr35356-2.c b/gcc/testsuite/gcc.dg/graphite/pr35356-2.c
index 5432dee..e5b0213 100644
--- a/gcc/testsuite/gcc.dg/graphite/pr35356-2.c
+++ b/gcc/testsuite/gcc.dg/graphite/pr35356-2.c
@@ -25,8 +25,20 @@ foo (int bar, int n, int k)
    | for (i = max(k+1,0); i < n; i++)
    |   a[i] = i;
 
+   XXX: At the moment we generate to protect loops that are executed zero times.
+
+   | if (0 < min (n, k) + 1)
+   |   for (i = 0; i < min (n, k); i++)
+   |     a[i] = i;
+   | if (k >= 0 && k < n)
+   |   a[k] = 1;
+   | if (0 < max(n, k) + 1)
+   |   for (i = max(k+1,0); i < n; i++)
+   |     a[i] = i;
+
 */
 
-/* { dg-final { scan-tree-dump-times "MIN_EXPR" 1 "graphite" } } */
-/* { dg-final { scan-tree-dump-times "MAX_EXPR" 1 "graphite" } } */
+
+/* { dg-final { scan-tree-dump-times "MIN_EXPR" 2 "graphite" } } */
+/* { dg-final { scan-tree-dump-times "MAX_EXPR" 2 "graphite" } } */
 /* { dg-final { cleanup-tree-dump "graphite" } } */
-- 
1.6.5.3