From patchwork Thu Oct 13 12:50:51 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kai Tietz X-Patchwork-Id: 119496 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 DC97DB6F80 for ; Fri, 14 Oct 2011 00:17:57 +1100 (EST) Received: (qmail 17527 invoked by alias); 13 Oct 2011 12:51:14 -0000 Received: (qmail 17508 invoked by uid 22791); 13 Oct 2011 12:51:11 -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-vx0-f175.google.com (HELO mail-vx0-f175.google.com) (209.85.220.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 13 Oct 2011 12:50:52 +0000 Received: by vcbf1 with SMTP id f1so1723983vcb.20 for ; Thu, 13 Oct 2011 05:50:51 -0700 (PDT) MIME-Version: 1.0 Received: by 10.220.74.20 with SMTP id s20mr274464vcj.13.1318510251047; Thu, 13 Oct 2011 05:50:51 -0700 (PDT) Received: by 10.220.180.5 with HTTP; Thu, 13 Oct 2011 05:50:51 -0700 (PDT) Date: Thu, 13 Oct 2011 14:50:51 +0200 Message-ID: Subject: [patch optimization]: Improve tree-ssa-ifcombine pass From: Kai Tietz To: GCC Patches 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 adds further optimization to gimple's ifcombine pass for single-bit andif operations. New patterns recognized are: * if ((a & 4) == 0) if ((a & 8) == 0) -> if ((a & 12) == 0) * if ((a & 4) != 0) if ((a & 8) == 0) -> if ((a & 12) == 4) * if ((a & 4) == 0) if ((a & 8) != 0) -> if ((a & 12) == 8) To support that, patch adds required additional patterns for if.and.if, and if.or.if detection to tree_ssa_ifcombine_bb. ChangeLog 2011-10-13 Kai Tietz * tree-ssa-ifcombine.c (same_phi_args_p_2): New helper for new andif pattern edge PHI comparison. (recognize_single_bit_test): Add new argument and allow EQ_EXPR. (ifcombine_ifandif): Handle == 0 cases. (tree_ssa_ifcombine_bb): Add new ifandif pattern. 2011-10-13 Kai Tietz * gcc.dg/tree-ssa/ssa-ifcombine-8.c: New test. * gcc.dg/tree-ssa/ssa-ifcombine-9.c: New test. * gcc.dg/tree-ssa/ssa-ifcombine-10.c: New test. * gcc.dg/tree-ssa/ssa-ifcombine-11.c: New test. * gcc.dg/tree-ssa/ssa-ifcombine-12.c: New test. Bootstrapped and regression tested for all languages plus Ada and Obj-C++ on x86_64-unknown-linux-gnu. Ok for apply? Regards, Kai Index: gcc/gcc/tree-ssa-ifcombine.c =================================================================== --- gcc.orig/gcc/tree-ssa-ifcombine.c +++ gcc/gcc/tree-ssa-ifcombine.c @@ -138,6 +138,54 @@ 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 be a PHI node + in DEST1 and DEST2 has not to have statements or its own PHI node. */ + +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)) + return (dest1 == dest2); + + /* 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 +213,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 +233,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,6 +360,7 @@ 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 @@ -321,25 +376,40 @@ ifcombine_ifandif (basic_block inner_con 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 = fold_build2 (EQ_EXPR, boolean_type_node, t2, t1); t = canonicalize_cond_expr_cond (t); if (!t) return false; @@ -354,11 +424,24 @@ ifcombine_ifandif (basic_block inner_con { fprintf (dump_file, "optimizing double bit test to "); print_generic_expr (dump_file, name1, 0); - fprintf (dump_file, " & T == T\nwith temporary T = (1 << "); + 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; @@ -571,24 +654,38 @@ tree_ssa_ifcombine_bb (basic_block inner if (single_pred_p (inner_cond_bb)) { basic_block outer_cond_bb = single_pred (inner_cond_bb); + basic_block outer_else_bb = NULL; + basic_block outer_then_bb = NULL; + + if (!recognize_if_then_else (outer_cond_bb, &outer_then_bb, + &outer_else_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) - && bb_no_side_effects_p (inner_cond_bb)) + if (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)) { /* 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; ... + ... - */ + 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. */ return ifcombine_ifandif (inner_cond_bb, outer_cond_bb); } @@ -596,18 +693,26 @@ tree_ssa_ifcombine_bb (basic_block inner 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) + if (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)) { /* 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 ...; + ... - */ + 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. */ return ifcombine_iforif (inner_cond_bb, outer_cond_bb); } } Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c =================================================================== --- /dev/null +++ gcc/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/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c =================================================================== --- /dev/null +++ gcc/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/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-10.c =================================================================== --- /dev/null +++ gcc/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/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-11.c =================================================================== --- /dev/null +++ gcc/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/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-12.c =================================================================== --- /dev/null +++ gcc/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" } } */