From patchwork Tue Aug 4 09:50:33 2026 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kyrylo Tkachov X-Patchwork-Id: 140575 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from vm01.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id DC6D54BAE7F2 for ; Tue, 4 Aug 2026 09:51:37 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org DC6D54BAE7F2 Authentication-Results: sourceware.org; dkim=pass (2048-bit key, unprotected) header.d=Nvidia.com header.i=@Nvidia.com header.a=rsa-sha256 header.s=selector2 header.b=Xjt0cQ/r X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from BL0PR03CU003.outbound.protection.outlook.com (mail-eastusazlp170120007.outbound.protection.outlook.com [IPv6:2a01:111:f403:c101::7]) by sourceware.org (Postfix) with ESMTPS id 7098D4BA2E07 for ; Tue, 4 Aug 2026 09:50:58 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 7098D4BA2E07 Authentication-Results: sourceware.org; dmarc=pass (p=reject dis=none) header.from=nvidia.com Authentication-Results: sourceware.org; spf=fail smtp.mailfrom=nvidia.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 7098D4BA2E07 Authentication-Results: sourceware.org; arc=pass smtp.remote-ip=2a01:111:f403:c101::7 ARC-Seal: i=2; a=rsa-sha256; d=sourceware.org; s=key; t=1785837058; cv=pass; b=lU3GJwUqnWDfJas/uLm36U/joQHEPVD/TFAFwkz+sj0pTlxfNKCaschGB1OfhH2QdMwTJnC0xpyBRcqWlSnhIR5fc3hN72Io+tcoRlLoXI6tJ7b38h2wlt0vFiLWQiL7mN/IiIQvn5GVjZ36ehI5Si8rRAIrSxA68W86VZVs6rY= ARC-Message-Signature: i=2; a=rsa-sha256; d=sourceware.org; s=key; t=1785837058; c=relaxed/simple; bh=qT9U3ngB5qhoETtyPQ5kO7EWKNfHUdQCDFb+/zpxB1Q=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=DkN8cIWh43/6syAmwzbKZHE87E77ks09v3gs3YCwCrJmFKj+msnskjfOHIVC99IporXjnIhhDRHBNx0s21Uc40+m6rWigS9FAy9yS/7gwJDO3nyT+ITtDBjcjY7NH5fmFQTal4aPJGDU0aKweZqN7hs56+9rgfuj5yO0bLA2DYM= ARC-Authentication-Results: i=2; sourceware.org; dkim=pass (2048-bit key, unprotected) header.d=Nvidia.com header.i=@Nvidia.com header.a=rsa-sha256 header.s=selector2 header.b=Xjt0cQ/r DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 7098D4BA2E07 ARC-Seal: i=1; a=rsa-sha256; s=arcselector10001; d=microsoft.com; cv=none; b=Ss12XRpjTZ/u7CzG+QEUn8c2t2FqCodC9xih+3/2STMwtIfANqLdr95Ixmoe0DD7+X+OaJ4rVyXGnZ9+aZMzERRxJCFOCsW54778O3MoFDlGRL/WYh4xNxIAR6jqq7apXwOHz8Rk1xPcFMcqyu1I8KZ1M/vkhFtnKgtnAPvLEzegYZXPJFRnDqjACtg0syUxAWk5dMBQN58GTuOZ7ADjCNuAM1DiqN38MxITkfUNnki33UokfKrqJzIKigXWhLUMDbLppWY7N+PMTqIXPLbc/ImPqToQEhV9pIP40GFuIOdIItHuQA89uubXusN2sZ1kcoYC17n9PTiXDwXbqjsECg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector10001; 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=w7zw6D5LXJ1sBNMnw5Yn7MiUhveSlVYfVKq+Ym4nhvA=; b=ekckgS4ZCoTi4XFIQqpeblJKVhLoa7IrJCRTSaHsIZk7ptZblOrgJjJb7ouRkrt4RdTI332hVhgxswvtDkAD1hDTUDAYoPjPu+HXGN9LvgBqlSKnQ1qoZzXKGYOmYOJZe22agAqozUkd8knOLD8bqKRK8SwlVmuyt5WKngMxzU3E/4TSKyPvpY8LI3NzCOId2Avjug0aGvUIwth83Zd+V/vvqn6CWwTNaQ/jC42patcAdUYNttfXaoSF2pra5XmvWY7pmFXmY0tc+XVzOavppzssjeKCeIPKqGyGNNeAAnv/WwA8IaoTFrDpxc1AH3kilWrrJN/B6eF2KcNr6QuUHA== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass (sender ip is 216.228.117.160) smtp.rcpttodomain=gcc.gnu.org smtp.mailfrom=nvidia.com; dmarc=pass (p=reject sp=reject pct=100) action=none header.from=nvidia.com; dkim=none (message not signed); arc=none (0) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=Nvidia.com; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=w7zw6D5LXJ1sBNMnw5Yn7MiUhveSlVYfVKq+Ym4nhvA=; b=Xjt0cQ/rrEoWgyDru9Ca3js3BGNFy693uYj+m6ibujKHZC2ZI3yg117gpnpBZXEwLyXf5UsHe98a2cchk88uwbZQRyDHpczT2KXvRa2QJ4xVQcBdUClebhVr+5ik9NKd7jtqGyV1sJUN8Ezd7dpGDcRFYgD68iADdHUWOVSxAzMMlRVKVU2SBwHnKSkDUXnNrYJ8d48F4twZSNpYMplu9c8AbdKpZIxWc56UTMdsXw23AZ8qRUaOYl/hnLoBdT4qy1PSY1lglpdkv8wkYeXvWJ+FmFlFYicqRkb4v5hnt0cFt102C5zu14vsyo1vpet4RmwCiWE7O9otGAf/CzoGAw== Received: from CH0PR04CA0072.namprd04.prod.outlook.com (2603:10b6:610:74::17) by SA3PR12MB8021.namprd12.prod.outlook.com (2603:10b6:806:305::16) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.21.292.15; Tue, 4 Aug 2026 09:50:55 +0000 Received: from CH1PEPF0000AD75.namprd04.prod.outlook.com (2603:10b6:610:74:cafe::84) by CH0PR04CA0072.outlook.office365.com (2603:10b6:610:74::17) with Microsoft SMTP Server (version=TLS1_3, cipher=TLS_AES_256_GCM_SHA384) id 15.21.292.16 via Frontend Transport; Tue, 4 Aug 2026 09:50:54 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 216.228.117.160) smtp.mailfrom=nvidia.com; dkim=none (message not signed) header.d=none;dmarc=pass action=none header.from=nvidia.com; Received-SPF: Pass (protection.outlook.com: domain of nvidia.com designates 216.228.117.160 as permitted sender) receiver=protection.outlook.com; client-ip=216.228.117.160; helo=mail.nvidia.com; pr=C Received: from mail.nvidia.com (216.228.117.160) by CH1PEPF0000AD75.mail.protection.outlook.com (10.167.244.54) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.21.292.8 via Frontend Transport; Tue, 4 Aug 2026 09:50:54 +0000 Received: from rnnvmail201.nvidia.com (10.129.68.8) by mail.nvidia.com (10.129.200.66) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.2562.45; Tue, 4 Aug 2026 02:50:43 -0700 Received: from ktkachov-mlt.nvidia.com (10.126.230.37) by rnnvmail201.nvidia.com (10.129.68.8) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.2562.20; Tue, 4 Aug 2026 02:50:42 -0700 From: To: CC: Kyrylo Tkachov Subject: [PATCH] match: fold a remainder of a remainder by a multiple Date: Tue, 4 Aug 2026 11:50:33 +0200 Message-ID: <20260804095033.55165-1-ktkachov@nvidia.com> X-Mailer: git-send-email 2.50.1 MIME-Version: 1.0 X-Originating-IP: [10.126.230.37] X-ClientProxiedBy: rnnvmail203.nvidia.com (10.129.68.9) To rnnvmail201.nvidia.com (10.129.68.8) X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: CH1PEPF0000AD75:EE_|SA3PR12MB8021:EE_ X-MS-Office365-Filtering-Correlation-Id: 81e51e98-0396-423e-1575-08def20de071 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; ARA:13230040|23010399003|1800799024|376014|82310400026|36860700016|10067099003|11063799006|6133799003|56012099006|18002099003|13003099007; X-Microsoft-Antispam-Message-Info: a3Z2aeuneY7x5blkJPKT7oqyHNkwwsnB5hfT/PAr+qoyiLv4DodbE7O/jlzNVVwJZTIqhXhTGR0XofF7FnJ98DU7rRNouZX+h4LfMpizKV16+syUOpkuoawfgENwWM3w5EBaXUsD90OdNrVJp2nuNoNpopzWstlF/JtrZc9EfrrdpHNxnW4G8jDMdJczbb5yf+vSmCdPAsX8e7Ngau/kKs3J0V57R7ObnCqmBlk/Z3rV1IHSd5tdAbHEsPVmyJyyvtrHHBYAMQGHkC/gwNZv2EYqxfArix9fXiVgJOAw6ycoG2rlELl9cFsvH/6kXSqEiAZh4dPszAO+x5ezjOrHheB3sxmdV48IzKoO+5Q8AbGdqMstNySRggFVs4HTlGg3CtYjcgWabyZIt2VLbd0/YGUZ721jlcmZ5wXKwzBOuxMOjbohURdvB4KMkJLdQxmVDA65MePx9EEkpO8yDGgWnb7NA3Lv2OeSvaZmpbXWUKr8P6/Ugqk7kvIkaWb5Qn1Olpb+LFuiXdIjXG6eIhkxn5kgz1mLfjw5NbhIWEByUPfkh6QCz3wdSAkeB75onm/vq5AbVckTbkiM3eZQGGcq8ijuLxXanhVkrec+vi7C+zrV/LDCBTdpzQQRHWkxtHC+Y7NMke46dJB4acvauuUBXn6yMSeD28aVwud/TodB+FXPSL1iCC56iZEt7wsd9N+VhU44r6f1gZO9tFCpvkCEBg== X-Forefront-Antispam-Report: CIP:216.228.117.160; CTRY:US; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:mail.nvidia.com; PTR:dc6edge1.nvidia.com; CAT:NONE; SFS:(13230040)(23010399003)(1800799024)(376014)(82310400026)(36860700016)(10067099003)(11063799006)(6133799003)(56012099006)(18002099003)(13003099007); DIR:OUT; SFP:1101; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: kS1dY+GOY/vRPvMEnHD3knrSBQ1J5BueGEYpL2jHwguBiUr+sAhwAZQ7Fp9SoRs2ce/ovOvF6sCSqR4C+el//5dCyaKC0e5DPjNIsxtK+zDR70By9Ewy+VfP/vyQVSd68Bv7BSKaduvLzu7Pt1jTS8UosuOaGVgfbypuP+e3k83KfJoL/nZmNugWkXVntkrYf8G3PhHQfDcH+QSbY3dcOTxvNVlOq92+S4BkTMkIAluLkrInuv//MWtTnlLZkGYYZ9S6p10acYwo5oyLI59FHgGOi9GWClh9ujbPZGuXCeLHRibhgAZ37TS984YO/6bZkxQD7SylkVZEkzorpWYCSjceglOHtLNdCIk/QYwEI0+1CMIhilnnZ6gyHvBFZ9A/4dx42GU3XSDmtox83BgqKrf0nojvsYsCOg+r37SlP55Une60ptR+ValJUgzLSZE3 X-OriginatorOrg: Nvidia.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 04 Aug 2026 09:50:54.5597 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 81e51e98-0396-423e-1575-08def20de071 X-MS-Exchange-CrossTenant-Id: 43083d15-7273-40c1-b7db-39efd9ccc17a X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=43083d15-7273-40c1-b7db-39efd9ccc17a; Ip=[216.228.117.160]; Helo=[mail.nvidia.com] X-MS-Exchange-CrossTenant-AuthSource: CH1PEPF0000AD75.namprd04.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: SA3PR12MB8021 X-Spam-Status: No, score=-8.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, LOCAL_AUTHENTICATION_FAIL_SPF, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_NONE, TXREP shortcircuit=no autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on 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: , Errors-To: gcc-patches-bounces~patchwork=sourceware.org@gcc.gnu.org From: Kyrylo Tkachov Truncating remainder keeps the sign of the dividend and its magnitude modulo the divisor, so reducing X % C1 again modulo C2 gives the same result as reducing X directly whenever C2 divides C1. Folding the pair removes one division. int f (int x) { return (x % 12) % 4; } aarch64 -O2: before after mov w1, 12 negs w1, w0 sdiv w1, w0, w1 and w0, w0, 3 add w1, w1, w1, lsl 1 and w1, w1, 3 sub w0, w0, w1, lsl 2 csneg w0, w0, w1, mi negs w1, w0 and w0, w0, 3 and w1, w1, 3 csneg w0, w0, w1, mi Bootstrapped and tested on aarch64-none-linux-gnu. Ok for trunk? Thanks, Kyrill gcc/ChangeLog: * match.pd ((X % C1) % C2): New simplification. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/modmod-1.c: New test. Signed-off-by: Kyrylo Tkachov --- gcc/match.pd | 12 ++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c | 19 +++++++++++++++++++ 2 files changed, 31 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c diff --git a/gcc/match.pd b/gcc/match.pd index 4fca75d6fb6..22202af2cc1 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -975,6 +975,18 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (with { tree utype = unsigned_type_for (TREE_TYPE (@0)); } (cmp (mod (convert:utype @0) (convert:utype @2)) (convert:utype @1))))))) +/* (X % C1) % C2 is X % C2 when C2 divides C1. Truncating remainder keeps + the sign of X and the magnitude modulo C1, so reducing modulo C2 gives + the same result as reducing X directly. */ +(simplify + (trunc_mod (trunc_mod @0 INTEGER_CST@1) INTEGER_CST@2) + (if (INTEGRAL_TYPE_P (type) + && !TYPE_OVERFLOW_TRAPS (type) + && !integer_zerop (@1) + && !integer_zerop (@2) + && wi::multiple_of_p (wi::to_widest (@1), wi::to_widest (@2), SIGNED)) + (trunc_mod @0 @2))) + /* X % -C is the same as X % C. */ (simplify (trunc_mod @0 INTEGER_CST@1) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c b/gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c new file mode 100644 index 00000000000..6689a518ff3 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c @@ -0,0 +1,19 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +/* (X % C1) % C2 is X % C2 when C2 divides C1. */ + +int f1 (int x) { return (x % 12) % 4; } +int f2 (int x) { return (x % 100) % 25; } +int f3 (int x) { return (x % -12) % 4; } +int f4 (int x) { return (x % 12) % -4; } +unsigned int f5 (unsigned int x) { return (x % 12) % 4; } + +/* C2 does not divide C1 here, both remainders have to stay. */ +int f6 (int x) { return (x % 12) % 5; } + +/* Only the unfoldable pair keeps both remainders. */ +/* { dg-final { scan-tree-dump-times " % 12;" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " % 5;" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " % 4;" 3 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " % 25;" 1 "optimized" } } */