[PATCH] Fix qsort ordering violation in tree-vrp.c

[PATCH] Fix qsort ordering violation in tree-vrp.c

[Yuri Gribov]

[-- Attachment #1: Type: text/plain, Size: 654 bytes --]

Hi,

This is a follow-up on https://gcc.gnu.org/ml/gcc/2017-07/msg00078.html

compare_assert_loc in tree-vrp.c could return unpredictable results
due to implicit conversion of unsigned subtraction to int here:
  return ha - hb;

This could return inconsistent results for objects with the following hashes:
  a: 0xdc8e4f72U
  b: 0x912ab538U
  c: 0x5ae66e3bU
Then
  a > b because (int)(0xdc8e4f72U - 0x912ab538U) > 0
  b > c because (int)(0x912ab538U - 0x5ae66e3bU) > 0
but
  a < c because (int)(0xdc8e4f72U - 0x5ae66e3bU) == (int)0x81a7e137U < 0

Bug was found with https://github.com/yugr/sortcheck

Bootstrapped and regtested in x64, ok for trunk?

-Y

[-- Attachment #2: fix-order-1.patch --]
[-- Type: application/octet-stream, Size: 627 bytes --]

2017-07-15  Yury Gribov  <tetra2005@gmail.com>

gcc/
        * tree-vrp.c (compare_assert_loc): Fix comparison function
	to return predictable results.

diff -rupN gcc/gcc/tree-vrp.c gcc-qsort/gcc/tree-vrp.c
--- gcc/gcc/tree-vrp.c	2017-07-14 08:20:48.000000000 +0200
+++ gcc-qsort/gcc/tree-vrp.c	2017-07-14 10:04:06.000000000 +0200
@@ -6426,7 +6426,7 @@ compare_assert_loc (const void *pa, cons
     return (a->e && b->e
 	    ? a->e->src->index - b->e->src->index
 	    : a->bb->index - b->bb->index);
-  return ha - hb;
+  return ha > hb ? 1 : -1;
 }
 
 /* Process all the insertions registered for every name N_i registered

Re: [PATCH] Fix qsort ordering violation in tree-vrp.c

[Richard Biener]

On Sat, 15 Jul 2017, Yuri Gribov wrote:

> Hi,
> 
> This is a follow-up on https://gcc.gnu.org/ml/gcc/2017-07/msg00078.html
> 
> compare_assert_loc in tree-vrp.c could return unpredictable results
> due to implicit conversion of unsigned subtraction to int here:
>   return ha - hb;
> 
> This could return inconsistent results for objects with the following hashes:
>   a: 0xdc8e4f72U
>   b: 0x912ab538U
>   c: 0x5ae66e3bU
> Then
>   a > b because (int)(0xdc8e4f72U - 0x912ab538U) > 0
>   b > c because (int)(0x912ab538U - 0x5ae66e3bU) > 0
> but
>   a < c because (int)(0xdc8e4f72U - 0x5ae66e3bU) == (int)0x81a7e137U < 0
> 
> Bug was found with https://github.com/yugr/sortcheck
> 
> Bootstrapped and regtested in x64, ok for trunk?

Ok.

Thanks,
Richard.