From patchwork Sun Nov 6 22:17:21 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kai Tietz X-Patchwork-Id: 123977 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 7CAE91007D5 for ; Mon, 7 Nov 2011 09:17:49 +1100 (EST) Received: (qmail 22385 invoked by alias); 6 Nov 2011 22:17:48 -0000 Received: (qmail 22369 invoked by uid 22791); 6 Nov 2011 22:17:42 -0000 X-SWARE-Spam-Status: No, hits=-7.6 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_HI, RP_MATCHES_RCVD, SPF_HELO_PASS, TW_CF, TW_TM X-Spam-Check-By: sourceware.org Received: from mx3-phx2.redhat.com (HELO mx3-phx2.redhat.com) (209.132.183.24) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sun, 06 Nov 2011 22:17:22 +0000 Received: from zmail14.collab.prod.int.phx2.redhat.com (zmail14.collab.prod.int.phx2.redhat.com [10.5.83.16]) by mx3-phx2.redhat.com (8.13.8/8.13.8) with ESMTP id pA6MHLP0016448; Sun, 6 Nov 2011 17:17:21 -0500 Date: Sun, 06 Nov 2011 17:17:21 -0500 (EST) From: Kai Tietz To: gcc-patches@gcc.gnu.org Cc: Jeff Law , Richard Henderson Subject: [patch tree-optimization 2/2]: Branch-cost optimizations Message-ID: <038a3161-065e-47c3-8222-8e8815bca853@zmail14.collab.prod.int.phx2.redhat.com> In-Reply-To: <5bf789cf-852c-4218-a3c9-e237896257c3@zmail14.collab.prod.int.phx2.redhat.com> MIME-Version: 1.0 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, the second patch extends the tree-ssa-ifcombine pass so, that it chains up simple if-and/or-if patterns via associative bitwise-and/or operations. This allows for example optimization for cases like: if (c == 0) return 2; if (c == 1) return 2; if (c == 2) return 2; ... as now reassociation-pass can optimize on them. ChangeLog 2011-11-06 Kai Tietz * tree-ssa-ifcombine.c (remove_stmt_chain): New helper. (update_gimple_cond_condtion_from_tree): Likewise. (stmt_no_side_effects_p): Likewise. (bb_no_side_effects_p): Use stmt_no_side_effects_p. (bb_no_side_effects_p_2): New helper function. (same_phi_args_p_2): Likewise. (recognize_single_bit_test): Allow equal and not-equal comparison handling. (ifcombine_ifandif): Handle equal and not-equal (X & CST) !=/== 0 optimization. (ifcombine_ifandif_merge): New helper for tree_ssa_ifmerge_bb. (ifcombine_iforif_merge): Likewise. (ifcombine_iforif): Simplify routine. (tree_ssa_ifmerge_bb): New helper for doing if-branch merging. (tree_ssa_ifcombine_bb): Adjust pattern-searching for iforif and ifandif. (tree_ssa_ifcombine): Add if-branch merging and allow multiple folding for if-combining. ChangeLog testsuite 2011-11-06 Kai Tietz * gcc.dg/tree-ssa/phi-opt-2.c: Adjust test. * gcc.dg/tree-ssa/ifcombine-8.c: New test. * gcc.dg/tree-ssa/ifcombine-9.c: New test. * gcc.dg/tree-ssa/ifcombine-10.c: New test. * gcc.dg/tree-ssa/ifcombine-11.c: New test. * gcc.dg/tree-ssa/ifcombine-12.c: New test. Bootstrapped and regression-tested for x86_64-unknown-linux-gnu for all languages (include Ada and Obj-C++). Ok for apply? Regards, Kai ChangeLog 2011-11-06 Kai Tietz * tree-ssa-ifcombine.c (remove_stmt_chain): New helper. (update_gimple_cond_condtion_from_tree): Likewise. (stmt_no_side_effects_p): Likewise. (bb_no_side_effects_p): Use stmt_no_side_effects_p. (bb_no_side_effects_p_2): New helper function. (same_phi_args_p_2): Likewise. (recognize_single_bit_test): Allow equal and not-equal comparison handling. (ifcombine_ifandif): Handle equal and not-equal (X & CST) !=/== 0 optimization. (ifcombine_ifandif_merge): New helper for tree_ssa_ifmerge_bb. (ifcombine_iforif_merge): Likewise. (ifcombine_iforif): Simplify routine. (tree_ssa_ifmerge_bb): New helper for doing if-branch merging. (tree_ssa_ifcombine_bb): Adjust pattern-searching for iforif and ifandif. (tree_ssa_ifcombine): Add if-branch merging and allow multiple folding for if-combining. ChangeLog testsuite 2011-11-06 Kai Tietz * gcc.dg/tree-ssa/phi-opt-2.c: Adjust test. * gcc.dg/tree-ssa/ifcombine-8.c: New test. * gcc.dg/tree-ssa/ifcombine-9.c: New test. * gcc.dg/tree-ssa/ifcombine-10.c: New test. * gcc.dg/tree-ssa/ifcombine-11.c: New test. * gcc.dg/tree-ssa/ifcombine-12.c: New test. Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-2.c =================================================================== --- gcc-trunk.orig/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-2.c +++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-2.c @@ -10,7 +10,7 @@ _Bool f1(_Bool a, _Bool b) else return 0; } - return 0; + return 2; } Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-10.c =================================================================== --- /dev/null +++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-10.c @@ -0,0 +1,15 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-ifcombine" } */ + +int foo (int x) +{ + if ((x & 4) == 0) + if ((x & 8) != 0) + /* returning 1 causes phiopt to trigger in */ + return 2; + return 0; +} + +/* { dg-final { scan-tree-dump "\\& 12" "ifcombine" } } */ +/* { dg-final { scan-tree-dump "== 8" "ifcombine" } } */ +/* { dg-final { cleanup-tree-dump "ifcombine" } } */ Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-11.c =================================================================== --- /dev/null +++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-11.c @@ -0,0 +1,15 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-ifcombine" } */ + +int foo (int x) +{ + if ((x & 4) != 0) + if ((x & 8) == 0) + /* returning 1 causes phiopt to trigger in */ + return 2; + return 0; +} + +/* { dg-final { scan-tree-dump "\\& 12" "ifcombine" } } */ +/* { dg-final { scan-tree-dump "== 4" "ifcombine" } } */ +/* { dg-final { cleanup-tree-dump "ifcombine" } } */ Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-12.c =================================================================== --- /dev/null +++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-12.c @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-ifcombine" } */ + +int foo (int x) +{ + if ((x & 4) != 0) + return 2; + if ((x & 8) != 0) + /* returning 1 causes phiopt to trigger in */ + return 2; + return 0; +} + +/* { dg-final { scan-tree-dump "\\& 12" "ifcombine" } } */ +/* { dg-final { scan-tree-dump "!= 0" "ifcombine" } } */ +/* { dg-final { cleanup-tree-dump "ifcombine" } } */ Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c =================================================================== --- /dev/null +++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c @@ -0,0 +1,15 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-optimized" } */ + +int foo (int x, int a, int b) +{ + int c = 1 << a; + if ((x & c) == 0) + if ((x & (1 << b)) == 0) + /* returning 1 causes phiopt to trigger in */ + return 2; + return 0; +} + +/* { dg-final { scan-tree-dump "\\|" "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c =================================================================== --- /dev/null +++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c @@ -0,0 +1,14 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-ifcombine" } */ + +int foo (int x) +{ + if ((x & 4) == 0) + if ((x & 8) == 0) + /* returning 1 causes phiopt to trigger in */ + return 2; + return 0; +} + +/* { dg-final { scan-tree-dump "\\& 12" "ifcombine" } } */ +/* { dg-final { cleanup-tree-dump "ifcombine" } } */ Index: gcc-trunk/gcc/tree-ssa-ifcombine.c =================================================================== --- gcc-trunk.orig/gcc/tree-ssa-ifcombine.c +++ gcc-trunk/gcc/tree-ssa-ifcombine.c @@ -49,6 +49,65 @@ along with GCC; see the file COPYING3. To simplify this pass, removing basic blocks and dead code is left to CFG cleanup and DCE. */ +/* Remove def stmt of VAR if VAR has zero uses and recurse + on rhs1, rhs2, and rhs3 operand if so. */ + +static void +remove_stmt_chain (tree var) +{ + gimple stmt; + gimple_stmt_iterator gsi; + tree var2, var3; + + while (1) + { + if (TREE_CODE (var) != SSA_NAME || !has_zero_uses (var)) + return; + stmt = SSA_NAME_DEF_STMT (var); + if (!stmt || !is_gimple_assign (stmt)) + return; + var = gimple_assign_rhs1 (stmt); + var2 = var3 = NULL_TREE; + + switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))) + { + case GIMPLE_TERNARY_RHS: + var3 = gimple_assign_rhs3 (stmt); + /* Fall through. */ + case GIMPLE_BINARY_RHS: + var2 = gimple_assign_rhs2 (stmt); + break; + default: + break; + } + gsi = gsi_for_stmt (stmt); + gsi_remove (&gsi, true); + release_defs (stmt); + /* Recurse on optional second and third operand, + if those arguments are of kind SSA_NAME. */ + if (var2 && TREE_CODE (var2) == SSA_NAME) + remove_stmt_chain (var2); + if (var3 && TREE_CODE (var3) == SSA_NAME) + remove_stmt_chain (var3); + } +} + +/* Helper to update a gimple_cond condition by tree + and remove use-chains of old condition. */ + +static void +update_gimple_cond_condition_from_tree (gimple cond, tree t) +{ + tree l, r; + l = gimple_cond_lhs (cond); + r = gimple_cond_rhs (cond); + gimple_cond_set_condition_from_tree (cond, t); + update_stmt (cond); + if (l) + remove_stmt_chain (l); + if (r) + remove_stmt_chain (r); +} /* Recognize a if-then-else CFG pattern starting to match with the COND_BB basic-block containing the COND_EXPR. The recognized @@ -95,6 +154,25 @@ recognize_if_then_else (basic_block cond return true; } +/* Check that a statement STMT doesn't have sider-effect. + and it doesn't have VUSE. + If CHECK_TRAP is true, then additional STMT gets checked + for trapping. */ + +static bool +stmt_no_side_effects_p (gimple stmt, bool check_trap) +{ + if (!stmt) + return true; + if (gimple_code (stmt) == GIMPLE_LABEL) + return false; + if (gimple_has_side_effects (stmt) + || (check_trap && gimple_could_trap_p (stmt)) + || gimple_vuse (stmt)) + return false; + return true; +} + /* Verify if the basic block BB does not have side-effects. Return true in this case, else false. */ @@ -105,16 +183,31 @@ bb_no_side_effects_p (basic_block bb) for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { - gimple stmt = gsi_stmt (gsi); - - if (gimple_has_side_effects (stmt) - || gimple_vuse (stmt)) + if (!stmt_no_side_effects_p (gsi_stmt (gsi), false)) return false; } return true; } +/* Verify if the basic block BB does not have side-effects, or trapping. + Return true in this case, else false. */ + +static bool +bb_no_side_effects_p_2 (basic_block bb) +{ + gimple_stmt_iterator gsi; + + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + if (!stmt_no_side_effects_p (gsi_stmt (gsi), true)) + return false; + } + + return true; +} + + /* Verify if all PHI node arguments in DEST for edges from BB1 or BB2 to DEST are the same. This makes the CFG merge point free from side-effects. Return true in this case, else false. */ @@ -138,6 +231,59 @@ same_phi_args_p (basic_block bb1, basic_ return true; } +/* Verify if all PHI node arguments in DEST1 for edges from BB1, BB2 + or DEST2 to DEST1 are the same. This makes the CFG merge point + free from side-effects. Return true in this case, else false. + If DEST1 is not equal to DEST2, then DEST2 has to have a PHI node + in DEST1 and DEST2 has not hold statements or its own PHI node. + In contrast to same_phi_args_p, function returns for no-PHI valued + branches FALSE. */ + +static bool +same_phi_args_p_2 (basic_block bb1, basic_block bb2, basic_block dest1, basic_block dest2) +{ + edge e1 = find_edge (bb1, dest1); + edge e2 = find_edge (bb2, dest2); + gimple_stmt_iterator gsi1; + gimple_stmt_iterator gsi2; + gimple phi; + + gsi1 = gsi_start_phis (dest1); + if (gsi_end_p (gsi1)) + { + gsi2 = gsi_start_phis (dest2); + return false; + } + + /* See if we can't find a PHI in DEST2 and that we find + a PHI edge in DEST1 for DEST2. */ + gsi2 = gsi_start_phis (dest2); + if (gsi_end_p (gsi2)) + { + /* If DEST2 has no PHI, then it also has not to contain + any statements. */ + if (last_stmt (dest2) != NULL) + return false; + gsi2 = gsi1; + /* See if we can find DEST2 within PHI of DEST1. */ + e2 = find_edge (dest2, dest1); + if (!e2) + return false; + } + else if (dest1 != dest2) + return false; + + for (; !gsi_end_p (gsi1); gsi_next (&gsi1)) + { + phi = gsi_stmt (gsi1); + if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1), + PHI_ARG_DEF_FROM_EDGE (phi, e2), 0)) + return false; + } + + return true; +} + /* Return the best representative SSA name for CANDIDATE which is used in a bit test. */ @@ -165,15 +311,19 @@ get_name_for_bit_test (tree 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). + The GIMPLE_COND code is either NE_EXPR or EQ_EXPR. + IS_CMPEQ will be set to true, if comparison is EQ_EXPR, otherwise + to false. 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 *is_cmpeq) { 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) != NE_EXPR + && gimple_cond_code (cond) != EQ_EXPR) || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME || !integer_zerop (gimple_cond_rhs (cond))) return false; @@ -181,6 +331,8 @@ recognize_single_bit_test (gimple cond, if (!is_gimple_assign (stmt)) return false; + *is_cmpeq = (gimple_cond_code (cond) == EQ_EXPR); + /* 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; @@ -306,62 +458,82 @@ ifcombine_ifandif (basic_block inner_con gimple_stmt_iterator gsi; gimple inner_cond, outer_cond; tree name1, name2, bit1, bit2; + bool is_cmpeq1, is_cmpeq2; 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, &is_cmpeq1) + && recognize_single_bit_test (outer_cond, &name2, &bit2, &is_cmpeq2) && name1 == name2) { - tree t, t2; + tree t, t1, t2; /* Do it. */ gsi = gsi_for_stmt (inner_cond); - t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1), + t1 = 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 = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t1, t2); t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, true, GSI_SAME_STMT); + if (!is_cmpeq1 && !is_cmpeq2) + t1 = t; + else if (is_cmpeq1 && is_cmpeq2) + t1 = build_int_cst (TREE_TYPE (name1), 0); + else if (!is_cmpeq1) + { + t1 = force_gimple_operand_gsi (&gsi, t1, true, NULL_TREE, + true, GSI_SAME_STMT); + } + else if (!is_cmpeq2) + { + t1 = force_gimple_operand_gsi (&gsi, t2, 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 = 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 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"); + t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t1); + + if ((t = canonicalize_cond_expr_cond (t)) != NULL_TREE) + { + update_gimple_cond_condition_from_tree (inner_cond, t); + + /* Leave CFG optimization to cfg_cleanup. */ + update_gimple_cond_condition_from_tree (outer_cond, boolean_true_node); + + if (dump_file) + { + fprintf (dump_file, "optimizing double bit test to "); + print_generic_expr (dump_file, name1, 0); + fprintf (dump_file, " & T == %s\n", + (!is_cmpeq1 && !is_cmpeq2 ? "T" + : (is_cmpeq1 == is_cmpeq2 + ? "0" : "Q"))); + fprintf (dump_file, "with 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"); + if (is_cmpeq1 != is_cmpeq2) + { + fprintf (dump_file, "with temporary Q = (1 << "); + if (!is_cmpeq1) + print_generic_expr (dump_file, bit1, 0); + else + print_generic_expr (dump_file, bit2, 0); + fprintf (dump_file, ")\n"); + } + } + return true; } - - return true; } /* See if we have two comparisons that we can merge into one. */ @@ -370,27 +542,96 @@ ifcombine_ifandif (basic_block inner_con { 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); + 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))) + != NULL + && (t = canonicalize_cond_expr_cond (t)) != NULL) + { + update_gimple_cond_condition_from_tree (inner_cond, t); + + /* Leave CFG optimization to cfg_cleanup. */ + update_gimple_cond_condition_from_tree (outer_cond, boolean_true_node); + + 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 and pattern with a common else block. The inner + if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB. + Returns true if the edges to the common else basic-block were merged + via binary-and. */ + +static bool +ifcombine_ifandif_merge (basic_block inner_cond_bb, basic_block outer_cond_bb) +{ + gimple_stmt_iterator gsi; + gimple inner_cond, outer_cond; + + inner_cond = last_stmt (inner_cond_bb); + outer_cond = last_stmt (outer_cond_bb); + + if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison + && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison) + { + tree t_l, t_r, t, l, r; + location_t loc; + + loc = gimple_location (outer_cond); + t_l = fold_build2_loc (loc, + gimple_cond_code (outer_cond), + boolean_type_node, + gimple_cond_lhs (outer_cond), + gimple_cond_rhs (outer_cond)); + if (tree_could_trap_p (t_l)) + return false; + loc = gimple_location (inner_cond); + t_r = fold_build2_loc (loc, + gimple_cond_code (inner_cond), + boolean_type_node, + gimple_cond_lhs (inner_cond), + gimple_cond_rhs (inner_cond)); + + if (tree_could_trap_p (t_r)) + return false; + gsi = gsi_for_stmt (inner_cond); + t = fold_build2 (BIT_AND_EXPR, boolean_type_node, + t_l, t_r); + t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, + true, GSI_SAME_STMT); + + gsi = gsi_for_stmt (inner_cond); + + l = gimple_cond_lhs (inner_cond); + r = gimple_cond_rhs (inner_cond); + gimple_cond_set_condition (inner_cond, NE_EXPR, t, boolean_false_node); update_stmt (inner_cond); + remove_stmt_chain (l); + if (r) + remove_stmt_chain (r); /* Leave CFG optimization to cfg_cleanup. */ - gimple_cond_set_condition_from_tree (outer_cond, boolean_true_node); - update_stmt (outer_cond); + update_gimple_cond_condition_from_tree (outer_cond, boolean_true_node); if (dump_file) { - fprintf (dump_file, "optimizing two comparisons to "); - print_generic_expr (dump_file, t, 0); + fprintf (dump_file, "branching if.and.if to "); + print_generic_expr (dump_file, t_l, 0); + fprintf (dump_file, " & "); + print_generic_expr (dump_file, t_r, 0); fprintf (dump_file, "\n"); } @@ -408,18 +649,12 @@ ifcombine_ifandif (basic_block inner_con static bool ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb) { + gimple_stmt_iterator gsi; 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 @@ -427,7 +662,6 @@ ifcombine_iforif (basic_block inner_cond if (recognize_bits_test (inner_cond, &name1, &bits1) && recognize_bits_test (outer_cond, &name2, &bits2)) { - gimple_stmt_iterator gsi; tree t; /* Find the common name which is bit-tested. */ @@ -486,28 +720,26 @@ ifcombine_iforif (basic_block inner_cond true, GSI_SAME_STMT); t = fold_build2 (NE_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); - update_stmt (outer_cond); + if ((t = canonicalize_cond_expr_cond (t)) != NULL_TREE) + { + update_gimple_cond_condition_from_tree (inner_cond, t); + + /* Leave CFG optimization to cfg_cleanup. */ + update_gimple_cond_condition_from_tree (outer_cond, boolean_false_node); + + 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"); + } - 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; } - - return true; } /* See if we have two comparisons that we can merge into one. @@ -518,27 +750,97 @@ ifcombine_iforif (basic_block inner_cond { tree t; - 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)))) - return false; - t = canonicalize_cond_expr_cond (t); - if (!t) - return false; - gimple_cond_set_condition_from_tree (inner_cond, t); + 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))) + != NULL + && (t = canonicalize_cond_expr_cond (t)) != NULL) + { + update_gimple_cond_condition_from_tree (inner_cond, t); + + /* Leave CFG optimization to cfg_cleanup. */ + update_gimple_cond_condition_from_tree (outer_cond, boolean_false_node); + + 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 via binary-or. */ + +static bool +ifcombine_iforif_merge (basic_block inner_cond_bb, basic_block outer_cond_bb) +{ + gimple_stmt_iterator gsi; + gimple inner_cond, outer_cond; + + inner_cond = last_stmt (inner_cond_bb); + outer_cond = last_stmt (outer_cond_bb); + + if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison + && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison) + { + tree t_l, t_r, t, l, r; + location_t loc; + + loc = gimple_location (outer_cond); + t_l = fold_build2_loc (loc, + gimple_cond_code (outer_cond), + boolean_type_node, + gimple_cond_lhs (outer_cond), + gimple_cond_rhs (outer_cond)); + + if (tree_could_trap_p (t_l)) + return false; + loc = gimple_location (inner_cond); + t_r = fold_build2_loc (loc, + gimple_cond_code (inner_cond), + boolean_type_node, + gimple_cond_lhs (inner_cond), + gimple_cond_rhs (inner_cond)); + + if (tree_could_trap_p (t_r)) + return false; + gsi = gsi_for_stmt (inner_cond); + t = fold_build2 (BIT_IOR_EXPR, boolean_type_node, + t_l, t_r); + t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, + true, GSI_SAME_STMT); + + gsi = gsi_for_stmt (inner_cond); + l = gimple_cond_lhs (inner_cond); + r = gimple_cond_rhs (inner_cond); + gimple_cond_set_condition (inner_cond, NE_EXPR, t, boolean_false_node); update_stmt (inner_cond); + if (l) + remove_stmt_chain (l); + if (r) + remove_stmt_chain (r); /* Leave CFG optimization to cfg_cleanup. */ - gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node); - update_stmt (outer_cond); + update_gimple_cond_condition_from_tree (outer_cond, boolean_false_node); if (dump_file) { - fprintf (dump_file, "optimizing two comparisons to "); - print_generic_expr (dump_file, t, 0); + fprintf (dump_file, "branching if.or.if to "); + print_generic_expr (dump_file, t_l, 0); + fprintf (dump_file, " | "); + print_generic_expr (dump_file, t_r, 0); fprintf (dump_file, "\n"); } @@ -549,68 +851,326 @@ ifcombine_iforif (basic_block inner_cond } /* Recognize a CFG pattern and dispatch to the appropriate + if-combine helper. We start with BB as the innermost + worker basic-block. Returns true if a transformation was done. */ + +/* Recognize a CFG pattern and dispatch to the appropriate if-conversion helper. We start with BB as the innermost worker basic-block. Returns true if a transformation was done. */ static bool +tree_ssa_ifmerge_bb (basic_block inner_cond_bb) +{ + basic_block outer_cond_bb, outer_else_bb, outer_then_bb; + basic_block then_bb = NULL, else_bb = NULL; + basic_block last_inner_cond_bb; + gimple excond; + bool cfg_changed = false, in_and_seq = false, in_or_seq = false; + + if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb)) + return false; + + /* Has inner bb side-effects? */ + if (!bb_no_side_effects_p_2 (inner_cond_bb)) + return false; + last_inner_cond_bb = inner_cond_bb; + + do + { + /* Recognize && and || of two conditions with a common + then/else block which entry edges we can merge. That is: + if (a || b) + ; + and + if (a && b) + ; + This requires a single predecessor of the inner cond_bb. */ + if (!single_pred_p (last_inner_cond_bb)) + return cfg_changed; + + outer_cond_bb = single_pred (last_inner_cond_bb); + outer_else_bb = NULL; + outer_then_bb = NULL; + + if (!recognize_if_then_else (outer_cond_bb, &outer_then_bb, + &outer_else_bb)) + return cfg_changed; + + /* Check that last_inner_cond_bb doesn't have side-effects. */ + if (last_inner_cond_bb != inner_cond_bb + && !bb_no_side_effects_p_2 (last_inner_cond_bb)) + return cfg_changed; + + if (!bb_no_side_effects_p_2 (outer_cond_bb)) + return cfg_changed; + + /* The && form is characterized by a common else_bb with + the two edges leading to it mergable. The latter is + guaranteed by matching PHI arguments in the else_bb and + the inner cond_bb having no side-effects. */ + if (last_inner_cond_bb == outer_then_bb + && ((else_bb == outer_else_bb + && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb)) + || (outer_else_bb == then_bb + && !same_phi_args_p_2 (outer_cond_bb, inner_cond_bb, + outer_else_bb, then_bb) + && same_phi_args_p_2 (outer_cond_bb, inner_cond_bb, + outer_else_bb, else_bb))) + && bb_no_side_effects_p_2 (inner_cond_bb)) + { + excond = last_stmt (inner_cond_bb); + if (!excond || gimple_code (excond) != GIMPLE_COND + || gimple_cond_true_p (excond) + || gimple_cond_false_p (excond)) + return cfg_changed; + + excond = last_stmt (outer_cond_bb); + if (!excond || gimple_code (excond) != GIMPLE_COND) + return cfg_changed; + + if (gimple_cond_true_p (excond)) + { + last_inner_cond_bb = outer_cond_bb; + continue; + } + else if (gimple_cond_false_p (excond)) + return cfg_changed; + + if (in_or_seq) + return cfg_changed; + + /* We have + + if (q) goto inner_cond_bb; else goto outer_else_bb; + + if (p) goto ...; else goto else_bb; + ... + + + ... + If the else_bb,is not equal to outer_else_bb, then the + else_bb needs to be empty (no PHIs, no statments) and + and the PHI in outer_else_bb for else_bb has to be the + same value as PHI value for outer_else_bb. */ + + if (!ifcombine_ifandif_merge (inner_cond_bb, outer_cond_bb)) + return cfg_changed; + + cfg_changed = true; + in_and_seq = true; + last_inner_cond_bb = outer_cond_bb; + continue; + } + + /* 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 (last_inner_cond_bb == outer_else_bb + && ((then_bb == outer_then_bb + && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb)) + || (outer_then_bb == else_bb + && !same_phi_args_p_2 (outer_cond_bb, inner_cond_bb, + outer_then_bb, else_bb) + && same_phi_args_p_2 (outer_cond_bb, inner_cond_bb, + outer_then_bb, then_bb))) + && bb_no_side_effects_p_2 (inner_cond_bb)) + { + excond = last_stmt (inner_cond_bb); + if (!excond || gimple_code (excond) != GIMPLE_COND + || gimple_cond_false_p (excond) + || gimple_cond_true_p (excond)) + return cfg_changed; + + excond = last_stmt (outer_cond_bb); + if (!excond || gimple_code (excond) != GIMPLE_COND) + return cfg_changed; + + if (gimple_cond_false_p (excond)) + { + last_inner_cond_bb = outer_cond_bb; + continue; + } + else if (gimple_cond_true_p (excond)) + return cfg_changed; + + if (in_and_seq) + return cfg_changed; + + /* We have + + if (q) goto outer_then_bb; else goto inner_cond_bb; + + if (q) goto then_bb; else goto ...; + + + ... + If the then_bb,is not equal to outer_then_bb, then the + then_bb needs to be empty (no PHIs, no statments) and + the PHI in outer_then_bb for then_bb has to be the same value + as PHI value for outer_then_bb. */ + if (!ifcombine_iforif_merge (inner_cond_bb, outer_cond_bb)) + return cfg_changed; + + cfg_changed = true; + in_or_seq = true; + last_inner_cond_bb = outer_cond_bb; + continue; + } + } + while (0); + + return cfg_changed; +} + +static bool tree_ssa_ifcombine_bb (basic_block inner_cond_bb) { + basic_block outer_cond_bb, outer_else_bb, outer_then_bb; basic_block then_bb = NULL, else_bb = NULL; + basic_block last_inner_cond_bb; + gimple excond; + bool in_and_seq = false, in_or_seq = false; if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb)) return false; - /* Recognize && and || of two conditions with a common - then/else block which entry edges we can merge. That is: - if (a || b) - ; - and - if (a && b) - ; - This requires a single predecessor of the inner cond_bb. */ - if (single_pred_p (inner_cond_bb)) + last_inner_cond_bb = inner_cond_bb; + do { - basic_block outer_cond_bb = single_pred (inner_cond_bb); + /* Recognize && and || of two conditions with a common + then/else block which entry edges we can merge. That is: + if (a || b) + ; + and + if (a && b) + ; + This requires a single predecessor of the inner cond_bb. */ + if (!single_pred_p (last_inner_cond_bb)) + return false; + + outer_cond_bb = single_pred (last_inner_cond_bb); + outer_else_bb = NULL; + outer_then_bb = NULL; + + if (!recognize_if_then_else (outer_cond_bb, &outer_then_bb, + &outer_else_bb)) + return false; + + /* Check that last_inner_cond_bb doesn't have side-effects. */ + if (last_inner_cond_bb != inner_cond_bb + && !bb_no_side_effects_p (last_inner_cond_bb)) + return false; /* The && form is characterized by a common else_bb with the two edges leading to it mergable. The latter is guaranteed by matching PHI arguments in the else_bb and the inner cond_bb having no side-effects. */ - if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb) - && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb) + if (last_inner_cond_bb == outer_then_bb + && ((else_bb == outer_else_bb + && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb)) + || (outer_else_bb == then_bb + && !same_phi_args_p_2 (outer_cond_bb, inner_cond_bb, + outer_else_bb, then_bb) + && same_phi_args_p_2 (outer_cond_bb, inner_cond_bb, + outer_else_bb, else_bb))) && bb_no_side_effects_p (inner_cond_bb)) { + excond = last_stmt (inner_cond_bb); + if (!excond || gimple_code (excond) != GIMPLE_COND + || gimple_cond_true_p (excond)) + return false; + + excond = last_stmt (outer_cond_bb); + if (!excond || gimple_code (excond) != GIMPLE_COND) + return false; + + if (gimple_cond_true_p (excond)) + { + last_inner_cond_bb = outer_cond_bb; + continue; + } + else if (gimple_cond_false_p (excond)) + return false; + + if (in_or_seq) + return false; + /* We have - if (q) goto inner_cond_bb; else goto else_bb; + if (q) goto inner_cond_bb; else goto outer_else_bb; if (p) goto ...; else goto else_bb; ... + ... - */ - return ifcombine_ifandif (inner_cond_bb, outer_cond_bb); + If the else_bb,is not equal to outer_else_bb, then the + else_bb needs to be empty (no PHIs, no statments) and + and the PHI in outer_else_bb for else_bb has to be the + same value as PHI value for outer_else_bb. */ + if (ifcombine_ifandif (inner_cond_bb, outer_cond_bb)) + return true; + in_and_seq = true; + last_inner_cond_bb = outer_cond_bb; + continue; } /* 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 + 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) + if (last_inner_cond_bb == outer_else_bb + && ((then_bb == outer_then_bb + && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb)) + || (outer_then_bb == else_bb + && !same_phi_args_p_2 (outer_cond_bb, inner_cond_bb, + outer_then_bb, else_bb) + && same_phi_args_p_2 (outer_cond_bb, inner_cond_bb, + outer_then_bb, then_bb))) && bb_no_side_effects_p (inner_cond_bb)) { + excond = last_stmt (inner_cond_bb); + if (!excond || gimple_code (excond) != GIMPLE_COND + || gimple_cond_false_p (excond)) + return false; + + excond = last_stmt (outer_cond_bb); + if (!excond || gimple_code (excond) != GIMPLE_COND) + return false; + + if (gimple_cond_false_p (excond)) + { + last_inner_cond_bb = outer_cond_bb; + continue; + } + else if (gimple_cond_true_p (excond)) + return false; + + if (in_and_seq) + return false; + /* We have - if (q) goto then_bb; else goto inner_cond_bb; + if (q) goto outer_then_bb; else goto inner_cond_bb; if (q) goto then_bb; else goto ...; + ... - */ - return ifcombine_iforif (inner_cond_bb, outer_cond_bb); + If the then_bb,is not equal to outer_then_bb, then the + then_bb needs to be empty (no PHIs, no statments) and + the PHI in outer_then_bb for then_bb has to be the same value + as PHI value for outer_then_bb. */ + if (ifcombine_iforif (inner_cond_bb, outer_cond_bb)) + return true; + + in_or_seq = true; + last_inner_cond_bb = outer_cond_bb; + continue; } } + while (0); return false; } @@ -627,6 +1187,7 @@ tree_ssa_ifcombine (void) bbs = blocks_in_phiopt_order (); calculate_dominance_info (CDI_DOMINATORS); + /* Try to optimize if.and/or.if conditions. */ for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; ++i) { basic_block bb = bbs[i]; @@ -634,7 +1195,27 @@ tree_ssa_ifcombine (void) if (stmt && gimple_code (stmt) == GIMPLE_COND) - cfg_changed |= tree_ssa_ifcombine_bb (bb); + { + if (tree_ssa_ifcombine_bb (bb)) + { + cfg_changed = true; + --i; + } + } + } + + /* Try to merge if.and/or.if chains. */ + for (i = n_basic_blocks - NUM_FIXED_BLOCKS; i > 0; --i) + { + basic_block bb = bbs[i-1]; + gimple stmt = last_stmt (bb); + + if (stmt + && gimple_code (stmt) == GIMPLE_COND) + { + if (tree_ssa_ifmerge_bb (bb)) + cfg_changed = true; + } } free (bbs);