From 84ff66b884e9a67d83fa58c659a3aff52b38e138 Mon Sep 17 00:00:00 2001 From: Andre Vieira Date: Fri, 9 Oct 2015 16:08:35 +0000 Subject: [PATCH] [PATCH V3][GCC] Algorithmic optimization in match and simplify gcc/ChangeLog * match.pd: ((X inner_op C0) outer_op C1) New pattern. ((X & C2) << C1): Expand to... (X {&,^,|} C2 << C1): ...This. ((X & C2) >> C1): Expand to... (X {&,^,|} C2 >> C1): ...This. gcc/testsuite/ChangeLog * gcc.dg/tree-ssa/forwprop-33.c: New. Co-Authored-By: Hale Wang From-SVN: r228661 --- gcc/ChangeLog | 8 +++ gcc/match.pd | 60 +++++++++++++++-- gcc/testsuite/ChangeLog | 5 ++ gcc/testsuite/gcc.dg/tree-ssa/forwprop-33.c | 71 +++++++++++++++++++++ 4 files changed, 137 insertions(+), 7 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/forwprop-33.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index cca2a8b5241..6156bd09c02 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,11 @@ +2015-10-09 Andre Vieira + + * match.pd: ((X inner_op C0) outer_op C1) New pattern. + ((X & C2) << C1): Expand to... + (X {&,^,|} C2 << C1): ...This. + ((X & C2) >> C1): Expand to... + (X {&,^,|} C2 >> C1): ...This. + 2015-10-09 Alexander Fomin PR target/67895 diff --git a/gcc/match.pd b/gcc/match.pd index 170d73e9fa6..b02dd03430d 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -710,6 +710,51 @@ 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 inner_op C0) outer_op C1) + With X being a tree where value_range has reasoned certain bits to always be + zero throughout its computed value range, + inner_op = {|,^}, outer_op = {|,^} and inner_op != outer_op + where zero_mask has 1's for all bits that are sure to be 0 in + and 0's otherwise. + if (inner_op == '^') C0 &= ~C1; + if ((C0 & ~zero_mask) == 0) then emit (X outer_op (C0 outer_op C1) + if ((C1 & ~zero_mask) == 0) then emit (X inner_op (C0 outer_op C1) +*/ +(for inner_op (bit_ior bit_xor) + outer_op (bit_xor bit_ior) +(simplify + (outer_op + (inner_op:s @2 INTEGER_CST@0) INTEGER_CST@1) + (with + { + bool fail = false; + wide_int zero_mask_not; + wide_int C0; + wide_int cst_emit; + + if (TREE_CODE (@2) == SSA_NAME) + zero_mask_not = get_nonzero_bits (@2); + else + fail = true; + + if (inner_op == BIT_XOR_EXPR) + { + C0 = wi::bit_and_not (@0, @1); + cst_emit = wi::bit_or (C0, @1); + } + else + { + C0 = @0; + cst_emit = wi::bit_xor (@0, @1); + } + } + (if (!fail && wi::bit_and (C0, zero_mask_not) == 0) + (outer_op @2 { wide_int_to_tree (type, cst_emit); }) + (if (!fail && wi::bit_and (@1, zero_mask_not) == 0) + (inner_op @2 { 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) @@ -1103,14 +1148,15 @@ along with GCC; see the file COPYING3. If not see (bit_and (convert (shift:shift_type (convert @3) @1)) { newmaskt; }) (bit_and @4 { newmaskt; }))))))))))))) -/* Fold (X & C2) << C1 into (X << C1) & (C2 << C1) - (X & C2) >> C1 into (X >> C1) & (C2 >> C1). */ +/* Fold (X {&,^,|} C2) << C1 into (X << C1) {&,^,|} (C2 << C1) + (X {&,^,|} C2) >> C1 into (X >> C1) & (C2 >> C1). */ (for shift (lshift rshift) - (simplify - (shift (convert?:s (bit_and:s @0 INTEGER_CST@2)) INTEGER_CST@1) - (if (tree_nop_conversion_p (type, TREE_TYPE (@0))) - (with { tree mask = int_const_binop (shift, fold_convert (type, @2), @1); } - (bit_and (shift (convert @0) @1) { mask; }))))) + (for bit_op (bit_and bit_xor bit_ior) + (simplify + (shift (convert?:s (bit_op:s @0 INTEGER_CST@2)) INTEGER_CST@1) + (if (tree_nop_conversion_p (type, TREE_TYPE (@0))) + (with { tree mask = int_const_binop (shift, fold_convert (type, @2), @1); } + (bit_op (shift (convert @0) @1) { mask; })))))) /* Simplifications of conversions. */ diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index f84b8ca38ad..929bfa57a97 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2015-10-09 Andre Vieira + Hale Wang + + * gcc.dg/tree-ssa/forwprop-33.c: New. + 2015-10-09 Alexander Fomin PR target/67895 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 00000000000..c7124deee11 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-33.c @@ -0,0 +1,71 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-forwprop3" } */ + +unsigned short +test1 (unsigned short a) +{ + a ^= 0x4002; + a >>= 1; + a |= 0x8000; /* Simplify to ((a >> 1) ^ 0xa001). */ + return a; +} +/* { dg-final { scan-tree-dump "\\^ 40961" "forwprop3" } } */ + +unsigned short +test2 (unsigned short a) +{ + a |= 0x4002; + a <<= 1; + a ^= 0x0001; /* Simplify to ((a << 1) | 0x8005). */ + return a; +} +/* { dg-final { scan-tree-dump "\\| 32773" "forwprop3" } } */ + +unsigned short +test3 (unsigned short a) +{ + a &= 0xd123; + a ^= 0x6040; + a |= 0xc031; /* Simplify to ((a & 0xd123) | 0xe071). */ + return a; +} +/* { dg-final { scan-tree-dump "\\| 57457" "forwprop3" } } */ + +unsigned short +test4 (unsigned short a) +{ + a ^= 0x8002; + a >>= 1; + a |= 0x8000; + return a; +} +/* { dg-final { scan-tree-dump "\\^ 49153" "forwprop3" } } */ + +unsigned short +test5 (unsigned short a) +{ + a ^= 0x8002; + a >>= 1; + a |= 0x8001; /* Only move shift inward: (((a >> 1) ^ 0x4001) | 0x8001). */ + return a; +} +/* { dg-final { scan-tree-dump "\\^ 16385" "forwprop3" } } */ +/* { dg-final { scan-tree-dump "\\| 32769" "forwprop3" } } */ + +short +test6 (short a) +{ + a &= 0x7fff; + a >>= 2; + return a; +} +/* { dg-final { scan-tree-dump "\\& 8191" "forwprop3" } } */ + +short +test7 (short a) +{ + a &= 0x8fff; + a >>= 2; + return a; +} +/* { dg-final { scan-tree-dump "\\& -7169" "forwprop3" } } */ -- 2.30.2