From patchwork Tue Sep 17 07:42:15 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Konstantinos Eleftheriou X-Patchwork-Id: 1986309 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=vrull.eu header.i=@vrull.eu header.a=rsa-sha256 header.s=google header.b=Vmn+R/Wy; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4X7DK52SPlz1y2N for ; Tue, 17 Sep 2024 17:42:49 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 77D653858403 for ; Tue, 17 Sep 2024 07:42:46 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-ed1-x530.google.com (mail-ed1-x530.google.com [IPv6:2a00:1450:4864:20::530]) by sourceware.org (Postfix) with ESMTPS id DDCCA3858D26 for ; Tue, 17 Sep 2024 07:42:23 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org DDCCA3858D26 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=vrull.eu Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=vrull.eu ARC-Filter: OpenARC Filter v1.0.0 sourceware.org DDCCA3858D26 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::530 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1726558945; cv=none; b=OblkVYsDFUtibbJKXHrk3jg9lFKcUR13TLCRKxLgfQIHQ486ofa0y5srh0g+Ia/95p5r6gA9yR5Cejan/jm1YBgXQqnGoSSD9+dYEUzuDJ6y5BMjHt5QPb04nhpedAXYjg33/oaoYNJ5Bf/8pJYJ1on3zVTyBOSfkxfBqVYvGhc= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1726558945; c=relaxed/simple; bh=aVaHAyMRDYCqv4Gqjfsn+fbps9gjWKZl4743UkGuaHg=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=mRdAiLUolyL5abHxlEgIaZEciFwKJu86vcBlB4d50laz027tDbPo8OOoHSRhCNHIzRw+6bMgWulV2+aW1FbgQLiIVAPiFDaEKCe/LGL84mo1PPaUbP7sHzMr0gMEBHiIccEdUR26poc3m9LajaKMG8sbcwiLMZCr+I6KoMXUT/k= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-ed1-x530.google.com with SMTP id 4fb4d7f45d1cf-5c255e3c327so6826323a12.1 for ; Tue, 17 Sep 2024 00:42:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=vrull.eu; s=google; t=1726558942; x=1727163742; darn=gcc.gnu.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=ZjjAa/6HgVfgWJTNr54KOAC6m9Qvw2bVdEf0OeGbG8Q=; b=Vmn+R/WyxHndynkI97pTh4B0k++GySqVG1Y0oMkgBN5ScHK7IKedulkWqOebY8zpaa Tfkr8BQDBFaCJQUDhbO4iCZ6Q08tz68UrVvR1MsDAiu0RB8ny9xRq6VvNded0+fcYr+d QdXCPkNTdA5/Q2Y/Nr86r8fhwkBOmse1NEkoVv/09dcOA7ooIy9+W4xOb94yFvtOOXpo JQ2kXtfECtLt+u7AE6vFhT7VOyc0T0FvpyRmjfp2LlqzE6bUXToSBSAii0rr41Sfsd7y DEE0D+5W1is1w/+qWDTgm9GBhzYY8hYparXuGDKDi8rW39YIV2lNPYrSmP7Rkh1RwA9U dMOQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1726558942; x=1727163742; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=ZjjAa/6HgVfgWJTNr54KOAC6m9Qvw2bVdEf0OeGbG8Q=; b=Zm6mOQmI3+b6FeUlgU8E2RZy6p6jSFJJN9lk2HPbQ7847GLnJC4xgjfTbZEqWkKKiK /QfkAzLkkoBQ9Qe1tBd5HPnvajr0wLdHRmGCw+vmUunm1zLY3I25QrhCuOrq8WW8Q2kt eOtJtdII96OfkynAjBAMlvW+E32RH92c+kTXR5FBzSeycAIiUaAISAxcZsW8DvlNw7dt odO6qwq7ccY0PHKqb8o39CLCbH4fnqO/mGlqAPJD/hecVblDVsdGXvOKvLlulwVHZELQ KLqudaPvI7umMXt66rxMWxDgIYctWSG9r6kV132bmp7mFFnYq+SuBNBrw+81O66GL8QT pJ0g== X-Gm-Message-State: AOJu0Yy26LwN7DtugT1I8Nor9jLjjdiv9TRY2iNfCpJ8ZzHbYsuzSDEw A2hFkG1zsG8BMNGOB2SWPz1NjAIypaCkzeAEYCuYKcYoPIDhTMEH3IxULhdZprxJfJKIFD39XmN j3gU= X-Google-Smtp-Source: AGHT+IGZP7eX5eSPX/fJ9gjk6CfuNcWl3cUQ9zQZH+pQ36qsADwmZ7wMP6UraOZHX1ZFjjifgz2Dvg== X-Received: by 2002:a17:907:e26a:b0:a8d:6329:d8cc with SMTP id a640c23a62f3a-a902943b52fmr1719763666b.25.1726558941597; Tue, 17 Sep 2024 00:42:21 -0700 (PDT) Received: from altra.sec.univie.ac.at (ampere.sec.univie.ac.at. [131.130.126.104]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a90610966b6sm417879466b.17.2024.09.17.00.42.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 17 Sep 2024 00:42:21 -0700 (PDT) From: Konstantinos Eleftheriou To: gcc-patches@gcc.gnu.org, Philipp Tomsich , =?utf-8?q?Christoph_M=C3=BCllner?= Cc: kelefth Subject: [PATCH v2] match: Change (A * B) + (-C) to (B - C/A) * A, if C multiple of A [PR109393] Date: Tue, 17 Sep 2024 09:42:15 +0200 Message-ID: <20240917074215.2978559-1-konstantinos.eleftheriou@vrull.eu> X-Mailer: git-send-email 2.46.0 MIME-Version: 1.0 X-Spam-Status: No, score=-12.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP 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: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org From: kelefth The following function: int foo(int *a, int j) { int k = j - 1; return a[j - 1] == a[k]; } does not fold to `return 1;` using -O2 or higher. The cause of this is that the expression `4 * j + (-4)` for the index computation is not folded to `4 * (j - 1)`. Existing simplifications that handle similar cases are applied when A == C, which is not the case in this instance. A previous attempt to address this issue is https://gcc.gnu.org/pipermail/gcc-patches/2024-April/649896.html This patch adds the following simplification in match.pd: (A * B) + (-C) -> (B - C/A) * A, if C a multiple of A which also handles cases where the index is j - 2, j - 3, etc. Bootstrapped for all languages and regression tested on x86-64 and aarch64. PR tree-optimization/109393 gcc/ChangeLog: * match.pd: (A * B) + (-C) -> (B - C/A) * A, if C a multiple of A. gcc/testsuite/ChangeLog: * gcc.dg/pr109393.c: New test. Tested-by: Christoph Müllner Signed-off-by: Philipp Tomsich Signed-off-by: Konstantinos Eleftheriou --- gcc/match.pd | 21 ++++++++++++++++++++- gcc/testsuite/gcc.dg/pr109393.c | 23 +++++++++++++++++++++++ 2 files changed, 43 insertions(+), 1 deletion(-) create mode 100644 gcc/testsuite/gcc.dg/pr109393.c diff --git a/gcc/match.pd b/gcc/match.pd index 5566c0e4c41..6aeb92cdad0 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -4245,7 +4245,26 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) ? wi::max_value (TYPE_PRECISION (type), SIGNED) : wi::min_value (TYPE_PRECISION (type), SIGNED)))))) && single_use (@3)) - (mult (plusminus @2 { build_one_cst (type); }) @0)))))) + (mult (plusminus @2 { build_one_cst (type); }) @0))))) + /* (A * B) + (-C) -> (B - C/A) * A, if C is a multiple of A. */ + (if (!ALL_FRACT_MODE_P (TYPE_MODE (type))) + (simplify + (plus (mult:cs integer_nonzerop@0 @1) INTEGER_CST@2) + /* Exclude the case that @2 == min to prevent UB when calculating abs + and (B - C/A). */ + (if (TREE_CODE (type) == INTEGER_TYPE + && wi::neg_p (wi::to_wide (@2)) + && wi::to_wide (@2) != wi::min_value (TYPE_PRECISION (type), SIGNED)) + (with { + wide_int c0 = wi::to_wide (@0); + wide_int c2 = wi::to_wide (@2); + wide_int c2_abs = wi::abs (c2); } + (if (wi::multiple_of_p (c2_abs, c0, TYPE_SIGN (type))) + (with { + /* Calculate @2 / @0 in order to factorize the expression. */ + wide_int div_res = wi::sdiv_trunc (c2, c0); + tree div_cst = wide_int_to_tree (type, div_res); } + (mult (plus @1 { div_cst; }) @0)))))))) #if GIMPLE /* Canonicalize X + (X << C) into X * (1 + (1 << C)) and diff --git a/gcc/testsuite/gcc.dg/pr109393.c b/gcc/testsuite/gcc.dg/pr109393.c new file mode 100644 index 00000000000..17bf9330796 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr109393.c @@ -0,0 +1,23 @@ +/* PR tree-optimization/109393 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int foo(int *a, int j) +{ + int k = j - 1; + return a[j - 1] == a[k]; +} + +int foo2(int *a, int j) +{ + int k = j - 5; + return a[j - 5] == a[k]; +} + +int bar(int *a, int j) +{ + int k = j - 1; + return (&a[j + 1] - 2) == &a[k]; +} + +/* { dg-final { scan-tree-dump-times "return 1;" 3 "optimized" } } */ \ No newline at end of file