Re: [patch tree-optimization]: [2 of 3]: Boolify compares & more

[Kai Tietz <ktietz70 at googlemail dot com>]

2011/7/12 Richard Guenther <richard.guenther@gmail.com>:
> On Tue, Jul 12, 2011 at 11:48 AM, Kai Tietz <ktietz70@googlemail.com> wrote:
>> 2011/7/12 Richard Guenther <richard.guenther@gmail.com>:
>>> On Mon, Jul 11, 2011 at 5:37 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>>> 2011/7/8 Richard Guenther <richard.guenther@gmail.com>:
>>>>> On Fri, Jul 8, 2011 at 1:32 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>>>>> 2011/7/8 Richard Guenther <richard.guenther@gmail.com>:
>>>>>>> On Thu, Jul 7, 2011 at 6:07 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>>>>>>> Hello,
>>>>>>>>
>>>>>>>> This patch - second of series - adds boolification of comparisions in
>>>>>>>> gimplifier. ?For this
>>>>>>>> casts from/to boolean are marked as not-useless. And in fold_unary_loc
>>>>>>>> casts to non-boolean integral types are preserved.
>>>>>>>> The hunk in tree-ssa-forwprop.c in combine_cond-expr_cond is not strictly
>>>>>>>> necessary - as long as fold-const handles 1-bit precision bitwise-expression
>>>>>>>> with truth-logic - but it has shown to short-cut some expensier folding. So
>>>>>>>> I kept it within this patch.
>>>>>>>
>>>>>>> Please split it out. ?Also ...
>>>>>>>
>>>>>>>>
>>>>>>>> The adjusted testcase gcc.dg/uninit-15.c indicates that due
>>>>>>>> optimization we loose
>>>>>>>> in this case variables declaration. ?But this might be to be expected.
>>>>>>>>
>>>>>>>> In vectorization we have a regression in gcc.dg/vect/vect-cond-3.c
>>>>>>>> test-case. ?It's caused
>>>>>>>> by always having boolean-type on conditions. ?So vectorizer sees
>>>>>>>> different types, which
>>>>>>>> aren't handled by vectorizer right now. ?Maybe this issue could be
>>>>>>>> special-cased for
>>>>>>>> boolean-types in tree-vect-loop, by making operand for used condition
>>>>>>>> equal to vector-type.
>>>>>>>> But this is a subject for a different patch and not addressed by this series.
>>>>>>>>
>>>>>>>> There is a regressions in tree-ssa/vrp47.c, and the fix is addressed
>>>>>>>> by the 3rd patch of this
>>>>>>>> series.
>>>>>>>>
>>>>>>>> Bootstrapped and regression tested for all standard-languages (plus
>>>>>>>> Ada and Obj-C++) on host x86_64-pc-linux-gnu.
>>>>>>>>
>>>>>>>> Ok for apply?
>>>>>>>>
>>>>>>>> Regards,
>>>>>>>> Kai
>>>>>>>>
>>>>>>>>
>>>>>>>> ChangeLog
>>>>>>>>
>>>>>>>> 2011-07-07 ?Kai Tietz ?<ktietz@redhat.com>
>>>>>>>>
>>>>>>>> ? ? ? ?* fold-const.c (fold_unary_loc): Preserve
>>>>>>>> ? ? ? ?non-boolean-typed casts.
>>>>>>>> ? ? ? ?* gimplify.c (gimple_boolify): Handle boolification
>>>>>>>> ? ? ? ?of comparisons.
>>>>>>>> ? ? ? ?(gimplify_expr): Boolifiy non aggregate-typed
>>>>>>>> ? ? ? ?comparisons.
>>>>>>>> ? ? ? ?* tree-cfg.c (verify_gimple_comparison): Check result
>>>>>>>> ? ? ? ?type of comparison expression.
>>>>>>>> ? ? ? ?* tree-ssa.c (useless_type_conversion_p): Preserve incompatible
>>>>>>>> ? ? ? ?casts from/to boolean,
>>>>>>>> ? ? ? ?* tree-ssa-forwprop.c (combine_cond_expr_cond): Add simplification
>>>>>>>> ? ? ? ?support for one-bit-precision typed X for cases X != 0 and X == 0.
>>>>>>>> ? ? ? ?(forward_propagate_comparison): Adjust test of condition
>>>>>>>> ? ? ? ?result.
>>>>>>>>
>>>>>>>>
>>>>>>>> ? ? ? ?* gcc.dg/tree-ssa/builtin-expect-5.c: Adjusted.
>>>>>>>> ? ? ? ?* gcc.dg/tree-ssa/pr21031.c: Likewise.
>>>>>>>> ? ? ? ?* gcc.dg/tree-ssa/pr30978.c: Likewise.
>>>>>>>> ? ? ? ?* gcc.dg/tree-ssa/ssa-fre-6.c: Likewise.
>>>>>>>> ? ? ? ?* gcc.dg/binop-xor1.c: Mark it as expected fail.
>>>>>>>> ? ? ? ?* gcc.dg/binop-xor3.c: Likewise.
>>>>>>>> ? ? ? ?* gcc.dg/uninit-15.c: Adjust reported message.
>>>>>>>>
>>>>>>>> Index: gcc-head/gcc/fold-const.c
>>>>>>>> ===================================================================
>>>>>>>> --- gcc-head.orig/gcc/fold-const.c
>>>>>>>> +++ gcc-head/gcc/fold-const.c
>>>>>>>> @@ -7665,11 +7665,11 @@ fold_unary_loc (location_t loc, enum tre
>>>>>>>> ? ? ? ? ? ? non-integral type.
>>>>>>>> ? ? ? ? ? ? Do not fold the result as that would not simplify further, also
>>>>>>>> ? ? ? ? ? ? folding again results in recursions. ?*/
>>>>>>>> - ? ? ? ? if (INTEGRAL_TYPE_P (type))
>>>>>>>> + ? ? ? ? if (TREE_CODE (type) == BOOLEAN_TYPE)
>>>>>>>> ? ? ? ? ? ?return build2_loc (loc, TREE_CODE (op0), type,
>>>>>>>> ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? TREE_OPERAND (op0, 0),
>>>>>>>> ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? TREE_OPERAND (op0, 1));
>>>>>>>> - ? ? ? ? else
>>>>>>>> + ? ? ? ? else if (!INTEGRAL_TYPE_P (type))
>>>>>>>> ? ? ? ? ? ?return build3_loc (loc, COND_EXPR, type, op0,
>>>>>>>> ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? fold_convert (type, boolean_true_node),
>>>>>>>> ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? fold_convert (type, boolean_false_node));
>>>>>>>> Index: gcc-head/gcc/gimplify.c
>>>>>>>> ===================================================================
>>>>>>>> --- gcc-head.orig/gcc/gimplify.c
>>>>>>>> +++ gcc-head/gcc/gimplify.c
>>>>>>>> @@ -2842,18 +2842,23 @@ gimple_boolify (tree expr)
>>>>>>>>
>>>>>>>> ? ? case TRUTH_NOT_EXPR:
>>>>>>>> ? ? ? TREE_OPERAND (expr, 0) = gimple_boolify (TREE_OPERAND (expr, 0));
>>>>>>>> - ? ? ?/* FALLTHRU */
>>>>>>>>
>>>>>>>> - ? ?case EQ_EXPR: case NE_EXPR:
>>>>>>>> - ? ?case LE_EXPR: case GE_EXPR: case LT_EXPR: case GT_EXPR:
>>>>>>>> ? ? ? /* These expressions always produce boolean results. ?*/
>>>>>>>> - ? ? ?TREE_TYPE (expr) = boolean_type_node;
>>>>>>>> + ? ? ?if (TREE_CODE (type) != BOOLEAN_TYPE)
>>>>>>>> + ? ? ? TREE_TYPE (expr) = boolean_type_node;
>>>>>>>> ? ? ? return expr;
>>>>>>>>
>>>>>>>> ? ? default:
>>>>>>>> + ? ? ?if (COMPARISON_CLASS_P (expr))
>>>>>>>> + ? ? ? {
>>>>>>>> + ? ? ? ? /* There expressions always prduce boolean results. ?*/
>>>>>>>> + ? ? ? ? if (TREE_CODE (type) != BOOLEAN_TYPE)
>>>>>>>> + ? ? ? ? ? TREE_TYPE (expr) = boolean_type_node;
>>>>>>>> + ? ? ? ? return expr;
>>>>>>>> + ? ? ? }
>>>>>>>> ? ? ? /* Other expressions that get here must have boolean values, but
>>>>>>>> ? ? ? ? might need to be converted to the appropriate mode. ?*/
>>>>>>>> - ? ? ?if (type == boolean_type_node)
>>>>>>>> + ? ? ?if (TREE_CODE (type) == BOOLEAN_TYPE)
>>>>>>>> ? ? ? ?return expr;
>>>>>>>> ? ? ? return fold_convert_loc (loc, boolean_type_node, expr);
>>>>>>>> ? ? }
>>>>>>>> @@ -6763,7 +6768,7 @@ gimplify_expr (tree *expr_p, gimple_seq
>>>>>>>> ? ? ? ? ? ?tree org_type = TREE_TYPE (*expr_p);
>>>>>>>>
>>>>>>>> ? ? ? ? ? ?*expr_p = gimple_boolify (*expr_p);
>>>>>>>> - ? ? ? ? ? if (org_type != boolean_type_node)
>>>>>>>> + ? ? ? ? ? if (!useless_type_conversion_p (org_type, TREE_TYPE (*expr_p)))
>>>>>>>> ? ? ? ? ? ? ?{
>>>>>>>> ? ? ? ? ? ? ? ?*expr_p = fold_convert (org_type, *expr_p);
>>>>>>>
>>>>>>> Use fold_convert_loc with saved_location
>>>>>>
>>>>>> Oh, good catch. Yes, I will adjust that.
>>>>>>
>>>>>>>> ? ? ? ? ? ? ? ?ret = GS_OK;
>>>>>>>> @@ -7208,7 +7213,7 @@ gimplify_expr (tree *expr_p, gimple_seq
>>>>>>>> ? ? ? ? ? ? ? fold_truth_not_expr) happily uses operand type and doesn't
>>>>>>>> ? ? ? ? ? ? ? automatically uses boolean_type as result, we need to keep
>>>>>>>> ? ? ? ? ? ? ? orignal type. ?*/
>>>>>>>> - ? ? ? ? ? if (org_type != boolean_type_node)
>>>>>>>> + ? ? ? ? ? if (!useless_type_conversion_p (org_type, TREE_TYPE (*expr_p)))
>>>>>>>> ? ? ? ? ? ? ?{
>>>>>>>> ? ? ? ? ? ? ? ?*expr_p = fold_convert (org_type, *expr_p);
>>>>>>>
>>>>>>> Likewise. ?Maybe this fixes the diagnostic regression.
>>>>>>>
>>>>>>>> ? ? ? ? ? ? ? ?ret = GS_OK;
>>>>>>>> @@ -7288,7 +7293,19 @@ gimplify_expr (tree *expr_p, gimple_seq
>>>>>>>> ? ? ? ? ? ? ? ? ?tree type = TREE_TYPE (TREE_OPERAND (*expr_p, 1));
>>>>>>>>
>>>>>>>> ? ? ? ? ? ? ? ? ?if (!AGGREGATE_TYPE_P (type))
>>>>>>>> - ? ? ? ? ? ? ? ? ? goto expr_2;
>>>>>>>> + ? ? ? ? ? ? ? ? ? {
>>>>>>>> + ? ? ? ? ? ? ? ? ? ? tree org_type = TREE_TYPE (*expr_p);
>>>>>>>> + ? ? ? ? ? ? ? ? ? ? *expr_p = gimple_boolify (*expr_p);
>>>>>>>> + ? ? ? ? ? ? ? ? ? ? if (!useless_type_conversion_p (org_type,
>>>>>>>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? TREE_TYPE (*expr_p)))
>>>>>>>> + ? ? ? ? ? ? ? ? ? ? ? {
>>>>>>>> + ? ? ? ? ? ? ? ? ? ? ? ? *expr_p = fold_convert_loc (saved_location,
>>>>>>>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? org_type, *expr_p);
>>>>>>>> + ? ? ? ? ? ? ? ? ? ? ? ? ret = GS_OK;
>>>>>>>> + ? ? ? ? ? ? ? ? ? ? ? }
>>>>>>>> + ? ? ? ? ? ? ? ? ? ? else
>>>>>>>> + ? ? ? ? ? ? ? ? ? ? ? goto expr_2;
>>>>>>>> + ? ? ? ? ? ? ? ? ? }
>>>>>>>> ? ? ? ? ? ? ? ? ?else if (TYPE_MODE (type) != BLKmode)
>>>>>>>> ? ? ? ? ? ? ? ? ? ?ret = gimplify_scalar_mode_aggregate_compare (expr_p);
>>>>>>>> ? ? ? ? ? ? ? ? ?else
>>>>>>>> Index: gcc-head/gcc/tree-cfg.c
>>>>>>>> ===================================================================
>>>>>>>> --- gcc-head.orig/gcc/tree-cfg.c
>>>>>>>> +++ gcc-head/gcc/tree-cfg.c
>>>>>>>> @@ -3203,7 +3203,9 @@ verify_gimple_comparison (tree type, tre
>>>>>>>> ? ? ? ?&& (!POINTER_TYPE_P (op0_type)
>>>>>>>> ? ? ? ? ? || !POINTER_TYPE_P (op1_type)
>>>>>>>> ? ? ? ? ? || TYPE_MODE (op0_type) != TYPE_MODE (op1_type)))
>>>>>>>> - ? ? ?|| !INTEGRAL_TYPE_P (type))
>>>>>>>> + ? ? ?|| !INTEGRAL_TYPE_P (type)
>>>>>>>> + ? ? ?|| (TREE_CODE (type) != BOOLEAN_TYPE
>>>>>>>> + ? ? ? ? && TYPE_PRECISION (type) != 1))
>>>>>>>> ? ? {
>>>>>>>> ? ? ? error ("type mismatch in comparison expression");
>>>>>>>> ? ? ? debug_generic_expr (type);
>>>>>>>> Index: gcc-head/gcc/tree-ssa.c
>>>>>>>> ===================================================================
>>>>>>>> --- gcc-head.orig/gcc/tree-ssa.c
>>>>>>>> +++ gcc-head/gcc/tree-ssa.c
>>>>>>>> @@ -1306,10 +1306,10 @@ useless_type_conversion_p (tree outer_ty
>>>>>>>> ? ? ? ? ?|| TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
>>>>>>>> ? ? ? ?return false;
>>>>>>>>
>>>>>>>> - ? ? ?/* Preserve conversions to BOOLEAN_TYPE if it is not of precision
>>>>>>>> - ? ? ? ? one. ?*/
>>>>>>>> - ? ? ?if (TREE_CODE (inner_type) != BOOLEAN_TYPE
>>>>>>>> - ? ? ? ? && TREE_CODE (outer_type) == BOOLEAN_TYPE
>>>>>>>> + ? ? ?/* Preserve conversions to/from BOOLEAN_TYPE if types are not
>>>>>>>> + ? ? ? ?of precision one. ?*/
>>>>>>>> + ? ? ?if (((TREE_CODE (inner_type) == BOOLEAN_TYPE)
>>>>>>>> + ? ? ? ? ?!= (TREE_CODE (outer_type) == BOOLEAN_TYPE))
>>>>>>>> ? ? ? ? ?&& TYPE_PRECISION (outer_type) != 1)
>>>>>>>> ? ? ? ?return false;
>>>>>>>>
>>>>>>>> Index: gcc-head/gcc/testsuite/gcc.dg/tree-ssa/builtin-expect-5.c
>>>>>>>> ===================================================================
>>>>>>>> --- gcc-head.orig/gcc/testsuite/gcc.dg/tree-ssa/builtin-expect-5.c
>>>>>>>> +++ gcc-head/gcc/testsuite/gcc.dg/tree-ssa/builtin-expect-5.c
>>>>>>>> @@ -11,5 +11,5 @@ f (int i, float j)
>>>>>>>>
>>>>>>>> ?/* { dg-final { scan-tree-dump-times { if } 2 "forwprop1"} } */
>>>>>>>> ?/* { dg-final { scan-tree-dump {builtin_expect[^\n]*, 0\);\n[^\n]*if}
>>>>>>>> "forwprop1"} } */
>>>>>>>> -/* { dg-final { scan-tree-dump {builtin_expect[^\n]*, 1\);\n[^\n]*if}
>>>>>>>> "forwprop1"} } */
>>>>>>>> +/* { dg-final { scan-tree-dump-not {builtin_expect[^\n]*,
>>>>>>>> 1\);\n[^\n]*if} "forwprop1"} } */
>>>>>>>
>>>>>>> Hm? ?Why that?
>>>>>>>
>>>>>>>> ?/* { dg-final { cleanup-tree-dump "forwprop?" } } */
>>>>>>>> Index: gcc-head/gcc/testsuite/gcc.dg/tree-ssa/pr21031.c
>>>>>>>> ===================================================================
>>>>>>>> --- gcc-head.orig/gcc/testsuite/gcc.dg/tree-ssa/pr21031.c
>>>>>>>> +++ gcc-head/gcc/testsuite/gcc.dg/tree-ssa/pr21031.c
>>>>>>>> @@ -16,5 +16,5 @@ foo (int a)
>>>>>>>> ? ? return 0;
>>>>>>>> ?}
>>>>>>>>
>>>>>>>> -/* { dg-final { scan-tree-dump-times "Replaced" 2 "forwprop1"} } */
>>>>>>>> +/* { dg-final { scan-tree-dump-times "Replaced" 1 "forwprop1"} } */
>>>>>>>> ?/* { dg-final { cleanup-tree-dump "forwprop1" } } */
>>>>>>>> Index: gcc-head/gcc/testsuite/gcc.dg/tree-ssa/pr30978.c
>>>>>>>> ===================================================================
>>>>>>>> --- gcc-head.orig/gcc/testsuite/gcc.dg/tree-ssa/pr30978.c
>>>>>>>> +++ gcc-head/gcc/testsuite/gcc.dg/tree-ssa/pr30978.c
>>>>>>>> @@ -10,5 +10,5 @@ int foo(int a)
>>>>>>>> ? return e;
>>>>>>>> ?}
>>>>>>>>
>>>>>>>> -/* { dg-final { scan-tree-dump "e_. = a_..D. > 0;" "optimized" } } */
>>>>>>>> +/* { dg-final { scan-tree-dump " = a_..D. > 0;" "optimized" } } */
>>>>>>>> ?/* { dg-final { cleanup-tree-dump "optimized" } } */
>>>>>>>> Index: gcc-head/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-6.c
>>>>>>>> ===================================================================
>>>>>>>> --- gcc-head.orig/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-6.c
>>>>>>>> +++ gcc-head/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-6.c
>>>>>>>> @@ -2,5 +2,5 @@
>>>>>>>> ?/* { dg-options "-O -fdump-tree-fre1-details" } */
>>>>>>>>
>>>>>>>> ?int i; int foo(void) { i = 2; int j = i * 2; int k = i + 2; return j == k; }
>>>>>>>> -/* { dg-final { scan-tree-dump-times "Replaced " 5 "fre1" } } */
>>>>>>>> +/* { dg-final { scan-tree-dump-times "Replaced " 6 "fre1" } } */
>>>>>>>> ?/* { dg-final { cleanup-tree-dump "fre1" } } */
>>>>>>>> Index: gcc-head/gcc/tree-ssa-forwprop.c
>>>>>>>> ===================================================================
>>>>>>>> --- gcc-head.orig/gcc/tree-ssa-forwprop.c
>>>>>>>> +++ gcc-head/gcc/tree-ssa-forwprop.c
>>>>>>>> @@ -367,9 +367,61 @@ combine_cond_expr_cond (location_t loc,
>>>>>>>> ? gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
>>>>>>>>
>>>>>>>> ? t = fold_binary_loc (loc, code, type, op0, op1);
>>>>>>>> +
>>>>>>>> + ?if (!t && INTEGRAL_TYPE_P (TREE_TYPE (op1))
>>>>>>>> + ? ? ?&& TYPE_PRECISION (TREE_TYPE (op1)) == 1
>>>>>>>> + ? ? ?&& (code == EQ_EXPR || code == NE_EXPR))
>>>>>>>> + ? ?{
>>>>>>>> + ? ? ?if (TREE_CODE (op1) == INTEGER_CST)
>>>>>>>> + ? ? ? ?{
>>>>>>>> + ? ? ? ? if (integer_onep (op1))
>>>>>>>> + ? ? ? ? ? {
>>>>>>>> + ? ? ? ? ? ? op1 = fold_convert_loc (loc, TREE_TYPE (op1), integer_zero_node);
>>>>>>>> + ? ? ? ? ? ? code = (code == NE_EXPR ? EQ_EXPR : NE_EXPR);
>>>>>>>
>>>>>>> So you change truthvalue !=/== 1 to truthvalue ==/!= 0 and then
>>>>>>> recurse ... that doesn't make sense to me and is super-ugly.
>>>>>>> What's the testcase that made you add all this code?
>>>>>>
>>>>>> Well, the convert from truthvalue !=/== 1 to !=/== 0 limits the amount
>>>>>> of cases to handle. As for truthvalued X the we have then just to
>>>>>> handle two cases. X != 0 -> X, and X == 0 -> (X ^ 1).
>>>>>> The recursion is someting I saw as existing pattern (for the same
>>>>>> thing) in truth-op folding in fold-const.
>>>>>>
>>>>>> Actual I can remove this optimization here, as it should be convered
>>>>>> by VRP already (when VRP handles 1-bit precision bitwise ops proper).
>>>>>
>>>>> We should have a canonical form for those compares and change
>>>>> them accordingly, best in fold_stmt.
>>>>>
>>>>> Richard.
>>>>
>>>> Hmm, I tried to add this code-pattern to fold_stmt, but for this kind
>>>> of branch it seems not to be invoked at all. At least not now without
>>>> boolification of compares. ?One nit I found for GIMPLE_BINARY, as here
>>>> just patterns getting replaced, which have fewer number of ops then
>>>> original statement. This check looks a bit bogus.
>>>> For getting this normalization right now in a consistant way,
>>>> fold-const might be right now the better place to handle this.
>>>
>>> It gets invoked (well, should get invoked) when anyone changes the
>>> statement. ?If it is present in that form from the beginning then we
>>> lack canonicalization in fold and/or gimplification.
>>>
>>> I suppose you have a testcase?
>>>
>>> Richard.
>>>
>>>> Regards,
>>>> Kai
>>>>
>>
>> Yes, testcase looks like this:
>>
>> int foo (_Bool a, _Bool b)
>> {
>> ?return a != ((b | !b));
>> }
>>
>> while reduces to
>> ...
>> return a != 1; ?right now, and not a == 0 (as a is boolean)
>
> fold_stmt should be called when copyprop produces a != 1
> via substitute_and_fold:
>
> ? ? ? ? ?/* Replace real uses in the statement. ?*/
> ? ? ? ? ?if (get_value_fn)
> ? ? ? ? ? ?did_replace |= replace_uses_in (stmt, get_value_fn);
>
> ? ? ? ? ?/* If we made a replacement, fold the statement. ?*/
> ? ? ? ? ?if (did_replace)
> ? ? ? ? ? ?fold_stmt (&oldi);

Well, I added this transformation for test in fold-const s
fold_comparison function and still it doesn't get converted.
I assume this caused by the fact that we do this optimization in
forwprop on argument's of the comparison, so no try to fold statement
happens here at this place.

Kai