From patchwork Wed Oct 12 06:35:46 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kugan Vivekanandarajah X-Patchwork-Id: 77531 Delivered-To: patch@linaro.org Received: by 10.140.97.247 with SMTP id m110csp320805qge; Tue, 11 Oct 2016 23:36:19 -0700 (PDT) X-Received: by 10.99.125.71 with SMTP id m7mr6467267pgn.58.1476254179698; Tue, 11 Oct 2016 23:36:19 -0700 (PDT) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id w9si4228100pgm.49.2016.10.11.23.36.19 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 11 Oct 2016 23:36:19 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-438284-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org; spf=pass (google.com: domain of gcc-patches-return-438284-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-438284-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :subject:to:references:cc:from:message-id:date:mime-version :in-reply-to:content-type; q=dns; s=default; b=N+az9GvYijS/LskwM fqV8lW9OZ8eskZXnm8d3xMOoVFoE5qrmMi5EaaojeF1odUMGemdHtQyUiKHBheAA Zlj8q4r+tRHJOCfCYkdArNJsV7h+Dyohk60UfxNhgia0EM/P/GwF8W86BaLHt9yG hB5UR0PRDxxQVLLdBRuM7blfvg= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :subject:to:references:cc:from:message-id:date:mime-version :in-reply-to:content-type; s=default; bh=T08In3FD+YM3GTf23tythhR 4BmA=; b=RuQBWx0H8Gv/jP3sgrBnZS6AjKpBDg0Iv7I5uAvBsaYAcq7T18zIcrp K1Z/5qCd/XfFyfcX/ue5pPm1s6kuyHlxGa01yH+hac6wXMKMemO+skMidEDSY2ZN QqknSr8jhijJa9arT+9PSG3PTnITw3J2QW6KRk7EZ9GsRXxwteAk= Received: (qmail 69947 invoked by alias); 12 Oct 2016 06:36:05 -0000 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 Received: (qmail 69926 invoked by uid 89); 12 Oct 2016 06:36:03 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.9 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=pushing, Attached X-HELO: mail-pf0-f177.google.com Received: from mail-pf0-f177.google.com (HELO mail-pf0-f177.google.com) (209.85.192.177) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 12 Oct 2016 06:35:53 +0000 Received: by mail-pf0-f177.google.com with SMTP id e6so13863619pfk.3 for ; Tue, 11 Oct 2016 23:35:53 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:subject:to:references:cc:from:message-id:date :user-agent:mime-version:in-reply-to; bh=W2alS+mWWjQPVGAnQ9PjrfRtjp+gaFNbFDxi4KwIlmc=; b=G6kNDxZEb4I32Aidx09wtE2C9xoYahFZl2kdvngOmQDKKG8Tx0kCFO16p137+cxhfx 6bUotCJNxUBW87Ulps0/dS1eIMTAxyLcyf/n8Lf+Nk8s1V7ehPFCcdjy/YFL4p2t8jN7 KqOH2EX1/u1RYxYB9au5jQ/JRy9blz4A436quvZ8D9P3JZelbdfs4FU2EvAnQgRe+wDw 0gS9r8uq1DeFVhPlJfvdUMp882CKW8kMs6kjersF2BB4nkK095MaWy3wNu6OryQ53C4P 4yNfHp5fxf4Eg5EieBYcIIs0E1BUB5vBX+zdGkZYXaqp1GBRur03/eLEsWiUJFc8REUt bh4A== X-Gm-Message-State: AA6/9RkbEvK0b8h/OdkqkXI19aPXslnPKpxm76hrj4ESsBywBdQNhODAK0q3cqA6D/DAhKMK X-Received: by 10.98.149.149 with SMTP id c21mr2902252pfk.100.1476254151885; Tue, 11 Oct 2016 23:35:51 -0700 (PDT) Received: from [10.1.1.7] (58-6-183-210.dyn.iinet.net.au. [58.6.183.210]) by smtp.gmail.com with ESMTPSA id f2sm8778511pfj.68.2016.10.11.23.35.49 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 11 Oct 2016 23:35:50 -0700 (PDT) Subject: Re: [RFC][VRP] Improve intersect_ranges To: Richard Biener References: <76edd771-749d-f85f-2d0e-84e714abb78e@linaro.org> <881b2805-15ec-ad68-96a5-e2debd2fb850@linaro.org> Cc: "gcc-patches@gcc.gnu.org" From: kugan Message-ID: <696145ed-2801-b342-ce7a-9e458ccb6909@linaro.org> Date: Wed, 12 Oct 2016 17:35:46 +1100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.3.0 MIME-Version: 1.0 In-Reply-To: X-IsSubscribed: yes Hi Richard, On 12/10/16 00:14, Richard Biener wrote: > On Tue, Oct 11, 2016 at 2:57 AM, kugan > wrote: >> Hi Richard, >>Hi Richard, >> >> On 10/10/16 20:13, Richard Biener wrote: >>> >>> On Sat, Oct 8, 2016 at 9:38 PM, kugan >>> wrote: >>>> >>>> Hi Richard, >>>> >>>> Thanks for the review. >>>> On 07/10/16 20:11, Richard Biener wrote: >>>>> >>>>> >>>>> On Fri, Oct 7, 2016 at 12:00 AM, kugan >>>>> wrote: >>>>>> >>>>>> >>>>>> Hi, >>>>>> >>>>>> In vrp intersect_ranges, Richard recently changed it to create integer >>>>>> value >>>>>> ranges when it is integer singleton. >>>>>> >>>>>> Maybe we should do the same when the other range is a complex ranges >>>>>> with >>>>>> SSA_NAME (like [x+2, +INF])? >>>>>> >>>>>> Attached patch tries to do this. There are cases where it will be >>>>>> beneficial >>>>>> as the testcase in the patch. (For this testcase to work with Early >>>>>> VRP, >>>>>> we >>>>>> need the patch posted at >>>>>> https://gcc.gnu.org/ml/gcc-patches/2016-10/msg00413.html) >>>>>> >>>>>> Bootstrapped and regression tested on x86_64-linux-gnu with no new >>>>>> regressions. >>>>> >>>>> >>>>> >>>>> This is not clearly a win, in fact it can completely lose an ASSERT_EXPR >>>>> because there is no way to add its effect back as an equivalence. The >>>>> current choice of always using the "left" keeps the ASSERT_EXPR range >>>>> and is able to record the other range via an equivalence. >>>> >>>> >>>> >>>> How about changing the order in Early VRP when we are dealing with the >>>> same >>>> SSA_NAME in inner and outer scope. Here is a patch that does this. Is >>>> this >>>> OK if no new regressions? >>> >>> >>> I'm not sure if this is a good way forward. The failure with the testcase >>> is >>> that we don't extract a range for k from if (j < k) which I believe >>> another >>> patch from you addresses? >> >> >> Yes, I have committed that. I am trying to add test cases for this and >> thats when I stumbled on this: >> >> For: >> foo (int k, int j) >> { >> : >> if (j_1(D) > 9) >> goto ; >> else >> goto ; >> >> : >> if (j_1(D) < k_2(D)) >> goto ; >> else >> goto ; >> >> : >> k_3 = k_2(D) + 1; >> if (k_2(D) <= 8) >> goto ; >> else >> goto ; >> >> : >> abort (); >> >> : >> return j_1(D); >> >> } >> >> Before we look at - if (j_1(D) < k_2(D)) >> j_1 (D) has [10, +INF] EQUIVALENCES: { j_1(D) } (1 elements) >> >> When we look at if (j_1(D) < k_2(D)) >> The range is [-INF, k_2(D) + -1] EQUIVALENCES: { j_1(D) } (1 elements) >> >> We intersect: >> [-INF, k_2(D) + -1] EQUIVALENCES: { j_1(D) } (1 elements) >> and >> [10, +INF] EQUIVALENCES: { j_1(D) } (1 elements) >> >> to >> [-INF, k_2(D) + -1] EQUIVALENCES: { j_1(D) } (1 elements) >> >> Due to this, in if (j_1(D) < k_2(D)) , we get pessimistic value range for >> k_2(D) > > Ah, but that is because when generating the range for k from j < k we > use the updated range for j. That obviously doens't make too much sense. > > @@ -10650,7 +10661,7 @@ public: > virtual void after_dom_children (basic_block); > void push_value_range (const_tree var, value_range *vr); > value_range *pop_value_range (const_tree var); > - void try_add_new_range (tree op, tree_code code, tree limit); > + value_range *try_add_new_range (tree op, tree_code code, tree limit); > > /* Cond_stack holds the old VR. */ > auto_vec > stack; > @@ -10661,7 +10672,7 @@ public: > > /* Add new range to OP such that (OP CODE LIMIT) is true. */ > > -void > +value_range * > evrp_dom_walker::try_add_new_range (tree op, tree_code code, tree limit) > { > value_range vr = VR_INITIALIZER; > @@ -10678,8 +10689,9 @@ evrp_dom_walker::try_add_new_range (tree > { > value_range *new_vr = vrp_value_range_pool.allocate (); > *new_vr = vr; > - push_value_range (op, new_vr); > + return new_vr; > } > + return NULL; > } > > /* See if there is any new scope is entered with new VR and set that VR to > @@ -10715,7 +10727,7 @@ evrp_dom_walker::before_dom_children (ba > code = invert_tree_comparison (gimple_cond_code (stmt), > HONOR_NANS (op0)); > /* Add VR when (OP0 CODE OP1) condition is true. */ > - try_add_new_range (op0, code, op1); > + value_range *op0_range = try_add_new_range (op0, code, op1); > > /* Register ranges for y in x < y where > y might have ranges that are useful. */ > @@ -10728,8 +10740,13 @@ evrp_dom_walker::before_dom_children (ba > &new_code, &limit)) > { > /* Add VR when (OP1 NEW_CODE LIMIT) condition is true. */ > - try_add_new_range (op1, new_code, limit); > + value_range *op1_range = try_add_new_range (op1, new_code, limit); > + if (op1_range) > + push_value_range (op1, op1_range); > } > + > + if (op0_range) > + push_value_range (op0, op0_range); > } > } > > > > seems to fix that and the issue. > Here is your patch with slight name change and ChangeLog. Bootstrapped and regression tested on x86_64-linux-gnu with no regressions. Is this OK for trunk? Thanks, Kugan gcc/ChangeLog: 2016-10-12 Richard Biener * tree-vrp.c (evrp_dom_walker::try_find_new_range): Renamed from try_add_new_range and made to return new range. (evrp_dom_walker::before_dom_children): Push op1 value range before pushing op0 value range. gcc/testsuite/ChangeLog: 2016-10-12 Kugan Vivekanandarajah * gcc.dg/tree-ssa/evrp6.c: New test. >> Thanks, >> Kugan >> >> >> >>> As said the issue is with the equivalence / value-range representation so >>> you can't do sth like >>> >>> /* Discover VR when condition is true. */ >>> extract_range_for_var_from_comparison_expr (op0, code, op0, op1, >>> &vr); >>> if (old_vr->type == VR_RANGE || old_vr->type == VR_ANTI_RANGE) >>> vrp_intersect_ranges (&vr, old_vr); >>> >>> /* If we found any usable VR, set the VR to ssa_name and create >>> a >>> PUSH old value in the stack with the old VR. */ >>> if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE) >>> { >>> new_vr = vrp_value_range_pool.allocate (); >>> *new_vr = vr; >>> push_value_range (op0, new_vr); >>> ->>> add equivalence to old_vr for new_vr. >>> >>> because old_vr and new_vr are the 'same' (they are associated with SSA >>> name op0) >>> >>> Richard. >>> >>>> Thanks, >>>> Kugan >>>> >>>> >>>> >>>> >>>> >>>>> My thought on this was that we need to separate "ranges" and associated >>>>> SSA names so we can introduce new ranges w/o the need for an SSA name >>>>> (and thus we can create an equivalence to the ASSERT_EXPR range). >>>>> IIRC I started on this at some point but never finished it ... >>>>> >>>>> Richard. >>>>> >>>>>> Thanks, >>>>>> Kugan >>>>>> >>>>>> >>>>>> gcc/testsuite/ChangeLog: >>>>>> >>>>>> 2016-10-07 Kugan Vivekanandarajah >>>>>> >>>>>> * gcc.dg/tree-ssa/evrp6.c: New test. >>>>>> >>>>>> gcc/ChangeLog: >>>>>> >>>>>> 2016-10-07 Kugan Vivekanandarajah >>>>>> >>>>>> * tree-vrp.c (intersect_ranges): If we failed to handle >>>>>> the intersection and the other range involves computation with >>>>>> symbolic values, choose integer range if available. >>>>>> >>>>>> >>>>>> >>>> >> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp6.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp6.c index e69de29..35d4d74 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/evrp6.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/evrp6.c @@ -0,0 +1,22 @@ + +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +extern void abort (void); + +int +foo (int k, int j) +{ + if (j >= 10) + { + if (j < k) + { + k++; + if (k < 10) + abort (); + } + } + + return j; +} +/* { dg-final { scan-tree-dump "\\\[12, \\+INF" "evrp" } } */ diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 8a129c6..c794e76 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -10650,7 +10650,7 @@ public: virtual void after_dom_children (basic_block); void push_value_range (const_tree var, value_range *vr); value_range *pop_value_range (const_tree var); - void try_add_new_range (tree op, tree_code code, tree limit); + value_range *try_find_new_range (tree op, tree_code code, tree limit); /* Cond_stack holds the old VR. */ auto_vec > stack; @@ -10659,10 +10659,10 @@ public: }; -/* Add new range to OP such that (OP CODE LIMIT) is true. */ +/* Find new range for OP such that (OP CODE LIMIT) is true. */ -void -evrp_dom_walker::try_add_new_range (tree op, tree_code code, tree limit) +value_range * +evrp_dom_walker::try_find_new_range (tree op, tree_code code, tree limit) { value_range vr = VR_INITIALIZER; value_range *old_vr = get_value_range (op); @@ -10678,8 +10678,9 @@ evrp_dom_walker::try_add_new_range (tree op, tree_code code, tree limit) { value_range *new_vr = vrp_value_range_pool.allocate (); *new_vr = vr; - push_value_range (op, new_vr); + return new_vr; } + return NULL; } /* See if there is any new scope is entered with new VR and set that VR to @@ -10715,7 +10716,7 @@ evrp_dom_walker::before_dom_children (basic_block bb) code = invert_tree_comparison (gimple_cond_code (stmt), HONOR_NANS (op0)); /* Add VR when (OP0 CODE OP1) condition is true. */ - try_add_new_range (op0, code, op1); + value_range *op0_range = try_find_new_range (op0, code, op1); /* Register ranges for y in x < y where y might have ranges that are useful. */ @@ -10728,8 +10729,13 @@ evrp_dom_walker::before_dom_children (basic_block bb) &new_code, &limit)) { /* Add VR when (OP1 NEW_CODE LIMIT) condition is true. */ - try_add_new_range (op1, new_code, limit); + value_range *op1_range = try_find_new_range (op1, new_code, limit); + if (op1_range) + push_value_range (op1, op1_range); } + + if (op0_range) + push_value_range (op0, op0_range); } }