Patchwork Does Graphite add useless constraints to the iteration domains?

login
register
mail settings
Submitter Sebastian Pop
Date June 8, 2010, 7:56 p.m.
Message ID <AANLkTimg5XJCtS79_49A6jt7tWGxXCLrENL77bQ6-DAS@mail.gmail.com>
Download mbox | patch
Permalink /patch/55025/
State New
Headers show

Comments

Sebastian Pop - June 8, 2010, 7:56 p.m.
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
Sebastian Pop - June 9, 2010, 11:41 p.m.
Sebastian Pop
--
AMD / Open Source Compiler Engineering / GNU Tools




On Tue, Jun 8, 2010 at 14:56, Sebastian Pop <sebpop@gmail.com> wrote:
> 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.
>

Committed to trunk r160509.

Patch

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