ipa-cp: Better representation of aggregate values we clone for

ipa-cp: Better representation of aggregate values we clone for

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.