[gcc(refs/vendors/vrull/heads/slp-improvements)] Change the representative of partitions in libiberty partition_union

[gcc(refs/vendors/vrull/heads/slp-improvements)] Change the representative of partitions in libiberty partition_union

[Philipp Tomsich]

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

commit af1f22d1dec9e0284e95636cd9d04ded04ad700b
Author: Manolis Tsamis <manolis.tsamis@vrull.eu>
Date:   Thu Feb 15 04:25:33 2024 -0800

    Change the representative of partitions in libiberty partition_union
    
    Libiberty contains a union-find implementation that is used in SSA
    name coalescing. The existing criterion for choosing the
    representative of a class is based on the size of the classes that are
    merged. This helps to iterate less elements and can make the operation
    faster but it also affects the ordering of the representatives. We
    have found that this ordering is less predictable and affected by the
    order of union operations which in turn can cause unwanted differences
    when doing SSA name coalescing. This commit changes the criterion and
    instead prefers to choose the smallest element as a representative
    which from empirical testing results in better partitioning and more
    natural ordering.
    
    Although we may iterate more elements, the worst case complexity is
    still the same. This particular implementation is O(n) union / O(1)
    find which can be improved anyway if needed.
    
    Ref #359

Diff:
---
 libiberty/partition.c | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

diff --git a/libiberty/partition.c b/libiberty/partition.c
index 007f851d2c2..2404c22dddb 100644
--- a/libiberty/partition.c
+++ b/libiberty/partition.c
@@ -86,9 +86,8 @@ partition_union (partition part, int elem1, int elem2)
   if (class_element == elements[elem2].class_element)
     return class_element;
 
-  /* Make sure ELEM1 is in the larger class of the two.  If not, swap
-     them.  This way we always scan the shorter list.  */
-  if (elements[elem1].class_count < elements[elem2].class_count) 
+  /* Make the class with the smaller index be the representative.  */
+  if (elements[elem1].class_element > elements[elem2].class_element)
     {
       int temp = elem1;
       elem1 = elem2;