Re: [patch tree-optimization]: Avoid !=/== 0/1 comparisons for boolean-typed argument

[Richard Guenther <richard dot guenther at gmail dot com>]

On Tue, Aug 2, 2011 at 12:17 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> Hello,
>
> this patch removes in forward-propagation useless comparisons X != 0
> and X != ~0 for boolean-typed X. ?For one-bit precision typed X we
> simplifiy X == 0 (and X != ~0) to ~X, and for X != 0 (and X == ~0) to
> X.
> For none one-bit precisione typed X, we simplify here X == 0 -> X ^ 1,
> and for X != 0 -> X. ?We can do this as even for Ada - which has only
> boolean-type with none-one-bit precision - the truth-value is one.

This isn't a simplification but a canonicalization and thus should be
done by fold_stmt instead (we are not propagating anything after all).
In fact, fold_stmt should do parts of this already by means of its
canonicalizations via fold.

> Additionally this patch changes for function
> forward_propagate_comparison the meaning of true-result. ?As this
> result wasn't used and it is benefitial to use this propagation also

which is a bug - for a true return value we need to set cfg_changed to true.

> in second loop in function ssa_forward_propagate_and_combine, it
> returns true iff statement was altered. ?Additionally this function
> handles now the boolean-typed simplifications.

why call it twice?  How should that be "beneficial"?  I think that
forward_propagate_into_comparison should instead fold the changed
statement.

> For the hunk in gimple.c for function canonicalize_cond_expr_cond:
> This change seems to show no real effect, but IMHO it makes sense to
> add here the check for cast from boolean-type to be consitant.

Probably yes.

Thanks,
Richard.

> ChangeLog
>
> 2011-08-02 ?Kai Tietz ?<ktietz@redhat.com>
>
> ? ? ? ?* gimple.c (canonicalize_cond_expr_cond): Handle cast from boolean-type.
> ? ? ? ?* tree-ssa-forwprop.c (forward_propagate_comparison): Return
> true iff statement was modified.
> ? ? ? ?Handle boolean-typed simplification for EQ_EXPR/NE_EXPR.
> ? ? ? ?(ssa_forward_propagate_and_combine): Call
> forward_propagate_comparison for comparisons.
>
> 2011-08-02 ?Kai Tietz ?<ktietz@redhat.com>
>
> ? ? ? ?* gcc.dg/tree-ssa/forwprop-9.c: New testcase.
>
>
> Bootstrapped and regression tested for all languages (including Ada
> and Obj-C++) on host x86_64-pc-linux-gnu. ?Ok for apply?
>
> Regards,
> Kai
>
> Index: gcc/gcc/gimple.c
> ===================================================================
> --- gcc.orig/gcc/gimple.c
> +++ gcc/gcc/gimple.c
> @@ -3160,7 +3160,9 @@ canonicalize_cond_expr_cond (tree t)
> ?{
> ? /* Strip conversions around boolean operations. ?*/
> ? if (CONVERT_EXPR_P (t)
> - ? ? ?&& truth_value_p (TREE_CODE (TREE_OPERAND (t, 0))))
> + ? ? ?&& (truth_value_p (TREE_CODE (TREE_OPERAND (t, 0)))
> + ? ? ? ? ?|| TREE_CODE (TREE_TYPE (TREE_OPERAND (t, 0)))
> + ? ? ? ? ? ?== BOOLEAN_TYPE))
> ? ? t = TREE_OPERAND (t, 0);
>
> ? /* For !x use x == 0. ?*/
> Index: gcc/gcc/tree-ssa-forwprop.c
> ===================================================================
> --- gcc.orig/gcc/tree-ssa-forwprop.c
> +++ gcc/gcc/tree-ssa-forwprop.c
> @@ -1114,7 +1114,18 @@ forward_propagate_addr_expr (tree name,
> ? ? ?a_1 = (T')cond_1
> ? ? ?a_1 = !cond_1
> ? ? ?a_1 = cond_1 != 0
> - ? Returns true if stmt is now unused. ?*/
> + ? ? For boolean typed comparisons with type-precision of one
> + ? ? X == 0 -> ~X
> + ? ? X != ~0 -> ~X
> + ? ? X != 0 -> X
> + ? ? X == ~0 -> X
> + ? ? For boolean typed comparison with none one-bit type-precision
> + ? ? we can assume that truth-value is one, and false-value is zero.
> + ? ? X == 1 -> X
> + ? ? X != 1 -> X ^ 1
> + ? ? X == 0 -> X ^ 1
> + ? ? X != 0 -> X
> + ? Returns true if stmt is changed. ?*/
>
> ?static bool
> ?forward_propagate_comparison (gimple stmt)
> @@ -1123,9 +1134,48 @@ forward_propagate_comparison (gimple stm
> ? gimple use_stmt;
> ? tree tmp = NULL_TREE;
> ? gimple_stmt_iterator gsi;
> - ?enum tree_code code;
> + ?enum tree_code code = gimple_assign_rhs_code (stmt);
> ? tree lhs;
>
> + ?/* Simplify X != 0 -> X and X == 0 -> ~X, if X is boolean-typed
> + ? ? and X has a compatible type to the comparison-expression. ?*/
> + ?if ((code == EQ_EXPR || code == NE_EXPR)
> + ? ? ?&& TREE_CODE (TREE_TYPE (gimple_assign_rhs1 (stmt))) == BOOLEAN_TYPE
> + ? ? ?&& TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST
> + ? ? ?/* A comparison is always boolean-typed, but there might be
> + ? ? ? ?differences in mode-size. ?*/
> + ? ? ?&& useless_type_conversion_p (TREE_TYPE (name),
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? TREE_TYPE (gimple_assign_rhs1 (stmt))))
> + ? ?{
> + ? ? ?tree tmp2;
> +
> + ? ? ?/* Normalize to reduce cases. ?*/
> + ? ? ?if (!integer_zerop (gimple_assign_rhs2 (stmt)))
> + ? ? ? ?code = (code == EQ_EXPR ? NE_EXPR : EQ_EXPR);
> + ? ? ?tmp = gimple_assign_rhs1 (stmt);
> + ? ? ?tmp2 = NULL_TREE;
> +
> + ? ? ?/* Convert X == 0 -> ~X for 1-bit precision boolean-type.
> + ? ? ? ?Otherwise convert X == 0 -> X ^ 1. ?*/
> + ? ? ?if (code == EQ_EXPR)
> + ? ? ? {
> + ? ? ? ? if (TYPE_PRECISION (TREE_TYPE (tmp)) == 1)
> + ? ? ? ? ? code = BIT_NOT_EXPR;
> + ? ? ? ? else
> + ? ? ? ? ? {
> + ? ? ? ? ? ? code = BIT_XOR_EXPR;
> + ? ? ? ? ? ? tmp2 = build_one_cst (TREE_TYPE (tmp));
> + ? ? ? ? ? }
> + ? ? ? }
> + ? ? ?else
> + ? ? ? code = TREE_CODE (tmp);
> + ? ? ?gsi = gsi_for_stmt (stmt);
> + ? ? ?gimple_assign_set_rhs_with_ops (&gsi, code,
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? tmp, tmp2);
> + ? ? ?update_stmt (stmt);
> + ? ? ?return true;
> + ? ?}
> +
> ? /* Don't propagate ssa names that occur in abnormal phis. ?*/
> ? if ((TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
> ? ? ? ?&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
> @@ -1179,7 +1229,8 @@ forward_propagate_comparison (gimple stm
> ? ? }
>
> ? /* Remove defining statements. ?*/
> - ?return remove_prop_source_from_use (name);
> + ?remove_prop_source_from_use (name);
> + ?return true;
> ?}
>
>
> @@ -2459,6 +2510,9 @@ ssa_forward_propagate_and_combine (void)
> ? ? ? ? ? ? ? ? ? ? ? ?(!no_warning && changed,
> ? ? ? ? ? ? ? ? ? ? ? ? stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
> ? ? ? ? ? ? ? ? ? ?changed = did_something != 0;
> + ? ? ? ? ? ? ? ? ? if (!changed)
> + ? ? ? ? ? ? ? ? ? ? changed = forward_propagate_comparison (stmt);
> +
> ? ? ? ? ? ? ? ? ?}
> ? ? ? ? ? ? ? ?else if (code == BIT_AND_EXPR
> ? ? ? ? ? ? ? ? ? ? ? ? || code == BIT_IOR_EXPR
> Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/forwprop-9.c
> ===================================================================
> --- gcc.orig/gcc/testsuite/gcc.dg/tree-ssa/forwprop-9.c
> +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/forwprop-9.c
> @@ -1,21 +1,14 @@
> ?/* { dg-do compile } */
> -/* { dg-options "-O1 -fdump-tree-optimized -fdump-tree-fre1 -W -Wall
> -fno-early-inlining" } */
> +/* { dg-options "-O2 -fdump-tree-forwprop1" } ?*/
>
> -int b;
> -unsigned a;
> -static inline int *g(void)
> +_Bool
> +foo (_Bool a, _Bool b, _Bool c
> ?{
> - ?a = 1;
> - ?return (int*)&a;
> + ?_Bool r1 = a == 0 & b != 0;
> + ?_Bool r2 = b != 0 & c == 0;
> + ?return (r1 == 0 & r2 == 0);
> ?}
> -void f(void)
> -{
> - ? b = *g();
> -}
> -
> -/* We should have converted the assignments to two = 1. ?FRE does this. ?*/
>
> -/* { dg-final { scan-tree-dump-times " = 1" 2 "optimized"} } */
> -/* { dg-final { scan-tree-dump-not " = a;" "fre1"} } */
> -/* { dg-final { cleanup-tree-dump "fre1" } } */
> -/* { dg-final { cleanup-tree-dump "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " == " 0 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times " != " 0 "forwprop1" } } */
> +/* { dg-final { cleanup-tree-dump "forwprop1" } } */
>