diff mbox

[3/5] "Fix" intransitive comparison in reload_pseudo_compare_func

Message ID 567279C9.4080707@samsung.com
State New
Headers show

Commit Message

Yury Gribov Dec. 17, 2015, 9 a.m. UTC 
This patch fixes intransitive comparison in reload_pseudo_compare_func. 
Imagine the following
situation:
1) bitmap_bit_p is unset for A and B but set for C
2) A < B (due to early ira_reg_class_max_nregs comparison)
3) B < C (due to following regno_assign_info comparison)

It may then easily happen that A > C (due to regno_assign_info 
comparison) which violates the transitiveness requirement of total ordering.

Unfortunately I'm not sure how to properly fix this so Cc-ing Vladimir 
for help.

/Yury

Comments

Vladimir Makarov Dec. 17, 2015, 7:36 p.m. UTC | #1 
On 12/17/2015 04:00 AM, Yury Gribov wrote:
> This patch fixes intransitive comparison in 
> reload_pseudo_compare_func. Imagine the following
> situation:
> 1) bitmap_bit_p is unset for A and B but set for C
> 2) A < B (due to early ira_reg_class_max_nregs comparison)
> 3) B < C (due to following regno_assign_info comparison)
>
> It may then easily happen that A > C (due to regno_assign_info 
> comparison) which violates the transitiveness requirement of total 
> ordering.
>
> Unfortunately I'm not sure how to properly fix this so Cc-ing Vladimir 
> for help.
>
   Yury, thanks for reporting this.  Yes that could be a problem but I 
can not approve this patch as it might result in *significant* 
performance degradation.  I remember the code.  What you propose is the 
original patch (PR57878) and it was exactly modified to the current 
version because of the negative performance impact.  The current code is 
safe although it might result into infinite cycling for some sort 
algorithms but not for used qsort.

   I'll think how to fix it better. Probably I will need two comparison 
functions for different assignment iterations.  The solution will need 
benchmarking as the code is critical for LRA performance.  Could you 
fill a bug report in order not to forget the issue.
Yury Gribov Dec. 18, 2015, 7:50 p.m. UTC | #2 
On 12/17/2015 10:36 PM, Vladimir Makarov wrote:
> On 12/17/2015 04:00 AM, Yury Gribov wrote:
>> This patch fixes intransitive comparison in
>> reload_pseudo_compare_func. Imagine the following
>> situation:
>> 1) bitmap_bit_p is unset for A and B but set for C
>> 2) A < B (due to early ira_reg_class_max_nregs comparison)
>> 3) B < C (due to following regno_assign_info comparison)
>>
>> It may then easily happen that A > C (due to regno_assign_info
>> comparison) which violates the transitiveness requirement of total
>> ordering.
>>
>> Unfortunately I'm not sure how to properly fix this so Cc-ing Vladimir
>> for help.
>>
>    Yury, thanks for reporting this.  Yes that could be a problem but I
> can not approve this patch as it might result in *significant*
> performance degradation.  I remember the code.  What you propose is the
> original patch (PR57878) and it was exactly modified to the current
> version because of the negative performance impact.  The current code is
> safe although it might result into infinite cycling for some sort
> algorithms but not for used qsort.
>
>    I'll think how to fix it better. Probably I will need two comparison
> functions for different assignment iterations.  The solution will need
> benchmarking as the code is critical for LRA performance.  Could you
> fill a bug report in order not to forget the issue.

Thanks! Submitted https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68988
diff mbox

Patch

From 83da5d11c4f013dd14c1ea0c1722c108d80f58ed Mon Sep 17 00:00:00 2001
From: Yury Gribov <tetra2005@gmail.com>
Date: Sat, 12 Dec 2015 10:08:45 +0300
Subject: [PATCH 3/5] "Fix" intransitive comparison in
 reload_pseudo_compare_func.

2015-12-17  Yury Gribov  <tetra2005@gmail.com>

	* lra-assigns.c (reload_pseudo_compare_func):
	Make transitive.

Error message:
Dec 10 00:33:18 yugr-ubuntu1404 : cc1plus[612]: qsort: comparison function is not transitive (comparison function 0x87bc50 (/home/yugr/build/gcc-4.9.3-patched-bootstrap/gcc/cc1plus+47bc50), called from 0x87d25c (/home/yugr/build/gcc-4.9.3-patched-bootstrap/gcc/cc1plus+47d25c), cmdline is "/home/yugr/build/gcc-4.9.3-patched-bootstrap/./gcc/cc1plus -quiet -nostdinc++ -I . -I /home/yugr/src/gcc-4.9.3-patched/libsanitizer/tsan -I .. -I /home/yugr/src/gcc-4.9.3-patched/libsanitizer -I /home/yugr/src/gcc-4.9.3-patched/libsanitizer/include -I ../../libstdc++-v3/include -I ../../libstdc++-v3/include/x86_64-unknown-linux-gnu -I /home/yugr/src/gcc-4.9.3-patched/libsanitizer/../libstdc++-v3/libsupc++ -imultiarch x86_64-linux-gnu -iprefix /home/yugr/build/gcc-4.9.3-patched-bootstrap/gcc/../lib/gcc/x86_64-unknown-linux-gnu/4.9.3/ -isystem /home/yugr/build/gcc-4.9.3-patched-bootstrap/./gcc/include -isystem /home/yugr/build/gcc-4.9.3-patched-bootstrap/./gcc/include-fixed -MD .libs/tsan_interface_atomic.d -MF .deps/tsan_interface_atomic.Tpo -MP -MT tsan_interface_atomic.lo -D_GNU_SOURCE -D _GNU_SOURCE -D _DEBUG -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -D _GNU_SOURCE -D PIC -isystem /home/yugr/install/gcc-4.9.3/x86_64-unknown-linux-gnu/include -isystem /home/yugr/install/gcc-4.9.3/x86_64-unknown-linux-gnu/sys-include /home/yugr/src/gcc-4.9.3-patched/libsanitizer/tsan/tsan_interface_atomic.cc -quiet -dumpbase tsan_interface_atomic.cc -mtune=generic -march=x86-64 -auxbase-strip .libs/tsan_interface_atomic.o -g -O2 -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wpedantic -Wno-long-long -Wno-variadic-macros -fno-builtin -fno-exceptions -fno-rtti -fomit-frame-pointer -funwind-tables -fvisibility=hidden -fPIC -o /tmp/cc3IPd7A.s")
---
 gcc/lra-assigns.c | 7 +------
 1 file changed, 1 insertion(+), 6 deletions(-)

diff --git a/gcc/lra-assigns.c b/gcc/lra-assigns.c
index 2a9ff21..94f3e66 100644
--- a/gcc/lra-assigns.c
+++ b/gcc/lra-assigns.c
@@ -208,12 +208,7 @@  reload_pseudo_compare_func (const void *v1p, const void *v2p)
     return diff;
   if ((diff
        = (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode]
-	  - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0
-      /* The code below executes rarely as nregs == 1 in most cases.
-	 So we should not worry about using faster data structures to
-	 check reload pseudos.  */
-      && ! bitmap_bit_p (&non_reload_pseudos, r1)
-      && ! bitmap_bit_p (&non_reload_pseudos, r2))
+	  - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0)
     return diff;
   if ((diff = (regno_assign_info[regno_assign_info[r2].first].freq
 	       - regno_assign_info[regno_assign_info[r1].first].freq)) != 0)
-- 
1.9.1