store-merging: Consider also overlapping stores earlier in the by bitpos sorting...

store-merging: Consider also overlapping stores earlier in the by bitpos sorting [PR97053]

As the testcases show, if we have something like:
  MEM <char[12]> [&b + 8B] = {};
  MEM[(short *) &b] = 5;
  _5 = *x_4(D);
  MEM <long long unsigned int> [&b + 2B] = _5;
  MEM[(char *)&b + 16B] = 88;
  MEM[(int *)&b + 20B] = 1;
then in sort_by_bitpos the stores are almost like in the given order,
except the first store is after the = _5; store.
We can't coalesce the = 5; store with = _5;, because the latter is MEM_REF,
while the former INTEGER_CST, and we can't coalesce the = _5 store with
the = {} store because the former is MEM_REF, the latter INTEGER_CST.
But we happily coalesce the remaining 3 stores, which is wrong, because the
= _5; store overlaps those and is in between them in the program order.
We already have code to deal with similar cases in check_no_overlap, but we
deal only with the following stores in sort_by_bitpos order, not the earlier
ones.

The following patch checks also the earlier ones.  In coalesce_immediate_stores
it computes the first one that needs to be checked (all the ones whose
bitpos + bitsize is smaller or equal to merged_store->start don't need to be
checked and don't need to be checked even for any following attempts because
of the sort_by_bitpos sorting) and the end of that (that is the first store
in the merged_store).

2020-09-16  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/97053
	* gimple-ssa-store-merging.c (check_no_overlap): Add FIRST_ORDER,
	START, FIRST_EARLIER and LAST_EARLIER arguments.  Return false if
	any stores between FIRST_EARLIER inclusive and LAST_EARLIER exclusive
	has order in between FIRST_ORDER and LAST_ORDER and overlaps the to
	be merged store.
	(imm_store_chain_info::try_coalesce_bswap): Add FIRST_EARLIER argument.
	Adjust check_no_overlap caller.
	(imm_store_chain_info::coalesce_immediate_stores): Add first_earlier
	and last_earlier variables, adjust them during iterations.  Adjust
	check_no_overlap callers, call check_no_overlap even when extending
	overlapping stores by extra INTEGER_CST stores.

	* gcc.dg/store_merging_31.c: New test.
	* gcc.dg/store_merging_32.c: New test.