| Message ID | 2017997593.883643.1309520672925.JavaMail.root@zmail06.collab.prod.int.phx2.redhat.com |
|---|---|
| State | New |
| Headers | show |
On Fri, Jul 1, 2011 at 1:44 PM, Kai Tietz <ktietz@redhat.com> wrote: > Ok, here is reworked patch with adjusted testcase. > > ChangeLog gcc/ > > 2011-07-01 Kai Tietz <ktietz@redhat.com> > > * tree-ssa-forwprop.c (truth_valued_ssa): New function. > (detect_not_expr_operand): New function. > (simplify_bitwise_binary_1): New function. > (simplify_bitwise_binary): Use simplify_bitwise_binary_1. > > ChangeLog gcc/ > > 2011-07-01 Kai Tietz <ktietz@redhat.com> > > * gcc.dg/binop-notand1a.c: New test. > * gcc.dg/binop-notand2a.c: New test. > * gcc.dg/binop-notand3a.c: New test. > * gcc.dg/binop-notand4a.c: New test. > * gcc.dg/binop-notand5a.c: New test. > * gcc.dg/binop-notand6a.c: New test. > * gcc.dg/binop-notor1.c: New test. > * gcc.dg/binop-notor2.c: New test. > * gcc.dg/binop-notxor1.c: New test. > * gcc.dg/binop-notxor2.c: New test. > > > Bootstrapped and regression tested for all standard languages plus Ada and Obj-C++ for x86_64-pc-linux-gnu. Ok for apply? (please post patches inline) +/* Checks if expression has type of one-bit precision, or is a known + truth-value pression. */ +static bool +truth_valued_ssa_name (tree name) The function comment should refer to each parameter in capital letters. The comment is also odd, if you consider the function name. Better would be "Return true if the SSA name NAME is of truth-value. " + /* 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; Technically correct, but did you run into actual problems without this? +/* Helper routine for simplify_bitwise_binary_1 function. + If a NOT-expression is found, the operand of the NOT-expression is + returned. Othewise NULL_TREE is returned. + Detected not-patterns are !X or X == 0 for X with integral type, and + X ^ 1 or ~X for X with integral type with precision of one. + The value of CNT_CASTS is either zero, or one. */ +static tree +detect_not_expr_operand (tree name) What's a NOT-expression? I'd suggest /* For the SSA name NAME return an expression X so that NAME = !X. If there is no such X, return NULL_TREE. */ Then a better name for the function would be lookup_inverted_value. + def = SSA_NAME_DEF_STMT (name); + if (!def || !is_gimple_assign (def)) + return NULL_TREE; + def is never NULL. + 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 == 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)) op1, not 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; I think you want this test generally, before the switch. + if (integer_zerop (op2)) + return op1; + else if (integer_zerop (op1)) + return op2; It's always op2 that is 0, no need to test op1. What about NE_EXPR? If you allow EQ/NE_EXPRs then what this function returns is not something for which NAME = !X holds but something for which NAME = X == 0 holds. Otherwise you have to make sure op1 is a truth value. There is also EQ/NE_EXPR with op2 == 1, which at least for truth-valued op1 can be handled as well. + 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; + } + /* First check if operands ARG1 and ARG2 are equal, if so we + won't have a NOT-pattern match. Fold these patterns, as + we have detected it already. */ + if (operand_equal_p (arg1, arg2, 0)) + { + /* X & X -> X, and X | X -> X. */ + if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR) + return arg1; + /* X ^ X -> 0. */ + return integer_zero_node; + } gimple_fold catches this already, no reason to do that here. + /* Do we have case not(X) op not(X)? */ + if (a1not && a2not) + { CSE would have handled this, so no reason to check this - you've done this with the previous operand_equal_p test already. + /* Get for each operation operand its optional by one integral typed + cast stripped argument. And get the not-expression's operand, if + argument represents an not-expression. */ + a1not = detect_not_expr_operand (arg1); + a2not = detect_not_expr_operand (arg2); + + /* If there are no not-expressions found, return NULL_TREE. */ + if (!a1not && !a2not) + return NULL_TREE; ... + if (a2not) + { + /* X equal to Y for X op not(Y) */ + if (operand_equal_p (arg1, a2not, 0)) + op = arg1; + } don't need a1not yet So I suggest to rewrite this to sth like a1not = detect_not_expr_operand (arg1); if (a1not && operand_equal_p (a1not, arg2, 0)) op = arg2; else if ((a2not = detect_not_expr_operand (arg2)) && operand_equal_p (arg1, a2not, 0)) op = arg1; else return NULL_TREE; ... as that is cheaper. The ???s below are probably not worth handling. Richard. > Regards, > Kai >
2011/7/1 Richard Guenther <richard.guenther@gmail.com>: > On Fri, Jul 1, 2011 at 1:44 PM, Kai Tietz <ktietz@redhat.com> wrote: >> Ok, here is reworked patch with adjusted testcase. >> >> ChangeLog gcc/ >> >> 2011-07-01 Kai Tietz <ktietz@redhat.com> >> >> * tree-ssa-forwprop.c (truth_valued_ssa): New function. >> (detect_not_expr_operand): New function. >> (simplify_bitwise_binary_1): New function. >> (simplify_bitwise_binary): Use simplify_bitwise_binary_1. >> >> ChangeLog gcc/ >> >> 2011-07-01 Kai Tietz <ktietz@redhat.com> >> >> * gcc.dg/binop-notand1a.c: New test. >> * gcc.dg/binop-notand2a.c: New test. >> * gcc.dg/binop-notand3a.c: New test. >> * gcc.dg/binop-notand4a.c: New test. >> * gcc.dg/binop-notand5a.c: New test. >> * gcc.dg/binop-notand6a.c: New test. >> * gcc.dg/binop-notor1.c: New test. >> * gcc.dg/binop-notor2.c: New test. >> * gcc.dg/binop-notxor1.c: New test. >> * gcc.dg/binop-notxor2.c: New test. >> >> >> Bootstrapped and regression tested for all standard languages plus Ada and Obj-C++ for x86_64-pc-linux-gnu. Ok for apply? > > (please post patches inline) > > +/* Checks if expression has type of one-bit precision, or is a known > + truth-value pression. */ > +static bool > +truth_valued_ssa_name (tree name) > > The function comment should refer to each parameter in capital letters. > The comment is also odd, if you consider the function name. Better > would be "Return true if the SSA name NAME is of truth-value. " Ok > + /* 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; > > Technically correct, but did you run into actual problems without this? Yes, this makes issues. See BIT_NOT_EXPR in fold-const. It uses LHS type for ~0. [*] > +/* Helper routine for simplify_bitwise_binary_1 function. > + If a NOT-expression is found, the operand of the NOT-expression is > + returned. Othewise NULL_TREE is returned. > + Detected not-patterns are !X or X == 0 for X with integral type, and > + X ^ 1 or ~X for X with integral type with precision of one. > + The value of CNT_CASTS is either zero, or one. */ > +static tree > +detect_not_expr_operand (tree name) > > What's a NOT-expression? I'd suggest > > /* For the SSA name NAME return an expression X so that > NAME = !X. If there is no such X, return NULL_TREE. */ > > Then a better name for the function would be lookup_inverted_value. Hmm, we don't look up inverted values in general. May lookup_inverted_truth_value? > + def = SSA_NAME_DEF_STMT (name); > + if (!def || !is_gimple_assign (def)) > + return NULL_TREE; > + > > def is never NULL. Ok > + 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 == 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)) > > op1, not name No, name is right. see [*] > + 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; > > I think you want this test generally, before the switch. No, no need for this. Just for comparisons I need to check that operands are equal. The type of NAME is always an integral value. > + if (integer_zerop (op2)) > + return op1; > + else if (integer_zerop (op1)) > + return op2; > > It's always op2 that is 0, no need to test op1. So for comparison constant will be moved always right-hand? Ok fine by this. > What about NE_EXPR? Maybe for X != 1 for an truth-valued X. But I never saw this pattern generated. All other cases related to NE_EXPR, which might be an inverted variant aren't trivial and not sure if it is worth checking them here. Eg. (X | Y) != 0 -> (X != 0 | Y != 0) would be the inverted variant of (X == 0 && Y == 0). But those things might be better placed in and/or_comparison folding in gimple-fold.c, isn't it? > If you allow EQ/NE_EXPRs then what this function returns is > not something for which NAME = !X holds but something > for which NAME = X == 0 holds. Otherwise you have to > make sure op1 is a truth value. !X is (for integral types) X == (type-x) 0. And this transformation is bijective AFAICS. I don't see the point you mean here. > There is also EQ/NE_EXPR with op2 == 1, which at least > for truth-valued op1 can be handled as well. See comment above. It is true that X != 1 (for truth-valued X) is X == 0. This might be a special case worth to add, but for X != 0 (for truth-valued X) it isn't. Same as for X == 1 cases. We want to return the argument of the not expression here. So we would need to return for those cases !X. > + 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; > + } > > + /* First check if operands ARG1 and ARG2 are equal, if so we > + won't have a NOT-pattern match. Fold these patterns, as > + we have detected it already. */ > + if (operand_equal_p (arg1, arg2, 0)) > + { > + /* X & X -> X, and X | X -> X. */ > + if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR) > + return arg1; > + /* X ^ X -> 0. */ > + return integer_zero_node; > + } > > gimple_fold catches this already, no reason to do that here. Ok > + /* Do we have case not(X) op not(X)? */ > + if (a1not && a2not) > + { > > CSE would have handled this, so no reason to check this - you've > done this with the previous operand_equal_p test already. No I didn't. As this will match cases like (X ^ 1) & !X (for truth-valued X). We compare here the operand of the not-expression. > + /* Get for each operation operand its optional by one integral typed > + cast stripped argument. And get the not-expression's operand, if > + argument represents an not-expression. */ > + a1not = detect_not_expr_operand (arg1); > + a2not = detect_not_expr_operand (arg2); > + > + /* If there are no not-expressions found, return NULL_TREE. */ > + if (!a1not && !a2not) > + return NULL_TREE; > > ... > > + if (a2not) > + { > + /* X equal to Y for X op not(Y) */ > + if (operand_equal_p (arg1, a2not, 0)) > + op = arg1; > + } > > don't need a1not yet > > So I suggest to rewrite this to sth like > > a1not = detect_not_expr_operand (arg1); > if (a1not > && operand_equal_p (a1not, arg2, 0)) > op = arg2; > else if ((a2not = detect_not_expr_operand (arg2)) > && operand_equal_p (arg1, a2not, 0)) > op = arg1; > else > return NULL_TREE; > > ... > > as that is cheaper. The ???s below are probably not worth handling. > > Richard. > >> Regards, >> Kai >> > Regards, Kai
2011/7/1 Kai Tietz <ktietz70@googlemail.com>: > 2011/7/1 Richard Guenther <richard.guenther@gmail.com>: >> On Fri, Jul 1, 2011 at 1:44 PM, Kai Tietz <ktietz@redhat.com> wrote: >>> Ok, here is reworked patch with adjusted testcase. >>> >>> ChangeLog gcc/ >>> >>> 2011-07-01 Kai Tietz <ktietz@redhat.com> >>> >>> * tree-ssa-forwprop.c (truth_valued_ssa): New function. >>> (detect_not_expr_operand): New function. >>> (simplify_bitwise_binary_1): New function. >>> (simplify_bitwise_binary): Use simplify_bitwise_binary_1. >>> >>> ChangeLog gcc/ >>> >>> 2011-07-01 Kai Tietz <ktietz@redhat.com> >>> >>> * gcc.dg/binop-notand1a.c: New test. >>> * gcc.dg/binop-notand2a.c: New test. >>> * gcc.dg/binop-notand3a.c: New test. >>> * gcc.dg/binop-notand4a.c: New test. >>> * gcc.dg/binop-notand5a.c: New test. >>> * gcc.dg/binop-notand6a.c: New test. >>> * gcc.dg/binop-notor1.c: New test. >>> * gcc.dg/binop-notor2.c: New test. >>> * gcc.dg/binop-notxor1.c: New test. >>> * gcc.dg/binop-notxor2.c: New test. >>> >>> >>> Bootstrapped and regression tested for all standard languages plus Ada and Obj-C++ for x86_64-pc-linux-gnu. Ok for apply? >> >> (please post patches inline) >> >> +/* Checks if expression has type of one-bit precision, or is a known >> + truth-value pression. */ >> +static bool >> +truth_valued_ssa_name (tree name) >> >> The function comment should refer to each parameter in capital letters. >> The comment is also odd, if you consider the function name. Better >> would be "Return true if the SSA name NAME is of truth-value. " > > Ok > >> + /* 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; >> >> Technically correct, but did you run into actual problems without this? > Yes, this makes issues. See BIT_NOT_EXPR in fold-const. It uses LHS type > for ~0. [*] > >> +/* Helper routine for simplify_bitwise_binary_1 function. >> + If a NOT-expression is found, the operand of the NOT-expression is >> + returned. Othewise NULL_TREE is returned. >> + Detected not-patterns are !X or X == 0 for X with integral type, and >> + X ^ 1 or ~X for X with integral type with precision of one. >> + The value of CNT_CASTS is either zero, or one. */ >> +static tree >> +detect_not_expr_operand (tree name) >> >> What's a NOT-expression? I'd suggest >> >> /* For the SSA name NAME return an expression X so that >> NAME = !X. If there is no such X, return NULL_TREE. */ >> >> Then a better name for the function would be lookup_inverted_value. > Hmm, we don't look up inverted values in general. May > lookup_inverted_truth_value? > >> + def = SSA_NAME_DEF_STMT (name); >> + if (!def || !is_gimple_assign (def)) >> + return NULL_TREE; >> + >> >> def is never NULL. > Ok > >> + 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 == 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)) >> >> op1, not name > > No, name is right. see [*] > >> + 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; >> >> I think you want this test generally, before the switch. > No, no need for this. Just for comparisons I need to check that > operands are equal. The type of NAME > is always an integral value. > >> + if (integer_zerop (op2)) >> + return op1; >> + else if (integer_zerop (op1)) >> + return op2; >> >> It's always op2 that is 0, no need to test op1. > So for comparison constant will be moved always right-hand? Ok fine by this. > >> What about NE_EXPR? > Maybe for X != 1 for an truth-valued X. But I never saw this pattern > generated. All other cases related to NE_EXPR, which might be an > inverted variant aren't trivial and not sure if it is worth checking > them here. > Eg. (X | Y) != 0 -> (X != 0 | Y != 0) would be the inverted variant of > (X == 0 && Y == 0). But those things might be better placed in > and/or_comparison folding in gimple-fold.c, isn't it? > >> If you allow EQ/NE_EXPRs then what this function returns is >> not something for which NAME = !X holds but something >> for which NAME = X == 0 holds. Otherwise you have to >> make sure op1 is a truth value. > !X is (for integral types) X == (type-x) 0. And this transformation is > bijective AFAICS. I don't see the point you mean here. > >> There is also EQ/NE_EXPR with op2 == 1, which at least >> for truth-valued op1 can be handled as well. > > See comment above. It is true that X != 1 (for truth-valued X) is X == > 0. This might be a special case worth to add, but for X != 0 (for > truth-valued X) it isn't. Same as for X == 1 cases. We want to return > the argument of the not expression here. So we would need to return > for those cases !X. > >> + 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; >> + } >> >> + /* First check if operands ARG1 and ARG2 are equal, if so we >> + won't have a NOT-pattern match. Fold these patterns, as >> + we have detected it already. */ >> + if (operand_equal_p (arg1, arg2, 0)) >> + { >> + /* X & X -> X, and X | X -> X. */ >> + if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR) >> + return arg1; >> + /* X ^ X -> 0. */ >> + return integer_zero_node; >> + } >> >> gimple_fold catches this already, no reason to do that here. > Ok > >> + /* Do we have case not(X) op not(X)? */ >> + if (a1not && a2not) >> + { >> >> CSE would have handled this, so no reason to check this - you've >> done this with the previous operand_equal_p test already. > No I didn't. As this will match cases like (X ^ 1) & !X (for > truth-valued X). We compare here the operand of the not-expression. > >> + /* Get for each operation operand its optional by one integral typed >> + cast stripped argument. And get the not-expression's operand, if >> + argument represents an not-expression. */ >> + a1not = detect_not_expr_operand (arg1); >> + a2not = detect_not_expr_operand (arg2); >> + >> + /* If there are no not-expressions found, return NULL_TREE. */ >> + if (!a1not && !a2not) >> + return NULL_TREE; >> >> ... >> >> + if (a2not) >> + { >> + /* X equal to Y for X op not(Y) */ >> + if (operand_equal_p (arg1, a2not, 0)) >> + op = arg1; >> + } >> >> don't need a1not yet >> >> So I suggest to rewrite this to sth like >> >> a1not = detect_not_expr_operand (arg1); >> if (a1not >> && operand_equal_p (a1not, arg2, 0)) >> op = arg2; >> else if ((a2not = detect_not_expr_operand (arg2)) >> && operand_equal_p (arg1, a2not, 0)) >> op = arg1; >> else >> return NULL_TREE; >> >> ... >> >> as that is cheaper. The ???s below are probably not worth handling. >> >> Richard. >> >>> Regards, >>> Kai >>> >> > > Regards, > Kai > To be more correct here about the use of the LHS for ~ X instead of using X. If I check X for truth-valued, I would match also things like ~(X == 0). But type of the comparison isn't necessarily bool, So I would match for code like 'int foo (int c) { return c & ~(c == 0); }' and would fold it to zero. But it has for c with value zero the value 0, and for c with value not zero the result c. Regards, Kai
2011/7/1 Kai Tietz <ktietz70@googlemail.com>: > 2011/7/1 Kai Tietz <ktietz70@googlemail.com>: >> 2011/7/1 Richard Guenther <richard.guenther@gmail.com>: >>> On Fri, Jul 1, 2011 at 1:44 PM, Kai Tietz <ktietz@redhat.com> wrote: >>>> Ok, here is reworked patch with adjusted testcase. >>>> >>>> ChangeLog gcc/ >>>> >>>> 2011-07-01 Kai Tietz <ktietz@redhat.com> >>>> >>>> * tree-ssa-forwprop.c (truth_valued_ssa): New function. >>>> (detect_not_expr_operand): New function. >>>> (simplify_bitwise_binary_1): New function. >>>> (simplify_bitwise_binary): Use simplify_bitwise_binary_1. >>>> >>>> ChangeLog gcc/ >>>> >>>> 2011-07-01 Kai Tietz <ktietz@redhat.com> >>>> >>>> * gcc.dg/binop-notand1a.c: New test. >>>> * gcc.dg/binop-notand2a.c: New test. >>>> * gcc.dg/binop-notand3a.c: New test. >>>> * gcc.dg/binop-notand4a.c: New test. >>>> * gcc.dg/binop-notand5a.c: New test. >>>> * gcc.dg/binop-notand6a.c: New test. >>>> * gcc.dg/binop-notor1.c: New test. >>>> * gcc.dg/binop-notor2.c: New test. >>>> * gcc.dg/binop-notxor1.c: New test. >>>> * gcc.dg/binop-notxor2.c: New test. >>>> >>>> >>>> Bootstrapped and regression tested for all standard languages plus Ada and Obj-C++ for x86_64-pc-linux-gnu. Ok for apply? >>> >>> (please post patches inline) >>> >>> +/* Checks if expression has type of one-bit precision, or is a known >>> + truth-value pression. */ >>> +static bool >>> +truth_valued_ssa_name (tree name) >>> >>> The function comment should refer to each parameter in capital letters. >>> The comment is also odd, if you consider the function name. Better >>> would be "Return true if the SSA name NAME is of truth-value. " >> >> Ok >> >>> + /* 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; >>> >>> Technically correct, but did you run into actual problems without this? >> Yes, this makes issues. See BIT_NOT_EXPR in fold-const. It uses LHS type >> for ~0. [*] >> >>> +/* Helper routine for simplify_bitwise_binary_1 function. >>> + If a NOT-expression is found, the operand of the NOT-expression is >>> + returned. Othewise NULL_TREE is returned. >>> + Detected not-patterns are !X or X == 0 for X with integral type, and >>> + X ^ 1 or ~X for X with integral type with precision of one. >>> + The value of CNT_CASTS is either zero, or one. */ >>> +static tree >>> +detect_not_expr_operand (tree name) >>> >>> What's a NOT-expression? I'd suggest >>> >>> /* For the SSA name NAME return an expression X so that >>> NAME = !X. If there is no such X, return NULL_TREE. */ >>> >>> Then a better name for the function would be lookup_inverted_value. >> Hmm, we don't look up inverted values in general. May >> lookup_inverted_truth_value? >> >>> + def = SSA_NAME_DEF_STMT (name); >>> + if (!def || !is_gimple_assign (def)) >>> + return NULL_TREE; >>> + >>> >>> def is never NULL. >> Ok >> >>> + 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 == 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)) >>> >>> op1, not name >> >> No, name is right. see [*] >> >>> + 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; >>> >>> I think you want this test generally, before the switch. >> No, no need for this. Just for comparisons I need to check that >> operands are equal. The type of NAME >> is always an integral value. >> >>> + if (integer_zerop (op2)) >>> + return op1; >>> + else if (integer_zerop (op1)) >>> + return op2; >>> >>> It's always op2 that is 0, no need to test op1. >> So for comparison constant will be moved always right-hand? Ok fine by this. >> >>> What about NE_EXPR? >> Maybe for X != 1 for an truth-valued X. But I never saw this pattern >> generated. All other cases related to NE_EXPR, which might be an >> inverted variant aren't trivial and not sure if it is worth checking >> them here. >> Eg. (X | Y) != 0 -> (X != 0 | Y != 0) would be the inverted variant of >> (X == 0 && Y == 0). But those things might be better placed in >> and/or_comparison folding in gimple-fold.c, isn't it? >> >>> If you allow EQ/NE_EXPRs then what this function returns is >>> not something for which NAME = !X holds but something >>> for which NAME = X == 0 holds. Otherwise you have to >>> make sure op1 is a truth value. >> !X is (for integral types) X == (type-x) 0. And this transformation is >> bijective AFAICS. I don't see the point you mean here. >> >>> There is also EQ/NE_EXPR with op2 == 1, which at least >>> for truth-valued op1 can be handled as well. >> >> See comment above. It is true that X != 1 (for truth-valued X) is X == >> 0. This might be a special case worth to add, but for X != 0 (for >> truth-valued X) it isn't. Same as for X == 1 cases. We want to return >> the argument of the not expression here. So we would need to return >> for those cases !X. >> >>> + 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; >>> + } >>> >>> + /* First check if operands ARG1 and ARG2 are equal, if so we >>> + won't have a NOT-pattern match. Fold these patterns, as >>> + we have detected it already. */ >>> + if (operand_equal_p (arg1, arg2, 0)) >>> + { >>> + /* X & X -> X, and X | X -> X. */ >>> + if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR) >>> + return arg1; >>> + /* X ^ X -> 0. */ >>> + return integer_zero_node; >>> + } >>> >>> gimple_fold catches this already, no reason to do that here. >> Ok >> >>> + /* Do we have case not(X) op not(X)? */ >>> + if (a1not && a2not) >>> + { >>> >>> CSE would have handled this, so no reason to check this - you've >>> done this with the previous operand_equal_p test already. >> No I didn't. As this will match cases like (X ^ 1) & !X (for >> truth-valued X). We compare here the operand of the not-expression. >> >>> + /* Get for each operation operand its optional by one integral typed >>> + cast stripped argument. And get the not-expression's operand, if >>> + argument represents an not-expression. */ >>> + a1not = detect_not_expr_operand (arg1); >>> + a2not = detect_not_expr_operand (arg2); >>> + >>> + /* If there are no not-expressions found, return NULL_TREE. */ >>> + if (!a1not && !a2not) >>> + return NULL_TREE; >>> >>> ... >>> >>> + if (a2not) >>> + { >>> + /* X equal to Y for X op not(Y) */ >>> + if (operand_equal_p (arg1, a2not, 0)) >>> + op = arg1; >>> + } >>> >>> don't need a1not yet >>> >>> So I suggest to rewrite this to sth like >>> >>> a1not = detect_not_expr_operand (arg1); >>> if (a1not >>> && operand_equal_p (a1not, arg2, 0)) >>> op = arg2; >>> else if ((a2not = detect_not_expr_operand (arg2)) >>> && operand_equal_p (arg1, a2not, 0)) >>> op = arg1; >>> else >>> return NULL_TREE; >>> >>> ... >>> >>> as that is cheaper. The ???s below are probably not worth handling. >>> >>> Richard. >>> >>>> Regards, >>>> Kai >>>> >>> >> >> Regards, >> Kai >> > > To be more correct here about the use of the LHS for ~ X instead of > using X. If I check X for truth-valued, I would match also things like > ~(X == 0). But type of the comparison isn't necessarily bool, So I > would match for code like 'int foo (int c) { return c & ~(c == 0); }' > and would fold it to zero. But it has for c with value zero the value > 0, and for c with value not zero the result c. Sorry, yesterday wasn't my day. Of course I meant sample 'int foo c) { return c & ~ (c != 0); }'. Its result for c != 0 is (c & 0xfffffffe), and for c == 0 it is 0. Kai
Index: gcc-head/gcc/tree-ssa-forwprop.c =================================================================== --- gcc-head.orig/gcc/tree-ssa-forwprop.c +++ gcc-head/gcc/tree-ssa-forwprop.c @@ -1602,6 +1602,179 @@ simplify_builtin_call (gimple_stmt_itera return false; } +/* Checks if expression has type of one-bit precision, or is a known + truth-value pression. */ +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. + If a NOT-expression is found, the operand of the NOT-expression is + returned. Othewise NULL_TREE is returned. + Detected not-patterns are !X or X == 0 for X with integral type, and + X ^ 1 or ~X for X with integral type with precision of one. + The value of CNT_CASTS is either zero, or one. */ +static tree +detect_not_expr_operand (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 (!def || !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 == 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; + else if (integer_zerop (op1)) + return op2; + 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; +} + +/* Try to optimize patterns X & not(X) -> zero, X | not(X) -> one, and + X ^ not(X) -> one, if type of X is valid for this. + Additional handle the variants X & X -> X, X | X -> X, and X ^ X -> zero. + + See for detected not-patterns the detect_not_expr_operand function. */ +static tree +simplify_bitwise_binary_1 (enum tree_code code, tree arg1, + tree arg2) +{ + tree a1not, a2not; + tree op = NULL_TREE; + + /* 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 we + won't have a NOT-pattern match. Fold these patterns, as + we have detected it already. */ + if (operand_equal_p (arg1, arg2, 0)) + { + /* X & X -> X, and X | X -> X. */ + if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR) + return arg1; + /* X ^ X -> 0. */ + return integer_zero_node; + } + /* Get for each operation operand its optional by one integral typed + cast stripped argument. And get the not-expression's operand, if + argument represents an not-expression. */ + a1not = detect_not_expr_operand (arg1); + a2not = detect_not_expr_operand (arg2); + + /* If there are no not-expressions found, return NULL_TREE. */ + if (!a1not && !a2not) + return NULL_TREE; + + /* Do we have case not(X) op not(X)? */ + if (a1not && a2not) + { + /* Check if operands not(ARG1) and not(ARG2) are equal and + fold them if so. */ + if (operand_equal_p (a1not, a2not, 0)) + { + /* !X & !X -> !X, and !X | i!X -> !X. */ + if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR) + return arg1; + /* !X ^ !X -> 0. */ + return integer_zero_node; + } + return NULL_TREE; + } + + if (a2not) + { + /* X equal to Y for X op not(Y) */ + if (operand_equal_p (arg1, a2not, 0)) + op = arg1; + } + if (!op && a1not) + { + /* X equal to Y for not(X) op Y */ + if (operand_equal_p (arg2, a1not, 0)) + op = arg2; + } + /* No match, return NULL_TREE. */ + if (!op) + return NULL_TREE; + + /* X & not(X) -> 0. */ + if (code == BIT_AND_EXPR) + return integer_zero_node; + else if (code == BIT_IOR_EXPR) + { + /* X | not(X) -> 1, if X is truth-valued. */ + if (truth_valued_ssa_name (op)) + return integer_one_node; + + /* ??? Otherwise result is (X != 0 ? X : 1). not handled. */ + } + else if (code == BIT_XOR_EXPR) + { + /* X ^ not(X) -> 1, if X is truth-valued. */ + if (truth_valued_ssa_name (op)) + return 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. */ @@ -1768,7 +1941,31 @@ simplify_bitwise_binary (gimple_stmt_ite update_stmt (stmt); return true; } + /* Try simple folding for X op !X, and X op X. */ + res = simplify_bitwise_binary_1 (code, arg1, arg2); + if (res != NULL_TREE && TREE_CODE (res) == INTEGER_CST) + { + res = fold_convert_loc (gimple_location (stmt), + TREE_TYPE (arg1), res); + gimple_assign_set_rhs_from_tree (gsi, res); + update_stmt (gsi_stmt (*gsi)); + return true; + } + else if (res) + { + if (!useless_type_conversion_p (TREE_TYPE (arg1), TREE_TYPE (res))) + { + res = force_gimple_operand_gsi (gsi, res, true, NULL_TREE, true, + GSI_SAME_STMT); + gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR, + res, NULL_TREE, NULL_TREE); + } + else + gimple_assign_set_rhs_from_tree (gsi, res); + update_stmt (gsi_stmt (*gsi)); + return true; + } return false; } Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand1a.c =================================================================== --- /dev/null +++ gcc-head/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" } } */ Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand2a.c =================================================================== --- /dev/null +++ gcc-head/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" } } */ Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand3a.c =================================================================== --- /dev/null +++ gcc-head/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" } } */ Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand4a.c =================================================================== --- /dev/null +++ gcc-head/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" } } */ Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand5a.c =================================================================== --- /dev/null +++ gcc-head/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" } } */ Index: gcc-head/gcc/testsuite/gcc.dg/binop-notand6a.c =================================================================== --- /dev/null +++ gcc-head/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" } } */ Index: gcc-head/gcc/testsuite/gcc.dg/binop-notor1.c =================================================================== --- /dev/null +++ gcc-head/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" } } */ Index: gcc-head/gcc/testsuite/gcc.dg/binop-notor2.c =================================================================== --- /dev/null +++ gcc-head/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" } } */ Index: gcc-head/gcc/testsuite/gcc.dg/binop-notxor1.c =================================================================== --- /dev/null +++ gcc-head/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" } } */ Index: gcc-head/gcc/testsuite/gcc.dg/binop-notxor2.c =================================================================== --- /dev/null +++ gcc-head/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" } } */