From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 0E8FA3858C54 for ; Wed, 7 Jun 2023 16:58:59 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 0E8FA3858C54 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1686157138; h=from:from:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=EKyF5Gm28qyvZvud4Z6qIClGVEHFBseibvW0UIwD9uM=; b=QZ3oeGH5OYBCoPUHgZ9ruE3F9mBxo94a9/HHIqhGnMkTz2odMO4LPu1Od/kvSraW5bxuVK fgSwC3/rNB70U+sCWUwAsYJ8ZUpGvB9TqplLTHidZJ6U1xpeHgZ+0sHQbDdodJUYefNe8m fpWNfs2+hsQRKxv9ZcH7S4mwciU+PLs= Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-284-smUlTjAhNwKD_0BNIRxnVg-1; Wed, 07 Jun 2023 12:58:57 -0400 X-MC-Unique: smUlTjAhNwKD_0BNIRxnVg-1 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.rdu2.redhat.com [10.11.54.6]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id DEFC6858EEB; Wed, 7 Jun 2023 16:58:56 +0000 (UTC) Received: from tucnak.zalov.cz (unknown [10.39.194.30]) by smtp.corp.redhat.com (Postfix) with ESMTPS id A1B1C2166B25; Wed, 7 Jun 2023 16:58:56 +0000 (UTC) Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.17.1/8.17.1) with ESMTPS id 357GwsDQ3600272 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Wed, 7 Jun 2023 18:58:54 +0200 Received: (from jakub@localhost) by tucnak.zalov.cz (8.17.1/8.17.1/Submit) id 357Gwr6C3600271; Wed, 7 Jun 2023 18:58:53 +0200 Date: Wed, 7 Jun 2023 18:58:53 +0200 From: Jakub Jelinek To: Richard Biener Cc: gcc-patches@gcc.gnu.org Subject: [PATCH] optabs: Implement double-word ctz and ffs expansion Message-ID: Reply-To: Jakub Jelinek MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.1 on 10.11.54.6 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-Spam-Status: No, score=-3.4 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,KAM_SHORT,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_NONE,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: 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? 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 * 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 (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