From: Richard Biener <rguenther@suse.de>
To: Jakub Jelinek <jakub@redhat.com>
Cc: gcc-patches@gcc.gnu.org
Subject: Re: [PATCH] optabs: Implement double-word ctz and ffs expansion
Date: Thu, 8 Jun 2023 07:55:08 +0200 [thread overview]
Message-ID: <CB1567FC-7FFE-4800-9A87-8FF69325EE12@suse.de> (raw)
In-Reply-To: <ZIC3TReXs9CBKEbz@tucnak>
> Am 07.06.2023 um 18:59 schrieb Jakub Jelinek via Gcc-patches <gcc-patches@gcc.gnu.org>:
>
> Hi!
>
> We have expand_doubleword_clz for a couple of years, where we emit
> double-word CLZ as if (high_word == 0) return CLZ (low_word) + word_size;
> else return CLZ (high_word);
> We can do something similar for CTZ and FFS IMHO, just with the 2
> words swapped. So if (low_word == 0) return CTZ (high_word) + word_size;
> else return CTZ (low_word); for CTZ and
> if (low_word == 0) { return high_word ? FFS (high_word) + word_size : 0;
> else return FFS (low_word);
>
> The following patch implements that.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
Ok
Richard
> Note, on some targets which implement both word_mode ctz and ffs patterns,
> it might be better to incrementally implement those double-word ffs expansion
> patterns in md files, because we aren't able to optimize it correctly;
> nothing can detect we have just made sure that argument is not 0 and so
> don't need to bother with handling that case. So, on ia32 just using
> CTZ patterns would be better there, but I think we can even do better and
> instead of doing the comparisons of the operands against 0 do the CTZ
> expansion followed by testing of flags.
>
> 2023-06-07 Jakub Jelinek <jakub@redhat.com>
>
> * optabs.cc (expand_ffs): Add forward declaration.
> (expand_doubleword_clz): Rename to ...
> (expand_doubleword_clz_ctz_ffs): ... this. Add UNOPTAB argument,
> handle also doubleword CTZ and FFS in addition to CLZ.
> (expand_unop): Adjust caller. Also call it for doubleword
> ctz_optab and ffs_optab.
>
> * gcc.target/i386/ctzll-1.c: New test.
> * gcc.target/i386/ffsll-1.c: New test.
>
> --- gcc/optabs.cc.jj 2023-06-07 09:42:14.701130305 +0200
> +++ gcc/optabs.cc 2023-06-07 14:35:04.909879272 +0200
> @@ -2697,10 +2697,14 @@ expand_clrsb_using_clz (scalar_int_mode
> return temp;
> }
>
> -/* Try calculating clz of a double-word quantity as two clz's of word-sized
> - quantities, choosing which based on whether the high word is nonzero. */
> +static rtx expand_ffs (scalar_int_mode, rtx, rtx);
> +
> +/* Try calculating clz, ctz or ffs of a double-word quantity as two clz, ctz or
> + ffs operations on word-sized quantities, choosing which based on whether the
> + high (for clz) or low (for ctz and ffs) word is nonzero. */
> static rtx
> -expand_doubleword_clz (scalar_int_mode mode, rtx op0, rtx target)
> +expand_doubleword_clz_ctz_ffs (scalar_int_mode mode, rtx op0, rtx target,
> + optab unoptab)
> {
> rtx xop0 = force_reg (mode, op0);
> rtx subhi = gen_highpart (word_mode, xop0);
> @@ -2709,6 +2713,7 @@ expand_doubleword_clz (scalar_int_mode m
> rtx_code_label *after_label = gen_label_rtx ();
> rtx_insn *seq;
> rtx temp, result;
> + int addend = 0;
>
> /* If we were not given a target, use a word_mode register, not a
> 'mode' register. The result will fit, and nobody is expecting
> @@ -2721,6 +2726,9 @@ expand_doubleword_clz (scalar_int_mode m
> 'target' to tag a REG_EQUAL note on. */
> result = gen_reg_rtx (word_mode);
>
> + if (unoptab != clz_optab)
> + std::swap (subhi, sublo);
> +
> start_sequence ();
>
> /* If the high word is not equal to zero,
> @@ -2728,7 +2736,13 @@ expand_doubleword_clz (scalar_int_mode m
> emit_cmp_and_jump_insns (subhi, CONST0_RTX (word_mode), EQ, 0,
> word_mode, true, hi0_label);
>
> - temp = expand_unop_direct (word_mode, clz_optab, subhi, result, true);
> + if (optab_handler (unoptab, word_mode) != CODE_FOR_nothing)
> + temp = expand_unop_direct (word_mode, unoptab, subhi, result, true);
> + else
> + {
> + gcc_assert (unoptab == ffs_optab);
> + temp = expand_ffs (word_mode, subhi, result);
> + }
> if (!temp)
> goto fail;
>
> @@ -2739,14 +2753,32 @@ expand_doubleword_clz (scalar_int_mode m
> emit_barrier ();
>
> /* Else clz of the full value is clz of the low word plus the number
> - of bits in the high word. */
> + of bits in the high word. Similarly for ctz/ffs of the high word,
> + except that ffs should be 0 when both words are zero. */
> emit_label (hi0_label);
>
> - temp = expand_unop_direct (word_mode, clz_optab, sublo, 0, true);
> + if (unoptab == ffs_optab)
> + {
> + convert_move (result, const0_rtx, true);
> + emit_cmp_and_jump_insns (sublo, CONST0_RTX (word_mode), EQ, 0,
> + word_mode, true, after_label);
> + }
> +
> + if (optab_handler (unoptab, word_mode) != CODE_FOR_nothing)
> + temp = expand_unop_direct (word_mode, unoptab, sublo, NULL_RTX, true);
> + else
> + {
> + gcc_assert (unoptab == ffs_optab);
> + temp = expand_unop_direct (word_mode, ctz_optab, sublo, NULL_RTX, true);
> + addend = 1;
> + }
> +
> if (!temp)
> goto fail;
> +
> temp = expand_binop (word_mode, add_optab, temp,
> - gen_int_mode (GET_MODE_BITSIZE (word_mode), word_mode),
> + gen_int_mode (GET_MODE_BITSIZE (word_mode) + addend,
> + word_mode),
> result, true, OPTAB_DIRECT);
> if (!temp)
> goto fail;
> @@ -2759,7 +2791,7 @@ expand_doubleword_clz (scalar_int_mode m
> seq = get_insns ();
> end_sequence ();
>
> - add_equal_note (seq, target, CLZ, xop0, NULL_RTX, mode);
> + add_equal_note (seq, target, optab_to_code (unoptab), xop0, NULL_RTX, mode);
> emit_insn (seq);
> return target;
>
> @@ -3252,7 +3284,8 @@ expand_unop (machine_mode mode, optab un
> if (GET_MODE_SIZE (int_mode) == 2 * UNITS_PER_WORD
> && optab_handler (unoptab, word_mode) != CODE_FOR_nothing)
> {
> - temp = expand_doubleword_clz (int_mode, op0, target);
> + temp = expand_doubleword_clz_ctz_ffs (int_mode, op0, target,
> + unoptab);
> if (temp)
> return temp;
> }
> @@ -3499,6 +3532,18 @@ expand_unop (machine_mode mode, optab un
> if (temp)
> return temp;
> }
> +
> + if ((unoptab == ctz_optab || unoptab == ffs_optab)
> + && optimize_insn_for_speed_p ()
> + && is_a <scalar_int_mode> (mode, &int_mode)
> + && GET_MODE_SIZE (int_mode) == 2 * UNITS_PER_WORD
> + && (optab_handler (unoptab, word_mode) != CODE_FOR_nothing
> + || optab_handler (ctz_optab, word_mode) != CODE_FOR_nothing))
> + {
> + temp = expand_doubleword_clz_ctz_ffs (int_mode, op0, target, unoptab);
> + if (temp)
> + return temp;
> + }
>
> try_libcall:
> /* Now try a library call in this mode. */
> --- gcc/testsuite/gcc.target/i386/ctzll-1.c.jj 2023-06-07 14:38:58.749648164 +0200
> +++ gcc/testsuite/gcc.target/i386/ctzll-1.c 2023-06-07 14:41:22.676659439 +0200
> @@ -0,0 +1,9 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2" } */
> +/* { dg-final { scan-assembler-not "__ctzdi2" } } */
> +
> +int
> +foo (unsigned long long x)
> +{
> + return __builtin_ctzll (x);
> +}
> --- gcc/testsuite/gcc.target/i386/ffsll-1.c.jj 2023-06-07 14:40:00.859789953 +0200
> +++ gcc/testsuite/gcc.target/i386/ffsll-1.c 2023-06-07 14:41:15.104764068 +0200
> @@ -0,0 +1,9 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2" } */
> +/* { dg-final { scan-assembler-not "__ffsdi2" } } */
> +
> +int
> +foo (unsigned long long x)
> +{
> + return __builtin_ffsll (x);
> +}
>
> Jakub
>
prev parent reply other threads:[~2023-06-08 5:55 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-06-07 16:58 Jakub Jelinek
2023-06-08 5:55 ` Richard Biener [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CB1567FC-7FFE-4800-9A87-8FF69325EE12@suse.de \
--to=rguenther@suse.de \
--cc=gcc-patches@gcc.gnu.org \
--cc=jakub@redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).