public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* Re: [PATCH][GCC] Simplification of 1U << (31 - x)
@ 2017-04-13 11:16 Wilco Dijkstra
  2017-04-13 11:21 ` Jakub Jelinek
  0 siblings, 1 reply; 24+ messages in thread
From: Wilco Dijkstra @ 2017-04-13 11:16 UTC (permalink / raw)
  To: Jakub Jelinek, Sudi Das
  Cc: GCC Patches, nd, Richard Earnshaw, James Greenhalgh

>On Wed, Apr 12, 2017 at 09:29:55AM +0000, Sudi Das wrote:
> > Hi all
> > 
> > This is a fix for PR 80131 
> > Currently the code A << (B - C) is not simplified.
>> However at least a more specific case of 1U << (C -x) where C = precision(type) - 1 can be simplified to (1 << C) >> x.
>
> Is that always a win though?

Yes assuming left and right shift have the same performance.

> Some constants have higher costs than others on various targets, some
> significantly higher.  This change might be beneficial only
> if if C is as expensive as 1, then you get rid of a one (typically cheap)
> operation.

Most targets can create the constant cheaply. Targets that can't would need 2
instructions (move+shift) or a literal load. That's not worse compared to the
original sequence (3 operations). The constant can be shared or lifted out of
a loop, so we're saving 1 subtract per use of the sequence.

> Which makes me wonder whether this should be done at GIMPLE time and not
> at RTL time (expansion or combine etc.) when one can compare the RTX costs.
> Or do this at match.pd as canonicalization and then have RTL transformation
> to rewrite such (1U << C) >> X as 1U << (C - X) if the latter is faster (or
> shorter).

I can't see why that would be useful for just this pattern. There are lots more useful
cases where GCC should simplify immediates to fit the target but it doesn't currently.
For example it changes x < 0x100000 to x <= 0xfffff which is worse on many targets.

Wilco

^ permalink raw reply	[flat|nested] 24+ messages in thread
* [PATCH][GCC] Simplification of 1U << (31 - x)
@ 2017-04-12  9:30 Sudi Das
  2017-04-12 17:06 ` Jakub Jelinek
  0 siblings, 1 reply; 24+ messages in thread
From: Sudi Das @ 2017-04-12  9:30 UTC (permalink / raw)
  To: gcc-patches; +Cc: Marcus Shawcroft, Richard Earnshaw, James Greenhalgh, nd

[-- Attachment #1: Type: text/plain, Size: 1006 bytes --]

Hi all

This is a fix for PR 80131 
Currently the code A << (B - C) is not simplified.
However at least a more specific case of 1U << (C -x) where C = precision(type) - 1 can be simplified to (1 << C) >> x.

This is done by adding a new simplification rule in match.pd

So for a test case :

unsigned int f1(unsigned int i)
{
  return 1U << (31 - i);
}

We see a gimple dump of 

f1 (unsigned int i)
{
  unsigned int D.3121;

  D.3121 = 2147483648 >> i;
  return D.3121;
}

instead of 

f1 (unsigned int i)
{
  unsigned int D.3121;

  _1 = 31 - i;
  D.3121 = 1 << _1;
  return D.3121;
}


Add a new test case and checked for regressions on bootstrapped aarch64-none-linux-gnu.
Ok for stage 1?

Thanks
Sudi

2017-03-23  Sudakshina Das  <sudi.das@arm.com>

	PR middle-end/80131
	* match.pd: Simplify 1 << (C - x) where C = precision (type) - 1.

2017-03-23  Sudakshina Das  <sudi.das@arm.com>

	PR middle-end/80131
	* testsuite/gcc.dg/pr80131-1.c: New Test.

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: patch-7259-4(1).diff --]
[-- Type: text/x-patch; name="patch-7259-4(1).diff", Size: 1815 bytes --]

diff --git a/gcc/match.pd b/gcc/match.pd
index 7b96800..be20fb7 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -508,6 +508,19 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
        && tree_nop_conversion_p (type, TREE_TYPE (@1)))
    (lshift @0 @2)))
 
+/* Fold (1 << (C - x)) where C = precision(type) - 1
+   into ((1 << C) >> x). */
+(simplify
+ (lshift integer_onep@0 (minus INTEGER_CST@1 @2))
+  (if (INTEGRAL_TYPE_P (type)
+       && TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT
+       && tree_to_uhwi (@1) == (unsigned)(TYPE_PRECISION (type) - 1))
+   (if (TYPE_UNSIGNED(type))
+     (rshift (lshift @0 @1) @2)
+   (with
+    { tree utype = unsigned_type_for (type); }
+    (convert:type (rshift (lshift (convert:utype @0) @1) @2))))))
+
 /* Fold (C1/X)*C2 into (C1*C2)/X.  */
 (simplify
  (mult (rdiv@3 REAL_CST@0 @1) REAL_CST@2)
diff --git a/gcc/testsuite/gcc.dg/pr80131-1.c b/gcc/testsuite/gcc.dg/pr80131-1.c
new file mode 100644
index 0000000..2bb6ff3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr80131-1.c
@@ -0,0 +1,30 @@
+/* { dg-do compile } */
+/* { dg-options "-fdump-tree-gimple" } */
+
+/* Checks the simplification of:
+   1 << (C - x) to (1 << C) >> x, where C = precision (type) - 1
+   f1 is not simplified but f2, f3 and f4 are. */
+
+__INT64_TYPE__ f1 (__INT64_TYPE__ i)
+{
+  return (__INT64_TYPE__)1 << (31 - i);
+}
+
+__INT64_TYPE__ f2 (__INT64_TYPE__ i)
+{
+  return (__INT64_TYPE__)1 << (63 - i);
+}
+
+__UINT64_TYPE__ f3 (__INT64_TYPE__ i)
+{
+  return (__UINT64_TYPE__)1 << (63 - i);
+}
+
+__INT32_TYPE__ f4 (__INT32_TYPE__ i)
+{
+  return (__INT32_TYPE__)1 << (31 - i);
+}
+
+/* { dg-final { scan-tree-dump-times "= 31 -"  1 "gimple" } } */
+/* { dg-final { scan-tree-dump-times "9223372036854775808 >>" 2 "gimple" } } */
+/* { dg-final { scan-tree-dump "2147483648 >>" "gimple" } } */

^ permalink raw reply	[flat|nested] 24+ messages in thread
end of thread, other threads:[~2017-11-07 13:42 UTC | newest]

Thread overview: 24+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-04-13 11:16 [PATCH][GCC] Simplification of 1U << (31 - x) Wilco Dijkstra
2017-04-13 11:21 ` Jakub Jelinek
2017-04-13 11:33   ` Wilco Dijkstra
2017-04-13 11:41     ` Jakub Jelinek
2017-04-13 11:49       ` Richard Biener
2017-04-13 11:55         ` Jakub Jelinek
2017-04-13 12:01         ` Wilco Dijkstra
2017-08-01  9:15           ` Sudi Das
2017-08-04 10:16             ` Richard Biener
2017-09-26 12:44               ` Sudi Das
2017-09-26 13:06                 ` Jakub Jelinek
2017-09-26 13:20                   ` Wilco Dijkstra
2017-10-06 17:00                     ` Sudi Das
2017-10-09 12:05                 ` Richard Biener
2017-10-09 13:04                   ` Wilco Dijkstra
2017-10-10 11:12                     ` Sudi Das
2017-11-07 12:37                       ` Wilco Dijkstra
2017-11-07 14:48                         ` Christophe Lyon
2017-11-07 14:49                           ` Wilco Dijkstra
  -- strict thread matches above, loose matches on Subject: below --
2017-04-12  9:30 Sudi Das
2017-04-12 17:06 ` Jakub Jelinek
2017-04-12 18:16   ` Segher Boessenkool
2017-04-12 18:59     ` Jakub Jelinek
2017-04-12 19:34       ` Segher Boessenkool

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).