From: Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org>
To: Jan Hubicka <hubicka@ucw.cz>
Cc: "gcc-patches@gcc.gnu.org" <gcc-patches@gcc.gnu.org>,
Richard Biener <richard.guenther@gmail.com>
Subject: Re: [RFC][IPA-VRP] Add support for IPA VRP in ipa-cp/ipa-prop
Date: Tue, 30 Aug 2016 05:21:00 -0000 [thread overview]
Message-ID: <CAELXzTPZibtMvYexaFnjchBkn1np45UxGaDiBu_yXbYH7ewDYA@mail.gmail.com> (raw)
In-Reply-To: <20160721125416.GA23760@kam.mff.cuni.cz>
[-- Attachment #1: Type: text/plain, Size: 4810 bytes --]
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<ipa_vr, va_gc> &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
[-- Attachment #2: 0002-Add-ipa-vrp.patch --]
[-- Type: text/x-patch, Size: 28964 bytes --]
From c6687f60001695dd71316e894010a764cb15606a Mon Sep 17 00:00:00 2001
From: Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org>
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<ipa_alignment, va_gc> *src_alignments = src_trans->alignments;
+ const vec<ipa_vr, va_gc> *src_vr = src_trans->m_vr;
vec<ipa_alignment, va_gc> *&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<ipa_vr, va_gc> *&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<ipa_vr, va_gc> &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<ipa_alignment, va_gc> *alignments;
/* Known bits information. */
vec<ipa_bits, va_gc> *bits;
+ /* Value range information. */
+ vec<ipa_vr, va_gc> *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
next prev parent reply other threads:[~2016-08-30 5:21 UTC|newest]
Thread overview: 67+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-07-15 4:41 [RFC][IPA-VRP] IPA VRP Implementation kugan
2016-07-15 4:42 ` [RFC][IPA-VRP] Disable setting param of __builtin_constant_p to null kugan
2016-07-15 8:43 ` Jan Hubicka
2016-07-25 6:59 ` kugan
2016-07-25 10:02 ` Richard Biener
2016-07-15 4:43 ` [RFC][IPA-VRP] Check for POINTER_TYPE_P before accessing SSA_NAME_PTR_INFO in tree-inline kugan
2016-07-15 4:47 ` Andrew Pinski
2016-07-15 7:03 ` Jakub Jelinek
2016-07-15 7:03 ` kugan
2016-07-15 7:32 ` Richard Biener
2016-07-15 4:44 ` [RFC][IPA-VRP] Re-factor tree-vrp to factor out common code kugan
2016-07-15 4:47 ` [RFC][IPA-VRP] Add support for IPA VRP in ipa-cp/ipa-prop kugan
2016-07-15 12:23 ` Martin Jambor
2016-07-19 8:22 ` kugan
2016-07-19 21:27 ` kugan
2016-07-21 12:54 ` Jan Hubicka
2016-08-30 5:21 ` Kugan Vivekanandarajah [this message]
2016-08-30 18:12 ` Prathamesh Kulkarni
2016-08-30 21:10 ` kugan
2016-09-02 12:31 ` Jan Hubicka
2016-07-17 13:24 ` Prathamesh Kulkarni
2016-07-22 12:27 ` [RFC][IPA-VRP] Re-factor tree-vrp to factor out common code kugan
2016-07-22 12:49 ` Richard Biener
2016-07-22 14:34 ` kugan
2016-07-23 10:12 ` kugan
2016-08-16 8:09 ` kugan
2016-08-16 11:56 ` Richard Biener
2016-08-16 22:20 ` kugan
2016-08-17 2:50 ` kugan
2016-08-17 13:46 ` Richard Biener
2016-07-15 4:45 ` [RFC][IPA-VRP] Early VRP Implementation kugan
2016-07-15 4:52 ` Andrew Pinski
2016-07-15 7:08 ` kugan
2016-07-15 7:28 ` Andrew Pinski
2016-07-15 7:33 ` kugan
2016-07-18 11:51 ` Richard Biener
2016-07-22 12:10 ` kugan
2016-07-25 11:18 ` Richard Biener
2016-07-26 12:27 ` kugan
2016-07-26 13:37 ` Richard Biener
2016-07-28 7:36 ` kugan
2016-07-28 11:34 ` Richard Biener
2016-08-03 1:17 ` kugan
2016-08-12 10:43 ` Richard Biener
2016-08-16 7:39 ` [RFC][IPA-VRP] splits out the update_value_range calls from vrp_visit_stmt kugan
2016-08-16 10:58 ` Richard Biener
2016-08-17 2:27 ` kugan
2016-08-17 13:44 ` Richard Biener
2016-08-16 7:45 ` [RFC][IPA-VRP] Early VRP Implementation kugan
2016-08-19 11:41 ` Richard Biener
2016-08-23 2:12 ` Kugan Vivekanandarajah
2016-09-02 8:11 ` Kugan Vivekanandarajah
2016-09-14 12:11 ` Richard Biener
2016-09-14 21:47 ` Jan Hubicka
2016-09-15 7:23 ` Richard Biener
2016-09-15 14:57 ` Jeff Law
2016-09-16 8:59 ` Richard Biener
2016-09-16 6:37 ` kugan
2016-09-16 10:26 ` Richard Biener
2016-09-18 23:40 ` kugan
2016-09-19 13:30 ` Richard Biener
2016-09-20 5:48 ` kugan
2016-07-19 16:19 ` Jeff Law
2016-07-19 18:35 ` Richard Biener
2016-07-19 20:14 ` Jeff Law
2016-07-15 4:47 ` [RFC][IPA-VRP] Teach tree-vrp to use the VR set in params kugan
2016-07-18 11:33 ` Richard Biener
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAELXzTPZibtMvYexaFnjchBkn1np45UxGaDiBu_yXbYH7ewDYA@mail.gmail.com \
--to=kugan.vivekanandarajah@linaro.org \
--cc=gcc-patches@gcc.gnu.org \
--cc=hubicka@ucw.cz \
--cc=richard.guenther@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).