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: 166182 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:9910:0:b0:403:3b70:6f57 with SMTP id i16csp545773vqn; Fri, 17 Nov 2023 06:01:35 -0800 (PST) X-Google-Smtp-Source: AGHT+IEJMelqI6LppmkiLtvwnqKICQb7ARz59eRCJuKMA54B2sF+XuMTiWqxgG54f3uB0+d3dfHU X-Received: by 2002:ac8:5b84:0:b0:41e:1f5d:7009 with SMTP id a4-20020ac85b84000000b0041e1f5d7009mr11784344qta.25.1700229694800; Fri, 17 Nov 2023 06:01:34 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1700229694; cv=pass; d=google.com; s=arc-20160816; b=AsIMXRW6i19rFDr3FGVdtcsesvcApotNgK3pStS1wfaqcnoDSSYxQC8vY5shogDrfS M2p7VwUHZIZis1wKI6nRpKUjw9slD3k9+Wu0I+DPMYtjUoVIfO/oSEBgUZhh/SsCMUBy 6sCP+EWO192bt7YjG4/nUCkSqUQ0rMrLg2KPc9AL6nLLuJ5Zg0KQax2eKIdb0tGt2o/k 7OfSpXouDBZBK7A6r9HzsVfdu7Lt9/GU0eGoXy5TKv/ZpteTPTydsueKpYd1ZRbzcf2r J5ydIAPWEA9rhu4y6nr44emnzrH56zFpZrElG44a41+XmA/BzXHnpNL7xr+fo+e05TqZ NgrA== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=errors-to:reply-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-disposition :mime-version:message-id:subject:cc:to:from:date:dkim-signature :arc-filter:dmarc-filter:delivered-to; bh=ziD9NFfR0oNr5Trii0qxQB/OrzsD4ijs4+U388nIFWA=; fh=FCjeRajqaQYHMkQtfIia8KT5yBac53mYOLLyJhYG/AY=; b=ixeFhym8lInEvM5n4uh1ObziSvm70XHSMtGjXue/P6uRTHwq2+fzV3QEdv5pyq2Kk7 PoZm2birAZDvW3eiHid9p00qSpDxOsTLyaD9YDyb+iHpbt/k2YqRdhY3XIPTKi3GN+ea WvYxetnu393WjNcELH40KhQsPSqs6aWexG/+gAzoPqjph/qSOz3eG1O1NFA3u1JYieKo HDpk5iI6MIwknhf9V18ZX9vm7rt0HwjCcP2TEwftYZANOZS5EiwXpeveUO8NA+yjas2n ehANMT3QnnDkyzkga18a/0CWyNyM/fzUJzZduvNLxvgDjaUA7hjU7iCBBAbQHQFlOF8m iulA== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=ByW53O9R; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=redhat.com Received: from server2.sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id k2-20020ac85fc2000000b00417afb934casi1705718qta.683.2023.11.17.06.01.34 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 17 Nov 2023 06:01:34 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=ByW53O9R; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=redhat.com Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 8F393385841F for ; Fri, 17 Nov 2023 14:01:34 +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+ouuuleilei=gmail.com@gcc.gnu.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1782820052428663324 X-GMAIL-MSGID: 1782820052428663324 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; +}