This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH][GCC] Algorithmic optimization in match and simplify
- From: Andre Vieira <Andre dot SimoesDiasVieira at arm dot com>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>
- Date: Fri, 28 Aug 2015 17:56:57 +0100
- Subject: [PATCH][GCC] Algorithmic optimization in match and simplify
- Authentication-results: sourceware.org; auth=none
Two new algorithmic optimisations:
1.((X op0 C0) op1 C1) op2 C2)
with op0 = {&, >>, <<}, op1 = {|,^}, op2 = {|,^} and op1 != op2
zero_mask has 1's for all bits that are sure to be 0 in (X op0 C0)
and 0's otherwise.
if (op1 == '^') C1 &= ~C2 (Only changed if actually emitted)
if ((C1 & ~zero_mask) == 0) then emit (X op0 C0) op2 (C1 op2 C2)
if ((C2 & ~zero_mask) == 0) then emit (X op0 C0) op1 (C1 op2 C2)
2. (X {|,^,&} C0) {<<,>>} C1 -> (X {<<,>>} C1) {|,^,&} (C0 {<<,>>} C1)
This patch does two algorithmic optimisations that target patterns like:
(((x << 24) | 0x00FFFFFF) ^ 0xFF000000) and ((x ^ 0x40000002) >> 1) |
0x80000000.
The transformation uses the knowledge of which bits are zero after
operations like (X {&,<<,(unsigned)>>}) to combine constants, reducing
run-time operations.
The two examples above would be transformed into (X << 24) ^ 0xFFFFFFFF
and (X >> 1) ^ 0xa0000001 respectively.
gcc/ChangeLog:
2015-08-03 Andre Vieira <andre.simoesdiasvieira@arm.com>
* match.pd: Added new patterns:
((X {&,<<,>>} C0) {|,^} C1) {^,|} C2)
(X {|,^,&} C0) {<<,>>} C1 -> (X {<<,>>} C1) {|,^,&} (C0 {<<,>>} C1)
gcc/testsuite/ChangeLog:
2015-08-03 Andre Vieira <andre.simoesdiasvieira@arm.com>
* gcc.dg/tree-ssa/forwprop-33.c: New test.
From 15f86df5b3561edf26ae79cedbe160fd46596fd9 Mon Sep 17 00:00:00 2001
From: Andre Simoes Dias Vieira <andsim01@arm.com>
Date: Wed, 26 Aug 2015 16:27:31 +0100
Subject: [PATCH] algorithmic optimization
---
gcc/match.pd | 70 +++++++++++++++++++++++++++++
gcc/testsuite/gcc.dg/tree-ssa/forwprop-33.c | 42 +++++++++++++++++
2 files changed, 112 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/forwprop-33.c
diff --git a/gcc/match.pd b/gcc/match.pd
index eb0ba9d10a9b8ca66c23c56da0678477379daf80..3d9a8f52713e8dfb2189aad76bce709c924fa286 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -708,6 +708,76 @@ along with GCC; see the file COPYING3. If not see
&& tree_nop_conversion_p (type, TREE_TYPE (@1)))
(convert (bit_and (bit_not @1) @0))))
+/* (X bit_op C0) rshift C1 -> (X rshift C0) bit_op (C0 rshift C1) */
+(for bit_op (bit_ior bit_xor bit_and)
+(simplify
+ (rshift (bit_op:c @0 INTEGER_CST@1) INTEGER_CST@2)
+ (bit_op
+ (rshift @0 @2)
+ { wide_int_to_tree (type, wi::rshift (@1, @2, TYPE_SIGN (type))); })))
+
+/* (X bit_op C0) lshift C1 -> (X lshift C0) bit_op (C0 lshift C1) */
+(for bit_op (bit_ior bit_xor bit_and)
+(simplify
+ (lshift (bit_op:c @0 INTEGER_CST@1) INTEGER_CST@2)
+ (bit_op
+ (lshift @0 @2)
+ { wide_int_to_tree (type, wi::lshift (@1, @2)); })))
+
+
+/* ((X op0 C0) op1 C1) op2 C2)
+ with op0 = {&, >>, <<}, op1 = {|,^}, op2 = {|,^} and op1 != op2
+ zero_mask has 1's for all bits that are sure to be 0 in (X op0 C0)
+ and 0's otherwise.
+ if (op1 == '^') C1 &= ~C2;
+ if ((C1 & ~zero_mask) == 0) then emit (X op0 C0) op2 (C1 op2 C2)
+ if ((C2 & ~zero_mask) == 0) then emit (X op0 C0) op1 (C1 op2 C2)
+*/
+(for op0 (rshift rshift lshift lshift bit_and bit_and)
+ op1 (bit_ior bit_xor bit_ior bit_xor bit_ior bit_xor)
+ op2 (bit_xor bit_ior bit_xor bit_ior bit_xor bit_ior)
+(simplify
+ (op2:c
+ (op1:c
+ (op0 @0 INTEGER_CST@1) INTEGER_CST@2) INTEGER_CST@3)
+ (with
+ {
+ unsigned int prec = TYPE_PRECISION (type);
+ wide_int zero_mask = wi::zero (prec);
+ wide_int C0 = wide_int_storage (@1);
+ wide_int C1 = wide_int_storage (@2);
+ wide_int C2 = wide_int_storage (@3);
+ wide_int cst_emit;
+
+ if (op0 == BIT_AND_EXPR)
+ {
+ zero_mask = wide_int_storage (wi::neg (@1));
+ }
+ else if (op0 == LSHIFT_EXPR && wi::fits_uhwi_p (@1))
+ {
+ zero_mask = wide_int_storage (wi::mask (C0.to_uhwi (), false, prec));
+ }
+ else if (op0 == RSHIFT_EXPR && TYPE_UNSIGNED (type) && wi::fits_uhwi_p (@1))
+ {
+ unsigned HOST_WIDE_INT m = prec - C0.to_uhwi ();
+ zero_mask = wide_int_storage (wi::mask (m, true, prec));
+ }
+
+ if (op1 == BIT_XOR_EXPR)
+ {
+ C1 = wi::bit_and_not (C1,C2);
+ cst_emit = wi::bit_or (C1, C2);
+ }
+ else
+ {
+ cst_emit = wi::bit_xor (C1, C2);
+ }
+ }
+ (if ((C1 & ~zero_mask) == 0)
+ (op2 (op0 @0 @1) { wide_int_to_tree (type, cst_emit); })
+ (if ((C2 & ~zero_mask) == 0)
+ (op1 (op0 @0 @1) { wide_int_to_tree (type, cst_emit); }))))))
+
/* Associate (p +p off1) +p off2 as (p +p (off1 + off2)). */
(simplify
(pointer_plus (pointer_plus:s @0 @1) @3)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/forwprop-33.c b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-33.c
new file mode 100644
index 0000000000000000000000000000000000000000..984d8b37a01defe0e6852070a7dfa7ace5027c51
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-33.c
@@ -0,0 +1,42 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-forwprop1" } */
+
+unsigned short
+foo (unsigned short a)
+{
+ a ^= 0x4002;
+ a >>= 1;
+ a |= 0x8000; /* Simplify to ((a >> 1) ^ 0xa001). */
+ return a;
+}
+
+unsigned short
+bar (unsigned short a)
+{
+ a |= 0x4002;
+ a <<= 1;
+ a ^= 0x0001; /* Simplify to ((a << 1) | 0x8005). */
+ return a;
+}
+
+unsigned short
+baz (unsigned short a)
+{
+ a &= 0xd123;
+ a ^= 0x6040;
+ a |= 0xc031; /* Simplify to ((a & 0xd123) | 0xe071). */
+ return a;
+}
+
+short
+qux (short a)
+{
+ a ^= 0x8002;
+ a >>= 1;
+ a |= 0x8000; /* Only move shift inward: (((a >> 1) ^ 0x4001 |) 0x8000). */
+ return a;
+}
+/* { dg-final { scan-tree-dump "\\^ 40961" "forwprop1" } } */
+/* { dg-final { scan-tree-dump "\\| 32773" "forwprop1" } } */
+/* { dg-final { scan-tree-dump "\\| 57457" "forwprop1" } } */
+/* { dg-final { scan-tree-dump "\\^ -16383" "forwprop1" } } */
--
1.9.1