#include "config.h"
#include "system.h"

Include dependency graph for sort.cc:

Data Structures
struct	sort_ctx

struct	sort_r_ctx

Macros
#define	noinline

#define	REORDER_23(TYPE, STRIDE, OFFSET)

#define	REORDER_45(TYPE, STRIDE, OFFSET)

#define	CMP(e0, e1)

#define	MERGE_ELTSIZE(SIZE)

Typedefs
typedef int	cmp_fn(const void , const void )

Functions
template<typename sort_ctx >
static void	reorder23 (sort_ctx c, char e0, char e1, char e2)

template<typename sort_ctx >
static void	reorder45 (sort_ctx c, char e0, char e1, char e2, char e3, char e4)

template<typename sort_ctx >
static noinline intptr_t	cmp1 (char e0, char e1, sort_ctx *c)

template<typename sort_ctx >
static void	netsort (char in, sort_ctx c)

template<typename sort_ctx >
static void	mergesort (char in, sort_ctx c, size_t n, char out, char tmp)

void	gcc_qsort (void vbase, size_t n, size_t size, cmp_fn cmp)

void	gcc_sort_r (void vbase, size_t n, size_t size, sort_r_cmp_fn cmp, void *data)

void	gcc_stablesort (void vbase, size_t n, size_t size, cmp_fn cmp)

void	gcc_stablesort_r (void vbase, size_t n, size_t size, sort_r_cmp_fn cmp, void *data)

Macro Definition Documentation

◆ CMP

#define CMP	(		e0,
			e1 )

Value:

do {                                  \
  intptr_t x = cmp1 (e1, e0, c);      \
  e0 = (char *)((intptr_t)e0 ^ x);    \
  e1 = (char *)((intptr_t)e1 ^ x);    \
} while (0)

Referenced by netsort().

◆ MERGE_ELTSIZE

#define MERGE_ELTSIZE ( SIZE )

Value:

do {                                            \
  intptr_t mr = c->cmp (r, l) >> 31;            \
  intptr_t lr = (intptr_t)l ^ (intptr_t)r;      \
  lr = (intptr_t)l ^ (lr & mr);                 \
  out = (char *)memcpy (out, (char *)lr, SIZE); \
  out += SIZE;                                  \
  r += mr & SIZE;                               \
  if (r == out) return;                         \
  l += ~mr & SIZE;                              \
} while (r != end)

Referenced by mergesort().

◆ noinline

#define noinline

Platform-independent deterministic sort function.
   Copyright (C) 2018-2024 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
<http://www.gnu.org/licenses/>.

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 sorting networks 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.

◆ REORDER_23

#define REORDER_23	(	TYPE,
		STRIDE,
		OFFSET )

Value:

do {                                                     \
  TYPE t0, t1;                                           \
  memcpy (&t0, e0 + OFFSET, sizeof (TYPE));              \
  memcpy (&t1, e1 + OFFSET, sizeof (TYPE));              \
  char *out = c->out + OFFSET;                           \
  if (LIKELY (c->n == 3))                                \
    memmove (out + 2*STRIDE, e2 + OFFSET, sizeof (TYPE));\
  memcpy (out, &t0, sizeof (TYPE)); out += STRIDE;       \
  memcpy (out, &t1, sizeof (TYPE));                      \
} while (0)

Referenced by reorder23().

◆ REORDER_45

#define REORDER_45	(	TYPE,
		STRIDE,
		OFFSET )

Value:

do {                                                     \
  TYPE t0, t1, t2, t3;                                   \
  memcpy (&t0, e0 + OFFSET, sizeof (TYPE));              \
  memcpy (&t1, e1 + OFFSET, sizeof (TYPE));              \
  memcpy (&t2, e2 + OFFSET, sizeof (TYPE));              \
  memcpy (&t3, e3 + OFFSET, sizeof (TYPE));              \
  char *out = c->out + OFFSET;                           \
  if (LIKELY (c->n == 5))                                \
    memmove (out + 4*STRIDE, e4 + OFFSET, sizeof (TYPE));\
  memcpy (out, &t0, sizeof (TYPE)); out += STRIDE;       \
  memcpy (out, &t1, sizeof (TYPE)); out += STRIDE;       \
  memcpy (out, &t2, sizeof (TYPE)); out += STRIDE;       \
  memcpy (out, &t3, sizeof (TYPE));                      \
} while (0)

Referenced by reorder45().

Typedef Documentation

◆ cmp_fn

typedef int cmp_fn(const void *, const void *)

C-style qsort comparator function type.

Function Documentation

◆ cmp1()

template<typename sort_ctx >

static noinline intptr_t cmp1	(	char *	e0,
		char *	e1,
		sort_ctx *	c )

static

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 confine invocation
to a single call site, assisting indirect branch prediction.

References sort_ctx::cmp.

Referenced by expand_doubleword_shift(), expand_doubleword_shift_condmove(), find_unswitching_predicates_for_bb(), fold_builtin_iseqsig(), gimple_simplify_phiopt(), optimize_vec_cond_expr(), spaceship_replacement(), and typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_splay().

◆ gcc_qsort()

void gcc_qsort	(	void *	vbase,
		size_t	n,
		size_t	size,
		cmp_fn *	cmp )

Replacement for C qsort.

References free(), mergesort(), qsort_chk(), and scratch.

Referenced by gcc_stablesort(), and vec< T, A, vl_embed >::qsort().

◆ gcc_sort_r()

void gcc_sort_r	(	void *	vbase,
		size_t	n,
		size_t	size,
		sort_r_cmp_fn *	cmp,
		void *	data )

Substitute for Glibc qsort_r.

References free(), mergesort(), qsort_chk(), and scratch.

Referenced by analyze_memory_references(), gcc_stablesort_r(), get_loop_body_in_custom_order(), rev_post_order_and_mark_dfs_back_seme(), vec< T, A, vl_embed >::sort(), and sort_bbs_postorder().

◆ gcc_stablesort()

void gcc_stablesort	(	void *	vbase,
		size_t	n,
		size_t	size,
		cmp_fn *	cmp )

Stable sort, signature-compatible to C qsort.

References gcc_qsort().

Referenced by fuse_memset_builtins(), and reorder_basic_blocks_simple().

◆ gcc_stablesort_r()

void gcc_stablesort_r	(	void *	vbase,
		size_t	n,
		size_t	size,
		sort_r_cmp_fn *	cmp,
		void *	data )

Stable sort, signature-compatible to Glibc qsort_r.

References gcc_sort_r().

Referenced by vec< T, A, vl_embed >::stablesort().

◆ mergesort()

template<typename sort_ctx >

static void mergesort	(	char *	in,
		sort_ctx *	c,
		size_t	n,
		char *	out,
		char *	tmp )

static

Execute merge sort on N elements from IN, placing them into OUT,
using TMP as temporary storage if IN is equal to OUT.
This is a stable sort if netsort is used only for 2 or 3 elements.

References sort_ctx::cmp, end(), LIKELY, MERGE_ELTSIZE, mergesort(), sort_ctx::n, netsort(), nr, sort_ctx::out, r, and sort_ctx::size.

Referenced by gcc_qsort(), gcc_sort_r(), and mergesort().

◆ netsort()

template<typename sort_ctx >

static void netsort	(	char *	in,
		sort_ctx *	c )

static

Apply a sorting network to 2 to 5 elements from IN, placing them into C->OUT.
IN may be equal to C->OUT, in which case elements are sorted in place.

References CMP, LIKELY, sort_ctx::n, reorder23(), reorder45(), and sort_ctx::size.

Referenced by mergesort().

◆ reorder23()

template<typename sort_ctx >

static void reorder23	(	sort_ctx *	c,
		char *	e0,
		char *	e1,
		char *	e2 )

static

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.

References LIKELY, offset, REORDER_23, and sort_ctx::size.

Referenced by netsort().

◆ reorder45()

template<typename sort_ctx >

static void reorder45	(	sort_ctx *	c,
		char *	e0,
		char *	e1,
		char *	e2,
		char *	e3,
		char *	e4 )

static

Like reorder23, but permute 4 or 5 elements.

References LIKELY, offset, REORDER_45, and sort_ctx::size.

Referenced by netsort().

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ CMP

◆ MERGE_ELTSIZE

◆ noinline

◆ REORDER_23

◆ REORDER_45

Typedef Documentation

◆ cmp_fn

Function Documentation

◆ cmp1()

◆ gcc_qsort()

◆ gcc_sort_r()

◆ gcc_stablesort()

◆ gcc_stablesort_r()

◆ mergesort()

◆ netsort()

◆ reorder23()

◆ reorder45()