> Am 21.11.2025 um 07:31 schrieb Alexandre Oliva <[email protected]>:
>
>
> Using hashes of data structures for tie breaking makes sorting
> dependent on type sizes, padding, and endianness, i.e., unstable
> across different hosts.
>
> ira-color.cc's allocno_hard_regs_compare does that, and it causes
> different register allocations to be chosen for the same target
> depending on the host. That's undesirable.
>
> Compare the HARD_REG_SETs directly instead, looking for the
> lowest-numbered difference register to use as the tie breaker for the
> cost compare.
>
> With a hardware implementation of ctz, this is likely faster than the
> hash used to break ties before.
>
> Regstrapped on x86_64-linux-gnu, bootstrapped with x86_64-linux-gnum32
> (64-bit stage1, 32-bit stage[23]), smoke-tested with m68k-elf (for
> FIRST_PSEUDO_REGISTER<=32). I suppose it's too late to fix this
> long-time issue in this cycle, but is it ok for the next stage1?
LGTM now, but please give Vlad the chance to comment.
Richard
>
> for gcc/ChangeLog
>
> PR rtl-optimization/122767
> * ira-color.cc (allocno_hard_regs_compare): Break ties
> using...
> * hard-reg-set.h (hard_reg_set_first_diff): ... this. New
> HARD_REG_SET API entry point.
> ---
> gcc/hard-reg-set.h | 50 ++++++++++++++++++++++++++++++++++++++++++++++++++
> gcc/ira-color.cc | 6 +++++-
> 2 files changed, 55 insertions(+), 1 deletion(-)
>
> diff --git a/gcc/hard-reg-set.h b/gcc/hard-reg-set.h
> index 0d03aed5128fe..e33c8e334d396 100644
> --- a/gcc/hard-reg-set.h
> +++ b/gcc/hard-reg-set.h
> @@ -197,6 +197,28 @@ hard_reg_set_popcount (const_hard_reg_set x)
> return popcount_hwi (x);
> }
>
> +/* Return 0 if there aren't any differences between X and Y after the first
> + SKIP registers, or 1 + the register number of the lowest-numbered
> + difference, negated if it's set in Y. The return value is suitable for
> + qsort. */
> +inline int
> +hard_reg_set_first_diff (const_hard_reg_set x, const_hard_reg_set y,
> + unsigned skip)
> +{
> + if (skip >= UHOST_BITS_PER_WIDE_INT)
> + return 0;
> + const HARD_REG_ELT_TYPE full_mask = -1;
> + HARD_REG_ELT_TYPE mask = full_mask << skip;
> + HARD_REG_ELT_TYPE dif = (x ^ y) & mask;
> + if (dif == 0)
> + return 0;
> + int bit = ctz_hwi (dif);
> + int regp1 = bit + 1;
> + if (y & (HARD_CONST (1) << bit))
> + return -regp1;
> + return regp1;
> +}
> +
> #else
>
> inline void
> @@ -269,6 +291,34 @@ hard_reg_set_popcount (const_hard_reg_set x)
> count += popcount_hwi (x.elts[i]);
> return count;
> }
> +
> +/* Return 0 if there aren't any differences between X and Y after the first
> + SKIP registers, or 1 + the register number of the lowest-numbered
> + difference, negated if it's set in Y. The return value is suitable for
> + qsort. */
> +inline int
> +hard_reg_set_first_diff (const_hard_reg_set x, const_hard_reg_set y,
> + unsigned skip)
> +{
> + const HARD_REG_ELT_TYPE full_mask = -1;
> + HARD_REG_ELT_TYPE mask = full_mask << (skip % UHOST_BITS_PER_WIDE_INT);
> + for (unsigned int i = skip / UHOST_BITS_PER_WIDE_INT;
> + i < ARRAY_SIZE (x.elts); ++i)
> + {
> + HARD_REG_ELT_TYPE dif = (x.elts[i] ^ y.elts[i]) & mask;
> + if (dif == 0)
> + {
> + mask = full_mask;
> + continue;
> + }
> + int bit = ctz_hwi (dif);
> + int regp1 = bit + 1 + i * UHOST_BITS_PER_WIDE_INT;
> + if (y.elts[i] & (HARD_CONST (1) << bit))
> + return -regp1;
> + return regp1;
> + }
> + return 0;
> +}
> #endif
>
> /* Iterator for hard register sets. */
> diff --git a/gcc/ira-color.cc b/gcc/ira-color.cc
> index fa2ea61cadf36..4ee2a65e29117 100644
> --- a/gcc/ira-color.cc
> +++ b/gcc/ira-color.cc
> @@ -310,7 +310,11 @@ allocno_hard_regs_compare (const void *v1p, const void
> *v2p)
> return 1;
> else if (hv2->cost < hv1->cost)
> return -1;
> - return SORTGT (allocno_hard_regs_hasher::hash(hv2),
> allocno_hard_regs_hasher::hash(hv1));
> +
> + /* Break ties using the HARD_REG_SETs themselves. Avoid influencing
> sorting
> + by such host features as word size and alignment, looking for the
> + lowest-numbered hard register difference. */
> + return hard_reg_set_first_diff (hv1->set, hv2->set, 0);
> }
>
>
>
>
> --
> Alexandre Oliva, happy hacker https://blog.lx.oliva.nom.br/
> Free Software Activist FSFLA co-founder GNU Toolchain Engineer
> More tolerance and less prejudice are key for inclusion and diversity.
> Excluding neuro-others for not behaving ""normal"" is *not* inclusive!
