From patchwork Thu Jul 26 16:01:08 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Marc Glisse X-Patchwork-Id: 173461 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 A4E0F2C0093 for ; Fri, 27 Jul 2012 02:01:50 +1000 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1343923311; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Date:From:To:cc:Subject:In-Reply-To:Message-ID:References: User-Agent:MIME-Version:Content-Type:Mailing-List:Precedence: List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender: Delivered-To; bh=8D+QjdsXKp1OyxRjqjFZP+SWIGA=; b=xfAKXpdWKVL46lQ JIrq/CuFGmZOi7dt/wfzpybOEdk5kFhs/L5p/tyUtuar1AEUV7LBs5VieXNkT9fx g2dj8BNByGHiZIltDtmEsQ4tZQAtNieEcepsU8bdc7oKqnAbLL4myE3YSbDg2Ueb NoIr5mQ+AStKBCTIDXDOcCOQNtvM= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Received:Date:From:To:cc:Subject:In-Reply-To:Message-ID:References:User-Agent:MIME-Version:Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=ulDfUrMhqF4P8I8p3mR0wM2qkcJJcqslpniTLVlF9ytQVLvkiAROb1mZgShlSk /Z7lCDrTul0Jfz1gYLt1gN/t9UW2rcAvOaYi97uXJP+2JIIrda6x/FmkuxiUOJbA c8f+skauvAUwiX9/zZpSnYRjt8T8xDDL8dCZL3H+9Wv1g=; Received: (qmail 11409 invoked by alias); 26 Jul 2012 16:01:42 -0000 Received: (qmail 11370 invoked by uid 22791); 26 Jul 2012 16:01:37 -0000 X-SWARE-Spam-Status: No, hits=-6.3 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, KHOP_THREADED, RCVD_IN_DNSWL_HI, SARE_OBFU_ALL, TW_TM, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail4-relais-sop.national.inria.fr (HELO mail4-relais-sop.national.inria.fr) (192.134.164.105) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 26 Jul 2012 16:01:11 +0000 Received: from stedding.saclay.inria.fr ([193.55.250.194]) by mail4-relais-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES128-SHA; 26 Jul 2012 18:01:08 +0200 Received: from glisse (helo=localhost) by stedding.saclay.inria.fr with local-esmtp (Exim 4.80) (envelope-from ) id 1SuQUu-0004nL-IF; Thu, 26 Jul 2012 18:01:08 +0200 Date: Thu, 26 Jul 2012 18:01:08 +0200 (CEST) From: Marc Glisse To: Andrew Pinski cc: Richard Guenther , GCC Patches Subject: Re: [PATCH] Improve ifcombine (PR 52005) In-Reply-To: Message-ID: References: User-Agent: Alpine 2.02 (DEB 1266 2009-07-14) MIME-Version: 1.0 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, here is a new version of the ifcombine patch, which handles Andrew's examples (though only with -O2 for one of them, same_phi_args_p returns false otherwise). Note that the new patch never calls maybe_fold_or_comparisons, only maybe_fold_and_comparisons. It would be possible to call maybe_fold_or_comparisons, when maybe_fold_and_comparisons fails, but I don't know if there are optimizations that one does and not the other, except for the odd trapping-math case. Bootstrap and testsuite are fine. 2012-07-26 Marc Glisse gcc/ PR tree-optimization/51938 PR tree-optimization/52005 * tree-ssa-ifcombine.c (ifcombine_ifandif): New parameters for inverted conditions. (ifcombine_iforif): Remove, merge code into ifcombine_ifandif. (tree_ssa_ifcombine_bb): Update calls to the above. Detect !a&&b and !a||b patterns. gcc/testsuite/ PR tree-optimization/51938 PR tree-optimization/52005 * gcc.dg/tree-ssa/ssa-ifcombine-8.c: New testcase. * gcc.dg/tree-ssa/ssa-ifcombine-9.c: Likewise. * gcc.dg/tree-ssa/ssa-ifcombine-10.c: Likewise. * gcc.dg/tree-ssa/ssa-ifcombine-11.c: Likewise. Index: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-10.c =================================================================== --- testsuite/gcc.dg/tree-ssa/ssa-ifcombine-10.c (revision 0) +++ testsuite/gcc.dg/tree-ssa/ssa-ifcombine-10.c (revision 0) @@ -0,0 +1,20 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +/* Testcase for PR31657. */ + +int f(int x, int a, int b) +{ + int t = 0; + int c = 1 << a; + if (!(x & 1)) + t = 0; + else + if (x & (1 << 2)) + t = 3; + else + t = 0; + return t; +} +/* { dg-final { scan-tree-dump "& 5" "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Property changes on: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-10.c ___________________________________________________________________ Added: svn:keywords + Author Date Id Revision URL Added: svn:eol-style + native Index: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c =================================================================== --- testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c (revision 0) +++ testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c (revision 0) @@ -0,0 +1,25 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fno-trapping-math -fdump-tree-ifcombine" } */ + +double test1 (double i, double j) +{ + if (i >= j) + if (i <= j) + goto plif; + else + goto plouf; + else + goto plif; + +plif: + return 0; +plouf: + return -1; +} + +/* The above should be optimized to a i > j test by ifcombine. + The transformation would also be legal with -ftrapping-math. + Instead we get u<=, which is acceptable with -fno-trapping-math. */ + +/* { dg-final { scan-tree-dump " u<= " "ifcombine" } } */ +/* { dg-final { cleanup-tree-dump "ifcombine" } } */ Property changes on: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c ___________________________________________________________________ Added: svn:keywords + Author Date Id Revision URL Added: svn:eol-style + native Index: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-11.c =================================================================== --- testsuite/gcc.dg/tree-ssa/ssa-ifcombine-11.c (revision 0) +++ testsuite/gcc.dg/tree-ssa/ssa-ifcombine-11.c (revision 0) @@ -0,0 +1,21 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-optimized" } */ + +/* Testcase for PR31657. */ +int g(void); +int f(int x, int a, int b) +{ + int t = 0; + int c = 1 << a; + if (!(x & 1)) + t = 0; + else + if (x & (1 << 2)) + t = g(); + else + t = 0; + return t; +} + +/* { dg-final { scan-tree-dump "& 5" "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Property changes on: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-11.c ___________________________________________________________________ Added: svn:keywords + Author Date Id Revision URL Added: svn:eol-style + native Index: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c =================================================================== --- testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c (revision 0) +++ testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c (revision 0) @@ -0,0 +1,22 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fno-trapping-math -fdump-tree-ifcombine" } */ + +void f (); +enum Sign { NEG=-1, ZERO, POS }; + +static inline enum Sign sign (double x) +{ + if (x > 0) return POS; + if (x < 0) return NEG; + return ZERO; +} +void g (double x) +{ + if (sign (x) == NEG) f(); +} + +/* The above should be optimized to x < 0 by ifcombine. + The transformation would also be legal with -ftrapping-math. */ + +/* { dg-final { scan-tree-dump "optimizing.* < " "ifcombine" } } */ +/* { dg-final { cleanup-tree-dump "ifcombine" } } */ Property changes on: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c ___________________________________________________________________ Added: svn:keywords + Author Date Id Revision URL Added: svn:eol-style + native Index: tree-ssa-ifcombine.c =================================================================== --- tree-ssa-ifcombine.c (revision 189891) +++ tree-ssa-ifcombine.c (working copy) @@ -159,26 +159,26 @@ get_name_for_bit_test (tree candidate) return candidate; } /* Recognize a single bit test pattern in GIMPLE_COND and its defining statements. Store the name being tested in *NAME and the bit in *BIT. The GIMPLE_COND computes *NAME & (1 << *BIT). Returns true if the pattern matched, false otherwise. */ static bool -recognize_single_bit_test (gimple cond, tree *name, tree *bit) +recognize_single_bit_test (gimple cond, tree *name, tree *bit, bool inv) { gimple stmt; /* Get at the definition of the result of the bit test. */ - if (gimple_cond_code (cond) != NE_EXPR + if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR) || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME || !integer_zerop (gimple_cond_rhs (cond))) return false; stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond)); if (!is_gimple_assign (stmt)) return false; /* Look at which bit is tested. One form to recognize is D.1985_5 = state_3(D) >> control1_4(D); D.1986_6 = (int) D.1985_5; @@ -267,170 +267,118 @@ recognize_single_bit_test (gimple cond, return false; } /* Recognize a bit test pattern in a GIMPLE_COND and its defining statements. Store the name being tested in *NAME and the bits in *BITS. The COND_EXPR computes *NAME & *BITS. Returns true if the pattern matched, false otherwise. */ static bool -recognize_bits_test (gimple cond, tree *name, tree *bits) +recognize_bits_test (gimple cond, tree *name, tree *bits, bool inv) { gimple stmt; /* Get at the definition of the result of the bit test. */ - if (gimple_cond_code (cond) != NE_EXPR + if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR) || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME || !integer_zerop (gimple_cond_rhs (cond))) return false; stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond)); if (!is_gimple_assign (stmt) || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR) return false; *name = get_name_for_bit_test (gimple_assign_rhs1 (stmt)); *bits = gimple_assign_rhs2 (stmt); return true; } /* If-convert on a and pattern with a common else block. The inner if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB. + inner_inv, outer_inv and result_inv indicate whether the conditions + are inverted. Returns true if the edges to the common else basic-block were merged. */ static bool -ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb) +ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv, + basic_block outer_cond_bb, bool outer_inv, bool result_inv) { gimple_stmt_iterator gsi; gimple inner_cond, outer_cond; - tree name1, name2, bit1, bit2; + tree name1, name2, bit1, bit2, bits1, bits2; inner_cond = last_stmt (inner_cond_bb); if (!inner_cond || gimple_code (inner_cond) != GIMPLE_COND) return false; outer_cond = last_stmt (outer_cond_bb); if (!outer_cond || gimple_code (outer_cond) != GIMPLE_COND) return false; /* See if we test a single bit of the same name in both tests. In that case remove the outer test, merging both else edges, and change the inner one to test for name & (bit1 | bit2) == (bit1 | bit2). */ - if (recognize_single_bit_test (inner_cond, &name1, &bit1) - && recognize_single_bit_test (outer_cond, &name2, &bit2) + if (recognize_single_bit_test (inner_cond, &name1, &bit1, inner_inv) + && recognize_single_bit_test (outer_cond, &name2, &bit2, outer_inv) && name1 == name2) { tree t, t2; /* Do it. */ gsi = gsi_for_stmt (inner_cond); t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1), build_int_cst (TREE_TYPE (name1), 1), bit1); t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1), build_int_cst (TREE_TYPE (name1), 1), bit2); t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2); t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, true, GSI_SAME_STMT); t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t); t2 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE, true, GSI_SAME_STMT); - t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t); + t = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR, + boolean_type_node, t2, t); t = canonicalize_cond_expr_cond (t); if (!t) return false; gimple_cond_set_condition_from_tree (inner_cond, t); update_stmt (inner_cond); /* Leave CFG optimization to cfg_cleanup. */ - gimple_cond_set_condition_from_tree (outer_cond, boolean_true_node); + gimple_cond_set_condition_from_tree (outer_cond, + outer_inv ? boolean_false_node : boolean_true_node); update_stmt (outer_cond); if (dump_file) { fprintf (dump_file, "optimizing double bit test to "); print_generic_expr (dump_file, name1, 0); fprintf (dump_file, " & T == T\nwith temporary T = (1 << "); print_generic_expr (dump_file, bit1, 0); fprintf (dump_file, ") | (1 << "); print_generic_expr (dump_file, bit2, 0); fprintf (dump_file, ")\n"); } return true; } - /* See if we have two comparisons that we can merge into one. */ - else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison - && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison) - { - tree t; - - if (!(t = maybe_fold_and_comparisons (gimple_cond_code (inner_cond), - gimple_cond_lhs (inner_cond), - gimple_cond_rhs (inner_cond), - gimple_cond_code (outer_cond), - gimple_cond_lhs (outer_cond), - gimple_cond_rhs (outer_cond)))) - return false; - t = canonicalize_cond_expr_cond (t); - if (!t) - return false; - gimple_cond_set_condition_from_tree (inner_cond, t); - update_stmt (inner_cond); - - /* Leave CFG optimization to cfg_cleanup. */ - gimple_cond_set_condition_from_tree (outer_cond, boolean_true_node); - update_stmt (outer_cond); - - if (dump_file) - { - fprintf (dump_file, "optimizing two comparisons to "); - print_generic_expr (dump_file, t, 0); - fprintf (dump_file, "\n"); - } - - return true; - } - - return false; -} - -/* If-convert on a or pattern with a common then block. The inner - if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB. - Returns true, if the edges leading to the common then basic-block - were merged. */ - -static bool -ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb) -{ - gimple inner_cond, outer_cond; - tree name1, name2, bits1, bits2; - - inner_cond = last_stmt (inner_cond_bb); - if (!inner_cond - || gimple_code (inner_cond) != GIMPLE_COND) - return false; - - outer_cond = last_stmt (outer_cond_bb); - if (!outer_cond - || gimple_code (outer_cond) != GIMPLE_COND) - return false; - /* See if we have two bit tests of the same name in both tests. In that case remove the outer test and change the inner one to test for name & (bits1 | bits2) != 0. */ - if (recognize_bits_test (inner_cond, &name1, &bits1) - && recognize_bits_test (outer_cond, &name2, &bits2)) + else if (recognize_bits_test (inner_cond, &name1, &bits1, !inner_inv) + && recognize_bits_test (outer_cond, &name2, &bits2, !outer_inv)) { gimple_stmt_iterator gsi; tree t; /* Find the common name which is bit-tested. */ if (name1 == name2) ; else if (bits1 == bits2) { t = name2; @@ -475,69 +423,86 @@ ifcombine_iforif (basic_block inner_cond } /* Do it. */ gsi = gsi_for_stmt (inner_cond); t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2); t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, true, GSI_SAME_STMT); t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t); t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, true, GSI_SAME_STMT); - t = fold_build2 (NE_EXPR, boolean_type_node, t, + t = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR, boolean_type_node, t, build_int_cst (TREE_TYPE (t), 0)); t = canonicalize_cond_expr_cond (t); if (!t) return false; gimple_cond_set_condition_from_tree (inner_cond, t); update_stmt (inner_cond); /* Leave CFG optimization to cfg_cleanup. */ - gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node); + gimple_cond_set_condition_from_tree (outer_cond, + outer_inv ? boolean_false_node : boolean_true_node); update_stmt (outer_cond); if (dump_file) { fprintf (dump_file, "optimizing bits or bits test to "); print_generic_expr (dump_file, name1, 0); fprintf (dump_file, " & T != 0\nwith temporary T = "); print_generic_expr (dump_file, bits1, 0); fprintf (dump_file, " | "); print_generic_expr (dump_file, bits2, 0); fprintf (dump_file, "\n"); } return true; } - /* See if we have two comparisons that we can merge into one. - This happens for C++ operator overloading where for example - GE_EXPR is implemented as GT_EXPR || EQ_EXPR. */ - else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison + /* See if we have two comparisons that we can merge into one. */ + else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison) { tree t; + enum tree_code inner_cond_code = gimple_cond_code (inner_cond); + enum tree_code outer_cond_code = gimple_cond_code (outer_cond); - if (!(t = maybe_fold_or_comparisons (gimple_cond_code (inner_cond), - gimple_cond_lhs (inner_cond), - gimple_cond_rhs (inner_cond), - gimple_cond_code (outer_cond), - gimple_cond_lhs (outer_cond), - gimple_cond_rhs (outer_cond)))) + /* Invert comparisons if necessary (and possible). */ + if (inner_inv) + inner_cond_code = invert_tree_comparison (inner_cond_code, + HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (inner_cond))))); + if (inner_cond_code == ERROR_MARK) return false; + if (outer_inv) + outer_cond_code = invert_tree_comparison (outer_cond_code, + HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (outer_cond))))); + if (outer_cond_code == ERROR_MARK) + return false; + /* Don't return false so fast, try maybe_fold_or_comparisons? */ + + if (!(t = maybe_fold_and_comparisons (inner_cond_code, + gimple_cond_lhs (inner_cond), + gimple_cond_rhs (inner_cond), + outer_cond_code, + gimple_cond_lhs (outer_cond), + gimple_cond_rhs (outer_cond)))) + return false; + if (result_inv) + t = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (t), t); t = canonicalize_cond_expr_cond (t); if (!t) return false; gimple_cond_set_condition_from_tree (inner_cond, t); update_stmt (inner_cond); /* Leave CFG optimization to cfg_cleanup. */ - gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node); + gimple_cond_set_condition_from_tree (outer_cond, + outer_inv ? boolean_false_node : boolean_true_node); update_stmt (outer_cond); if (dump_file) { fprintf (dump_file, "optimizing two comparisons to "); print_generic_expr (dump_file, t, 0); fprintf (dump_file, "\n"); } return true; @@ -580,40 +545,77 @@ tree_ssa_ifcombine_bb (basic_block inner { /* We have if (q) goto inner_cond_bb; else goto else_bb; if (p) goto ...; else goto else_bb; ... ... */ - return ifcombine_ifandif (inner_cond_bb, outer_cond_bb); + return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, false, + false); + } + + /* And a version where the outer condition is negated. */ + if (recognize_if_then_else (outer_cond_bb, &else_bb, &inner_cond_bb) + && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb) + && bb_no_side_effects_p (inner_cond_bb)) + { + /* We have + + if (q) goto else_bb; else goto inner_cond_bb; + + if (p) goto ...; else goto else_bb; + ... + + ... + */ + return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, true, + false); } /* The || form is characterized by a common then_bb with the two edges leading to it mergable. The latter is guaranteed by matching PHI arguments in the then_bb and the inner cond_bb having no side-effects. */ if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb) && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb) && bb_no_side_effects_p (inner_cond_bb)) { /* We have if (q) goto then_bb; else goto inner_cond_bb; if (q) goto then_bb; else goto ...; ... */ - return ifcombine_iforif (inner_cond_bb, outer_cond_bb); + return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, true, + true); + } + + /* And a version where the outer condition is negated. */ + if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &then_bb) + && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb) + && bb_no_side_effects_p (inner_cond_bb)) + { + /* We have + + if (q) goto inner_cond_bb; else goto then_bb; + + if (q) goto then_bb; else goto ...; + + ... + */ + return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, false, + true); } } return false; } /* Main entry for the tree if-conversion pass. */ static unsigned int tree_ssa_ifcombine (void)