From patchwork Fri Sep 6 12:44:06 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Konstantinos Eleftheriou X-Patchwork-Id: 1981894 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=eY10hgB1; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; 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 [IPv6:2620:52:3:1:0:246e:9693:128c]) (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 4X0bXR32MKz1y1D for ; Fri, 6 Sep 2024 22:44:37 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 99AFD384A44F for ; Fri, 6 Sep 2024 12:44:34 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-ej1-x629.google.com (mail-ej1-x629.google.com [IPv6:2a00:1450:4864:20::629]) by sourceware.org (Postfix) with ESMTPS id 3F0BD385828B for ; Fri, 6 Sep 2024 12:44:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 3F0BD385828B 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 3F0BD385828B Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::629 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1725626653; cv=none; b=GIXyRIJxF5bNA6oKE6Oqf9z6T+11EJse5RJ+OCvrheaszXHwypcHoo0LXq2X0bt5OP+G7U6SuBiuvNOIrIBwov6oCyFVNMlqPb+a+WFDs0d9KQ5kbo3q7j/w85t3dF87dAT/PHHOo444sdjFPyn35Bp2LALXBX3JNEr/eeihXe4= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1725626653; c=relaxed/simple; bh=ABYcwPzslWkTkcaqLIM352O67WdWCXbzFUufBo4Ohzk=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=eh0VUrQvns/FDn2trVXCyNW6T9ZVl96zS2skdQOT3ivgDc5b/8aS9Hc2aMNJiaQCW62P7Rha1uIXm/keyDcN8HSHG8iBZaYsrrVjw+/7pH+CUWn8o7laPgenaceLH1+VGPzmKK1sAauBK4cFbXr32KAwFyoxTA4PxTfiUptQjrc= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-ej1-x629.google.com with SMTP id a640c23a62f3a-a8a7596b7dfso297277566b.0 for ; Fri, 06 Sep 2024 05:44:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=vrull.eu; s=google; t=1725626649; x=1726231449; 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=v0VAQXXzxg6hEwU3Fc40gDj2X+rrgl3hXGCnWSEgxik=; b=eY10hgB13KGggkH6VI7+0PWgxr75cXkOddYtTaG04Jzu8ncunpI4dRqeSocbgMvivF hQrCLDnMmU/V2cCghfdbrlEwx/RCjhRu9JKWmmmOzD1mHGBq5YLQWP1s4f83ERfMjeAI AwZQbYBMvXA2d8pnlPcg5ALyctmqrKP75Nald5R2qo8XGkcWkHTQSym/2k+ZqFVGE+0C DdaUYfyY2VHDKRioAoljLrZ4tcDje/jfNCxqg2xWVnW3I0a2U8adW+RKUdXYDATzqDRW vekdiheXQLNv5GtlXhxG7Oq7lA4sCcCfUyRRLC+dl3picRAod/hXIHiaclwXvUbbuiyK 8GTg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1725626649; x=1726231449; 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=v0VAQXXzxg6hEwU3Fc40gDj2X+rrgl3hXGCnWSEgxik=; b=geiaUttKv6xBWthE+L7uKsrB1qAUEQZC+LRLJkVX46i1uWmoQJx/AB7Iip3422WXSM qWPW7u5FnBa3t/ofmNQPBzO/aRQlpYWnAuU8qGkPDo2e1HVkbiwBsk04qHi7cJVTa1FQ A+vz2DpEyRnYEjYIvGGs+IkLv1G4nhbgerm+2T81eXSDLmx2dbLdIMJLgo5pQmbfAhji A9/e/ASzGTRcFvhHWmdehOCqiMYNjYgplzarKtXG0J9bTC0DrXwpjJkMPTIKkWo4J3r9 oCMhLR9slKsZ2oRACd68NADcdq19roq4heIb/vE7xse65RnmWD4qHJgAUe68treqVjem 075g== X-Gm-Message-State: AOJu0YzsYAqdyJl75wVgO+HO0g35vc4jedaNwUhU3KUYYifY8AwMuxZd INrTUo2ZciYGjMBwe7MlzP8K7YTA7dndpMnLOLE7yzRCMBVu8oqWlYTspFr+KPyI9PbuIRzZ1FM QAYY= X-Google-Smtp-Source: AGHT+IEIyKCg/HMP03iBbrnuv68dYk7lOlp6S/vbMaVEpwM1jnekc1EB5oICyR8AdzFTsMwUMVA0tA== X-Received: by 2002:a17:906:4789:b0:a80:9c1b:554f with SMTP id a640c23a62f3a-a8a86442be2mr308999466b.27.1725626648826; Fri, 06 Sep 2024 05:44:08 -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-a8a78b09b26sm192924066b.24.2024.09.06.05.44.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 06 Sep 2024 05:44:08 -0700 (PDT) From: konstantinos.eleftheriou@vrull.eu To: gcc-patches@gcc.gnu.org, Philipp Tomsich , =?utf-8?q?Christoph_M=C3=BCllner?= Cc: kelefth Subject: [PATCH] match: Change (A * B) + (-C) to (B - C/A) * A, if C multiple of A [PR109393] Date: Fri, 6 Sep 2024 14:44:06 +0200 Message-ID: <20240906124406.3990973-1-konstantinos.eleftheriou@vrull.eu> X-Mailer: git-send-email 2.46.0 MIME-Version: 1.0 X-Spam-Status: No, score=-12.5 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, 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: , 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 | 15 ++++++++++++++- gcc/testsuite/gcc.dg/pr109393.c | 23 +++++++++++++++++++++++ 2 files changed, 37 insertions(+), 1 deletion(-) create mode 100644 gcc/testsuite/gcc.dg/pr109393.c diff --git a/gcc/match.pd b/gcc/match.pd index 621306213e4..9d971b663c6 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -4216,7 +4216,20 @@ 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. */ + (simplify + (plus (mult:cs@3 integer_nonzerop@0 @2) INTEGER_CST@4) + (if (TREE_CODE (type) == INTEGER_TYPE + && wi::neg_p (wi::to_wide (@4))) + (with { + wide_int c1 = wi::to_wide (@0); + wide_int c2_abs = wi::abs (wi::to_wide (@4)); + /* Calculate @4 / @0 in order to factorize the expression. */ + wide_int div_res = wi::div_trunc (c2_abs, c1, TYPE_SIGN (type)); + tree div_cst = wide_int_to_tree (type, div_res); } + (if (wi::multiple_of_p (c2_abs, c1, TYPE_SIGN (type))) + (mult (minus @2 { 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