From: Marek Polacek <polacek@redhat.com>
To: GCC Patches <gcc-patches@gcc.gnu.org>
Subject: [PATCH] Optimize (CST1 << A) == CST2 (PR tree-optimization/66299)
Date: Thu, 28 May 2015 12:33:00 -0000 [thread overview]
Message-ID: <20150528121545.GE27320@redhat.com> (raw)
This PR points out that we weren't able to optimize 1 << x == 2 to just
x == 1. This is my attempt to fix that: if we see (CST1 << A) == CST2
and CST2 is a multiple of CST1, use log2 to get rid of the shift, but
only if the result of the shift is a natural number (including zero).
If CST2 is not a multiple of CST1, then the whole expression can be
discarded, but I'd like to do that as a follow-up.
(It would help if our current match.pd grammar allowed us to use "else",
any plans on doing that?)
Bootstrapped/regtested on x86_64-linux, ok for trunk?
2015-05-28 Marek Polacek <polacek@redhat.com>
PR tree-optimization/66299
* match.pd ((CST1 << A) == CST2 -> A == log2 (CST2 / CST1),
(CST1 << A) != CST2 -> A != log2 (CST2 / CST1)): New
patterns.
* gcc.dg/pr66299-1.c: New test.
* gcc.dg/pr66299-2.c: New test.
diff --git gcc/match.pd gcc/match.pd
index abd7851..5d07a70 100644
--- gcc/match.pd
+++ gcc/match.pd
@@ -676,6 +676,19 @@ along with GCC; see the file COPYING3. If not see
(cmp (bit_and (lshift integer_onep @0) integer_onep) integer_zerop)
(icmp @0 { build_zero_cst (TREE_TYPE (@0)); })))
+/* (CST1 << A) == CST2 -> A == log2 (CST2 / CST1)
+ (CST1 << A) != CST2 -> A != log2 (CST2 / CST1)
+ if CST2 is a multiple of CST1. */
+(for cmp (ne eq)
+ (simplify
+ (cmp (lshift@3 INTEGER_CST@0 @1) INTEGER_CST@2)
+ (if ((TREE_CODE (@3) != SSA_NAME || has_single_use (@3))
+ && wi::multiple_of_p (@2, @0, TYPE_SIGN (type)))
+ (with {
+ int shift = wi::exact_log2 (wi::div_trunc (@2, @0, TYPE_SIGN (type))); }
+ (if (shift != -1)
+ (cmp @1 { build_int_cst (TREE_TYPE (@1), shift); }))))))
+
/* Simplifications of conversions. */
/* Basic strip-useless-type-conversions / strip_nops. */
diff --git gcc/testsuite/gcc.dg/pr66299-1.c gcc/testsuite/gcc.dg/pr66299-1.c
index e69de29..9d41275 100644
--- gcc/testsuite/gcc.dg/pr66299-1.c
+++ gcc/testsuite/gcc.dg/pr66299-1.c
@@ -0,0 +1,83 @@
+/* PR tree-optimization/66299 */
+/* { dg-do run } */
+/* { dg-options "-fdump-tree-original" } */
+
+void
+test1 (int x)
+{
+ if ((0 << x) != 0
+ || (1 << x) != 2
+ || (2 << x) != 4
+ || (3 << x) != 6
+ || (4 << x) != 8
+ || (5 << x) != 10
+ || (6 << x) != 12
+ || (7 << x) != 14
+ || (8 << x) != 16
+ || (9 << x) != 18
+ || (10 << x) != 20)
+ __builtin_abort ();
+}
+
+void
+test2 (int x)
+{
+ if (!((0 << x) == 0
+ && (1 << x) == 4
+ && (2 << x) == 8
+ && (3 << x) == 12
+ && (4 << x) == 16
+ && (5 << x) == 20
+ && (6 << x) == 24
+ && (7 << x) == 28
+ && (8 << x) == 32
+ && (9 << x) == 36
+ && (10 << x) == 40))
+ __builtin_abort ();
+}
+
+void
+test3 (unsigned int x)
+{
+ if ((0U << x) != 0U
+ || (1U << x) != 16U
+ || (2U << x) != 32U
+ || (3U << x) != 48U
+ || (4U << x) != 64U
+ || (5U << x) != 80U
+ || (6U << x) != 96U
+ || (7U << x) != 112U
+ || (8U << x) != 128U
+ || (9U << x) != 144U
+ || (10U << x) != 160U)
+ __builtin_abort ();
+}
+
+void
+test4 (unsigned int x)
+{
+ if (!((0U << x) == 0U
+ || (1U << x) == 8U
+ || (2U << x) == 16U
+ || (3U << x) == 24U
+ || (4U << x) == 32U
+ || (5U << x) == 40U
+ || (6U << x) == 48U
+ || (7U << x) == 56U
+ || (8U << x) == 64U
+ || (9U << x) == 72U
+ || (10U << x) == 80U))
+ __builtin_abort ();
+}
+
+int
+main (void)
+{
+ test1 (1);
+ test2 (2);
+ test3 (4U);
+ test4 (3U);
+}
+
+/* { dg-final { scan-tree-dump-not "<<" "original" } } */
+/* { dg-final { cleanup-tree-dump "original" } } */
diff --git gcc/testsuite/gcc.dg/pr66299-2.c gcc/testsuite/gcc.dg/pr66299-2.c
index e69de29..dde0549 100644
--- gcc/testsuite/gcc.dg/pr66299-2.c
+++ gcc/testsuite/gcc.dg/pr66299-2.c
@@ -0,0 +1,34 @@
+/* PR tree-optimization/66299 */
+/* { dg-do run } */
+/* { dg-options "-fdump-tree-optimized -O" } */
+
+void
+test1 (int x, unsigned u)
+{
+ if ((1U << x) != 64
+ || (2 << x) != u
+ || (x << x) != 384
+ || (3 << x) == 9
+ || (x << 14) != 98304U
+ || (1 << x) == 14
+ || (3 << 2) != 12)
+ __builtin_abort ();
+}
+
+void
+test2 (int x)
+{
+ unsigned int t = ((unsigned int) 1U << x);
+ if (t != 2U)
+ __builtin_abort ();
+}
+
+int
+main (void)
+{
+ test1 (6, 128U);
+ test2 (1);
+}
+
+/* { dg-final { scan-tree-dump-not "<<" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Marek
next reply other threads:[~2015-05-28 12:15 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-05-28 12:33 Marek Polacek [this message]
2015-05-28 13:10 ` Jakub Jelinek
2015-05-28 20:33 ` Marc Glisse
2015-06-08 15:12 ` Marek Polacek
2015-06-08 17:14 ` Marc Glisse
2015-06-09 7:56 ` Richard Biener
2015-06-09 11:46 ` Marc Glisse
2015-06-09 11:49 ` Richard Biener
2015-06-09 11:57 ` Richard Biener
2015-06-09 12:13 ` Marc Glisse
2015-06-09 12:22 ` Richard Biener
2015-06-09 13:46 ` Marek Polacek
2015-06-09 14:11 ` Richard Biener
2015-05-28 13:16 ` Richard Biener
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20150528121545.GE27320@redhat.com \
--to=polacek@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).