From patchwork Mon Jul 2 21:17:37 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Martin Jambor X-Patchwork-Id: 168642 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 7C70A2C009F for ; Tue, 3 Jul 2012 07:18:02 +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=1341868683; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Date: From:To:Cc:Subject:Message-ID:Mail-Followup-To:MIME-Version: Content-Type:Content-Disposition:User-Agent:Mailing-List: Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:Sender:Delivered-To; bh=Thd1RapDgCt6QN5Ku5VNhAJlcfs=; b=WqVJQITSz+avZQpp78oYIS1prPtxthubvaU1A8wImHGd2XHe6ZvEF58Dfc1dYp aR3yyLzUVxf7SGw5eh038HPmm2LbZ1DrtK0xPxdrjCzXwweCMFtEUcjKFTGiB1Zl RLEuYAhMAejWbEdxZpoEaAYUkkjhoWQNEr3YCMp8SPo8w= 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:Date:From:To:Cc:Subject:Message-ID:Mail-Followup-To:MIME-Version:Content-Type:Content-Disposition:User-Agent:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=UsWkoE61vAXW92kfp2FJrHaeVpMwa6XPPRblAmsQCuAxTEzJtDJ+MCj/8SWi1w dT7nCdO4UlElUxIAKb5UjuU8XXbQDNpC9uB8POXhfEoWPupxI4JavO//PxWPIBnG fULrbXE64cLcmxqBh+uk6xoB6MfE8eK9TT+Ym4RuaD2eM=; Received: (qmail 20136 invoked by alias); 2 Jul 2012 21:17:58 -0000 Received: (qmail 20126 invoked by uid 22791); 2 Jul 2012 21:17:56 -0000 X-SWARE-Spam-Status: No, hits=-5.3 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, RCVD_IN_DNSWL_HI, TW_TM X-Spam-Check-By: sourceware.org Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 02 Jul 2012 21:17:39 +0000 Received: from relay1.suse.de (unknown [195.135.220.254]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mx2.suse.de (Postfix) with ESMTP id 37B40A30EC; Mon, 2 Jul 2012 23:17:38 +0200 (CEST) Date: Mon, 2 Jul 2012 23:17:37 +0200 From: Martin Jambor To: GCC Patches Cc: Jan Hubicka Subject: [PATCH 3/3] Compute predicates for phi node results in ipa-inline-analysis.c Message-ID: <20120702211737.GA7599@virgil.arch.suse.de> Mail-Followup-To: GCC Patches , Jan Hubicka MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) 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 Hi, this third patch is basically a proof-of-concept aiming at alleviating the following code found in Fortran functions when they look at the contents of array descriptors: : stride.156_7 = strain_tensor_6(D)->dim[0].stride; if (stride.156_7 != 0) goto ; else goto ; : : # stride.156_4 = PHI and stride.156_4 is then used for other computations. Currently we compute a predicate for SSA name stride.156_7 but the PHI node stops us from having one for stride.156_4 and those computed from it. This patch looks at phi nodes, and if its pairs of predecessors have the same nearest common dominator, and the condition there is known to be described by a predicate (computed either by set_cond_stmt_execution_predicate or, set_switch_stmt_execution_predicate, we depend on knowing how exactly they behave), we use the parameter and offset from the predicate condition and create one for the PHI node result, provided the arguments of a phi node allow that, of course. I hacked this together one evening a some timw ago and I expect to talk with Honza about how we can perhaps access information abut edges properly, nevertheless the patch passes bootstrap and testing on x86_64. On current trunk, I need to pass -finline-limit=204 to cut down execution time of fatigue2 polyhedron benchmark from 155 seconds to 91 seconds. With the patch, I only need -finline-limit=166. So there's still quite some way to go but something along these lines can be part of it. Thanks for all comments and suggestions, Martin 2012-05-30 Martin Jambor * ipa-inline-analysis.c (known_phi_condition_for_bb): New function. (predicate_for_phi_result): Likewise. (estimate_function_body_sizes): Use the above two functions. (inline_analyze_function): Calculate and free dominance info. Index: src/gcc/ipa-inline-analysis.c =================================================================== --- src.orig/gcc/ipa-inline-analysis.c +++ src/gcc/ipa-inline-analysis.c @@ -1954,6 +1954,96 @@ param_change_prob (gimple stmt, int i) return REG_BR_PROB_BASE; } +/* For basic block BB, find if all pairs of its predecesors have a common + dominator and if that dominator ends with a simple condition. If so, return + TRUE and stor pointer to *C. */ + +static bool +known_phi_condition_for_bb (struct inline_summary *info, basic_block bb, + struct condition **c) +{ + edge_iterator ei; + edge e; + basic_block computed_dom = NULL; + basic_block prev = NULL; + + FOR_EACH_EDGE (e, ei, bb->preds) + { + if (prev) + { + basic_block dom = nearest_common_dominator (CDI_DOMINATORS, prev, + e->src); + if (!computed_dom) + computed_dom = dom; + else if (dom != computed_dom) + return false; + + } + prev = e->src; + } + + if (!computed_dom) + return false; + + FOR_EACH_EDGE (e, ei, computed_dom->succs) + if (e->aux) + { + struct predicate *p; + int i; + p = (struct predicate *) e->aux; + + if (p->clause[0] == 0 || p->clause[1] != 0) + return false; + for (i = 0 ; i < NUM_CONDITIONS; i++) + if (((1 << i) & p->clause[0]) == p->clause[0]) + break; + if (i == NUM_CONDITIONS || i < predicate_first_dynamic_condition) + return false; + + *c = VEC_index (condition, info->conds, + i - predicate_first_dynamic_condition); + return true; + } + return false; +} + +/* Given a PHI statement STMT in a function described by inline properties INFO + and in a basic lock whose predecesors in CFG is selected according to a + parameter (and potentially offset) stored in condition *C, store a predicate + for the result of the PHI statement into NONCONSTANT_NAMES, if possible. */ + +static void +predicate_for_phi_result (struct inline_summary *info, gimple stmt, + struct condition *c, + VEC (predicate_t, heap) *nonconstant_names) +{ + struct predicate p; + unsigned i; + + for (i = 0; i < gimple_phi_num_args (stmt); i++) + { + tree arg = gimple_phi_arg (stmt, i)->def; + if (!is_gimple_min_invariant (arg)) + { + gcc_assert (TREE_CODE (arg) == SSA_NAME); + if (true_predicate_p (VEC_index (predicate_t, nonconstant_names, + SSA_NAME_VERSION (arg)))) + return; + } + } + + p = add_condition (info, c->operand_num, c->agg_contents, c->offset, + CHANGED, NULL); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " "); + print_gimple_stmt (dump_file, stmt, 0, 0); + fprintf (dump_file, "\t\tphi predicate: "); + dump_predicate (dump_file, info->conds, &p); + } + VEC_replace (predicate_t, nonconstant_names, + SSA_NAME_VERSION (gimple_phi_result (stmt)), &p); +} /* Compute function body size parameters for NODE. When EARLY is true, we compute only simple summaries without @@ -2022,7 +2112,17 @@ estimate_function_body_sizes (struct cgr fprintf (dump_file, "\n BB %i predicate:", bb->index); dump_predicate (dump_file, info->conds, &bb_predicate); } - + + if (parms_info && nonconstant_names) + for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi)) + { + struct condition *phi_condition; + if (!known_phi_condition_for_bb (info, bb, &phi_condition)) + break; + predicate_for_phi_result (info, gsi_stmt (bsi), phi_condition, + nonconstant_names); + } + for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) { gimple stmt = gsi_stmt (bsi); @@ -3070,12 +3170,16 @@ inline_analyze_function (struct cgraph_n push_cfun (DECL_STRUCT_FUNCTION (node->symbol.decl)); current_function_decl = node->symbol.decl; + if (cfun) + calculate_dominance_info (CDI_DOMINATORS); if (dump_file) fprintf (dump_file, "\nAnalyzing function: %s/%u\n", cgraph_node_name (node), node->uid); if (optimize && !node->thunk.thunk_p) inline_indirect_intraprocedural_analysis (node); compute_inline_parameters (node, false); + if (cfun) + free_dominance_info (CDI_DOMINATORS); current_function_decl = NULL; pop_cfun ();