From patchwork Tue Aug 30 05:20:58 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kugan Vivekanandarajah X-Patchwork-Id: 74934 Delivered-To: patch@linaro.org Received: by 10.140.29.52 with SMTP id a49csp1961909qga; Mon, 29 Aug 2016 22:21:27 -0700 (PDT) X-Received: by 10.67.7.228 with SMTP id df4mr1013027pad.24.1472534487036; Mon, 29 Aug 2016 22:21:27 -0700 (PDT) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id y8si43189729pab.178.2016.08.29.22.21.26 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 29 Aug 2016 22:21:27 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-434897-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-434897-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-434897-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 :mime-version:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; q=dns; s=default; b=YlxCd0DRRsAG5iW tXUhfmz3fY094/lPnC0xql2WhFzZTZY+UtsbJxN+5TzQJBcdzLZohqf2iyDjXks9 6Kp+XbxukiOjQq6OzRiDwLYDLfnVfSngbBLtJe+6rjq+lz6M4iNYo1SE7KUuUJPa 3snDoN6w+ASo6OFehqeFsNvdEjxM= 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 :mime-version:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; s=default; bh=Vwcg9VCMFobrMi7yucknM UOerRw=; b=drfYptqUQZSFlEfdu6wLt9WqszVMM5C2tCSLGsjD9o7333Wy6gpc5 3H2rMSQ8CvY1yjH79WG8NgM5PypgvAxaDhf19sMkfcUo54+Ecs2uIzm9uQK6vVbg 20kT3SMv2naowR4H0JqDofNoIyt6ugZhmBuNscK3iYnMmeI2C9plyY= Received: (qmail 61777 invoked by alias); 30 Aug 2016 05:21:12 -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 61764 invoked by uid 89); 30 Aug 2016 05:21:11 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=2.3 required=5.0 tests=BAYES_95, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=no version=3.3.2 spammy=Meet, lat, UD:ipa-prop.c, sk:stream_ X-HELO: mail-qt0-f178.google.com Received: from mail-qt0-f178.google.com (HELO mail-qt0-f178.google.com) (209.85.216.178) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 30 Aug 2016 05:21:01 +0000 Received: by mail-qt0-f178.google.com with SMTP id 52so4126681qtq.3 for ; Mon, 29 Aug 2016 22:21:01 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=CIKfYCm6ax9nyfyB7ihHGjpyGjcotVetOBSTlnzqCwA=; b=ftIoBKY7aGIUEd3e+4wRjvlSdseK8xJfq5zq8Ge8u1bdo1uCxDiu6EV7tR/urF3g2a gXZ0m1+4x/ZfSnRw3jcA84BsDuzvuCkXNKCxaNY7KVruyiDyS6mOKtrxlQh3KLz4rqXz gyF7sR7wuiSvcng0Tu7DdCAp8JHMJQXeoahcirJiO0uP5qNm15TzibS+q4aA+38YY8Q7 /fPAiVVNnNnWsJ3RbQ2UraZIptcaMEcLZ0uaPfRtPoZu9BOqvj01FQ6pcqC3VEnL8NtV uqEOAUrIq1mnX/3/BavqQl1A9ZpMspcsxSNUyOi+lo2cVEEVueeV7HdfB3sqTafLTSUX mJkw== X-Gm-Message-State: AE9vXwN5f2zzuH8PtPoyQi+LkPa7SC5/k4XFcPetokKDDhKXSAcgv9MB0++pvU5XKsTK+9z/gieJ315RWDn0GgvC X-Received: by 10.237.37.216 with SMTP id y24mr1981404qtc.58.1472534459598; Mon, 29 Aug 2016 22:20:59 -0700 (PDT) MIME-Version: 1.0 Received: by 10.200.53.49 with HTTP; Mon, 29 Aug 2016 22:20:58 -0700 (PDT) In-Reply-To: <20160721125416.GA23760@kam.mff.cuni.cz> References: <57886949.8010300@linaro.org> <57886A2A.4070703@linaro.org> <57886ABA.2060404@linaro.org> <20160715122309.glir5vk5ttwoagdp@virgil.suse.cz> <578DE340.4010904@linaro.org> <578E9B16.2080100@linaro.org> <20160721125416.GA23760@kam.mff.cuni.cz> From: Kugan Vivekanandarajah Date: Tue, 30 Aug 2016 15:20:58 +1000 Message-ID: Subject: Re: [RFC][IPA-VRP] Add support for IPA VRP in ipa-cp/ipa-prop To: Jan Hubicka Cc: "gcc-patches@gcc.gnu.org" , Richard Biener X-IsSubscribed: yes Hi Honza, Here is a re-based version which also addresses the review comments. On 21/07/16 22:54, Jan Hubicka wrote: >> Maybe it is better to separate value range and alignment summary >> writing/reading to different functions. Here is another updated >> version which does this. > > Makes sense to me. Note that the alignment summary propagation can be either > handled by doing bitwise constant propagation and/or extending our value ranges > by stride (as described in > http://www.lighterra.com/papers/valuerangeprop/Patterson1995-ValueRangeProp.pdf > I would like it to go eventually away in favour of more generic solution. > >> -/* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches >> +/* Propagate value range across jump function JFUNC that is associated with >> + edge CS and update DEST_PLATS accordingly. */ >> + >> +static bool >> +propagate_vr_accross_jump_function (cgraph_edge *cs, >> + ipa_jump_func *jfunc, >> + struct ipcp_param_lattices *dest_plats) >> +{ >> + struct ipcp_param_lattices *src_lats; >> + ipcp_vr_lattice *dest_lat = &dest_plats->m_value_range; >> + >> + if (dest_lat->bottom_p ()) >> + return false; >> + >> + if (jfunc->type == IPA_JF_PASS_THROUGH) >> + { >> + struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); >> + int src_idx = ipa_get_jf_pass_through_formal_id (jfunc); >> + src_lats = ipa_get_parm_lattices (caller_info, src_idx); >> + >> + if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR) >> + return dest_lat->meet_with (src_lats->m_value_range); > > Clearly we can propagate thorugh expressions here (PLUS_EXPR). I have run > into similar issue in loop code that builds simple generic expresisons > (like (int)ssa_name+10) and it would be nice to have easy way to deterine > their value range based on the knowledge of SSA_NAME's valur range. > > Bit this is fine for initial implementaiotn for sure. Indeed. I will do this as a follow up. >> >> +/* Look up all VR information that we have discovered and copy it over >> + to the transformation summary. */ >> + >> +static void >> +ipcp_store_vr_results (void) >> +{ >> + cgraph_node *node; >> + >> + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) >> + { >> + ipa_node_params *info = IPA_NODE_REF (node); >> + bool found_useful_result = false; >> + >> + if (!opt_for_fn (node->decl, flag_ipa_vrp)) >> + { >> + if (dump_file) >> + fprintf (dump_file, "Not considering %s for VR discovery " >> + "and propagate; -fipa-ipa-vrp: disabled.\n", >> + node->name ()); >> + continue; > > I belive you need to also prevent propagation through functions copmiled with > -fno-ipa-vrp, not only prevent any transformations. Do you mean the following, I was following other implementations. @@ -2264,6 +2430,11 @@ propagate_constants_accross_call (struct cgraph_edge *cs) &dest_plats->bits_lattice); ret |= propagate_aggs_accross_jump_function (cs, jump_func, dest_plats); + if (opt_for_fn (callee->decl, flag_ipa_vrp)) + ret |= propagate_vr_accross_jump_function (cs, + jump_func, dest_plats); + else + ret |= dest_plats->m_value_range.set_to_bottom (); >> +/* Update value range of formal parameters as described in >> + ipcp_transformation_summary. */ >> + >> +static void >> +ipcp_update_vr (struct cgraph_node *node) >> +{ >> + tree fndecl = node->decl; >> + tree parm = DECL_ARGUMENTS (fndecl); >> + tree next_parm = parm; >> + ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node); >> + if (!ts || vec_safe_length (ts->m_vr) == 0) >> + return; >> + const vec &vr = *ts->m_vr; >> + unsigned count = vr.length (); >> + >> + for (unsigned i = 0; i < count; ++i, parm = next_parm) >> + { >> + if (node->clone.combined_args_to_skip >> + && bitmap_bit_p (node->clone.combined_args_to_skip, i)) >> + continue; >> + gcc_checking_assert (parm); >> + next_parm = DECL_CHAIN (parm); >> + tree ddef = ssa_default_def (DECL_STRUCT_FUNCTION (node->decl), parm); >> + >> + if (!ddef || !is_gimple_reg (parm)) >> + continue; >> + >> + if (cgraph_local_p (node) > The test of cgraph_local_p seems redundant here. The analysis phase should not determine > anything if function is reachable non-locally. Removed it. >> +/* Info about value ranges. */ >> + >> +struct GTY(()) ipa_vr >> +{ >> + /* The data fields below are valid only if known is true. */ >> + bool known; >> + enum value_range_type type; >> + tree min; >> + tree max; > What is the point of representing range as trees rather than wide ints. Can they > be non-constant integer? Changed to wide_int after adding that support. LTO Bootstrapped and regression tested on x86_64-linux-gnu with no new regressions, is this OK? Thanks Kugan >From c6687f60001695dd71316e894010a764cb15606a Mon Sep 17 00:00:00 2001 From: Kugan Vivekanandarajah Date: Tue, 23 Aug 2016 19:47:58 +1000 Subject: [PATCH 2/3] Add ipa-vrp --- gcc/cgraph.c | 1 + gcc/cgraphunit.c | 1 + gcc/common.opt | 4 + gcc/ipa-cp.c | 243 ++++++++++++++++++++++++++++++++ gcc/ipa-devirt.c | 1 + gcc/ipa-inline-transform.c | 1 + gcc/ipa-inline.c | 1 + gcc/ipa-profile.c | 1 + gcc/ipa-prop.c | 180 ++++++++++++++++++++++- gcc/ipa-prop.h | 16 +++ gcc/ipa-utils.c | 1 + gcc/ipa.c | 1 + gcc/lto/lto-partition.c | 1 + gcc/lto/lto.c | 1 + gcc/opts.c | 1 + gcc/testsuite/g++.dg/ipa/pure-const-3.C | 2 +- gcc/testsuite/gcc.dg/ipa/vrp1.c | 32 +++++ gcc/testsuite/gcc.dg/ipa/vrp2.c | 35 +++++ gcc/testsuite/gcc.dg/ipa/vrp3.c | 30 ++++ gcc/toplev.c | 1 + 20 files changed, 547 insertions(+), 7 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/ipa/vrp1.c create mode 100644 gcc/testsuite/gcc.dg/ipa/vrp2.c create mode 100644 gcc/testsuite/gcc.dg/ipa/vrp3.c diff --git a/gcc/cgraph.c b/gcc/cgraph.c index 9bc5b6b..0a43850 100644 --- a/gcc/cgraph.c +++ b/gcc/cgraph.c @@ -49,6 +49,7 @@ along with GCC; see the file COPYING3. If not see #include "value-prof.h" #include "ipa-utils.h" #include "symbol-summary.h" +#include "tree-vrp.h" #include "ipa-prop.h" #include "ipa-inline.h" #include "cfgloop.h" diff --git a/gcc/cgraphunit.c b/gcc/cgraphunit.c index 6a1d126..5588807 100644 --- a/gcc/cgraphunit.c +++ b/gcc/cgraphunit.c @@ -190,6 +190,7 @@ along with GCC; see the file COPYING3. If not see #include "toplev.h" #include "debug.h" #include "symbol-summary.h" +#include "tree-vrp.h" #include "ipa-prop.h" #include "gimple-pretty-print.h" #include "plugin.h" diff --git a/gcc/common.opt b/gcc/common.opt index fd1ac87..79ee799 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -1601,6 +1601,10 @@ fipa-struct-reorg Common Ignore Does nothing. Preserved for backward compatibility. +fipa-vrp +Common Report Var(flag_ipa_vrp) Optimization +Perform IPA Value Range Propagation. + fira-algorithm= Common Joined RejectNegative Enum(ira_algorithm) Var(flag_ira_algorithm) Init(IRA_ALGORITHM_CB) Optimization -fira-algorithm=[CB|priority] Set the used IRA algorithm. diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c index 9514dd1..dacef4c 100644 --- a/gcc/ipa-cp.c +++ b/gcc/ipa-cp.c @@ -114,6 +114,7 @@ along with GCC; see the file COPYING3. If not see #include "fold-const.h" #include "gimple-fold.h" #include "symbol-summary.h" +#include "tree-vrp.h" #include "ipa-prop.h" #include "tree-pretty-print.h" #include "tree-inline.h" @@ -321,6 +322,25 @@ private: void get_value_and_mask (tree, widest_int *, widest_int *); }; +/* Lattice of value ranges. */ + +class ipcp_vr_lattice +{ +public: + value_range m_vr; + + inline bool bottom_p () const; + inline bool top_p () const; + inline bool set_to_bottom (); + bool meet_with (const value_range *p_vr); + bool meet_with (const ipcp_vr_lattice &other); + void init () { m_vr.type = VR_UNDEFINED; } + void print (FILE * f); + +private: + bool meet_with_1 (const value_range *other_vr); +}; + /* Structure containing lattices for a parameter itself and for pieces of aggregates that are passed in the parameter or by a reference in a parameter plus some other useful flags. */ @@ -338,6 +358,8 @@ public: ipcp_alignment_lattice alignment; /* Lattice describing known bits. */ ipcp_bits_lattice bits_lattice; + /* Lattice describing value range. */ + ipcp_vr_lattice m_value_range; /* Number of aggregate lattices */ int aggs_count; /* True if aggregate data were passed by reference (as opposed to by @@ -405,6 +427,16 @@ ipa_get_poly_ctx_lat (struct ipa_node_params *info, int i) return &plats->ctxlat; } +/* Return the lattice corresponding to the value range of the Ith formal + parameter of the function described by INFO. */ + +static inline ipcp_vr_lattice * +ipa_get_vr_lat (struct ipa_node_params *info, int i) +{ + struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); + return &plats->m_value_range; +} + /* Return whether LAT is a lattice with a single constant and without an undefined value. */ @@ -530,6 +562,14 @@ ipcp_bits_lattice::print (FILE *f) } } +/* Print value range lattice to F. */ + +void +ipcp_vr_lattice::print (FILE * f) +{ + dump_value_range (f, &m_vr); +} + /* Print all ipcp_lattices of all functions to F. */ static void @@ -557,6 +597,9 @@ print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits) plats->ctxlat.print (f, dump_sources, dump_benefits); plats->alignment.print (f); plats->bits_lattice.print (f); + fprintf (f, " "); + plats->m_value_range.print (f); + fprintf (f, "\n"); if (plats->virt_call) fprintf (f, " virt_call flag set\n"); @@ -908,6 +951,77 @@ ipcp_alignment_lattice::set_to_bottom () return true; } +/* Meet the current value of the lattice with described by OTHER + lattice. */ + +bool +ipcp_vr_lattice::meet_with (const ipcp_vr_lattice &other) +{ + return meet_with_1 (&other.m_vr); +} + +/* Meet the current value of the lattice with value ranfge described by VR + lattice. */ + +bool +ipcp_vr_lattice::meet_with (const value_range *p_vr) +{ + return meet_with_1 (p_vr); +} + +/* Meet the current value of the lattice with value ranfge described by + OTHER_VR lattice. */ + +bool +ipcp_vr_lattice::meet_with_1 (const value_range *other_vr) +{ + tree min = m_vr.min, max = m_vr.max; + value_range_type type = m_vr.type; + + if (bottom_p ()) + return false; + + if (other_vr->type == VR_VARYING) + return set_to_bottom (); + + vrp_meet (&m_vr, other_vr); + if (type != m_vr.type + || min != m_vr.min + || max != m_vr.max) + return true; + else + return false; +} + +/* Return true if value range information in the lattice is yet unknown. */ + +bool +ipcp_vr_lattice::top_p () const +{ + return m_vr.type == VR_UNDEFINED; +} + +/* Return true if value range information in the lattice is known to be + unusable. */ + +bool +ipcp_vr_lattice::bottom_p () const +{ + return m_vr.type == VR_VARYING; +} + +/* Set value range information in the lattice to bottom. Return true if it + previously was in a different state. */ + +bool +ipcp_vr_lattice::set_to_bottom () +{ + if (m_vr.type == VR_VARYING) + return false; + m_vr.type = VR_VARYING; + return true; +} + /* Meet the current value of the lattice with alignment described by NEW_ALIGN and NEW_MISALIGN, assuming that we know the current value is neither TOP nor BOTTOM. Return true if the value of lattice has changed. */ @@ -1141,6 +1255,7 @@ set_all_contains_variable (struct ipcp_param_lattices *plats) ret |= set_agg_lats_contain_variable (plats); ret |= plats->alignment.set_to_bottom (); ret |= plats->bits_lattice.set_to_bottom (); + ret |= plats->m_value_range.set_to_bottom (); return ret; } @@ -1211,6 +1326,12 @@ initialize_node_lattices (struct cgraph_node *node) disable = true; } + for (i = 0; i < ipa_get_param_count (info) ; i++) + { + struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); + plats->m_value_range.init (); + } + if (disable || variable) { for (i = 0; i < ipa_get_param_count (info) ; i++) @@ -1223,6 +1344,7 @@ initialize_node_lattices (struct cgraph_node *node) set_agg_lats_to_bottom (plats); plats->alignment.set_to_bottom (); plats->bits_lattice.set_to_bottom (); + plats->m_value_range.set_to_bottom (); } else set_all_contains_variable (plats); @@ -1913,6 +2035,50 @@ propagate_bits_accross_jump_function (cgraph_edge *cs, int idx, ipa_jump_func *j return dest_lattice->set_to_bottom (); } +/* Propagate value range across jump function JFUNC that is associated with + edge CS and update DEST_PLATS accordingly. */ + +static bool +propagate_vr_accross_jump_function (cgraph_edge *cs, + ipa_jump_func *jfunc, + struct ipcp_param_lattices *dest_plats) +{ + struct ipcp_param_lattices *src_lats; + ipcp_vr_lattice *dest_lat = &dest_plats->m_value_range; + + if (dest_lat->bottom_p ()) + return false; + + if (jfunc->type == IPA_JF_PASS_THROUGH) + { + struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); + if (dest_lat->bottom_p ()) + return false; + int src_idx = ipa_get_jf_pass_through_formal_id (jfunc); + src_lats = ipa_get_parm_lattices (caller_info, src_idx); + + if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR) + return dest_lat->meet_with (src_lats->m_value_range); + } + else if (jfunc->type == IPA_JF_CONST) + { + tree val = ipa_get_jf_constant (jfunc); + if (TREE_CODE (val) == INTEGER_CST) + { + jfunc->vr_known = true; + jfunc->m_vr.type = VR_RANGE; + jfunc->m_vr.min = val; + jfunc->m_vr.max = val; + return dest_lat->meet_with (&jfunc->m_vr); + } + } + + if (jfunc->vr_known) + return dest_lat->meet_with (&jfunc->m_vr); + else + return dest_lat->set_to_bottom (); +} + /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all other cases, return false). If there are no aggregate items, set @@ -2264,6 +2430,11 @@ propagate_constants_accross_call (struct cgraph_edge *cs) &dest_plats->bits_lattice); ret |= propagate_aggs_accross_jump_function (cs, jump_func, dest_plats); + if (opt_for_fn (callee->decl, flag_ipa_vrp)) + ret |= propagate_vr_accross_jump_function (cs, + jump_func, dest_plats); + else + ret |= dest_plats->m_value_range.set_to_bottom (); } } for (; i < parms_count; i++) @@ -4974,6 +5145,76 @@ ipcp_store_bits_results (void) } } } + +/* Look up all VR information that we have discovered and copy it over + to the transformation summary. */ + +static void +ipcp_store_vr_results (void) +{ + cgraph_node *node; + + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) + { + ipa_node_params *info = IPA_NODE_REF (node); + bool found_useful_result = false; + + if (!opt_for_fn (node->decl, flag_ipa_vrp)) + { + if (dump_file) + fprintf (dump_file, "Not considering %s for VR discovery " + "and propagate; -fipa-ipa-vrp: disabled.\n", + node->name ()); + continue; + } + + if (info->ipcp_orig_node) + info = IPA_NODE_REF (info->ipcp_orig_node); + + unsigned count = ipa_get_param_count (info); + for (unsigned i = 0; i < count ; i++) + { + ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); + if (!plats->m_value_range.bottom_p () + && !plats->m_value_range.top_p ()) + { + found_useful_result = true; + break; + } + } + if (!found_useful_result) + continue; + + ipcp_grow_transformations_if_necessary (); + ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node); + vec_safe_reserve_exact (ts->m_vr, count); + + for (unsigned i = 0; i < count ; i++) + { + ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); + ipa_vr vr; + + if (!plats->m_value_range.bottom_p () + && !plats->m_value_range.top_p ()) + { + vr.known = true; + vr.type = plats->m_value_range.m_vr.type; + vr.min = plats->m_value_range.m_vr.min; + vr.max = plats->m_value_range.m_vr.max; + } + else + { + static wide_int zero = integer_zero_node; + vr.known = false; + vr.type = VR_VARYING; + vr.min = zero; + vr.max = zero; + } + ts->m_vr->quick_push (vr); + } + } +} + /* The IPCP driver. */ static unsigned int @@ -5009,6 +5250,8 @@ ipcp_driver (void) ipcp_store_alignment_results (); /* Store results of bits propagation. */ ipcp_store_bits_results (); + /* Store results of value range propagation. */ + ipcp_store_vr_results (); /* Free all IPCP structures. */ free_toporder_info (&topo); diff --git a/gcc/ipa-devirt.c b/gcc/ipa-devirt.c index 2cf018b..62a08f8 100644 --- a/gcc/ipa-devirt.c +++ b/gcc/ipa-devirt.c @@ -122,6 +122,7 @@ along with GCC; see the file COPYING3. If not see #include "ipa-utils.h" #include "gimple-fold.h" #include "symbol-summary.h" +#include "tree-vrp.h" #include "ipa-prop.h" #include "ipa-inline.h" #include "demangle.h" diff --git a/gcc/ipa-inline-transform.c b/gcc/ipa-inline-transform.c index 98c7f96..efe7421 100644 --- a/gcc/ipa-inline-transform.c +++ b/gcc/ipa-inline-transform.c @@ -39,6 +39,7 @@ along with GCC; see the file COPYING3. If not see #include "cgraph.h" #include "tree-cfg.h" #include "symbol-summary.h" +#include "tree-vrp.h" #include "ipa-prop.h" #include "ipa-inline.h" #include "tree-inline.h" diff --git a/gcc/ipa-inline.c b/gcc/ipa-inline.c index 5c9366a..82bb94f 100644 --- a/gcc/ipa-inline.c +++ b/gcc/ipa-inline.c @@ -108,6 +108,7 @@ along with GCC; see the file COPYING3. If not see #include "params.h" #include "profile.h" #include "symbol-summary.h" +#include "tree-vrp.h" #include "ipa-prop.h" #include "ipa-inline.h" #include "ipa-utils.h" diff --git a/gcc/ipa-profile.c b/gcc/ipa-profile.c index da17bcd..e87615a 100644 --- a/gcc/ipa-profile.c +++ b/gcc/ipa-profile.c @@ -62,6 +62,7 @@ along with GCC; see the file COPYING3. If not see #include "value-prof.h" #include "tree-inline.h" #include "symbol-summary.h" +#include "tree-vrp.h" #include "ipa-prop.h" #include "ipa-inline.h" diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c index 1629781..9d040f9 100644 --- a/gcc/ipa-prop.c +++ b/gcc/ipa-prop.c @@ -311,6 +311,19 @@ ipa_print_node_jump_functions_for_edge (FILE *f, struct cgraph_edge *cs) } else fprintf (f, " Unknown bits\n"); + + if (jump_func->vr_known) + { + fprintf (f, " VR "); + fprintf (f, "%s[", + (jump_func->m_vr.type == VR_ANTI_RANGE) ? "~" : ""); + print_decs (jump_func->m_vr.min, f); + fprintf (f, ", "); + print_decs (jump_func->m_vr.max, f); + fprintf (f, "]\n"); + } + else + fprintf (f, " Unknown VR\n"); } } @@ -391,6 +404,7 @@ ipa_set_jf_unknown (struct ipa_jump_func *jfunc) jfunc->type = IPA_JF_UNKNOWN; jfunc->alignment.known = false; jfunc->bits.known = false; + jfunc->vr_known = false; } /* Set JFUNC to be a copy of another jmp (to be used by jump function @@ -1680,9 +1694,28 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi, } else gcc_assert (!jfunc->alignment.known); + gcc_assert (!jfunc->vr_known); } else - gcc_assert (!jfunc->alignment.known); + { + wide_int min, max; + value_range_type type; + if (TREE_CODE (arg) == SSA_NAME + && param_type + && (type = get_range_info (arg, &min, &max)) + && (type == VR_RANGE || type == VR_ANTI_RANGE) + && (min.get_precision () <= TYPE_PRECISION (param_type) + || TYPE_OVERFLOW_WRAPS (param_type))) + { + jfunc->vr_known = true; + jfunc->m_vr.type = type; + jfunc->m_vr.min = wide_int_to_tree (param_type, min); + jfunc->m_vr.max = wide_int_to_tree (param_type, max); + } + else + gcc_assert (!jfunc->vr_known); + gcc_assert (!jfunc->alignment.known); + } if (INTEGRAL_TYPE_P (TREE_TYPE (arg)) && (TREE_CODE (arg) == SSA_NAME || TREE_CODE (arg) == INTEGER_CST)) @@ -3709,16 +3742,28 @@ ipa_node_params_t::duplicate(cgraph_node *src, cgraph_node *dst, ipcp_transformation_summary *src_trans = ipcp_get_transformation_summary (src); - if (src_trans && vec_safe_length (src_trans->alignments) > 0) + if (src_trans) { ipcp_grow_transformations_if_necessary (); src_trans = ipcp_get_transformation_summary (src); const vec *src_alignments = src_trans->alignments; + const vec *src_vr = src_trans->m_vr; vec *&dst_alignments = ipcp_get_transformation_summary (dst)->alignments; - vec_safe_reserve_exact (dst_alignments, src_alignments->length ()); - for (unsigned i = 0; i < src_alignments->length (); ++i) - dst_alignments->quick_push ((*src_alignments)[i]); + vec *&dst_vr + = ipcp_get_transformation_summary (dst)->m_vr; + if (vec_safe_length (src_trans->alignments) > 0) + { + vec_safe_reserve_exact (dst_alignments, src_alignments->length ()); + for (unsigned i = 0; i < src_alignments->length (); ++i) + dst_alignments->quick_push ((*src_alignments)[i]); + } + if (vec_safe_length (src_trans->m_vr) > 0) + { + vec_safe_reserve_exact (dst_vr, src_vr->length ()); + for (unsigned i = 0; i < src_vr->length (); ++i) + dst_vr->quick_push ((*src_vr)[i]); + } } if (src_trans && vec_safe_length (src_trans->bits) > 0) @@ -4660,6 +4705,15 @@ ipa_write_jump_function (struct output_block *ob, streamer_write_widest_int (ob, jump_func->bits.value); streamer_write_widest_int (ob, jump_func->bits.mask); } + bp_pack_value (&bp, jump_func->vr_known, 1); + streamer_write_bitpack (&bp); + if (jump_func->vr_known) + { + streamer_write_enum (ob->main_stream, value_rang_type, + VR_LAST, jump_func->m_vr.type); + stream_write_tree (ob, jump_func->m_vr.min, true); + stream_write_tree (ob, jump_func->m_vr.max, true); + } } /* Read in jump function JUMP_FUNC from IB. */ @@ -4747,6 +4801,20 @@ ipa_read_jump_function (struct lto_input_block *ib, } else jump_func->bits.known = false; + + struct bitpack_d vr_bp = streamer_read_bitpack (ib); + bool vr_known = bp_unpack_value (&vr_bp, 1); + if (vr_known) + { + jump_func->vr_known = true; + jump_func->m_vr.type = streamer_read_enum (ib, + value_range_type, + VR_LAST); + jump_func->m_vr.min = stream_read_tree (ib, data_in); + jump_func->m_vr.max = stream_read_tree (ib, data_in); + } + else + jump_func->vr_known = false; } /* Stream out parts of cgraph_indirect_call_info corresponding to CS that are @@ -5113,7 +5181,29 @@ write_ipcp_transformation_info (output_block *ob, cgraph_node *node) else streamer_write_uhwi (ob, 0); - ts = ipcp_get_transformation_summary (node); + if (ts && vec_safe_length (ts->m_vr) > 0) + { + count = ts->m_vr->length (); + streamer_write_uhwi (ob, count); + for (unsigned i = 0; i < count; ++i) + { + struct bitpack_d bp; + ipa_vr *parm_vr = &(*ts->m_vr)[i]; + bp = bitpack_create (ob->main_stream); + bp_pack_value (&bp, parm_vr->known, 1); + streamer_write_bitpack (&bp); + if (parm_vr->known) + { + streamer_write_enum (ob->main_stream, value_rang_type, + VR_LAST, parm_vr->type); + streamer_write_wide_int (ob, parm_vr->min); + streamer_write_wide_int (ob, parm_vr->max); + } + } + } + else + streamer_write_uhwi (ob, 0); + if (ts && vec_safe_length (ts->bits) > 0) { count = ts->bits->length (); @@ -5191,6 +5281,30 @@ read_ipcp_transformation_info (lto_input_block *ib, cgraph_node *node, if (count > 0) { ipcp_grow_transformations_if_necessary (); + + ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node); + vec_safe_grow_cleared (ts->m_vr, count); + for (i = 0; i < count; i++) + { + ipa_vr *parm_vr; + parm_vr = &(*ts->m_vr)[i]; + struct bitpack_d bp; + bp = streamer_read_bitpack (ib); + parm_vr->known = bp_unpack_value (&bp, 1); + if (parm_vr->known) + { + parm_vr->type = streamer_read_enum (ib, value_range_type, + VR_LAST); + parm_vr->min = streamer_read_wide_int (ib); + parm_vr->max = streamer_read_wide_int (ib); + } + } + } + count = streamer_read_uhwi (ib); + if (count > 0) + { + ipcp_grow_transformations_if_necessary (); + ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node); vec_safe_grow_cleared (ts->bits, count); @@ -5558,6 +5672,59 @@ ipcp_update_bits (struct cgraph_node *node) } } +/* Update value range of formal parameters as described in + ipcp_transformation_summary. */ + +static void +ipcp_update_vr (struct cgraph_node *node) +{ + tree fndecl = node->decl; + tree parm = DECL_ARGUMENTS (fndecl); + tree next_parm = parm; + ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node); + if (!ts || vec_safe_length (ts->m_vr) == 0) + return; + const vec &vr = *ts->m_vr; + unsigned count = vr.length (); + + for (unsigned i = 0; i < count; ++i, parm = next_parm) + { + if (node->clone.combined_args_to_skip + && bitmap_bit_p (node->clone.combined_args_to_skip, i)) + continue; + gcc_checking_assert (parm); + next_parm = DECL_CHAIN (parm); + tree ddef = ssa_default_def (DECL_STRUCT_FUNCTION (node->decl), parm); + + if (!ddef || !is_gimple_reg (parm)) + continue; + + if (vr[i].known + && INTEGRAL_TYPE_P (TREE_TYPE (ddef)) + && !POINTER_TYPE_P (TREE_TYPE (ddef)) + && (vr[i].type == VR_RANGE || vr[i].type == VR_ANTI_RANGE)) + { + tree type = TREE_TYPE (ddef); + unsigned prec = TYPE_PRECISION (type); + if (dump_file) + { + fprintf (dump_file, "Setting value range of param %u ", i); + fprintf (dump_file, "%s[", + (vr[i].type == VR_ANTI_RANGE) ? "~" : ""); + print_decs (vr[i].min, dump_file); + fprintf (dump_file, ", "); + print_decs (vr[i].max, dump_file); + fprintf (dump_file, "]\n"); + } + set_range_info (ddef, vr[i].type, + wide_int_storage::from (vr[i].min, prec, + TYPE_SIGN (type)), + wide_int_storage::from (vr[i].max, prec, + TYPE_SIGN (type))); + } + } +} + /* IPCP transformation phase doing propagation of aggregate values. */ unsigned int @@ -5578,6 +5745,7 @@ ipcp_transform_function (struct cgraph_node *node) ipcp_update_alignments (node); ipcp_update_bits (node); + ipcp_update_vr (node); aggval = ipa_get_agg_replacements_for_node (node); if (!aggval) return 0; diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h index e5a56da..a123978 100644 --- a/gcc/ipa-prop.h +++ b/gcc/ipa-prop.h @@ -167,6 +167,16 @@ struct GTY(()) ipa_bits bool known; }; +/* Info about value ranges. */ +struct GTY(()) ipa_vr +{ + /* The data fields below are valid only if known is true. */ + bool known; + enum value_range_type type; + wide_int min; + wide_int max; +}; + /* A jump function for a callsite represents the values passed as actual arguments of the callsite. See enum jump_func_type for the various types of jump functions supported. */ @@ -182,6 +192,10 @@ struct GTY (()) ipa_jump_func /* Information about zero/non-zero bits. */ struct ipa_bits bits; + /* Information about value range. */ + bool vr_known; + value_range m_vr; + enum jump_func_type type; /* Represents a value of a jump function. pass_through is used only in jump function context. constant represents the actual constant in constant jump @@ -521,6 +535,8 @@ struct GTY(()) ipcp_transformation_summary vec *alignments; /* Known bits information. */ vec *bits; + /* Value range information. */ + vec *m_vr; }; void ipa_set_node_agg_value_chain (struct cgraph_node *node, diff --git a/gcc/ipa-utils.c b/gcc/ipa-utils.c index 5eb7d5f..61d8dd1 100644 --- a/gcc/ipa-utils.c +++ b/gcc/ipa-utils.c @@ -32,6 +32,7 @@ along with GCC; see the file COPYING3. If not see #include "splay-tree.h" #include "ipa-utils.h" #include "symbol-summary.h" +#include "tree-vrp.h" #include "ipa-prop.h" #include "ipa-inline.h" diff --git a/gcc/ipa.c b/gcc/ipa.c index 035fb64..b26dad5 100644 --- a/gcc/ipa.c +++ b/gcc/ipa.c @@ -32,6 +32,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-iterator.h" #include "ipa-utils.h" #include "symbol-summary.h" +#include "tree-vrp.h" #include "ipa-prop.h" #include "ipa-inline.h" #include "dbgcnt.h" diff --git a/gcc/lto/lto-partition.c b/gcc/lto/lto-partition.c index 453343a..b52d175 100644 --- a/gcc/lto/lto-partition.c +++ b/gcc/lto/lto-partition.c @@ -31,6 +31,7 @@ along with GCC; see the file COPYING3. If not see #include "lto-streamer.h" #include "params.h" #include "symbol-summary.h" +#include "tree-vrp.h" #include "ipa-prop.h" #include "ipa-inline.h" #include "lto-partition.h" diff --git a/gcc/lto/lto.c b/gcc/lto/lto.c index 73d1e26..bbf02e8 100644 --- a/gcc/lto/lto.c +++ b/gcc/lto/lto.c @@ -36,6 +36,7 @@ along with GCC; see the file COPYING3. If not see #include "toplev.h" #include "stor-layout.h" #include "symbol-summary.h" +#include "tree-vrp.h" #include "ipa-prop.h" #include "common.h" #include "debug.h" diff --git a/gcc/opts.c b/gcc/opts.c index bc0570d..bb7879b 100644 --- a/gcc/opts.c +++ b/gcc/opts.c @@ -506,6 +506,7 @@ static const struct default_options default_options_table[] = { OPT_LEVELS_2_PLUS, OPT_fipa_cp, NULL, 1 }, { OPT_LEVELS_2_PLUS, OPT_fipa_cp_alignment, NULL, 1 }, { OPT_LEVELS_2_PLUS, OPT_fipa_bit_cp, NULL, 1 }, + { OPT_LEVELS_2_PLUS, OPT_fipa_vrp, NULL, 1 }, { OPT_LEVELS_2_PLUS, OPT_fdevirtualize, NULL, 1 }, { OPT_LEVELS_2_PLUS, OPT_fdevirtualize_speculatively, NULL, 1 }, { OPT_LEVELS_2_PLUS, OPT_fipa_sra, NULL, 1 }, diff --git a/gcc/testsuite/g++.dg/ipa/pure-const-3.C b/gcc/testsuite/g++.dg/ipa/pure-const-3.C index 3779ecb..ff7fe53 100644 --- a/gcc/testsuite/g++.dg/ipa/pure-const-3.C +++ b/gcc/testsuite/g++.dg/ipa/pure-const-3.C @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* { dg-options "-O2 -fno-ipa-vrp -fdump-tree-optimized" } */ int *ptr; static int barvar; static int b(int a); diff --git a/gcc/testsuite/gcc.dg/ipa/vrp1.c b/gcc/testsuite/gcc.dg/ipa/vrp1.c new file mode 100644 index 0000000..72a3139 --- /dev/null +++ b/gcc/testsuite/gcc.dg/ipa/vrp1.c @@ -0,0 +1,32 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-ipa-cp-details" } */ + +static __attribute__((noinline, noclone)) +int foo (int i) +{ + if (i < 5) + __builtin_abort (); + return 0; +} + +static __attribute__((noinline, noclone)) +int bar (int j) +{ + if (j > 8) + return foo (j + 2); + else if (j > 2) + return foo (j + 3); + + return 0; +} + +int main () +{ + for (unsigned int i =0; i < 1000; ++i) + bar (i); + + return 0; +} + +/* { dg-final { scan-ipa-dump "Setting value range of param 0 \\\[6," "cp" } } */ +/* { dg-final { scan-ipa-dump "Setting value range of param 0 \\\[0, 999\\\]" "cp" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/vrp2.c b/gcc/testsuite/gcc.dg/ipa/vrp2.c new file mode 100644 index 0000000..c720e5c --- /dev/null +++ b/gcc/testsuite/gcc.dg/ipa/vrp2.c @@ -0,0 +1,35 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-ipa-cp-details" } */ + +static __attribute__((noinline, noclone)) +int foo (int i) +{ + if (i < 4) + __builtin_abort (); + return 0; +} + +static __attribute__((noinline, noclone)) +int bar (int j) +{ + if (j > 8) + return foo (j + 2); + else if (j > 2) + return foo (j + 3); + + return 0; +} + +int main () +{ + foo (100); + for (unsigned int i = 0; i < 12; ++i) + { + bar (i); + } + foo (4); + return 0; +} + +/* { dg-final { scan-ipa-dump "Setting value range of param 0 \\\[4," "cp" } } */ +/* { dg-final { scan-ipa-dump "Setting value range of param 0 \\\[0, 11\\\]" "cp" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/vrp3.c b/gcc/testsuite/gcc.dg/ipa/vrp3.c new file mode 100644 index 0000000..fb5d54a --- /dev/null +++ b/gcc/testsuite/gcc.dg/ipa/vrp3.c @@ -0,0 +1,30 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-ipa-cp-details" } */ + +volatile int cond; + +static __attribute__((noinline, noclone)) +int foo (int i) +{ + if (i < 5) + __builtin_abort (); + return 0; +} + +static __attribute__((noinline, noclone)) +int bar (int j) +{ + if (cond) + foo (j); + return 0; +} + +int main () +{ + for (unsigned int i = 0; i < 10; ++i) + bar (i); + + return 0; +} + +/* { dg-final { scan-ipa-dump-times "Setting value range of param 0 \\\[0, 9\\\]" 2 "cp" } } */ diff --git a/gcc/toplev.c b/gcc/toplev.c index 2607904..668eccd 100644 --- a/gcc/toplev.c +++ b/gcc/toplev.c @@ -71,6 +71,7 @@ along with GCC; see the file COPYING3. If not see #include "dwarf2out.h" #include "ipa-reference.h" #include "symbol-summary.h" +#include "tree-vrp.h" #include "ipa-prop.h" #include "gcse.h" #include "tree-chkp.h" -- 2.7.4