[2/2] Fix unstable sort

Message ID 1515790698-6489-3-git-send-email-lists@coryfields.com
State New
Headers show
Series
  • Fix unstable sorts affecting codegen
Related show

Commit Message

Cory Fields Jan. 12, 2018, 8:58 p.m.
From: Cory Fields <cory-nospam-@coryfields.com>

2018-01-12  Cory Fields  <cory-nospam-@coryfields.com>
       * tree-ira.c (allocno_hard_regs_compare): stabilize sort
---
 gcc/ChangeLog   | 3 +++
 gcc/ira-color.c | 3 +--
 2 files changed, 4 insertions(+), 2 deletions(-)

Comments

Jeff Law Jan. 13, 2018, 7:48 p.m. | #1
On 01/12/2018 01:58 PM, lists@coryfields.com wrote:
> From: Cory Fields <cory-nospam-@coryfields.com>
> 
> 2018-01-12  Cory Fields  <cory-nospam-@coryfields.com>
>        * tree-ira.c (allocno_hard_regs_compare): stabilize sort
> ---
>  gcc/ChangeLog   | 3 +++
>  gcc/ira-color.c | 3 +--
>  2 files changed, 4 insertions(+), 2 deletions(-)
> 
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index ab96bd6..546e84c 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,4 +1,7 @@
>  2018-01-12  Cory Fields  <cory-nospam-@coryfields.com>
> +	* tree-ira.c (allocno_hard_regs_compare): stabilize sort
Note I'm not sure this is sufficient to stabilize the sort.  Given two
allocnos with the same cost and the same potential hard reg set ought to
hash to the same value.

Similarly if two sets with the same cost had a hash collision.

But it's still more stable than doing nothing.

jeff
Cory Fields Jan. 13, 2018, 9:32 p.m. | #2
On Sat, Jan 13, 2018 at 2:48 PM, Jeff Law <law@redhat.com> wrote:
> On 01/12/2018 01:58 PM, lists@coryfields.com wrote:
>> From: Cory Fields <cory-nospam-@coryfields.com>
>>
>> 2018-01-12  Cory Fields  <cory-nospam-@coryfields.com>
>>        * tree-ira.c (allocno_hard_regs_compare): stabilize sort
>> ---
>>  gcc/ChangeLog   | 3 +++
>>  gcc/ira-color.c | 3 +--
>>  2 files changed, 4 insertions(+), 2 deletions(-)
>>
>> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
>> index ab96bd6..546e84c 100644
>> --- a/gcc/ChangeLog
>> +++ b/gcc/ChangeLog
>> @@ -1,4 +1,7 @@
>>  2018-01-12  Cory Fields  <cory-nospam-@coryfields.com>
>> +     * tree-ira.c (allocno_hard_regs_compare): stabilize sort
> Note I'm not sure this is sufficient to stabilize the sort.  Given two
> allocnos with the same cost and the same potential hard reg set ought to
> hash to the same value.
>

If the set and cost are the same, then the two allocno_hard_regs are
bit-for-bit identical, so returning 0 in that case is fine. Or have I
misunderstood you?

> Similarly if two sets with the same cost had a hash collision.

A hash collision would cause breakage here, yes. I'd be happy to
change it to a full memcmp-like compare, it just wasn't obvious to me
how to do so.

>
> But it's still more stable than doing nothing.

Agreed, it's enough to fix my bootstrap issues, at least.

Side-note: I just noticed that I wrote the wrong filename in the
changelog/commit msg. I assume those entries will likely change anyway
if committed, but please let me know if I should re-send.

Cory
Jeff Law Jan. 15, 2018, 6:06 a.m. | #3
On 01/12/2018 01:58 PM, lists@coryfields.com wrote:
> From: Cory Fields <cory-nospam-@coryfields.com>
> 
> 2018-01-12  Cory Fields  <cory-nospam-@coryfields.com>
>        * tree-ira.c (allocno_hard_regs_compare): stabilize sort
Thanks.  I fixed the ChangeLog entry and installed hte patch on the trunk.

jeff
Cory Fields Jan. 15, 2018, 5:19 p.m. | #4
Thanks!

Cory

On Jan 15, 2018 1:06 AM, "Jeff Law" <law@redhat.com> wrote:

> On 01/12/2018 01:58 PM, lists@coryfields.com wrote:
> > From: Cory Fields <cory-nospam-@coryfields.com>
> >
> > 2018-01-12  Cory Fields  <cory-nospam-@coryfields.com>
> >        * tree-ira.c (allocno_hard_regs_compare): stabilize sort
> Thanks.  I fixed the ChangeLog entry and installed hte patch on the trunk.
>
> jeff
>

Patch

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index ab96bd6..546e84c 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,4 +1,7 @@ 
 2018-01-12  Cory Fields  <cory-nospam-@coryfields.com>
+	* tree-ira.c (allocno_hard_regs_compare): stabilize sort
+
+2018-01-12  Cory Fields  <cory-nospam-@coryfields.com>
 	* tree-ssa-loop-im.c (sort_bbs_in_loop_postorder_cmp): stabilize sort
 
 2018-01-12  Jakub Jelinek  <jakub@redhat.com>
diff --git a/gcc/ira-color.c b/gcc/ira-color.c
index c8b6ab4..8c02c27 100644
--- a/gcc/ira-color.c
+++ b/gcc/ira-color.c
@@ -300,8 +300,7 @@  allocno_hard_regs_compare (const void *v1p, const void *v2p)
     return 1;
   else if (hv2->cost < hv1->cost)
     return -1;
-  else
-    return 0;
+  return SORTGT(allocno_hard_regs_hasher::hash(hv2), allocno_hard_regs_hasher::hash(hv1));
 }