ipa: Sort ipa_param_body_adjustments::m_replacements (PR 108110)

ipa: Sort ipa_param_body_adjustments::m_replacements (PR 108110)

The problem in PR 108110 is that elements describing the same base
parameter in ipa_param_body_adjustments::m_replacements are not
adjacent to each other, which is something that
ipa_param_body_adjustments::modify_call_stmt when it gathers all
replacements for a parameter.

One option would be to simply always keep looking until the end of the
vector (see bugzilla comment 15 for a one-line fix) but the correct
thing to do is to keep the elements of the vector sorted and thus make
such elements adjacent again.  This patch does that and then also
modifies the look-ups to take advantage of it.

Since the one user of ipa_param_body_adjustments that is not
tree-inline.cc, which is OpenMP declare SIMD cloning code, also
registers its own replacements and in theory pointers to elements of
the m_replacements vector can leak through public method
get_expr_replacement, I decided that in those cases it is the
responsibility of the user of the class to call the sorting method
between the replacement registrations and the first lookup.  That is
why the patch also adds a line to omp-simd-clone.cc.

gcc/ChangeLog:

2023-01-09  Martin Jambor  <mjambor@suse.cz>

	PR ipa/108110
	* ipa-param-manipulation.h (ipa_param_body_adjustments): New members
	sort_replacements, lookup_first_base_replacement and
	m_sorted_replacements_p.
	* ipa-param-manipulation.cc: Define INCLUDE_ALGORITHM.
	(ipa_param_body_adjustments::register_replacement): Set
	m_sorted_replacements_p to false.
	(compare_param_body_replacement): New function.
	(ipa_param_body_adjustments::sort_replacements): Likewise.
	(ipa_param_body_adjustments::common_initialization): Call
	sort_replacements.
	(ipa_param_body_adjustments::ipa_param_body_adjustments): Initialize
	m_sorted_replacements_p.
	(ipa_param_body_adjustments::lookup_replacement_1): Rework to use
	std::lower_bound.
	(ipa_param_body_adjustments::lookup_first_base_replacement): New
	function.
	(ipa_param_body_adjustments::modify_call_stmt): Use
	lookup_first_base_replacement.
	* omp-simd-clone.cc (ipa_simd_modify_function_body): Call
	adjustments->sort_replacements.

gcc/testsuite/ChangeLog:

2023-01-04  Martin Jambor  <mjambor@suse.cz>

	PR ipa/108110
	* g++.dg/ipa/pr108110.C: New test.