From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.220.28]) by sourceware.org (Postfix) with ESMTPS id 704843858D33 for ; Mon, 20 Nov 2023 07:54:55 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 704843858D33 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 704843858D33 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=195.135.220.28 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700466897; cv=none; b=nuDgZl3J5+ouJWECGfr/uDyTTojt4WZKD7FTMyQQDQeUaROb76e3RUDo+3cthWb8pPAOUIyf4I0VySN1FgTQcDh0A9OWwQhy/RdwNrXCgpmSn5c7opL4762GalrOAS9uTCf8fpqfPwCGMfjEGzD2muW5HrokaB0IuBQ6b64PkdM= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700466897; c=relaxed/simple; bh=w0DdiIre04YfhfArgKHGrFjRL8eZJdvylX+M7qNPWFc=; h=DKIM-Signature:DKIM-Signature:Date:From:To:Subject:Message-ID: MIME-Version; b=MfZLktUgri+pME0MwUu15krpsyEVOuYIxlyom8Q5pxDSd2tpRCTTugdSXN2qzwnfVTnOIo6/tKB0VussC/x9nppzKiXEjfd0OYSqB6TBSkpi6bVfpoRyWZX6mHhm3an6CKEnWvblJUdNousRXAk9tw+8f9mgBdih7a/is4eq4r8= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out1.suse.de (Postfix) with ESMTP id 4C46E218BB; Mon, 20 Nov 2023 07:54:54 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1700466894; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=+O4H436+ErZ9ttRysei/k+aiZXXuyaCQfQqGOpIEiAI=; b=w6Yq6VcHtnWQEvjwCSZb7FqpMebMeGIVBLUBKhMy2d0DOY+SgIOSgyLP1RbFZo3nq3bNIa KS1+h3eId+cv4cj73j8qfdPdzZ4yeEz23cdBOwwbVO++kctFUijr0BqTQ8PRO7uwcgpfOF ZnkP0hROE1Wum7AfAITyzb297zfzed4= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1700466894; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=+O4H436+ErZ9ttRysei/k+aiZXXuyaCQfQqGOpIEiAI=; b=yLsTaUnvsRQAJ2Rq7GyeDQ75En0hQW6RyXk0M3SBFGv5zjAnndd47dRwlcwfJqRe8IscBB g5gUuGeKnB2iBmCw== Received: from wotan.suse.de (wotan.suse.de [10.160.0.1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id 38D2A2C569; Mon, 20 Nov 2023 07:54:54 +0000 (UTC) Date: Mon, 20 Nov 2023 07:54:54 +0000 (UTC) From: Richard Biener To: Jakub Jelinek cc: gcc-patches@gcc.gnu.org Subject: Re: [PATCH] tree-ssa-math-opts: popcount (X) == 1 to (X ^ (X - 1)) > (X - 1) optimization [PR90693] In-Reply-To: Message-ID: References: User-Agent: Alpine 2.22 (LSU 394 2020-01-19) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-Spamd-Bar: +++++++++++++ Authentication-Results: smtp-out1.suse.de; dkim=none; dmarc=none; spf=softfail (smtp-out1.suse.de: 149.44.160.134 is neither permitted nor denied by domain of rguenther@suse.de) smtp.mailfrom=rguenther@suse.de X-Rspamd-Server: rspamd1 X-Spamd-Result: default: False [13.99 / 50.00]; ARC_NA(0.00)[]; FROM_HAS_DN(0.00)[]; TO_DN_SOME(0.00)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; NEURAL_SPAM_SHORT(3.00)[1.000]; MIME_GOOD(-0.10)[text/plain]; DMARC_NA(1.20)[suse.de]; R_SPF_SOFTFAIL(4.60)[~all:c]; RWL_MAILSPIKE_GOOD(-1.00)[149.44.160.134:from]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; MX_GOOD(-0.01)[]; RCPT_COUNT_TWO(0.00)[2]; VIOLATED_DIRECT_SPF(3.50)[]; NEURAL_SPAM_LONG(3.50)[1.000]; FUZZY_BLOCKED(0.00)[rspamd.com]; RCVD_NO_TLS_LAST(0.10)[]; FROM_EQ_ENVFROM(0.00)[]; R_DKIM_NA(2.20)[]; MIME_TRACE(0.00)[0:+]; RCVD_COUNT_TWO(0.00)[2]; BAYES_HAM(-3.00)[100.00%] X-Spam-Score: 13.99 X-Rspamd-Queue-Id: 4C46E218BB X-Spam-Status: No, score=-5.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,KAM_SHORT,SPF_HELO_NONE,SPF_PASS,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: On Fri, 17 Nov 2023, Jakub Jelinek wrote: > Hi! > > Per the earlier discussions on this PR, the following patch folds > popcount (x) == 1 (and != 1) into (x ^ (x - 1)) > x - 1 (or <=) > if the corresponding popcount optab isn't implemented (I think any > double-word popcount or call will be necessarily slower than the > above cheap 3 op check and even for -Os larger or same size). > > I've noticed e.g. C++ aligned new starts with std::has_single_bit > which does popcount (x) == 1. > > As a follow-up, I'm considering changing in this routine the popcount > call to IFN_POPCOUNT with 2 arguments and during expansion test costs. > > Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? Classically this would have been an RTL expansion alternative, given we want to do less of those the next place would have been the ISEL pass. Any particular reason you chose widening-mul for this (guess that pass just has a bad name and it's the effective "optimize" ISEL pass we have). Richard. > 2023-11-17 Jakub Jelinek > > PR tree-optimization/90693 > * tree-ssa-math-opts.cc (match_single_bit_test): New function. > (math_opts_dom_walker::after_dom_children): Call it for EQ_EXPR > and NE_EXPR assignments and GIMPLE_CONDs. > > * gcc.target/i386/pr90693.c: New test. > > --- gcc/tree-ssa-math-opts.cc.jj 2023-11-13 15:51:02.920562303 +0100 > +++ gcc/tree-ssa-math-opts.cc 2023-11-17 11:37:02.255905475 +0100 > @@ -5154,6 +5154,72 @@ match_uaddc_usubc (gimple_stmt_iterator > return true; > } > > +/* Replace .POPCOUNT (x) == 1 or .POPCOUNT (x) != 1 with > + (x & (x - 1)) > x - 1 or (x & (x - 1)) <= x - 1 if .POPCOUNT > + isn't a direct optab. */ > + > +static void > +match_single_bit_test (gimple_stmt_iterator *gsi, gimple *stmt) > +{ > + tree clhs, crhs; > + enum tree_code code; > + if (gimple_code (stmt) == GIMPLE_COND) > + { > + clhs = gimple_cond_lhs (stmt); > + crhs = gimple_cond_rhs (stmt); > + code = gimple_cond_code (stmt); > + } > + else > + { > + clhs = gimple_assign_rhs1 (stmt); > + crhs = gimple_assign_rhs2 (stmt); > + code = gimple_assign_rhs_code (stmt); > + } > + if (code != EQ_EXPR && code != NE_EXPR) > + return; > + if (TREE_CODE (clhs) != SSA_NAME || !integer_onep (crhs)) > + return; > + gimple *call = SSA_NAME_DEF_STMT (clhs); > + combined_fn cfn = gimple_call_combined_fn (call); > + switch (cfn) > + { > + CASE_CFN_POPCOUNT: > + break; > + default: > + return; > + } > + if (!has_single_use (clhs)) > + return; > + tree arg = gimple_call_arg (call, 0); > + tree type = TREE_TYPE (arg); > + if (!INTEGRAL_TYPE_P (type)) > + return; > + if (direct_internal_fn_supported_p (IFN_POPCOUNT, type, OPTIMIZE_FOR_BOTH)) > + return; > + tree argm1 = make_ssa_name (type); > + gimple *g = gimple_build_assign (argm1, PLUS_EXPR, arg, > + build_int_cst (type, -1)); > + gsi_insert_before (gsi, g, GSI_SAME_STMT); > + g = gimple_build_assign (make_ssa_name (type), BIT_XOR_EXPR, arg, argm1); > + gsi_insert_before (gsi, g, GSI_SAME_STMT); > + if (gcond *cond = dyn_cast (stmt)) > + { > + gimple_cond_set_lhs (cond, gimple_assign_lhs (g)); > + gimple_cond_set_rhs (cond, argm1); > + gimple_cond_set_code (cond, code == EQ_EXPR ? GT_EXPR : LE_EXPR); > + } > + else > + { > + gimple_assign_set_rhs1 (stmt, gimple_assign_lhs (g)); > + gimple_assign_set_rhs2 (stmt, argm1); > + gimple_assign_set_rhs_code (stmt, code == EQ_EXPR ? GT_EXPR : LE_EXPR); > + } > + update_stmt (stmt); > + gimple_stmt_iterator gsi2 = gsi_for_stmt (call); > + gsi_remove (&gsi2, true); > + release_defs (call); > +} > + > /* Return true if target has support for divmod. */ > > static bool > @@ -5807,6 +5873,11 @@ math_opts_dom_walker::after_dom_children > match_uaddc_usubc (&gsi, stmt, code); > break; > > + case EQ_EXPR: > + case NE_EXPR: > + match_single_bit_test (&gsi, stmt); > + break; > + > default:; > } > } > @@ -5872,7 +5943,10 @@ math_opts_dom_walker::after_dom_children > } > } > else if (gimple_code (stmt) == GIMPLE_COND) > - optimize_spaceship (as_a (stmt)); > + { > + match_single_bit_test (&gsi, stmt); > + optimize_spaceship (as_a (stmt)); > + } > gsi_next (&gsi); > } > if (fma_state.m_deferring_p > --- gcc/testsuite/gcc.target/i386/pr90693.c.jj 2023-11-16 19:31:43.383587048 +0100 > +++ gcc/testsuite/gcc.target/i386/pr90693.c 2023-11-16 19:33:23.676177086 +0100 > @@ -0,0 +1,29 @@ > +/* PR tree-optimization/90693 */ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -mno-abm -mno-popcnt -fdump-tree-optimized" } */ > +/* { dg-final { scan-tree-dump-not "POPCOUNT \\\(" "optimized" } } */ > +/* { dg-final { scan-tree-dump-not "__builtin_popcount(ll)? \\\(" "optimized" } } */ > + > +int > +foo (unsigned int x) > +{ > + return __builtin_popcount (x) == 1; > +} > + > +int > +bar (unsigned int x) > +{ > + return (x ^ (x - 1)) > x - 1; > +} > + > +int > +baz (unsigned long long x) > +{ > + return __builtin_popcountll (x) == 1; > +} > + > +int > +qux (unsigned long long x) > +{ > + return (x ^ (x - 1)) > x - 1; > +} > > Jakub > > -- Richard Biener SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg, Germany; GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)