Re: Does Graphite add useless constraints to the iteration domains?

[Sebastian Pop <sebpop at gmail dot com>]

On Tue, Jun 8, 2010 at 14:11, Sebastian Pop <sebpop@gmail.com> wrote:
> Hi,
>
> I remarked that in add_conditions_to_domain, we are adding the exit
> condition of a loop to the basic blocks following the loop.
> Why do we need to do this?
>
> The example I am looking at is a bit more complicated than this,
> but here is an abstraction that shows the problem:
>
> loop
> ?bb0:
> ? ?i_0 = phi (0, i_1)
> ? ?i_1 = i_0 + 1
> ? ?if (i_0 < 1000)
> ? ? ?goto bb1
> ? ?else
> ? ? ?goto bb2
>
> ?bb1:
> ? ? goto bb0
> end_loop
>
> bb2:
> ?S;
>
> We want to add the condition "i_0 >= 1000" to the domain of bb2, and
> this fails in my case as the scev analysis is not able to compute the
> overall effect of the inner loop on i_0. ?In the end I wrote a patch
> that makes scev return the right answer, and not surprisingly, in the
> simple example above, we insert a useless constraint: 1000 >= 1000.
>
> Tobias, do you see any reason to keep adding the loop exit condition
> to the basic blocks following the loop?

0002 removes these useless constraints.

0001 fixes comments and indentation.

These passed make -k check RUNTESTFLAGS=graphite.exp
If there are no objections by tomorrow, I will commit the attached
patches to the graphite branch for further test, and then once test
is finished, I will commit these patches to trunk.

Sebastian

From 74c6f7896fae8fc957f955eb689aaca189aefdf1 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Mon, 7 Jun 2010 13:43:13 -0500
Subject: [PATCH 1/2] Fix comments.

---
 gcc/graphite-poly.h         |    1 +
 gcc/graphite-sese-to-poly.c |   18 ++++++++++--------
 gcc/tree-chrec.c            |    6 ++++--
 gcc/tree-ssa-loop-niter.c   |    6 +++---
 4 files changed, 18 insertions(+), 13 deletions(-)

diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h
index 8ab24f9..5f858eb 100644
--- a/gcc/graphite-poly.h
+++ b/gcc/graphite-poly.h
@@ -388,6 +388,7 @@ number_of_write_pdrs (poly_bb_p pbb)
 }
 
 /* The basic block of the PBB.  */
+
 static inline basic_block
 pbb_bb (poly_bb_p pbb)
 {
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index e2d4192..584ff7c 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -1328,8 +1328,7 @@ add_condition_to_pbb (poly_bb_p pbb, gimple stmt, enum tree_code code)
 	(&right, left);
       add_condition_to_domain (left, stmt, pbb, LT_EXPR);
       add_condition_to_domain (right, stmt, pbb, GT_EXPR);
-      ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left,
-							       right);
+      ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left, right);
       ppl_delete_Pointset_Powerset_C_Polyhedron (right);
     }
   else
@@ -1344,12 +1343,11 @@ add_conditions_to_domain (poly_bb_p pbb)
   unsigned int i;
   gimple stmt;
   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
-  VEC (gimple, heap) *conditions = GBB_CONDITIONS (gbb);
 
-  if (VEC_empty (gimple, conditions))
+  if (VEC_empty (gimple, GBB_CONDITIONS (gbb)))
     return;
 
-  for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
+  for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gbb), i, stmt); i++)
     switch (gimple_code (stmt))
       {
       case GIMPLE_COND:
@@ -1357,7 +1355,7 @@ add_conditions_to_domain (poly_bb_p pbb)
 	    enum tree_code code = gimple_cond_code (stmt);
 
 	    /* The conditions for ELSE-branches are inverted.  */
-	    if (VEC_index (gimple, gbb->condition_cases, i) == NULL)
+	    if (!VEC_index (gimple, GBB_CONDITION_CASES (gbb), i))
 	      code = invert_tree_comparison (code, false);
 
 	    add_condition_to_pbb (pbb, stmt, code);
@@ -1409,12 +1407,14 @@ build_sese_conditions_before (struct dom_walk_data *dw_data,
   struct bsc *data = (struct bsc *) dw_data->global_data;
   VEC (gimple, heap) **conditions = data->conditions;
   VEC (gimple, heap) **cases = data->cases;
-  gimple_bb_p gbb = gbb_from_bb (bb);
-  gimple stmt = single_pred_cond (bb);
+  gimple_bb_p gbb;
+  gimple stmt;
 
   if (!bb_in_sese_p (bb, data->region))
     return;
 
+  stmt = single_pred_cond (bb);
+
   if (stmt)
     {
       edge e = single_pred_edge (bb);
@@ -1427,6 +1427,8 @@ build_sese_conditions_before (struct dom_walk_data *dw_data,
 	VEC_safe_push (gimple, heap, *cases, NULL);
     }
 
+  gbb = gbb_from_bb (bb);
+
   if (gbb)
     {
       GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c
index 24e1944..2d15285 100644
--- a/gcc/tree-chrec.c
+++ b/gcc/tree-chrec.c
@@ -1230,13 +1230,15 @@ convert_affine_scev (struct loop *loop, tree type,
 }
 
 
-/* Convert CHREC for the right hand side of a CREC.
+/* Convert CHREC for the right hand side of a CHREC.
    The increment for a pointer type is always sizetype.  */
+
 tree
 chrec_convert_rhs (tree type, tree chrec, gimple at_stmt)
 {
   if (POINTER_TYPE_P (type))
-   type = sizetype;
+    type = sizetype;
+
   return chrec_convert (type, chrec, at_stmt);
 }
 
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 279718e..1bad6ca 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -875,11 +875,11 @@ assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
      -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
 
      (where MAX is the maximum value of the unsigned variant of TYPE, and
-     the computations in this formula are performed in full precision
-     (without overflows).
+     the computations in this formula are performed in full precision,
+     i.e., without overflows).
 
      Usually, for loops with exit condition iv0->base + step * i < iv1->base,
-     we have a condition of form iv0->base - step < iv1->base before the loop,
+     we have a condition of the form iv0->base - step < iv1->base before the loop,
      and for loops iv0->base < iv1->base - step * i the condition
      iv0->base < iv1->base + step, due to loop header copying, which enable us
      to prove the lower bound.
-- 
1.7.0.4

From 5e729a6011d204766f1fdd7cb2ef14361f6e02c3 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Tue, 8 Jun 2010 14:35:04 -0500
Subject: [PATCH 2/2] Do not gather loop exit conditions on the basic blocks outside the loop.

---
 gcc/graphite-sese-to-poly.c |   19 +++++++++++++------
 1 files changed, 13 insertions(+), 6 deletions(-)

diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 584ff7c..770df0a 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -1379,21 +1379,28 @@ struct bsc
   sese region;
 };
 
-/* Returns non NULL when BB has a single predecessor and the last
-   statement of that predecessor is a COND_EXPR.  */
+/* Returns a COND_EXPR statement when BB has a single predecessor, the
+   edge between BB and its predecessor is not a loop exit edge, and
+   the last statement of the single predecessor is a COND_EXPR.  */
 
 static gimple
-single_pred_cond (basic_block bb)
+single_pred_cond_non_loop_exit (basic_block bb)
 {
   if (single_pred_p (bb))
     {
       edge e = single_pred_edge (bb);
       basic_block pred = e->src;
-      gimple stmt = last_stmt (pred);
+      gimple stmt;
+
+      if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
+	return NULL;
+
+      stmt = last_stmt (pred);
 
       if (stmt && gimple_code (stmt) == GIMPLE_COND)
 	return stmt;
     }
+
   return NULL;
 }
 
@@ -1413,7 +1420,7 @@ build_sese_conditions_before (struct dom_walk_data *dw_data,
   if (!bb_in_sese_p (bb, data->region))
     return;
 
-  stmt = single_pred_cond (bb);
+  stmt = single_pred_cond_non_loop_exit (bb);
 
   if (stmt)
     {
@@ -1450,7 +1457,7 @@ build_sese_conditions_after (struct dom_walk_data *dw_data,
   if (!bb_in_sese_p (bb, data->region))
     return;
 
-  if (single_pred_cond (bb))
+  if (single_pred_cond_non_loop_exit (bb))
     {
       VEC_pop (gimple, *conditions);
       VEC_pop (gimple, *cases);
-- 
1.7.0.4