From patchwork Thu Dec 1 22:13:56 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bill Schmidt X-Patchwork-Id: 128772 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 77EDBB6F7B for ; Fri, 2 Dec 2011 09:14:30 +1100 (EST) Received: (qmail 16312 invoked by alias); 1 Dec 2011 22:14:26 -0000 Received: (qmail 16299 invoked by uid 22791); 1 Dec 2011 22:14:24 -0000 X-SWARE-Spam-Status: No, hits=-2.5 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD, TW_TM X-Spam-Check-By: sourceware.org Received: from e32.co.us.ibm.com (HELO e32.co.us.ibm.com) (32.97.110.150) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 01 Dec 2011 22:14:09 +0000 Received: from /spool/local by e32.co.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Thu, 1 Dec 2011 15:14:08 -0700 Received: from d03relay04.boulder.ibm.com (9.17.195.106) by e32.co.us.ibm.com (192.168.1.132) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; Thu, 1 Dec 2011 15:14:07 -0700 Received: from d03av03.boulder.ibm.com (d03av03.boulder.ibm.com [9.17.195.169]) by d03relay04.boulder.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id pB1MDwH2147098 for ; Thu, 1 Dec 2011 15:13:58 -0700 Received: from d03av03.boulder.ibm.com (loopback [127.0.0.1]) by d03av03.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVout) with ESMTP id pB1MDwkn027307 for ; Thu, 1 Dec 2011 15:13:58 -0700 Received: from [9.65.245.49] (sig-9-65-245-49.mts.ibm.com [9.65.245.49]) by d03av03.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVin) with ESMTP id pB1MDt9L027119; Thu, 1 Dec 2011 15:13:56 -0700 Message-ID: <1322777636.19158.1.camel@gnopaine> Subject: [PATCH] Fix PR middle-end/39976, 200.sixtrack degradation From: "William J. Schmidt" To: gcc-patches@gcc.gnu.org, bergner@vnet.ibm.com Date: Thu, 01 Dec 2011 16:13:56 -0600 Mime-Version: 1.0 x-cbid: 11120122-3270-0000-0000-000002492153 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 Greetings, Bug 39976 reported a degradation to 200.sixtrack wherein a hot single-block loop is broken into two blocks. Investigation showed the cause to be a redundant PHI statement in the block, which the tree-outof-ssa logic doesn't handle well. Currently we don't have code following the introduction of the redundant PHI that can clean it up. This patch modifies the dom pass to include redundant PHIs in the logic that removes redundant computations. With the patch applied, the extra block is no longer created and the 200.sixtrack degradation is removed. This improves its performance by 7.3% on PowerPC64 32-bit and by 5.0% on PowerPC64 64-bit. Bootstrapped and regtested on powerpc64-linux. OK for trunk? Thanks, Bill 2011-11-29 Bill Schmidt PR middle-end/39976 * tree-ssa-dom.c (enum expr_kind): Add EXPR_PHI. (struct hashable_expr): Add struct phi field. (initialize_hash_element): Handle phis. (hashable_expr_equal_p): Likewise. (iterative_hash_hashable_expr): Likewise. (print_expr_hash_elt): Likewise. (dom_opt_enter_block): Create equivalences from redundant phis. (eliminate_redundant_computations): Handle redundant phis. Index: gcc/tree-ssa-dom.c =================================================================== --- gcc/tree-ssa-dom.c (revision 181501) +++ gcc/tree-ssa-dom.c (working copy) @@ -52,7 +52,8 @@ enum expr_kind EXPR_UNARY, EXPR_BINARY, EXPR_TERNARY, - EXPR_CALL + EXPR_CALL, + EXPR_PHI }; struct hashable_expr @@ -65,6 +66,7 @@ struct hashable_expr struct { enum tree_code op; tree opnd0, opnd1; } binary; struct { enum tree_code op; tree opnd0, opnd1, opnd2; } ternary; struct { gimple fn_from; bool pure; size_t nargs; tree *args; } call; + struct { size_t nargs; tree *args; } phi; } ops; }; @@ -281,6 +283,19 @@ initialize_hash_element (gimple stmt, tree lhs, expr->kind = EXPR_SINGLE; expr->ops.single.rhs = gimple_goto_dest (stmt); } + else if (code == GIMPLE_PHI) + { + size_t nargs = gimple_phi_num_args (stmt); + size_t i; + + expr->type = TREE_TYPE (gimple_phi_result (stmt)); + expr->kind = EXPR_PHI; + expr->ops.phi.nargs = nargs; + expr->ops.phi.args = (tree *) xcalloc (nargs, sizeof (tree)); + + for (i = 0; i < nargs; i++) + expr->ops.phi.args[i] = gimple_phi_arg_def (stmt, i); + } else gcc_unreachable (); @@ -439,6 +454,21 @@ hashable_expr_equal_p (const struct hashable_expr return true; } + case EXPR_PHI: + { + size_t i; + + if (expr0->ops.phi.nargs != expr1->ops.phi.nargs) + return false; + + for (i = 0; i < expr0->ops.phi.nargs; i++) + if (! operand_equal_p (expr0->ops.phi.args[i], + expr1->ops.phi.args[i], 0)) + return false; + + return true; + } + default: gcc_unreachable (); } @@ -516,6 +546,15 @@ iterative_hash_hashable_expr (const struct hashabl } break; + case EXPR_PHI: + { + size_t i; + + for (i = 0; i < expr->ops.phi.nargs; i++) + val = iterative_hash_expr (expr->ops.phi.args[i], val); + } + break; + default: gcc_unreachable (); } @@ -588,6 +627,22 @@ print_expr_hash_elt (FILE * stream, const struct e fprintf (stream, ")"); } break; + + case EXPR_PHI: + { + size_t i; + size_t nargs = element->expr.ops.phi.nargs; + + fprintf (stream, "PHI <"); + for (i = 0; i < nargs; i++) + { + print_generic_expr (stream, element->expr.ops.phi.args[i], 0); + if (i + 1 < nargs) + fprintf (stream, ", "); + } + fprintf (stream, ">"); + } + break; } fprintf (stream, "\n"); @@ -1688,6 +1743,10 @@ dom_opt_enter_block (struct dom_walk_data *walk_da /* PHI nodes can create equivalences too. */ record_equivalences_from_phis (bb); + /* Create equivalences from redundant PHIs. */ + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + eliminate_redundant_computations (&gsi); + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) optimize_stmt (bb, gsi); @@ -1818,13 +1877,27 @@ eliminate_redundant_computations (gimple_stmt_iter { tree expr_type; tree cached_lhs; + tree def; bool insert = true; bool assigns_var_p = false; + size_t i; gimple stmt = gsi_stmt (*gsi); - tree def = gimple_get_lhs (stmt); + /* If this is a PHI, we only want to consider it if all of its + arguments are SSA names (which are known to be defined in a + single place). This avoids errors when dealing with if-temps, + for example. */ + if (gimple_code (stmt) == GIMPLE_PHI) + for (i = 0; i < gimple_phi_num_args (stmt); i++) + if (TREE_CODE (gimple_phi_arg_def (stmt, i)) != SSA_NAME) + return; + if (gimple_code (stmt) == GIMPLE_PHI) + def = gimple_phi_result (stmt); + else + def = gimple_get_lhs (stmt); + /* Certain expressions on the RHS can be optimized away, but can not themselves be entered into the hash tables. */ if (! def @@ -1857,6 +1930,16 @@ eliminate_redundant_computations (gimple_stmt_iter } else if (gimple_code (stmt) == GIMPLE_SWITCH) expr_type = TREE_TYPE (gimple_switch_index (stmt)); + else if (gimple_code (stmt) == GIMPLE_PHI) + /* We can't propagate into a phi, so the logic below doesn't apply. + Instead record an equivalence between the cached LHS and the + PHI result of this statement. This should be sufficient to + kill the redundant phi. */ + { + if (def && cached_lhs) + record_const_or_copy (def, cached_lhs); + return; + } else gcc_unreachable (); @@ -2299,8 +2382,11 @@ lookup_avail_expr (gimple stmt, bool insert) tree temp; struct expr_hash_elt element; - /* Get LHS of assignment or call, else NULL_TREE. */ - lhs = gimple_get_lhs (stmt); + /* Get LHS of phi, assignment, or call; else NULL_TREE. */ + if (gimple_code (stmt) == GIMPLE_PHI) + lhs = gimple_phi_result (stmt); + else + lhs = gimple_get_lhs (stmt); initialize_hash_element (stmt, lhs, &element);