From patchwork Tue Aug 16 07:45:21 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kugan Vivekanandarajah X-Patchwork-Id: 73953 Delivered-To: patch@linaro.org Received: by 10.140.29.52 with SMTP id a49csp1854047qga; Tue, 16 Aug 2016 00:45:54 -0700 (PDT) X-Received: by 10.66.193.7 with SMTP id hk7mr61487161pac.78.1471333554698; Tue, 16 Aug 2016 00:45:54 -0700 (PDT) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id im1si23823284pab.45.2016.08.16.00.45.54 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 16 Aug 2016 00:45:54 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-434030-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-434030-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-434030-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:from :subject:to:references:cc:message-id:date:mime-version :in-reply-to:content-type; q=dns; s=default; b=n+JTi7Gx3WdVaRbVv Im/yEZgkSIubTyXwq9URZ3XZ9mrr3n+Mhhu02+ob4pKjw5kq3Uze4fAOQkqmDn9W hhidRZ42zbTY2Xh8h27qiBnvw136r6sO8sRosAh1i2u5v4riqU9XVRCktiTMgQLy I+sjPLtu8kohwWUoWWlAZMAf/Q= 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:from :subject:to:references:cc:message-id:date:mime-version :in-reply-to:content-type; s=default; bh=jnb8D7CZbnvE78YW/j8EPEl 0kAI=; b=mDO8EwtY4cey5tl57o8GPFGK8dIP8C/ttqxRZtD8pOGj6NBjaPSlYkR g3sMYQw1t5f9eHv62AQFKqRhGYlPTj8tlhSUo7FZN6vPGthR1fi19pZ/XQCOSXFv dOjKpHehHtKlZlgSEA6dtXyezIyk+L/V0dFc6zmEpHPFRvK6Trp8= Received: (qmail 26925 invoked by alias); 16 Aug 2016 07:45:41 -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 26906 invoked by uid 89); 16 Aug 2016 07:45:40 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.8 required=5.0 tests=AWL, BAYES_40, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 spammy=sk:calcula, Allocation, flip, preds X-HELO: mail-pa0-f48.google.com Received: from mail-pa0-f48.google.com (HELO mail-pa0-f48.google.com) (209.85.220.48) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 16 Aug 2016 07:45:28 +0000 Received: by mail-pa0-f48.google.com with SMTP id ti13so24043839pac.0 for ; Tue, 16 Aug 2016 00:45:28 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:subject:to:references:cc:message-id:date :user-agent:mime-version:in-reply-to; bh=5lWQq3IGipu3akvQdc84VRqaUlPtAd6TjhDVLRjAtLM=; b=g2jwiQ6Rtb3Cg1o7MZAGQOmqt3E1VEZj5oZA2RkZJWZ+Xh8+6jYImFfGuUH7lqJfnn Hqso/k/P+Zba8CBIN0/aNF4bS2lwYic9Mk0Qm8IQRi/K4xV/MSdDUCQ9a/RI9nmmLKCH +IJ3NsIZCjL5Yy4yGohtGBwhCF0+KEMMl4HN7Z3O3xf+0LWla3a/q30GlmWyzP7b4Aj2 FtaowuUUD36nUsBSLLIfLDpQqUb95epIijfvpIre6J0p+I4yBL0RrC9JD9db/sNhTRiS yp46Ba4gfSgSfxSVCH2gTHRqtgqj4Ed2B824ZShG+xV2EOXCQr3TVRUTgI9S/TweuX6k T8dg== X-Gm-Message-State: AEkoousYU7EtHuCh4osslZhYHTUNNS3ikbr91jxm0zaxhIfMbqR0cGL8PU4SWnzC7gYbU6Ki X-Received: by 10.66.250.196 with SMTP id ze4mr62350283pac.86.1471333527073; Tue, 16 Aug 2016 00:45:27 -0700 (PDT) Received: from [10.1.1.3] (58-6-183-210.dyn.iinet.net.au. [58.6.183.210]) by smtp.gmail.com with ESMTPSA id r21sm36595140pfi.52.2016.08.16.00.45.23 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 16 Aug 2016 00:45:26 -0700 (PDT) From: kugan Subject: Re: [RFC][IPA-VRP] Early VRP Implementation To: Richard Biener References: <57886949.8010300@linaro.org> <57886A71.6030103@linaro.org> <57888BD6.6070200@linaro.org> <578891C8.7090609@linaro.org> <19ff8188-aed7-0f9e-cc0b-0603698787ff@linaro.org> <48e42d0c-057c-312a-4e41-cd78c8b38b5e@linaro.org> Cc: Andrew Pinski , "gcc-patches@gcc.gnu.org" , Jan Hubicka , Martin Jambor Message-ID: Date: Tue, 16 Aug 2016 17:45:21 +1000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0 MIME-Version: 1.0 In-Reply-To: X-IsSubscribed: yes Hi Richard, On 12/08/16 20:43, Richard Biener wrote: > On Wed, Aug 3, 2016 at 3:17 AM, kugan wrote: [SNIP] > > diff --git a/gcc/common.opt b/gcc/common.opt > index 8a292ed..7028cd4 100644 > --- a/gcc/common.opt > +++ b/gcc/common.opt > @@ -2482,6 +2482,10 @@ ftree-vrp > Common Report Var(flag_tree_vrp) Init(0) Optimization > Perform Value Range Propagation on trees. > > +fdisable-tree-evrp > +Common Report Var(flag_disable_early_vrp) Init(0) Optimization > +Disable Early Value Range Propagation on trees. > + > > no please, this is automatically supported via -fdisable- I am now having -ftree-evrp which is enabled all the time. But This will only be used for disabling the early-vrp. That is, early-vrp will be run when ftree-vrp is enabled and ftree-evrp is not explicitly disabled. Is this OK? > > @@ -1728,11 +1736,12 @@ extract_range_from_assert (value_range *vr_p, tree expr) > always false. */ > > static void > -extract_range_from_ssa_name (value_range *vr, tree var) > +extract_range_from_ssa_name (value_range *vr, bool dom_p, tree var) > { > value_range *var_vr = get_value_range (var); > > - if (var_vr->type != VR_VARYING) > + if (var_vr->type != VR_VARYING > + && (!dom_p || var_vr->type != VR_UNDEFINED)) > copy_value_range (vr, var_vr); > else > set_value_range (vr, VR_RANGE, var, var, NULL); > > why do you need these changes? I think I already told you you need to > initialize the lattice to sth else than VR_UNDEFINED and that you can't > fully re-use update_value_range. If you don't want to do that then instead > of doing changes all over the place do it in get_value_range and have a > global flag. I have now added a global early_vrp_p and use this to initialize VR_INITIALIZER and get_value_range default to VR_VARYING. > > > @@ -3594,7 +3643,8 @@ extract_range_from_cond_expr (value_range *vr, > gassign *stmt) > on the range of its operand and the expression code. */ > > static void > -extract_range_from_comparison (value_range *vr, enum tree_code code, > +extract_range_from_comparison (value_range *vr, > + enum tree_code code, > tree type, tree op0, tree op1) > { > bool sop = false; > > remove these kind of no-op changes. Done. > > +/* Initialize local data structures for VRP. If DOM_P is true, > + we will be calling this from early_vrp where value range propagation > + is done by visiting stmts in dominator tree. ssa_propagate engine > + is not used in this case and that part of the ininitialization will > + be skipped. */ > > static void > -vrp_initialize (void) > +vrp_initialize (bool dom_p) > { > basic_block bb; > > @@ -6949,6 +7010,9 @@ vrp_initialize (void) > vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names); > bitmap_obstack_initialize (&vrp_equiv_obstack); > > + if (dom_p) > + return; > + > > split the function instead. > > @@ -7926,7 +7992,8 @@ vrp_visit_switch_stmt (gswitch *stmt, edge *taken_edge_p) > If STMT produces a varying value, return SSA_PROP_VARYING. */ > > static enum ssa_prop_result > -vrp_visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p) > +vrp_visit_stmt_worker (gimple *stmt, bool dom_p, edge *taken_edge_p, > + tree *output_p) > { > tree def; > ssa_op_iter iter; > @@ -7940,7 +8007,7 @@ vrp_visit_stmt (gimple *stmt, edge > *taken_edge_p, tree *output_p) > if (!stmt_interesting_for_vrp (stmt)) > gcc_assert (stmt_ends_bb_p (stmt)); > else if (is_gimple_assign (stmt) || is_gimple_call (stmt)) > - return vrp_visit_assignment_or_call (stmt, output_p); > + return vrp_visit_assignment_or_call (stmt, dom_p, output_p); > else if (gimple_code (stmt) == GIMPLE_COND) > return vrp_visit_cond_stmt (as_a (stmt), taken_edge_p); > else if (gimple_code (stmt) == GIMPLE_SWITCH) > @@ -7954,6 +8021,12 @@ vrp_visit_stmt (gimple *stmt, edge > *taken_edge_p, tree *output_p) > return SSA_PROP_VARYING; > } > > +static enum ssa_prop_result > +vrp_visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p) > +{ > + return vrp_visit_stmt_worker (stmt, false, taken_edge_p, output_p); > +} > > as said the refactoring that would be appreciated is to split out the > update_value_range calls > from the worker functions so you can call the respective functions > from the DOM implementations. > That they are globbed in vrp_visit_stmt currently is due to the API of > the SSA propagator. Sent this as separate patch for easy reviewing and testing. > > @@ -8768,6 +8842,12 @@ vrp_visit_phi_node (gphi *phi) > fprintf (dump_file, "\n"); > } > > + if (dom_p && vr_arg.type == VR_UNDEFINED) > + { > + set_value_range_to_varying (&vr_result); > + break; > + } > + > > eh... ok, so another way to attack this is, instead of initializing > the lattice to sth else > than VR_UNDEFINED, make sure to drop the lattice to varying for all PHI args on > yet unvisited incoming edges (you're not doing optimistic VRP). That's the only > place you _have_ to do it. Even when it is initialize (as I am doing now), we can still end up with VR_UNDEFINED during the propagation. I have just left the above so that we dont end up with the wrong VR. I also noticed that g++.dg/warn/pr33738.C testcase is now failing. This is because, with early-vrp setting value range ccp2 is optimizing without issuing a warning. I will look into it. bootstrap and regression testing is in progress. Thanks, Kugan >From 255054400db3f6cd20abc89f3735c7e488985c1e Mon Sep 17 00:00:00 2001 From: Kugan Vivekanandarajah Date: Mon, 15 Aug 2016 10:11:36 +1000 Subject: [PATCH 3/5] Add Early VRP --- gcc/common.opt | 4 + gcc/doc/invoke.texi | 9 + gcc/passes.def | 1 + gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C | 2 +- gcc/testsuite/gcc.dg/tree-ssa/evrp1.c | 13 + gcc/testsuite/gcc.dg/tree-ssa/evrp2.c | 18 ++ gcc/testsuite/gcc.dg/tree-ssa/evrp3.c | 15 ++ gcc/testsuite/gcc.dg/tree-ssa/pr22117.c | 2 +- gcc/testsuite/gcc.dg/tree-ssa/pr25382.c | 2 +- gcc/testsuite/gcc.dg/tree-ssa/vrp58.c | 4 +- gcc/testsuite/gcc.dg/tree-ssa/vrp67.c | 5 +- gcc/timevar.def | 1 + gcc/tree-pass.h | 1 + gcc/tree-vrp.c | 419 ++++++++++++++++++++++++++---- 14 files changed, 434 insertions(+), 62 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/evrp1.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/evrp2.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/evrp3.c diff --git a/gcc/common.opt b/gcc/common.opt index 65a9762..aec618e 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -2499,6 +2499,10 @@ ftree-vrp Common Report Var(flag_tree_vrp) Init(0) Optimization Perform Value Range Propagation on trees. +ftree-evrp +Common Report Var(flag_early_vrp) Init(1) Optimization +This can be used to disable Early Value Range Propagation on trees. + fsplit-paths Common Report Var(flag_split_paths) Init(0) Optimization Split paths leading to loop backedges. diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index d04be6f..3cad409 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -7715,6 +7715,10 @@ enabled by default at @option{-O2} and higher. Null pointer check elimination is only done if @option{-fdelete-null-pointer-checks} is enabled. +@item -fdisable-tree-evrp +@opindex fdisable-tree-evrp +Disables Early Value Range Propagation on trees. + @item -fsplit-paths @opindex fsplit-paths Split paths leading to loop backedges. This can improve dead code @@ -12350,6 +12354,11 @@ is made by appending @file{.slp} to the source file name. Dump each function after Value Range Propagation (VRP). The file name is made by appending @file{.vrp} to the source file name. +@item early vrp +@opindex fdump-tree-evrp +Dump each function after Early Value Range Propagation (EVRP). The file name +is made by appending @file{.evrp} to the source file name. + @item oaccdevlow @opindex fdump-tree-oaccdevlow Dump each function after applying device-specific OpenACC transformations. diff --git a/gcc/passes.def b/gcc/passes.def index 3647e90..ebd360b 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -89,6 +89,7 @@ along with GCC; see the file COPYING3. If not see execute TODO_rebuild_alias at this point. */ NEXT_PASS (pass_build_ealias); NEXT_PASS (pass_fre); + NEXT_PASS (pass_early_vrp); NEXT_PASS (pass_merge_phi); NEXT_PASS (pass_dse); NEXT_PASS (pass_cd_dce); diff --git a/gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C b/gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C index 5e09583..dce05d6 100644 --- a/gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C +++ b/gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O -fdump-tree-forwprop1" } */ +/* { dg-options "-O -fno-tree-evrp -fdump-tree-forwprop1" } */ #include diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp1.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp1.c new file mode 100644 index 0000000..8c6e4e6 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/evrp1.c @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +int foo (int i); +int bar (int j) +{ + if (j > 2) + return foo (j + 2); + else + return j; +} + +/* { dg-final { scan-tree-dump "\\\[5, \\+INF" "evrp" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp2.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp2.c new file mode 100644 index 0000000..e6d4235 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/evrp2.c @@ -0,0 +1,18 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +int foo (int i); +int bar2 (int j) +{ + if (j > 2) + { + if (j < 7) + return foo (j + 1); + else + return foo (j + 2); + } + return j; +} + + +/* { dg-final { scan-tree-dump "\\\[4, 7\\\]" "evrp" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp3.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp3.c new file mode 100644 index 0000000..1a3bbd5 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/evrp3.c @@ -0,0 +1,15 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +int foo (int i); +void bar (int j) +{ + unsigned int i; + for (i = 0; i < 10; ++i) + { + bar (i + 1); + } +} + +/* { dg-final { scan-tree-dump "\\\[1, 10\\\]" "evrp" } } */ + diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c b/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c index 7efdd63..d4fcdfe 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c @@ -3,7 +3,7 @@ known to be zero after entering the first two "if" statements. */ /* { dg-do compile } */ -/* { dg-options "-O2 -fdump-tree-vrp1" } */ +/* { dg-options "-O2 -fno-tree-evrp -fdump-tree-vrp1" } */ void link_error (void); diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr25382.c b/gcc/testsuite/gcc.dg/tree-ssa/pr25382.c index dcf9148..c4fda8b 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr25382.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr25382.c @@ -3,7 +3,7 @@ Check that VRP now gets ranges from BIT_AND_EXPRs. */ /* { dg-do compile } */ -/* { dg-options "-O2 -fno-tree-ccp -fdump-tree-vrp1" } */ +/* { dg-options "-O2 -fno-tree-ccp -fdump-tree-vrp" } */ int foo (int a) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp58.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp58.c index 5b44ae2..6df91ca 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp58.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp58.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fdump-tree-vrp1-details" } */ +/* { dg-options "-O2 -fdump-tree-evrp-details" } */ long long foo (long long a, signed char b, signed char c) @@ -9,4 +9,4 @@ foo (long long a, signed char b, signed char c) } /* { dg-final { scan-tree-dump "Folded into" "vrp1" { target int32plus } } } */ -/* { dg-final { scan-tree-dump "Folding statement: _\[0-9\]\* = \\(long long int\\) bc_\[0-9\]\*;" "vrp1" { target int16 } } } */ +/* { dg-final { scan-tree-dump "Folding statement: _\[0-9\]\* = \\(long long int\\) bc_\[0-9\]\*;" "evrp" { target int16 } } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c index ef5e8f9..ec1cc9a 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fdump-tree-vrp1" } */ +/* { dg-options "-O2 -fdump-tree-ccp2 -fdump-tree-vrp1" } */ extern void link_error (void); @@ -36,4 +36,5 @@ unsigned baz (unsigned i) return i; } -/* { dg-final { scan-tree-dump-times "Folding predicate" 3 "vrp1" } } */ +/* { dg-final { scan-tree-dump-times "Folding predicate" 1 "ccp2" } } */ +/* { dg-final { scan-tree-dump-times "Folding predicate" 2 "vrp1" } } */ diff --git a/gcc/timevar.def b/gcc/timevar.def index 5f12118..8837832 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -149,6 +149,7 @@ DEFTIMEVAR (TV_TREE_CFG , "tree CFG construction") DEFTIMEVAR (TV_TREE_CLEANUP_CFG , "tree CFG cleanup") DEFTIMEVAR (TV_TREE_TAIL_MERGE , "tree tail merge") DEFTIMEVAR (TV_TREE_VRP , "tree VRP") +DEFTIMEVAR (TV_TREE_EARLY_VRP , "tree Early VRP") DEFTIMEVAR (TV_TREE_COPY_PROP , "tree copy propagation") DEFTIMEVAR (TV_FIND_REFERENCED_VARS , "tree find ref. vars") DEFTIMEVAR (TV_TREE_PTA , "tree PTA") diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 36299a6..d836d57 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -440,6 +440,7 @@ extern gimple_opt_pass *make_pass_fre (gcc::context *ctxt); extern gimple_opt_pass *make_pass_check_data_deps (gcc::context *ctxt); extern gimple_opt_pass *make_pass_copy_prop (gcc::context *ctxt); extern gimple_opt_pass *make_pass_isolate_erroneous_paths (gcc::context *ctxt); +extern gimple_opt_pass *make_pass_early_vrp (gcc::context *ctxt); extern gimple_opt_pass *make_pass_vrp (gcc::context *ctxt); extern gimple_opt_pass *make_pass_uncprop (gcc::context *ctxt); extern gimple_opt_pass *make_pass_return_slot (gcc::context *ctxt); diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index b56ceec..1eb0fa7 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -62,7 +62,7 @@ along with GCC; see the file COPYING3. If not see #include "alloc-pool.h" #include "domwalk.h" -#define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL } +#define VR_INITIALIZER { early_vrp_p ? VR_VARYING: VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL } /* Allocation pools for tree-vrp allocations. */ static object_allocator vrp_value_range_pool ("Tree VRP value ranges"); @@ -72,6 +72,9 @@ static bitmap_obstack vrp_equiv_obstack; for still active basic-blocks. */ static sbitmap *live; +/* True if we are in DOM based Early VRP. */ +static bool early_vrp_p = false; + /* Return true if the SSA name NAME is live on the edge E. */ static bool @@ -669,6 +672,8 @@ get_value_range (const_tree var) /* Create a default value range. */ vr_value[ver] = vr = vrp_value_range_pool.allocate (); memset (vr, 0, sizeof (*vr)); + if (early_vrp_p) + vr->type = VR_VARYING; /* Defer allocating the equivalence set. */ vr->equiv = NULL; @@ -1441,44 +1446,17 @@ op_with_boolean_value_range_p (tree op) && integer_onep (vr->max)); } -/* Extract value range information from an ASSERT_EXPR EXPR and store - it in *VR_P. */ +/* Extract value range information for VAR when (OP COND_CODE LIMIT) is + true and store it in *VR_P. */ static void -extract_range_from_assert (value_range *vr_p, tree expr) +extract_range_for_var_from_comparison_expr (tree var, enum tree_code cond_code, + tree op, tree limit, + value_range *vr_p) { - tree var, cond, limit, min, max, type; + tree min, max, type; value_range *limit_vr; - enum tree_code cond_code; - - var = ASSERT_EXPR_VAR (expr); - cond = ASSERT_EXPR_COND (expr); - - gcc_assert (COMPARISON_CLASS_P (cond)); - - /* Find VAR in the ASSERT_EXPR conditional. */ - if (var == TREE_OPERAND (cond, 0) - || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR - || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR) - { - /* If the predicate is of the form VAR COMP LIMIT, then we just - take LIMIT from the RHS and use the same comparison code. */ - cond_code = TREE_CODE (cond); - limit = TREE_OPERAND (cond, 1); - cond = TREE_OPERAND (cond, 0); - } - else - { - /* If the predicate is of the form LIMIT COMP VAR, then we need - to flip around the comparison code to create the proper range - for VAR. */ - cond_code = swap_tree_comparison (TREE_CODE (cond)); - limit = TREE_OPERAND (cond, 0); - cond = TREE_OPERAND (cond, 1); - } - limit = avoid_overflow_infinity (limit); - type = TREE_TYPE (var); gcc_assert (limit != var); @@ -1524,15 +1502,15 @@ extract_range_from_assert (value_range *vr_p, tree expr) as well build the range [b_4, +INF] for it. One special case we handle is extracting a range from a range test encoded as (unsigned)var + CST <= limit. */ - if (TREE_CODE (cond) == NOP_EXPR - || TREE_CODE (cond) == PLUS_EXPR) + if (TREE_CODE (op) == NOP_EXPR + || TREE_CODE (op) == PLUS_EXPR) { - if (TREE_CODE (cond) == PLUS_EXPR) + if (TREE_CODE (op) == PLUS_EXPR) { - min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (cond, 1)), - TREE_OPERAND (cond, 1)); + min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (op, 1)), + TREE_OPERAND (op, 1)); max = int_const_binop (PLUS_EXPR, limit, min); - cond = TREE_OPERAND (cond, 0); + op = TREE_OPERAND (op, 0); } else { @@ -1716,6 +1694,41 @@ extract_range_from_assert (value_range *vr_p, tree expr) vrp_intersect_ranges (vr_p, get_value_range (var)); } +/* Extract value range information from an ASSERT_EXPR EXPR and store + it in *VR_P. */ + +static void +extract_range_from_assert (value_range *vr_p, tree expr) +{ + tree var = ASSERT_EXPR_VAR (expr); + tree cond = ASSERT_EXPR_COND (expr); + tree limit, op; + enum tree_code cond_code; + gcc_assert (COMPARISON_CLASS_P (cond)); + + /* Find VAR in the ASSERT_EXPR conditional. */ + if (var == TREE_OPERAND (cond, 0) + || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR + || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR) + { + /* If the predicate is of the form VAR COMP LIMIT, then we just + take LIMIT from the RHS and use the same comparison code. */ + cond_code = TREE_CODE (cond); + limit = TREE_OPERAND (cond, 1); + op = TREE_OPERAND (cond, 0); + } + else + { + /* If the predicate is of the form LIMIT COMP VAR, then we need + to flip around the comparison code to create the proper range + for VAR. */ + cond_code = swap_tree_comparison (TREE_CODE (cond)); + limit = TREE_OPERAND (cond, 0); + op = TREE_OPERAND (cond, 1); + } + extract_range_for_var_from_comparison_expr (var, cond_code, op, + limit, vr_p); +} /* Extract range information from SSA name VAR and store it in VR. If VAR has an interesting range, use it. Otherwise, create the @@ -6938,19 +6951,28 @@ stmt_interesting_for_vrp (gimple *stmt) return false; } - -/* Initialize local data structures for VRP. */ +/* Initialize VRP lattice. */ static void -vrp_initialize (void) +vrp_initialize_lattice () { - basic_block bb; - values_propagated = false; num_vr_values = num_ssa_names; vr_value = XCNEWVEC (value_range *, num_vr_values); vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names); bitmap_obstack_initialize (&vrp_equiv_obstack); +} + +/* Initialize local data structures for VRP. If DOM_P is true, + we will be calling this from early_vrp where value range propagation + is done by visiting stmts in dominator tree. ssa_propagate engine + is not used in this case and that part of the ininitialization will + be skipped. */ + +static void +vrp_initialize () +{ + basic_block bb; FOR_EACH_BB_FN (bb, cfun) { @@ -8803,6 +8825,12 @@ vrp_visit_phi_node_worker (gphi *phi, value_range *vr_result) fprintf (dump_file, "\n"); } + if (early_vrp_p && vr_arg.type == VR_UNDEFINED) + { + set_value_range_to_varying (vr_result); + break; + } + if (first) copy_value_range (vr_result, &vr_arg); else @@ -8831,6 +8859,7 @@ vrp_visit_phi_node_worker (gphi *phi, value_range *vr_result) simulate this PHI again with the same number of edges then iterate one more time. */ if (edges > 0 + && !early_vrp_p && gimple_phi_num_args (phi) > 1 && edges == old_edges && lhs_vr->type != VR_UNDEFINED @@ -8898,7 +8927,8 @@ scev_check: scev_check can be reached from two paths, one is a fall through from above "varying" label, the other is direct goto from code block which tries to avoid infinite simulation. */ - if ((l = loop_containing_stmt (phi)) + if (!early_vrp_p + && (l = loop_containing_stmt (phi)) && l->header == gimple_bb (phi)) adjust_range_with_scev (vr_result, l, phi, lhs); @@ -10419,6 +10449,22 @@ finalize_jump_threads (void) delete equiv_stack; } +/* Free VRP lattice. */ + +static void +vrp_free_lattice () +{ + /* Free allocated memory. */ + free (vr_value); + free (vr_phi_edge_counts); + bitmap_obstack_release (&vrp_equiv_obstack); + vrp_value_range_pool.release (); + + /* So that we can distinguish between VRP data being available + and not available. */ + vr_value = NULL; + vr_phi_edge_counts = NULL; +} /* Traverse all the blocks folding conditionals with known ranges. */ @@ -10465,17 +10511,237 @@ vrp_finalize (bool warn_array_bounds_p) /* We must identify jump threading opportunities before we release the datastructures built by VRP. */ identify_jump_threads (); +} - /* Free allocated memory. */ - free (vr_value); - free (vr_phi_edge_counts); - bitmap_obstack_release (&vrp_equiv_obstack); - vrp_value_range_pool.release (); +/* Check to see if the PHI stmt has any back edges. In dominator based + VRP, if we have back-edges, we will have to set the resulting VR to + varying. This is because we dont iteratetively visit the stmt till + we reach fixed point. */ - /* So that we can distinguish between VRP data being available - and not available. */ - vr_value = NULL; - vr_phi_edge_counts = NULL; +static bool +visit_phi_node_p (gphi *phi) +{ + for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++) + { + edge e = gimple_phi_arg_edge (phi, i); + if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX)) + return false; + } + return true; +} + +/* evrp_dom_walker visits the basic blocks in the dominance order and set + the Value Ranges (VR) for SSA_NAMEs in the scope. Use this VR to + discover more VRs. */ + +class evrp_dom_walker : public dom_walker +{ +public: + evrp_dom_walker () + : dom_walker (CDI_DOMINATORS), stack (10) {} + + virtual edge before_dom_children (basic_block); + 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); + + /* Cond_stack holds the old VR. */ + auto_vec > stack; +}; + +/* See if there is any new scope is entered with new VR and set that VR to + ssa_name before visiting the statements in the scope. */ + +edge +evrp_dom_walker::before_dom_children (basic_block bb) +{ + value_range *new_vr = NULL; + tree op0 = NULL_TREE; + push_value_range (NULL_TREE, NULL); + if (single_pred_p (bb)) + { + edge e = single_pred_edge (bb); + value_range vr = VR_INITIALIZER; + gimple *stmt = last_stmt (e->src); + if (stmt + && gimple_code (stmt) == GIMPLE_COND + && (op0 = gimple_cond_lhs (stmt)) + && TREE_CODE (op0) == SSA_NAME + && INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))) + { + /* Entering a new scope. Try to see if we can find a VR + here. */ + tree op1 = gimple_cond_rhs (stmt); + tree_code code = gimple_cond_code (stmt); + value_range *old_vr = get_value_range (op0); + + if (TREE_OVERFLOW_P (op1)) + op1 = drop_tree_overflow (op1); + + /* If condition is false, invert the cond. */ + if (e->flags & EDGE_FALSE_VALUE) + code = invert_tree_comparison (gimple_cond_code (stmt), + HONOR_NANS (op0)); + /* 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); + } + } + } + + /* Visit PHI stmts and discover any new VRs possible. */ + gimple_stmt_iterator gsi; + for (gphi_iterator gpi = gsi_start_phis (bb); + !gsi_end_p (gpi); gsi_next (&gpi)) + { + gphi *phi = gpi.phi (); + if (stmt_interesting_for_vrp (phi)) + { + tree lhs = PHI_RESULT (phi); + value_range vr_result = VR_INITIALIZER; + /* See if the PHI has any back edges. If there is any + backedges we will have to set the lattice to + VR_VARYING as we will not be traversing it till it + reach fix point. */ + if (visit_phi_node_p (phi)) + vrp_visit_phi_node_worker (phi, &vr_result); + else + set_value_range_to_varying (&vr_result); + update_value_range (lhs, &vr_result); + } + } + + /* Visit all other stmts and discover any new VRs possible. */ + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple *stmt = gsi_stmt (gsi); + edge taken_edge; + tree output; + /* TODO, if found taken_edge, we should visit (return it) and travel + again to improve VR as done in DOM/SCCVN optimizations. It should + be done carefully as stmts might prematurely leave a BB like + in EH. */ + if (stmt_interesting_for_vrp (stmt)) + { + tree lhs = gimple_get_lhs (stmt); + value_range vr = VR_INITIALIZER; + vrp_visit_stmt_worker (stmt, &taken_edge, &output, &vr); + update_value_range (lhs, &vr); + + /* Try folding stmts with the VR discovered. */ + if (fold_stmt (&gsi, follow_single_use_edges)) + update_stmt (gsi_stmt (gsi)); + + def_operand_p def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF); + /* Set the SSA with the value range. */ + if (def_p + && TREE_CODE (DEF_FROM_PTR (def_p)) == SSA_NAME + && INTEGRAL_TYPE_P (TREE_TYPE (DEF_FROM_PTR (def_p)))) + { + tree def = DEF_FROM_PTR (def_p); + unsigned ver = SSA_NAME_VERSION (def); + if ((vr_value[ver]->type == VR_RANGE + || vr_value[ver]->type == VR_ANTI_RANGE) + && (TREE_CODE (vr_value[ver]->min) == INTEGER_CST) + && (TREE_CODE (vr_value[ver]->max) == INTEGER_CST)) + set_range_info (def, vr_value[ver]->type, vr_value[ver]->min, + vr_value[ver]->max); + } + } + } + return NULL; +} + +/* Restore/pop VRs valid only for BB when we leave BB. */ + +void +evrp_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED) +{ + gcc_checking_assert (!stack.is_empty ()); + while (stack.last ().first != NULL_TREE) + pop_value_range (stack.last ().first); + pop_value_range (stack.last ().first); +} + +/* Push the Value Range of VAR to the stack and update it with new VR. */ + +void +evrp_dom_walker::push_value_range (const_tree var, value_range *vr) +{ + if (vr != NULL) + { + unsigned ver = SSA_NAME_VERSION (var); + gcc_checking_assert (vr_value); + stack.safe_push (std::make_pair (var, vr_value[ver])); + + if (ver < num_vr_values) + vr_value[ver] = vr; + } + else + stack.safe_push (std::make_pair (var, vr)); +} + +/* Pop the Value Range from the vrp_stack and update VAR with it. */ + +value_range * +evrp_dom_walker::pop_value_range (const_tree var) +{ + value_range *vr = stack.last ().second; + if (vr != NULL) + { + unsigned ver = SSA_NAME_VERSION (var); + gcc_checking_assert (var == stack.last ().first); + gcc_checking_assert (vr_value); + + if (ver < num_vr_values) + vr_value[ver] = vr; + } + stack.pop (); + return vr; +} + + +/* Main entry point for the early vrp pass which is a simplified non-iterative + version of VRP where basic blocks are visited in dominance order. Value + ranges discovered in early vrp will also be used by ipa-vrp. */ + +static unsigned int +execute_early_vrp () +{ + edge e; + edge_iterator ei; + basic_block bb; + early_vrp_p = true; + + calculate_dominance_info (CDI_DOMINATORS); + FOR_EACH_BB_FN (bb, cfun) + { + FOR_EACH_EDGE (e, ei, bb->preds) + e->flags |= EDGE_EXECUTABLE; + } + vrp_initialize_lattice (); + + /* Walk stmts in dominance order and propagate VRP. */ + evrp_dom_walker walker; + walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); + if (dump_file) + { + fprintf (dump_file, "\nValue ranges after Early VRP:\n\n"); + dump_all_value_ranges (dump_file); + fprintf (dump_file, "\n"); + } + vrp_free_lattice (); + early_vrp_p = false; + return 0; } @@ -10546,9 +10812,11 @@ execute_vrp (bool warn_array_bounds_p) /* For visiting PHI nodes we need EDGE_DFS_BACK computed. */ mark_dfs_back_edges (); + vrp_initialize_lattice (); vrp_initialize (); ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node); vrp_finalize (warn_array_bounds_p); + vrp_free_lattice (); free_numbers_of_iterations_estimates (cfun); @@ -10646,3 +10914,44 @@ make_pass_vrp (gcc::context *ctxt) { return new pass_vrp (ctxt); } + +namespace { + +const pass_data pass_data_early_vrp = +{ + GIMPLE_PASS, /* type */ + "evrp", /* name */ + OPTGROUP_NONE, /* optinfo_flags */ + TV_TREE_EARLY_VRP, /* tv_id */ + PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ), +}; + +class pass_early_vrp : public gimple_opt_pass +{ +public: + pass_early_vrp (gcc::context *ctxt) + : gimple_opt_pass (pass_data_early_vrp, ctxt) + {} + + /* opt_pass methods: */ + opt_pass * clone () { return new pass_early_vrp (m_ctxt); } + virtual bool gate (function *) + { + return flag_early_vrp != 0 && flag_tree_vrp != 0; + } + virtual unsigned int execute (function *) + { return execute_early_vrp (); } + +}; // class pass_vrp +} // anon namespace + +gimple_opt_pass * +make_pass_early_vrp (gcc::context *ctxt) +{ + return new pass_early_vrp (ctxt); +} + -- 2.7.4