From 0816a42a1fa5f3fa99d5756b35c9e7a94cbdb86e Mon Sep 17 00:00:00 2001 From: Kai Tietz Date: Thu, 7 Jul 2011 16:16:44 +0200 Subject: [PATCH] tree-ssa-forwprop.c (truth_valued_ssa_name): New function. 2011-07-07 Kai Tietz * tree-ssa-forwprop.c (truth_valued_ssa_name): New function. (lookup_logical_inverted_value): Likewise. (simplify_bitwise_binary_1): Likewise. (simplify_bitwise_binary): Use simplify_bitwise_binary_1. 2011-07-07 Kai Tietz * gcc.dg/binop-notxor1.c: New test. * gcc.dg/binop-notand4a.c: New test. * gcc.dg/binop-notxor2.c: New test. * gcc.dg/binop-notand3a.c: New test. * gcc.dg/binop-notand2a.c: New test. * gcc.dg/binop-notand6a.c: New test. * gcc.dg/binop-notor1.c: New test. * gcc.dg/binop-notand1a.c: New test. * gcc.dg/binop-notand5a.c: New test. * gcc.dg/binop-notor2.c: New test. From-SVN: r175974 --- gcc/ChangeLog | 7 ++ gcc/testsuite/ChangeLog | 13 +++ gcc/testsuite/gcc.dg/binop-notand1a.c | 13 +++ gcc/testsuite/gcc.dg/binop-notand2a.c | 11 +++ gcc/testsuite/gcc.dg/binop-notand3a.c | 11 +++ gcc/testsuite/gcc.dg/binop-notand4a.c | 13 +++ gcc/testsuite/gcc.dg/binop-notand5a.c | 11 +++ gcc/testsuite/gcc.dg/binop-notand6a.c | 11 +++ gcc/testsuite/gcc.dg/binop-notor1.c | 11 +++ gcc/testsuite/gcc.dg/binop-notor2.c | 11 +++ gcc/testsuite/gcc.dg/binop-notxor1.c | 11 +++ gcc/testsuite/gcc.dg/binop-notxor2.c | 11 +++ gcc/tree-ssa-forwprop.c | 132 ++++++++++++++++++++++++++ 13 files changed, 266 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/binop-notand1a.c create mode 100644 gcc/testsuite/gcc.dg/binop-notand2a.c create mode 100644 gcc/testsuite/gcc.dg/binop-notand3a.c create mode 100644 gcc/testsuite/gcc.dg/binop-notand4a.c create mode 100644 gcc/testsuite/gcc.dg/binop-notand5a.c create mode 100644 gcc/testsuite/gcc.dg/binop-notand6a.c create mode 100644 gcc/testsuite/gcc.dg/binop-notor1.c create mode 100644 gcc/testsuite/gcc.dg/binop-notor2.c create mode 100644 gcc/testsuite/gcc.dg/binop-notxor1.c create mode 100644 gcc/testsuite/gcc.dg/binop-notxor2.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index b2be0973cb0..09a817a1e94 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,10 @@ +2011-07-07 Kai Tietz + + * tree-ssa-forwprop.c (truth_valued_ssa_name): New function. + (lookup_logical_inverted_value): Likewise. + (simplify_bitwise_binary_1): Likewise. + (simplify_bitwise_binary): Use simplify_bitwise_binary_1. + 2011-07-07 Joseph Myers * gcc.c (%[Spec]): Don't document. diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index e54290995d8..e73b5ea428a 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,16 @@ +2011-07-07 Kai Tietz + + * gcc.dg/binop-notxor1.c: New test. + * gcc.dg/binop-notand4a.c: New test. + * gcc.dg/binop-notxor2.c: New test. + * gcc.dg/binop-notand3a.c: New test. + * gcc.dg/binop-notand2a.c: New test. + * gcc.dg/binop-notand6a.c: New test. + * gcc.dg/binop-notor1.c: New test. + * gcc.dg/binop-notand1a.c: New test. + * gcc.dg/binop-notand5a.c: New test. + * gcc.dg/binop-notor2.c: New test. + 2011-07-07 Jakub Jelinek PR middle-end/49640 diff --git a/gcc/testsuite/gcc.dg/binop-notand1a.c b/gcc/testsuite/gcc.dg/binop-notand1a.c new file mode 100644 index 00000000000..2d8202a0c13 --- /dev/null +++ b/gcc/testsuite/gcc.dg/binop-notand1a.c @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (char a, unsigned short b) +{ + return (a & !a) | (b & !b); +} + +/* As long as comparisons aren't boolified and casts from boolean-types + aren't preserved, the folding of X & !X to zero fails. */ +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" { xfail *-*-* } } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/binop-notand2a.c b/gcc/testsuite/gcc.dg/binop-notand2a.c new file mode 100644 index 00000000000..0076d4be7a1 --- /dev/null +++ b/gcc/testsuite/gcc.dg/binop-notand2a.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (int a) +{ + return (!a & 1) != (a == 0); +} + +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/binop-notand3a.c b/gcc/testsuite/gcc.dg/binop-notand3a.c new file mode 100644 index 00000000000..40e8038a78d --- /dev/null +++ b/gcc/testsuite/gcc.dg/binop-notand3a.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (short a) +{ + return (!a & 1) != ((a == 0) & 1); +} + +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/binop-notand4a.c b/gcc/testsuite/gcc.dg/binop-notand4a.c new file mode 100644 index 00000000000..1178cf78826 --- /dev/null +++ b/gcc/testsuite/gcc.dg/binop-notand4a.c @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (unsigned char a, _Bool b) +{ + return (!a & a) | (b & !b); +} + +/* As long as comparisons aren't boolified and casts from boolean-types + aren't preserved, the folding of X & !X to zero fails. */ +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" { xfail *-*-* } } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/binop-notand5a.c b/gcc/testsuite/gcc.dg/binop-notand5a.c new file mode 100644 index 00000000000..289abcb6b85 --- /dev/null +++ b/gcc/testsuite/gcc.dg/binop-notand5a.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (long a, unsigned long b) +{ + return (a & (a == 0)) | (b & !b); +} + +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/binop-notand6a.c b/gcc/testsuite/gcc.dg/binop-notand6a.c new file mode 100644 index 00000000000..b9fe4052d58 --- /dev/null +++ b/gcc/testsuite/gcc.dg/binop-notand6a.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (unsigned long a, long b) +{ + return (a & !a) | (b & (b == 0)); +} + +/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/binop-notor1.c b/gcc/testsuite/gcc.dg/binop-notor1.c new file mode 100644 index 00000000000..a2cb6a3277f --- /dev/null +++ b/gcc/testsuite/gcc.dg/binop-notor1.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (_Bool a, _Bool b) +{ + return (a | !a) | (!b | b); +} + +/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/binop-notor2.c b/gcc/testsuite/gcc.dg/binop-notor2.c new file mode 100644 index 00000000000..ab8d70e4b5a --- /dev/null +++ b/gcc/testsuite/gcc.dg/binop-notor2.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (_Bool a, _Bool b) +{ + return (a | (a == 0)) | ((b ^ 1) | b); +} + +/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/binop-notxor1.c b/gcc/testsuite/gcc.dg/binop-notxor1.c new file mode 100644 index 00000000000..39c258dcd75 --- /dev/null +++ b/gcc/testsuite/gcc.dg/binop-notxor1.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (_Bool a, _Bool b) +{ + return (a ^ !a) | (!b ^ b); +} + +/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/binop-notxor2.c b/gcc/testsuite/gcc.dg/binop-notxor2.c new file mode 100644 index 00000000000..9f34cf284f4 --- /dev/null +++ b/gcc/testsuite/gcc.dg/binop-notxor2.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int +foo (_Bool a, _Bool b) +{ + return (a ^ (a == 0)) | ((b == 0) ^ b); +} + +/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ diff --git a/gcc/tree-ssa-forwprop.c b/gcc/tree-ssa-forwprop.c index 893f17b47a4..8e6b7040af0 100644 --- a/gcc/tree-ssa-forwprop.c +++ b/gcc/tree-ssa-forwprop.c @@ -1602,6 +1602,129 @@ simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2) return false; } +/* Checks if expression has type of one-bit precision, or is a known + truth-valued expression. */ +static bool +truth_valued_ssa_name (tree name) +{ + gimple def; + tree type = TREE_TYPE (name); + + if (!INTEGRAL_TYPE_P (type)) + return false; + /* Don't check here for BOOLEAN_TYPE as the precision isn't + necessarily one and so ~X is not equal to !X. */ + if (TYPE_PRECISION (type) == 1) + return true; + def = SSA_NAME_DEF_STMT (name); + if (is_gimple_assign (def)) + return truth_value_p (gimple_assign_rhs_code (def)); + return false; +} + +/* Helper routine for simplify_bitwise_binary_1 function. + Return for the SSA name NAME the expression X if it mets condition + NAME = !X. Otherwise return NULL_TREE. + Detected patterns for NAME = !X are: + !X and X == 0 for X with integral type. + X ^ 1, X != 1,or ~X for X with integral type with precision of one. */ +static tree +lookup_logical_inverted_value (tree name) +{ + tree op1, op2; + enum tree_code code; + gimple def; + + /* If name has none-intergal type, or isn't a SSA_NAME, then + return. */ + if (TREE_CODE (name) != SSA_NAME + || !INTEGRAL_TYPE_P (TREE_TYPE (name))) + return NULL_TREE; + def = SSA_NAME_DEF_STMT (name); + if (!is_gimple_assign (def)) + return NULL_TREE; + + code = gimple_assign_rhs_code (def); + op1 = gimple_assign_rhs1 (def); + op2 = NULL_TREE; + + /* Get for EQ_EXPR or BIT_XOR_EXPR operation the second operand. + If CODE isn't an EQ_EXPR, BIT_XOR_EXPR, TRUTH_NOT_EXPR, + or BIT_NOT_EXPR, then return. */ + if (code == EQ_EXPR || code == NE_EXPR + || code == BIT_XOR_EXPR) + op2 = gimple_assign_rhs2 (def); + + switch (code) + { + case TRUTH_NOT_EXPR: + return op1; + case BIT_NOT_EXPR: + if (truth_valued_ssa_name (name)) + return op1; + break; + case EQ_EXPR: + /* Check if we have X == 0 and X has an integral type. */ + if (!INTEGRAL_TYPE_P (TREE_TYPE (op1))) + break; + if (integer_zerop (op2)) + return op1; + break; + case NE_EXPR: + /* Check if we have X != 1 and X is a truth-valued. */ + if (!INTEGRAL_TYPE_P (TREE_TYPE (op1))) + break; + if (integer_onep (op2) && truth_valued_ssa_name (op1)) + return op1; + break; + case BIT_XOR_EXPR: + /* Check if we have X ^ 1 and X is truth valued. */ + if (integer_onep (op2) && truth_valued_ssa_name (op1)) + return op1; + break; + default: + break; + } + + return NULL_TREE; +} + +/* Optimize ARG1 CODE ARG2 to a constant for bitwise binary + operations CODE, if one operand has the logically inverted + value of the other. */ +static tree +simplify_bitwise_binary_1 (enum tree_code code, tree type, + tree arg1, tree arg2) +{ + tree anot; + + /* If CODE isn't a bitwise binary operation, return NULL_TREE. */ + if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR + && code != BIT_XOR_EXPR) + return NULL_TREE; + + /* First check if operands ARG1 and ARG2 are equal. If so + return NULL_TREE as this optimization is handled fold_stmt. */ + if (arg1 == arg2) + return NULL_TREE; + /* See if we have in arguments logical-not patterns. */ + if (((anot = lookup_logical_inverted_value (arg1)) == NULL_TREE + || anot != arg2) + && ((anot = lookup_logical_inverted_value (arg2)) == NULL_TREE + || anot != arg1)) + return NULL_TREE; + + /* X & !X -> 0. */ + if (code == BIT_AND_EXPR) + return fold_convert (type, integer_zero_node); + /* X | !X -> 1 and X ^ !X -> 1, if X is truth-valued. */ + if (truth_valued_ssa_name (anot)) + return fold_convert (type, integer_one_node); + + /* ??? Otherwise result is (X != 0 ? X : 1). not handled. */ + return NULL_TREE; +} + /* Simplify bitwise binary operations. Return true if a transformation applied, otherwise return false. */ @@ -1769,6 +1892,15 @@ simplify_bitwise_binary (gimple_stmt_iterator *gsi) return true; } + /* Try simple folding for X op !X, and X op X. */ + res = simplify_bitwise_binary_1 (code, TREE_TYPE (arg1), arg1, arg2); + if (res != NULL_TREE) + { + gimple_assign_set_rhs_from_tree (gsi, res); + update_stmt (gsi_stmt (*gsi)); + return true; + } + return false; } -- 2.30.2