Re: [PATCH 7/7] riscv: Add support for str(n)cmp inline expansion
> > I would like to have a unified option interface, > > maybe -m[no-]inline-str[n]cmp and -minline-str[n]cmp-limit. > > For the basic option (-m[no-]inline-str[n]cmp), I would punt to > -fno-builtin-str[n]cmp. -fno-bulitin-* will also suppress middle-end optimization for those builtins. see: https://github.com/gcc-mirror/gcc/blob/master/gcc/tree-ssa-strlen.cc#L5372 and https://github.com/gcc-mirror/gcc/blob/master/gcc/tree-loop-distribution.cc for -fno-bulitin-memcpy/memset/memmove > The limit-one sounds more like a --param? Use -param=inline-*-limit= sound good idea, aarch64 and x86 have few options like that. > > > And add some option like this: > > -minline-str[n]cmp=[bitmanip|vector|auto] in future, > > If we want to follow the lead of others, then x86 has a > -mstringop-strategy=alg Using same option name as x86 is SGTM. > > since I assume we'll have different versions of those things. > > > > > > > > gcc/ChangeLog: > > > > > > * config/riscv/riscv-protos.h (riscv_expand_strn_compare): New > > > prototype. > > > * config/riscv/riscv-string.cc (GEN_EMIT_HELPER3): New helper > > > macros. > > > (GEN_EMIT_HELPER2): New helper macros. > > > (expand_strncmp_zbb_sequence): New function. > > > (riscv_emit_str_compare_zbb): New function. > > > (riscv_expand_strn_compare): New function. > > > * config/riscv/riscv.md (cmpstrnsi): Invoke expansion functions > > > for strn_compare. > > > (cmpstrsi): Invoke expansion functions for strn_compare. > > > * config/riscv/riscv.opt: Add new parameter > > > '-mstring-compare-inline-limit'. > > > > We need to document this option.
Re: [PATCH 7/7] riscv: Add support for str(n)cmp inline expansion
On Tue, 15 Nov 2022 at 01:46, Kito Cheng wrote: > > Hi Christoph: > > > This patch implements expansions for the cmpstrsi and the cmpstrnsi > > builtins using Zbb instructions (if available). > > This allows to inline calls to strcmp() and strncmp(). > > > > The expansion basically emits a peeled comparison sequence (i.e. a peeled > > comparison loop) which compares XLEN bits per step if possible. > > > > The emitted sequence can be controlled, by setting the maximum number > > of compared bytes (-mstring-compare-inline-limit). > > I would like to have a unified option interface, > maybe -m[no-]inline-str[n]cmp and -minline-str[n]cmp-limit. For the basic option (-m[no-]inline-str[n]cmp), I would punt to -fno-builtin-str[n]cmp. The limit-one sounds more like a --param? > And add some option like this: > -minline-str[n]cmp=[bitmanip|vector|auto] in future, If we want to follow the lead of others, then x86 has a -mstringop-strategy=alg > since I assume we'll have different versions of those things. > > > > > gcc/ChangeLog: > > > > * config/riscv/riscv-protos.h (riscv_expand_strn_compare): New > > prototype. > > * config/riscv/riscv-string.cc (GEN_EMIT_HELPER3): New helper > > macros. > > (GEN_EMIT_HELPER2): New helper macros. > > (expand_strncmp_zbb_sequence): New function. > > (riscv_emit_str_compare_zbb): New function. > > (riscv_expand_strn_compare): New function. > > * config/riscv/riscv.md (cmpstrnsi): Invoke expansion functions > > for strn_compare. > > (cmpstrsi): Invoke expansion functions for strn_compare. > > * config/riscv/riscv.opt: Add new parameter > > '-mstring-compare-inline-limit'. > > We need to document this option.
Re: [PATCH 7/7] riscv: Add support for str(n)cmp inline expansion
On Tue, Nov 15, 2022 at 1:46 AM Kito Cheng wrote: > Hi Christoph: > > > This patch implements expansions for the cmpstrsi and the cmpstrnsi > > builtins using Zbb instructions (if available). > > This allows to inline calls to strcmp() and strncmp(). > > > > The expansion basically emits a peeled comparison sequence (i.e. a peeled > > comparison loop) which compares XLEN bits per step if possible. > > > > The emitted sequence can be controlled, by setting the maximum number > > of compared bytes (-mstring-compare-inline-limit). > > I would like to have a unified option interface, > maybe -m[no-]inline-str[n]cmp and -minline-str[n]cmp-limit. > Ok, I don't mind (in fact, I thought about this as well). The reason why it is how it is: I took inspiration from the rs6000 backend. > And add some option like this: > -minline-str[n]cmp=[bitmanip|vector|auto] in future, > since I assume we'll have different versions of those things. > > > > > gcc/ChangeLog: > > > > * config/riscv/riscv-protos.h (riscv_expand_strn_compare): New > > prototype. > > * config/riscv/riscv-string.cc (GEN_EMIT_HELPER3): New helper > > macros. > > (GEN_EMIT_HELPER2): New helper macros. > > (expand_strncmp_zbb_sequence): New function. > > (riscv_emit_str_compare_zbb): New function. > > (riscv_expand_strn_compare): New function. > > * config/riscv/riscv.md (cmpstrnsi): Invoke expansion functions > > for strn_compare. > > (cmpstrsi): Invoke expansion functions for strn_compare. > > * config/riscv/riscv.opt: Add new parameter > > '-mstring-compare-inline-limit'. > > We need to document this option. >
Re: [PATCH 7/7] riscv: Add support for str(n)cmp inline expansion
On 11/14/22 17:53, Palmer Dabbelt wrote: On Mon, 14 Nov 2022 16:46:37 PST (-0800), Kito Cheng wrote: Hi Christoph: This patch implements expansions for the cmpstrsi and the cmpstrnsi builtins using Zbb instructions (if available). This allows to inline calls to strcmp() and strncmp(). The expansion basically emits a peeled comparison sequence (i.e. a peeled comparison loop) which compares XLEN bits per step if possible. The emitted sequence can be controlled, by setting the maximum number of compared bytes (-mstring-compare-inline-limit). I would like to have a unified option interface, maybe -m[no-]inline-str[n]cmp and -minline-str[n]cmp-limit. And add some option like this: -minline-str[n]cmp=[bitmanip|vector|auto] in future, since I assume we'll have different versions of those things. Can we just decide that from mtune? We'll probably have uarch-specific string functions at some point, might as well start planning for it now. Sure, though the implementation isn't terribly tied to any uarch at the moment and I doubt uarch approaches would make significant impacts here -- we're peeling off some small number of iterations fairly generically. The uarch specific stuff would be the code in glibc selected by an ifunc. uarch variants for block copiers seem inevitable though :-) I don' t have strong opinions here, so if we want to key off mtune, sure. If we want to have variants for scalar vs vector that's quite reasonable too. Or if we want to go all the way to uarch specific implementations, I won't object. th gcc/ChangeLog: * config/riscv/riscv-protos.h (riscv_expand_strn_compare): New prototype. * config/riscv/riscv-string.cc (GEN_EMIT_HELPER3): New helper macros. (GEN_EMIT_HELPER2): New helper macros. (expand_strncmp_zbb_sequence): New function. (riscv_emit_str_compare_zbb): New function. (riscv_expand_strn_compare): New function. * config/riscv/riscv.md (cmpstrnsi): Invoke expansion functions for strn_compare. (cmpstrsi): Invoke expansion functions for strn_compare. * config/riscv/riscv.opt: Add new parameter '-mstring-compare-inline-limit'. We need to document this option. Yes, definitely needs documentation. Thanks for catching that. jeff
Re: [PATCH 7/7] riscv: Add support for str(n)cmp inline expansion
On Tue, Nov 15, 2022 at 8:53 AM Palmer Dabbelt wrote: > > On Mon, 14 Nov 2022 16:46:37 PST (-0800), Kito Cheng wrote: > > Hi Christoph: > > > >> This patch implements expansions for the cmpstrsi and the cmpstrnsi > >> builtins using Zbb instructions (if available). > >> This allows to inline calls to strcmp() and strncmp(). > >> > >> The expansion basically emits a peeled comparison sequence (i.e. a peeled > >> comparison loop) which compares XLEN bits per step if possible. > >> > >> The emitted sequence can be controlled, by setting the maximum number > >> of compared bytes (-mstring-compare-inline-limit). > > > > I would like to have a unified option interface, > > maybe -m[no-]inline-str[n]cmp and -minline-str[n]cmp-limit. > > And add some option like this: > > -minline-str[n]cmp=[bitmanip|vector|auto] in future, > > since I assume we'll have different versions of those things. > > Can we just decide that from mtune? We'll probably have uarch-specific > string functions at some point, might as well start planning for it now. I assume you mean the -minline-str[n]cmp=[bitmanip|vector|auto] part? I think this part should have more discussion and could defer that until we reach consensus. But -m[no-]inline-str[n]cmp and -minline-str[n]cmp-limit part I favor having those two options to disable and/or fine tune those parameters. > > >> gcc/ChangeLog: > >> > >> * config/riscv/riscv-protos.h (riscv_expand_strn_compare): New > >> prototype. > >> * config/riscv/riscv-string.cc (GEN_EMIT_HELPER3): New helper > >> macros. > >> (GEN_EMIT_HELPER2): New helper macros. > >> (expand_strncmp_zbb_sequence): New function. > >> (riscv_emit_str_compare_zbb): New function. > >> (riscv_expand_strn_compare): New function. > >> * config/riscv/riscv.md (cmpstrnsi): Invoke expansion functions > >> for strn_compare. > >> (cmpstrsi): Invoke expansion functions for strn_compare. > >> * config/riscv/riscv.opt: Add new parameter > >> '-mstring-compare-inline-limit'. > > > > We need to document this option.
Re: [PATCH 7/7] riscv: Add support for str(n)cmp inline expansion
On Mon, 14 Nov 2022 16:46:37 PST (-0800), Kito Cheng wrote: Hi Christoph: This patch implements expansions for the cmpstrsi and the cmpstrnsi builtins using Zbb instructions (if available). This allows to inline calls to strcmp() and strncmp(). The expansion basically emits a peeled comparison sequence (i.e. a peeled comparison loop) which compares XLEN bits per step if possible. The emitted sequence can be controlled, by setting the maximum number of compared bytes (-mstring-compare-inline-limit). I would like to have a unified option interface, maybe -m[no-]inline-str[n]cmp and -minline-str[n]cmp-limit. And add some option like this: -minline-str[n]cmp=[bitmanip|vector|auto] in future, since I assume we'll have different versions of those things. Can we just decide that from mtune? We'll probably have uarch-specific string functions at some point, might as well start planning for it now. gcc/ChangeLog: * config/riscv/riscv-protos.h (riscv_expand_strn_compare): New prototype. * config/riscv/riscv-string.cc (GEN_EMIT_HELPER3): New helper macros. (GEN_EMIT_HELPER2): New helper macros. (expand_strncmp_zbb_sequence): New function. (riscv_emit_str_compare_zbb): New function. (riscv_expand_strn_compare): New function. * config/riscv/riscv.md (cmpstrnsi): Invoke expansion functions for strn_compare. (cmpstrsi): Invoke expansion functions for strn_compare. * config/riscv/riscv.opt: Add new parameter '-mstring-compare-inline-limit'. We need to document this option.
Re: [PATCH 7/7] riscv: Add support for str(n)cmp inline expansion
Hi Christoph: > This patch implements expansions for the cmpstrsi and the cmpstrnsi > builtins using Zbb instructions (if available). > This allows to inline calls to strcmp() and strncmp(). > > The expansion basically emits a peeled comparison sequence (i.e. a peeled > comparison loop) which compares XLEN bits per step if possible. > > The emitted sequence can be controlled, by setting the maximum number > of compared bytes (-mstring-compare-inline-limit). I would like to have a unified option interface, maybe -m[no-]inline-str[n]cmp and -minline-str[n]cmp-limit. And add some option like this: -minline-str[n]cmp=[bitmanip|vector|auto] in future, since I assume we'll have different versions of those things. > > gcc/ChangeLog: > > * config/riscv/riscv-protos.h (riscv_expand_strn_compare): New > prototype. > * config/riscv/riscv-string.cc (GEN_EMIT_HELPER3): New helper > macros. > (GEN_EMIT_HELPER2): New helper macros. > (expand_strncmp_zbb_sequence): New function. > (riscv_emit_str_compare_zbb): New function. > (riscv_expand_strn_compare): New function. > * config/riscv/riscv.md (cmpstrnsi): Invoke expansion functions > for strn_compare. > (cmpstrsi): Invoke expansion functions for strn_compare. > * config/riscv/riscv.opt: Add new parameter > '-mstring-compare-inline-limit'. We need to document this option.
Re: [PATCH 7/7] riscv: Add support for str(n)cmp inline expansion
On 11/14/22 14:49, Christoph Müllner wrote: We can take this further, but then the following questions pop up: * how much data processing per loop iteration? I have no idea because I don't have any real data. Last time I gathered any data on this issue was circa 1988 :-) * what about unaligned strings? I'd punt. I don't think we can depend on having a high performance unaligned access. You could do a dynamic check of alignment, but you'd really need to know that they're aligned often enough that the dynamic check can often be recovered. Happy to get suggestions/opinions for improvement. I think this is pretty good without additional data that would indicate that handling unaligned cases or a different number of loop peels would be a notable improvement. Jeff
Re: [PATCH 7/7] riscv: Add support for str(n)cmp inline expansion
On Mon, Nov 14, 2022 at 8:28 PM Jeff Law wrote: > > On 11/13/22 16:05, Christoph Muellner wrote: > > From: Christoph Müllner > > > > This patch implements expansions for the cmpstrsi and the cmpstrnsi > > builtins using Zbb instructions (if available). > > This allows to inline calls to strcmp() and strncmp(). > > > > The expansion basically emits a peeled comparison sequence (i.e. a peeled > > comparison loop) which compares XLEN bits per step if possible. > > > > The emitted sequence can be controlled, by setting the maximum number > > of compared bytes (-mstring-compare-inline-limit). > > > > gcc/ChangeLog: > > > > * config/riscv/riscv-protos.h (riscv_expand_strn_compare): New > > prototype. > > * config/riscv/riscv-string.cc (GEN_EMIT_HELPER3): New helper > > macros. > > (GEN_EMIT_HELPER2): New helper macros. > > (expand_strncmp_zbb_sequence): New function. > > (riscv_emit_str_compare_zbb): New function. > > (riscv_expand_strn_compare): New function. > > * config/riscv/riscv.md (cmpstrnsi): Invoke expansion functions > > for strn_compare. > > (cmpstrsi): Invoke expansion functions for strn_compare. > > * config/riscv/riscv.opt: Add new parameter > > '-mstring-compare-inline-limit'. > > Presumably the hybrid inline + out of line approach is to capture the > fact that most strings compare unequal early, then punt out to the > library if they don't follow that model? It looks like we're structured > for that case by peeling iterations rather than having a fully inlined > approach. Just want to confirm... > Yes, this was inspired by gcc/config/rs6000/rs6000-string.cc (e.g. expand_strncmp_gpr_sequence). The current implementation emits an unrolled loop to process up to N characters. For longer strings, we do a handover to libc to process the remainder there. The hand-over implies a call overhead and, of course, a well-optimized str(n)cmp implementation would be beneficial (once we have the information in user space for ifuncs). We can take this further, but then the following questions pop up: * how much data processing per loop iteration? * what about unaligned strings? Happy to get suggestions/opinions for improvement. > I was a bit worried about the "readahead" problem that arises when > reading more than a byte and a NUL is found in the first string. If > you're not careful, the readahead of the second string could fault. But > it looks like we avoid that by requiring word alignment on both strings. > Yes, aligned strings are not affected by the readahead. I wonder if we should add dynamic tests in case the compiler cannot derive XLEN-alignment so we capture more cases (e.g. character-arrays have guaranteed alignment 1, but are allocated with a higher actual alignment on the stack). > > + > > +/* Emit a string comparison sequence using Zbb instruction. > > + > > + OPERANDS[0] is the target (result). > > + OPERANDS[1] is the first source. > > + OPERANDS[2] is the second source. > > + If NO_LENGTH is zero, then: > > + OPERANDS[3] is the length. > > + OPERANDS[4] is the alignment in bytes. > > + If NO_LENGTH is nonzero, then: > > + OPERANDS[3] is the alignment in bytes. > > Ugh. I guess it's inevitable unless we want to drop the array and pass > each element individually (in which case we'd pass a NULL_RTX in the > case we don't have a length argument). > I will split the array into individual rtx arguments as suggested. > I'd like to give others a chance to chime in here. Everything looks > sensible here, but I may have missed something. So give the other > maintainers a couple days to chime in before committing. > > > Jeff > >
Re: [PATCH 7/7] riscv: Add support for str(n)cmp inline expansion
On 11/13/22 16:05, Christoph Muellner wrote: From: Christoph Müllner This patch implements expansions for the cmpstrsi and the cmpstrnsi builtins using Zbb instructions (if available). This allows to inline calls to strcmp() and strncmp(). The expansion basically emits a peeled comparison sequence (i.e. a peeled comparison loop) which compares XLEN bits per step if possible. The emitted sequence can be controlled, by setting the maximum number of compared bytes (-mstring-compare-inline-limit). gcc/ChangeLog: * config/riscv/riscv-protos.h (riscv_expand_strn_compare): New prototype. * config/riscv/riscv-string.cc (GEN_EMIT_HELPER3): New helper macros. (GEN_EMIT_HELPER2): New helper macros. (expand_strncmp_zbb_sequence): New function. (riscv_emit_str_compare_zbb): New function. (riscv_expand_strn_compare): New function. * config/riscv/riscv.md (cmpstrnsi): Invoke expansion functions for strn_compare. (cmpstrsi): Invoke expansion functions for strn_compare. * config/riscv/riscv.opt: Add new parameter '-mstring-compare-inline-limit'. Presumably the hybrid inline + out of line approach is to capture the fact that most strings compare unequal early, then punt out to the library if they don't follow that model? It looks like we're structured for that case by peeling iterations rather than having a fully inlined approach. Just want to confirm... I was a bit worried about the "readahead" problem that arises when reading more than a byte and a NUL is found in the first string. If you're not careful, the readahead of the second string could fault. But it looks like we avoid that by requiring word alignment on both strings. + +/* Emit a string comparison sequence using Zbb instruction. + + OPERANDS[0] is the target (result). + OPERANDS[1] is the first source. + OPERANDS[2] is the second source. + If NO_LENGTH is zero, then: + OPERANDS[3] is the length. + OPERANDS[4] is the alignment in bytes. + If NO_LENGTH is nonzero, then: + OPERANDS[3] is the alignment in bytes. Ugh. I guess it's inevitable unless we want to drop the array and pass each element individually (in which case we'd pass a NULL_RTX in the case we don't have a length argument). I'd like to give others a chance to chime in here. Everything looks sensible here, but I may have missed something. So give the other maintainers a couple days to chime in before committing. Jeff
[PATCH 7/7] riscv: Add support for str(n)cmp inline expansion
From: Christoph Müllner
This patch implements expansions for the cmpstrsi and the cmpstrnsi
builtins using Zbb instructions (if available).
This allows to inline calls to strcmp() and strncmp().
The expansion basically emits a peeled comparison sequence (i.e. a peeled
comparison loop) which compares XLEN bits per step if possible.
The emitted sequence can be controlled, by setting the maximum number
of compared bytes (-mstring-compare-inline-limit).
gcc/ChangeLog:
* config/riscv/riscv-protos.h (riscv_expand_strn_compare): New
prototype.
* config/riscv/riscv-string.cc (GEN_EMIT_HELPER3): New helper
macros.
(GEN_EMIT_HELPER2): New helper macros.
(expand_strncmp_zbb_sequence): New function.
(riscv_emit_str_compare_zbb): New function.
(riscv_expand_strn_compare): New function.
* config/riscv/riscv.md (cmpstrnsi): Invoke expansion functions
for strn_compare.
(cmpstrsi): Invoke expansion functions for strn_compare.
* config/riscv/riscv.opt: Add new parameter
'-mstring-compare-inline-limit'.
Signed-off-by: Christoph Müllner
---
gcc/config/riscv/riscv-protos.h | 1 +
gcc/config/riscv/riscv-string.cc | 344 ++
gcc/config/riscv/riscv.md | 46 +++
gcc/config/riscv/riscv.opt| 5 +
.../gcc.target/riscv/zbb-strcmp-unaligned.c | 36 ++
gcc/testsuite/gcc.target/riscv/zbb-strcmp.c | 55 +++
6 files changed, 487 insertions(+)
create mode 100644 gcc/testsuite/gcc.target/riscv/zbb-strcmp-unaligned.c
create mode 100644 gcc/testsuite/gcc.target/riscv/zbb-strcmp.c
diff --git a/gcc/config/riscv/riscv-protos.h b/gcc/config/riscv/riscv-protos.h
index 18187e3bd78..7f334be333c 100644
--- a/gcc/config/riscv/riscv-protos.h
+++ b/gcc/config/riscv/riscv-protos.h
@@ -97,6 +97,7 @@ rtl_opt_pass * make_pass_shorten_memrefs (gcc::context *ctxt);
/* Routines implemented in riscv-string.c. */
extern bool riscv_expand_block_move (rtx, rtx, rtx);
extern bool riscv_expand_strlen (rtx[]);
+extern bool riscv_expand_strn_compare (rtx[], int);
/* Information about one CPU we know about. */
struct riscv_cpu_info {
diff --git a/gcc/config/riscv/riscv-string.cc b/gcc/config/riscv/riscv-string.cc
index bf96522b608..f157e04ac0c 100644
--- a/gcc/config/riscv/riscv-string.cc
+++ b/gcc/config/riscv/riscv-string.cc
@@ -84,6 +84,11 @@ GEN_EMIT_HELPER2(one_cmpl) /* do_one_cmpl2 */
GEN_EMIT_HELPER2(clz) /* do_clz2 */
GEN_EMIT_HELPER2(ctz) /* do_ctz2 */
GEN_EMIT_HELPER2(zero_extendqi) /* do_zero_extendqi2 */
+GEN_EMIT_HELPER3(xor) /* do_xor3 */
+GEN_EMIT_HELPER3(ashl) /* do_ashl3 */
+GEN_EMIT_HELPER2(bswap) /* do_bswap2 */
+GEN_EMIT_HELPER3(riscv_ior_not) /* do_riscv_ior_not3 */
+GEN_EMIT_HELPER3(riscv_and_not) /* do_riscv_and_not3 */
/* Helper function to load a byte or a Pmode register.
@@ -268,6 +273,345 @@ riscv_expand_block_move (rtx dest, rtx src, rtx length)
return false;
}
+/* Generate the sequence of compares for strcmp/strncmp using zbb instructions.
+ BYTES_TO_COMPARE is the number of bytes to be compared.
+ BASE_ALIGN is the smaller of the alignment of the two strings.
+ ORIG_SRC1 is the unmodified rtx for the first string.
+ ORIG_SRC2 is the unmodified rtx for the second string.
+ DATA1 is the register for loading the first string.
+ DATA2 is the register for loading the second string.
+ HAS_NUL is the register holding non-NUL bytes for NUL-bytes in the string.
+ TARGET is the rtx for the result register (SImode)
+ EQUALITY_COMPARE_REST if set, then we hand over to libc if string matches.
+ END_LABEL is the location before the calculation of the result value.
+ FINAL_LABEL is the location after the calculation of the result value. */
+
+static void
+expand_strncmp_zbb_sequence (unsigned HOST_WIDE_INT bytes_to_compare,
+rtx src1, rtx src2, rtx data1, rtx data2,
+rtx target, rtx orc, bool equality_compare_rest,
+rtx end_label, rtx final_label)
+{
+ const unsigned HOST_WIDE_INT p_mode_size = GET_MODE_SIZE (Pmode);
+ rtx src1_addr = force_reg (Pmode, XEXP (src1, 0));
+ rtx src2_addr = force_reg (Pmode, XEXP (src2, 0));
+ unsigned HOST_WIDE_INT offset = 0;
+
+ rtx m1 = gen_reg_rtx (Pmode);
+ emit_insn (gen_rtx_SET (m1, constm1_rtx));
+
+ /* Generate a compare sequence. */
+ while (bytes_to_compare > 0)
+{
+ machine_mode load_mode = QImode;
+ unsigned HOST_WIDE_INT load_mode_size = 1;
+ if (bytes_to_compare > 1)
+ {
+ load_mode = Pmode;
+ load_mode_size = p_mode_size;
+ }
+ unsigned HOST_WIDE_INT cmp_bytes = 0;
+
+ if (bytes_to_compare >= load_mode_size)
+ cmp_bytes = load_mode_size;
+ else
+ cmp_bytes = bytes_to_compare;
+
+ unsigned HOST_WIDE_INT remain = bytes_to_compare - cmp_bytes;
+
+ /*
