From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 9075 invoked by alias); 21 May 2014 13:31:11 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 8998 invoked by uid 89); 21 May 2014 13:31:10 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.1 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.3.2 X-HELO: mx2.suse.de Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (CAMELLIA256-SHA encrypted) ESMTPS; Wed, 21 May 2014 13:30:35 +0000 Received: from relay1.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id B8619AC78 for ; Wed, 21 May 2014 13:30:32 +0000 (UTC) Resent-From: Martin Jambor Resent-Date: Wed, 21 May 2014 15:30:32 +0200 Resent-Message-ID: <20140521133032.GC15866@virgil.suse> Resent-To: GCC Patches Message-Id: <20140521131634.335594343@virgil.suse.cz> User-Agent: quilt/0.60-8.1.3 Date: Wed, 21 May 2014 13:31:00 -0000 From: Martin Jambor To: GCC Patches Cc: Jan Hubicka Subject: [PATCH 2/7] Analyze BBs in DOM order in ipa-prop.c References: <20140521131634.178838544@virgil.suse.cz> Content-Disposition: inline; filename=analyze_edges_in_dom_order.diff X-IsSubscribed: yes X-SW-Source: 2014-05/txt/msg01768.txt.bz2 Hi, this patch has already been reviewed and pre-approved by Honza, so I'm including this mainly for reference and I will commit it once the previous (documentation) patch is approved. The original submission can be found at http://gcc.gnu.org/ml/gcc-patches/2014-04/msg01681.html. This patch introduce a better structure for holding intermediate information about the current function during analysis called function_body_info and above all analyzes BBs in DOM order which alone improves results as seen in PR 53787. Bootstrapped and tested on x86_64-linux. I have also LTO-bootstrapped it and LTO built Firefox with it. Thanks, Martin 2014-05-15 Martin Jambor PR tree-optimization/53787 * params.def (PARAM_IPA_CP_LOOP_HINT_BONUS): New param. * ipa-prop.h (ipa_node_params): Rename uses_analysis_done to analysis_done, update all uses. * ipa-prop.c: Include domwalk.h (param_analysis_info): Removed. (param_aa_status): New type. (ipa_bb_info): Likewise. (func_body_info): Likewise. (ipa_get_bb_info): New function. (aa_overwalked): Likewise. (find_dominating_aa_status): Likewise. (parm_bb_aa_status_for_bb): Likewise. (parm_preserved_before_stmt_p): Changed to use new param AA info. (load_from_unmodified_param): Accept func_body_info as a parameter instead of parms_ainfo. (parm_ref_data_preserved_p): Changed to use new param AA info. (parm_ref_data_pass_through_p): Likewise. (ipa_load_from_parm_agg_1): Likewise. Update callers. (compute_complex_assign_jump_func): Changed to use new param AA info. (compute_complex_ancestor_jump_func): Likewise. (ipa_compute_jump_functions_for_edge): Likewise. (ipa_compute_jump_functions): Removed. (ipa_compute_jump_functions_for_bb): New function. (ipa_analyze_indirect_call_uses): Likewise, moved variable declarations down. (ipa_analyze_virtual_call_uses): Accept func_body_info instead of node and info, moved variable declarations down. (ipa_analyze_call_uses): Accept and pass on func_body_info instead of node and info. (ipa_analyze_stmt_uses): Likewise. (ipa_analyze_params_uses): Removed. (ipa_analyze_params_uses_in_bb): New function. (ipa_analyze_controlled_uses): Likewise. (free_ipa_bb_info): Likewise. (analysis_dom_walker): New class. (ipa_analyze_node): Handle node-specific forbidden analysis, initialize and free func_body_info, use dominator walker. (ipcp_modif_dom_walker): New class. (ipcp_transform_function): Create and free func_body_info, use ipcp_modif_dom_walker, moved a lot of functionality there. Index: src/gcc/ipa-prop.c =================================================================== --- src.orig/gcc/ipa-prop.c +++ src/gcc/ipa-prop.c @@ -59,14 +59,57 @@ along with GCC; see the file COPYING3. #include "ipa-utils.h" #include "stringpool.h" #include "tree-ssanames.h" +#include "domwalk.h" -/* Intermediate information about a parameter that is only useful during the - run of ipa_analyze_node and is not kept afterwards. */ +/* Intermediate information that we get from alias analysis about a particular + parameter in a particular basic_block. When a parameter or the memory it + references is marked modified, we use that information in all dominatd + blocks without cosulting alias analysis oracle. */ + +struct param_aa_status +{ + /* Set when this structure contains meaningful information. If not, the + structure describing a dominating BB should be used instead. */ + bool valid; + + /* Whether we have seen something which might have modified the data in + question. PARM is for the parameter itself, REF is for data it points to + but using the alias type of individual accesses and PT is the same thing + but for computing aggregate pass-through functions using a very inclusive + ao_ref. */ + bool parm_modified, ref_modified, pt_modified; +}; -struct param_analysis_info +/* Information related to a given BB that used only when looking at function + body. */ + +struct ipa_bb_info { - bool parm_modified, ref_modified, pt_modified; - bitmap parm_visited_statements, pt_visited_statements; + /* Call graph edges going out of this BB. */ + vec cg_edges; + /* Alias analysis statuses of each formal parameter at this bb. */ + vec param_aa_statuses; +}; + +/* Structure with global information that is only used when looking at function + body. */ + +struct func_body_info +{ + /* The node that is being analyzed. */ + cgraph_node *node; + + /* Its info. */ + struct ipa_node_params *info; + + /* Information about individual BBs. */ + vec bb_infos; + + /* Number of parameters. */ + int param_count; + + /* Number of statements already walked by when analyzing this function. */ + unsigned int aa_walked; }; /* Vector where the parameter infos are actually stored. */ @@ -510,6 +553,16 @@ ipa_binfo_from_known_type_jfunc (struct jfunc->value.known_type.component_type); } +/* Get IPA BB information about the given BB. FBI is the context of analyzis + of this function body. */ + +static struct ipa_bb_info * +ipa_get_bb_info (struct func_body_info *fbi, basic_block bb) +{ + gcc_checking_assert (fbi); + return &fbi->bb_infos[bb->index]; +} + /* Structure to be passed in between detect_type_change and check_stmt_for_type_change. */ @@ -769,34 +822,101 @@ mark_modified (ao_ref *ao ATTRIBUTE_UNUS return true; } +/* Return true if we have already walked so many statements in AA that we + should really just start giving up. */ + +static bool +aa_overwalked (struct func_body_info *fbi) +{ + gcc_checking_assert (fbi); + return fbi->aa_walked > (unsigned) PARAM_VALUE (PARAM_IPA_MAX_AA_STEPS); +} + +/* Find the nearest valid aa status for parameter specified by INDEX that + dominates BB. */ + +static struct param_aa_status * +find_dominating_aa_status (struct func_body_info *fbi, basic_block bb, + int index) +{ + while (true) + { + bb = get_immediate_dominator (CDI_DOMINATORS, bb); + if (!bb) + return NULL; + struct ipa_bb_info *bi = ipa_get_bb_info (fbi, bb); + if (!bi->param_aa_statuses.is_empty () + && bi->param_aa_statuses[index].valid) + return &bi->param_aa_statuses[index]; + } +} + +/* Get AA status structure for the given BB and parameter with INDEX. Allocate + structures and/or intialize the result with a dominating description as + necessary. */ + +static struct param_aa_status * +parm_bb_aa_status_for_bb (struct func_body_info *fbi, basic_block bb, + int index) +{ + gcc_checking_assert (fbi); + struct ipa_bb_info *bi = ipa_get_bb_info (fbi, bb); + if (bi->param_aa_statuses.is_empty ()) + bi->param_aa_statuses.safe_grow_cleared (fbi->param_count); + struct param_aa_status *paa = &bi->param_aa_statuses[index]; + if (!paa->valid) + { + gcc_checking_assert (!paa->parm_modified + && !paa->ref_modified + && !paa->pt_modified); + struct param_aa_status *dom_paa; + dom_paa = find_dominating_aa_status (fbi, bb, index); + if (dom_paa) + *paa = *dom_paa; + else + paa->valid = true; + } + + return paa; +} + /* Return true if a load from a formal parameter PARM_LOAD is known to retrieve a value known not to be modified in this function before reaching the - statement STMT. PARM_AINFO is a pointer to a structure containing temporary - information about the parameter. */ + statement STMT. FBI holds information about the function we have so far + gathered but do not survive the summary building stage. */ static bool -parm_preserved_before_stmt_p (struct param_analysis_info *parm_ainfo, - gimple stmt, tree parm_load) +parm_preserved_before_stmt_p (struct func_body_info *fbi, int index, + gimple stmt, tree parm_load) { + struct param_aa_status *paa; bool modified = false; - bitmap *visited_stmts; ao_ref refd; - if (parm_ainfo && parm_ainfo->parm_modified) - return false; + /* FIXME: FBI can be NULL if we are being called from outside + ipa_node_analysis or ipcp_transform_function, which currently happens + during inlining analysis. It would be great to extend fbi's lifetime and + always have it. Currently, we are just not afraid of too much walking in + that case. */ + if (fbi) + { + if (aa_overwalked (fbi)) + return false; + paa = parm_bb_aa_status_for_bb (fbi, gimple_bb (stmt), index); + if (paa->parm_modified) + return false; + } + else + paa = NULL; gcc_checking_assert (gimple_vuse (stmt) != NULL_TREE); ao_ref_init (&refd, parm_load); - /* We can cache visited statements only when parm_ainfo is available and when - we are looking at a naked load of the whole parameter. */ - if (!parm_ainfo || TREE_CODE (parm_load) != PARM_DECL) - visited_stmts = NULL; - else - visited_stmts = &parm_ainfo->parm_visited_statements; - walk_aliased_vdefs (&refd, gimple_vuse (stmt), mark_modified, &modified, - visited_stmts); - if (parm_ainfo && modified) - parm_ainfo->parm_modified = true; + int walked = walk_aliased_vdefs (&refd, gimple_vuse (stmt), mark_modified, + &modified, NULL); + if (fbi) + fbi->aa_walked += walked; + if (paa && modified) + paa->parm_modified = true; return !modified; } @@ -805,8 +925,8 @@ parm_preserved_before_stmt_p (struct par modified. Otherwise return -1. */ static int -load_from_unmodified_param (vec descriptors, - struct param_analysis_info *parms_ainfo, +load_from_unmodified_param (struct func_body_info *fbi, + vec descriptors, gimple stmt) { int index; @@ -821,45 +941,58 @@ load_from_unmodified_param (vecref_modified) - return false; + /* FIXME: FBI can be NULL if we are being called from outside + ipa_node_analysis or ipcp_transform_function, which currently happens + during inlining analysis. It would be great to extend fbi's lifetime and + always have it. Currently, we are just not afraid of too much walking in + that case. */ + if (fbi) + { + if (aa_overwalked (fbi)) + return false; + paa = parm_bb_aa_status_for_bb (fbi, gimple_bb (stmt), index); + if (paa->ref_modified) + return false; + } + else + paa = NULL; + gcc_checking_assert (gimple_vuse (stmt)); ao_ref_init (&refd, ref); - walk_aliased_vdefs (&refd, gimple_vuse (stmt), mark_modified, &modified, - NULL); - if (parm_ainfo && modified) - parm_ainfo->ref_modified = true; + int walked = walk_aliased_vdefs (&refd, gimple_vuse (stmt), mark_modified, + &modified, NULL); + if (fbi) + fbi->aa_walked += walked; + if (paa && modified) + paa->ref_modified = true; return !modified; } -/* Return true if the data pointed to by PARM is known to be unmodified in this - function before reaching call statement CALL into which it is passed. - PARM_AINFO is a pointer to a structure containing temporary information - about PARM. */ +/* Return true if the data pointed to by PARM (which is a parameter with INDEX) + is known to be unmodified in this function before reaching call statement + CALL into which it is passed. FBI describes the function body. */ static bool -parm_ref_data_pass_through_p (struct param_analysis_info *parm_ainfo, - gimple call, tree parm) +parm_ref_data_pass_through_p (struct func_body_info *fbi, int index, + gimple call, tree parm) { bool modified = false; ao_ref refd; @@ -868,17 +1001,21 @@ parm_ref_data_pass_through_p (struct par function because it is not goin to use it. But do not cache the result either. Also, no such calculations for non-pointers. */ if (!gimple_vuse (call) - || !POINTER_TYPE_P (TREE_TYPE (parm))) + || !POINTER_TYPE_P (TREE_TYPE (parm)) + || aa_overwalked (fbi)) return false; - if (parm_ainfo->pt_modified) + struct param_aa_status *paa = parm_bb_aa_status_for_bb (fbi, gimple_bb (call), + index); + if (paa->pt_modified) return false; ao_ref_init_from_ptr_and_size (&refd, parm, NULL_TREE); - walk_aliased_vdefs (&refd, gimple_vuse (call), mark_modified, &modified, - parm_ainfo ? &parm_ainfo->pt_visited_statements : NULL); + int walked = walk_aliased_vdefs (&refd, gimple_vuse (call), mark_modified, + &modified, NULL); + fbi->aa_walked += walked; if (modified) - parm_ainfo->pt_modified = true; + paa->pt_modified = true; return !modified; } @@ -893,10 +1030,11 @@ parm_ref_data_pass_through_p (struct par reference respectively. */ static bool -ipa_load_from_parm_agg_1 (vec descriptors, - struct param_analysis_info *parms_ainfo, gimple stmt, - tree op, int *index_p, HOST_WIDE_INT *offset_p, - HOST_WIDE_INT *size_p, bool *by_ref_p) +ipa_load_from_parm_agg_1 (struct func_body_info *fbi, + vec descriptors, + gimple stmt, tree op, int *index_p, + HOST_WIDE_INT *offset_p, HOST_WIDE_INT *size_p, + bool *by_ref_p) { int index; HOST_WIDE_INT size, max_size; @@ -909,8 +1047,7 @@ ipa_load_from_parm_agg_1 (vec= 0 - && parm_preserved_before_stmt_p (parms_ainfo ? &parms_ainfo[index] - : NULL, stmt, op)) + && parm_preserved_before_stmt_p (fbi, index, stmt, op)) { *index_p = index; *by_ref_p = false; @@ -949,12 +1086,11 @@ ipa_load_from_parm_agg_1 (vec= 0 - && parm_ref_data_preserved_p (parms_ainfo ? &parms_ainfo[index] : NULL, - stmt, op)) + && parm_ref_data_preserved_p (fbi, index, stmt, op)) { *index_p = index; *by_ref_p = true; @@ -973,7 +1109,7 @@ ipa_load_from_parm_agg (struct ipa_node_ tree op, int *index_p, HOST_WIDE_INT *offset_p, bool *by_ref_p) { - return ipa_load_from_parm_agg_1 (info->descriptors, NULL, stmt, op, index_p, + return ipa_load_from_parm_agg_1 (NULL, info->descriptors, stmt, op, index_p, offset_p, NULL, by_ref_p); } @@ -1031,8 +1167,8 @@ ipa_load_from_parm_agg (struct ipa_node_ only needed for intraprocedural analysis. */ static void -compute_complex_assign_jump_func (struct ipa_node_params *info, - struct param_analysis_info *parms_ainfo, +compute_complex_assign_jump_func (struct func_body_info *fbi, + struct ipa_node_params *info, struct ipa_jump_func *jfunc, gimple call, gimple stmt, tree name, tree param_type) @@ -1048,13 +1184,13 @@ compute_complex_assign_jump_func (struct if (SSA_NAME_IS_DEFAULT_DEF (op1)) index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op1)); else - index = load_from_unmodified_param (info->descriptors, parms_ainfo, + index = load_from_unmodified_param (fbi, info->descriptors, SSA_NAME_DEF_STMT (op1)); tc_ssa = op1; } else { - index = load_from_unmodified_param (info->descriptors, parms_ainfo, stmt); + index = load_from_unmodified_param (fbi, info->descriptors, stmt); tc_ssa = gimple_assign_lhs (stmt); } @@ -1075,8 +1211,7 @@ compute_complex_assign_jump_func (struct } else if (gimple_assign_single_p (stmt)) { - bool agg_p = parm_ref_data_pass_through_p (&parms_ainfo[index], - call, tc_ssa); + bool agg_p = parm_ref_data_pass_through_p (fbi, index, call, tc_ssa); bool type_p = false; if (param_type && POINTER_TYPE_P (param_type)) @@ -1115,7 +1250,7 @@ compute_complex_assign_jump_func (struct if (type_p || jfunc->type == IPA_JF_UNKNOWN) ipa_set_ancestor_jf (jfunc, offset, type_p ? TREE_TYPE (param_type) : NULL, index, - parm_ref_data_pass_through_p (&parms_ainfo[index], + parm_ref_data_pass_through_p (fbi, index, call, ssa), type_p); } } @@ -1187,8 +1322,8 @@ get_ancestor_addr_info (gimple assign, t return D.1879_6; */ static void -compute_complex_ancestor_jump_func (struct ipa_node_params *info, - struct param_analysis_info *parms_ainfo, +compute_complex_ancestor_jump_func (struct func_body_info *fbi, + struct ipa_node_params *info, struct ipa_jump_func *jfunc, gimple call, gimple phi, tree param_type) { @@ -1247,9 +1382,10 @@ compute_complex_ancestor_jump_func (stru type_p = !detect_type_change (obj, expr, TREE_TYPE (param_type), call, jfunc, offset); if (type_p || jfunc->type == IPA_JF_UNKNOWN) - ipa_set_ancestor_jf (jfunc, offset, type_p ? TREE_TYPE (param_type) : NULL, index, - parm_ref_data_pass_through_p (&parms_ainfo[index], - call, parm), type_p); + ipa_set_ancestor_jf (jfunc, offset, type_p ? TREE_TYPE (param_type) : NULL, + index, + parm_ref_data_pass_through_p (fbi, index, call, parm), + type_p); } /* Given OP which is passed as an actual argument to a called function, @@ -1594,7 +1730,7 @@ ipa_get_callee_param_type (struct cgraph to this callsite. */ static void -ipa_compute_jump_functions_for_edge (struct param_analysis_info *parms_ainfo, +ipa_compute_jump_functions_for_edge (struct func_body_info *fbi, struct cgraph_edge *cs) { struct ipa_node_params *info = IPA_NODE_REF (cs->caller); @@ -1628,7 +1764,7 @@ ipa_compute_jump_functions_for_edge (str /* Aggregate passed by value, check for pass-through, otherwise we will attempt to fill in aggregate contents later in this for cycle. */ - if (parm_preserved_before_stmt_p (&parms_ainfo[index], call, arg)) + if (parm_preserved_before_stmt_p (fbi, index, call, arg)) { ipa_set_jf_simple_pass_through (jfunc, index, false, false); continue; @@ -1642,8 +1778,7 @@ ipa_compute_jump_functions_for_edge (str if (index >= 0) { bool agg_p, type_p; - agg_p = parm_ref_data_pass_through_p (&parms_ainfo[index], - call, arg); + agg_p = parm_ref_data_pass_through_p (fbi, index, call, arg); if (param_type && POINTER_TYPE_P (param_type)) type_p = !detect_type_change_ssa (arg, TREE_TYPE (param_type), call, jfunc); @@ -1658,10 +1793,10 @@ ipa_compute_jump_functions_for_edge (str { gimple stmt = SSA_NAME_DEF_STMT (arg); if (is_gimple_assign (stmt)) - compute_complex_assign_jump_func (info, parms_ainfo, jfunc, + compute_complex_assign_jump_func (fbi, info, jfunc, call, stmt, arg, param_type); else if (gimple_code (stmt) == GIMPLE_PHI) - compute_complex_ancestor_jump_func (info, parms_ainfo, jfunc, + compute_complex_ancestor_jump_func (fbi, info, jfunc, call, stmt, param_type); } } @@ -1692,27 +1827,29 @@ ipa_compute_jump_functions_for_edge (str } /* Compute jump functions for all edges - both direct and indirect - outgoing - from NODE. Also count the actual arguments in the process. */ + from BB. */ static void -ipa_compute_jump_functions (struct cgraph_node *node, - struct param_analysis_info *parms_ainfo) +ipa_compute_jump_functions_for_bb (struct func_body_info *fbi, basic_block bb) { + struct ipa_bb_info *bi = ipa_get_bb_info (fbi, bb); + int i; struct cgraph_edge *cs; - for (cs = node->callees; cs; cs = cs->next_callee) + FOR_EACH_VEC_ELT_REVERSE (bi->cg_edges, i, cs) { - struct cgraph_node *callee = cgraph_function_or_thunk_node (cs->callee, - NULL); - /* We do not need to bother analyzing calls to unknown - functions unless they may become known during lto/whopr. */ - if (!callee->definition && !flag_lto) - continue; - ipa_compute_jump_functions_for_edge (parms_ainfo, cs); - } + struct cgraph_node *callee = cs->callee; - for (cs = node->indirect_calls; cs; cs = cs->next_callee) - ipa_compute_jump_functions_for_edge (parms_ainfo, cs); + if (callee) + { + cgraph_function_or_thunk_node (callee, NULL); + /* We do not need to bother analyzing calls to unknown functions + unless they may become known during lto/whopr. */ + if (!callee->definition && !flag_lto) + continue; + } + ipa_compute_jump_functions_for_edge (fbi, cs); + } } /* If STMT looks like a statement loading a value from a member pointer formal @@ -1855,37 +1992,30 @@ ipa_note_param_call (struct cgraph_node passed by value or reference. */ static void -ipa_analyze_indirect_call_uses (struct cgraph_node *node, - struct ipa_node_params *info, - struct param_analysis_info *parms_ainfo, - gimple call, tree target) -{ - gimple def; - tree n1, n2; - gimple d1, d2; - tree rec, rec2, cond; - gimple branch; - int index; - basic_block bb, virt_bb, join; +ipa_analyze_indirect_call_uses (struct func_body_info *fbi, gimple call, + tree target) +{ + struct ipa_node_params *info = fbi->info; HOST_WIDE_INT offset; bool by_ref; if (SSA_NAME_IS_DEFAULT_DEF (target)) { tree var = SSA_NAME_VAR (target); - index = ipa_get_param_decl_index (info, var); + int index = ipa_get_param_decl_index (info, var); if (index >= 0) - ipa_note_param_call (node, index, call); + ipa_note_param_call (fbi->node, index, call); return; } - def = SSA_NAME_DEF_STMT (target); + int index; + gimple def = SSA_NAME_DEF_STMT (target); if (gimple_assign_single_p (def) - && ipa_load_from_parm_agg_1 (info->descriptors, parms_ainfo, def, + && ipa_load_from_parm_agg_1 (fbi, info->descriptors, def, gimple_assign_rhs1 (def), &index, &offset, NULL, &by_ref)) { - struct cgraph_edge *cs = ipa_note_param_call (node, index, call); + struct cgraph_edge *cs = ipa_note_param_call (fbi->node, index, call); if (cs->indirect_info->offset != offset) cs->indirect_info->outer_type = NULL; cs->indirect_info->offset = offset; @@ -1904,14 +2034,16 @@ ipa_analyze_indirect_call_uses (struct c /* First, we need to check whether one of these is a load from a member pointer that is a parameter to this function. */ - n1 = PHI_ARG_DEF (def, 0); - n2 = PHI_ARG_DEF (def, 1); + tree n1 = PHI_ARG_DEF (def, 0); + tree n2 = PHI_ARG_DEF (def, 1); if (!ipa_is_ssa_with_stmt_def (n1) || !ipa_is_ssa_with_stmt_def (n2)) return; - d1 = SSA_NAME_DEF_STMT (n1); - d2 = SSA_NAME_DEF_STMT (n2); + gimple d1 = SSA_NAME_DEF_STMT (n1); + gimple d2 = SSA_NAME_DEF_STMT (n2); - join = gimple_bb (def); + tree rec; + basic_block bb, virt_bb; + basic_block join = gimple_bb (def); if ((rec = ipa_get_stmt_member_ptr_load_param (d1, false, &offset))) { if (ipa_get_stmt_member_ptr_load_param (d2, false, NULL)) @@ -1939,7 +2071,7 @@ ipa_analyze_indirect_call_uses (struct c /* Third, let's see that the branching is done depending on the least significant bit of the pfn. */ - branch = last_stmt (bb); + gimple branch = last_stmt (bb); if (!branch || gimple_code (branch) != GIMPLE_COND) return; @@ -1948,7 +2080,7 @@ ipa_analyze_indirect_call_uses (struct c || !integer_zerop (gimple_cond_rhs (branch))) return; - cond = gimple_cond_lhs (branch); + tree cond = gimple_cond_lhs (branch); if (!ipa_is_ssa_with_stmt_def (cond)) return; @@ -1973,6 +2105,7 @@ ipa_analyze_indirect_call_uses (struct c def = SSA_NAME_DEF_STMT (cond); } + tree rec2; rec2 = ipa_get_stmt_member_ptr_load_param (def, (TARGET_PTRMEMFUNC_VBIT_LOCATION == ptrmemfunc_vbit_in_delta), @@ -1982,9 +2115,9 @@ ipa_analyze_indirect_call_uses (struct c index = ipa_get_param_decl_index (info, rec); if (index >= 0 - && parm_preserved_before_stmt_p (&parms_ainfo[index], call, rec)) + && parm_preserved_before_stmt_p (fbi, index, call, rec)) { - struct cgraph_edge *cs = ipa_note_param_call (node, index, call); + struct cgraph_edge *cs = ipa_note_param_call (fbi->node, index, call); if (cs->indirect_info->offset != offset) cs->indirect_info->outer_type = NULL; cs->indirect_info->offset = offset; @@ -1997,16 +2130,13 @@ ipa_analyze_indirect_call_uses (struct c /* Analyze a CALL to an OBJ_TYPE_REF which is passed in TARGET and if the object referenced in the expression is a formal parameter of the caller - (described by INFO), create a call note for the statement. */ + FBI->node (described by FBI->info), create a call note for the + statement. */ static void -ipa_analyze_virtual_call_uses (struct cgraph_node *node, - struct ipa_node_params *info, gimple call, - tree target) +ipa_analyze_virtual_call_uses (struct func_body_info *fbi, + gimple call, tree target) { - struct cgraph_edge *cs; - struct cgraph_indirect_call_info *ii; - struct ipa_jump_func jfunc; tree obj = OBJ_TYPE_REF_OBJECT (target); int index; HOST_WIDE_INT anc_offset; @@ -2017,8 +2147,10 @@ ipa_analyze_virtual_call_uses (struct cg if (TREE_CODE (obj) != SSA_NAME) return; + struct ipa_node_params *info = fbi->info; if (SSA_NAME_IS_DEFAULT_DEF (obj)) { + struct ipa_jump_func jfunc; if (TREE_CODE (SSA_NAME_VAR (obj)) != PARM_DECL) return; @@ -2031,6 +2163,7 @@ ipa_analyze_virtual_call_uses (struct cg } else { + struct ipa_jump_func jfunc; gimple stmt = SSA_NAME_DEF_STMT (obj); tree expr; @@ -2045,8 +2178,8 @@ ipa_analyze_virtual_call_uses (struct cg return; } - cs = ipa_note_param_call (node, index, call); - ii = cs->indirect_info; + struct cgraph_edge *cs = ipa_note_param_call (fbi->node, index, call); + struct cgraph_indirect_call_info *ii = cs->indirect_info; ii->offset = anc_offset; ii->otr_token = tree_to_uhwi (OBJ_TYPE_REF_TOKEN (target)); ii->otr_type = obj_type_ref_class (target); @@ -2058,12 +2191,9 @@ ipa_analyze_virtual_call_uses (struct cg containing intermediate information about each formal parameter. */ static void -ipa_analyze_call_uses (struct cgraph_node *node, - struct ipa_node_params *info, - struct param_analysis_info *parms_ainfo, gimple call) +ipa_analyze_call_uses (struct func_body_info *fbi, gimple call) { tree target = gimple_call_fn (call); - struct cgraph_edge *cs; if (!target || (TREE_CODE (target) != SSA_NAME @@ -2072,27 +2202,25 @@ ipa_analyze_call_uses (struct cgraph_nod /* If we previously turned the call into a direct call, there is no need to analyze. */ - cs = cgraph_edge (node, call); + struct cgraph_edge *cs = cgraph_edge (fbi->node, call); if (cs && !cs->indirect_unknown_callee) return; if (TREE_CODE (target) == SSA_NAME) - ipa_analyze_indirect_call_uses (node, info, parms_ainfo, call, target); + ipa_analyze_indirect_call_uses (fbi, call, target); else if (virtual_method_call_p (target)) - ipa_analyze_virtual_call_uses (node, info, call, target); + ipa_analyze_virtual_call_uses (fbi, call, target); } /* Analyze the call statement STMT with respect to formal parameters (described - in INFO) of caller given by NODE. Currently it only checks whether formal - parameters are called. PARMS_AINFO is a pointer to a vector containing - intermediate information about each formal parameter. */ + in INFO) of caller given by FBI->NODE. Currently it only checks whether + formal parameters are called. */ static void -ipa_analyze_stmt_uses (struct cgraph_node *node, struct ipa_node_params *info, - struct param_analysis_info *parms_ainfo, gimple stmt) +ipa_analyze_stmt_uses (struct func_body_info *fbi, gimple stmt) { if (is_gimple_call (stmt)) - ipa_analyze_call_uses (node, info, parms_ainfo, stmt); + ipa_analyze_call_uses (fbi, stmt); } /* Callback of walk_stmt_load_store_addr_ops for the visit_load. @@ -2116,37 +2244,43 @@ visit_ref_for_mod_analysis (gimple, tree return false; } -/* Scan the function body of NODE and inspect the uses of formal parameters. - Store the findings in various structures of the associated ipa_node_params - structure, such as parameter flags, notes etc. PARMS_AINFO is a pointer to a - vector containing intermediate information about each formal parameter. */ +/* Scan the statements in BB and inspect the uses of formal parameters. Store + the findings in various structures of the associated ipa_node_params + structure, such as parameter flags, notes etc. FBI holds various data about + the function being analyzed. */ static void -ipa_analyze_params_uses (struct cgraph_node *node, - struct param_analysis_info *parms_ainfo) +ipa_analyze_params_uses_in_bb (struct func_body_info *fbi, basic_block bb) { - tree decl = node->decl; - basic_block bb; - struct function *func; gimple_stmt_iterator gsi; - struct ipa_node_params *info = IPA_NODE_REF (node); - int i; + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple stmt = gsi_stmt (gsi); - if (ipa_get_param_count (info) == 0 || info->uses_analysis_done) - return; + if (is_gimple_debug (stmt)) + continue; - info->uses_analysis_done = 1; - if (ipa_func_spec_opts_forbid_analysis_p (node)) - { - for (i = 0; i < ipa_get_param_count (info); i++) - { - ipa_set_param_used (info, i, true); - ipa_set_controlled_uses (info, i, IPA_UNDESCRIBED_USE); - } - return; - } + ipa_analyze_stmt_uses (fbi, stmt); + walk_stmt_load_store_addr_ops (stmt, fbi->info, + visit_ref_for_mod_analysis, + visit_ref_for_mod_analysis, + visit_ref_for_mod_analysis); + } + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + walk_stmt_load_store_addr_ops (gsi_stmt (gsi), fbi->info, + visit_ref_for_mod_analysis, + visit_ref_for_mod_analysis, + visit_ref_for_mod_analysis); +} + +/* Calculate controlled uses of parameters of NODE. */ + +static void +ipa_analyze_controlled_uses (struct cgraph_node *node) +{ + struct ipa_node_params *info = IPA_NODE_REF (node); - for (i = 0; i < ipa_get_param_count (info); i++) + for (int i = 0; i < ipa_get_param_count (info); i++) { tree parm = ipa_get_param (info, i); int controlled_uses = 0; @@ -2182,45 +2316,36 @@ ipa_analyze_params_uses (struct cgraph_n controlled_uses = IPA_UNDESCRIBED_USE; ipa_set_controlled_uses (info, i, controlled_uses); } +} - func = DECL_STRUCT_FUNCTION (decl); - FOR_EACH_BB_FN (bb, func) - { - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - { - gimple stmt = gsi_stmt (gsi); - - if (is_gimple_debug (stmt)) - continue; +/* Free stuff in BI. */ - ipa_analyze_stmt_uses (node, info, parms_ainfo, stmt); - walk_stmt_load_store_addr_ops (stmt, info, - visit_ref_for_mod_analysis, - visit_ref_for_mod_analysis, - visit_ref_for_mod_analysis); - } - for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - walk_stmt_load_store_addr_ops (gsi_stmt (gsi), info, - visit_ref_for_mod_analysis, - visit_ref_for_mod_analysis, - visit_ref_for_mod_analysis); - } +static void +free_ipa_bb_info (struct ipa_bb_info *bi) +{ + bi->cg_edges.release (); + bi->param_aa_statuses.release (); } -/* Free stuff in PARMS_AINFO, assume there are PARAM_COUNT parameters. */ +/* Dominator walker driving the analysis. */ -static void -free_parms_ainfo (struct param_analysis_info *parms_ainfo, int param_count) +class analysis_dom_walker : public dom_walker { - int i; +public: + analysis_dom_walker (struct func_body_info *fbi) + : dom_walker (CDI_DOMINATORS), m_fbi (fbi) {} - for (i = 0; i < param_count; i++) - { - if (parms_ainfo[i].parm_visited_statements) - BITMAP_FREE (parms_ainfo[i].parm_visited_statements); - if (parms_ainfo[i].pt_visited_statements) - BITMAP_FREE (parms_ainfo[i].pt_visited_statements); - } + virtual void before_dom_children (basic_block); + +private: + struct func_body_info *m_fbi; +}; + +void +analysis_dom_walker::before_dom_children (basic_block bb) +{ + ipa_analyze_params_uses_in_bb (m_fbi, bb); + ipa_compute_jump_functions_for_bb (m_fbi, bb); } /* Initialize the array describing properties of of formal parameters @@ -2230,24 +2355,60 @@ free_parms_ainfo (struct param_analysis_ void ipa_analyze_node (struct cgraph_node *node) { + struct func_body_info fbi; struct ipa_node_params *info; - struct param_analysis_info *parms_ainfo; - int param_count; ipa_check_create_node_params (); ipa_check_create_edge_args (); info = IPA_NODE_REF (node); - push_cfun (DECL_STRUCT_FUNCTION (node->decl)); + + if (info->analysis_done) + return; + info->analysis_done = 1; + + if (ipa_func_spec_opts_forbid_analysis_p (node)) + { + for (int i = 0; i < ipa_get_param_count (info); i++) + { + ipa_set_param_used (info, i, true); + ipa_set_controlled_uses (info, i, IPA_UNDESCRIBED_USE); + } + return; + } + + struct function *func = DECL_STRUCT_FUNCTION (node->decl); + push_cfun (func); + calculate_dominance_info (CDI_DOMINATORS); ipa_initialize_node_params (node); + ipa_analyze_controlled_uses (node); + + fbi.node = node; + fbi.info = IPA_NODE_REF (node); + fbi.bb_infos = vNULL; + fbi.bb_infos.safe_grow_cleared (last_basic_block_for_fn (cfun)); + fbi.param_count = ipa_get_param_count (info); + fbi.aa_walked = 0; + + for (struct cgraph_edge *cs = node->callees; cs; cs = cs->next_callee) + { + ipa_bb_info *bi = ipa_get_bb_info (&fbi, gimple_bb (cs->call_stmt)); + bi->cg_edges.safe_push (cs); + } - param_count = ipa_get_param_count (info); - parms_ainfo = XALLOCAVEC (struct param_analysis_info, param_count); - memset (parms_ainfo, 0, sizeof (struct param_analysis_info) * param_count); + for (struct cgraph_edge *cs = node->indirect_calls; cs; cs = cs->next_callee) + { + ipa_bb_info *bi = ipa_get_bb_info (&fbi, gimple_bb (cs->call_stmt)); + bi->cg_edges.safe_push (cs); + } - ipa_analyze_params_uses (node, parms_ainfo); - ipa_compute_jump_functions (node, parms_ainfo); + analysis_dom_walker (&fbi).walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); - free_parms_ainfo (parms_ainfo, param_count); + int i; + struct ipa_bb_info *bi; + FOR_EACH_VEC_ELT (fbi.bb_infos, i, bi) + free_ipa_bb_info (bi); + fbi.bb_infos.release (); + free_dominance_info (CDI_DOMINATORS); pop_cfun (); } @@ -3303,7 +3464,7 @@ ipa_node_duplication_hook (struct cgraph new_info->lattices = NULL; new_info->ipcp_orig_node = old_info->ipcp_orig_node; - new_info->uses_analysis_done = old_info->uses_analysis_done; + new_info->analysis_done = old_info->analysis_done; new_info->node_enqueued = old_info->node_enqueued; old_av = ipa_get_agg_replacements_for_node (src); @@ -4428,7 +4589,7 @@ ipa_write_node_info (struct output_block for (j = 0; j < ipa_get_param_count (info); j++) streamer_write_uhwi (ob, ipa_get_param_move_cost (info, j)); bp = bitpack_create (ob->main_stream); - gcc_assert (info->uses_analysis_done + gcc_assert (info->analysis_done || ipa_get_param_count (info) == 0); gcc_assert (!info->node_enqueued); gcc_assert (!info->ipcp_orig_node); @@ -4474,7 +4635,7 @@ ipa_read_node_info (struct lto_input_blo bp = streamer_read_bitpack (ib); if (ipa_get_param_count (info) != 0) - info->uses_analysis_done = true; + info->analysis_done = true; info->node_enqueued = false; for (k = 0; k < ipa_get_param_count (info); k++) ipa_set_param_used (info, k, bp_unpack_value (&bp, 1)); @@ -4824,17 +4985,129 @@ adjust_agg_replacement_values (struct cg v->index = adj[v->index]; } +/* Dominator walker driving the ipcp modification phase. */ + +class ipcp_modif_dom_walker : public dom_walker +{ +public: + ipcp_modif_dom_walker (struct func_body_info *fbi, + vec descs, + struct ipa_agg_replacement_value *av, + bool *sc, bool *cc) + : dom_walker (CDI_DOMINATORS), m_fbi (fbi), m_descriptors (descs), + m_aggval (av), m_something_changed (sc), m_cfg_changed (cc) {} + + virtual void before_dom_children (basic_block); + +private: + struct func_body_info *m_fbi; + vec m_descriptors; + struct ipa_agg_replacement_value *m_aggval; + bool *m_something_changed, *m_cfg_changed; +}; + +void +ipcp_modif_dom_walker::before_dom_children (basic_block bb) +{ + gimple_stmt_iterator gsi; + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + struct ipa_agg_replacement_value *v; + gimple stmt = gsi_stmt (gsi); + tree rhs, val, t; + HOST_WIDE_INT offset, size; + int index; + bool by_ref, vce; + + if (!gimple_assign_load_p (stmt)) + continue; + rhs = gimple_assign_rhs1 (stmt); + if (!is_gimple_reg_type (TREE_TYPE (rhs))) + continue; + + vce = false; + t = rhs; + while (handled_component_p (t)) + { + /* V_C_E can do things like convert an array of integers to one + bigger integer and similar things we do not handle below. */ + if (TREE_CODE (rhs) == VIEW_CONVERT_EXPR) + { + vce = true; + break; + } + t = TREE_OPERAND (t, 0); + } + if (vce) + continue; + + if (!ipa_load_from_parm_agg_1 (m_fbi, m_descriptors, stmt, rhs, &index, + &offset, &size, &by_ref)) + continue; + for (v = m_aggval; v; v = v->next) + if (v->index == index + && v->offset == offset) + break; + if (!v + || v->by_ref != by_ref + || tree_to_shwi (TYPE_SIZE (TREE_TYPE (v->value))) != size) + continue; + + gcc_checking_assert (is_gimple_ip_invariant (v->value)); + if (!useless_type_conversion_p (TREE_TYPE (rhs), TREE_TYPE (v->value))) + { + if (fold_convertible_p (TREE_TYPE (rhs), v->value)) + val = fold_build1 (NOP_EXPR, TREE_TYPE (rhs), v->value); + else if (TYPE_SIZE (TREE_TYPE (rhs)) + == TYPE_SIZE (TREE_TYPE (v->value))) + val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (rhs), v->value); + else + { + if (dump_file) + { + fprintf (dump_file, " const "); + print_generic_expr (dump_file, v->value, 0); + fprintf (dump_file, " can't be converted to type of "); + print_generic_expr (dump_file, rhs, 0); + fprintf (dump_file, "\n"); + } + continue; + } + } + else + val = v->value; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Modifying stmt:\n "); + print_gimple_stmt (dump_file, stmt, 0, 0); + } + gimple_assign_set_rhs_from_tree (&gsi, val); + update_stmt (stmt); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "into:\n "); + print_gimple_stmt (dump_file, stmt, 0, 0); + fprintf (dump_file, "\n"); + } + + *m_something_changed = true; + if (maybe_clean_eh_stmt (stmt) + && gimple_purge_dead_eh_edges (gimple_bb (stmt))) + *m_cfg_changed = true; + } -/* Function body transformation phase. */ +} + +/* IPCP transformation phase doing propagation of aggregate values. */ unsigned int ipcp_transform_function (struct cgraph_node *node) { vec descriptors = vNULL; - struct param_analysis_info *parms_ainfo; + struct func_body_info fbi; struct ipa_agg_replacement_value *aggval; - gimple_stmt_iterator gsi; - basic_block bb; int param_count; bool cfg_changed = false, something_changed = false; @@ -4854,102 +5127,27 @@ ipcp_transform_function (struct cgraph_n adjust_agg_replacement_values (node, aggval); if (dump_file) ipa_dump_agg_replacement_values (dump_file, aggval); - parms_ainfo = XALLOCAVEC (struct param_analysis_info, param_count); - memset (parms_ainfo, 0, sizeof (struct param_analysis_info) * param_count); - descriptors.safe_grow_cleared (param_count); - ipa_populate_param_decls (node, descriptors); - - FOR_EACH_BB_FN (bb, cfun) - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - { - struct ipa_agg_replacement_value *v; - gimple stmt = gsi_stmt (gsi); - tree rhs, val, t; - HOST_WIDE_INT offset, size; - int index; - bool by_ref, vce; - - if (!gimple_assign_load_p (stmt)) - continue; - rhs = gimple_assign_rhs1 (stmt); - if (!is_gimple_reg_type (TREE_TYPE (rhs))) - continue; - - vce = false; - t = rhs; - while (handled_component_p (t)) - { - /* V_C_E can do things like convert an array of integers to one - bigger integer and similar things we do not handle below. */ - if (TREE_CODE (rhs) == VIEW_CONVERT_EXPR) - { - vce = true; - break; - } - t = TREE_OPERAND (t, 0); - } - if (vce) - continue; - if (!ipa_load_from_parm_agg_1 (descriptors, parms_ainfo, stmt, - rhs, &index, &offset, &size, &by_ref)) - continue; - for (v = aggval; v; v = v->next) - if (v->index == index - && v->offset == offset) - break; - if (!v - || v->by_ref != by_ref - || tree_to_shwi (TYPE_SIZE (TREE_TYPE (v->value))) != size) - continue; + fbi.node = node; + fbi.info = NULL; + fbi.bb_infos = vNULL; + fbi.bb_infos.safe_grow_cleared (last_basic_block_for_fn (cfun)); + fbi.param_count = param_count; + fbi.aa_walked = 0; - gcc_checking_assert (is_gimple_ip_invariant (v->value)); - if (!useless_type_conversion_p (TREE_TYPE (rhs), TREE_TYPE (v->value))) - { - if (fold_convertible_p (TREE_TYPE (rhs), v->value)) - val = fold_build1 (NOP_EXPR, TREE_TYPE (rhs), v->value); - else if (TYPE_SIZE (TREE_TYPE (rhs)) - == TYPE_SIZE (TREE_TYPE (v->value))) - val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (rhs), v->value); - else - { - if (dump_file) - { - fprintf (dump_file, " const "); - print_generic_expr (dump_file, v->value, 0); - fprintf (dump_file, " can't be converted to type of "); - print_generic_expr (dump_file, rhs, 0); - fprintf (dump_file, "\n"); - } - continue; - } - } - else - val = v->value; - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Modifying stmt:\n "); - print_gimple_stmt (dump_file, stmt, 0, 0); - } - gimple_assign_set_rhs_from_tree (&gsi, val); - update_stmt (stmt); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "into:\n "); - print_gimple_stmt (dump_file, stmt, 0, 0); - fprintf (dump_file, "\n"); - } - - something_changed = true; - if (maybe_clean_eh_stmt (stmt) - && gimple_purge_dead_eh_edges (gimple_bb (stmt))) - cfg_changed = true; - } + descriptors.safe_grow_cleared (param_count); + ipa_populate_param_decls (node, descriptors); + calculate_dominance_info (CDI_DOMINATORS); + ipcp_modif_dom_walker (&fbi, descriptors, aggval, &something_changed, + &cfg_changed).walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); + int i; + struct ipa_bb_info *bi; + FOR_EACH_VEC_ELT (fbi.bb_infos, i, bi) + free_ipa_bb_info (bi); + fbi.bb_infos.release (); + free_dominance_info (CDI_DOMINATORS); (*ipa_node_agg_replacements)[node->uid] = NULL; - free_parms_ainfo (parms_ainfo, param_count); descriptors.release (); if (!something_changed) Index: src/gcc/ipa-prop.h =================================================================== --- src.orig/gcc/ipa-prop.h +++ src/gcc/ipa-prop.h @@ -371,8 +371,9 @@ struct ipa_node_params /* If this node is an ipa-cp clone, these are the known values that describe what it has been specialized for. */ vec known_vals; - /* Whether the param uses analysis has already been performed. */ - unsigned uses_analysis_done : 1; + /* Whether the param uses analysis and jump function computation has already + been performed. */ + unsigned analysis_done : 1; /* Whether the function is enqueued in ipa-cp propagation stack. */ unsigned node_enqueued : 1; /* Whether we should create a specialized version based on values that are Index: src/gcc/params.def =================================================================== --- src.orig/gcc/params.def +++ src/gcc/params.def @@ -959,6 +959,12 @@ DEFPARAM (PARAM_IPA_CP_ARRAY_INDEX_HINT_ "index known.", 48, 0, 0) +DEFPARAM (PARAM_IPA_MAX_AA_STEPS, + "ipa-max-aa-steps", + "Maximum number of statements that will be visited by IPA formal " + "parameter analysis based on alias analysis in any given function", + 25000, 0, 0) + /* WHOPR partitioning configuration. */ DEFPARAM (PARAM_LTO_PARTITIONS, Index: src/gcc/doc/invoke.texi =================================================================== --- src.orig/gcc/doc/invoke.texi +++ src/gcc/doc/invoke.texi @@ -10098,6 +10098,13 @@ an array access known, it adds a bonus o @option{ipa-cp-array-index-hint-bonus} bonus to the profitability score of the candidate. +@item ipa-max-aa-steps +During its analysis of function bodies, IPA-CP employs alias analysis +in order to track values pointed to by function parameters. In order +not spend too much time analyzing huge functions, it will give up and +consider all memory clobbered after examining +@option{ipa-max-aa-steps} statements modifying memory. + @item lto-partitions Specify desired number of partitions produced during WHOPR compilation. The number of partitions should exceed the number of CPUs used for compilation.