From patchwork Tue Jun 8 21:23:26 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 55036 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 54E79B7D48 for ; Wed, 9 Jun 2010 07:23:57 +1000 (EST) Received: (qmail 16934 invoked by alias); 8 Jun 2010 21:23:55 -0000 Received: (qmail 16924 invoked by uid 22791); 8 Jun 2010 21:23:54 -0000 X-SWARE-Spam-Status: No, hits=-1.8 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE X-Spam-Check-By: sourceware.org Received: from mail-pz0-f199.google.com (HELO mail-pz0-f199.google.com) (209.85.222.199) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 08 Jun 2010 21:23:48 +0000 Received: by pzk37 with SMTP id 37so2569093pzk.27 for ; Tue, 08 Jun 2010 14:23:46 -0700 (PDT) Received: by 10.224.87.106 with SMTP id v42mr10402948qal.23.1276032226264; Tue, 08 Jun 2010 14:23:46 -0700 (PDT) MIME-Version: 1.0 Received: by 10.224.19.137 with HTTP; Tue, 8 Jun 2010 14:23:26 -0700 (PDT) From: Sebastian Pop Date: Tue, 8 Jun 2010 16:23:26 -0500 Message-ID: Subject: [patch] Make scev instantiation call compute_overall_effect_of_inner_loop To: gcc-graphite , Tobias Grosser Cc: GCC Patches , Richard Guenther 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. So here is that other patch that makes the instantiation of the SCEVs call compute_overall_effect_of_inner_loop when the instantiation should happen in an outer loop than where the SSA_NAME was defined. Regstrap in progress on amd64-linux. Ok for trunk? Thanks, Sebastian From c7a2e1b80c1e1d3c1eb32000b6a70ce4c4f75ed8 Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Tue, 8 Jun 2010 13:21:56 -0500 Subject: [PATCH] Call compute_overall_effect_of_inner_loop from instantiate_scev_name. * tree-scalar-evolution.c (instantiate_scev_name): Do not fail the scev analysis when the variable is not used outside the loop in a close phi node: call compute_overall_effect_of_inner_loop. --- gcc/tree-scalar-evolution.c | 16 +++++++++++++--- 1 files changed, 13 insertions(+), 3 deletions(-) diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index bf564d8..5dce6af 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -2172,9 +2172,19 @@ instantiate_scev_name (basic_block instantiate_below, else res = chrec; - if (res == NULL_TREE - || !dominated_by_p (CDI_DOMINATORS, instantiate_below, - gimple_bb (SSA_NAME_DEF_STMT (res)))) + /* When ther is no loop_closed_phi_def, it means that the + variable is not used after the loop: try to still compute the + value of the variable when exiting the loop. */ + if (res == NULL_TREE) + { + loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec)); + res = analyze_scalar_evolution (loop, chrec); + res = compute_overall_effect_of_inner_loop (loop, res); + res = instantiate_scev_r (instantiate_below, evolution_loop, res, + fold_conversions, cache, size_expr); + } + else if (!dominated_by_p (CDI_DOMINATORS, instantiate_below, + gimple_bb (SSA_NAME_DEF_STMT (res)))) res = chrec_dont_know; } -- 1.7.0.4