GCC Middle and Back End API Reference
|
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) |
#define CMP | ( | e0, | |
e1 ) |
#define MERGE_ELTSIZE | ( | SIZE | ) |
#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.
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, and ggc_alloc().
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().
Replacement for C qsort.
References free(), ggc_alloc(), mergesort(), qsort_chk(), and scratch.
Referenced by gcc_stablesort(), and vec< T, A, vl_embed >::qsort().
Substitute for Glibc qsort_r.
References free(), ggc_alloc(), 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().
Stable sort, signature-compatible to C qsort.
References gcc_qsort(), and ggc_alloc().
Referenced by fuse_memset_builtins(), and reorder_basic_blocks_simple().
Stable sort, signature-compatible to Glibc qsort_r.
References gcc_sort_r(), and ggc_alloc().
Referenced by vec< T, A, vl_embed >::stablesort().
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(), ggc_alloc(), 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().
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, ggc_alloc(), LIKELY, sort_ctx::n, reorder23(), reorder45(), and sort_ctx::size.
Referenced by mergesort().
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 ggc_alloc(), LIKELY, offset, REORDER_23, and sort_ctx::size.
Referenced by netsort().