From patchwork Tue Jun 8 19:56:49 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: Does Graphite add useless constraints to the iteration domains? Date: Tue, 08 Jun 2010 09:56:49 -0000 From: Sebastian Pop X-Patchwork-Id: 55025 Message-Id: To: gcc-graphite , Tobias Grosser Cc: GCC Patches On Tue, Jun 8, 2010 at 14:11, Sebastian Pop 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 5e729a6011d204766f1fdd7cb2ef14361f6e02c3 Mon Sep 17 00:00:00 2001 From: Sebastian Pop 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