[gcc r16-5566] ira: sort allocno_hard_regs by regset

[Alexandre Oliva]

https://gcc.gnu.org/g:ee8a5c03f6d94da0c9b7f4495915647c84478af5

commit r16-5566-gee8a5c03f6d94da0c9b7f4495915647c84478af5
Author: Alexandre Oliva <oliva@adacore.com>
Date:   Mon Nov 24 20:07:20 2025 -0300

    ira: sort allocno_hard_regs by regset
    
    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.
    
    
    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.

Diff:
---
 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 0d03aed5128f..e33c8e334d39 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 fa2ea61cadf3..4ee2a65e2911 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);
 }