From patchwork Fri Nov 17 14:01:04 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 80129 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2228F3858287 for ; Fri, 17 Nov 2023 14:01:27 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org 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 16AA63858D1E for ; Fri, 17 Nov 2023 14:01:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 16AA63858D1E Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 16AA63858D1E Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700229672; cv=none; b=LE0hE6py1SpNsUTV7pfBTIzfI+SiB+qvW3Df3U22B3SEQGDnHwCEJ/Ck5ufscbv8X583NqP0LAdmXXLJUyeOFNPURDDZoX3SQKsX4fAF1dcFGuqJ8lczibcgPPvmRsa1h3qaCRJ79k5qHpjDVwIX44Q5p5gNRpGCvqnz3YZCSyg= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700229672; c=relaxed/simple; bh=Gn7IY5KtQaCq+DRfjXLLAIOfZRxdXZN4yJtdbaLi71o=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:MIME-Version; b=Ea+2NW4c5l9ec1jikoBp2/gB1nuwx9Pw1cmQ/lU5rH0rVMIWzvPxr+AIW86xm73irbE608vzRTE8Z/VJvJqxVhOsZ8lI/RjlpQOwYZ+tUdEMwSqe9+wQSgiFrJc1ktST/kid4pMunBCZXpfDQuMtkedWot9c2aN/VkQ7R1iMkoo= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1700229670; 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=ziD9NFfR0oNr5Trii0qxQB/OrzsD4ijs4+U388nIFWA=; b=ByW53O9Rm0KUNHcJH66r/lBhN3u5Gc266XozHMqFCbLwI8M/+vBHDt6iKALKnjmWvLgbkO vUwZBO6HQMc/rIvqYbHtR7ngZklXQaXoltgChf2ukSmTsuNCAOThfMIIUDCfHphpok2vd7 1DhcoNtq1PHKKI/VYSYhI5vOJZxtD8w= Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-66-g03yPgDNPVGc2-PH44rMQQ-1; Fri, 17 Nov 2023 09:01:08 -0500 X-MC-Unique: g03yPgDNPVGc2-PH44rMQQ-1 Received: from smtp.corp.redhat.com (int-mx09.intmail.prod.int.rdu2.redhat.com [10.11.54.9]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id 32E34811002; Fri, 17 Nov 2023 14:01:08 +0000 (UTC) Received: from tucnak.zalov.cz (unknown [10.39.194.53]) by smtp.corp.redhat.com (Postfix) with ESMTPS id EAE09492BE0; Fri, 17 Nov 2023 14:01:07 +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 3AHE15LH3135205 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Fri, 17 Nov 2023 15:01:05 +0100 Received: (from jakub@localhost) by tucnak.zalov.cz (8.17.1/8.17.1/Submit) id 3AHE14eJ3135202; Fri, 17 Nov 2023 15:01:04 +0100 Date: Fri, 17 Nov 2023 15:01:04 +0100 From: Jakub Jelinek To: Richard Biener Cc: gcc-patches@gcc.gnu.org Subject: [PATCH] tree-ssa-math-opts: popcount (X) == 1 to (X ^ (X - 1)) > (X - 1) optimization [PR90693] Message-ID: MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.11.54.9 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com 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, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, 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 X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: Jakub Jelinek Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org 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? 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. Jakub --- 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; +}