Re: [PATCH 1/2] gcc_qsort: source code changes

2018-05-14 Thread Richard Biener 
On Mon, May 14, 2018 at 8:37 AM, Alexander Monakov  wrote:
> On Sun, 13 May 2018, H.J. Lu wrote:
>> This breaks bootstrap on Fedora 28/i686:
>>
>> https://gcc.gnu.org/ml/gcc-regression/2018-05/msg00088.html
>>
>> ../../src-trunk/gcc/sort.cc:112:5: note: in expansion of macro ‘REORDER_45’
>>  REORDER_45 (8, 8, 0);
>>  ^~
>> ../../src-trunk/gcc/sort.cc:100:10: error: ‘void* memcpy(void*, const
>> void*, size_t)’ forming offset [5, 8] is out of the bounds [0, 4] of
>> object ‘t2’ with type ‘size_t’ {aka ‘unsigned int’}
>> [-Werror=array-bounds]
>>memcpy (, e2 + OFFSET, SIZE);  \
>>~~~^~~~
>
> Hm, on 32-bit this is trivially dead code, I wonder why we issue the warning?
>
> In any case, due to PR 85757 it's desirable to use types with sizes matching
> the memcpy size; is the following OK to apply? Bootstrapped on 32-bit x86.

OK.

Richard.

> * sort.cc (REORDER_23): Pass the type for the temporaries instead of
> intended memcpy size.
> (REORDER_45): Likewise.
> ---
>  gcc/sort.cc | 72 
> ++---
>  1 file changed, 36 insertions(+), 36 deletions(-)
>
> diff --git a/gcc/sort.cc b/gcc/sort.cc
> index 4faf6d45dc6..c41683c91dd 100644
> --- a/gcc/sort.cc
> +++ b/gcc/sort.cc
> @@ -62,29 +62,29 @@ struct sort_ctx
>  static void
>  reorder23 (sort_ctx *c, char *e0, char *e1, char *e2)
>  {
> -#define REORDER_23(SIZE, STRIDE, OFFSET)\
> -do {\
> -  size_t t0, t1;\
> -  memcpy (, e0 + OFFSET, SIZE);  \
> -  memcpy (, e1 + OFFSET, SIZE);  \
> -  char *out = c->out + OFFSET;  \
> -  if (likely (c->n == 3))   \
> -memcpy (out + 2*STRIDE, e2 + OFFSET, SIZE); \
> -  memcpy (out, , SIZE); out += STRIDE;   \
> -  memcpy (out, , SIZE);  \
> +#define REORDER_23(TYPE, STRIDE, OFFSET) \
> +do { \
> +  TYPE t0, t1;   \
> +  memcpy (, e0 + OFFSET, sizeof (TYPE));  \
> +  memcpy (, e1 + OFFSET, sizeof (TYPE));  \
> +  char *out = c->out + OFFSET;   \
> +  if (likely (c->n == 3))\
> +memcpy (out + 2*STRIDE, e2 + OFFSET, sizeof (TYPE)); \
> +  memcpy (out, , sizeof (TYPE)); out += STRIDE;   \
> +  memcpy (out, , sizeof (TYPE));  \
>  } while (0)
>
> -  if (sizeof (size_t) == 8 && likely (c->size == 8))
> -REORDER_23 (8, 8, 0);
> -  else if (likely (c->size == 4))
> -REORDER_23 (4, 4, 0);
> +  if (likely (c->size == sizeof (size_t)))
> +REORDER_23 (size_t, sizeof (size_t), 0);
> +  else if (likely (c->size == sizeof (int)))
> +REORDER_23 (int, sizeof (int), 0);
>else
>  {
>size_t offset = 0, step = sizeof (size_t);
>for (; offset + step <= c->size; offset += step)
> -   REORDER_23 (step, c->size, offset);
> +   REORDER_23 (size_t, c->size, offset);
>for (; offset < c->size; offset++)
> -   REORDER_23 (1, c->size, offset);
> +   REORDER_23 (char, c->size, offset);
>  }
>  }
>
> @@ -92,33 +92,33 @@ do {\
>  static void
>  reorder45 (sort_ctx *c, char *e0, char *e1, char *e2, char *e3, char *e4)
>  {
> -#define REORDER_45(SIZE, STRIDE, OFFSET)\
> -do {\
> -  size_t t0, t1, t2, t3;\
> -  memcpy (, e0 + OFFSET, SIZE);  \
> -  memcpy (, e1 + OFFSET, SIZE);  \
> -  memcpy (, e2 + OFFSET, SIZE);  \
> -  memcpy (, e3 + OFFSET, SIZE);  \
> -  char *out = c->out + OFFSET;  \
> -  if (likely (c->n == 5))   \
> -memcpy (out + 4*STRIDE, e4 + OFFSET, SIZE); \
> -  memcpy (out, , SIZE); out += STRIDE;   \
> -  memcpy (out, , SIZE); out += STRIDE;   \
> -  memcpy (out, , SIZE); out += STRIDE;   \
> -  memcpy (out, , SIZE);  \
> +#define REORDER_45(TYPE, STRIDE, OFFSET) \
> +do { \
> +  TYPE t0, t1, t2, t3;   \
> +  memcpy (, e0 + OFFSET, sizeof (TYPE));  \
> +  memcpy (, e1 + OFFSET, sizeof (TYPE));  \
> +  memcpy (, e2 + OFFSET, sizeof (TYPE));  \
> +  memcpy (, e3 + OFFSET, sizeof (TYPE));  \
> +  char *out = c->out + OFFSET;   \
> +  if (likely (c->n == 5))\
> +memcpy (out + 4*STRIDE, e4 + OFFSET, sizeof (TYPE)); \
> +  memcpy (out, , sizeof (TYPE)); out += STRIDE;   \
> +  memcpy (out, , sizeof (TYPE)); out += STRIDE;   \
> +  memcpy (out, , sizeof (TYPE)); out += STRIDE;   \
> +  memcpy (out, ,

Re: [PATCH 1/2] gcc_qsort: source code changes

2018-05-14 Thread Alexander Monakov 
On Sun, 13 May 2018, H.J. Lu wrote:
> This breaks bootstrap on Fedora 28/i686:
> 
> https://gcc.gnu.org/ml/gcc-regression/2018-05/msg00088.html
> 
> ../../src-trunk/gcc/sort.cc:112:5: note: in expansion of macro ‘REORDER_45’
>  REORDER_45 (8, 8, 0);
>  ^~
> ../../src-trunk/gcc/sort.cc:100:10: error: ‘void* memcpy(void*, const
> void*, size_t)’ forming offset [5, 8] is out of the bounds [0, 4] of
> object ‘t2’ with type ‘size_t’ {aka ‘unsigned int’}
> [-Werror=array-bounds]
>memcpy (, e2 + OFFSET, SIZE);  \
>~~~^~~~

Hm, on 32-bit this is trivially dead code, I wonder why we issue the warning?

In any case, due to PR 85757 it's desirable to use types with sizes matching
the memcpy size; is the following OK to apply? Bootstrapped on 32-bit x86.

* sort.cc (REORDER_23): Pass the type for the temporaries instead of
intended memcpy size.
(REORDER_45): Likewise.
---
 gcc/sort.cc | 72 ++---
 1 file changed, 36 insertions(+), 36 deletions(-)

diff --git a/gcc/sort.cc b/gcc/sort.cc
index 4faf6d45dc6..c41683c91dd 100644
--- a/gcc/sort.cc
+++ b/gcc/sort.cc
@@ -62,29 +62,29 @@ struct sort_ctx
 static void
 reorder23 (sort_ctx *c, char *e0, char *e1, char *e2)
 {
-#define REORDER_23(SIZE, STRIDE, OFFSET)\
-do {\
-  size_t t0, t1;\
-  memcpy (, e0 + OFFSET, SIZE);  \
-  memcpy (, e1 + OFFSET, SIZE);  \
-  char *out = c->out + OFFSET;  \
-  if (likely (c->n == 3))   \
-memcpy (out + 2*STRIDE, e2 + OFFSET, SIZE); \
-  memcpy (out, , SIZE); out += STRIDE;   \
-  memcpy (out, , SIZE);  \
+#define REORDER_23(TYPE, STRIDE, OFFSET) \
+do { \
+  TYPE t0, t1;   \
+  memcpy (, e0 + OFFSET, sizeof (TYPE));  \
+  memcpy (, e1 + OFFSET, sizeof (TYPE));  \
+  char *out = c->out + OFFSET;   \
+  if (likely (c->n == 3))\
+memcpy (out + 2*STRIDE, e2 + OFFSET, sizeof (TYPE)); \
+  memcpy (out, , sizeof (TYPE)); out += STRIDE;   \
+  memcpy (out, , sizeof (TYPE));  \
 } while (0)
 
-  if (sizeof (size_t) == 8 && likely (c->size == 8))
-REORDER_23 (8, 8, 0);
-  else if (likely (c->size == 4))
-REORDER_23 (4, 4, 0);
+  if (likely (c->size == sizeof (size_t)))
+REORDER_23 (size_t, sizeof (size_t), 0);
+  else if (likely (c->size == sizeof (int)))
+REORDER_23 (int, sizeof (int), 0);
   else
 {
   size_t offset = 0, step = sizeof (size_t);
   for (; offset + step <= c->size; offset += step)
-   REORDER_23 (step, c->size, offset);
+   REORDER_23 (size_t, c->size, offset);
   for (; offset < c->size; offset++)
-   REORDER_23 (1, c->size, offset);
+   REORDER_23 (char, c->size, offset);
 }
 }
 
@@ -92,33 +92,33 @@ do {\
 static void
 reorder45 (sort_ctx *c, char *e0, char *e1, char *e2, char *e3, char *e4)
 {
-#define REORDER_45(SIZE, STRIDE, OFFSET)\
-do {\
-  size_t t0, t1, t2, t3;\
-  memcpy (, e0 + OFFSET, SIZE);  \
-  memcpy (, e1 + OFFSET, SIZE);  \
-  memcpy (, e2 + OFFSET, SIZE);  \
-  memcpy (, e3 + OFFSET, SIZE);  \
-  char *out = c->out + OFFSET;  \
-  if (likely (c->n == 5))   \
-memcpy (out + 4*STRIDE, e4 + OFFSET, SIZE); \
-  memcpy (out, , SIZE); out += STRIDE;   \
-  memcpy (out, , SIZE); out += STRIDE;   \
-  memcpy (out, , SIZE); out += STRIDE;   \
-  memcpy (out, , SIZE);  \
+#define REORDER_45(TYPE, STRIDE, OFFSET) \
+do { \
+  TYPE t0, t1, t2, t3;   \
+  memcpy (, e0 + OFFSET, sizeof (TYPE));  \
+  memcpy (, e1 + OFFSET, sizeof (TYPE));  \
+  memcpy (, e2 + OFFSET, sizeof (TYPE));  \
+  memcpy (, e3 + OFFSET, sizeof (TYPE));  \
+  char *out = c->out + OFFSET;   \
+  if (likely (c->n == 5))\
+memcpy (out + 4*STRIDE, e4 + OFFSET, sizeof (TYPE)); \
+  memcpy (out, , sizeof (TYPE)); out += STRIDE;   \
+  memcpy (out, , sizeof (TYPE)); out += STRIDE;   \
+  memcpy (out, , sizeof (TYPE)); out += STRIDE;   \
+  memcpy (out, , sizeof (TYPE));  \
 } while (0)
 
-  if (sizeof (size_t) == 8 && likely (c->size == 8))
-REORDER_45 (8, 8, 0);
-  else if (likely(c->size == 4))
-REORDER_45 (4, 4, 0);
+  if (likely (c->size == sizeof (size_t)))
+REORDER_45 (size_t, sizeof (size_t), 0);
+

Re: [PATCH 1/2] gcc_qsort: source code changes

2018-05-13 Thread H.J. Lu 
On Thu, May 10, 2018 at 8:56 AM, Alexander Monakov  wrote:
> * sort.cc: New file.
> * system.h [!CHECKING_P] (qsort): Redirect to gcc_qsort.
> * vec.c (qsort_chk): Use gcc_qsort.
>

This breaks bootstrap on Fedora 28/i686:

https://gcc.gnu.org/ml/gcc-regression/2018-05/msg00088.html

../../src-trunk/gcc/sort.cc:112:5: note: in expansion of macro ‘REORDER_45’
 REORDER_45 (8, 8, 0);
 ^~
../../src-trunk/gcc/sort.cc:100:10: error: ‘void* memcpy(void*, const
void*, size_t)’ forming offset [5, 8] is out of the bounds [0, 4] of
object ‘t2’ with type ‘size_t’ {aka ‘unsigned int’}
[-Werror=array-bounds]
   memcpy (, e2 + OFFSET, SIZE);  \
   ~~~^~~~
../../src-trunk/gcc/sort.cc:112:5: note: in expansion of macro ‘REORDER_45’
 REORDER_45 (8, 8, 0);
 ^~
../../src-trunk/gcc/sort.cc:97:18: note: ‘t2’ declared here
   size_t t0, t1, t2, t3;\
  ^~
../../src-trunk/gcc/sort.cc:112:5: note: in expansion of macro ‘REORDER_45’
 REORDER_45 (8, 8, 0);
 ^~
../../src-trunk/gcc/sort.cc:101:10: error: ‘void* memcpy(void*, const
void*, size_t)’ forming offset [5, 8] is out of the bounds [0, 4] of
object ‘t3’ with type ‘size_t’ {aka ‘unsigned int’}
[-Werror=array-bounds]
   memcpy (, e3 + OFFSET, SIZE);  \
   ~~~^~~~
../../src-trunk/gcc/sort.cc:112:5: note: in expansion of macro ‘REORDER_45’
 REORDER_45 (8, 8, 0);
 ^~
../../src-trunk/gcc/sort.cc:97:22: note: ‘t3’ declared here
   size_t t0, t1, t2, t3;\
  ^~
../../src-trunk/gcc/sort.cc:112:5: note: in expansion of macro ‘REORDER_45’
 REORDER_45 (8, 8, 0);
 ^~
../../src-trunk/gcc/sort.cc:105:10: error: ‘void* memcpy(void*, const
void*, size_t)’ forming offset [5, 8] is out of the bounds [0, 4] of
object ‘t0’ with type ‘size_t’ {aka ‘unsigned int’}
[-Werror=array-bounds]
   memcpy (out, , SIZE); out += STRIDE;   \
   ~~~^~~~
../../src-trunk/gcc/sort.cc:112:5: note: in expansion of macro ‘REORDER_45’
 REORDER_45 (8, 8, 0);
 ^~
../../src-trunk/gcc/sort.cc:97:10: note: ‘t0’ declared here
   size_t t0, t1, t2, t3;\
  ^~
../../src-trunk/gcc/sort.cc:112:5: note: in expansion of macro ‘REORDER_45’
 REORDER_45 (8, 8, 0);
 ^~
../../src-trunk/gcc/sort.cc:106:10: error: ‘void* memcpy(void*, const
void*, size_t)’ forming offset [5, 8] is out of the bounds [0, 4] of
object ‘t1’ with type ‘size_t’ {aka ‘unsigned int’}
[-Werror=array-bounds]
   memcpy (out, , SIZE); out += STRIDE;   \
   ~~~^~~~
../../src-trunk/gcc/sort.cc:112:5: note: in expansion of macro ‘REORDER_45’
 REORDER_45 (8, 8, 0);
 ^~
../../src-trunk/gcc/sort.cc:97:14: note: ‘t1’ declared here
   size_t t0, t1, t2, t3;\
  ^~
../../src-trunk/gcc/sort.cc:112:5: note: in expansion of macro ‘REORDER_45’
 REORDER_45 (8, 8, 0);
 ^~
../../src-trunk/gcc/sort.cc:107:10: error: ‘void* memcpy(void*, const
void*, size_t)’ forming offset [5, 8] is out of the bounds [0, 4] of
object ‘t2’ with type ‘size_t’ {aka ‘unsigned int’}
[-Werror=array-bounds]
   memcpy (out, , SIZE); out += STRIDE;   \
   ~~~^~~~
../../src-trunk/gcc/sort.cc:112:5: note: in expansion of macro ‘REORDER_45’
 REORDER_45 (8, 8, 0);
 ^~
../../src-trunk/gcc/sort.cc:97:18: note: ‘t2’ declared here
   size_t t0, t1, t2, t3;\
  ^~
../../src-trunk/gcc/sort.cc:112:5: note: in expansion of macro ‘REORDER_45’
 REORDER_45 (8, 8, 0);
 ^~
../../src-trunk/gcc/sort.cc:108:10: error: ‘void* memcpy(void*, const
void*, size_t)’ forming offset [5, 8] is out of the bounds [0, 4] of
object ‘t3’ with type ‘size_t’ {aka ‘unsigned int’}
[-Werror=array-bounds]
   memcpy (out, , SIZE);  \
   ~~~^~~~
../../src-trunk/gcc/sort.cc:112:5: note: in expansion of macro ‘REORDER_45’
 REORDER_45 (8, 8, 0);
 ^~
../../src-trunk/gcc/sort.cc:97:22: note: ‘t3’ declared here
   size_t t0, t1, t2, t3;\
  ^~
../../src-trunk/gcc/sort.cc:112:5: note: in expansion of macro ‘REORDER_45’
 REORDER_45 (8, 8, 0);
 ^~

Re: [PATCH 1/2] gcc_qsort: source code changes

2018-05-11 Thread Alexander Monakov 
On Fri, 11 May 2018, Richard Biener wrote:
> Looks good to me.  As additional enhancement we might want to provide
> (even unconditionally?)
> the glibc qsort_r() interface.  I remember adding various globals to
> pass down state to the comparator...

Thanks. I have no plans w.r.t qsort_r, but OTOH a stable sort interface
can be added with tiny size/speed cost, and the sole in-tree use can be
converted :)

> I agree self-tests might be good to have.  Also it looks like the
> qsort-checking may now be somehow
> embedded within our qsort implementation?

I gave self-tests some thought after David's mail, and honestly I don't
see much value in that, given that we run qsort_chk on everything.

As for embedding, I don't think that's necessary. I prefer to keep them
separate.

Alexander

Re: [PATCH 1/2] gcc_qsort: source code changes

2018-05-11 Thread Richard Biener 
On Thu, May 10, 2018 at 5:56 PM, Alexander Monakov  wrote:
> * sort.cc: New file.
> * system.h [!CHECKING_P] (qsort): Redirect to gcc_qsort.
> * vec.c (qsort_chk): Use gcc_qsort.

Looks good to me.  As additional enhancement we might want to provide
(even unconditionally?)
the glibc qsort_r() interface.  I remember adding various globals to
pass down state to the comparator...

I agree self-tests might be good to have.  Also it looks like the
qsort-checking may now be somehow
embedded within our qsort implementation?

But all these things can be done as followup I think.

Thanks,
Richard.

> ---
>  gcc/sort.cc  | 232 
> +++
>  gcc/system.h |   7 +-
>  gcc/vec.c|   2 +-
>  3 files changed, 238 insertions(+), 3 deletions(-)
>  create mode 100644 gcc/sort.cc
>
> diff --git a/gcc/sort.cc b/gcc/sort.cc
> new file mode 100644
> index 000..4faf6d45dc6
> --- /dev/null
> +++ b/gcc/sort.cc
> @@ -0,0 +1,232 @@
> +/* Platform-independent deterministic sort function.
> +   Copyright (C) 2018 Free Software Foundation, Inc.
> +   Contributed by Alexander Monakov.
> +
> +This file is part of GCC.
> +
> +GCC is free software; you can redistribute it and/or modify it
> +under the terms of the GNU General Public License as published by the
> +Free Software Foundation; either version 3, or (at your option) any
> +later version.
> +
> +GCC is distributed in the hope that it will be useful, but WITHOUT
> +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
> +FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
> +for more details.
> +
> +You should have received a copy of the GNU General Public License
> +along with GCC; see the file COPYING3.  If not see
> +.  */
> +
> +/* This implements a sort function suitable for GCC use cases:
> +   - signature-compatible to C qsort, but relaxed contract:
> + - may apply the comparator to elements in a temporary buffer
> + - may abort on allocation failure
> +   - deterministic (but not necessarily stable)
> +   - fast, especially for common cases (0-5 elements of size 8 or 4)
> +
> +   The implementation uses a network sort for up to 5 elements and
> +   a merge sort on top of that.  Neither stage has branches depending on
> +   comparator result, trading extra arithmetic for branch mispredictions.  */
> +
> +#ifdef GENERATOR_FILE
> +#include "bconfig.h"
> +#else
> +#include "config.h"
> +#endif
> +
> +#include "system.h"
> +
> +#define likely(cond) __builtin_expect ((cond), 1)
> +
> +#ifdef __GNUC__
> +#define noinline __attribute__ ((__noinline__))
> +#else
> +#define noinline
> +#endif
> +
> +/* C-style qsort comparator function type.  */
> +typedef int cmp_fn (const void *, const void *);
> +
> +/* Structure holding read-mostly (read-only in netsort) context. */
> +struct sort_ctx
> +{
> +  cmp_fn *cmp; // pointer to comparator
> +  char   *out; // output buffer
> +  size_t n;// number of elements
> +  size_t size; // element size
> +};
> +
> +/* Helper for netsort. Permute, possibly in-place, 2 or 3 elements,
> +   placing E0 to C->OUT, E1 to C->OUT + C->SIZE, and so on. */
> +static void
> +reorder23 (sort_ctx *c, char *e0, char *e1, char *e2)
> +{
> +#define REORDER_23(SIZE, STRIDE, OFFSET)\
> +do {\
> +  size_t t0, t1;\
> +  memcpy (, e0 + OFFSET, SIZE);  \
> +  memcpy (, e1 + OFFSET, SIZE);  \
> +  char *out = c->out + OFFSET;  \
> +  if (likely (c->n == 3))   \
> +memcpy (out + 2*STRIDE, e2 + OFFSET, SIZE); \
> +  memcpy (out, , SIZE); out += STRIDE;   \
> +  memcpy (out, , SIZE);  \
> +} while (0)
> +
> +  if (sizeof (size_t) == 8 && likely (c->size == 8))
> +REORDER_23 (8, 8, 0);
> +  else if (likely (c->size == 4))
> +REORDER_23 (4, 4, 0);
> +  else
> +{
> +  size_t offset = 0, step = sizeof (size_t);
> +  for (; offset + step <= c->size; offset += step)
> +   REORDER_23 (step, c->size, offset);
> +  for (; offset < c->size; offset++)
> +   REORDER_23 (1, c->size, offset);
> +}
> +}
> +
> +/* Like reorder23, but permute 4 or 5 elements. */
> +static void
> +reorder45 (sort_ctx *c, char *e0, char *e1, char *e2, char *e3, char *e4)
> +{
> +#define REORDER_45(SIZE, STRIDE, OFFSET)\
> +do {\
> +  size_t t0, t1, t2, t3;\
> +  memcpy (, e0 + OFFSET, SIZE);  \
> +  memcpy (, e1 + OFFSET, SIZE);  \
> +  memcpy (, e2 + OFFSET, SIZE);  \
> +  memcpy (, e3 + OFFSET, SIZE);  \
> +  char *out = c->out + OFFSET;  \
> +  if (likely (c->n == 5))   \
> +memcpy (out + 4*STRIDE, e4 + OFFSET, SIZE); \
> +  memcpy (out, , SIZE); out += STRIDE;

Re: [PATCH 1/2] gcc_qsort: source code changes

2018-05-10 Thread DJ Delorie 

Alexander Monakov  writes:
> I'm not sure.  It has a weaker contract compared to qsort, and I believe
> functions in libiberty are understood to provide stronger/better replacements.

The original intent of libiberty was to provide a stronger *portability*
contract, i.e. to work around differences in underlying operating
systems.  The xfoo() variants often handle error conditions also, as
that has traditionally been something that OSs do differently anyway.

Having said that, adding something to libiberty is more complicated than
adding something to gcc (it didn't used to be), and if nobody else needs
a more portable qsort, it's a wasted effort.

Libiberty is *not* a generic "toss things in here because they're useful
and generic" library, despite being used as such.  However, it is common
among a few large projects (which used to share a repo, limiting copies
of libiberty to one), and does help in code re-use.

Given all that, I'd say that an xqsort might be appropriate in
libiberty, if it was (1) able to take over for the generic qsort[1] ,
and (2) the changes are also needed or useful in one of the other
projects using libiberty.  But given that it's currently written in C++
(it would need to be C-compatible) and only used by gcc, IMHO putting it
in libiberty would be inappropriate at this time.  The fact that qsort
is defined to be nondeterministic is not a portability issue[2].

Consider that there is also gnulib, which serves a similar purpose.

[1] i.e. if replacing qsort() with xqsort() in a C or C++ program
resulted in the same behavior as far as standards imply.

[2] if the nondeterminism is a problem, you probably need to fix your
compare function ;-)

Re: [PATCH 1/2] gcc_qsort: source code changes

2018-05-10 Thread Alexander Monakov 
On Thu, 10 May 2018, Richard Biener wrote:
> 
> Just a quick first remark - how about putting this into libiberty?  And then 
> name it xqsort? 

I'm not sure.  It has a weaker contract compared to qsort, and I believe
functions in libiberty are understood to provide stronger/better replacements.

Alexander

Re: [PATCH 1/2] gcc_qsort: source code changes

2018-05-10 Thread Richard Biener 
On May 10, 2018 5:56:40 PM GMT+02:00, Alexander Monakov  
wrote:
>   * sort.cc: New file.
>* system.h [!CHECKING_P] (qsort): Redirect to gcc_qsort.
>* vec.c (qsort_chk): Use gcc_qsort.

Just a quick first remark - how about putting this into libiberty?  And then 
name it xqsort? 

Richard. 

>---
>gcc/sort.cc  | 232
>+++
> gcc/system.h |   7 +-
> gcc/vec.c|   2 +-
> 3 files changed, 238 insertions(+), 3 deletions(-)
> create mode 100644 gcc/sort.cc
>
>diff --git a/gcc/sort.cc b/gcc/sort.cc
>new file mode 100644
>index 000..4faf6d45dc6
>--- /dev/null
>+++ b/gcc/sort.cc
>@@ -0,0 +1,232 @@
>+/* Platform-independent deterministic sort function.
>+   Copyright (C) 2018 Free Software Foundation, Inc.
>+   Contributed by Alexander Monakov.
>+
>+This file is part of GCC.
>+
>+GCC is free software; you can redistribute it and/or modify it
>+under the terms of the GNU General Public License as published by the
>+Free Software Foundation; either version 3, or (at your option) any
>+later version.
>+
>+GCC is distributed in the hope that it will be useful, but WITHOUT
>+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
>+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
>+for more details.
>+
>+You should have received a copy of the GNU General Public License
>+along with GCC; see the file COPYING3.  If not see
>+.  */
>+
>+/* This implements a sort function suitable for GCC use cases:
>+   - signature-compatible to C qsort, but relaxed contract:
>+ - may apply the comparator to elements in a temporary buffer
>+ - may abort on allocation failure
>+   - deterministic (but not necessarily stable)
>+   - fast, especially for common cases (0-5 elements of size 8 or 4)
>+
>+   The implementation uses a network sort for up to 5 elements and
>+   a merge sort on top of that.  Neither stage has branches depending
>on
>+   comparator result, trading extra arithmetic for branch
>mispredictions.  */
>+
>+#ifdef GENERATOR_FILE
>+#include "bconfig.h"
>+#else
>+#include "config.h"
>+#endif
>+
>+#include "system.h"
>+
>+#define likely(cond) __builtin_expect ((cond), 1)
>+
>+#ifdef __GNUC__
>+#define noinline __attribute__ ((__noinline__))
>+#else
>+#define noinline
>+#endif
>+
>+/* C-style qsort comparator function type.  */
>+typedef int cmp_fn (const void *, const void *);
>+
>+/* Structure holding read-mostly (read-only in netsort) context. */
>+struct sort_ctx
>+{
>+  cmp_fn *cmp; // pointer to comparator
>+  char   *out; // output buffer
>+  size_t n;// number of elements
>+  size_t size; // element size
>+};
>+
>+/* Helper for netsort. Permute, possibly in-place, 2 or 3 elements,
>+   placing E0 to C->OUT, E1 to C->OUT + C->SIZE, and so on. */
>+static void
>+reorder23 (sort_ctx *c, char *e0, char *e1, char *e2)
>+{
>+#define REORDER_23(SIZE, STRIDE, OFFSET)\
>+do {\
>+  size_t t0, t1;\
>+  memcpy (, e0 + OFFSET, SIZE);  \
>+  memcpy (, e1 + OFFSET, SIZE);  \
>+  char *out = c->out + OFFSET;  \
>+  if (likely (c->n == 3))   \
>+memcpy (out + 2*STRIDE, e2 + OFFSET, SIZE); \
>+  memcpy (out, , SIZE); out += STRIDE;   \
>+  memcpy (out, , SIZE);  \
>+} while (0)
>+
>+  if (sizeof (size_t) == 8 && likely (c->size == 8))
>+REORDER_23 (8, 8, 0);
>+  else if (likely (c->size == 4))
>+REORDER_23 (4, 4, 0);
>+  else
>+{
>+  size_t offset = 0, step = sizeof (size_t);
>+  for (; offset + step <= c->size; offset += step)
>+  REORDER_23 (step, c->size, offset);
>+  for (; offset < c->size; offset++)
>+  REORDER_23 (1, c->size, offset);
>+}
>+}
>+
>+/* Like reorder23, but permute 4 or 5 elements. */
>+static void
>+reorder45 (sort_ctx *c, char *e0, char *e1, char *e2, char *e3, char
>*e4)
>+{
>+#define REORDER_45(SIZE, STRIDE, OFFSET)\
>+do {\
>+  size_t t0, t1, t2, t3;\
>+  memcpy (, e0 + OFFSET, SIZE);  \
>+  memcpy (, e1 + OFFSET, SIZE);  \
>+  memcpy (, e2 + OFFSET, SIZE);  \
>+  memcpy (, e3 + OFFSET, SIZE);  \
>+  char *out = c->out + OFFSET;  \
>+  if (likely (c->n == 5))   \
>+memcpy (out + 4*STRIDE, e4 + OFFSET, SIZE); \
>+  memcpy (out, , SIZE); out += STRIDE;   \
>+  memcpy (out, , SIZE); out += STRIDE;   \
>+  memcpy (out, , SIZE); out += STRIDE;   \
>+  memcpy (out, , SIZE);  \
>+} while (0)
>+
>+  if (sizeof (size_t) == 8 && likely (c->size == 8))
>+REORDER_45 (8, 8, 0);
>+  else if (likely(c->size == 4))
>+REORDER_45 (4, 4, 0);
>+  else
>+{
>+  size_t offset = 0, step = sizeof (size_t);
>+  for (; offset + step <= c->size;

Re: [PATCH 1/2] gcc_qsort: source code changes

2018-05-10 Thread David Malcolm 
On Thu, 2018-05-10 at 18:56 +0300, Alexander Monakov wrote:
>   * sort.cc: New file.
> * system.h [!CHECKING_P] (qsort): Redirect to gcc_qsort.
> * vec.c (qsort_chk): Use gcc_qsort.

[...snip...]

I'm not a reviewer for this, but there's a lot of fiddly implementation
logic here, so maybe this code could use the selftest framework?

Maybe, in pseudo-code, something like this:

template 
static void
test_gcc_sort ()
{
   for (creation_strategy in {in-order, backwards}: // and anything else?
 for (int n = 0; n < some_limit; n++)
   {
  make_a_list_of_t (n, creation_strategy)
  gcc_sort (the_list);
  assert that the list is sorted;
  assert that the number of calls to the callback was sane
 }
}

void
test_gcc_sort_cc ()
{
   test_gcc_sort ();
   test_gcc_sort ();
   // etc; maybe some custom structs to exercise the deterministic property???
}

...or some such, to quickly get coverage of the various list sizes
(which the implementation seems to rely on heavily), in a non-release
build.



Hope this is constructive
Dave

[PATCH 1/2] gcc_qsort: source code changes

2018-05-10 Thread Alexander Monakov 
* sort.cc: New file.
* system.h [!CHECKING_P] (qsort): Redirect to gcc_qsort.
* vec.c (qsort_chk): Use gcc_qsort.

---
 gcc/sort.cc  | 232 +++
 gcc/system.h |   7 +-
 gcc/vec.c|   2 +-
 3 files changed, 238 insertions(+), 3 deletions(-)
 create mode 100644 gcc/sort.cc

diff --git a/gcc/sort.cc b/gcc/sort.cc
new file mode 100644
index 000..4faf6d45dc6
--- /dev/null
+++ b/gcc/sort.cc
@@ -0,0 +1,232 @@
+/* Platform-independent deterministic sort function.
+   Copyright (C) 2018 Free Software Foundation, Inc.
+   Contributed by Alexander Monakov.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 3, or (at your option) any
+later version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+.  */
+
+/* This implements a sort function suitable for GCC use cases:
+   - signature-compatible to C qsort, but relaxed contract:
+ - may apply the comparator to elements in a temporary buffer
+ - may abort on allocation failure
+   - deterministic (but not necessarily stable)
+   - fast, especially for common cases (0-5 elements of size 8 or 4)
+
+   The implementation uses a network sort for up to 5 elements and
+   a merge sort on top of that.  Neither stage has branches depending on
+   comparator result, trading extra arithmetic for branch mispredictions.  */
+
+#ifdef GENERATOR_FILE
+#include "bconfig.h"
+#else
+#include "config.h"
+#endif
+
+#include "system.h"
+
+#define likely(cond) __builtin_expect ((cond), 1)
+
+#ifdef __GNUC__
+#define noinline __attribute__ ((__noinline__))
+#else
+#define noinline
+#endif
+
+/* C-style qsort comparator function type.  */
+typedef int cmp_fn (const void *, const void *);
+
+/* Structure holding read-mostly (read-only in netsort) context. */
+struct sort_ctx
+{
+  cmp_fn *cmp; // pointer to comparator
+  char   *out; // output buffer
+  size_t n;// number of elements
+  size_t size; // element size
+};
+
+/* Helper for netsort. Permute, possibly in-place, 2 or 3 elements,
+   placing E0 to C->OUT, E1 to C->OUT + C->SIZE, and so on. */
+static void
+reorder23 (sort_ctx *c, char *e0, char *e1, char *e2)
+{
+#define REORDER_23(SIZE, STRIDE, OFFSET)\
+do {\
+  size_t t0, t1;\
+  memcpy (, e0 + OFFSET, SIZE);  \
+  memcpy (, e1 + OFFSET, SIZE);  \
+  char *out = c->out + OFFSET;  \
+  if (likely (c->n == 3))   \
+memcpy (out + 2*STRIDE, e2 + OFFSET, SIZE); \
+  memcpy (out, , SIZE); out += STRIDE;   \
+  memcpy (out, , SIZE);  \
+} while (0)
+
+  if (sizeof (size_t) == 8 && likely (c->size == 8))
+REORDER_23 (8, 8, 0);
+  else if (likely (c->size == 4))
+REORDER_23 (4, 4, 0);
+  else
+{
+  size_t offset = 0, step = sizeof (size_t);
+  for (; offset + step <= c->size; offset += step)
+   REORDER_23 (step, c->size, offset);
+  for (; offset < c->size; offset++)
+   REORDER_23 (1, c->size, offset);
+}
+}
+
+/* Like reorder23, but permute 4 or 5 elements. */
+static void
+reorder45 (sort_ctx *c, char *e0, char *e1, char *e2, char *e3, char *e4)
+{
+#define REORDER_45(SIZE, STRIDE, OFFSET)\
+do {\
+  size_t t0, t1, t2, t3;\
+  memcpy (, e0 + OFFSET, SIZE);  \
+  memcpy (, e1 + OFFSET, SIZE);  \
+  memcpy (, e2 + OFFSET, SIZE);  \
+  memcpy (, e3 + OFFSET, SIZE);  \
+  char *out = c->out + OFFSET;  \
+  if (likely (c->n == 5))   \
+memcpy (out + 4*STRIDE, e4 + OFFSET, SIZE); \
+  memcpy (out, , SIZE); out += STRIDE;   \
+  memcpy (out, , SIZE); out += STRIDE;   \
+  memcpy (out, , SIZE); out += STRIDE;   \
+  memcpy (out, , SIZE);  \
+} while (0)
+
+  if (sizeof (size_t) == 8 && likely (c->size == 8))
+REORDER_45 (8, 8, 0);
+  else if (likely(c->size == 4))
+REORDER_45 (4, 4, 0);
+  else
+{
+  size_t offset = 0, step = sizeof (size_t);
+  for (; offset + step <= c->size; offset += step)
+   REORDER_45 (step, c->size, offset);
+  for (; offset < c->size; offset++)
+   REORDER_45 (1, c->size, offset);
+}
+}
+
+/* Helper for netsort. Invoke comparator CMP on E0 and E1.
+   Return E0^E1 if E0 compares less than E1, zero otherwise.
+   This is noinline to avoid code growth and