| Message ID | ri6ilm9k6fh.fsf@suse.cz |
|---|---|
| State | New |
| Headers | show |
| Series | [1/2] ipa-cp: Better representation of aggregate values we clone for | expand |
> gcc/ChangeLog: > > 2022-08-26 Martin Jambor <mjambor@suse.cz> > > * ipa-prop.h (IPA_PROP_ARG_INDEX_LIMIT_BITS): New. > (ipcp_transformation): Added forward declaration. > (ipa_argagg_value): New type. > (ipa_argagg_value_list): New type. > (ipa_agg_replacement_value): Removed type. > (ipcp_transformation): Switch from using ipa_agg_replacement_value > to ipa_argagg_value_list. > (ipa_get_agg_replacements_for_node): Removed. > (ipa_dump_agg_replacement_values): Removed declaration. > * ipa-cp.cc: Include <algorithm>. > (values_equal_for_ipcp_p): Moved up in the file. > (ipa_argagg_value_list::dump): Likewise. > (ipa_argagg_value_list::debug): Likewise. > (ipa_argagg_value_list::get_elt): Likewise. > (ipa_argagg_value_list::get_elt_for_index): Likewise. > (ipa_argagg_value_list::get_value): New overloaded functions. > (ipa_argagg_value_list::superset_of_p): New function. > (new ipa_argagg_value_list::push_adjusted_values): Likewise. > (push_agg_values_from_plats): Likewise. > (intersect_argaggs_with): Likewise. > (get_clone_agg_value): Removed. > (ipa_agg_value_from_node): Make last parameter const, use > ipa_argagg_value_list to search values coming from clones. > (ipa_get_indirect_edge_target_1): Use ipa_argagg_value_list to search > values coming from clones. > (ipcp_discover_new_direct_edges): Pass around a vector of > ipa_argagg_values rather than a link list of replacement values. > (cgraph_edge_brings_value_p): Use ipa_argagg_value_list to search > values coming from clones. > (create_specialized_node): Work with a vector of ipa_argagg_values > rather than a link list of replacement values. > (self_recursive_agg_pass_through_p): Make the pointer parameters > const. > (copy_plats_to_inter): Removed. > (intersect_with_plats): Likewise. > (agg_replacements_to_vector): Likewise. > (intersect_with_agg_replacements): Likewise. > (intersect_aggregates_with_edge): Likewise. > (push_agg_values_for_index_from_edge): Likewise. > (push_agg_values_from_edge): Likewise. > (find_aggregate_values_for_callers_subset): Rewrite. > (cgraph_edge_brings_all_agg_vals_for_node): Likewise. > (ipcp_val_agg_replacement_ok_p): Use ipa_argagg_value_list to search > aggregate values. > (decide_about_value): Work with a vector of ipa_argagg_values rather > than a link list of replacement values. > (decide_whether_version_node): Likewise. > (ipa_analyze_node): Check number of parameters, assert that there > are no descriptors when bailing out. > * ipa-prop.cc (ipa_set_node_agg_value_chain): Switch to a vector of > ipa_argagg_value. > (ipa_node_params_t::duplicate): Removed superfluous handling of > ipa_agg_replacement_values. Name of src parameter removed because > it is no longer used. > (ipcp_transformation_t::duplicate): Replaced duplication of > ipa_agg_replacement_values with copying vector m_agg_values. > (ipa_dump_agg_replacement_values): Removed. > (write_ipcp_transformation_info): Stream the new data-structure > instead of the old. > (read_ipcp_transformation_info): Likewise. > (adjust_agg_replacement_values): Work with ipa_argagg_values instead > of linked lists of ipa_agg_replacement_values, copy the items and > truncate the vector as necessary to keep it sorted instead of marking > items as invalid. Return one bool if CFG should be updated. > (ipcp_modif_dom_walker): Store ipcp_transformation instead of > linked list of ipa_agg_replacement_values. > (ipcp_modif_dom_walker::before_dom_children): Use > ipa_argagg_value_list instead of walking a list of > ipa_agg_replacement_values. > (ipcp_transform_function): Switch to the new data structure, adjust > dumping. > > gcc/testsuite/ChangeLog: > > 2022-08-15 Martin Jambor <mjambor@suse.cz> > > * gcc.dg/ipa/ipcp-agg-11.c: Adjust dumps. > * gcc.dg/ipa/ipcp-agg-8.c: Likewise. > --- > gcc/ipa-cp.cc | 1010 ++++++++++++------------ > gcc/ipa-prop.cc | 254 +++--- > gcc/ipa-prop.h | 139 +++- > gcc/testsuite/gcc.dg/ipa/ipcp-agg-11.c | 4 +- > gcc/testsuite/gcc.dg/ipa/ipcp-agg-8.c | 4 +- > 5 files changed, 736 insertions(+), 675 deletions(-) > > diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc > index 543a9334e2c..024f8c06b5d 100644 > --- a/gcc/ipa-cp.cc > +++ b/gcc/ipa-cp.cc > @@ -127,6 +127,7 @@ along with GCC; see the file COPYING3. If not see > #include "attribs.h" > #include "dbgcnt.h" > #include "symtab-clones.h" > +#include <algorithm> > > template <typename valtype> class ipcp_value; > > @@ -455,6 +456,26 @@ ipcp_lattice<valtype>::is_single_const () > return true; > } > > +/* Return true iff X and Y should be considered equal values by IPA-CP. */ > + > +static bool > +values_equal_for_ipcp_p (tree x, tree y) > +{ > + gcc_checking_assert (x != NULL_TREE && y != NULL_TREE); > + > + if (x == y) > + return true; > + > + if (TREE_CODE (x) == ADDR_EXPR > + && TREE_CODE (y) == ADDR_EXPR > + && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL > + && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL) > + return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)), > + DECL_INITIAL (TREE_OPERAND (y, 0)), 0); I wonder if we want to handle MEM_REFs here too? They get quite common in IPA mode and I think we miss the fixup removing them here. > + else > + return operand_equal_p (x, y, 0); > +/* Return the item describing a constant stored for INDEX at UNIT_OFFSET or > + NULL if there is no such constant. */ > + > +const ipa_argagg_value * > +ipa_argagg_value_list::get_elt (int index, unsigned unit_offset) const > +{ > + ipa_argagg_value key; > + key.index = index; > + key.unit_offset = unit_offset; > + const ipa_argagg_value *res > + = std::lower_bound (m_elts.begin (), m_elts.end (), key, > + [] (const ipa_argagg_value &elt, > + const ipa_argagg_value &val) > + { > + if (elt.index < val.index) > + return true; > + if (elt.index > val.index) > + return false; > + if (elt.unit_offset < val.unit_offset) > + return true; > + return false; > + }); > + > + if (res == m_elts.end () > + || res->index != index > + || res->unit_offset != unit_offset) > + res = nullptr; > + > + /* TODO: perhaps remove after some extensive testing? */ > + if (!flag_checking) > + return res; > + > + const ipa_argagg_value *slow_res = NULL; > + int prev_index = -1; > + unsigned prev_unit_offset = 0; > + for (const ipa_argagg_value &av : m_elts) > + { > + gcc_assert (prev_index < 0 > + || prev_index < av.index > + || prev_unit_offset < av.unit_offset); > + prev_index = av.index; > + prev_unit_offset = av.unit_offset; > + if (av.index == index > + && av.unit_offset == unit_offset) > + slow_res = &av; > + } > + gcc_assert (res == slow_res); So this is just checking that the std::lower_bound works as expected? I am just curious if you expect it to break? > +/* Turn all values that are not present in OTHER into NULL_TREEs. Return the > + number of remaining valid entries. */ > + > +bool > +ipa_argagg_value_list::superset_of_p (const ipa_argagg_value_list &other) const It returns bool, so not number of entries. > +/* Push into RES aggregate all stored aggregate values relating to parameter > + with SRC_INDEX as those relating to of DST_INDEX while subtracting > + UNIT_DELTA from the individual unit offsets. */ > + > +void > +ipa_argagg_value_list::push_adjusted_values (unsigned src_index, > + unsigned dest_index, > + unsigned unit_delta, > + vec<ipa_argagg_value> *res) const > +{ > + const ipa_argagg_value *av = get_elt_for_index (src_index); > + if (!av) > + return; > + unsigned prev_unit_offset = 0; > + bool first = true; > + for (; av < m_elts.end (); ++av) > + { > + if (av->index > src_index) > + return; > + if (av->index == src_index > + && (av->unit_offset >= unit_delta) > + && av->value) > + { > + ipa_argagg_value new_av; > + gcc_checking_assert (av->value); > + new_av.value = av->value; > + new_av.unit_offset = av->unit_offset - unit_delta; > + new_av.index = dest_index; > + new_av.by_ref = av->by_ref; I am bit lost on what is going here, so perhaps a comment would help. > > +class ipcp_transformation; > + > +/* Element of a vector describing aggregate values for a number of arguments in > + a particular context, be it a call or the aggregate constants that a node is > + specialized for. */ > + > +struct GTY(()) ipa_argagg_value > +{ > + /* The constant value. In the contexts where the list of known values is > + being pruned, NULL means a variable value. */ > + tree value; > + /* Unit offset within the aggregate. */ > + unsigned unit_offset; since this is 32bit, it makes me wonder if we have overflow checks (even though greater than 4GB structures on stack are likely rare even today) > + /* Index of the parameter, as it was in the original function (i.e. needs > + remapping after parameter modification is carried out as part of clone > + materialization). */ > + unsigned index : IPA_PROP_ARG_INDEX_LIMIT_BITS; > + /* Whether the value was passed by reference. */ > + unsigned by_ref : 1; > +}; > + > +/* A view into a sorted list of aggregate values in a particular context, be it > + a call or the aggregate constants that a node is specialized for. The > + actual data is stored in the vector this has been constructed from. */ > + > +class ipa_argagg_value_list > +{ > +public: > + ipa_argagg_value_list () = delete; > + ipa_argagg_value_list (const vec<ipa_argagg_value, va_gc> *values) > + : m_elts (values) > + {} > + ipa_argagg_value_list (const vec<ipa_argagg_value> *values) > + : m_elts (*values) > + {} > + ipa_argagg_value_list (const ipcp_transformation *tinfo); > + > + /* Return the aggregate constant stored for INDEX at UNIT_OFFSET, if it is > + passed by reference or not according to BY_REF, or NULL_TREE > + otherwise. */ > + > + tree get_value (int index, unsigned unit_offset, bool by_ref) const; > + > + /* Return the aggregate constant stored for INDEX at UNIT_OFFSET, not > + performing any check of whether value is passed by reference. Return > + NULL_TREE if there is no such constant. */ > + > + tree get_value (int index, unsigned unit_offset) const; > + > + /* Return the item describing a constant stored for INDEX at UNIT_OFFSET or > + NULL if there is no such constant. */ > + > + const ipa_argagg_value *get_elt (int index, unsigned unit_offset) const; > + > + /* Return the first item describing a constant stored for parameter with > + INDEX, regardless of offset or reference, or NULL if there is no such > + constant. */ > + > + const ipa_argagg_value *get_elt_for_index (int index) const; > + > + /* Return true if all elements present in OTHER are also present in this > + class. */ > + > + bool superset_of_p (const ipa_argagg_value_list &other) const; > + > + /* Push into RES aggregate all stored aggregate values relating to parameter > + with SRC_INDEX as those relating to of DST_INDEX while subtracting > + UNIT_DELTA from the individual unit offsets. */ > + > + void push_adjusted_values (unsigned src_index, unsigned dest_index, > + unsigned unit_delta, > + vec<ipa_argagg_value> *res) const; > + > + /* Dump aggregate constants to FILE. */ > + > + void dump (FILE *f); > + > + /* Dump aggregate constants to stderr. */ > + DEBUG_FUNCTION here. > + void debug (); > + > + /* Array slice pointing to the actual storage. */ > + > + array_slice<const ipa_argagg_value> m_elts; > +}; > + Patch is OK with those changes. Thanks, Honza
Hi, thanks for the review. On Fri, Oct 14 2022, Jan Hubicka wrote: >> [...] >> >> gcc/testsuite/ChangeLog: >> >> 2022-08-15 Martin Jambor <mjambor@suse.cz> >> >> * gcc.dg/ipa/ipcp-agg-11.c: Adjust dumps. >> * gcc.dg/ipa/ipcp-agg-8.c: Likewise. >> --- >> gcc/ipa-cp.cc | 1010 ++++++++++++------------ >> gcc/ipa-prop.cc | 254 +++--- >> gcc/ipa-prop.h | 139 +++- >> gcc/testsuite/gcc.dg/ipa/ipcp-agg-11.c | 4 +- >> gcc/testsuite/gcc.dg/ipa/ipcp-agg-8.c | 4 +- >> 5 files changed, 736 insertions(+), 675 deletions(-) >> >> diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc >> index 543a9334e2c..024f8c06b5d 100644 >> --- a/gcc/ipa-cp.cc >> +++ b/gcc/ipa-cp.cc >> @@ -127,6 +127,7 @@ along with GCC; see the file COPYING3. If not see >> #include "attribs.h" >> #include "dbgcnt.h" >> #include "symtab-clones.h" >> +#include <algorithm> >> >> template <typename valtype> class ipcp_value; >> >> @@ -455,6 +456,26 @@ ipcp_lattice<valtype>::is_single_const () >> return true; >> } >> >> +/* Return true iff X and Y should be considered equal values by IPA-CP. */ >> + >> +static bool >> +values_equal_for_ipcp_p (tree x, tree y) >> +{ >> + gcc_checking_assert (x != NULL_TREE && y != NULL_TREE); >> + >> + if (x == y) >> + return true; >> + >> + if (TREE_CODE (x) == ADDR_EXPR >> + && TREE_CODE (y) == ADDR_EXPR >> + && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL >> + && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL) >> + return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)), >> + DECL_INITIAL (TREE_OPERAND (y, 0)), 0); > > I wonder if we want to handle MEM_REFs here too? They get quite common > in IPA mode and I think we miss the fixup removing them here. This patch just moves the function up without modifying it, and I'd like to do any changes separately, unless they are required for this patch. And just to be sure, you mean it should cover also the MEM_REF case as in is_gimple_invariant_address, right? >> + else >> + return operand_equal_p (x, y, 0); >> +/* Return the item describing a constant stored for INDEX at UNIT_OFFSET or >> + NULL if there is no such constant. */ >> + >> +const ipa_argagg_value * >> +ipa_argagg_value_list::get_elt (int index, unsigned unit_offset) const >> +{ >> + ipa_argagg_value key; >> + key.index = index; >> + key.unit_offset = unit_offset; >> + const ipa_argagg_value *res >> + = std::lower_bound (m_elts.begin (), m_elts.end (), key, >> + [] (const ipa_argagg_value &elt, >> + const ipa_argagg_value &val) >> + { >> + if (elt.index < val.index) >> + return true; >> + if (elt.index > val.index) >> + return false; >> + if (elt.unit_offset < val.unit_offset) >> + return true; >> + return false; >> + }); >> + >> + if (res == m_elts.end () >> + || res->index != index >> + || res->unit_offset != unit_offset) >> + res = nullptr; >> + >> + /* TODO: perhaps remove after some extensive testing? */ >> + if (!flag_checking) >> + return res; >> + >> + const ipa_argagg_value *slow_res = NULL; >> + int prev_index = -1; >> + unsigned prev_unit_offset = 0; >> + for (const ipa_argagg_value &av : m_elts) >> + { >> + gcc_assert (prev_index < 0 >> + || prev_index < av.index >> + || prev_unit_offset < av.unit_offset); >> + prev_index = av.index; >> + prev_unit_offset = av.unit_offset; >> + if (av.index == index >> + && av.unit_offset == unit_offset) >> + slow_res = &av; >> + } >> + gcc_assert (res == slow_res); > So this is just checking that the std::lower_bound works as expected? > I am just curious if you expect it to break? It rather checks that the underlying array on which it operates really is sorted :-) When I was writing this code I had not carefully checked all the places where we construct them. Now I am quite confident they indeed are always sorted but still thought this would be a useful check against future errors. We can remove the test at any time if it ever becomes too slow. >> +/* Turn all values that are not present in OTHER into NULL_TREEs. Return the >> + number of remaining valid entries. */ >> + >> +bool >> +ipa_argagg_value_list::superset_of_p (const ipa_argagg_value_list &other) const > It returns bool, so not number of entries. Umm, that comment was from an entirely different function, fixed. I also changed the names of local variables this_index and this_offset to other_index and other_offset because that is what they really are. >> +/* Push into RES aggregate all stored aggregate values relating to parameter >> + with SRC_INDEX as those relating to of DST_INDEX while subtracting >> + UNIT_DELTA from the individual unit offsets. */ >> + >> +void >> +ipa_argagg_value_list::push_adjusted_values (unsigned src_index, >> + unsigned dest_index, >> + unsigned unit_delta, >> + vec<ipa_argagg_value> *res) const >> +{ >> + const ipa_argagg_value *av = get_elt_for_index (src_index); >> + if (!av) >> + return; >> + unsigned prev_unit_offset = 0; >> + bool first = true; >> + for (; av < m_elts.end (); ++av) >> + { >> + if (av->index > src_index) >> + return; >> + if (av->index == src_index >> + && (av->unit_offset >= unit_delta) >> + && av->value) >> + { >> + ipa_argagg_value new_av; >> + gcc_checking_assert (av->value); >> + new_av.value = av->value; >> + new_av.unit_offset = av->unit_offset - unit_delta; >> + new_av.index = dest_index; >> + new_av.by_ref = av->by_ref; > I am bit lost on what is going here, so perhaps a comment would help. I have changed the function description to: /* Push all items in this list that describe parameter SRC_INDEX into RES as ones describing DST_INDEX while subtracting UNIT_DELTA from their unit offsets but skip those which would end up with a negative offset. */ Plus the function has a simple assert that we indeed push offsets in increasing order. I have added a comment saying that too. >> >> +class ipcp_transformation; >> + >> +/* Element of a vector describing aggregate values for a number of arguments in >> + a particular context, be it a call or the aggregate constants that a node is >> + specialized for. */ >> + >> +struct GTY(()) ipa_argagg_value >> +{ >> + /* The constant value. In the contexts where the list of known values is >> + being pruned, NULL means a variable value. */ >> + tree value; >> + /* Unit offset within the aggregate. */ >> + unsigned unit_offset; > since this is 32bit, it makes me wonder if we have overflow checks (even > though greater than 4GB structures on stack are likely rare even > today) Right, I meant to add it but forgot, I have just added the check to ipa_load_from_parm_agg in ipa-prop.cc. >> + /* Index of the parameter, as it was in the original function (i.e. needs >> + remapping after parameter modification is carried out as part of clone >> + materialization). */ >> + unsigned index : IPA_PROP_ARG_INDEX_LIMIT_BITS; >> + /* Whether the value was passed by reference. */ >> + unsigned by_ref : 1; >> +}; >> + >> +/* A view into a sorted list of aggregate values in a particular context, be it >> + a call or the aggregate constants that a node is specialized for. The >> + actual data is stored in the vector this has been constructed from. */ >> + >> +class ipa_argagg_value_list >> +{ >> +public: >> + ipa_argagg_value_list () = delete; >> + ipa_argagg_value_list (const vec<ipa_argagg_value, va_gc> *values) >> + : m_elts (values) >> + {} >> + ipa_argagg_value_list (const vec<ipa_argagg_value> *values) >> + : m_elts (*values) >> + {} >> + ipa_argagg_value_list (const ipcp_transformation *tinfo); >> + >> + /* Return the aggregate constant stored for INDEX at UNIT_OFFSET, if it is >> + passed by reference or not according to BY_REF, or NULL_TREE >> + otherwise. */ >> + >> + tree get_value (int index, unsigned unit_offset, bool by_ref) const; >> + >> + /* Return the aggregate constant stored for INDEX at UNIT_OFFSET, not >> + performing any check of whether value is passed by reference. Return >> + NULL_TREE if there is no such constant. */ >> + >> + tree get_value (int index, unsigned unit_offset) const; >> + >> + /* Return the item describing a constant stored for INDEX at UNIT_OFFSET or >> + NULL if there is no such constant. */ >> + >> + const ipa_argagg_value *get_elt (int index, unsigned unit_offset) const; >> + >> + /* Return the first item describing a constant stored for parameter with >> + INDEX, regardless of offset or reference, or NULL if there is no such >> + constant. */ >> + >> + const ipa_argagg_value *get_elt_for_index (int index) const; >> + >> + /* Return true if all elements present in OTHER are also present in this >> + class. */ >> + >> + bool superset_of_p (const ipa_argagg_value_list &other) const; >> + >> + /* Push into RES aggregate all stored aggregate values relating to parameter >> + with SRC_INDEX as those relating to of DST_INDEX while subtracting >> + UNIT_DELTA from the individual unit offsets. */ >> + >> + void push_adjusted_values (unsigned src_index, unsigned dest_index, >> + unsigned unit_delta, >> + vec<ipa_argagg_value> *res) const; >> + >> + /* Dump aggregate constants to FILE. */ >> + >> + void dump (FILE *f); >> + >> + /* Dump aggregate constants to stderr. */ >> + > DEBUG_FUNCTION here. OK. >> + void debug (); >> + >> + /* Array slice pointing to the actual storage. */ >> + >> + array_slice<const ipa_argagg_value> m_elts; >> +}; >> + > > Patch is OK with those changes. This is what I am about to re-bootstrap, test and then push if everything passes. Thank you! Martin This patch replaces linked lists of ipa_agg_replacement_value with vectors of similar structures called ipa_argagg_value and simplifies how we compute them in the first place. Having a vector should also result in less overhead when allocating and because we keep it sorted, it leads to logarithmic searches. The slightly obnoxious "argagg" bit in the name can be changed into "agg" after the next patch removes our current ipa_agg_value type. The patch also introduces type ipa_argagg_value_list which serves as a common view into a vector of ipa_argagg_value structures regardless whether they are stored in GC memory (required for IPA-CP transformation summary because we store trees) or in an auto_vec which is hopefully usually only allocated on stack. The calculation of aggreagete costant values for a given subsert of callers is then rewritten to compute known constants for each edge (some pruning to skip obviously not needed is still employed and should not be really worse than what I am replacing) and these vectors are there intersected, which can be done linearly since they are sorted. The patch also removes a lot of heap allocations of small lists of aggregate values and replaces them with stack based auto_vecs. As Richard Sandiford suggested, I use std::lower_bound from <algorithm> rather than re-implementing bsearch for array_slice. The patch depends on the patch which adds the ability to construct array_slices from gc-allocated vectors. gcc/ChangeLog: 2022-10-17 Martin Jambor <mjambor@suse.cz> * ipa-prop.h (IPA_PROP_ARG_INDEX_LIMIT_BITS): New. (ipcp_transformation): Added forward declaration. (ipa_argagg_value): New type. (ipa_argagg_value_list): New type. (ipa_agg_replacement_value): Removed type. (ipcp_transformation): Switch from using ipa_agg_replacement_value to ipa_argagg_value_list. (ipa_get_agg_replacements_for_node): Removed. (ipa_dump_agg_replacement_values): Removed declaration. * ipa-cp.cc: Define INCLUDE_ALGORITHM. (values_equal_for_ipcp_p): Moved up in the file. (ipa_argagg_value_list::dump): New function. (ipa_argagg_value_list::debug): Likewise. (ipa_argagg_value_list::get_elt): Likewise. (ipa_argagg_value_list::get_elt_for_index): Likewise. (ipa_argagg_value_list::get_value): New overloaded functions. (ipa_argagg_value_list::superset_of_p): New function. (new ipa_argagg_value_list::push_adjusted_values): Likewise. (push_agg_values_from_plats): Likewise. (intersect_argaggs_with): Likewise. (get_clone_agg_value): Removed. (ipa_agg_value_from_node): Make last parameter const, use ipa_argagg_value_list to search values coming from clones. (ipa_get_indirect_edge_target_1): Use ipa_argagg_value_list to search values coming from clones. (ipcp_discover_new_direct_edges): Pass around a vector of ipa_argagg_values rather than a link list of replacement values. (cgraph_edge_brings_value_p): Use ipa_argagg_value_list to search values coming from clones. (create_specialized_node): Work with a vector of ipa_argagg_values rather than a link list of replacement values. (self_recursive_agg_pass_through_p): Make the pointer parameters const. (copy_plats_to_inter): Removed. (intersect_with_plats): Likewise. (agg_replacements_to_vector): Likewise. (intersect_with_agg_replacements): Likewise. (intersect_aggregates_with_edge): Likewise. (push_agg_values_for_index_from_edge): Likewise. (push_agg_values_from_edge): Likewise. (find_aggregate_values_for_callers_subset): Rewrite. (cgraph_edge_brings_all_agg_vals_for_node): Likewise. (ipcp_val_agg_replacement_ok_p): Use ipa_argagg_value_list to search aggregate values. (decide_about_value): Work with a vector of ipa_argagg_values rather than a link list of replacement values. (decide_whether_version_node): Likewise. (ipa_analyze_node): Check number of parameters, assert that there are no descriptors when bailing out. * ipa-prop.cc (ipa_set_node_agg_value_chain): Switch to a vector of ipa_argagg_value. (ipa_node_params_t::duplicate): Removed superfluous handling of ipa_agg_replacement_values. Name of src parameter removed because it is no longer used. (ipcp_transformation_t::duplicate): Replaced duplication of ipa_agg_replacement_values with copying vector m_agg_values. (ipa_dump_agg_replacement_values): Removed. (write_ipcp_transformation_info): Stream the new data-structure instead of the old. (read_ipcp_transformation_info): Likewise. (adjust_agg_replacement_values): Work with ipa_argagg_values instead of linked lists of ipa_agg_replacement_values, copy the items and truncate the vector as necessary to keep it sorted instead of marking items as invalid. Return one bool if CFG should be updated. (ipcp_modif_dom_walker): Store ipcp_transformation instead of linked list of ipa_agg_replacement_values. (ipcp_modif_dom_walker::before_dom_children): Use ipa_argagg_value_list instead of walking a list of ipa_agg_replacement_values. (ipcp_transform_function): Switch to the new data structure, adjust dumping. gcc/testsuite/ChangeLog: 2022-08-15 Martin Jambor <mjambor@suse.cz> * gcc.dg/ipa/ipcp-agg-11.c: Adjust dumps. * gcc.dg/ipa/ipcp-agg-8.c: Likewise. --- gcc/ipa-cp.cc | 1012 ++++++++++++------------ gcc/ipa-prop.cc | 262 +++--- gcc/ipa-prop.h | 139 +++- gcc/testsuite/gcc.dg/ipa/ipcp-agg-11.c | 4 +- gcc/testsuite/gcc.dg/ipa/ipcp-agg-8.c | 4 +- 5 files changed, 744 insertions(+), 677 deletions(-) diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc index 66bba71c068..530733515e6 100644 --- a/gcc/ipa-cp.cc +++ b/gcc/ipa-cp.cc @@ -100,6 +100,7 @@ along with GCC; see the file COPYING3. If not see and tree-inline.cc) according to instructions inserted to the call graph by the second stage. */ +#define INCLUDE_ALGORITHM #include "config.h" #include "system.h" #include "coretypes.h" @@ -455,6 +456,26 @@ ipcp_lattice<valtype>::is_single_const () return true; } +/* Return true iff X and Y should be considered equal values by IPA-CP. */ + +static bool +values_equal_for_ipcp_p (tree x, tree y) +{ + gcc_checking_assert (x != NULL_TREE && y != NULL_TREE); + + if (x == y) + return true; + + if (TREE_CODE (x) == ADDR_EXPR + && TREE_CODE (y) == ADDR_EXPR + && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL + && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL) + return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)), + DECL_INITIAL (TREE_OPERAND (y, 0)), 0); + else + return operand_equal_p (x, y, 0); +} + /* Print V which is extracted from a value in a lattice to F. */ static void @@ -1217,6 +1238,274 @@ ipcp_bits_lattice::meet_with (ipcp_bits_lattice& other, unsigned precision, drop_all_ones); } +/* Dump the contents of the list to FILE. */ + +void +ipa_argagg_value_list::dump (FILE *f) +{ + bool comma = false; + for (const ipa_argagg_value &av : m_elts) + { + fprintf (f, "%s %i[%u]=", comma ? "," : "", + av.index, av.unit_offset); + print_generic_expr (f, av.value); + if (av.by_ref) + fprintf (f, "(by_ref)"); + comma = true; + } + fprintf (f, "\n"); +} + +/* Dump the contents of the list to stderr. */ + +void +ipa_argagg_value_list::debug () +{ + dump (stderr); +} + +/* Return the item describing a constant stored for INDEX at UNIT_OFFSET or + NULL if there is no such constant. */ + +const ipa_argagg_value * +ipa_argagg_value_list::get_elt (int index, unsigned unit_offset) const +{ + ipa_argagg_value key; + key.index = index; + key.unit_offset = unit_offset; + const ipa_argagg_value *res + = std::lower_bound (m_elts.begin (), m_elts.end (), key, + [] (const ipa_argagg_value &elt, + const ipa_argagg_value &val) + { + if (elt.index < val.index) + return true; + if (elt.index > val.index) + return false; + if (elt.unit_offset < val.unit_offset) + return true; + return false; + }); + + if (res == m_elts.end () + || res->index != index + || res->unit_offset != unit_offset) + res = nullptr; + + /* TODO: perhaps remove the check (that the underlying array is indeed + sorted) if it turns out it can be too slow? */ + if (!flag_checking) + return res; + + const ipa_argagg_value *slow_res = NULL; + int prev_index = -1; + unsigned prev_unit_offset = 0; + for (const ipa_argagg_value &av : m_elts) + { + gcc_assert (prev_index < 0 + || prev_index < av.index + || prev_unit_offset < av.unit_offset); + prev_index = av.index; + prev_unit_offset = av.unit_offset; + if (av.index == index + && av.unit_offset == unit_offset) + slow_res = &av; + } + gcc_assert (res == slow_res); + + return res; +} + +/* Return the first item describing a constant stored for parameter with INDEX, + regardless of offset or reference, or NULL if there is no such constant. */ + +const ipa_argagg_value * +ipa_argagg_value_list::get_elt_for_index (int index) const +{ + const ipa_argagg_value *res + = std::lower_bound (m_elts.begin (), m_elts.end (), index, + [] (const ipa_argagg_value &elt, unsigned idx) + { + return elt.index < idx; + }); + if (res == m_elts.end () + || res->index != index) + res = nullptr; + return res; +} + +/* Return the aggregate constant stored for INDEX at UNIT_OFFSET, not + performing any check of whether value is passed by reference, or NULL_TREE + if there is no such constant. */ + +tree +ipa_argagg_value_list::get_value (int index, unsigned unit_offset) const +{ + const ipa_argagg_value *av = get_elt (index, unit_offset); + return av ? av->value : NULL_TREE; +} + +/* Return the aggregate constant stored for INDEX at UNIT_OFFSET, if it is + passed by reference or not according to BY_REF, or NULL_TREE if there is + no such constant. */ + +tree +ipa_argagg_value_list::get_value (int index, unsigned unit_offset, + bool by_ref) const +{ + const ipa_argagg_value *av = get_elt (index, unit_offset); + if (av && av->by_ref == by_ref) + return av->value; + return NULL_TREE; +} + +/* Return true if all elements present in OTHER are also present in this + list. */ + +bool +ipa_argagg_value_list::superset_of_p (const ipa_argagg_value_list &other) const +{ + unsigned j = 0; + for (unsigned i = 0; i < other.m_elts.size (); i++) + { + unsigned other_index = other.m_elts[i].index; + unsigned other_offset = other.m_elts[i].unit_offset; + + while (j < m_elts.size () + && (m_elts[j].index < other_index + || (m_elts[j].index == other_index + && m_elts[j].unit_offset < other_offset))) + j++; + + if (j >= m_elts.size () + || m_elts[j].index != other_index + || m_elts[j].unit_offset != other_offset + || m_elts[j].by_ref != other.m_elts[i].by_ref + || !m_elts[j].value + || !values_equal_for_ipcp_p (m_elts[j].value, other.m_elts[i].value)) + return false; + } + return true; +} + +/* Push all items in this list that describe parameter SRC_INDEX into RES as + ones describing DST_INDEX while subtracting UNIT_DELTA from their unit + offsets but skip those which would end up with a negative offset. */ + +void +ipa_argagg_value_list::push_adjusted_values (unsigned src_index, + unsigned dest_index, + unsigned unit_delta, + vec<ipa_argagg_value> *res) const +{ + const ipa_argagg_value *av = get_elt_for_index (src_index); + if (!av) + return; + unsigned prev_unit_offset = 0; + bool first = true; + for (; av < m_elts.end (); ++av) + { + if (av->index > src_index) + return; + if (av->index == src_index + && (av->unit_offset >= unit_delta) + && av->value) + { + ipa_argagg_value new_av; + gcc_checking_assert (av->value); + new_av.value = av->value; + new_av.unit_offset = av->unit_offset - unit_delta; + new_av.index = dest_index; + new_av.by_ref = av->by_ref; + + /* Quick check that the offsets we push are indeed increasing. */ + gcc_assert (first + || new_av.unit_offset > prev_unit_offset); + prev_unit_offset = new_av.unit_offset; + first = false; + + res->safe_push (new_av); + } + } +} + +/* Push to RES information about single lattices describing aggregate values in + PLATS as those describing parameter DEST_INDEX and the original offset minus + UNIT_DELTA. Return true if any item has been pushed to RES. */ + +static bool +push_agg_values_from_plats (ipcp_param_lattices *plats, int dest_index, + unsigned unit_delta, + vec<ipa_argagg_value> *res) +{ + if (plats->aggs_contain_variable) + return false; + + bool pushed_sth = false; + bool first = true; + unsigned prev_unit_offset = 0; + for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next) + if (aglat->is_single_const () + && (aglat->offset / BITS_PER_UNIT - unit_delta) >= 0) + { + ipa_argagg_value iav; + iav.value = aglat->values->value; + iav.unit_offset = aglat->offset / BITS_PER_UNIT - unit_delta; + iav.index = dest_index; + iav.by_ref = plats->aggs_by_ref; + + gcc_assert (first + || iav.unit_offset > prev_unit_offset); + prev_unit_offset = iav.unit_offset; + first = false; + + pushed_sth = true; + res->safe_push (iav); + } + return pushed_sth; +} + +/* Turn all values in LIST that are not present in OTHER into NULL_TREEs. + Return the number of remaining valid entries. */ + +static unsigned +intersect_argaggs_with (vec<ipa_argagg_value> &elts, + const vec<ipa_argagg_value> &other) +{ + unsigned valid_entries = 0; + unsigned j = 0; + for (unsigned i = 0; i < elts.length (); i++) + { + if (!elts[i].value) + continue; + + unsigned this_index = elts[i].index; + unsigned this_offset = elts[i].unit_offset; + + while (j < other.length () + && (other[j].index < this_index + || (other[j].index == this_index + && other[j].unit_offset < this_offset))) + j++; + + if (j >= other.length ()) + { + elts[i].value = NULL_TREE; + continue; + } + + if (other[j].index == this_index + && other[j].unit_offset == this_offset + && other[j].by_ref == elts[i].by_ref + && other[j].value + && values_equal_for_ipcp_p (other[j].value, elts[i].value)) + valid_entries++; + else + elts[i].value = NULL_TREE; + } + return valid_entries; +} + /* Mark bot aggregate and scalar lattices as containing an unknown variable, return true is any of them has not been marked as such so far. */ @@ -1401,26 +1690,6 @@ ipacp_value_safe_for_type (tree param_type, tree value) return false; } -/* Return true iff X and Y should be considered equal values by IPA-CP. */ - -static bool -values_equal_for_ipcp_p (tree x, tree y) -{ - gcc_checking_assert (x != NULL_TREE && y != NULL_TREE); - - if (x == y) - return true; - - if (TREE_CODE (x) == ADDR_EXPR - && TREE_CODE (y) == ADDR_EXPR - && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL - && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL) - return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)), - DECL_INITIAL (TREE_OPERAND (y, 0)), 0); - else - return operand_equal_p (x, y, 0); -} - /* Return the result of a (possibly arithmetic) operation on the constant value INPUT. OPERAND is 2nd operand for binary operation. RES_TYPE is the type of the parameter to which the result is passed. Return @@ -1701,26 +1970,6 @@ ipa_value_range_from_jfunc (ipa_node_params *info, cgraph_edge *cs, return vr; } -/* See if NODE is a clone with a known aggregate value at a given OFFSET of a - parameter with the given INDEX. */ - -static tree -get_clone_agg_value (struct cgraph_node *node, HOST_WIDE_INT offset, - int index) -{ - struct ipa_agg_replacement_value *aggval; - - aggval = ipa_get_agg_replacements_for_node (node); - while (aggval) - { - if (aggval->offset == offset - && aggval->index == index) - return aggval->value; - aggval = aggval->next; - } - return NULL_TREE; -} - /* Determine whether ITEM, jump function for an aggregate part, evaluates to a single known constant value and if so, return it. Otherwise return NULL. NODE and INFO describes the caller node or the one it is inlined to, and @@ -1729,7 +1978,7 @@ get_clone_agg_value (struct cgraph_node *node, HOST_WIDE_INT offset, static tree ipa_agg_value_from_node (class ipa_node_params *info, struct cgraph_node *node, - struct ipa_agg_jf_item *item) + const ipa_agg_jf_item *item) { tree value = NULL_TREE; int src_idx; @@ -1749,9 +1998,13 @@ ipa_agg_value_from_node (class ipa_node_params *info, { if (item->jftype == IPA_JF_PASS_THROUGH) value = info->known_csts[src_idx]; - else - value = get_clone_agg_value (node, item->value.load_agg.offset, - src_idx); + else if (ipcp_transformation *ts = ipcp_get_transformation_summary (node)) + { + ipa_argagg_value_list avl (ts); + value = avl.get_value (src_idx, + item->value.load_agg.offset / BITS_PER_UNIT, + item->value.load_agg.by_ref); + } } else if (info->lattices) { @@ -2979,15 +3232,16 @@ propagate_constants_across_call (struct cgraph_edge *cs) } /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS - KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter - three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */ + KNOWN_CONTEXTS, and known aggregates either in AVS or KNOWN_AGGS return + the destination. The latter three can be NULL. If AGG_REPS is not NULL, + KNOWN_AGGS is ignored. */ static tree ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie, const vec<tree> &known_csts, const vec<ipa_polymorphic_call_context> &known_contexts, const vec<ipa_agg_value_set> &known_aggs, - struct ipa_agg_replacement_value *agg_reps, + const ipa_argagg_value_list *avs, bool *speculative) { int param_index = ie->indirect_info->param_index; @@ -3007,20 +3261,10 @@ ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie, if (ie->indirect_info->agg_contents) { t = NULL; - if (agg_reps && ie->indirect_info->guaranteed_unmodified) - { - while (agg_reps) - { - if (agg_reps->index == param_index - && agg_reps->offset == ie->indirect_info->offset - && agg_reps->by_ref == ie->indirect_info->by_ref) - { - t = agg_reps->value; - break; - } - agg_reps = agg_reps->next; - } - } + if (avs && ie->indirect_info->guaranteed_unmodified) + t = avs->get_value (param_index, + ie->indirect_info->offset / BITS_PER_UNIT, + ie->indirect_info->by_ref); if (!t) { const ipa_agg_value_set *agg; @@ -3063,20 +3307,10 @@ ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie, t = NULL; /* Try to work out value of virtual table pointer value in replacements. */ - if (!t && agg_reps && !ie->indirect_info->by_ref) - { - while (agg_reps) - { - if (agg_reps->index == param_index - && agg_reps->offset == ie->indirect_info->offset - && agg_reps->by_ref) - { - t = agg_reps->value; - break; - } - agg_reps = agg_reps->next; - } - } + if (!t && avs && !ie->indirect_info->by_ref) + t = avs->get_value (param_index, + ie->indirect_info->offset / BITS_PER_UNIT, + true); /* Try to work out value of virtual table pointer value in known aggregate values. */ @@ -4103,7 +4337,7 @@ ipcp_discover_new_direct_edges (struct cgraph_node *node, vec<tree> known_csts, vec<ipa_polymorphic_call_context> known_contexts, - struct ipa_agg_replacement_value *aggvals) + vec<ipa_argagg_value, va_gc> *aggvals) { struct cgraph_edge *ie, *next_ie; bool found = false; @@ -4114,8 +4348,9 @@ ipcp_discover_new_direct_edges (struct cgraph_node *node, bool speculative; next_ie = ie->next_callee; + ipa_argagg_value_list avs (aggvals); target = ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts, - vNULL, aggvals, &speculative); + vNULL, &avs, &speculative); if (target) { bool agg_contents = ie->indirect_info->agg_contents; @@ -4249,11 +4484,15 @@ cgraph_edge_brings_value_p (cgraph_edge *cs, ipcp_value_source<tree> *src, if (caller_info->ipcp_orig_node) { - tree t; + tree t = NULL_TREE; if (src->offset == -1) t = caller_info->known_csts[src->index]; - else - t = get_clone_agg_value (cs->caller, src->offset, src->index); + else if (ipcp_transformation *ts + = ipcp_get_transformation_summary (cs->caller)) + { + ipa_argagg_value_list avl (ts); + t = avl.get_value (src->index, src->offset / BITS_PER_UNIT); + } return (t != NULL_TREE && values_equal_for_ipcp_p (src->val->value, t)); } @@ -5060,13 +5299,12 @@ static struct cgraph_node * create_specialized_node (struct cgraph_node *node, vec<tree> known_csts, vec<ipa_polymorphic_call_context> known_contexts, - struct ipa_agg_replacement_value *aggvals, + vec<ipa_argagg_value, va_gc> *aggvals, vec<cgraph_edge *> &callers) { ipa_node_params *new_info, *info = ipa_node_params_sum->get (node); vec<ipa_replace_map *, va_gc> *replace_trees = NULL; vec<ipa_adjusted_param, va_gc> *new_params = NULL; - struct ipa_agg_replacement_value *av; struct cgraph_node *new_node; int i, count = ipa_get_param_count (info); clone_info *cinfo = clone_info::get (node); @@ -5194,8 +5432,8 @@ create_specialized_node (struct cgraph_node *node, new_node->expand_all_artificial_thunks (); ipa_set_node_agg_value_chain (new_node, aggvals); - for (av = aggvals; av; av = av->next) - new_node->maybe_create_reference (av->value, NULL); + for (const ipa_argagg_value &av : aggvals) + new_node->maybe_create_reference (av.value, NULL); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -5210,7 +5448,11 @@ create_specialized_node (struct cgraph_node *node, } } if (aggvals) - ipa_dump_agg_replacement_values (dump_file, aggvals); + { + fprintf (dump_file, " Aggregate replacements:"); + ipa_argagg_value_list avs (aggvals); + avs.dump (dump_file); + } } new_info = ipa_node_params_sum->get (new_node); @@ -5219,7 +5461,8 @@ create_specialized_node (struct cgraph_node *node, new_info->known_csts = known_csts; new_info->known_contexts = known_contexts; - ipcp_discover_new_direct_edges (new_node, known_csts, known_contexts, aggvals); + ipcp_discover_new_direct_edges (new_node, known_csts, known_contexts, + aggvals); return new_node; } @@ -5252,7 +5495,8 @@ self_recursive_pass_through_p (cgraph_edge *cs, ipa_jump_func *jfunc, int i, pass-through. */ static bool -self_recursive_agg_pass_through_p (cgraph_edge *cs, ipa_agg_jf_item *jfunc, +self_recursive_agg_pass_through_p (const cgraph_edge *cs, + const ipa_agg_jf_item *jfunc, int i, bool simple = true) { enum availability availability; @@ -5427,376 +5671,215 @@ find_more_contexts_for_caller_subset (cgraph_node *node, } } -/* Go through PLATS and create a vector of values consisting of values and - offsets (minus OFFSET) of lattices that contain only a single value. */ +/* Push all aggregate values coming along edge CS for parameter number INDEX to + RES. If INTERIM is non-NULL, it contains the current interim state of + collected aggregate values which can be used to compute values passed over + self-recursive edges. -static vec<ipa_agg_value> -copy_plats_to_inter (class ipcp_param_lattices *plats, HOST_WIDE_INT offset) -{ - vec<ipa_agg_value> res = vNULL; - - if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom) - return vNULL; - - for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next) - if (aglat->is_single_const ()) - { - struct ipa_agg_value ti; - ti.offset = aglat->offset - offset; - ti.value = aglat->values->value; - res.safe_push (ti); - } - return res; -} - -/* Intersect all values in INTER with single value lattices in PLATS (while - subtracting OFFSET). */ + This basically one iteration of push_agg_values_from_edge over one + parameter, which allows for simpler early returns. */ static void -intersect_with_plats (class ipcp_param_lattices *plats, - vec<ipa_agg_value> *inter, - HOST_WIDE_INT offset) +push_agg_values_for_index_from_edge (struct cgraph_edge *cs, int index, + vec<ipa_argagg_value> *res, + const ipa_argagg_value_list *interim) { - struct ipcp_agg_lattice *aglat; - struct ipa_agg_value *item; - int k; + bool agg_values_from_caller = false; + bool agg_jf_preserved = false; + unsigned unit_delta = UINT_MAX; + int src_idx = -1; + ipa_jump_func *jfunc = ipa_get_ith_jump_func (ipa_edge_args_sum->get (cs), + index); - if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom) - { - inter->release (); - return; - } - - aglat = plats->aggs; - FOR_EACH_VEC_ELT (*inter, k, item) - { - bool found = false; - if (!item->value) - continue; - while (aglat) - { - if (aglat->offset - offset > item->offset) - break; - if (aglat->offset - offset == item->offset) - { - if (aglat->is_single_const ()) - { - tree value = aglat->values->value; - - if (values_equal_for_ipcp_p (item->value, value)) - found = true; - } - break; - } - aglat = aglat->next; - } - if (!found) - item->value = NULL_TREE; - } -} - -/* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the - vector result while subtracting OFFSET from the individual value offsets. */ - -static vec<ipa_agg_value> -agg_replacements_to_vector (struct cgraph_node *node, int index, - HOST_WIDE_INT offset) -{ - struct ipa_agg_replacement_value *av; - vec<ipa_agg_value> res = vNULL; - - for (av = ipa_get_agg_replacements_for_node (node); av; av = av->next) - if (av->index == index - && (av->offset - offset) >= 0) - { - struct ipa_agg_value item; - gcc_checking_assert (av->value); - item.offset = av->offset - offset; - item.value = av->value; - res.safe_push (item); - } - - return res; -} - -/* Intersect all values in INTER with those that we have already scheduled to - be replaced in parameter number INDEX of NODE, which is an IPA-CP clone - (while subtracting OFFSET). */ - -static void -intersect_with_agg_replacements (struct cgraph_node *node, int index, - vec<ipa_agg_value> *inter, - HOST_WIDE_INT offset) -{ - struct ipa_agg_replacement_value *srcvals; - struct ipa_agg_value *item; - int i; - - srcvals = ipa_get_agg_replacements_for_node (node); - if (!srcvals) - { - inter->release (); - return; - } - - FOR_EACH_VEC_ELT (*inter, i, item) - { - struct ipa_agg_replacement_value *av; - bool found = false; - if (!item->value) - continue; - for (av = srcvals; av; av = av->next) - { - gcc_checking_assert (av->value); - if (av->index == index - && av->offset - offset == item->offset) - { - if (values_equal_for_ipcp_p (item->value, av->value)) - found = true; - break; - } - } - if (!found) - item->value = NULL_TREE; - } -} - -/* Intersect values in INTER with aggregate values that come along edge CS to - parameter number INDEX and return it. If INTER does not actually exist yet, - copy all incoming values to it. If we determine we ended up with no values - whatsoever, return a released vector. */ - -static vec<ipa_agg_value> -intersect_aggregates_with_edge (struct cgraph_edge *cs, int index, - vec<ipa_agg_value> inter) -{ - struct ipa_jump_func *jfunc; - jfunc = ipa_get_ith_jump_func (ipa_edge_args_sum->get (cs), index); if (jfunc->type == IPA_JF_PASS_THROUGH && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR) { - ipa_node_params *caller_info = ipa_node_params_sum->get (cs->caller); - int src_idx = ipa_get_jf_pass_through_formal_id (jfunc); - - if (caller_info->ipcp_orig_node) - { - struct cgraph_node *orig_node = caller_info->ipcp_orig_node; - class ipcp_param_lattices *orig_plats; - ipa_node_params *orig_info = ipa_node_params_sum->get (orig_node); - orig_plats = ipa_get_parm_lattices (orig_info, src_idx); - if (agg_pass_through_permissible_p (orig_plats, jfunc)) - { - if (!inter.exists ()) - inter = agg_replacements_to_vector (cs->caller, src_idx, 0); - else - intersect_with_agg_replacements (cs->caller, src_idx, - &inter, 0); - return inter; - } - } - else - { - class ipcp_param_lattices *src_plats; - src_plats = ipa_get_parm_lattices (caller_info, src_idx); - if (agg_pass_through_permissible_p (src_plats, jfunc)) - { - /* Currently we do not produce clobber aggregate jump - functions, adjust when we do. */ - gcc_checking_assert (!jfunc->agg.items); - if (!inter.exists ()) - inter = copy_plats_to_inter (src_plats, 0); - else - intersect_with_plats (src_plats, &inter, 0); - return inter; - } - } + agg_values_from_caller = true; + agg_jf_preserved = ipa_get_jf_pass_through_agg_preserved (jfunc); + src_idx = ipa_get_jf_pass_through_formal_id (jfunc); + unit_delta = 0; } else if (jfunc->type == IPA_JF_ANCESTOR && ipa_get_jf_ancestor_agg_preserved (jfunc)) { - ipa_node_params *caller_info = ipa_node_params_sum->get (cs->caller); - int src_idx = ipa_get_jf_ancestor_formal_id (jfunc); - class ipcp_param_lattices *src_plats; - HOST_WIDE_INT delta = ipa_get_jf_ancestor_offset (jfunc); + agg_values_from_caller = true; + agg_jf_preserved = true; + src_idx = ipa_get_jf_ancestor_formal_id (jfunc); + unit_delta = ipa_get_jf_ancestor_offset (jfunc) / BITS_PER_UNIT; + } + ipa_node_params *caller_info = ipa_node_params_sum->get (cs->caller); + if (agg_values_from_caller) + { if (caller_info->ipcp_orig_node) { - if (!inter.exists ()) - inter = agg_replacements_to_vector (cs->caller, src_idx, delta); - else - intersect_with_agg_replacements (cs->caller, src_idx, &inter, - delta); + struct cgraph_node *orig_node = caller_info->ipcp_orig_node; + ipcp_transformation *ts + = ipcp_get_transformation_summary (cs->caller); + ipa_node_params *orig_info = ipa_node_params_sum->get (orig_node); + ipcp_param_lattices *orig_plats + = ipa_get_parm_lattices (orig_info, src_idx); + if (ts + && orig_plats->aggs + && (agg_jf_preserved || !orig_plats->aggs_by_ref)) + { + ipa_argagg_value_list src (ts); + src.push_adjusted_values (src_idx, index, unit_delta, res); + return; + } } else { - src_plats = ipa_get_parm_lattices (caller_info, src_idx); - /* Currently we do not produce clobber aggregate jump - functions, adjust when we do. */ - gcc_checking_assert (!src_plats->aggs || !jfunc->agg.items); - if (!inter.exists ()) - inter = copy_plats_to_inter (src_plats, delta); - else - intersect_with_plats (src_plats, &inter, delta); + ipcp_param_lattices *src_plats + = ipa_get_parm_lattices (caller_info, src_idx); + if (src_plats->aggs + && !src_plats->aggs_bottom + && (agg_jf_preserved || !src_plats->aggs_by_ref)) + { + if (interim && self_recursive_pass_through_p (cs, jfunc, index)) + { + interim->push_adjusted_values (src_idx, index, unit_delta, + res); + return; + } + if (!src_plats->aggs_contain_variable) + { + push_agg_values_from_plats (src_plats, index, unit_delta, + res); + return; + } + } } - return inter; } - if (jfunc->agg.items) + if (!jfunc->agg.items) + return; + bool first = true; + unsigned prev_unit_offset = 0; + for (const ipa_agg_jf_item &agg_jf : *jfunc->agg.items) { - ipa_node_params *caller_info = ipa_node_params_sum->get (cs->caller); - struct ipa_agg_value *item; - int k; + tree value, srcvalue; + /* Besides simple pass-through aggregate jump function, arithmetic + aggregate jump function could also bring same aggregate value as + parameter passed-in for self-feeding recursive call. For example, - if (!inter.exists ()) - for (unsigned i = 0; i < jfunc->agg.items->length (); i++) - { - struct ipa_agg_jf_item *agg_item = &(*jfunc->agg.items)[i]; - tree value = ipa_agg_value_from_node (caller_info, cs->caller, - agg_item); - if (value) - { - struct ipa_agg_value agg_value; + fn (int *i) + { + int j = *i & 1; + fn (&j); + } - agg_value.value = value; - agg_value.offset = agg_item->offset; - inter.safe_push (agg_value); - } - } + Given that *i is 0, recursive propagation via (*i & 1) also gets 0. */ + if (interim + && self_recursive_agg_pass_through_p (cs, &agg_jf, index, false) + && (srcvalue = interim->get_value(index, + agg_jf.offset / BITS_PER_UNIT))) + value = ipa_get_jf_arith_result (agg_jf.value.pass_through.operation, + srcvalue, + agg_jf.value.pass_through.operand, + agg_jf.type); else - FOR_EACH_VEC_ELT (inter, k, item) - { - int l = 0; - bool found = false; + value = ipa_agg_value_from_node (caller_info, cs->caller, + &agg_jf); + if (value) + { + struct ipa_argagg_value iav; + iav.value = value; + iav.unit_offset = agg_jf.offset / BITS_PER_UNIT; + iav.index = index; + iav.by_ref = jfunc->agg.by_ref; - if (!item->value) - continue; + gcc_assert (first + || iav.unit_offset > prev_unit_offset); + prev_unit_offset = iav.unit_offset; + first = false; - while ((unsigned) l < jfunc->agg.items->length ()) - { - struct ipa_agg_jf_item *ti; - ti = &(*jfunc->agg.items)[l]; - if (ti->offset > item->offset) - break; - if (ti->offset == item->offset) - { - tree value; - - /* Besides simple pass-through aggregate jump function, - arithmetic aggregate jump function could also bring - same aggregate value as parameter passed-in for - self-feeding recursive call. For example, - - fn (int *i) - { - int j = *i & 1; - fn (&j); - } - - Given that *i is 0, recursive propagation via (*i & 1) - also gets 0. */ - if (self_recursive_agg_pass_through_p (cs, ti, index, - false)) - value = ipa_get_jf_arith_result ( - ti->value.pass_through.operation, - item->value, - ti->value.pass_through.operand, - ti->type); - else - value = ipa_agg_value_from_node (caller_info, - cs->caller, ti); - - if (value && values_equal_for_ipcp_p (item->value, value)) - found = true; - break; - } - l++; - } - if (!found) - item->value = NULL; - } + res->safe_push (iav); + } } - else - { - inter.release (); - return vNULL; - } - return inter; + return; } -/* Look at edges in CALLERS and collect all known aggregate values that arrive - from all of them. */ +/* Push all aggregate values coming along edge CS to RES. DEST_INFO is the + description of ultimate callee of CS or the one it was cloned from (the + summary where lattices are). If INTERIM is non-NULL, it contains the + current interim state of collected aggregate values which can be used to + compute values passed over self-recursive edges and to skip values which + clearly will not be part of intersection with INTERIM. */ -static struct ipa_agg_replacement_value * +static void +push_agg_values_from_edge (struct cgraph_edge *cs, + ipa_node_params *dest_info, + vec<ipa_argagg_value> *res, + const ipa_argagg_value_list *interim) +{ + ipa_edge_args *args = ipa_edge_args_sum->get (cs); + if (!args) + return; + + int count = MIN (ipa_get_param_count (dest_info), + ipa_get_cs_argument_count (args)); + + unsigned interim_index = 0; + for (int index = 0; index < count; index++) + { + if (interim) + { + while (interim_index < interim->m_elts.size () + && interim->m_elts[interim_index].value + && interim->m_elts[interim_index].index < index) + interim_index++; + if (interim_index >= interim->m_elts.size () + || interim->m_elts[interim_index].index > index) + continue; + } + + ipcp_param_lattices *plats = ipa_get_parm_lattices (dest_info, index); + if (plats->aggs_bottom) + continue; + push_agg_values_for_index_from_edge (cs, index, res, interim); + } +} + + +/* Look at edges in CALLERS and collect all known aggregate values that arrive + from all of them. Return nullptr if there are none. */ + +static struct vec<ipa_argagg_value, va_gc> * find_aggregate_values_for_callers_subset (struct cgraph_node *node, const vec<cgraph_edge *> &callers) { ipa_node_params *dest_info = ipa_node_params_sum->get (node); - struct ipa_agg_replacement_value *res; - struct ipa_agg_replacement_value **tail = &res; - struct cgraph_edge *cs; - int i, j, count = ipa_get_param_count (dest_info); + if (dest_info->ipcp_orig_node) + dest_info = ipa_node_params_sum->get (dest_info->ipcp_orig_node); - FOR_EACH_VEC_ELT (callers, j, cs) + /* gather_edges_for_value puts a non-recursive call into the first element of + callers if it can. */ + auto_vec<ipa_argagg_value, 32> interim; + push_agg_values_from_edge (callers[0], dest_info, &interim, NULL); + + unsigned valid_entries = interim.length (); + if (!valid_entries) + return nullptr; + + unsigned caller_count = callers.length(); + for (unsigned i = 1; i < caller_count; i++) { - ipa_edge_args *args = ipa_edge_args_sum->get (cs); - if (!args) - { - count = 0; - break; - } - int c = ipa_get_cs_argument_count (args); - if (c < count) - count = c; + auto_vec<ipa_argagg_value, 32> last; + ipa_argagg_value_list avs (&interim); + push_agg_values_from_edge (callers[i], dest_info, &last, &avs); + + valid_entries = intersect_argaggs_with (interim, last); + if (!valid_entries) + return nullptr; } - for (i = 0; i < count; i++) - { - struct cgraph_edge *cs; - vec<ipa_agg_value> inter = vNULL; - struct ipa_agg_value *item; - class ipcp_param_lattices *plats = ipa_get_parm_lattices (dest_info, i); - int j; - - /* Among other things, the following check should deal with all by_ref - mismatches. */ - if (plats->aggs_bottom) - continue; - - FOR_EACH_VEC_ELT (callers, j, cs) - { - struct ipa_jump_func *jfunc - = ipa_get_ith_jump_func (ipa_edge_args_sum->get (cs), i); - if (self_recursive_pass_through_p (cs, jfunc, i) - && (!plats->aggs_by_ref - || ipa_get_jf_pass_through_agg_preserved (jfunc))) - continue; - inter = intersect_aggregates_with_edge (cs, i, inter); - - if (!inter.exists ()) - goto next_param; - } - - FOR_EACH_VEC_ELT (inter, j, item) - { - struct ipa_agg_replacement_value *v; - - if (!item->value) - continue; - - v = ggc_alloc<ipa_agg_replacement_value> (); - v->index = i; - v->offset = item->offset; - v->value = item->value; - v->by_ref = plats->aggs_by_ref; - *tail = v; - tail = &v->next; - } - - next_param: - if (inter.exists ()) - inter.release (); - } - *tail = NULL; + vec<ipa_argagg_value, va_gc> *res = NULL; + vec_safe_reserve_exact (res, valid_entries); + for (const ipa_argagg_value &av : interim) + if (av.value) + res->quick_push(av); + gcc_checking_assert (res->length () == valid_entries); return res; } @@ -5837,72 +5920,23 @@ cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge *cs, /* Determine whether CS also brings all aggregate values that NODE is specialized for. */ + static bool cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge *cs, struct cgraph_node *node) { - struct ipa_agg_replacement_value *aggval; - int i, ec, count; - - aggval = ipa_get_agg_replacements_for_node (node); - if (!aggval) + ipcp_transformation *ts = ipcp_get_transformation_summary (node); + if (!ts || vec_safe_is_empty (ts->m_agg_values)) return true; - ipa_node_params *clone_node_info = ipa_node_params_sum->get (node); - count = ipa_get_param_count (clone_node_info); - ec = ipa_get_cs_argument_count (ipa_edge_args_sum->get (cs)); - if (ec < count) - for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next) - if (aggval->index >= ec) - return false; - - ipa_node_params *orig_node_info - = ipa_node_params_sum->get (clone_node_info->ipcp_orig_node); - - for (i = 0; i < count; i++) - { - class ipcp_param_lattices *plats; - bool interesting = false; - for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next) - if (aggval->index == i) - { - interesting = true; - break; - } - if (!interesting) - continue; - - plats = ipa_get_parm_lattices (orig_node_info, aggval->index); - if (plats->aggs_bottom) - return false; - - vec<ipa_agg_value> values = intersect_aggregates_with_edge (cs, i, vNULL); - if (!values.exists ()) - return false; - - for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next) - if (aggval->index == i) - { - struct ipa_agg_value *item; - int j; - bool found = false; - FOR_EACH_VEC_ELT (values, j, item) - if (item->value - && item->offset == av->offset - && values_equal_for_ipcp_p (item->value, av->value)) - { - found = true; - break; - } - if (!found) - { - values.release (); - return false; - } - } - values.release (); - } - return true; + const ipa_argagg_value_list existing (ts->m_agg_values); + auto_vec<ipa_argagg_value, 32> edge_values; + ipa_node_params *dest_info = ipa_node_params_sum->get (node); + gcc_checking_assert (dest_info->ipcp_orig_node); + dest_info = ipa_node_params_sum->get (dest_info->ipcp_orig_node); + push_agg_values_from_edge (cs, dest_info, &edge_values, &existing); + const ipa_argagg_value_list avl (&edge_values); + return avl.superset_of_p (existing); } /* Given an original NODE and a VAL for which we have already created a @@ -6006,28 +6040,22 @@ copy_known_vectors_add_val (ipa_auto_call_arg_values *avals, AGGVALS list. */ DEBUG_FUNCTION bool -ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *aggvals, +ipcp_val_agg_replacement_ok_p (vec<ipa_argagg_value, va_gc> *aggvals, int index, HOST_WIDE_INT offset, tree value) { if (offset == -1) return true; - while (aggvals) - { - if (aggvals->index == index - && aggvals->offset == offset - && values_equal_for_ipcp_p (aggvals->value, value)) - return true; - aggvals = aggvals->next; - } - return false; + const ipa_argagg_value_list avl (aggvals); + tree v = avl.get_value (index, offset / BITS_PER_UNIT); + return v && values_equal_for_ipcp_p (v, value); } /* Return true if offset is minus one because source of a polymorphic context cannot be an aggregate value. */ DEBUG_FUNCTION bool -ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *, +ipcp_val_agg_replacement_ok_p (vec<ipa_argagg_value, va_gc> *, int , HOST_WIDE_INT offset, ipa_polymorphic_call_context) { @@ -6047,7 +6075,6 @@ decide_about_value (struct cgraph_node *node, int index, HOST_WIDE_INT offset, ipcp_value<valtype> *val, ipa_auto_call_arg_values *avals, vec<cgraph_node *> *self_gen_clones) { - struct ipa_agg_replacement_value *aggvals; int caller_count; sreal freq_sum; profile_count count_sum, rec_count_sum; @@ -6126,7 +6153,8 @@ decide_about_value (struct cgraph_node *node, int index, HOST_WIDE_INT offset, } find_more_scalar_values_for_callers_subset (node, known_csts, callers); find_more_contexts_for_caller_subset (node, &known_contexts, callers); - aggvals = find_aggregate_values_for_callers_subset (node, callers); + vec<ipa_argagg_value, va_gc> *aggvals + = find_aggregate_values_for_callers_subset (node, callers); gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals, index, offset, val->value)); val->spec_node = create_specialized_node (node, known_csts, known_contexts, @@ -6277,7 +6305,7 @@ decide_whether_version_node (struct cgraph_node *node) = copy_useful_known_contexts (avals.m_known_contexts); find_more_scalar_values_for_callers_subset (node, known_csts, callers); find_more_contexts_for_caller_subset (node, &known_contexts, callers); - ipa_agg_replacement_value *aggvals + vec<ipa_argagg_value, va_gc> *aggvals = find_aggregate_values_for_callers_subset (node, callers); if (!known_contexts_useful_p (known_contexts)) diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc index 724c9456308..24148a3bbba 100644 --- a/gcc/ipa-prop.cc +++ b/gcc/ipa-prop.cc @@ -1095,7 +1095,10 @@ parm_ref_data_pass_through_p (struct ipa_func_body_info *fbi, int index, latter can be NULL), STMT is the load statement. If function returns true, *INDEX_P, *OFFSET_P and *BY_REF is filled with the parameter index, offset within the aggregate and whether it is a load from a value passed by - reference respectively. */ + reference respectively. + + Return false if the offset divided by BITS_PER_UNIT would not fit into an + unsigned int. */ bool ipa_load_from_parm_agg (struct ipa_func_body_info *fbi, @@ -1109,7 +1112,8 @@ ipa_load_from_parm_agg (struct ipa_func_body_info *fbi, bool reverse; tree base = get_ref_base_and_extent_hwi (op, offset_p, &size, &reverse); - if (!base) + if (!base + || (*offset_p / BITS_PER_UNIT) > UINT_MAX) return false; /* We can not propagate across volatile loads. */ @@ -3057,13 +3061,11 @@ ipa_analyze_node (struct cgraph_node *node) return; info->analysis_done = 1; - if (ipa_func_spec_opts_forbid_analysis_p (node)) + if (ipa_func_spec_opts_forbid_analysis_p (node) + || (count_formal_params (node->decl) + >= (1 << IPA_PROP_ARG_INDEX_LIMIT_BITS))) { - for (int i = 0; i < ipa_get_param_count (info); i++) - { - ipa_set_param_used (info, i, true); - ipa_set_controlled_uses (info, i, IPA_UNDESCRIBED_USE); - } + gcc_assert (!ipa_get_param_count (info)); return; } @@ -4383,11 +4385,11 @@ ipcp_free_transformation_sum (void) void ipa_set_node_agg_value_chain (struct cgraph_node *node, - struct ipa_agg_replacement_value *aggvals) + vec<ipa_argagg_value, va_gc> *aggs) { ipcp_transformation_initialize (); ipcp_transformation *s = ipcp_transformation_sum->get_create (node); - s->agg_values = aggvals; + s->m_agg_values = aggs; } /* Hook that is called by cgraph.cc when an edge is removed. Adjust reference @@ -4532,12 +4534,10 @@ ipa_add_new_function (cgraph_node *node, void *data ATTRIBUTE_UNUSED) /* Hook that is called by summary when a node is duplicated. */ void -ipa_node_params_t::duplicate(cgraph_node *src, cgraph_node *dst, +ipa_node_params_t::duplicate(cgraph_node *, cgraph_node *, ipa_node_params *old_info, ipa_node_params *new_info) { - ipa_agg_replacement_value *old_av, *new_av; - new_info->descriptors = vec_safe_copy (old_info->descriptors); new_info->lattices = NULL; new_info->ipcp_orig_node = old_info->ipcp_orig_node; @@ -4547,23 +4547,6 @@ ipa_node_params_t::duplicate(cgraph_node *src, cgraph_node *dst, new_info->analysis_done = old_info->analysis_done; new_info->node_enqueued = old_info->node_enqueued; new_info->versionable = old_info->versionable; - - old_av = ipa_get_agg_replacements_for_node (src); - if (old_av) - { - new_av = NULL; - while (old_av) - { - struct ipa_agg_replacement_value *v; - - v = ggc_alloc<ipa_agg_replacement_value> (); - memcpy (v, old_av, sizeof (*v)); - v->next = new_av; - new_av = v; - old_av = old_av->next; - } - ipa_set_node_agg_value_chain (dst, new_av); - } } /* Duplication of ipcp transformation summaries. */ @@ -4576,17 +4559,9 @@ ipcp_transformation_t::duplicate(cgraph_node *, cgraph_node *dst, /* Avoid redundant work of duplicating vectors we will never use. */ if (dst->inlined_to) return; + dst_trans->m_agg_values = vec_safe_copy (src_trans->m_agg_values); dst_trans->bits = vec_safe_copy (src_trans->bits); dst_trans->m_vr = vec_safe_copy (src_trans->m_vr); - ipa_agg_replacement_value *agg = src_trans->agg_values, - **aggptr = &dst_trans->agg_values; - while (agg) - { - *aggptr = ggc_alloc<ipa_agg_replacement_value> (); - **aggptr = *agg; - agg = agg->next; - aggptr = &(*aggptr)->next; - } } /* Register our cgraph hooks if they are not already there. */ @@ -4703,23 +4678,6 @@ ipa_print_all_params (FILE * f) ipa_print_node_params (f, node); } -/* Dump the AV linked list. */ - -void -ipa_dump_agg_replacement_values (FILE *f, struct ipa_agg_replacement_value *av) -{ - bool comma = false; - fprintf (f, " Aggregate replacements:"); - for (; av; av = av->next) - { - fprintf (f, "%s %i[" HOST_WIDE_INT_PRINT_DEC "]=", comma ? "," : "", - av->index, av->offset); - print_generic_expr (f, av->value); - comma = true; - } - fprintf (f, "\n"); -} - /* Stream out jump function JUMP_FUNC to OB. */ static void @@ -5356,31 +5314,31 @@ write_ipcp_transformation_info (output_block *ob, cgraph_node *node) int node_ref; unsigned int count = 0; lto_symtab_encoder_t encoder; - struct ipa_agg_replacement_value *aggvals, *av; - aggvals = ipa_get_agg_replacements_for_node (node); encoder = ob->decl_state->symtab_node_encoder; node_ref = lto_symtab_encoder_encode (encoder, node); streamer_write_uhwi (ob, node_ref); - for (av = aggvals; av; av = av->next) - count++; - streamer_write_uhwi (ob, count); - - for (av = aggvals; av; av = av->next) - { - struct bitpack_d bp; - - streamer_write_uhwi (ob, av->offset); - streamer_write_uhwi (ob, av->index); - stream_write_tree (ob, av->value, true); - - bp = bitpack_create (ob->main_stream); - bp_pack_value (&bp, av->by_ref, 1); - streamer_write_bitpack (&bp); - } - ipcp_transformation *ts = ipcp_get_transformation_summary (node); + if (ts && !vec_safe_is_empty (ts->m_agg_values)) + { + streamer_write_uhwi (ob, ts->m_agg_values->length ()); + for (const ipa_argagg_value &av : ts->m_agg_values) + { + struct bitpack_d bp; + + stream_write_tree (ob, av.value, true); + streamer_write_uhwi (ob, av.unit_offset); + streamer_write_uhwi (ob, av.index); + + bp = bitpack_create (ob->main_stream); + bp_pack_value (&bp, av.by_ref, 1); + streamer_write_bitpack (&bp); + } + } + else + streamer_write_uhwi (ob, 0); + if (ts && vec_safe_length (ts->m_vr) > 0) { count = ts->m_vr->length (); @@ -5432,26 +5390,27 @@ static void read_ipcp_transformation_info (lto_input_block *ib, cgraph_node *node, data_in *data_in) { - struct ipa_agg_replacement_value *aggvals = NULL; unsigned int count, i; count = streamer_read_uhwi (ib); - for (i = 0; i <count; i++) + if (count > 0) { - struct ipa_agg_replacement_value *av; - struct bitpack_d bp; + ipcp_transformation_initialize (); + ipcp_transformation *ts = ipcp_transformation_sum->get_create (node); + vec_safe_grow_cleared (ts->m_agg_values, count, true); + for (i = 0; i <count; i++) + { + ipa_argagg_value *av = &(*ts->m_agg_values)[i];; - av = ggc_alloc<ipa_agg_replacement_value> (); - av->offset = streamer_read_uhwi (ib); - av->index = streamer_read_uhwi (ib); - av->value = stream_read_tree (ib, data_in); - bp = streamer_read_bitpack (ib); - av->by_ref = bp_unpack_value (&bp, 1); - av->next = aggvals; - aggvals = av; + av->value = stream_read_tree (ib, data_in); + av->unit_offset = streamer_read_uhwi (ib); + av->index = streamer_read_uhwi (ib); + + bitpack_d bp = streamer_read_bitpack (ib); + av->by_ref = bp_unpack_value (&bp, 1); + } } - ipa_set_node_agg_value_chain (node, aggvals); - + count = streamer_read_uhwi (ib); if (count > 0) { @@ -5595,56 +5554,75 @@ ipcp_read_transformation_summaries (void) } } -/* Adjust the aggregate replacements in AGGVAL to reflect parameters skipped in +/* Adjust the aggregate replacements in TS to reflect parameters skipped in NODE but also if any parameter was IPA-SRAed into a scalar go ahead with substitution of the default_definitions of that new param with the appropriate constant. - Return two bools. the first it true if at least one item in AGGVAL still - exists and function body walk should go ahead. The second is true if any - values were already substituted for scalarized parameters and update_cfg - shuld be run after replace_uses_by. */ + If after adjustments there are no aggregate replacements left, the + m_agg_values will be set to NULL. In other cases, it may be shrunk. -static std::pair<bool, bool> + Return true if any values were already substituted for scalarized parameters + and update_cfg shuld be run after replace_uses_by. */ + +static bool adjust_agg_replacement_values (cgraph_node *node, - ipa_agg_replacement_value *aggval, + ipcp_transformation *ts, const vec<ipa_param_descriptor, va_gc> &descriptors) { - struct ipa_agg_replacement_value *v; clone_info *cinfo = clone_info::get (node); if (!cinfo || !cinfo->param_adjustments) - return std::pair<bool, bool> (true, false); + return false; - bool anything_left = false; + bool removed_item = false; bool done_replacement = false; - for (v = aggval; v; v = v->next) + unsigned dst_index = 0; + unsigned count = ts->m_agg_values->length (); + for (unsigned i = 0; i < count; i++) { + ipa_argagg_value *v = &(*ts->m_agg_values)[i]; gcc_checking_assert (v->index >= 0); - unsigned unit_offset = v->offset / BITS_PER_UNIT; tree cst_type = TREE_TYPE (v->value); int split_idx; int new_idx = cinfo->param_adjustments->get_updated_index_or_split (v->index, - unit_offset, + v->unit_offset, cst_type, &split_idx); - v->index = new_idx; if (new_idx >= 0) - anything_left = true; - else if (split_idx >= 0) { - tree parm = ipa_get_param (descriptors, split_idx); - tree ddef = ssa_default_def (cfun, parm); - if (ddef) + v->index = new_idx; + if (removed_item) + (*ts->m_agg_values)[dst_index] = *v; + dst_index++; + } + else + { + removed_item = true; + if (split_idx >= 0) { - replace_uses_by (ddef, v->value); - done_replacement = true; + tree parm = ipa_get_param (descriptors, split_idx); + tree ddef = ssa_default_def (cfun, parm); + if (ddef) + { + replace_uses_by (ddef, v->value); + done_replacement = true; + } } } } - return std::pair<bool, bool> (anything_left, done_replacement); + + if (dst_index == 0) + { + ggc_free (ts->m_agg_values); + ts->m_agg_values = NULL; + } + else if (removed_item) + ts->m_agg_values->truncate (dst_index); + + return done_replacement; } /* Dominator walker driving the ipcp modification phase. */ @@ -5654,10 +5632,9 @@ class ipcp_modif_dom_walker : public dom_walker public: ipcp_modif_dom_walker (struct ipa_func_body_info *fbi, vec<ipa_param_descriptor, va_gc> *descs, - struct ipa_agg_replacement_value *av, - bool *sc) + ipcp_transformation *ts, bool *sc) : dom_walker (CDI_DOMINATORS), m_fbi (fbi), m_descriptors (descs), - m_aggval (av), m_something_changed (sc) {} + m_ts (ts), m_something_changed (sc) {} edge before_dom_children (basic_block) final override; bool cleanup_eh () @@ -5666,7 +5643,7 @@ public: private: struct ipa_func_body_info *m_fbi; vec<ipa_param_descriptor, va_gc> *m_descriptors; - struct ipa_agg_replacement_value *m_aggval; + ipcp_transformation *m_ts; bool *m_something_changed; auto_bitmap m_need_eh_cleanup; }; @@ -5677,10 +5654,9 @@ ipcp_modif_dom_walker::before_dom_children (basic_block bb) gimple_stmt_iterator gsi; for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { - struct ipa_agg_replacement_value *v; gimple *stmt = gsi_stmt (gsi); tree rhs, val, t; - HOST_WIDE_INT offset; + HOST_WIDE_INT bit_offset; poly_int64 size; int index; bool by_ref, vce; @@ -5708,32 +5684,30 @@ ipcp_modif_dom_walker::before_dom_children (basic_block bb) continue; if (!ipa_load_from_parm_agg (m_fbi, m_descriptors, stmt, rhs, &index, - &offset, &size, &by_ref)) + &bit_offset, &size, &by_ref)) continue; - for (v = m_aggval; v; v = v->next) - if (v->index == index - && v->offset == offset) - break; + unsigned unit_offset = bit_offset / BITS_PER_UNIT; + ipa_argagg_value_list avl (m_ts); + tree v = avl.get_value (index, unit_offset, by_ref); + if (!v - || v->by_ref != by_ref - || maybe_ne (tree_to_poly_int64 (TYPE_SIZE (TREE_TYPE (v->value))), - size)) + || maybe_ne (tree_to_poly_int64 (TYPE_SIZE (TREE_TYPE (v))), size)) continue; - gcc_checking_assert (is_gimple_ip_invariant (v->value)); - if (!useless_type_conversion_p (TREE_TYPE (rhs), TREE_TYPE (v->value))) + gcc_checking_assert (is_gimple_ip_invariant (v)); + if (!useless_type_conversion_p (TREE_TYPE (rhs), TREE_TYPE (v))) { - if (fold_convertible_p (TREE_TYPE (rhs), v->value)) - val = fold_build1 (NOP_EXPR, TREE_TYPE (rhs), v->value); + if (fold_convertible_p (TREE_TYPE (rhs), v)) + val = fold_build1 (NOP_EXPR, TREE_TYPE (rhs), v); else if (TYPE_SIZE (TREE_TYPE (rhs)) - == TYPE_SIZE (TREE_TYPE (v->value))) - val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (rhs), v->value); + == TYPE_SIZE (TREE_TYPE (v))) + val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (rhs), v); else { if (dump_file) { fprintf (dump_file, " const "); - print_generic_expr (dump_file, v->value); + print_generic_expr (dump_file, v); fprintf (dump_file, " can't be converted to type of "); print_generic_expr (dump_file, rhs); fprintf (dump_file, "\n"); @@ -5742,7 +5716,7 @@ ipcp_modif_dom_walker::before_dom_children (basic_block bb) } } else - val = v->value; + val = v; if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -6019,7 +5993,6 @@ ipcp_transform_function (struct cgraph_node *node) { vec<ipa_param_descriptor, va_gc> *descriptors = NULL; struct ipa_func_body_info fbi; - struct ipa_agg_replacement_value *aggval; int param_count; gcc_checking_assert (cfun); @@ -6031,18 +6004,17 @@ ipcp_transform_function (struct cgraph_node *node) ipcp_update_bits (node); ipcp_update_vr (node); - aggval = ipa_get_agg_replacements_for_node (node); - if (!aggval) + ipcp_transformation *ts = ipcp_get_transformation_summary (node); + if (!ts || vec_safe_is_empty (ts->m_agg_values)) return 0; param_count = count_formal_params (node->decl); if (param_count == 0) return 0; vec_safe_grow_cleared (descriptors, param_count, true); ipa_populate_param_decls (node, *descriptors); - std::pair<bool, bool> rr - = adjust_agg_replacement_values (node, aggval, *descriptors); - bool cfg_changed = rr.second; - if (!rr.first) + + bool cfg_changed = adjust_agg_replacement_values (node, ts, *descriptors); + if (vec_safe_is_empty (ts->m_agg_values)) { vec_free (descriptors); if (dump_file) @@ -6053,7 +6025,11 @@ ipcp_transform_function (struct cgraph_node *node) return 0; } if (dump_file) - ipa_dump_agg_replacement_values (dump_file, aggval); + { + fprintf (dump_file, " Aggregate replacements:"); + ipa_argagg_value_list avs (ts); + avs.dump (dump_file); + } fbi.node = node; fbi.info = NULL; @@ -6064,7 +6040,7 @@ ipcp_transform_function (struct cgraph_node *node) bool modified_mem_access = false; calculate_dominance_info (CDI_DOMINATORS); - ipcp_modif_dom_walker walker (&fbi, descriptors, aggval, &modified_mem_access); + ipcp_modif_dom_walker walker (&fbi, descriptors, ts, &modified_mem_access); walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); free_dominance_info (CDI_DOMINATORS); cfg_changed |= walker.cleanup_eh (); @@ -6076,7 +6052,7 @@ ipcp_transform_function (struct cgraph_node *node) fbi.bb_infos.release (); ipcp_transformation *s = ipcp_transformation_sum->get (node); - s->agg_values = NULL; + s->m_agg_values = NULL; s->bits = NULL; s->m_vr = NULL; diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h index e54842de9a3..008d34d0bc6 100644 --- a/gcc/ipa-prop.h +++ b/gcc/ipa-prop.h @@ -25,6 +25,11 @@ along with GCC; see the file COPYING3. If not see #define IPA_UNDESCRIBED_USE -1 +/* Index identifying an actualargument or a formal parameter may have only this + many bits. */ + +#define IPA_PROP_ARG_INDEX_LIMIT_BITS 16 + /* ipa-prop.cc stuff (ipa-cp, indirect inlining): */ /* A jump function for a callsite represents the values passed as actual @@ -184,6 +189,92 @@ struct GTY(()) ipa_agg_jump_function bool by_ref; }; +class ipcp_transformation; + +/* Element of a vector describing aggregate values for a number of arguments in + a particular context, be it a call or the aggregate constants that a node is + specialized for. */ + +struct GTY(()) ipa_argagg_value +{ + /* The constant value. In the contexts where the list of known values is + being pruned, NULL means a variable value. */ + tree value; + /* Unit offset within the aggregate. */ + unsigned unit_offset; + /* Index of the parameter, as it was in the original function (i.e. needs + remapping after parameter modification is carried out as part of clone + materialization). */ + unsigned index : IPA_PROP_ARG_INDEX_LIMIT_BITS; + /* Whether the value was passed by reference. */ + unsigned by_ref : 1; +}; + +/* A view into a sorted list of aggregate values in a particular context, be it + a call or the aggregate constants that a node is specialized for. The + actual data is stored in the vector this has been constructed from. */ + +class ipa_argagg_value_list +{ +public: + ipa_argagg_value_list () = delete; + ipa_argagg_value_list (const vec<ipa_argagg_value, va_gc> *values) + : m_elts (values) + {} + ipa_argagg_value_list (const vec<ipa_argagg_value> *values) + : m_elts (*values) + {} + ipa_argagg_value_list (const ipcp_transformation *tinfo); + + /* Return the aggregate constant stored for INDEX at UNIT_OFFSET, if it is + passed by reference or not according to BY_REF, or NULL_TREE + otherwise. */ + + tree get_value (int index, unsigned unit_offset, bool by_ref) const; + + /* Return the aggregate constant stored for INDEX at UNIT_OFFSET, not + performing any check of whether value is passed by reference. Return + NULL_TREE if there is no such constant. */ + + tree get_value (int index, unsigned unit_offset) const; + + /* Return the item describing a constant stored for INDEX at UNIT_OFFSET or + NULL if there is no such constant. */ + + const ipa_argagg_value *get_elt (int index, unsigned unit_offset) const; + + /* Return the first item describing a constant stored for parameter with + INDEX, regardless of offset or reference, or NULL if there is no such + constant. */ + + const ipa_argagg_value *get_elt_for_index (int index) const; + + /* Return true if all elements present in OTHER are also present in this + list. */ + + bool superset_of_p (const ipa_argagg_value_list &other) const; + + /* Push all items in this list that describe parameter SRC_INDEX into RES as + ones describing DST_INDEX while subtracting UNIT_DELTA from their unit + offsets but skip those which would end up with a negative offset. */ + + void push_adjusted_values (unsigned src_index, unsigned dest_index, + unsigned unit_delta, + vec<ipa_argagg_value> *res) const; + + /* Dump aggregate constants to FILE. */ + + void dump (FILE *f); + + /* Dump aggregate constants to stderr. */ + + void DEBUG_FUNCTION debug (); + + /* Array slice pointing to the actual storage. */ + + array_slice<const ipa_argagg_value> m_elts; +}; + /* An element in an aggregate part describing a known value at a given offset. All unlisted positions are assumed to be unknown and all listed values must fulfill is_gimple_ip_invariant. */ @@ -882,28 +973,12 @@ ipa_is_param_used_by_polymorphic_call (class ipa_node_params *info, int i) return (*info->descriptors)[i].used_by_polymorphic_call; } -/* Information about replacements done in aggregates for a given node (each - node has its linked list). */ -struct GTY(()) ipa_agg_replacement_value -{ - /* Next item in the linked list. */ - struct ipa_agg_replacement_value *next; - /* Offset within the aggregate. */ - HOST_WIDE_INT offset; - /* The constant value. */ - tree value; - /* The parameter index. */ - int index; - /* Whether the value was passed by reference. */ - bool by_ref; -}; - /* Structure holding information for the transformation phase of IPA-CP. */ struct GTY(()) ipcp_transformation { - /* Linked list of known aggregate values. */ - ipa_agg_replacement_value *agg_values; + /* Known aggregate values. */ + vec<ipa_argagg_value, va_gc> *m_agg_values; /* Known bits information. */ vec<ipa_bits *, va_gc> *bits; /* Value range information. */ @@ -911,26 +986,25 @@ struct GTY(()) ipcp_transformation /* Default constructor. */ ipcp_transformation () - : agg_values (NULL), bits (NULL), m_vr (NULL) + : m_agg_values (NULL), bits (NULL), m_vr (NULL) { } /* Default destructor. */ ~ipcp_transformation () { - ipa_agg_replacement_value *agg = agg_values; - while (agg) - { - ipa_agg_replacement_value *next = agg->next; - ggc_free (agg); - agg = next; - } + vec_free (m_agg_values); vec_free (bits); vec_free (m_vr); } }; +inline +ipa_argagg_value_list::ipa_argagg_value_list (const ipcp_transformation *tinfo) + : m_elts (tinfo->m_agg_values) +{} + void ipa_set_node_agg_value_chain (struct cgraph_node *node, - struct ipa_agg_replacement_value *aggvals); + vec<ipa_argagg_value, va_gc> *aggs); void ipcp_transformation_initialize (void); void ipcp_free_transformation_sum (void); @@ -1107,15 +1181,6 @@ ipcp_get_transformation_summary (cgraph_node *node) return ipcp_transformation_sum->get (node); } -/* Return the aggregate replacements for NODE, if there are any. */ - -static inline struct ipa_agg_replacement_value * -ipa_get_agg_replacements_for_node (cgraph_node *node) -{ - ipcp_transformation *ts = ipcp_get_transformation_summary (node); - return ts ? ts->agg_values : NULL; -} - /* Function formal parameters related computations. */ void ipa_initialize_node_params (struct cgraph_node *node); bool ipa_propagate_indirect_call_infos (struct cgraph_edge *cs, @@ -1171,8 +1236,6 @@ struct ipcp_agg_lattice; extern object_allocator<ipcp_agg_lattice> ipcp_agg_lattice_pool; -void ipa_dump_agg_replacement_values (FILE *f, - struct ipa_agg_replacement_value *av); void ipa_prop_write_jump_functions (void); void ipa_prop_read_jump_functions (void); void ipcp_write_transformation_summaries (void); diff --git a/gcc/testsuite/gcc.dg/ipa/ipcp-agg-11.c b/gcc/testsuite/gcc.dg/ipa/ipcp-agg-11.c index 3c496eeef39..48bf77222b2 100644 --- a/gcc/testsuite/gcc.dg/ipa/ipcp-agg-11.c +++ b/gcc/testsuite/gcc.dg/ipa/ipcp-agg-11.c @@ -73,5 +73,5 @@ entry () /* { dg-final { scan-ipa-dump "offset: 0, type: int, CONST: 101" "cp" } } */ /* { dg-final { scan-ipa-dump "offset: 32, type: int, PASS THROUGH: 0, op trunc_mod_expr 7" "cp" } } */ /* { dg-final { scan-ipa-dump "offset: 64, type: int, LOAD AGG: 1 \\\[offset: 0, by reference], op plus_expr 6" "cp" } } */ -/* { dg-final { scan-ipa-dump "Aggregate replacements: 0\\\[0]=1, 0\\\[32]=105, 0\\\[64]=-18" "cp" } } */ -/* { dg-final { scan-ipa-dump "Aggregate replacements: 0\\\[0]=101, 0\\\[32]=2, 0\\\[64]=9" "cp" } } */ +/* { dg-final { scan-ipa-dump "Aggregate replacements: 0\\\[0]=1\\(by_ref\\), 0\\\[4]=105\\(by_ref\\), 0\\\[8]=-18\\(by_ref\\)" "cp" } } */ +/* { dg-final { scan-ipa-dump "Aggregate replacements: 0\\\[0]=101, 0\\\[4]=2, 0\\\[8]=9" "cp" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/ipcp-agg-8.c b/gcc/testsuite/gcc.dg/ipa/ipcp-agg-8.c index 2d9c82f7310..8234702dd6e 100644 --- a/gcc/testsuite/gcc.dg/ipa/ipcp-agg-8.c +++ b/gcc/testsuite/gcc.dg/ipa/ipcp-agg-8.c @@ -48,5 +48,5 @@ entry (int c) foo (4, i, &s); } } -/* { dg-final { scan-ipa-dump "Aggregate replacements: 1\\\[32]=64, 1\\\[64]=32" "cp" } } */ -/* { dg-final { scan-ipa-dump "Aggregate replacements: 1\\\[32]=0" "cp" } } */ +/* { dg-final { scan-ipa-dump "Aggregate replacements: 1\\\[4]=64\\(by_ref\\), 1\\\[8]=32\\(by_ref\\)" "cp" } } */ +/* { dg-final { scan-ipa-dump "Aggregate replacements: 1\\\[4]=0\\(by_ref\\)" "cp" } } */
diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc index 543a9334e2c..024f8c06b5d 100644 --- a/gcc/ipa-cp.cc +++ b/gcc/ipa-cp.cc @@ -127,6 +127,7 @@ along with GCC; see the file COPYING3. If not see #include "attribs.h" #include "dbgcnt.h" #include "symtab-clones.h" +#include <algorithm> template <typename valtype> class ipcp_value; @@ -455,6 +456,26 @@ ipcp_lattice<valtype>::is_single_const () return true; } +/* Return true iff X and Y should be considered equal values by IPA-CP. */ + +static bool +values_equal_for_ipcp_p (tree x, tree y) +{ + gcc_checking_assert (x != NULL_TREE && y != NULL_TREE); + + if (x == y) + return true; + + if (TREE_CODE (x) == ADDR_EXPR + && TREE_CODE (y) == ADDR_EXPR + && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL + && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL) + return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)), + DECL_INITIAL (TREE_OPERAND (y, 0)), 0); + else + return operand_equal_p (x, y, 0); +} + /* Print V which is extracted from a value in a lattice to F. */ static void @@ -1217,6 +1238,272 @@ ipcp_bits_lattice::meet_with (ipcp_bits_lattice& other, unsigned precision, drop_all_ones); } +/* Dump the contents of the list to FILE. */ + +void +ipa_argagg_value_list::dump (FILE *f) +{ + bool comma = false; + for (const ipa_argagg_value &av : m_elts) + { + fprintf (f, "%s %i[%u]=", comma ? "," : "", + av.index, av.unit_offset); + print_generic_expr (f, av.value); + if (av.by_ref) + fprintf (f, "(by_ref)"); + comma = true; + } + fprintf (f, "\n"); +} + +/* Dump the contents of the list to stderr. */ + +void +ipa_argagg_value_list::debug () +{ + dump (stderr); +} + +/* Return the item describing a constant stored for INDEX at UNIT_OFFSET or + NULL if there is no such constant. */ + +const ipa_argagg_value * +ipa_argagg_value_list::get_elt (int index, unsigned unit_offset) const +{ + ipa_argagg_value key; + key.index = index; + key.unit_offset = unit_offset; + const ipa_argagg_value *res + = std::lower_bound (m_elts.begin (), m_elts.end (), key, + [] (const ipa_argagg_value &elt, + const ipa_argagg_value &val) + { + if (elt.index < val.index) + return true; + if (elt.index > val.index) + return false; + if (elt.unit_offset < val.unit_offset) + return true; + return false; + }); + + if (res == m_elts.end () + || res->index != index + || res->unit_offset != unit_offset) + res = nullptr; + + /* TODO: perhaps remove after some extensive testing? */ + if (!flag_checking) + return res; + + const ipa_argagg_value *slow_res = NULL; + int prev_index = -1; + unsigned prev_unit_offset = 0; + for (const ipa_argagg_value &av : m_elts) + { + gcc_assert (prev_index < 0 + || prev_index < av.index + || prev_unit_offset < av.unit_offset); + prev_index = av.index; + prev_unit_offset = av.unit_offset; + if (av.index == index + && av.unit_offset == unit_offset) + slow_res = &av; + } + gcc_assert (res == slow_res); + + return res; +} + +/* Return the first item describing a constant stored for parameter with INDEX, + regardless of offset or reference, or NULL if there is no such constant. */ + +const ipa_argagg_value * +ipa_argagg_value_list::get_elt_for_index (int index) const +{ + const ipa_argagg_value *res + = std::lower_bound (m_elts.begin (), m_elts.end (), index, + [] (const ipa_argagg_value &elt, unsigned idx) + { + return elt.index < idx; + }); + if (res == m_elts.end () + || res->index != index) + res = nullptr; + return res; +} + +/* Return the aggregate constant stored for INDEX at UNIT_OFFSET, not + performing any check of whether value is passed by reference, or NULL_TREE + if there is no such constant. */ + +tree +ipa_argagg_value_list::get_value (int index, unsigned unit_offset) const +{ + const ipa_argagg_value *av = get_elt (index, unit_offset); + return av ? av->value : NULL_TREE; +} + +/* Return the aggregate constant stored for INDEX at UNIT_OFFSET, if it is + passed by reference or not according to BY_REF, or NULL_TREE if there is + no such constant. */ + +tree +ipa_argagg_value_list::get_value (int index, unsigned unit_offset, + bool by_ref) const +{ + const ipa_argagg_value *av = get_elt (index, unit_offset); + if (av && av->by_ref == by_ref) + return av->value; + return NULL_TREE; +} + +/* Turn all values that are not present in OTHER into NULL_TREEs. Return the + number of remaining valid entries. */ + +bool +ipa_argagg_value_list::superset_of_p (const ipa_argagg_value_list &other) const +{ + unsigned j = 0; + for (unsigned i = 0; i < other.m_elts.size (); i++) + { + unsigned this_index = other.m_elts[i].index; + unsigned this_offset = other.m_elts[i].unit_offset; + + while (j < m_elts.size () + && (m_elts[j].index < this_index + || (m_elts[j].index == this_index + && m_elts[j].unit_offset < this_offset))) + j++; + + if (j >= m_elts.size () + || m_elts[j].index != this_index + || m_elts[j].unit_offset != this_offset + || m_elts[j].by_ref != other.m_elts[i].by_ref + || !m_elts[j].value + || !values_equal_for_ipcp_p (m_elts[j].value, other.m_elts[i].value)) + return false; + } + return true; +} + +/* Push into RES aggregate all stored aggregate values relating to parameter + with SRC_INDEX as those relating to of DST_INDEX while subtracting + UNIT_DELTA from the individual unit offsets. */ + +void +ipa_argagg_value_list::push_adjusted_values (unsigned src_index, + unsigned dest_index, + unsigned unit_delta, + vec<ipa_argagg_value> *res) const +{ + const ipa_argagg_value *av = get_elt_for_index (src_index); + if (!av) + return; + unsigned prev_unit_offset = 0; + bool first = true; + for (; av < m_elts.end (); ++av) + { + if (av->index > src_index) + return; + if (av->index == src_index + && (av->unit_offset >= unit_delta) + && av->value) + { + ipa_argagg_value new_av; + gcc_checking_assert (av->value); + new_av.value = av->value; + new_av.unit_offset = av->unit_offset - unit_delta; + new_av.index = dest_index; + new_av.by_ref = av->by_ref; + + gcc_assert (first + || new_av.unit_offset > prev_unit_offset); + prev_unit_offset = new_av.unit_offset; + first = false; + + res->safe_push (new_av); + } + } +} + +/* Push to RES information about single lattices describing aggregate values in + PLATS as those describing parameter DEST_INDEX and the original offset minus + UNIT_DELTA. Return true if any item has been pushed to RES. */ + +static bool +push_agg_values_from_plats (ipcp_param_lattices *plats, int dest_index, + unsigned unit_delta, + vec<ipa_argagg_value> *res) +{ + if (plats->aggs_contain_variable) + return false; + + bool pushed_sth = false; + bool first = true; + unsigned prev_unit_offset = 0; + for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next) + if (aglat->is_single_const () + && (aglat->offset / BITS_PER_UNIT - unit_delta) >= 0) + { + ipa_argagg_value iav; + iav.value = aglat->values->value; + iav.unit_offset = aglat->offset / BITS_PER_UNIT - unit_delta; + iav.index = dest_index; + iav.by_ref = plats->aggs_by_ref; + + gcc_assert (first + || iav.unit_offset > prev_unit_offset); + prev_unit_offset = iav.unit_offset; + first = false; + + pushed_sth = true; + res->safe_push (iav); + } + return pushed_sth; +} + +/* Turn all values in LIST that are not present in OTHER into NULL_TREEs. + Return the number of remaining valid entries. */ + +static unsigned +intersect_argaggs_with (vec<ipa_argagg_value> &elts, + const vec<ipa_argagg_value> &other) +{ + unsigned valid_entries = 0; + unsigned j = 0; + for (unsigned i = 0; i < elts.length (); i++) + { + if (!elts[i].value) + continue; + + unsigned this_index = elts[i].index; + unsigned this_offset = elts[i].unit_offset; + + while (j < other.length () + && (other[j].index < this_index + || (other[j].index == this_index + && other[j].unit_offset < this_offset))) + j++; + + if (j >= other.length ()) + { + elts[i].value = NULL_TREE; + continue; + } + + if (other[j].index == this_index + && other[j].unit_offset == this_offset + && other[j].by_ref == elts[i].by_ref + && other[j].value + && values_equal_for_ipcp_p (other[j].value, elts[i].value)) + valid_entries++; + else + elts[i].value = NULL_TREE; + } + return valid_entries; +} + /* Mark bot aggregate and scalar lattices as containing an unknown variable, return true is any of them has not been marked as such so far. */ @@ -1401,26 +1688,6 @@ ipacp_value_safe_for_type (tree param_type, tree value) return false; } -/* Return true iff X and Y should be considered equal values by IPA-CP. */ - -static bool -values_equal_for_ipcp_p (tree x, tree y) -{ - gcc_checking_assert (x != NULL_TREE && y != NULL_TREE); - - if (x == y) - return true; - - if (TREE_CODE (x) == ADDR_EXPR - && TREE_CODE (y) == ADDR_EXPR - && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL - && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL) - return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)), - DECL_INITIAL (TREE_OPERAND (y, 0)), 0); - else - return operand_equal_p (x, y, 0); -} - /* Return the result of a (possibly arithmetic) operation on the constant value INPUT. OPERAND is 2nd operand for binary operation. RES_TYPE is the type of the parameter to which the result is passed. Return @@ -1701,26 +1968,6 @@ ipa_value_range_from_jfunc (ipa_node_params *info, cgraph_edge *cs, return vr; } -/* See if NODE is a clone with a known aggregate value at a given OFFSET of a - parameter with the given INDEX. */ - -static tree -get_clone_agg_value (struct cgraph_node *node, HOST_WIDE_INT offset, - int index) -{ - struct ipa_agg_replacement_value *aggval; - - aggval = ipa_get_agg_replacements_for_node (node); - while (aggval) - { - if (aggval->offset == offset - && aggval->index == index) - return aggval->value; - aggval = aggval->next; - } - return NULL_TREE; -} - /* Determine whether ITEM, jump function for an aggregate part, evaluates to a single known constant value and if so, return it. Otherwise return NULL. NODE and INFO describes the caller node or the one it is inlined to, and @@ -1729,7 +1976,7 @@ get_clone_agg_value (struct cgraph_node *node, HOST_WIDE_INT offset, static tree ipa_agg_value_from_node (class ipa_node_params *info, struct cgraph_node *node, - struct ipa_agg_jf_item *item) + const ipa_agg_jf_item *item) { tree value = NULL_TREE; int src_idx; @@ -1749,9 +1996,13 @@ ipa_agg_value_from_node (class ipa_node_params *info, { if (item->jftype == IPA_JF_PASS_THROUGH) value = info->known_csts[src_idx]; - else - value = get_clone_agg_value (node, item->value.load_agg.offset, - src_idx); + else if (ipcp_transformation *ts = ipcp_get_transformation_summary (node)) + { + ipa_argagg_value_list avl (ts); + value = avl.get_value (src_idx, + item->value.load_agg.offset / BITS_PER_UNIT, + item->value.load_agg.by_ref); + } } else if (info->lattices) { @@ -2979,15 +3230,16 @@ propagate_constants_across_call (struct cgraph_edge *cs) } /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS - KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter - three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */ + KNOWN_CONTEXTS, and known aggregates either in AVS or KNOWN_AGGS return + the destination. The latter three can be NULL. If AGG_REPS is not NULL, + KNOWN_AGGS is ignored. */ static tree ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie, const vec<tree> &known_csts, const vec<ipa_polymorphic_call_context> &known_contexts, const vec<ipa_agg_value_set> &known_aggs, - struct ipa_agg_replacement_value *agg_reps, + const ipa_argagg_value_list *avs, bool *speculative) { int param_index = ie->indirect_info->param_index; @@ -3007,20 +3259,10 @@ ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie, if (ie->indirect_info->agg_contents) { t = NULL; - if (agg_reps && ie->indirect_info->guaranteed_unmodified) - { - while (agg_reps) - { - if (agg_reps->index == param_index - && agg_reps->offset == ie->indirect_info->offset - && agg_reps->by_ref == ie->indirect_info->by_ref) - { - t = agg_reps->value; - break; - } - agg_reps = agg_reps->next; - } - } + if (avs && ie->indirect_info->guaranteed_unmodified) + t = avs->get_value (param_index, + ie->indirect_info->offset / BITS_PER_UNIT, + ie->indirect_info->by_ref); if (!t) { const ipa_agg_value_set *agg; @@ -3063,20 +3305,10 @@ ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie, t = NULL; /* Try to work out value of virtual table pointer value in replacements. */ - if (!t && agg_reps && !ie->indirect_info->by_ref) - { - while (agg_reps) - { - if (agg_reps->index == param_index - && agg_reps->offset == ie->indirect_info->offset - && agg_reps->by_ref) - { - t = agg_reps->value; - break; - } - agg_reps = agg_reps->next; - } - } + if (!t && avs && !ie->indirect_info->by_ref) + t = avs->get_value (param_index, + ie->indirect_info->offset / BITS_PER_UNIT, + true); /* Try to work out value of virtual table pointer value in known aggregate values. */ @@ -4103,7 +4335,7 @@ ipcp_discover_new_direct_edges (struct cgraph_node *node, vec<tree> known_csts, vec<ipa_polymorphic_call_context> known_contexts, - struct ipa_agg_replacement_value *aggvals) + vec<ipa_argagg_value, va_gc> *aggvals) { struct cgraph_edge *ie, *next_ie; bool found = false; @@ -4114,8 +4346,9 @@ ipcp_discover_new_direct_edges (struct cgraph_node *node, bool speculative; next_ie = ie->next_callee; + ipa_argagg_value_list avs (aggvals); target = ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts, - vNULL, aggvals, &speculative); + vNULL, &avs, &speculative); if (target) { bool agg_contents = ie->indirect_info->agg_contents; @@ -4249,11 +4482,15 @@ cgraph_edge_brings_value_p (cgraph_edge *cs, ipcp_value_source<tree> *src, if (caller_info->ipcp_orig_node) { - tree t; + tree t = NULL_TREE; if (src->offset == -1) t = caller_info->known_csts[src->index]; - else - t = get_clone_agg_value (cs->caller, src->offset, src->index); + else if (ipcp_transformation *ts + = ipcp_get_transformation_summary (cs->caller)) + { + ipa_argagg_value_list avl (ts); + t = avl.get_value (src->index, src->offset / BITS_PER_UNIT); + } return (t != NULL_TREE && values_equal_for_ipcp_p (src->val->value, t)); } @@ -5060,13 +5297,12 @@ static struct cgraph_node * create_specialized_node (struct cgraph_node *node, vec<tree> known_csts, vec<ipa_polymorphic_call_context> known_contexts, - struct ipa_agg_replacement_value *aggvals, + vec<ipa_argagg_value, va_gc> *aggvals, vec<cgraph_edge *> &callers) { ipa_node_params *new_info, *info = ipa_node_params_sum->get (node); vec<ipa_replace_map *, va_gc> *replace_trees = NULL; vec<ipa_adjusted_param, va_gc> *new_params = NULL; - struct ipa_agg_replacement_value *av; struct cgraph_node *new_node; int i, count = ipa_get_param_count (info); clone_info *cinfo = clone_info::get (node); @@ -5194,8 +5430,8 @@ create_specialized_node (struct cgraph_node *node, new_node->expand_all_artificial_thunks (); ipa_set_node_agg_value_chain (new_node, aggvals); - for (av = aggvals; av; av = av->next) - new_node->maybe_create_reference (av->value, NULL); + for (const ipa_argagg_value &av : aggvals) + new_node->maybe_create_reference (av.value, NULL); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -5210,7 +5446,11 @@ create_specialized_node (struct cgraph_node *node, } } if (aggvals) - ipa_dump_agg_replacement_values (dump_file, aggvals); + { + fprintf (dump_file, " Aggregate replacements:"); + ipa_argagg_value_list avs (aggvals); + avs.dump (dump_file); + } } new_info = ipa_node_params_sum->get (new_node); @@ -5219,7 +5459,8 @@ create_specialized_node (struct cgraph_node *node, new_info->known_csts = known_csts; new_info->known_contexts = known_contexts; - ipcp_discover_new_direct_edges (new_node, known_csts, known_contexts, aggvals); + ipcp_discover_new_direct_edges (new_node, known_csts, known_contexts, + aggvals); return new_node; } @@ -5252,7 +5493,8 @@ self_recursive_pass_through_p (cgraph_edge *cs, ipa_jump_func *jfunc, int i, pass-through. */ static bool -self_recursive_agg_pass_through_p (cgraph_edge *cs, ipa_agg_jf_item *jfunc, +self_recursive_agg_pass_through_p (const cgraph_edge *cs, + const ipa_agg_jf_item *jfunc, int i, bool simple = true) { enum availability availability; @@ -5427,376 +5669,215 @@ find_more_contexts_for_caller_subset (cgraph_node *node, } } -/* Go through PLATS and create a vector of values consisting of values and - offsets (minus OFFSET) of lattices that contain only a single value. */ +/* Push all aggregate values coming along edge CS for parameter number INDEX to + RES. If INTERIM is non-NULL, it contains the current interim state of + collected aggregate values which can be used to compute values passed over + self-recursive edges. -static vec<ipa_agg_value> -copy_plats_to_inter (class ipcp_param_lattices *plats, HOST_WIDE_INT offset) -{ - vec<ipa_agg_value> res = vNULL; - - if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom) - return vNULL; - - for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next) - if (aglat->is_single_const ()) - { - struct ipa_agg_value ti; - ti.offset = aglat->offset - offset; - ti.value = aglat->values->value; - res.safe_push (ti); - } - return res; -} - -/* Intersect all values in INTER with single value lattices in PLATS (while - subtracting OFFSET). */ + This basically one iteration of push_agg_values_from_edge over one + parameter, which allows for simpler early returns. */ static void -intersect_with_plats (class ipcp_param_lattices *plats, - vec<ipa_agg_value> *inter, - HOST_WIDE_INT offset) +push_agg_values_for_index_from_edge (struct cgraph_edge *cs, int index, + vec<ipa_argagg_value> *res, + const ipa_argagg_value_list *interim) { - struct ipcp_agg_lattice *aglat; - struct ipa_agg_value *item; - int k; + bool agg_values_from_caller = false; + bool agg_jf_preserved = false; + unsigned unit_delta = UINT_MAX; + int src_idx = -1; + ipa_jump_func *jfunc = ipa_get_ith_jump_func (ipa_edge_args_sum->get (cs), + index); - if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom) - { - inter->release (); - return; - } - - aglat = plats->aggs; - FOR_EACH_VEC_ELT (*inter, k, item) - { - bool found = false; - if (!item->value) - continue; - while (aglat) - { - if (aglat->offset - offset > item->offset) - break; - if (aglat->offset - offset == item->offset) - { - if (aglat->is_single_const ()) - { - tree value = aglat->values->value; - - if (values_equal_for_ipcp_p (item->value, value)) - found = true; - } - break; - } - aglat = aglat->next; - } - if (!found) - item->value = NULL_TREE; - } -} - -/* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the - vector result while subtracting OFFSET from the individual value offsets. */ - -static vec<ipa_agg_value> -agg_replacements_to_vector (struct cgraph_node *node, int index, - HOST_WIDE_INT offset) -{ - struct ipa_agg_replacement_value *av; - vec<ipa_agg_value> res = vNULL; - - for (av = ipa_get_agg_replacements_for_node (node); av; av = av->next) - if (av->index == index - && (av->offset - offset) >= 0) - { - struct ipa_agg_value item; - gcc_checking_assert (av->value); - item.offset = av->offset - offset; - item.value = av->value; - res.safe_push (item); - } - - return res; -} - -/* Intersect all values in INTER with those that we have already scheduled to - be replaced in parameter number INDEX of NODE, which is an IPA-CP clone - (while subtracting OFFSET). */ - -static void -intersect_with_agg_replacements (struct cgraph_node *node, int index, - vec<ipa_agg_value> *inter, - HOST_WIDE_INT offset) -{ - struct ipa_agg_replacement_value *srcvals; - struct ipa_agg_value *item; - int i; - - srcvals = ipa_get_agg_replacements_for_node (node); - if (!srcvals) - { - inter->release (); - return; - } - - FOR_EACH_VEC_ELT (*inter, i, item) - { - struct ipa_agg_replacement_value *av; - bool found = false; - if (!item->value) - continue; - for (av = srcvals; av; av = av->next) - { - gcc_checking_assert (av->value); - if (av->index == index - && av->offset - offset == item->offset) - { - if (values_equal_for_ipcp_p (item->value, av->value)) - found = true; - break; - } - } - if (!found) - item->value = NULL_TREE; - } -} - -/* Intersect values in INTER with aggregate values that come along edge CS to - parameter number INDEX and return it. If INTER does not actually exist yet, - copy all incoming values to it. If we determine we ended up with no values - whatsoever, return a released vector. */ - -static vec<ipa_agg_value> -intersect_aggregates_with_edge (struct cgraph_edge *cs, int index, - vec<ipa_agg_value> inter) -{ - struct ipa_jump_func *jfunc; - jfunc = ipa_get_ith_jump_func (ipa_edge_args_sum->get (cs), index); if (jfunc->type == IPA_JF_PASS_THROUGH && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR) { - ipa_node_params *caller_info = ipa_node_params_sum->get (cs->caller); - int src_idx = ipa_get_jf_pass_through_formal_id (jfunc); - - if (caller_info->ipcp_orig_node) - { - struct cgraph_node *orig_node = caller_info->ipcp_orig_node; - class ipcp_param_lattices *orig_plats; - ipa_node_params *orig_info = ipa_node_params_sum->get (orig_node); - orig_plats = ipa_get_parm_lattices (orig_info, src_idx); - if (agg_pass_through_permissible_p (orig_plats, jfunc)) - { - if (!inter.exists ()) - inter = agg_replacements_to_vector (cs->caller, src_idx, 0); - else - intersect_with_agg_replacements (cs->caller, src_idx, - &inter, 0); - return inter; - } - } - else - { - class ipcp_param_lattices *src_plats; - src_plats = ipa_get_parm_lattices (caller_info, src_idx); - if (agg_pass_through_permissible_p (src_plats, jfunc)) - { - /* Currently we do not produce clobber aggregate jump - functions, adjust when we do. */ - gcc_checking_assert (!jfunc->agg.items); - if (!inter.exists ()) - inter = copy_plats_to_inter (src_plats, 0); - else - intersect_with_plats (src_plats, &inter, 0); - return inter; - } - } + agg_values_from_caller = true; + agg_jf_preserved = ipa_get_jf_pass_through_agg_preserved (jfunc); + src_idx = ipa_get_jf_pass_through_formal_id (jfunc); + unit_delta = 0; } else if (jfunc->type == IPA_JF_ANCESTOR && ipa_get_jf_ancestor_agg_preserved (jfunc)) { - ipa_node_params *caller_info = ipa_node_params_sum->get (cs->caller); - int src_idx = ipa_get_jf_ancestor_formal_id (jfunc); - class ipcp_param_lattices *src_plats; - HOST_WIDE_INT delta = ipa_get_jf_ancestor_offset (jfunc); + agg_values_from_caller = true; + agg_jf_preserved = true; + src_idx = ipa_get_jf_ancestor_formal_id (jfunc); + unit_delta = ipa_get_jf_ancestor_offset (jfunc) / BITS_PER_UNIT; + } + ipa_node_params *caller_info = ipa_node_params_sum->get (cs->caller); + if (agg_values_from_caller) + { if (caller_info->ipcp_orig_node) { - if (!inter.exists ()) - inter = agg_replacements_to_vector (cs->caller, src_idx, delta); - else - intersect_with_agg_replacements (cs->caller, src_idx, &inter, - delta); + struct cgraph_node *orig_node = caller_info->ipcp_orig_node; + ipcp_transformation *ts + = ipcp_get_transformation_summary (cs->caller); + ipa_node_params *orig_info = ipa_node_params_sum->get (orig_node); + ipcp_param_lattices *orig_plats + = ipa_get_parm_lattices (orig_info, src_idx); + if (ts + && orig_plats->aggs + && (agg_jf_preserved || !orig_plats->aggs_by_ref)) + { + ipa_argagg_value_list src (ts); + src.push_adjusted_values (src_idx, index, unit_delta, res); + return; + } } else { - src_plats = ipa_get_parm_lattices (caller_info, src_idx); - /* Currently we do not produce clobber aggregate jump - functions, adjust when we do. */ - gcc_checking_assert (!src_plats->aggs || !jfunc->agg.items); - if (!inter.exists ()) - inter = copy_plats_to_inter (src_plats, delta); - else - intersect_with_plats (src_plats, &inter, delta); + ipcp_param_lattices *src_plats + = ipa_get_parm_lattices (caller_info, src_idx); + if (src_plats->aggs + && !src_plats->aggs_bottom + && (agg_jf_preserved || !src_plats->aggs_by_ref)) + { + if (interim && self_recursive_pass_through_p (cs, jfunc, index)) + { + interim->push_adjusted_values (src_idx, index, unit_delta, + res); + return; + } + if (!src_plats->aggs_contain_variable) + { + push_agg_values_from_plats (src_plats, index, unit_delta, + res); + return; + } + } } - return inter; } - if (jfunc->agg.items) + if (!jfunc->agg.items) + return; + bool first = true; + unsigned prev_unit_offset = 0; + for (const ipa_agg_jf_item &agg_jf : *jfunc->agg.items) { - ipa_node_params *caller_info = ipa_node_params_sum->get (cs->caller); - struct ipa_agg_value *item; - int k; + tree value, srcvalue; + /* Besides simple pass-through aggregate jump function, arithmetic + aggregate jump function could also bring same aggregate value as + parameter passed-in for self-feeding recursive call. For example, - if (!inter.exists ()) - for (unsigned i = 0; i < jfunc->agg.items->length (); i++) - { - struct ipa_agg_jf_item *agg_item = &(*jfunc->agg.items)[i]; - tree value = ipa_agg_value_from_node (caller_info, cs->caller, - agg_item); - if (value) - { - struct ipa_agg_value agg_value; + fn (int *i) + { + int j = *i & 1; + fn (&j); + } - agg_value.value = value; - agg_value.offset = agg_item->offset; - inter.safe_push (agg_value); - } - } + Given that *i is 0, recursive propagation via (*i & 1) also gets 0. */ + if (interim + && self_recursive_agg_pass_through_p (cs, &agg_jf, index, false) + && (srcvalue = interim->get_value(index, + agg_jf.offset / BITS_PER_UNIT))) + value = ipa_get_jf_arith_result (agg_jf.value.pass_through.operation, + srcvalue, + agg_jf.value.pass_through.operand, + agg_jf.type); else - FOR_EACH_VEC_ELT (inter, k, item) - { - int l = 0; - bool found = false; + value = ipa_agg_value_from_node (caller_info, cs->caller, + &agg_jf); + if (value) + { + struct ipa_argagg_value iav; + iav.value = value; + iav.unit_offset = agg_jf.offset / BITS_PER_UNIT; + iav.index = index; + iav.by_ref = jfunc->agg.by_ref; - if (!item->value) - continue; + gcc_assert (first + || iav.unit_offset > prev_unit_offset); + prev_unit_offset = iav.unit_offset; + first = false; - while ((unsigned) l < jfunc->agg.items->length ()) - { - struct ipa_agg_jf_item *ti; - ti = &(*jfunc->agg.items)[l]; - if (ti->offset > item->offset) - break; - if (ti->offset == item->offset) - { - tree value; - - /* Besides simple pass-through aggregate jump function, - arithmetic aggregate jump function could also bring - same aggregate value as parameter passed-in for - self-feeding recursive call. For example, - - fn (int *i) - { - int j = *i & 1; - fn (&j); - } - - Given that *i is 0, recursive propagation via (*i & 1) - also gets 0. */ - if (self_recursive_agg_pass_through_p (cs, ti, index, - false)) - value = ipa_get_jf_arith_result ( - ti->value.pass_through.operation, - item->value, - ti->value.pass_through.operand, - ti->type); - else - value = ipa_agg_value_from_node (caller_info, - cs->caller, ti); - - if (value && values_equal_for_ipcp_p (item->value, value)) - found = true; - break; - } - l++; - } - if (!found) - item->value = NULL; - } + res->safe_push (iav); + } } - else - { - inter.release (); - return vNULL; - } - return inter; + return; } -/* Look at edges in CALLERS and collect all known aggregate values that arrive - from all of them. */ +/* Push all aggregate values coming along edge CS to RES. DEST_INFO is the + description of ultimate callee of CS or the one it was cloned from (the + summary where lattices are). If INTERIM is non-NULL, it contains the + current interim state of collected aggregate values which can be used to + compute values passed over self-recursive edges and to skip values which + clearly will not be part of intersection with INTERIM. */ -static struct ipa_agg_replacement_value * +static void +push_agg_values_from_edge (struct cgraph_edge *cs, + ipa_node_params *dest_info, + vec<ipa_argagg_value> *res, + const ipa_argagg_value_list *interim) +{ + ipa_edge_args *args = ipa_edge_args_sum->get (cs); + if (!args) + return; + + int count = MIN (ipa_get_param_count (dest_info), + ipa_get_cs_argument_count (args)); + + unsigned interim_index = 0; + for (int index = 0; index < count; index++) + { + if (interim) + { + while (interim_index < interim->m_elts.size () + && interim->m_elts[interim_index].value + && interim->m_elts[interim_index].index < index) + interim_index++; + if (interim_index >= interim->m_elts.size () + || interim->m_elts[interim_index].index > index) + continue; + } + + ipcp_param_lattices *plats = ipa_get_parm_lattices (dest_info, index); + if (plats->aggs_bottom) + continue; + push_agg_values_for_index_from_edge (cs, index, res, interim); + } +} + + +/* Look at edges in CALLERS and collect all known aggregate values that arrive + from all of them. Return nullptr if there are none. */ + +static struct vec<ipa_argagg_value, va_gc> * find_aggregate_values_for_callers_subset (struct cgraph_node *node, const vec<cgraph_edge *> &callers) { ipa_node_params *dest_info = ipa_node_params_sum->get (node); - struct ipa_agg_replacement_value *res; - struct ipa_agg_replacement_value **tail = &res; - struct cgraph_edge *cs; - int i, j, count = ipa_get_param_count (dest_info); + if (dest_info->ipcp_orig_node) + dest_info = ipa_node_params_sum->get (dest_info->ipcp_orig_node); - FOR_EACH_VEC_ELT (callers, j, cs) + /* gather_edges_for_value puts a non-recursive call into the first element of + callers if it can. */ + auto_vec<ipa_argagg_value, 32> interim; + push_agg_values_from_edge (callers[0], dest_info, &interim, NULL); + + unsigned valid_entries = interim.length (); + if (!valid_entries) + return nullptr; + + unsigned caller_count = callers.length(); + for (unsigned i = 1; i < caller_count; i++) { - ipa_edge_args *args = ipa_edge_args_sum->get (cs); - if (!args) - { - count = 0; - break; - } - int c = ipa_get_cs_argument_count (args); - if (c < count) - count = c; + auto_vec<ipa_argagg_value, 32> last; + ipa_argagg_value_list avs (&interim); + push_agg_values_from_edge (callers[i], dest_info, &last, &avs); + + valid_entries = intersect_argaggs_with (interim, last); + if (!valid_entries) + return nullptr; } - for (i = 0; i < count; i++) - { - struct cgraph_edge *cs; - vec<ipa_agg_value> inter = vNULL; - struct ipa_agg_value *item; - class ipcp_param_lattices *plats = ipa_get_parm_lattices (dest_info, i); - int j; - - /* Among other things, the following check should deal with all by_ref - mismatches. */ - if (plats->aggs_bottom) - continue; - - FOR_EACH_VEC_ELT (callers, j, cs) - { - struct ipa_jump_func *jfunc - = ipa_get_ith_jump_func (ipa_edge_args_sum->get (cs), i); - if (self_recursive_pass_through_p (cs, jfunc, i) - && (!plats->aggs_by_ref - || ipa_get_jf_pass_through_agg_preserved (jfunc))) - continue; - inter = intersect_aggregates_with_edge (cs, i, inter); - - if (!inter.exists ()) - goto next_param; - } - - FOR_EACH_VEC_ELT (inter, j, item) - { - struct ipa_agg_replacement_value *v; - - if (!item->value) - continue; - - v = ggc_alloc<ipa_agg_replacement_value> (); - v->index = i; - v->offset = item->offset; - v->value = item->value; - v->by_ref = plats->aggs_by_ref; - *tail = v; - tail = &v->next; - } - - next_param: - if (inter.exists ()) - inter.release (); - } - *tail = NULL; + vec<ipa_argagg_value, va_gc> *res = NULL; + vec_safe_reserve_exact (res, valid_entries); + for (const ipa_argagg_value &av : interim) + if (av.value) + res->quick_push(av); + gcc_checking_assert (res->length () == valid_entries); return res; } @@ -5837,72 +5918,23 @@ cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge *cs, /* Determine whether CS also brings all aggregate values that NODE is specialized for. */ + static bool cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge *cs, struct cgraph_node *node) { - struct ipa_agg_replacement_value *aggval; - int i, ec, count; - - aggval = ipa_get_agg_replacements_for_node (node); - if (!aggval) + ipcp_transformation *ts = ipcp_get_transformation_summary (node); + if (!ts || vec_safe_is_empty (ts->m_agg_values)) return true; - ipa_node_params *clone_node_info = ipa_node_params_sum->get (node); - count = ipa_get_param_count (clone_node_info); - ec = ipa_get_cs_argument_count (ipa_edge_args_sum->get (cs)); - if (ec < count) - for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next) - if (aggval->index >= ec) - return false; - - ipa_node_params *orig_node_info - = ipa_node_params_sum->get (clone_node_info->ipcp_orig_node); - - for (i = 0; i < count; i++) - { - class ipcp_param_lattices *plats; - bool interesting = false; - for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next) - if (aggval->index == i) - { - interesting = true; - break; - } - if (!interesting) - continue; - - plats = ipa_get_parm_lattices (orig_node_info, aggval->index); - if (plats->aggs_bottom) - return false; - - vec<ipa_agg_value> values = intersect_aggregates_with_edge (cs, i, vNULL); - if (!values.exists ()) - return false; - - for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next) - if (aggval->index == i) - { - struct ipa_agg_value *item; - int j; - bool found = false; - FOR_EACH_VEC_ELT (values, j, item) - if (item->value - && item->offset == av->offset - && values_equal_for_ipcp_p (item->value, av->value)) - { - found = true; - break; - } - if (!found) - { - values.release (); - return false; - } - } - values.release (); - } - return true; + const ipa_argagg_value_list existing (ts->m_agg_values); + auto_vec<ipa_argagg_value, 32> edge_values; + ipa_node_params *dest_info = ipa_node_params_sum->get (node); + gcc_checking_assert (dest_info->ipcp_orig_node); + dest_info = ipa_node_params_sum->get (dest_info->ipcp_orig_node); + push_agg_values_from_edge (cs, dest_info, &edge_values, &existing); + const ipa_argagg_value_list avl (&edge_values); + return avl.superset_of_p (existing); } /* Given an original NODE and a VAL for which we have already created a @@ -6006,28 +6038,22 @@ copy_known_vectors_add_val (ipa_auto_call_arg_values *avals, AGGVALS list. */ DEBUG_FUNCTION bool -ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *aggvals, +ipcp_val_agg_replacement_ok_p (vec<ipa_argagg_value, va_gc> *aggvals, int index, HOST_WIDE_INT offset, tree value) { if (offset == -1) return true; - while (aggvals) - { - if (aggvals->index == index - && aggvals->offset == offset - && values_equal_for_ipcp_p (aggvals->value, value)) - return true; - aggvals = aggvals->next; - } - return false; + const ipa_argagg_value_list avl (aggvals); + tree v = avl.get_value (index, offset / BITS_PER_UNIT); + return v && values_equal_for_ipcp_p (v, value); } /* Return true if offset is minus one because source of a polymorphic context cannot be an aggregate value. */ DEBUG_FUNCTION bool -ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *, +ipcp_val_agg_replacement_ok_p (vec<ipa_argagg_value, va_gc> *, int , HOST_WIDE_INT offset, ipa_polymorphic_call_context) { @@ -6047,7 +6073,6 @@ decide_about_value (struct cgraph_node *node, int index, HOST_WIDE_INT offset, ipcp_value<valtype> *val, ipa_auto_call_arg_values *avals, vec<cgraph_node *> *self_gen_clones) { - struct ipa_agg_replacement_value *aggvals; int caller_count; sreal freq_sum; profile_count count_sum, rec_count_sum; @@ -6126,7 +6151,8 @@ decide_about_value (struct cgraph_node *node, int index, HOST_WIDE_INT offset, } find_more_scalar_values_for_callers_subset (node, known_csts, callers); find_more_contexts_for_caller_subset (node, &known_contexts, callers); - aggvals = find_aggregate_values_for_callers_subset (node, callers); + vec<ipa_argagg_value, va_gc> *aggvals + = find_aggregate_values_for_callers_subset (node, callers); gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals, index, offset, val->value)); val->spec_node = create_specialized_node (node, known_csts, known_contexts, @@ -6277,7 +6303,7 @@ decide_whether_version_node (struct cgraph_node *node) = copy_useful_known_contexts (avals.m_known_contexts); find_more_scalar_values_for_callers_subset (node, known_csts, callers); find_more_contexts_for_caller_subset (node, &known_contexts, callers); - ipa_agg_replacement_value *aggvals + vec<ipa_argagg_value, va_gc> *aggvals = find_aggregate_values_for_callers_subset (node, callers); if (!known_contexts_useful_p (known_contexts)) diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc index ca5b9f31570..6196d7e6bdb 100644 --- a/gcc/ipa-prop.cc +++ b/gcc/ipa-prop.cc @@ -3057,13 +3057,11 @@ ipa_analyze_node (struct cgraph_node *node) return; info->analysis_done = 1; - if (ipa_func_spec_opts_forbid_analysis_p (node)) + if (ipa_func_spec_opts_forbid_analysis_p (node) + || (count_formal_params (node->decl) + >= (1 << IPA_PROP_ARG_INDEX_LIMIT_BITS))) { - for (int i = 0; i < ipa_get_param_count (info); i++) - { - ipa_set_param_used (info, i, true); - ipa_set_controlled_uses (info, i, IPA_UNDESCRIBED_USE); - } + gcc_assert (!ipa_get_param_count (info)); return; } @@ -4383,11 +4381,11 @@ ipcp_free_transformation_sum (void) void ipa_set_node_agg_value_chain (struct cgraph_node *node, - struct ipa_agg_replacement_value *aggvals) + vec<ipa_argagg_value, va_gc> *aggs) { ipcp_transformation_initialize (); ipcp_transformation *s = ipcp_transformation_sum->get_create (node); - s->agg_values = aggvals; + s->m_agg_values = aggs; } /* Hook that is called by cgraph.cc when an edge is removed. Adjust reference @@ -4532,12 +4530,10 @@ ipa_add_new_function (cgraph_node *node, void *data ATTRIBUTE_UNUSED) /* Hook that is called by summary when a node is duplicated. */ void -ipa_node_params_t::duplicate(cgraph_node *src, cgraph_node *dst, +ipa_node_params_t::duplicate(cgraph_node *, cgraph_node *, ipa_node_params *old_info, ipa_node_params *new_info) { - ipa_agg_replacement_value *old_av, *new_av; - new_info->descriptors = vec_safe_copy (old_info->descriptors); new_info->lattices = NULL; new_info->ipcp_orig_node = old_info->ipcp_orig_node; @@ -4547,23 +4543,6 @@ ipa_node_params_t::duplicate(cgraph_node *src, cgraph_node *dst, new_info->analysis_done = old_info->analysis_done; new_info->node_enqueued = old_info->node_enqueued; new_info->versionable = old_info->versionable; - - old_av = ipa_get_agg_replacements_for_node (src); - if (old_av) - { - new_av = NULL; - while (old_av) - { - struct ipa_agg_replacement_value *v; - - v = ggc_alloc<ipa_agg_replacement_value> (); - memcpy (v, old_av, sizeof (*v)); - v->next = new_av; - new_av = v; - old_av = old_av->next; - } - ipa_set_node_agg_value_chain (dst, new_av); - } } /* Duplication of ipcp transformation summaries. */ @@ -4576,17 +4555,9 @@ ipcp_transformation_t::duplicate(cgraph_node *, cgraph_node *dst, /* Avoid redundant work of duplicating vectors we will never use. */ if (dst->inlined_to) return; + dst_trans->m_agg_values = vec_safe_copy (src_trans->m_agg_values); dst_trans->bits = vec_safe_copy (src_trans->bits); dst_trans->m_vr = vec_safe_copy (src_trans->m_vr); - ipa_agg_replacement_value *agg = src_trans->agg_values, - **aggptr = &dst_trans->agg_values; - while (agg) - { - *aggptr = ggc_alloc<ipa_agg_replacement_value> (); - **aggptr = *agg; - agg = agg->next; - aggptr = &(*aggptr)->next; - } } /* Register our cgraph hooks if they are not already there. */ @@ -4703,23 +4674,6 @@ ipa_print_all_params (FILE * f) ipa_print_node_params (f, node); } -/* Dump the AV linked list. */ - -void -ipa_dump_agg_replacement_values (FILE *f, struct ipa_agg_replacement_value *av) -{ - bool comma = false; - fprintf (f, " Aggregate replacements:"); - for (; av; av = av->next) - { - fprintf (f, "%s %i[" HOST_WIDE_INT_PRINT_DEC "]=", comma ? "," : "", - av->index, av->offset); - print_generic_expr (f, av->value); - comma = true; - } - fprintf (f, "\n"); -} - /* Stream out jump function JUMP_FUNC to OB. */ static void @@ -5356,31 +5310,31 @@ write_ipcp_transformation_info (output_block *ob, cgraph_node *node) int node_ref; unsigned int count = 0; lto_symtab_encoder_t encoder; - struct ipa_agg_replacement_value *aggvals, *av; - aggvals = ipa_get_agg_replacements_for_node (node); encoder = ob->decl_state->symtab_node_encoder; node_ref = lto_symtab_encoder_encode (encoder, node); streamer_write_uhwi (ob, node_ref); - for (av = aggvals; av; av = av->next) - count++; - streamer_write_uhwi (ob, count); - - for (av = aggvals; av; av = av->next) - { - struct bitpack_d bp; - - streamer_write_uhwi (ob, av->offset); - streamer_write_uhwi (ob, av->index); - stream_write_tree (ob, av->value, true); - - bp = bitpack_create (ob->main_stream); - bp_pack_value (&bp, av->by_ref, 1); - streamer_write_bitpack (&bp); - } - ipcp_transformation *ts = ipcp_get_transformation_summary (node); + if (ts && !vec_safe_is_empty (ts->m_agg_values)) + { + streamer_write_uhwi (ob, ts->m_agg_values->length ()); + for (const ipa_argagg_value &av : ts->m_agg_values) + { + struct bitpack_d bp; + + stream_write_tree (ob, av.value, true); + streamer_write_uhwi (ob, av.unit_offset); + streamer_write_uhwi (ob, av.index); + + bp = bitpack_create (ob->main_stream); + bp_pack_value (&bp, av.by_ref, 1); + streamer_write_bitpack (&bp); + } + } + else + streamer_write_uhwi (ob, 0); + if (ts && vec_safe_length (ts->m_vr) > 0) { count = ts->m_vr->length (); @@ -5432,26 +5386,27 @@ static void read_ipcp_transformation_info (lto_input_block *ib, cgraph_node *node, data_in *data_in) { - struct ipa_agg_replacement_value *aggvals = NULL; unsigned int count, i; count = streamer_read_uhwi (ib); - for (i = 0; i <count; i++) + if (count > 0) { - struct ipa_agg_replacement_value *av; - struct bitpack_d bp; + ipcp_transformation_initialize (); + ipcp_transformation *ts = ipcp_transformation_sum->get_create (node); + vec_safe_grow_cleared (ts->m_agg_values, count, true); + for (i = 0; i <count; i++) + { + ipa_argagg_value *av = &(*ts->m_agg_values)[i];; - av = ggc_alloc<ipa_agg_replacement_value> (); - av->offset = streamer_read_uhwi (ib); - av->index = streamer_read_uhwi (ib); - av->value = stream_read_tree (ib, data_in); - bp = streamer_read_bitpack (ib); - av->by_ref = bp_unpack_value (&bp, 1); - av->next = aggvals; - aggvals = av; + av->value = stream_read_tree (ib, data_in); + av->unit_offset = streamer_read_uhwi (ib); + av->index = streamer_read_uhwi (ib); + + bitpack_d bp = streamer_read_bitpack (ib); + av->by_ref = bp_unpack_value (&bp, 1); + } } - ipa_set_node_agg_value_chain (node, aggvals); - + count = streamer_read_uhwi (ib); if (count > 0) { @@ -5595,56 +5550,75 @@ ipcp_read_transformation_summaries (void) } } -/* Adjust the aggregate replacements in AGGVAL to reflect parameters skipped in +/* Adjust the aggregate replacements in TS to reflect parameters skipped in NODE but also if any parameter was IPA-SRAed into a scalar go ahead with substitution of the default_definitions of that new param with the appropriate constant. - Return two bools. the first it true if at least one item in AGGVAL still - exists and function body walk should go ahead. The second is true if any - values were already substituted for scalarized parameters and update_cfg - shuld be run after replace_uses_by. */ + If after adjustments there are no aggregate replacements left, the + m_agg_values will be set to NULL. In other cases, it may be shrunk. -static std::pair<bool, bool> + Return true if any values were already substituted for scalarized parameters + and update_cfg shuld be run after replace_uses_by. */ + +static bool adjust_agg_replacement_values (cgraph_node *node, - ipa_agg_replacement_value *aggval, + ipcp_transformation *ts, const vec<ipa_param_descriptor, va_gc> &descriptors) { - struct ipa_agg_replacement_value *v; clone_info *cinfo = clone_info::get (node); if (!cinfo || !cinfo->param_adjustments) - return std::pair<bool, bool> (true, false); + return false; - bool anything_left = false; + bool removed_item = false; bool done_replacement = false; - for (v = aggval; v; v = v->next) + unsigned dst_index = 0; + unsigned count = ts->m_agg_values->length (); + for (unsigned i = 0; i < count; i++) { + ipa_argagg_value *v = &(*ts->m_agg_values)[i]; gcc_checking_assert (v->index >= 0); - unsigned unit_offset = v->offset / BITS_PER_UNIT; tree cst_type = TREE_TYPE (v->value); int split_idx; int new_idx = cinfo->param_adjustments->get_updated_index_or_split (v->index, - unit_offset, + v->unit_offset, cst_type, &split_idx); - v->index = new_idx; if (new_idx >= 0) - anything_left = true; - else if (split_idx >= 0) { - tree parm = ipa_get_param (descriptors, split_idx); - tree ddef = ssa_default_def (cfun, parm); - if (ddef) + v->index = new_idx; + if (removed_item) + (*ts->m_agg_values)[dst_index] = *v; + dst_index++; + } + else + { + removed_item = true; + if (split_idx >= 0) { - replace_uses_by (ddef, v->value); - done_replacement = true; + tree parm = ipa_get_param (descriptors, split_idx); + tree ddef = ssa_default_def (cfun, parm); + if (ddef) + { + replace_uses_by (ddef, v->value); + done_replacement = true; + } } } } - return std::pair<bool, bool> (anything_left, done_replacement); + + if (dst_index == 0) + { + ggc_free (ts->m_agg_values); + ts->m_agg_values = NULL; + } + else if (removed_item) + ts->m_agg_values->truncate (dst_index); + + return done_replacement; } /* Dominator walker driving the ipcp modification phase. */ @@ -5654,10 +5628,9 @@ class ipcp_modif_dom_walker : public dom_walker public: ipcp_modif_dom_walker (struct ipa_func_body_info *fbi, vec<ipa_param_descriptor, va_gc> *descs, - struct ipa_agg_replacement_value *av, - bool *sc) + ipcp_transformation *ts, bool *sc) : dom_walker (CDI_DOMINATORS), m_fbi (fbi), m_descriptors (descs), - m_aggval (av), m_something_changed (sc) {} + m_ts (ts), m_something_changed (sc) {} edge before_dom_children (basic_block) final override; bool cleanup_eh () @@ -5666,7 +5639,7 @@ public: private: struct ipa_func_body_info *m_fbi; vec<ipa_param_descriptor, va_gc> *m_descriptors; - struct ipa_agg_replacement_value *m_aggval; + ipcp_transformation *m_ts; bool *m_something_changed; auto_bitmap m_need_eh_cleanup; }; @@ -5677,10 +5650,9 @@ ipcp_modif_dom_walker::before_dom_children (basic_block bb) gimple_stmt_iterator gsi; for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { - struct ipa_agg_replacement_value *v; gimple *stmt = gsi_stmt (gsi); tree rhs, val, t; - HOST_WIDE_INT offset; + HOST_WIDE_INT bit_offset; poly_int64 size; int index; bool by_ref, vce; @@ -5708,32 +5680,30 @@ ipcp_modif_dom_walker::before_dom_children (basic_block bb) continue; if (!ipa_load_from_parm_agg (m_fbi, m_descriptors, stmt, rhs, &index, - &offset, &size, &by_ref)) + &bit_offset, &size, &by_ref)) continue; - for (v = m_aggval; v; v = v->next) - if (v->index == index - && v->offset == offset) - break; + unsigned unit_offset = bit_offset / BITS_PER_UNIT; + ipa_argagg_value_list avl (m_ts); + tree v = avl.get_value (index, unit_offset, by_ref); + if (!v - || v->by_ref != by_ref - || maybe_ne (tree_to_poly_int64 (TYPE_SIZE (TREE_TYPE (v->value))), - size)) + || maybe_ne (tree_to_poly_int64 (TYPE_SIZE (TREE_TYPE (v))), size)) continue; - gcc_checking_assert (is_gimple_ip_invariant (v->value)); - if (!useless_type_conversion_p (TREE_TYPE (rhs), TREE_TYPE (v->value))) + gcc_checking_assert (is_gimple_ip_invariant (v)); + if (!useless_type_conversion_p (TREE_TYPE (rhs), TREE_TYPE (v))) { - if (fold_convertible_p (TREE_TYPE (rhs), v->value)) - val = fold_build1 (NOP_EXPR, TREE_TYPE (rhs), v->value); + if (fold_convertible_p (TREE_TYPE (rhs), v)) + val = fold_build1 (NOP_EXPR, TREE_TYPE (rhs), v); else if (TYPE_SIZE (TREE_TYPE (rhs)) - == TYPE_SIZE (TREE_TYPE (v->value))) - val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (rhs), v->value); + == TYPE_SIZE (TREE_TYPE (v))) + val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (rhs), v); else { if (dump_file) { fprintf (dump_file, " const "); - print_generic_expr (dump_file, v->value); + print_generic_expr (dump_file, v); fprintf (dump_file, " can't be converted to type of "); print_generic_expr (dump_file, rhs); fprintf (dump_file, "\n"); @@ -5742,7 +5712,7 @@ ipcp_modif_dom_walker::before_dom_children (basic_block bb) } } else - val = v->value; + val = v; if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -6019,7 +5989,6 @@ ipcp_transform_function (struct cgraph_node *node) { vec<ipa_param_descriptor, va_gc> *descriptors = NULL; struct ipa_func_body_info fbi; - struct ipa_agg_replacement_value *aggval; int param_count; gcc_checking_assert (cfun); @@ -6031,18 +6000,17 @@ ipcp_transform_function (struct cgraph_node *node) ipcp_update_bits (node); ipcp_update_vr (node); - aggval = ipa_get_agg_replacements_for_node (node); - if (!aggval) + ipcp_transformation *ts = ipcp_get_transformation_summary (node); + if (!ts || vec_safe_is_empty (ts->m_agg_values)) return 0; param_count = count_formal_params (node->decl); if (param_count == 0) return 0; vec_safe_grow_cleared (descriptors, param_count, true); ipa_populate_param_decls (node, *descriptors); - std::pair<bool, bool> rr - = adjust_agg_replacement_values (node, aggval, *descriptors); - bool cfg_changed = rr.second; - if (!rr.first) + + bool cfg_changed = adjust_agg_replacement_values (node, ts, *descriptors); + if (vec_safe_is_empty (ts->m_agg_values)) { vec_free (descriptors); if (dump_file) @@ -6053,7 +6021,11 @@ ipcp_transform_function (struct cgraph_node *node) return 0; } if (dump_file) - ipa_dump_agg_replacement_values (dump_file, aggval); + { + fprintf (dump_file, " Aggregate replacements:"); + ipa_argagg_value_list avs (ts); + avs.dump (dump_file); + } fbi.node = node; fbi.info = NULL; @@ -6064,7 +6036,7 @@ ipcp_transform_function (struct cgraph_node *node) bool modified_mem_access = false; calculate_dominance_info (CDI_DOMINATORS); - ipcp_modif_dom_walker walker (&fbi, descriptors, aggval, &modified_mem_access); + ipcp_modif_dom_walker walker (&fbi, descriptors, ts, &modified_mem_access); walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); free_dominance_info (CDI_DOMINATORS); cfg_changed |= walker.cleanup_eh (); @@ -6076,7 +6048,7 @@ ipcp_transform_function (struct cgraph_node *node) fbi.bb_infos.release (); ipcp_transformation *s = ipcp_transformation_sum->get (node); - s->agg_values = NULL; + s->m_agg_values = NULL; s->bits = NULL; s->m_vr = NULL; diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h index 8811e0ea987..b04c1d1e8f9 100644 --- a/gcc/ipa-prop.h +++ b/gcc/ipa-prop.h @@ -25,6 +25,11 @@ along with GCC; see the file COPYING3. If not see #define IPA_UNDESCRIBED_USE -1 +/* Index identifying an actualargument or a formal parameter may have only this + many bits. */ + +#define IPA_PROP_ARG_INDEX_LIMIT_BITS 16 + /* ipa-prop.cc stuff (ipa-cp, indirect inlining): */ /* A jump function for a callsite represents the values passed as actual @@ -184,6 +189,92 @@ struct GTY(()) ipa_agg_jump_function bool by_ref; }; +class ipcp_transformation; + +/* Element of a vector describing aggregate values for a number of arguments in + a particular context, be it a call or the aggregate constants that a node is + specialized for. */ + +struct GTY(()) ipa_argagg_value +{ + /* The constant value. In the contexts where the list of known values is + being pruned, NULL means a variable value. */ + tree value; + /* Unit offset within the aggregate. */ + unsigned unit_offset; + /* Index of the parameter, as it was in the original function (i.e. needs + remapping after parameter modification is carried out as part of clone + materialization). */ + unsigned index : IPA_PROP_ARG_INDEX_LIMIT_BITS; + /* Whether the value was passed by reference. */ + unsigned by_ref : 1; +}; + +/* A view into a sorted list of aggregate values in a particular context, be it + a call or the aggregate constants that a node is specialized for. The + actual data is stored in the vector this has been constructed from. */ + +class ipa_argagg_value_list +{ +public: + ipa_argagg_value_list () = delete; + ipa_argagg_value_list (const vec<ipa_argagg_value, va_gc> *values) + : m_elts (values) + {} + ipa_argagg_value_list (const vec<ipa_argagg_value> *values) + : m_elts (*values) + {} + ipa_argagg_value_list (const ipcp_transformation *tinfo); + + /* Return the aggregate constant stored for INDEX at UNIT_OFFSET, if it is + passed by reference or not according to BY_REF, or NULL_TREE + otherwise. */ + + tree get_value (int index, unsigned unit_offset, bool by_ref) const; + + /* Return the aggregate constant stored for INDEX at UNIT_OFFSET, not + performing any check of whether value is passed by reference. Return + NULL_TREE if there is no such constant. */ + + tree get_value (int index, unsigned unit_offset) const; + + /* Return the item describing a constant stored for INDEX at UNIT_OFFSET or + NULL if there is no such constant. */ + + const ipa_argagg_value *get_elt (int index, unsigned unit_offset) const; + + /* Return the first item describing a constant stored for parameter with + INDEX, regardless of offset or reference, or NULL if there is no such + constant. */ + + const ipa_argagg_value *get_elt_for_index (int index) const; + + /* Return true if all elements present in OTHER are also present in this + class. */ + + bool superset_of_p (const ipa_argagg_value_list &other) const; + + /* Push into RES aggregate all stored aggregate values relating to parameter + with SRC_INDEX as those relating to of DST_INDEX while subtracting + UNIT_DELTA from the individual unit offsets. */ + + void push_adjusted_values (unsigned src_index, unsigned dest_index, + unsigned unit_delta, + vec<ipa_argagg_value> *res) const; + + /* Dump aggregate constants to FILE. */ + + void dump (FILE *f); + + /* Dump aggregate constants to stderr. */ + + void debug (); + + /* Array slice pointing to the actual storage. */ + + array_slice<const ipa_argagg_value> m_elts; +}; + /* An element in an aggregate part describing a known value at a given offset. All unlisted positions are assumed to be unknown and all listed values must fulfill is_gimple_ip_invariant. */ @@ -882,28 +973,12 @@ ipa_is_param_used_by_polymorphic_call (class ipa_node_params *info, int i) return (*info->descriptors)[i].used_by_polymorphic_call; } -/* Information about replacements done in aggregates for a given node (each - node has its linked list). */ -struct GTY(()) ipa_agg_replacement_value -{ - /* Next item in the linked list. */ - struct ipa_agg_replacement_value *next; - /* Offset within the aggregate. */ - HOST_WIDE_INT offset; - /* The constant value. */ - tree value; - /* The parameter index. */ - int index; - /* Whether the value was passed by reference. */ - bool by_ref; -}; - /* Structure holding information for the transformation phase of IPA-CP. */ struct GTY(()) ipcp_transformation { - /* Linked list of known aggregate values. */ - ipa_agg_replacement_value *agg_values; + /* Known aggregate values. */ + vec<ipa_argagg_value, va_gc> *m_agg_values; /* Known bits information. */ vec<ipa_bits *, va_gc> *bits; /* Value range information. */ @@ -911,26 +986,25 @@ struct GTY(()) ipcp_transformation /* Default constructor. */ ipcp_transformation () - : agg_values (NULL), bits (NULL), m_vr (NULL) + : m_agg_values (NULL), bits (NULL), m_vr (NULL) { } /* Default destructor. */ ~ipcp_transformation () { - ipa_agg_replacement_value *agg = agg_values; - while (agg) - { - ipa_agg_replacement_value *next = agg->next; - ggc_free (agg); - agg = next; - } + vec_free (m_agg_values); vec_free (bits); vec_free (m_vr); } }; +inline +ipa_argagg_value_list::ipa_argagg_value_list (const ipcp_transformation *tinfo) + : m_elts (tinfo->m_agg_values) +{} + void ipa_set_node_agg_value_chain (struct cgraph_node *node, - struct ipa_agg_replacement_value *aggvals); + vec<ipa_argagg_value, va_gc> *aggs); void ipcp_transformation_initialize (void); void ipcp_free_transformation_sum (void); @@ -1107,15 +1181,6 @@ ipcp_get_transformation_summary (cgraph_node *node) return ipcp_transformation_sum->get (node); } -/* Return the aggregate replacements for NODE, if there are any. */ - -static inline struct ipa_agg_replacement_value * -ipa_get_agg_replacements_for_node (cgraph_node *node) -{ - ipcp_transformation *ts = ipcp_get_transformation_summary (node); - return ts ? ts->agg_values : NULL; -} - /* Function formal parameters related computations. */ void ipa_initialize_node_params (struct cgraph_node *node); bool ipa_propagate_indirect_call_infos (struct cgraph_edge *cs, @@ -1171,8 +1236,6 @@ struct ipcp_agg_lattice; extern object_allocator<ipcp_agg_lattice> ipcp_agg_lattice_pool; -void ipa_dump_agg_replacement_values (FILE *f, - struct ipa_agg_replacement_value *av); void ipa_prop_write_jump_functions (void); void ipa_prop_read_jump_functions (void); void ipcp_write_transformation_summaries (void); diff --git a/gcc/testsuite/gcc.dg/ipa/ipcp-agg-11.c b/gcc/testsuite/gcc.dg/ipa/ipcp-agg-11.c index 3c496eeef39..48bf77222b2 100644 --- a/gcc/testsuite/gcc.dg/ipa/ipcp-agg-11.c +++ b/gcc/testsuite/gcc.dg/ipa/ipcp-agg-11.c @@ -73,5 +73,5 @@ entry () /* { dg-final { scan-ipa-dump "offset: 0, type: int, CONST: 101" "cp" } } */ /* { dg-final { scan-ipa-dump "offset: 32, type: int, PASS THROUGH: 0, op trunc_mod_expr 7" "cp" } } */ /* { dg-final { scan-ipa-dump "offset: 64, type: int, LOAD AGG: 1 \\\[offset: 0, by reference], op plus_expr 6" "cp" } } */ -/* { dg-final { scan-ipa-dump "Aggregate replacements: 0\\\[0]=1, 0\\\[32]=105, 0\\\[64]=-18" "cp" } } */ -/* { dg-final { scan-ipa-dump "Aggregate replacements: 0\\\[0]=101, 0\\\[32]=2, 0\\\[64]=9" "cp" } } */ +/* { dg-final { scan-ipa-dump "Aggregate replacements: 0\\\[0]=1\\(by_ref\\), 0\\\[4]=105\\(by_ref\\), 0\\\[8]=-18\\(by_ref\\)" "cp" } } */ +/* { dg-final { scan-ipa-dump "Aggregate replacements: 0\\\[0]=101, 0\\\[4]=2, 0\\\[8]=9" "cp" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/ipcp-agg-8.c b/gcc/testsuite/gcc.dg/ipa/ipcp-agg-8.c index 2d9c82f7310..8234702dd6e 100644 --- a/gcc/testsuite/gcc.dg/ipa/ipcp-agg-8.c +++ b/gcc/testsuite/gcc.dg/ipa/ipcp-agg-8.c @@ -48,5 +48,5 @@ entry (int c) foo (4, i, &s); } } -/* { dg-final { scan-ipa-dump "Aggregate replacements: 1\\\[32]=64, 1\\\[64]=32" "cp" } } */ -/* { dg-final { scan-ipa-dump "Aggregate replacements: 1\\\[32]=0" "cp" } } */ +/* { dg-final { scan-ipa-dump "Aggregate replacements: 1\\\[4]=64\\(by_ref\\), 1\\\[8]=32\\(by_ref\\)" "cp" } } */ +/* { dg-final { scan-ipa-dump "Aggregate replacements: 1\\\[4]=0\\(by_ref\\)" "cp" } } */