From patchwork Thu Dec 22 17:42:16 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrew Carlotti X-Patchwork-Id: 35889 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:e747:0:0:0:0:0 with SMTP id c7csp80785wrn; Thu, 22 Dec 2022 09:43:29 -0800 (PST) X-Google-Smtp-Source: AMrXdXtHQwNTkIMrEdyO9aB8ptpda74dg5+I3b71BvZj0rCGGO2MQHpMLVzSyfuMauUpUb4o+gvw X-Received: by 2002:a17:906:c250:b0:79e:4880:dd85 with SMTP id bl16-20020a170906c25000b0079e4880dd85mr4515352ejb.47.1671731009026; Thu, 22 Dec 2022 09:43:29 -0800 (PST) Received: from sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id hv16-20020a17090760d000b0083b6e04f379si957671ejc.492.2022.12.22.09.43.28 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 22 Dec 2022 09:43:29 -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=@gcc.gnu.org header.s=default header.b=cTipAoUV; arc=fail (signature failed); 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=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 377273858298 for ; Thu, 22 Dec 2022 17:43:24 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 377273858298 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1671731004; bh=M4kStG8V+OjaFT6366rA4yqnKYZ8hf1SlZcT9AJfKng=; h=Date:To:Cc:Subject:References:In-Reply-To:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:List-Subscribe: From:Reply-To:From; b=cTipAoUVCpqP8WCx1IRhWqWYbPvdt1vwjCHYm659QktmO2QVYs59g+8aOYEN/Gt1Y ZjcT5FLfZn3oQFRsSkdGOmkeccN69Q4QAOnKQubgo6MKmksHFBqDzB5Fwk6DOVkEHG xLfzr2MPmMW/oTDdqqL8jFaVWfKqQfQKqVpz/MfI= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from EUR04-HE1-obe.outbound.protection.outlook.com (mail-he1eur04on2040.outbound.protection.outlook.com [40.107.7.40]) by sourceware.org (Postfix) with ESMTPS id 90B7C3857C45 for ; Thu, 22 Dec 2022 17:42:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 90B7C3857C45 Received: from AM6P191CA0076.EURP191.PROD.OUTLOOK.COM (2603:10a6:209:8a::17) by VI1PR08MB10299.eurprd08.prod.outlook.com (2603:10a6:800:1bf::12) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5944.6; Thu, 22 Dec 2022 17:42:29 +0000 Received: from VI1EUR03FT012.eop-EUR03.prod.protection.outlook.com (2603:10a6:209:8a:cafe::a8) by AM6P191CA0076.outlook.office365.com (2603:10a6:209:8a::17) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5944.12 via Frontend Transport; Thu, 22 Dec 2022 17:42:28 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 63.35.35.123) smtp.mailfrom=arm.com; dkim=pass (signature was verified) header.d=armh.onmicrosoft.com;dmarc=pass action=none header.from=arm.com; Received-SPF: Pass (protection.outlook.com: domain of arm.com designates 63.35.35.123 as permitted sender) receiver=protection.outlook.com; client-ip=63.35.35.123; helo=64aa7808-outbound-1.mta.getcheckrecipient.com; pr=C Received: from 64aa7808-outbound-1.mta.getcheckrecipient.com (63.35.35.123) by VI1EUR03FT012.mail.protection.outlook.com (100.127.145.22) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5944.12 via Frontend Transport; Thu, 22 Dec 2022 17:42:28 +0000 Received: ("Tessian outbound 8038f0863a52:v132"); Thu, 22 Dec 2022 17:42:28 +0000 X-CheckRecipientChecked: true X-CR-MTA-CID: 2cec0a5c03a3b7c4 X-CR-MTA-TID: 64aa7808 Received: from aea7d99a4ce9.1 by 64aa7808-outbound-1.mta.getcheckrecipient.com id E66658EE-F2FC-474C-8F84-6D615C1EE090.1; Thu, 22 Dec 2022 17:42:21 +0000 Received: from EUR02-VI1-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id aea7d99a4ce9.1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Thu, 22 Dec 2022 17:42:21 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=dPYOAgSd7sJ2g/l25aKq5hTAMs36WdFjtO9iacKWa4v5Uz3DQIXXkJhmEsKN9Ejod6X+qMIHMNwVERcac8Q5HYWSRdbI4tXDqrFb5J0DNA8xaPSkbBH3T1m/yBzgjmiXcIsHoTJIKmqvLUm5XZRyi9CKUmWWSeQEa6OF8s2OdUQqzCLisICNKgpnbCW69ftWM27C8FjoDVV2x+QsrmcjI2x3N9q+k94ZN/51ZYL32WVcFmFndTWAUaBMhpK45sYQcKNQehhYOFRo5GLWS/JSVqHoAiZpc/U6Gqr/Qu8JPM1ezJPQhObCjEyHjc4l4ZFzd2YP+pPjHeAQhCBiqEl1vQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=M4kStG8V+OjaFT6366rA4yqnKYZ8hf1SlZcT9AJfKng=; b=HOuvoyXqPAcipbDSXTtR/DRvrbXhWwM7CIgxpvR9VGbYTPI5ysgnzTlgTlMfyGqn8CPE18Ik6IrIupGd6+eVmpXzv7FxiVak2OkOCu06fE10kvw8rFecwWD8tI2g8wROiQqxdwRYiHkeJUyrgO6XWOVcS2n0iIJeNBF5xNAMaTKj+dfub9ldv6zB9hr60x16FqWRKJAA8S5pT0J3TqMVabbLLIDrNhQc9FmrClKfVrH/8iR2uhb56lzUGHI82ixesz7j8Z/XZejJrulCE2aFTK/p4+fRNFwcOw+6n7zYJ0RKBgT/Y7VeB5LLxcEorGBMVnt+1xs1ZRQVpAxKt/YwpA== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=arm.com; dmarc=pass action=none header.from=arm.com; dkim=pass header.d=arm.com; arc=none Authentication-Results-Original: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=arm.com; Received: from AS8PR08MB6678.eurprd08.prod.outlook.com (2603:10a6:20b:398::8) by AS8PR08MB9954.eurprd08.prod.outlook.com (2603:10a6:20b:638::11) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5944.6; Thu, 22 Dec 2022 17:42:19 +0000 Received: from AS8PR08MB6678.eurprd08.prod.outlook.com ([fe80::8256:29ca:bcd8:b754]) by AS8PR08MB6678.eurprd08.prod.outlook.com ([fe80::8256:29ca:bcd8:b754%5]) with mapi id 15.20.5944.011; Thu, 22 Dec 2022 17:42:19 +0000 Date: Thu, 22 Dec 2022 17:42:16 +0000 To: Richard Biener Cc: gcc-patches@gcc.gnu.org Subject: [PATCH 5/8 v2] middle-end: Add cltz_complement idiom recognition Message-ID: References: Content-Disposition: inline In-Reply-To: X-ClientProxiedBy: LO4P123CA0094.GBRP123.PROD.OUTLOOK.COM (2603:10a6:600:191::9) To AS8PR08MB6678.eurprd08.prod.outlook.com (2603:10a6:20b:398::8) MIME-Version: 1.0 X-MS-TrafficTypeDiagnostic: AS8PR08MB6678:EE_|AS8PR08MB9954:EE_|VI1EUR03FT012:EE_|VI1PR08MB10299:EE_ X-MS-Office365-Filtering-Correlation-Id: 0c5fcc36-774e-438a-c159-08dae443e536 x-checkrecipientrouted: true NoDisclaimer: true X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam-Untrusted: BCL:0; X-Microsoft-Antispam-Message-Info-Original: 8KKHJmN9m0rBk60DSXvpL3zq/SL9APPBr55h9Nsc7blh57J9rOH8XiZ8N3n8LBfCApxuAxZjNgEOSWobJSZzgCkbTuKjhWKrdjmUGK9yArgjBP1tdVmsZ1P9z9+4hDCrZheBTT7xQEWv+sc391sZn/Jzud8654c6kHEz6AOgKaMjavXeAIwc0/Gu/BO2rG5O/RDULSwzYUMI0vHJnt3hduPpEWyOC7Wl08bGHwPt7Wt4dDy38HmyFGNgGLdqkEjGE2ky09SZ2a/63Jj8k55xQBj/j8HAhL/unx4fOtGGkSyMKviytvSUej0covUSAIfF9wR2XpJLXG4n1jIwsyUp+PTXc0a2jhHpGr7DSGD6EvBXEhwhlKBzuzCr2iHw1SSHYWS7+A/mzbgvWhupFZY1RZebch5EQnjJ+pNXRzNp9XhYukfovY6XKjrTKPNmubZMl75Rz66gInyui9tBfTBdLLn+El0YIkEfX0iI53T4NljCNt5ApHiIJi/CKU/ycouTbzqHOZ8OFq9WyAbqN0ObqoxoFk6rU5Qxc/TMDiJzmRsFCNKWY8jruootpTGJ83ybhTcioRSANaQP60xZLu9NewZT4ZCrV6hPkt1jIKGWTytW+EJOL6wv+ZdnHO1SAnFk36vluQK72FnsQ4sJhAavoNb++AUt5j2rx+7rMuXft8DPkjSvuxOQddUS3ZJXzpn0DtgH5un8bdGeVzIqEtXJEQ== X-Forefront-Antispam-Report-Untrusted: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:AS8PR08MB6678.eurprd08.prod.outlook.com; PTR:; CAT:NONE; SFS:(13230022)(4636009)(376002)(346002)(366004)(39860400002)(396003)(136003)(451199015)(8676002)(86362001)(4326008)(66476007)(66556008)(66946007)(6512007)(6486002)(478600001)(186003)(6666004)(6506007)(6916009)(316002)(26005)(38100700002)(83380400001)(2906002)(41300700001)(5660300002)(84970400001)(8936002)(44832011)(30864003); DIR:OUT; SFP:1101; X-MS-Exchange-Transport-CrossTenantHeadersStamped: AS8PR08MB9954 Original-Authentication-Results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=arm.com; X-EOPAttributedMessage: 0 X-MS-Exchange-Transport-CrossTenantHeadersStripped: VI1EUR03FT012.eop-EUR03.prod.protection.outlook.com X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id-Prvs: 640db51a-59f7-422a-c01f-08dae443df83 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: 5jDzvBi/0/JKXGHhihaHDiSB4/U+DqAtaqpxgNzxZIFc6+TDmVLsKwgKzPOYg4oiuLqQiITIcDKu9eFRjnJK9gd8bOePRMFJN/0e4wN1Xjpp/cx3kvO/UFo5pJgQAmmscvszt/OL/tVhYRKuSc14T3lzh9ye0YShWeBUY4l9cL5cK3udRxzaVNxM0uTYxPY77rRLL+R3935MQ1SP6t9DUNuDO8ut8b1mXPU6h5QOciwns4C6JqgsZ8Bb9NcGHoxp6sqea4f22bo5GytiQbPvyQIvOyLkU6TlXClVVRwTvzAJg1M4M0nvR/ECxUcfzkn6AYxsAD6FZk/a4L42X+BGiH+yDvo7UimStOwx1eBy+9wVzgkyyohUWZJqbbho5KpKvQtCxVl4ngcfC4si+hIG/pFpV5if7CpvkMasJyCsXtOAxjl7JSvogJg4DUynucdq4eZOHFImHY7LgRm/MlmEgEg30EMVWpVZtlDMPGmm+LqhHpBfb8HQO7KhmDS/wEtIKwPxPHq55fWvH+j1Uy1NQO7DRT0SQjbp7iucvE6hGf5+fvhPpSOUx911DMpoZm3C7+5mx5j6Cujbo91QWer/Yh1b3pHm6fUn3yIk9du7kCh7KeaTb5a0P920QAZ9lmisFxJfLc+xBghmSAdfUDNv3BBNXapnhytXV+HKyOwleVqgH1WbUPBUEw1Y4WUAwbvZBB4eoWMHL7TQCKTPimod2s2TooW1A6dHb8oXg8E/LvFUAoJpMkQhYG8mCXpmK9N2UU0VOWsYpV+dlWWG2MfsSw== X-Forefront-Antispam-Report: CIP:63.35.35.123; CTRY:IE; LANG:en; SCL:1; SRV:; IPV:CAL; SFV:NSPM; H:64aa7808-outbound-1.mta.getcheckrecipient.com; PTR:ec2-63-35-35-123.eu-west-1.compute.amazonaws.com; CAT:NONE; SFS:(13230022)(4636009)(136003)(396003)(346002)(39860400002)(376002)(451199015)(36840700001)(40470700004)(46966006)(83380400001)(8676002)(316002)(41300700001)(44832011)(5660300002)(4326008)(356005)(336012)(70586007)(81166007)(70206006)(40460700003)(47076005)(82740400003)(40480700001)(6486002)(36860700001)(30864003)(86362001)(6512007)(186003)(478600001)(82310400005)(6506007)(26005)(6666004)(84970400001)(6862004)(8936002)(2906002); DIR:OUT; SFP:1101; X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 22 Dec 2022 17:42:28.4296 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 0c5fcc36-774e-438a-c159-08dae443e536 X-MS-Exchange-CrossTenant-Id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=f34e5979-57d9-4aaa-ad4d-b122a662184d; Ip=[63.35.35.123]; Helo=[64aa7808-outbound-1.mta.getcheckrecipient.com] X-MS-Exchange-CrossTenant-AuthSource: VI1EUR03FT012.eop-EUR03.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR08MB10299 X-Spam-Status: No, score=-13.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, FORGED_SPF_HELO, GIT_PATCH_0, KAM_DMARC_NONE, KAM_LOTSOFHASH, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_PASS, SPF_NONE, TXREP, UNPARSEABLE_RELAY 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.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Andrew Carlotti via Gcc-patches From: Andrew Carlotti Reply-To: Andrew Carlotti Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1749226959279612589?= X-GMAIL-MSGID: =?utf-8?q?1752937014107407709?= On Thu, Nov 24, 2022 at 11:41:31AM +0100, Richard Biener wrote: > Note we do have CTZ and CLZ > optabs and internal functions - in case there's a HImode CLZ this > could be elided. More general you can avoid using the __builtin_ > functions with their fixed types in favor of using IFN_C[TL]Z which > are type agnostic (but require optab support - you should be able > to check this via direct_internal_fn_supported_p). IFN support added. I've also renamed the defined_at_zero parameter to define_at_zero, since this is a request for the expression to define it, rather than a guarantee that it is already defined. New patch below, bootstrapped and regression tested on aarch64-unknown-linux-gnu and x86_64-pc-linux-gnu - ok to merge? --- This recognises patterns of the form: while (n) { n >>= 1 } This patch results in improved (but still suboptimal) codegen: foo (unsigned int b) { int c = 0; while (b) { b >>= 1; c++; } return c; } foo: .LFB11: .cfi_startproc cbz w0, .L3 clz w1, w0 tst x0, 1 mov w0, 32 sub w0, w0, w1 csel w0, w0, wzr, ne ret The conditional is unnecessary. phiopt could recognise a redundant csel (using cond_removal_in_builtin_zero_pattern) when one of the inputs is a clz call, but it cannot recognise the redunancy when the input is (e.g.) (32 - clz). I could perhaps extend this function to recognise this pattern in a later patch, if this is a good place to recognise more patterns. gcc/ChangeLog: PR tree-optimization/94793 * tree-scalar-evolution.cc (expression_expensive_p): Add checks for c[lt]z optabs. * tree-ssa-loop-niter.cc (build_cltz_expr): New. (number_of_iterations_cltz_complement): New. (number_of_iterations_bitcount): Add call to the above. gcc/testsuite/ChangeLog: * lib/target-supports.exp (check_effective_target_clz) (check_effective_target_clzl, check_effective_target_clzll) (check_effective_target_ctz, check_effective_target_clzl) (check_effective_target_ctzll): New. * gcc.dg/tree-ssa/cltz-complement-max.c: New test. * gcc.dg/tree-ssa/clz-complement-char.c: New test. * gcc.dg/tree-ssa/clz-complement-int.c: New test. * gcc.dg/tree-ssa/clz-complement-long-long.c: New test. * gcc.dg/tree-ssa/clz-complement-long.c: New test. * gcc.dg/tree-ssa/ctz-complement-char.c: New test. * gcc.dg/tree-ssa/ctz-complement-int.c: New test. * gcc.dg/tree-ssa/ctz-complement-long-long.c: New test. * gcc.dg/tree-ssa/ctz-complement-long.c: New test. --- diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cltz-complement-max.c b/gcc/testsuite/gcc.dg/tree-ssa/cltz-complement-max.c new file mode 100644 index 0000000000000000000000000000000000000000..1a29ca52e42e50822e4e3213b2cb008b766d0318 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/cltz-complement-max.c @@ -0,0 +1,60 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fno-tree-loop-optimize -fdump-tree-optimized" } */ + +#define PREC (__CHAR_BIT__) + +int clz_complement_count1 (unsigned char b) { + int c = 0; + + while (b) { + b >>= 1; + c++; + } + if (c <= PREC) + return 0; + else + return 34567; +} + +int clz_complement_count2 (unsigned char b) { + int c = 0; + + while (b) { + b >>= 1; + c++; + } + if (c <= PREC - 1) + return 0; + else + return 76543; +} + +int ctz_complement_count1 (unsigned char b) { + int c = 0; + + while (b) { + b <<= 1; + c++; + } + if (c <= PREC) + return 0; + else + return 23456; +} + +int ctz_complement_count2 (unsigned char b) { + int c = 0; + + while (b) { + b <<= 1; + c++; + } + if (c <= PREC - 1) + return 0; + else + return 65432; +} +/* { dg-final { scan-tree-dump-times "34567" 0 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "76543" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "23456" 0 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "65432" 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-char.c b/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-char.c new file mode 100644 index 0000000000000000000000000000000000000000..2ebe8fabcaf0ce88f3a6a46e9ba4ba79b7d3672e --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-char.c @@ -0,0 +1,31 @@ +/* { dg-do run } */ +/* { dg-require-effective-target clz } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +#define PREC (__CHAR_BIT__) + +int +__attribute__ ((noinline, noclone)) +foo (unsigned char b) { + int c = 0; + + while (b) { + b >>= 1; + c++; + } + + return c; +} + +int main() +{ + if (foo(0) != 0) + __builtin_abort (); + if (foo(5) != 3) + __builtin_abort (); + if (foo(255) != 8) + __builtin_abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "__builtin_clz|\\.CLZ" 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-int.c b/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-int.c new file mode 100644 index 0000000000000000000000000000000000000000..f2c5c23f6a7d84ecb637c6961698b0fc30d7426b --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-int.c @@ -0,0 +1,31 @@ +/* { dg-do run } */ +/* { dg-require-effective-target clz } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +#define PREC (__CHAR_BIT__ * __SIZEOF_INT__) + +int +__attribute__ ((noinline, noclone)) +foo (unsigned int b) { + int c = 0; + + while (b) { + b >>= 1; + c++; + } + + return c; +} + +int main() +{ + if (foo(0) != 0) + __builtin_abort (); + if (foo(5) != 3) + __builtin_abort (); + if (foo(1 << (PREC - 1)) != PREC) + __builtin_abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "__builtin_clz|\\.CLZ" 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-long-long.c b/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-long-long.c new file mode 100644 index 0000000000000000000000000000000000000000..7f7793f0efac1f0d793e6e99b84988e5cc5221c9 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-long-long.c @@ -0,0 +1,31 @@ +/* { dg-do run } */ +/* { dg-require-effective-target clzll } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +#define PREC (__CHAR_BIT__ * __SIZEOF_LONG_LONG__) + +int +__attribute__ ((noinline, noclone)) +foo (unsigned long long b) { + int c = 0; + + while (b) { + b >>= 1; + c++; + } + + return c; +} + +int main() +{ + if (foo(0) != 0) + __builtin_abort (); + if (foo(5) != 3) + __builtin_abort (); + if (foo(1LL << (PREC - 1)) != PREC) + __builtin_abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "__builtin_clz|\\.CLZ" 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-long.c b/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-long.c new file mode 100644 index 0000000000000000000000000000000000000000..97161bb7a74260bea20e325ebab64acb33a2b696 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/clz-complement-long.c @@ -0,0 +1,31 @@ +/* { dg-do run } */ +/* { dg-require-effective-target clzl } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +#define PREC (__CHAR_BIT__ * __SIZEOF_LONG__) + +int +__attribute__ ((noinline, noclone)) +foo (unsigned long b) { + int c = 0; + + while (b) { + b >>= 1; + c++; + } + + return c; +} + +int main() +{ + if (foo(0) != 0) + __builtin_abort (); + if (foo(5) != 3) + __builtin_abort (); + if (foo(1L << (PREC - 1)) != PREC) + __builtin_abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "__builtin_clz|\\.CLZ" 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-char.c b/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-char.c new file mode 100644 index 0000000000000000000000000000000000000000..b9afe8852d8ffbc7ee9a0760cf04b8f98af293a2 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-char.c @@ -0,0 +1,31 @@ +/* { dg-do run } */ +/* { dg-require-effective-target ctz } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +#define PREC (__CHAR_BIT__) + +int +__attribute__ ((noinline, noclone)) +foo (unsigned char b) { + int c = 0; + + while (b) { + b <<= 1; + c++; + } + + return c; +} + +int main() +{ + if (foo(0) != 0) + __builtin_abort (); + if (foo(96) != PREC - 5) + __builtin_abort (); + if (foo(35) != PREC) + __builtin_abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "__builtin_ctz|\\.CTZ" 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-int.c b/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-int.c new file mode 100644 index 0000000000000000000000000000000000000000..d2702a65daf34db66550d2255395db68a29a4797 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-int.c @@ -0,0 +1,31 @@ +/* { dg-do run } */ +/* { dg-require-effective-target ctz } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +#define PREC (__CHAR_BIT__ * __SIZEOF_INT__) + +int +__attribute__ ((noinline, noclone)) +foo (unsigned int b) { + int c = 0; + + while (b) { + b <<= 1; + c++; + } + + return c; +} + +int main() +{ + if (foo(0) != 0) + __builtin_abort (); + if (foo(96) != PREC - 5) + __builtin_abort (); + if (foo(35) != PREC) + __builtin_abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "__builtin_ctz|\\.CTZ" 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-long-long.c b/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-long-long.c new file mode 100644 index 0000000000000000000000000000000000000000..1ea0d5d7d9f8be1824c4177c33edd91e66b4ddab --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-long-long.c @@ -0,0 +1,31 @@ +/* { dg-do run } */ +/* { dg-require-effective-target ctzll } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +#define PREC (__CHAR_BIT__ * __SIZEOF_LONG_LONG__) + +int +__attribute__ ((noinline, noclone)) +foo (unsigned long long b) { + int c = 0; + + while (b) { + b <<= 1; + c++; + } + + return c; +} + +int main() +{ + if (foo(0) != 0) + __builtin_abort (); + if (foo(96) != PREC - 5) + __builtin_abort (); + if (foo(35) != PREC) + __builtin_abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "__builtin_ctz|\\.CTZ" 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-long.c b/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-long.c new file mode 100644 index 0000000000000000000000000000000000000000..80fb02dcfa68bc022ae69b26fb189323e01fc6fc --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-long.c @@ -0,0 +1,31 @@ +/* { dg-do run } */ +/* { dg-require-effective-target ctzl } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +#define PREC (__CHAR_BIT__ * __SIZEOF_LONG__) + +int +__attribute__ ((noinline, noclone)) +foo (unsigned long b) { + int c = 0; + + while (b) { + b <<= 1; + c++; + } + + return c; +} + +int main() +{ + if (foo(0) != 0) + __builtin_abort (); + if (foo(96) != PREC - 5) + __builtin_abort (); + if (foo(35) != PREC) + __builtin_abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "__builtin_ctz|\\.CTZ" 1 "optimized" } } */ diff --git a/gcc/testsuite/lib/target-supports.exp b/gcc/testsuite/lib/target-supports.exp index 2a058c67c53466fe41b748d37ab660afd4e3403f..c745202624da672d1bdc21b8e74c1daac6ad9933 100644 --- a/gcc/testsuite/lib/target-supports.exp +++ b/gcc/testsuite/lib/target-supports.exp @@ -8701,6 +8701,72 @@ proc check_effective_target_popcount { } { } "" ] } +# Return 1 if the target supports clz on int. + +proc check_effective_target_clz { } { + return [check_no_messages_and_pattern clz "!\\(call" rtl-expand { + int foo (int b) + { + return __builtin_clz (b); + } + } "" ] +} + +# Return 1 if the target supports clz on long. + +proc check_effective_target_clzl { } { + return [check_no_messages_and_pattern clzl "!\\(call" rtl-expand { + int foo (long b) + { + return __builtin_clzl (b); + } + } "" ] +} + +# Return 1 if the target supports clz on long long. + +proc check_effective_target_clzll { } { + return [check_no_messages_and_pattern clzll "!\\(call" rtl-expand { + int foo (long long b) + { + return __builtin_clzll (b); + } + } "" ] +} + +# Return 1 if the target supports ctz on int. + +proc check_effective_target_ctz { } { + return [check_no_messages_and_pattern ctz "!\\(call" rtl-expand { + int foo (int b) + { + return __builtin_ctz (b); + } + } "" ] +} + +# Return 1 if the target supports ctz on long. + +proc check_effective_target_ctzl { } { + return [check_no_messages_and_pattern ctzl "!\\(call" rtl-expand { + int foo (long b) + { + return __builtin_ctzl (b); + } + } "" ] +} + +# Return 1 if the target supports ctz on long long. + +proc check_effective_target_ctzll { } { + return [check_no_messages_and_pattern ctzll "!\\(call" rtl-expand { + int foo (long long b) + { + return __builtin_ctzll (b); + } + } "" ] +} + # Return 1 if the target supports atomic operations on "long long" # and can execute them. # diff --git a/gcc/tree-scalar-evolution.cc b/gcc/tree-scalar-evolution.cc index f75398afb7c9fdf42e69e940e2232942143049f6..0e4e87aea34622c8ee21f5c8e29dae2d0cdd2643 100644 --- a/gcc/tree-scalar-evolution.cc +++ b/gcc/tree-scalar-evolution.cc @@ -3397,12 +3397,21 @@ expression_expensive_p (tree expr, hash_map &cache, library call for popcount when backend does not have an instruction to do so. We consider this to be expensive and generate __builtin_popcount only when backend defines it. */ + optab optab; combined_fn cfn = get_call_combined_fn (expr); switch (cfn) { CASE_CFN_POPCOUNT: + optab = popcount_optab; + goto bitcount_call; + CASE_CFN_CLZ: + optab = clz_optab; + goto bitcount_call; + CASE_CFN_CTZ: + optab = ctz_optab; +bitcount_call: /* Check if opcode for popcount is available in the mode required. */ - if (optab_handler (popcount_optab, + if (optab_handler (optab, TYPE_MODE (TREE_TYPE (CALL_EXPR_ARG (expr, 0)))) == CODE_FOR_nothing) { @@ -3415,7 +3424,7 @@ expression_expensive_p (tree expr, hash_map &cache, instructions. */ if (is_a (mode, &int_mode) && GET_MODE_SIZE (int_mode) == 2 * UNITS_PER_WORD - && (optab_handler (popcount_optab, word_mode) + && (optab_handler (optab, word_mode) != CODE_FOR_nothing)) break; return true; diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc index fece876099c1687569d6351e7d2416ea6acae5b5..ce2441f2a6dbdf2d8fe42755d5d1abd8a631bb5c 100644 --- a/gcc/tree-ssa-loop-niter.cc +++ b/gcc/tree-ssa-loop-niter.cc @@ -42,6 +42,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-chrec.h" #include "tree-scalar-evolution.h" #include "tree-dfa.h" +#include "internal-fn.h" #include "gimple-range.h" @@ -2198,6 +2199,224 @@ number_of_iterations_popcount (loop_p loop, edge exit, return true; } +/* Return an expression that counts the leading/trailing zeroes of src. + + If define_at_zero is true, then the built expression will be defined to + return the precision of src when src == 0 (using either a conditional + expression or a suitable internal function). + Otherwise, we can elide the conditional expression and let src = 0 invoke + undefined behaviour. */ + +static tree +build_cltz_expr (tree src, bool leading, bool define_at_zero) +{ + tree fn; + internal_fn ifn = leading ? IFN_CLZ : IFN_CTZ; + bool use_ifn = false; + int prec = TYPE_PRECISION (TREE_TYPE (src)); + int i_prec = TYPE_PRECISION (integer_type_node); + int li_prec = TYPE_PRECISION (long_integer_type_node); + int lli_prec = TYPE_PRECISION (long_long_integer_type_node); + + tree utype = unsigned_type_for (TREE_TYPE (src)); + src = fold_convert (utype, src); + + if (direct_internal_fn_supported_p (ifn, utype, OPTIMIZE_FOR_BOTH)) + use_ifn = true; + else if (prec <= i_prec) + fn = leading ? builtin_decl_implicit (BUILT_IN_CLZ) + : builtin_decl_implicit (BUILT_IN_CTZ); + else if (prec == li_prec) + fn = leading ? builtin_decl_implicit (BUILT_IN_CLZL) + : builtin_decl_implicit (BUILT_IN_CTZL); + else if (prec == lli_prec || prec == 2 * lli_prec) + fn = leading ? builtin_decl_implicit (BUILT_IN_CLZLL) + : builtin_decl_implicit (BUILT_IN_CTZLL); + else + return NULL_TREE; + + tree call; + if (use_ifn) + { + call = build_call_expr_internal_loc (UNKNOWN_LOCATION, ifn, + integer_type_node, 1, src); + int val; + scalar_int_mode mode = SCALAR_INT_TYPE_MODE (utype); + int optab_defined_at_zero + = leading ? CLZ_DEFINED_VALUE_AT_ZERO (mode, val) + : CTZ_DEFINED_VALUE_AT_ZERO (mode, val); + if (define_at_zero && !(optab_defined_at_zero == 2 && val == prec)) + { + tree is_zero = fold_build2 (NE_EXPR, boolean_type_node, src, + build_zero_cst (TREE_TYPE (src))); + call = fold_build3(COND_EXPR, integer_type_node, is_zero, call, + build_int_cst (integer_type_node, prec)); + } + } + else if (prec == 2 * lli_prec) + { + tree src1 = fold_convert (long_long_unsigned_type_node, + fold_build2 (RSHIFT_EXPR, TREE_TYPE (src), + unshare_expr (src), + build_int_cst (integer_type_node, + lli_prec))); + tree src2 = fold_convert (long_long_unsigned_type_node, src); + /* We count the zeroes in src1, and add the number in src2 when src1 + is 0. */ + if (!leading) + std::swap(src1, src2); + tree call1 = build_call_expr (fn, 1, src1); + tree call2 = build_call_expr (fn, 1, src2); + if (define_at_zero) + { + tree is_zero2 = fold_build2 (NE_EXPR, boolean_type_node, src2, + build_zero_cst (TREE_TYPE (src2))); + call2 = fold_build3(COND_EXPR, integer_type_node, is_zero2, call2, + build_int_cst (integer_type_node, lli_prec)); + } + tree is_zero1 = fold_build2 (NE_EXPR, boolean_type_node, src1, + build_zero_cst (TREE_TYPE (src1))); + call = fold_build3(COND_EXPR, integer_type_node, is_zero1, call1, + fold_build2 (PLUS_EXPR, integer_type_node, call2, + build_int_cst (integer_type_node, + lli_prec))); + } + else + { + if (prec < i_prec) + src = fold_convert (unsigned_type_node, src); + + call = build_call_expr (fn, 1, src); + if (define_at_zero) + { + tree is_zero = fold_build2 (NE_EXPR, boolean_type_node, src, + build_zero_cst (TREE_TYPE (src))); + call = fold_build3(COND_EXPR, integer_type_node, is_zero, call, + build_int_cst (integer_type_node, prec)); + } + + if (leading && prec < i_prec) + call = fold_build2(MINUS_EXPR, integer_type_node, call, + build_int_cst (integer_type_node, + i_prec - prec)); + } + + return call; +} + +/* See comment below for number_of_iterations_bitcount. + For c[lt]z complement, we have: + + modify: + iv_2 = iv_1 >> 1 OR iv_1 << 1 + + test: + if (iv != 0) + + modification count: + src precision - c[lt]z (src) + + */ + +static bool +number_of_iterations_cltz_complement (loop_p loop, edge exit, + enum tree_code code, + class tree_niter_desc *niter) +{ + bool modify_before_test = true; + HOST_WIDE_INT max; + + /* Check that condition for staying inside the loop is like + if (iv != 0). */ + gimple *cond_stmt = last_stmt (exit->src); + if (!cond_stmt + || gimple_code (cond_stmt) != GIMPLE_COND + || code != NE_EXPR + || !integer_zerop (gimple_cond_rhs (cond_stmt)) + || TREE_CODE (gimple_cond_lhs (cond_stmt)) != SSA_NAME) + return false; + + tree iv_2 = gimple_cond_lhs (cond_stmt); + gimple *iv_2_stmt = SSA_NAME_DEF_STMT (iv_2); + + /* If the test comes before the iv modification, then these will actually be + iv_1 and a phi node. */ + if (gimple_code (iv_2_stmt) == GIMPLE_PHI + && gimple_bb (iv_2_stmt) == loop->header + && gimple_phi_num_args (iv_2_stmt) == 2 + && (TREE_CODE (gimple_phi_arg_def (iv_2_stmt, + loop_latch_edge (loop)->dest_idx)) + == SSA_NAME)) + { + /* iv_2 is actually one of the inputs to the phi. */ + iv_2 = gimple_phi_arg_def (iv_2_stmt, loop_latch_edge (loop)->dest_idx); + iv_2_stmt = SSA_NAME_DEF_STMT (iv_2); + modify_before_test = false; + } + + /* Make sure iv_2_stmt is a logical shift by one stmt: + iv_2 = iv_1 {>>|<<} 1 */ + if (!is_gimple_assign (iv_2_stmt) + || (gimple_assign_rhs_code (iv_2_stmt) != LSHIFT_EXPR + && (gimple_assign_rhs_code (iv_2_stmt) != RSHIFT_EXPR + || !TYPE_UNSIGNED (TREE_TYPE (gimple_assign_lhs (iv_2_stmt))))) + || !integer_onep (gimple_assign_rhs2 (iv_2_stmt))) + return false; + + bool left_shift = (gimple_assign_rhs_code (iv_2_stmt) == LSHIFT_EXPR); + + tree iv_1 = gimple_assign_rhs1 (iv_2_stmt); + + /* Check the recurrence. */ + gimple *phi = SSA_NAME_DEF_STMT (iv_1); + if (gimple_code (phi) != GIMPLE_PHI + || (gimple_bb (phi) != loop_latch_edge (loop)->dest) + || (iv_2 != gimple_phi_arg_def (phi, loop_latch_edge (loop)->dest_idx))) + return false; + + /* We found a match. */ + tree src = gimple_phi_arg_def (phi, loop_preheader_edge (loop)->dest_idx); + int src_precision = TYPE_PRECISION (TREE_TYPE (src)); + + /* Get the corresponding c[lt]z builtin. */ + tree expr = build_cltz_expr (src, !left_shift, true); + + if (!expr) + return false; + + expr = fold_build2 (MINUS_EXPR, integer_type_node, + build_int_cst (integer_type_node, src_precision), + expr); + + max = src_precision; + + tree may_be_zero = boolean_false_node; + + if (modify_before_test) + { + expr = fold_build2 (MINUS_EXPR, integer_type_node, expr, + integer_one_node); + max = max - 1; + may_be_zero = fold_build2 (EQ_EXPR, boolean_type_node, src, + build_zero_cst (TREE_TYPE (src))); + } + + expr = fold_convert (unsigned_type_node, expr); + + niter->assumptions = boolean_true_node; + niter->may_be_zero = simplify_using_initial_conditions (loop, may_be_zero); + niter->niter = simplify_using_initial_conditions (loop, expr); + + if (TREE_CODE (niter->niter) == INTEGER_CST) + niter->max = tree_to_uhwi (niter->niter); + else + niter->max = max; + + niter->bound = NULL_TREE; + niter->cmp = ERROR_MARK; + return true; +} + /* See if LOOP contains a bit counting idiom. The idiom consists of two parts: 1. A modification to the induction variabler;. 2. A test to determine whether or not to exit the loop. @@ -2244,7 +2463,8 @@ number_of_iterations_bitcount (loop_p loop, edge exit, enum tree_code code, class tree_niter_desc *niter) { - return number_of_iterations_popcount (loop, exit, code, niter); + return (number_of_iterations_popcount (loop, exit, code, niter) + || number_of_iterations_cltz_complement (loop, exit, code, niter)); } /* Substitute NEW_TREE for OLD in EXPR and fold the result.