From patchwork Tue Aug 2 10:17:54 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kai Tietz X-Patchwork-Id: 107882 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 5CBA7B71BE for ; Tue, 2 Aug 2011 20:18:17 +1000 (EST) Received: (qmail 22539 invoked by alias); 2 Aug 2011 10:18:15 -0000 Received: (qmail 22496 invoked by uid 22791); 2 Aug 2011 10:18:09 -0000 X-SWARE-Spam-Status: No, hits=-1.8 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_ENVFROM_END_DIGIT, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, TW_TM X-Spam-Check-By: sourceware.org Received: from mail-qy0-f175.google.com (HELO mail-qy0-f175.google.com) (209.85.216.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 02 Aug 2011 10:17:55 +0000 Received: by qyk30 with SMTP id 30so1559277qyk.20 for ; Tue, 02 Aug 2011 03:17:54 -0700 (PDT) MIME-Version: 1.0 Received: by 10.229.56.12 with SMTP id w12mr2543761qcg.102.1312280274309; Tue, 02 Aug 2011 03:17:54 -0700 (PDT) Received: by 10.229.99.137 with HTTP; Tue, 2 Aug 2011 03:17:54 -0700 (PDT) Date: Tue, 2 Aug 2011 12:17:54 +0200 Message-ID: Subject: [patch tree-optimization]: Avoid !=/== 0/1 comparisons for boolean-typed argument From: Kai Tietz To: GCC Patches Cc: Richard Guenther X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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. 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 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. 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. ChangeLog 2011-08-02 Kai Tietz * 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 * 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" } } */