From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 A51323858D35 for ; Fri, 27 Oct 2023 06:56:48 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org A51323858D35 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org A51323858D35 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=1698389811; cv=none; b=m059GAbl8sFchTWKAtsCRQ70YdYcUG90HQDZDNMH2NhOFmhzCc5RUIMVAZKvClm2htqFLcWiU4y4sJk8A7k8a48Tyq0eyi4qDNucWnO1ROEKbpxop6QAxKk4e8y+RDm0qs1pm+EIvf0vR9FWfCQVGJ6y3JtB8FHkT0r4VjAX1RE= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1698389811; c=relaxed/simple; bh=aRg5+f4j3eNULt2xSIqoUmt0tpdGKYzQuyVKAQCmRX4=; h=DKIM-Signature:From:Mime-Version:Subject:Date:Message-Id:To; b=C6FOEZohfQb986wJ2cgCbv5OTiYsfiavTfHaBC75yb9w/+AJssB+s08GdFG2VAQm12G4Njf9LniMwaqIfjRbR7qJ0Y4yqlNeyQve+yQfWjg8677bhrfxXh1WMgoKA4VGrvjIjPZ41EPDXCv+HZHnaGA/efUVsdoxFUIgr7xhIzc= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-ej1-x629.google.com with SMTP id a640c23a62f3a-9c603e235d1so271050766b.3 for ; Thu, 26 Oct 2023 23:56:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1698389807; x=1698994607; darn=gcc.gnu.org; h=to:in-reply-to:cc:references:message-id:date:subject:mime-version :from:content-transfer-encoding:from:to:cc:subject:date:message-id :reply-to; bh=qpVXBhqW7IGVSzAdl72SRaRvQ2sGEBSW0OjeDpoCr0I=; b=EPK4YELRgY9AGPqEo5nQU63Tswc+ZeWE33WDtiDzQC2ZlHI79MpaHzfwOpNYv7OwgF mTU4hXOoZMSR9dFZ/Srfecc8xF2sVmkUQDQe67dhuAtBxVDIkCLJibM+2cRqK3WMvHa0 GEZGMco9gz4vh/KsSyvqdvGUl+hN3vvE+UtibLPxbH0I6ybNHXiyguk8lfqwujgOcsym OayuKKeC1d4WMbY6Ve5JE4BBO7TaATwB13Zv3xJOUDfN5Hsp8vOdGcO1KuTBO4RYvgFM F5dy7cXYSO9wC5+HNLnpCiYHQMiaPm6S0TSoiug6BiJvRkCv09Ub+vXHNo8hzIcDPKsc QrxA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698389807; x=1698994607; h=to:in-reply-to:cc:references:message-id:date:subject:mime-version :from:content-transfer-encoding:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=qpVXBhqW7IGVSzAdl72SRaRvQ2sGEBSW0OjeDpoCr0I=; b=ML9Crg6prnB4TMXnPj0wnOYVe03RGNOPK2si3RU8wlXUFQu+fkrYPSc0wu+H7zKWQ0 C+zTEMp5EIVwr1xj12qWqhrK3+7oEqv35MXw5Gxb3kpj3otYnlGVGoac4Iyy328ryT/Q JRokUKXJHOGxafuH/X8eSxhob87ShYjDqKqo74M4jnMV8B5URrbCbz/7IdduJ8eAoetO KdUGJ+ye0rwS3FHEPsG+Ng8BLBy6AMm55+O0DPvXoFcldrMYMuJG4Enj2P8lzcwN220/ R3xE/7J9sckZ2na73iWpMBQaP2DXPpio8hTLTaQXQnOV0zEQZAh3ZS42x9SBvRtUA7Ce j1hg== X-Gm-Message-State: AOJu0Yzbdfabs6KZ68P81JG/PAgmIp4sIB+u1A7YvCaUmrmxYtVSKkUT WEzyd4LmvpiTQw6oTl4mNaAQUz3fENk= X-Google-Smtp-Source: AGHT+IEl4z+QUifNfh/lpBYtJSFBqIwXobmxSTchQ+//0z+CQf30YTM8FUiEPN+6HWMHOCLimUZPvA== X-Received: by 2002:a17:906:fe0c:b0:9be:1bde:d4b with SMTP id wy12-20020a170906fe0c00b009be1bde0d4bmr1392295ejb.44.1698389806518; Thu, 26 Oct 2023 23:56:46 -0700 (PDT) Received: from smtpclient.apple (dynamic-095-117-023-019.95.117.pool.telefonica.de. [95.117.23.19]) by smtp.gmail.com with ESMTPSA id kg12-20020a17090776ec00b009932337747esm696410ejc.86.2023.10.26.23.56.45 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 26 Oct 2023 23:56:45 -0700 (PDT) Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable From: Richard Biener Mime-Version: 1.0 (1.0) Subject: Re: [PATCH] MATCH: Simplify `(X &| B) CMP X` if possible [PR 101590] Date: Fri, 27 Oct 2023 08:56:35 +0200 Message-Id: <24B3B859-0A59-4699-8C3D-2C6D5D4450BF@gmail.com> References: <20231026210949.2881006-1-pinskia@gmail.com> Cc: gcc-patches@gcc.gnu.org, Andrew Pinski In-Reply-To: <20231026210949.2881006-1-pinskia@gmail.com> To: Andrew Pinski X-Mailer: iPhone Mail (20H115) X-Spam-Status: No, score=-10.6 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,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 List-Id: > Am 26.10.2023 um 23:10 schrieb Andrew Pinski : >=20 > =EF=BB=BFFrom: Andrew Pinski >=20 > I noticed we were missing these simplifications so let's add them. >=20 > This adds the following simplifications: > U & N <=3D U -> true > U & N > U -> false > When U is known to be as non-negative. >=20 > When N is also known to be non-negative, this is also true: > U | N < U -> false > U | N >=3D U -> true >=20 > When N is a negative integer, the result flips and we get: > U | N < U -> true > U | N >=3D U -> false I think bit-CCP should get this, does ranger also figure this out (iirc it t= racks nonzero bits?) Your testcases suggest this doesn=E2=80=99t happen, can you figure out why C= CP doesn=E2=80=99t optimize this and maybe file a bug? > We could extend this later on to be the case where we know N > is nonconstant but is known to be negative. >=20 > Bootstrapped and tested on x86_64-linux-gnu with no regressions. Ok Richard=20 > PR tree-optimization/101590 > PR tree-optimization/94884 >=20 > gcc/ChangeLog: >=20 > * match.pd (`(X BIT_OP Y) CMP X`): New pattern. >=20 > gcc/testsuite/ChangeLog: >=20 > * gcc.dg/tree-ssa/bitcmp-1.c: New test. > * gcc.dg/tree-ssa/bitcmp-2.c: New test. > * gcc.dg/tree-ssa/bitcmp-3.c: New test. > * gcc.dg/tree-ssa/bitcmp-4.c: New test. > * gcc.dg/tree-ssa/bitcmp-5.c: New test. > * gcc.dg/tree-ssa/bitcmp-6.c: New test. > --- > gcc/match.pd | 24 +++++++++++++ > gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c | 20 +++++++++++ > gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c | 20 +++++++++++ > gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c | 21 ++++++++++++ > gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c | 36 ++++++++++++++++++++ > gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c | 43 ++++++++++++++++++++++++ > gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c | 41 ++++++++++++++++++++++ > 7 files changed, 205 insertions(+) > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c >=20 > diff --git a/gcc/match.pd b/gcc/match.pd > index 5f6aeb07ac0..7d651a6582d 100644 > --- a/gcc/match.pd > +++ b/gcc/match.pd > @@ -2707,6 +2707,30 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) > (if (TREE_INT_CST_LOW (@1) & 1) > { constant_boolean_node (cmp =3D=3D NE_EXPR, type); }))) >=20 > +/* > + U & N <=3D U -> true > + U & N > U -> false > + U needs to be non-negative. > + > + U | N < U -> false > + U | N >=3D U -> true > + U and N needs to be non-negative > + > + U | N < U -> true > + U | N >=3D U -> false > + U needs to be non-negative and N needs to be a negative constant. > + */ > +(for cmp (lt ge le gt ) > + bitop (bit_ior bit_ior bit_and bit_and) > + (simplify > + (cmp:c (bitop:c tree_expr_nonnegative_p@0 @1) @0) > + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))) > + (if (bitop =3D=3D BIT_AND_EXPR || tree_expr_nonnegative_p (@1)) > + { constant_boolean_node (cmp =3D=3D GE_EXPR || cmp =3D=3D LE_EXPR, ty= pe); } > + /* The sign is opposite now so the comparison is swapped around. */ > + (if (TREE_CODE (@1) =3D=3D INTEGER_CST && wi::neg_p (wi::to_wide (@1)= )) > + { constant_boolean_node (cmp =3D=3D LT_EXPR, type); }))))) > + > /* Arguments on which one can call get_nonzero_bits to get the bits > possibly set. */ > (match with_possible_nonzero_bits > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c b/gcc/testsuite/gcc.= dg/tree-ssa/bitcmp-1.c > new file mode 100644 > index 00000000000..f3d515bb2d6 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c > @@ -0,0 +1,20 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-optimized" } */ > +/* PR tree-optimization/101590 */ > + > +int f_and_le(unsigned len) { > + const unsigned N =3D 4; > + unsigned newlen =3D len & -N; > + return newlen <=3D len; // return 1 > +} > +int f_or_ge(unsigned len) { > + const unsigned N =3D 4; > + unsigned newlen =3D len | -N; > + return newlen >=3D len; // return 1 > +} > + > +/* { dg-final { scan-tree-dump-not " <=3D " "optimized" } } */ > +/* { dg-final { scan-tree-dump-not " >=3D " "optimized" } } */ > +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */ > +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */ > +/* { dg-final { scan-tree-dump-times "return 1;" 2 "optimized" } } */ > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c b/gcc/testsuite/gcc.= dg/tree-ssa/bitcmp-2.c > new file mode 100644 > index 00000000000..d0031d9ecb8 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c > @@ -0,0 +1,20 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-optimized" } */ > +/* PR tree-optimization/101590 */ > + > +int f_and_gt(unsigned len) { > + const unsigned N =3D 4; > + unsigned newlen =3D len & -N; > + return newlen > len; // return 0 > +} > +int f_or_lt(unsigned len) { > + const unsigned N =3D 4; > + unsigned newlen =3D len | -N; > + return newlen < len; // return 0 > +} > + > +/* { dg-final { scan-tree-dump-not " > " "optimized" } } */ > +/* { dg-final { scan-tree-dump-not " < " "optimized" } } */ > +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */ > +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */ > +/* { dg-final { scan-tree-dump-times "return 0;" 2 "optimized" } } */ > \ No newline at end of file > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c b/gcc/testsuite/gcc.= dg/tree-ssa/bitcmp-3.c > new file mode 100644 > index 00000000000..5cfab7dc742 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c > @@ -0,0 +1,21 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-optimized" } */ > +/* PR tree-optimization/94884 */ > + > +#define bool _Bool > +bool decide() __attribute((const)); > + > +inline unsigned getXOrY(unsigned x, unsigned y) > +{ > + return decide() ? y : x; > +} > + > +bool f(unsigned x, unsigned y) > +{ > + return (x | y) >=3D getXOrY(x, y); > +} > + > + > +/* { dg-final { scan-tree-dump-not " >=3D " "optimized" } } */ > +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */ > +/* { dg-final { scan-tree-dump-times "return 1;" 1 "optimized" } } */ > \ No newline at end of file > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c b/gcc/testsuite/gcc.= dg/tree-ssa/bitcmp-4.c > new file mode 100644 > index 00000000000..701014b2d0e > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c > @@ -0,0 +1,36 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-optimized" } */ > +/* PR tree-optimization/101590 */ > + > +int f_and_le(int len) { > + const int N =3D 4; > + int newlen =3D len & -N; > + return newlen <=3D len; > +} > +int f_or_ge(int len) { > + const int N =3D 4; > + int newlen =3D len | -N; > + return newlen >=3D len; > +} > + > +int f_and_gt(int len) { > + const int N =3D 4; > + int newlen =3D len & -N; > + return newlen > len; > +} > +int f_or_lt(int len) { > + const int N =3D 4; > + int newlen =3D len | -N; > + return newlen < len; > +} > + > +/* These cannot be optimized since we don't know if the sign > + can change or not. */ > +/* { dg-final { scan-tree-dump-times " > " 1 "optimized" } } */ > +/* { dg-final { scan-tree-dump-times " < " 1 "optimized" } } */ > +/* { dg-final { scan-tree-dump-times " <=3D " 1 "optimized" } } */ > +/* { dg-final { scan-tree-dump-times " >=3D " 1 "optimized" } } */ > +/* { dg-final { scan-tree-dump-times " & " 2 "optimized" } } */ > +/* { dg-final { scan-tree-dump-times " \\\| " 2 "optimized" } } */ > +/* { dg-final { scan-tree-dump-not "return 1;" "optimized" } } */ > +/* { dg-final { scan-tree-dump-not "return 0;" "optimized" } } */ > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c b/gcc/testsuite/gcc.= dg/tree-ssa/bitcmp-5.c > new file mode 100644 > index 00000000000..a6be14294b4 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c > @@ -0,0 +1,43 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-optimized" } */ > +/* PR tree-optimization/101590 */ > + > +/* These are the signed integer versions > + of `(a & b) CMP a` and `(a | b) CMP a` > + which can be optimized to 1. */ > + > + > +/* For `&`, the non-negativeness of b is not taken into account. */ > +int f_and_le(int len) { > + len &=3D 0xfffff; > + const int N =3D 4; > + int newlen =3D len & -N; > + return newlen <=3D len; // return 1 > +} > +int f_and_le_(int len, int N) { > + len &=3D 0xfffff; > + int newlen =3D len & -N; > + return newlen <=3D len; // return 1 > +} > + > + > +/* For `|`, to get a known value, b either needs to be non-negative > + or a constant. For the negative constant case, we swap around the com= parison. */ > +int f_or_ge_(int len, int N) { > + len &=3D 0xfffff; > + N &=3D 0xffff; > + int newlen =3D len | N; > + return newlen >=3D len; // return 1 > +} > +int f_or_lt(int len) { > + len &=3D 0xfffff; > + const int N =3D 4; > + int newlen =3D len | -N; > + return newlen < len; // return 1 > +} > + > +/* { dg-final { scan-tree-dump-not " <=3D " "optimized" } } */ > +/* { dg-final { scan-tree-dump-not " >=3D " "optimized" } } */ > +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */ > +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */ > +/* { dg-final { scan-tree-dump-times "return 1;" 4 "optimized" } } */ > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c b/gcc/testsuite/gcc.= dg/tree-ssa/bitcmp-6.c > new file mode 100644 > index 00000000000..a86a19fbef2 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c > @@ -0,0 +1,41 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-optimized" } */ > +/* PR tree-optimization/101590 */ > + > +/* These are the signed integer versions > + of `(a & b) CMP a` and `(a | b) CMP a` > + which can be optimized to 0. */ > + > +/* For `&`, the non-negativeness of b is not taken into account. */ > +int f_and_gt(int len) { > + len &=3D 0xfffff; > + const int N =3D 4; > + int newlen =3D len & -N; > + return newlen > len; // return 0 > +} > +int f_and_gt_(int len, int N) { > + len &=3D 0xfffff; > + int newlen =3D len & -N; > + return newlen > len; // return 0 > +} > + > +/* For `|`, to get a known value, b either needs to be non-negative > + or a constant. For the negative constant case, we swap around the com= parison. */ > +int f_or_lt_(int len, int N) { > + len &=3D 0xfffff; > + N &=3D 0xffff; > + int newlen =3D len | N; > + return newlen < len; // return 0 > +} > +int f_or_ge(int len) { > + len &=3D 0xfffff; > + const int N =3D 4; > + int newlen =3D len | -N; > + return newlen >=3D len; // return 0 > +} > + > +/* { dg-final { scan-tree-dump-not " > " "optimized" } } */ > +/* { dg-final { scan-tree-dump-not " < " "optimized" } } */ > +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */ > +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */ > +/* { dg-final { scan-tree-dump-times "return 0;" 4 "optimized" } } */ > --=20 > 2.39.3 >=20