From patchwork Tue Jun 8 19:56:49 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 55025 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 325371009EA for ; Wed, 9 Jun 2010 05:57:25 +1000 (EST) Received: (qmail 31142 invoked by alias); 8 Jun 2010 19:57:23 -0000 Received: (qmail 31133 invoked by uid 22791); 8 Jun 2010 19:57:22 -0000 X-SWARE-Spam-Status: No, hits=-1.7 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, TW_GB, TW_TM X-Spam-Check-By: sourceware.org Received: from mail-pv0-f175.google.com (HELO mail-pv0-f175.google.com) (74.125.83.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 08 Jun 2010 19:57:12 +0000 Received: by pvc21 with SMTP id 21so474345pvc.20 for ; Tue, 08 Jun 2010 12:57:10 -0700 (PDT) Received: by 10.224.58.234 with SMTP id i42mr218623qah.96.1276027029161; Tue, 08 Jun 2010 12:57:09 -0700 (PDT) MIME-Version: 1.0 Received: by 10.224.19.137 with HTTP; Tue, 8 Jun 2010 12:56:49 -0700 (PDT) In-Reply-To: References: From: Sebastian Pop Date: Tue, 8 Jun 2010 14:56:49 -0500 Message-ID: Subject: Re: Does Graphite add useless constraints to the iteration domains? To: gcc-graphite , Tobias Grosser Cc: GCC Patches X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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