diff options
| -rw-r--r-- | gcc/ChangeLog | 62 | ||||
| -rw-r--r-- | gcc/Makefile.in | 2 | ||||
| -rw-r--r-- | gcc/doc/invoke.texi | 10 | ||||
| -rw-r--r-- | gcc/ipa-cp.c | 3048 | ||||
| -rw-r--r-- | gcc/ipa-prop.c | 225 | ||||
| -rw-r--r-- | gcc/ipa-prop.h | 178 | ||||
| -rw-r--r-- | gcc/params.def | 14 | ||||
| -rw-r--r-- | gcc/testsuite/ChangeLog | 16 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/ipa/ipa-1.c | 3 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/ipa/ipa-2.c | 3 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/ipa/ipa-3.c | 7 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/ipa/ipa-4.c | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/ipa/ipa-5.c | 3 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/ipa/ipa-7.c | 4 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/ipa/ipa-8.c | 3 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/ipa/ipacost-1.c | 8 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/ipa/ipacost-2.c | 25 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/ipa/ipcp-1.c | 52 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/ipa/ipcp-2.c | 99 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ipa-cp-1.c | 8 |
20 files changed, 2364 insertions, 1408 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index eade32cfc71..f114c254423 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,65 @@ +2011-07-18 Martin Jambor <mjambor@suse.cz> + + * ipa-prop.h: Include alloc-pool.h, all sorts of updates to general + comments. + (ipcp_values_pool): Declare. + (ipcp_sources_pool): Likewise. + (ipcp_lattice): Changed to forward declaration. + (ipa_param_descriptor): Removed fields ipcp_lattice, types and + cannot_devirtualize. + (ipa_node_params): New fields descriptors, lattices, known_vals, + clone_for_all_contexts and node dead, removed fields params and + count_scale. + (ipa_set_param_count): Removed. + (ipa_get_param_count): Made to work with descriptors vector. + (ipa_get_param): Updated. + (ipa_param_cannot_devirtualize_p): Removed. + (ipa_param_types_vec_empty): Likewise. + (ipa_set_param_used): New function. + (ipa_get_param_used): Updated to use descriptors vector. + (ipa_func_list): Removed. + (ipa_init_func_list): Removed declaration. + (ipa_push_func_to_list_1): Likewise. + (ipa_pop_func_from_list): Likewise. + (ipa_push_func_to_list): Removed. + (ipa_lattice_from_jfunc): Remove declaration. + (ipa_get_jf_pass_through_result): Declare. + (ipa_get_jf_ancestor_result): Likewise. + (ipa_value_from_jfunc): Likewise. + (ipa_get_lattice): Update. + (ipa_lat_is_single_const): New function. + * ipa-prop.c (ipa_push_func_to_list_1): Removed. + (ipa_init_func_list): Likewise. + (ipa_pop_func_from_list): Likewise. + (ipa_get_param_decl_index): Fix coding style. + (count_formal_params): Removed. + (count_formal_params_1): Renamed to count_formal_params. + (ipa_populate_param_decls): Update to use descriptors vector. + (ipa_initialize_node_params): Likewise. + (visit_ref_for_mod_analysis): Use ipa_set_param_used. + (ipa_analyze_params_uses): Likewise. + (ipa_free_node_params_substructures): Likewise and free also lattices + and known values. + (duplicate_array): Removed. + (ipa_edge_duplication_hook): Add the new edge to the list of edge + clones. + (ipa_node_duplication_hook): Update to use new lattices. + (ipa_free_all_structures_after_ipa_cp): Free alloc pools. + (ipa_free_all_structures_after_iinln): Likewise. + (ipa_write_node_info): Update to use new lattices. + (ipa_read_node_info): Likewise. + (ipa_get_jf_pass_through_result): New function. + (ipa_get_jf_ancestor_result): Likewise. + (ipa_value_from_jfunc): Likewise. + (ipa_cst_from_jfunc): Reimplemented using ipa_value_from_jfunc. + * ipa-cp.c: Reimplemented. + * params.def (PARAM_DEVIRT_TYPE_LIST_SIZE): Removed. + (PARAM_IPA_CP_VALUE_LIST_SIZE): New parameter. + (PARAM_IPA_CP_EVAL_THRESHOLD): Likewise. + * Makefile.in (IPA_PROP_H): Added alloc-pool.h to dependencies. + * doc/invoke.texi (devirt-type-list-size): Removed description. + (ipa-cp-value-list-size): Added description. + 2011-07-18 Richard Henderson <rth@redhat.com> * bb-reorder.c (fix_crossing_conditional_branches): Emit all insns diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 47e14fa9697..cbebc239114 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1006,7 +1006,7 @@ LTO_STREAMER_H = lto-streamer.h $(LINKER_PLUGIN_API_H) $(TARGET_H) \ $(CGRAPH_H) $(VEC_H) vecprim.h $(TREE_H) $(GIMPLE_H) \ $(GCOV_IO_H) TREE_VECTORIZER_H = tree-vectorizer.h $(TREE_DATA_REF_H) -IPA_PROP_H = ipa-prop.h $(TREE_H) $(VEC_H) $(CGRAPH_H) $(GIMPLE_H) +IPA_PROP_H = ipa-prop.h $(TREE_H) $(VEC_H) $(CGRAPH_H) $(GIMPLE_H) alloc-pool.h GSTAB_H = gstab.h stab.def BITMAP_H = bitmap.h $(HASHTAB_H) statistics.h GCC_PLUGIN_H = gcc-plugin.h highlev-plugin-common.h $(CONFIG_H) $(SYSTEM_H) \ diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 7541e3a92f3..ddad55b303f 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -9006,11 +9006,11 @@ loop in the loop nest by a given number of iterations. The strip length can be changed using the @option{loop-block-tile-size} parameter. The default value is 51 iterations. -@item devirt-type-list-size -IPA-CP attempts to track all possible types passed to a function's -parameter in order to perform devirtualization. -@option{devirt-type-list-size} is the maximum number of types it -stores per a single formal parameter of a function. +@item ipa-cp-value-list-size +IPA-CP attempts to track all possible values and types passed to a function's +parameter in order to propagate them and perform devirtualization. +@option{ipa-cp-value-list-size} is the maximum number of values and types it +stores per one formal parameter of a function. @item lto-partitions Specify desired number of partitions produced during WHOPR compilation. diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c index a7fecf26fbf..dc8cf095f6e 100644 --- a/gcc/ipa-cp.c +++ b/gcc/ipa-cp.c @@ -1,7 +1,9 @@ /* Interprocedural constant propagation Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc. - Contributed by Razya Ladelsky <RAZYA@il.ibm.com> + + Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor + <mjambor@suse.cz> This file is part of GCC. @@ -19,116 +21,85 @@ You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see <http://www.gnu.org/licenses/>. */ -/* Interprocedural constant propagation. The aim of interprocedural constant - propagation (IPCP) is to find which function's argument has the same - constant value in each invocation throughout the whole program. For example, - consider the following program: - - int g (int y) - { - printf ("value is %d",y); - } +/* Interprocedural constant propagation (IPA-CP). - int f (int x) - { - g (x); - } + The goal of this transformation is to - int h (int y) - { - g (y); - } + 1) discover functions which are always invoked with some arguments with the + same known constant values and modify the functions so that the + subsequent optimizations can take advantage of the knowledge, and - void main (void) - { - f (3); - h (3); - } + 2) partial specialization - create specialized versions of functions + transformed in this way if some parameters are known constants only in + certain contexts but the estimated tradeoff between speedup and cost size + is deemed good. + The algorithm also propagates types and attempts to perform type based + devirtualization. Types are propagated much like constants. - The IPCP algorithm will find that g's formal argument y is always called - with the value 3. + The algorithm basically consists of three stages. In the first, functions + are analyzed one at a time and jump functions are constructed for all known + call-sites. In the second phase, the pass propagates information from the + jump functions across the call to reveal what values are available at what + call sites, performs estimations of effects of known values on functions and + their callees, and finally decides what specialized extra versions should be + created. In the third, the special versions materialize and appropriate + calls are redirected. - The algorithm used is based on "Interprocedural Constant Propagation", by - David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon, Comp86, pg - 152-161 + The algorithm used is to a certain extent based on "Interprocedural Constant + Propagation", by David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon, + Comp86, pg 152-161 and "A Methodology for Procedure Cloning" by Keith D + Cooper, Mary W. Hall, and Ken Kennedy. - The optimization is divided into three stages: First stage - intraprocedural analysis ======================================= + This phase computes jump_function and modification flags. - A jump function for a callsite represents the values passed as an actual - arguments of a given callsite. There are three types of values: - Pass through - the caller's formal parameter is passed as an actual argument. + A jump function for a call-site represents the values passed as an actual + arguments of a given call-site. In principle, there are three types of + values: + + Pass through - the caller's formal parameter is passed as an actual + argument, plus an operation on it can be performed. Constant - a constant is passed as an actual argument. Unknown - neither of the above. - The jump function info, ipa_jump_func, is stored in ipa_edge_args - structure (defined in ipa_prop.h and pointed to by cgraph_node->aux) - modified_flags are defined in ipa_node_params structure - (defined in ipa_prop.h and pointed to by cgraph_edge->aux). + All jump function types are described in detail in ipa-prop.h, together with + the data structures that represent them and methods of accessing them. - -ipcp_generate_summary() is the first stage driver. + ipcp_generate_summary() is the main function of the first stage. Second stage - interprocedural analysis ======================================== - This phase does the interprocedural constant propagation. - It computes lattices for all formal parameters in the program - and their value that may be: - TOP - unknown. - BOTTOM - non constant. - CONSTANT - constant value. - Lattice describing a formal parameter p will have a constant value if all - callsites invoking this function have the same constant value passed to p. + This stage is itself divided into two phases. In the first, we propagate + known values over the call graph, in the second, we make cloning decisions. + It uses a different algorithm than the original Callahan's paper. - The lattices are stored in ipcp_lattice which is itself in ipa_node_params - structure (defined in ipa_prop.h and pointed to by cgraph_edge->aux). + First, we traverse the functions topologically from callers to callees and, + for each strongly connected component (SCC), we propagate constants + according to previously computed jump functions. We also record what known + values depend on other known values and estimate local effects. Finally, we + propagate cumulative information about these effects from dependant values + to those on which they depend. - -ipcp_iterate_stage() is the second stage driver. + Second, we again traverse the call graph in the same topological order and + make clones for functions which we know are called with the same values in + all contexts and decide about extra specialized clones of functions just for + some contexts - these decisions are based on both local estimates and + cumulative estimates propagated from callees. - Third phase - transformation of function code + ipcp_propagate_stage() and ipcp_decision_stage() together constitute the + third stage. + + Third phase - materialization of clones, call statement updates. ============================================ - Propagates the constant-valued formals into the function. - For each function whose parameters are constants, we create its clone. - - Then we process the clone in two ways: - 1. We insert an assignment statement 'parameter = const' at the beginning - of the cloned function. - 2. For read-only parameters that do not live in memory, we replace all their - uses with the constant. - - We also need to modify some callsites to call the cloned functions instead - of the original ones. For a callsite passing an argument found to be a - constant by IPCP, there are two different cases to handle: - 1. A constant is passed as an argument. In this case the callsite in the - should be redirected to call the cloned callee. - 2. A parameter (of the caller) passed as an argument (pass through - argument). In such cases both the caller and the callee have clones and - only the callsite in the cloned caller is redirected to call to the - cloned callee. - - This update is done in two steps: First all cloned functions are created - during a traversal of the call graph, during which all callsites are - redirected to call the cloned function. Then the callsites are traversed - and many calls redirected back to fit the description above. - - -ipcp_insert_stage() is the third phase driver. - - - This pass also performs devirtualization - turns virtual calls into direct - ones if it can prove that all invocations of the function call the same - callee. This is achieved by building a list of all base types (actually, - their BINFOs) that individual parameters can have in an iterative matter - just like propagating scalar constants and then examining whether virtual - calls which take a parameter as their object fold to the same target for all - these types. If we cannot enumerate all types or there is a type which does - not have any BINFO associated with it, cannot_devirtualize of the associated - parameter descriptor is set which is an equivalent of BOTTOM lattice value - in standard IPA constant propagation. -*/ + + This stage is currently performed by call graph code (mainly in cgraphunit.c + and tree-inline.c) according to instructions inserted to the call graph by + the second stage. */ #include "config.h" #include "system.h" @@ -149,317 +120,372 @@ along with GCC; see the file COPYING3. If not see #include "fibheap.h" #include "params.h" #include "ipa-inline.h" +#include "ipa-utils.h" -/* Number of functions identified as candidates for cloning. When not cloning - we can simplify iterate stage not forcing it to go through the decision - on what is profitable and what not. */ -static int n_cloning_candidates; +struct ipcp_value; -/* Maximal count found in program. */ -static gcov_type max_count; +/* Describes a particular source for an IPA-CP value. */ -/* Cgraph nodes that has been completely replaced by cloning during iterate - * stage and will be removed after ipcp is finished. */ -static bitmap dead_nodes; +struct ipcp_value_source +{ + /* The incoming edge that brought the value. */ + struct cgraph_edge *cs; + /* If the jump function that resulted into his value was a pass-through or an + ancestor, this is the ipcp_value of the caller from which the described + value has been derived. Otherwise it is NULL. */ + struct ipcp_value *val; + /* Next pointer in a linked list of sources of a value. */ + struct ipcp_value_source *next; + /* If the jump function that resulted into his value was a pass-through or an + ancestor, this is the index of the parameter of the caller the jump + function references. */ + int index; +}; -static void ipcp_print_profile_data (FILE *); -static void ipcp_function_scale_print (FILE *); +/* Describes one particular value stored in struct ipcp_lattice. */ -/* Get the original node field of ipa_node_params associated with node NODE. */ -static inline struct cgraph_node * -ipcp_get_orig_node (struct cgraph_node *node) +struct ipcp_value { - return IPA_NODE_REF (node)->ipcp_orig_node; -} + /* The actual value for the given parameter. This is either an IPA invariant + or a TREE_BINFO describing a type that can be used for + devirtualization. */ + tree value; + /* The list of sources from which this value originates. */ + struct ipcp_value_source *sources; + /* Next pointers in a linked list of all values in a lattice. */ + struct ipcp_value *next; + /* Next pointers in a linked list of values in a strongly connected component + of values. */ + struct ipcp_value *scc_next; + /* Next pointers in a linked list of SCCs of values sorted topologically + according their sources. */ + struct ipcp_value *topo_next; + /* A specialized node created for this value, NULL if none has been (so far) + created. */ + struct cgraph_node *spec_node; + /* Depth first search number and low link for topological sorting of + values. */ + int dfs, low_link; + /* Time benefit and size cost that specializing the function for this value + would bring about in this function alone. */ + int local_time_benefit, local_size_cost; + /* Time benefit and size cost that specializing the function for this value + can bring about in it's callees (transitively). */ + int prop_time_benefit, prop_size_cost; + /* True if this valye is currently on the topo-sort stack. */ + bool on_stack; +}; -/* Return true if NODE describes a cloned/versioned function. */ -static inline bool -ipcp_node_is_clone (struct cgraph_node *node) -{ - return (ipcp_get_orig_node (node) != NULL); -} +/* Allocation pools for values and their sources in ipa-cp. */ -/* Create ipa_node_params and its data structures for NEW_NODE. Set ORIG_NODE - as the ipcp_orig_node field in ipa_node_params. */ -static void -ipcp_init_cloned_node (struct cgraph_node *orig_node, - struct cgraph_node *new_node) -{ - gcc_checking_assert (ipa_node_params_vector - && (VEC_length (ipa_node_params_t, - ipa_node_params_vector) - > (unsigned) cgraph_max_uid)); - gcc_checking_assert (IPA_NODE_REF (new_node)->params); - IPA_NODE_REF (new_node)->ipcp_orig_node = orig_node; -} +alloc_pool ipcp_values_pool; +alloc_pool ipcp_sources_pool; -/* Return scale for NODE. */ -static inline gcov_type -ipcp_get_node_scale (struct cgraph_node *node) +/* Lattice describing potential values of a formal parameter of a function and + some of their other properties. TOP is represented by a lattice with zero + values and with contains_variable and bottom flags cleared. BOTTOM is + represented by a lattice with the bottom flag set. In that case, values and + contains_variable flag should be disregarded. */ + +struct ipcp_lattice { - return IPA_NODE_REF (node)->count_scale; -} + /* The list of known values and types in this lattice. Note that values are + not deallocated if a lattice is set to bottom because there may be value + sources referencing them. */ + struct ipcp_value *values; + /* Number of known values and types in this lattice. */ + int values_count; + /* The lattice contains a variable component (in addition to values). */ + bool contains_variable; + /* The value of the lattice is bottom (i.e. variable and unusable for any + propagation). */ + bool bottom; + /* There is a virtual call based on this parameter. */ + bool virt_call; +}; -/* Set COUNT as scale for NODE. */ -static inline void -ipcp_set_node_scale (struct cgraph_node *node, gcov_type count) +/* Maximal count found in program. */ + +static gcov_type max_count; + +/* Original overall size of the program. */ + +static long overall_size, max_new_size; + +/* Head of the linked list of topologically sorted values. */ + +static struct ipcp_value *values_topo; + +/* Return the lattice corresponding to the Ith formal parameter of the function + described by INFO. */ +static inline struct ipcp_lattice * +ipa_get_lattice (struct ipa_node_params *info, int i) { - IPA_NODE_REF (node)->count_scale = count; + gcc_assert (i >= 0 && i <= ipa_get_param_count (info)); + gcc_checking_assert (!info->ipcp_orig_node); + gcc_checking_assert (info->lattices); + return &(info->lattices[i]); } -/* Return whether LAT is a constant lattice. */ +/* Return whether LAT is a lattice with a single constant and without an + undefined value. */ + static inline bool -ipcp_lat_is_const (struct ipcp_lattice *lat) +ipa_lat_is_single_const (struct ipcp_lattice *lat) { - if (lat->type == IPA_CONST_VALUE) - return true; - else + if (lat->bottom + || lat->contains_variable + || lat->values_count != 1) return false; + else + return true; } -/* Return whether LAT is a constant lattice that ipa-cp can actually insert - into the code (i.e. constants excluding member pointers and pointers). */ -static inline bool -ipcp_lat_is_insertable (struct ipcp_lattice *lat) -{ - return lat->type == IPA_CONST_VALUE; -} +/* Return true iff the CS is an edge within a strongly connected component as + computed by ipa_reduced_postorder. */ -/* Return true if LAT1 and LAT2 are equal. */ static inline bool -ipcp_lats_are_equal (struct ipcp_lattice *lat1, struct ipcp_lattice *lat2) +edge_within_scc (struct cgraph_edge *cs) { - gcc_assert (ipcp_lat_is_const (lat1) && ipcp_lat_is_const (lat2)); - if (lat1->type != lat2->type) - return false; - - if (TREE_CODE (lat1->constant) == ADDR_EXPR - && TREE_CODE (lat2->constant) == ADDR_EXPR - && TREE_CODE (TREE_OPERAND (lat1->constant, 0)) == CONST_DECL - && TREE_CODE (TREE_OPERAND (lat2->constant, 0)) == CONST_DECL) - return operand_equal_p (DECL_INITIAL (TREE_OPERAND (lat1->constant, 0)), - DECL_INITIAL (TREE_OPERAND (lat2->constant, 0)), 0); - else - return operand_equal_p (lat1->constant, lat2->constant, 0); + struct ipa_dfs_info *caller_dfs = (struct ipa_dfs_info *) cs->caller->aux; + struct ipa_dfs_info *callee_dfs; + struct cgraph_node *callee = cgraph_function_node (cs->callee, NULL); + + callee_dfs = (struct ipa_dfs_info *) callee->aux; + return (caller_dfs + && callee_dfs + && caller_dfs->scc_no == callee_dfs->scc_no); } -/* Compute Meet arithmetics: - Meet (IPA_BOTTOM, x) = IPA_BOTTOM - Meet (IPA_TOP,x) = x - Meet (const_a,const_b) = IPA_BOTTOM, if const_a != const_b. - MEET (const_a,const_b) = const_a, if const_a == const_b.*/ +/* Print V which is extracted from a value in a lattice to F. */ + static void -ipa_lattice_meet (struct ipcp_lattice *res, struct ipcp_lattice *lat1, - struct ipcp_lattice *lat2) +print_ipcp_constant_value (FILE * f, tree v) { - if (lat1->type == IPA_BOTTOM || lat2->type == IPA_BOTTOM) - { - res->type = IPA_BOTTOM; - return; - } - if (lat1->type == IPA_TOP) - { - res->type = lat2->type; - res->constant = lat2->constant; - return; - } - if (lat2->type == IPA_TOP) - { - res->type = lat1->type; - res->constant = lat1->constant; - return; - } - if (!ipcp_lats_are_equal (lat1, lat2)) + if (TREE_CODE (v) == TREE_BINFO) { - res->type = IPA_BOTTOM; - return; + fprintf (f, "BINFO "); + print_generic_expr (f, BINFO_TYPE (v), 0); } - res->type = lat1->type; - res->constant = lat1->constant; -} - -/* True when OLD_LAT and NEW_LAT values are not the same. */ - -static bool -ipcp_lattice_changed (struct ipcp_lattice *old_lat, - struct ipcp_lattice *new_lat) -{ - if (old_lat->type == new_lat->type) + else if (TREE_CODE (v) == ADDR_EXPR + && TREE_CODE (TREE_OPERAND (v, 0)) == CONST_DECL) { - if (!ipcp_lat_is_const (old_lat)) - return false; - if (ipcp_lats_are_equal (old_lat, new_lat)) - return false; + fprintf (f, "& "); + print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (v, 0)), 0); } - return true; + else + print_generic_expr (f, v, 0); } /* Print all ipcp_lattices of all functions to F. */ + static void -ipcp_print_all_lattices (FILE * f) +print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits) { struct cgraph_node *node; int i, count; - fprintf (f, "\nLattice:\n"); - for (node = cgraph_nodes; node; node = node->next) + fprintf (f, "\nLattices:\n"); + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) { struct ipa_node_params *info; - if (!node->analyzed) - continue; info = IPA_NODE_REF (node); - fprintf (f, " Node: %s:\n", cgraph_node_name (node)); + fprintf (f, " Node: %s/%i:\n", cgraph_node_name (node), node->uid); count = ipa_get_param_count (info); for (i = 0; i < count; i++) { struct ipcp_lattice *lat = ipa_get_lattice (info, i); + struct ipcp_value *val; + bool prev = false; fprintf (f, " param [%d]: ", i); - if (lat->type == IPA_CONST_VALUE) + if (lat->bottom) { - tree cst = lat->constant; - fprintf (f, "type is CONST "); - print_generic_expr (f, cst, 0); - if (TREE_CODE (cst) == ADDR_EXPR - && TREE_CODE (TREE_OPERAND (cst, 0)) == CONST_DECL) + fprintf (f, "BOTTOM\n"); + continue; + } + + if (!lat->values_count && !lat->contains_variable) + { + fprintf (f, "TOP\n"); + continue; + } + + if (lat->contains_variable) + { + fprintf (f, "VARIABLE"); + prev = true; + if (dump_benefits) + fprintf (f, "\n"); + } + + for (val = lat->values; val; val = val->next) + { + if (dump_benefits && prev) + fprintf (f, " "); + else if (!dump_benefits && prev) + fprintf (f, ", "); + else + prev = true; + + print_ipcp_constant_value (f, val->value); + + if (dump_sources) { - fprintf (f, " -> "); - print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (cst, 0)), - 0); + struct ipcp_value_source *s; + + fprintf (f, " [from:"); + for (s = val->sources; s; s = s->next) + fprintf (f, " %i(%i)", s->cs->caller->uid,s->cs->frequency); + fprintf (f, "]"); } + + if (dump_benefits) + fprintf (f, " [loc_time: %i, loc_size: %i, " + "prop_time: %i, prop_size: %i]\n", + val->local_time_benefit, val->local_size_cost, + val->prop_time_benefit, val->prop_size_cost); } - else if (lat->type == IPA_TOP) - fprintf (f, "type is TOP"); - else - fprintf (f, "type is BOTTOM"); - if (ipa_param_cannot_devirtualize_p (info, i)) - fprintf (f, " - cannot_devirtualize set\n"); - else if (ipa_param_types_vec_empty (info, i)) - fprintf (f, " - type list empty\n"); - else + if (!dump_benefits) fprintf (f, "\n"); } } } -/* Return true if ipcp algorithms would allow cloning NODE. */ +/* Determine whether it is at all technically possible to create clones of NODE + and store this information in the ipa_node_params structure associated + with NODE. */ -static bool -ipcp_versionable_function_p (struct cgraph_node *node) +static void +determine_versionability (struct cgraph_node *node) { struct cgraph_edge *edge; - - /* We always version the actual function and redirect through the aliases. */ - if (node->alias) - return false; - - /* We don't know how to clone thunks. */ - if (node->thunk.thunk_p) - return false; + const char *reason = NULL; /* There are a number of generic reasons functions cannot be versioned. We also cannot remove parameters if there are type attributes such as fnspec present. */ - if (!inline_summary (node)->versionable - || TYPE_ATTRIBUTES (TREE_TYPE (node->decl))) - return false; + if (node->alias || node->thunk.thunk_p) + reason = "alias or thunk"; + else if (!inline_summary (node)->versionable) + reason = "inliner claims it is so"; + else if (TYPE_ATTRIBUTES (TREE_TYPE (node->decl))) + reason = "there are type attributes"; + else if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE) + reason = "insufficient body availability"; + else + /* Removing arguments doesn't work if the function takes varargs + or use __builtin_apply_args. + FIXME: handle this together with can_change_signature flag. */ + for (edge = node->callees; edge; edge = edge->next_callee) + { + tree t = edge->callee->decl; + if (DECL_BUILT_IN_CLASS (t) == BUILT_IN_NORMAL + && (DECL_FUNCTION_CODE (t) == BUILT_IN_APPLY_ARGS + || DECL_FUNCTION_CODE (t) == BUILT_IN_VA_START)) + { + reason = "prohibitive builtins called"; + break; + }; + } - /* Removing arguments doesn't work if the function takes varargs - or use __builtin_apply_args. - FIXME: handle this together with can_change_signature flag. */ - for (edge = node->callees; edge; edge = edge->next_callee) - { - tree t = edge->callee->decl; - if (DECL_BUILT_IN_CLASS (t) == BUILT_IN_NORMAL - && (DECL_FUNCTION_CODE (t) == BUILT_IN_APPLY_ARGS - || DECL_FUNCTION_CODE (t) == BUILT_IN_VA_START)) - return false; - } + if (reason && dump_file && !node->alias && !node->thunk.thunk_p) + fprintf (dump_file, "Function %s/%i is not versionable, reason: %s.\n", + cgraph_node_name (node), node->uid, reason); - return true; + IPA_NODE_REF (node)->node_versionable = (reason == NULL); } -/* Return true if this NODE is viable candidate for cloning. */ +/* Return true if it is at all technically possible to create clones of a + NODE. */ + static bool -ipcp_cloning_candidate_p (struct cgraph_node *node) +ipcp_versionable_function_p (struct cgraph_node *node) { - int n_calls = 0; - int n_hot_calls = 0; - gcov_type direct_call_sum = 0; - struct cgraph_edge *e; + return IPA_NODE_REF (node)->node_versionable; +} - /* We look through aliases, so we clone the aliased function instead. */ - if (node->alias) - return false; +/* Structure holding accumulated information about callers of a node. */ - /* We never clone functions that are not visible from outside. - FIXME: in future we should clone such functions when they are called with - different constants, but current ipcp implementation is not good on this. - */ - if (cgraph_only_called_directly_p (node) || !node->analyzed) - return false; +struct caller_statistics +{ + gcov_type count_sum; + int n_calls, n_hot_calls, freq_sum; +}; - /* When function address is taken, we are pretty sure it will be called in hidden way. */ - if (node->address_taken) - { - if (dump_file) - fprintf (dump_file, "Not considering %s for cloning; address is taken.\n", - cgraph_node_name (node)); - return false; - } +/* Initialize fields of STAT to zeroes. */ - if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE) - { - if (dump_file) - fprintf (dump_file, "Not considering %s for cloning; body is overwritable.\n", - cgraph_node_name (node)); - return false; - } - if (!ipcp_versionable_function_p (node)) - { - if (dump_file) - fprintf (dump_file, "Not considering %s for cloning; body is not versionable.\n", - cgraph_node_name (node)); - return false; - } - for (e = node->callers; e; e = e->next_caller) - { - direct_call_sum += e->count; - n_calls ++; - if (cgraph_maybe_hot_edge_p (e)) - n_hot_calls ++; - } +static inline void +init_caller_stats (struct caller_statistics *stats) +{ + stats->count_sum = 0; + stats->n_calls = 0; + stats->n_hot_calls = 0; + stats->freq_sum = 0; +} + +/* Worker callback of cgraph_for_node_and_aliases accumulating statistics of + non-thunk incoming edges to NODE. */ + +static bool +gather_caller_stats (struct cgraph_node *node, void *data) +{ + struct caller_statistics *stats = (struct caller_statistics *) data; + struct cgraph_edge *cs; + + for (cs = node->callers; cs; cs = cs->next_caller) + if (cs->caller->thunk.thunk_p) + cgraph_for_node_and_aliases (cs->caller, gather_caller_stats, + stats, false); + else + { + stats->count_sum += cs->count; + stats->freq_sum += cs->frequency; + stats->n_calls++; + if (cgraph_maybe_hot_edge_p (cs)) + stats->n_hot_calls ++; + } + return false; + +} + +/* Return true if this NODE is viable candidate for cloning. */ - if (!n_calls) +static bool +ipcp_cloning_candidate_p (struct cgraph_node *node) +{ + struct caller_statistics stats; + + gcc_checking_assert (cgraph_function_with_gimple_body_p (node)); + + if (!flag_ipa_cp_clone) { if (dump_file) - fprintf (dump_file, "Not considering %s for cloning; no direct calls.\n", + fprintf (dump_file, "Not considering %s for cloning; " + "-fipa-cp-clone disabled.\n", cgraph_node_name (node)); return false; } - if (inline_summary (node)->self_size < n_calls) - { - if (dump_file) - fprintf (dump_file, "Considering %s for cloning; code would shrink.\n", - cgraph_node_name (node)); - return true; - } - if (!flag_ipa_cp_clone) + if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl))) { if (dump_file) - fprintf (dump_file, "Not considering %s for cloning; -fipa-cp-clone disabled.\n", + fprintf (dump_file, "Not considering %s for cloning; " + "optimizing it for size.\n", cgraph_node_name (node)); return false; } - if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl))) + init_caller_stats (&stats); + cgraph_for_node_and_aliases (node, gather_caller_stats, &stats, false); + + if (inline_summary (node)->self_size < stats.n_calls) { if (dump_file) - fprintf (dump_file, "Not considering %s for cloning; optimizing it for size.\n", + fprintf (dump_file, "Considering %s for cloning; code might shrink.\n", cgraph_node_name (node)); - return false; + return true; } /* When profile is available and function is hot, propagate into it even if @@ -467,15 +493,16 @@ ipcp_cloning_candidate_p (struct cgraph_node *node) significantly. */ if (max_count) { - if (direct_call_sum > node->count * 90 / 100) + if (stats.count_sum > node->count * 90 / 100) { if (dump_file) - fprintf (dump_file, "Considering %s for cloning; usually called directly.\n", + fprintf (dump_file, "Considering %s for cloning; " + "usually called directly.\n", cgraph_node_name (node)); return true; } } - if (!n_hot_calls) + if (!stats.n_hot_calls) { if (dump_file) fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n", @@ -488,1012 +515,1918 @@ ipcp_cloning_candidate_p (struct cgraph_node *node) return true; } -/* Mark parameter with index I of function described by INFO as unsuitable for - devirtualization. Return true if it has already been marked so. */ +/* Arrays representing a topological ordering of call graph nodes and a stack + of noes used during constant propagation. */ -static bool -ipa_set_param_cannot_devirtualize (struct ipa_node_params *info, int i) +struct topo_info { - bool ret = info->params[i].cannot_devirtualize; - info->params[i].cannot_devirtualize = true; - if (info->params[i].types) - VEC_free (tree, heap, info->params[i].types); + struct cgraph_node **order; + struct cgraph_node **stack; + int nnodes, stack_top; +}; + +/* Allocate the arrays in TOPO and topologically sort the nodes into order. */ + +static void +build_toporder_info (struct topo_info *topo) +{ + topo->order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); + topo->stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); + topo->stack_top = 0; + topo->nnodes = ipa_reduced_postorder (topo->order, true, true, NULL); +} + +/* Free information about strongly connected components and the arrays in + TOPO. */ + +static void +free_toporder_info (struct topo_info *topo) +{ + ipa_free_postorder_info (); + free (topo->order); + free (topo->stack); +} + +/* Add NODE to the stack in TOPO, unless it is already there. */ + +static inline void +push_node_to_stack (struct topo_info *topo, struct cgraph_node *node) +{ + struct ipa_node_params *info = IPA_NODE_REF (node); + if (info->node_enqueued) + return; + info->node_enqueued = 1; + topo->stack[topo->stack_top++] = node; +} + +/* Pop a node from the stack in TOPO and return it or return NULL if the stack + is empty. */ + +static struct cgraph_node * +pop_node_from_stack (struct topo_info *topo) +{ + if (topo->stack_top) + { + struct cgraph_node *node; + topo->stack_top--; + node = topo->stack[topo->stack_top]; + IPA_NODE_REF (node)->node_enqueued = 0; + return node; + } + else + return NULL; +} + +/* Set lattice LAT to bottom and return true if it previously was not set as + such. */ + +static inline bool +set_lattice_to_bottom (struct ipcp_lattice *lat) +{ + bool ret = !lat->bottom; + lat->bottom = true; return ret; } -/* Initialize ipcp_lattices array. The lattices corresponding to supported - types (integers, real types and Fortran constants defined as const_decls) - are initialized to IPA_TOP, the rest of them to IPA_BOTTOM. */ +/* Mark lattice as containing an unknown value and return true if it previously + was not marked as such. */ + +static inline bool +set_lattice_contains_variable (struct ipcp_lattice *lat) +{ + bool ret = !lat->contains_variable; + lat->contains_variable = true; + return ret; +} + +/* Initialize ipcp_lattices. */ + static void -ipcp_initialize_node_lattices (struct cgraph_node *node) +initialize_node_lattices (struct cgraph_node *node) { - int i; struct ipa_node_params *info = IPA_NODE_REF (node); - enum ipa_lattice_type type; + struct cgraph_edge *ie; + bool disable = false, variable = false; + int i; + gcc_checking_assert (cgraph_function_with_gimple_body_p (node)); if (ipa_is_called_with_var_arguments (info)) - type = IPA_BOTTOM; - /* We don't know how to clone thunks even when they are local. */ - else if (node->local.local - && !node->thunk.thunk_p) - type = IPA_TOP; - /* When cloning is allowed, we can assume that externally visible functions - are not called. We will compensate this by cloning later. */ - else if (ipcp_cloning_candidate_p (node)) - type = IPA_TOP, n_cloning_candidates ++; - else - type = IPA_BOTTOM; + disable = true; + else if (!node->local.local) + { + /* When cloning is allowed, we can assume that externally visible + functions are not called. We will compensate this by cloning + later. */ + if (ipcp_versionable_function_p (node) + && ipcp_cloning_candidate_p (node)) + variable = true; + else + disable = true; + } - for (i = 0; i < ipa_get_param_count (info) ; i++) + if (disable || variable) { - ipa_get_lattice (info, i)->type = type; - if (type == IPA_BOTTOM) - ipa_set_param_cannot_devirtualize (info, i); + for (i = 0; i < ipa_get_param_count (info) ; i++) + { + struct ipcp_lattice *lat = ipa_get_lattice (info, i); + if (disable) + set_lattice_to_bottom (lat); + else + set_lattice_contains_variable (lat); + } + if (dump_file && (dump_flags & TDF_DETAILS) + && node->alias && node->thunk.thunk_p) + fprintf (dump_file, "Marking all lattices of %s/%i as %s\n", + cgraph_node_name (node), node->uid, + disable ? "BOTTOM" : "VARIABLE"); } + + for (ie = node->indirect_calls; ie; ie = ie->next_callee) + if (ie->indirect_info->polymorphic) + { + gcc_checking_assert (ie->indirect_info->param_index >= 0); + ipa_get_lattice (info, ie->indirect_info->param_index)->virt_call = 1; + } +} + +/* Return the result of a (possibly arithmetic) pass through jump function + JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be + determined or itself is considered an interprocedural invariant. */ + +static tree +ipa_get_jf_pass_through_result (struct ipa_jump_func *jfunc, tree input) +{ + tree restype, res; + + gcc_checking_assert (is_gimple_ip_invariant (input)); + if (jfunc->value.pass_through.operation == NOP_EXPR) + return input; + + if (TREE_CODE_CLASS (jfunc->value.pass_through.operation) + == tcc_comparison) + restype = boolean_type_node; + else + restype = TREE_TYPE (input); + res = fold_binary (jfunc->value.pass_through.operation, restype, + input, jfunc->value.pass_through.operand); + + if (res && !is_gimple_ip_invariant (res)) + return NULL_TREE; + + return res; } -/* Build a constant tree with type TREE_TYPE and value according to LAT. - Return the tree, or, if it is not possible to convert such value - to TREE_TYPE, NULL. */ +/* Return the result of an ancestor jump function JFUNC on the constant value + INPUT. Return NULL_TREE if that cannot be determined. */ + static tree -build_const_val (struct ipcp_lattice *lat, tree tree_type) +ipa_get_jf_ancestor_result (struct ipa_jump_func *jfunc, tree input) { - tree val; + if (TREE_CODE (input) == ADDR_EXPR) + { + tree t = TREE_OPERAND (input, 0); + t = build_ref_for_offset (EXPR_LOCATION (t), t, + jfunc->value.ancestor.offset, + jfunc->value.ancestor.type, NULL, false); + return build_fold_addr_expr (t); + } + else + return NULL_TREE; +} - gcc_assert (ipcp_lat_is_const (lat)); - val = lat->constant; +/* Determine whether JFUNC evaluates to a known value (that is either a + constant or a binfo) and if so, return it. Otherwise return NULL. INFO + describes the caller node so that pass-through jump functions can be + evaluated. */ - if (!useless_type_conversion_p (tree_type, TREE_TYPE (val))) +static tree +ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc) +{ + if (jfunc->type == IPA_JF_CONST) + return jfunc->value.constant; + else if (jfunc->type == IPA_JF_KNOWN_TYPE) + return jfunc->value.base_binfo; + else if (jfunc->type == IPA_JF_PASS_THROUGH + || jfunc->type == IPA_JF_ANCESTOR) { - if (fold_convertible_p (tree_type, val)) - return fold_build1 (NOP_EXPR, tree_type, val); - else if (TYPE_SIZE (tree_type) == TYPE_SIZE (TREE_TYPE (val))) - return fold_build1 (VIEW_CONVERT_EXPR, tree_type, val); + tree input; + int idx; + + if (jfunc->type == IPA_JF_PASS_THROUGH) + idx = jfunc->value.pass_through.formal_id; else - return NULL; + idx = jfunc->value.ancestor.formal_id; + + if (info->ipcp_orig_node) + input = VEC_index (tree, info->known_vals, idx); + else + { + struct ipcp_lattice *lat; + + if (!info->lattices) + { + gcc_checking_assert (!flag_ipa_cp); + return NULL_TREE; + } + lat = ipa_get_lattice (info, idx); + if (!ipa_lat_is_single_const (lat)) + return NULL_TREE; + input = lat->values->value; + } + + if (!input) + return NULL_TREE; + + if (jfunc->type == IPA_JF_PASS_THROUGH) + { + if (jfunc->value.pass_through.operation == NOP_EXPR) + return input; + else if (TREE_CODE (input) == TREE_BINFO) + return NULL_TREE; + else + return ipa_get_jf_pass_through_result (jfunc, input); + } + else + { + if (TREE_CODE (input) == TREE_BINFO) + return get_binfo_at_offset (input, jfunc->value.ancestor.offset, + jfunc->value.ancestor.type); + else + return ipa_get_jf_ancestor_result (jfunc, input); + } } - return val; + else + return NULL_TREE; } -/* Compute the proper scale for NODE. It is the ratio between the number of - direct calls (represented on the incoming cgraph_edges) and sum of all - invocations of NODE (represented as count in cgraph_node). +/* Determine whether JFUNC evaluates to a constant and if so, return it. + Otherwise return NULL. INFO describes the caller node so that pass-through + jump functions can be evaluated. */ - FIXME: This code is wrong. Since the callers can be also clones and - the clones are not scaled yet, the sums gets unrealistically high. - To properly compute the counts, we would need to do propagation across - callgraph (as external call to A might imply call to non-cloned B - if A's clone calls cloned B). */ -static void -ipcp_compute_node_scale (struct cgraph_node *node) +tree +ipa_cst_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc) { - gcov_type sum; - struct cgraph_edge *cs; + tree res = ipa_value_from_jfunc (info, jfunc); - sum = 0; - /* Compute sum of all counts of callers. */ - for (cs = node->callers; cs != NULL; cs = cs->next_caller) - sum += cs->count; - /* Work around the unrealistically high sum problem. We just don't want - the non-cloned body to have negative or very low frequency. Since - majority of execution time will be spent in clones anyway, this should - give good enough profile. */ - if (sum > node->count * 9 / 10) - sum = node->count * 9 / 10; - if (node->count == 0) - ipcp_set_node_scale (node, 0); + if (res && TREE_CODE (res) == TREE_BINFO) + return NULL_TREE; else - ipcp_set_node_scale (node, sum * REG_BR_PROB_BASE / node->count); + return res; } -/* Return true if there are some formal parameters whose value is IPA_TOP (in - the whole compilation unit). Change their values to IPA_BOTTOM, since they - most probably get their values from outside of this compilation unit. */ -static bool -ipcp_change_tops_to_bottom (void) + +/* If checking is enabled, verify that no lattice is in the TOP state, i.e. not + bottom, not containing a variable component and without any known value at + the same time. */ + +DEBUG_FUNCTION void +ipcp_verify_propagated_values (void) { - int i, count; struct cgraph_node *node; - bool prop_again; - prop_again = false; - for (node = cgraph_nodes; node; node = node->next) - if (!node->alias) + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) + { + struct ipa_node_params *info = IPA_NODE_REF (node); + int i, count = ipa_get_param_count (info); + + for (i = 0; i < count; i++) + { + struct ipcp_lattice *lat = ipa_get_lattice (info, i); + + if (!lat->bottom + && !lat->contains_variable + && lat->values_count == 0) + { + if (dump_file) + { + fprintf (dump_file, "\nIPA lattices after constant " + "propagation:\n"); + print_all_lattices (dump_file, true, false); + } + + gcc_unreachable (); + } + } + } +} + +/* Return true iff X and Y should be considered equal values by IPA-CP. */ + +static bool +values_equal_for_ipcp_p (tree x, tree y) +{ + gcc_checking_assert (x != NULL_TREE && y != NULL_TREE); + + if (x == y) + return true; + + if (TREE_CODE (x) == TREE_BINFO || TREE_CODE (y) == TREE_BINFO) + return false; + + if (TREE_CODE (x) == ADDR_EXPR + && TREE_CODE (y) == ADDR_EXPR + && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL + && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL) + return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)), + DECL_INITIAL (TREE_OPERAND (y, 0)), 0); + else + return operand_equal_p (x, y, 0); +} + +/* Add a new value source to VAL, marking that a value comes from edge CS and + (if the underlying jump function is a pass-through or an ancestor one) from + a caller value SRC_VAL of a caller parameter described by SRC_INDEX. */ + +static void +add_value_source (struct ipcp_value *val, struct cgraph_edge *cs, + struct ipcp_value *src_val, int src_idx) +{ + struct ipcp_value_source *src; + + src = (struct ipcp_value_source *) pool_alloc (ipcp_sources_pool); + src->cs = cs; + src->val = src_val; + src->index = src_idx; + + src->next = val->sources; + val->sources = src; +} + + +/* Try to add NEWVAL to LAT, potentially creating a new struct ipcp_value for + it. CS, SRC_VAL and SRC_INDEX are meant for add_value_source and have the + same meaning. */ + +static bool +add_value_to_lattice (struct ipcp_lattice *lat, tree newval, + struct cgraph_edge *cs, struct ipcp_value *src_val, + int src_idx) +{ + struct ipcp_value *val; + + if (lat->bottom) + return false; + + + for (val = lat->values; val; val = val->next) + if (values_equal_for_ipcp_p (val->value, newval)) + { + if (edge_within_scc (cs)) + { + struct ipcp_value_source *s; + for (s = val->sources; s ; s = s->next) + if (s->cs == cs) + break; + if (s) + return false; + } + + add_value_source (val, cs, src_val, src_idx); + return false; + } + + if (lat->values_count == PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE)) + { + /* We can only free sources, not the values themselves, because sources + of other values in this this SCC might point to them. */ + for (val = lat->values; val; val = val->next) + { + while (val->sources) + { + struct ipcp_value_source *src = val->sources; + val->sources = src->next; + pool_free (ipcp_sources_pool, src); + } + } + + lat->values = NULL; + return set_lattice_to_bottom (lat); + } + + lat->values_count++; + val = (struct ipcp_value *) pool_alloc (ipcp_values_pool); + memset (val, 0, sizeof (*val)); + + add_value_source (val, cs, src_val, src_idx); + val->value = newval; + val->next = lat->values; + lat->values = val; + return true; +} + +/* Propagate values through a pass-through jump function JFUNC associated with + edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX + is the index of the source parameter. */ + +static bool +propagate_vals_accross_pass_through (struct cgraph_edge *cs, + struct ipa_jump_func *jfunc, + struct ipcp_lattice *src_lat, + struct ipcp_lattice *dest_lat, + int src_idx) +{ + struct ipcp_value *src_val; + bool ret = false; + + if (jfunc->value.pass_through.operation == NOP_EXPR) + for (src_val = src_lat->values; src_val; src_val = src_val->next) + ret |= add_value_to_lattice (dest_lat, src_val->value, cs, + src_val, src_idx); + /* Do not create new values when propagating within an SCC because if there + arithmetic functions with circular dependencies, there is infinite number + of them and we would just make lattices bottom. */ + else if (edge_within_scc (cs)) + ret = set_lattice_contains_variable (dest_lat); + else + for (src_val = src_lat->values; src_val; src_val = src_val->next) { - struct ipa_node_params *info = IPA_NODE_REF (node); - count = ipa_get_param_count (info); - for (i = 0; i < count; i++) + tree cstval = src_val->value; + + if (TREE_CODE (cstval) == TREE_BINFO) { - struct ipcp_lattice *lat = ipa_get_lattice (info, i); - if (lat->type == IPA_TOP) - { - prop_again = true; - if (dump_file) - { - fprintf (dump_file, "Forcing param "); - print_generic_expr (dump_file, ipa_get_param (info, i), 0); - fprintf (dump_file, " of node %s to bottom.\n", - cgraph_node_name (node)); - } - lat->type = IPA_BOTTOM; - } - if (!ipa_param_cannot_devirtualize_p (info, i) - && ipa_param_types_vec_empty (info, i)) - { - prop_again = true; - ipa_set_param_cannot_devirtualize (info, i); - if (dump_file) - { - fprintf (dump_file, "Marking param "); - print_generic_expr (dump_file, ipa_get_param (info, i), 0); - fprintf (dump_file, " of node %s as unusable for " - "devirtualization.\n", - cgraph_node_name (node)); - } - } + ret |= set_lattice_contains_variable (dest_lat); + continue; } + cstval = ipa_get_jf_pass_through_result (jfunc, cstval); + + if (cstval) + ret |= add_value_to_lattice (dest_lat, cstval, cs, src_val, src_idx); + else + ret |= set_lattice_contains_variable (dest_lat); } - return prop_again; + + return ret; } -/* Insert BINFO to the list of known types of parameter number I of the - function described by CALLEE_INFO. Return true iff the type information - associated with the callee parameter changed in any way. */ +/* Propagate values through an ancestor jump function JFUNC associated with + edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX + is the index of the source parameter. */ static bool -ipcp_add_param_type (struct ipa_node_params *callee_info, int i, tree binfo) +propagate_vals_accross_ancestor (struct cgraph_edge *cs, + struct ipa_jump_func *jfunc, + struct ipcp_lattice *src_lat, + struct ipcp_lattice *dest_lat, + int src_idx) { - int j, count; + struct ipcp_value *src_val; + bool ret = false; - if (ipa_param_cannot_devirtualize_p (callee_info, i)) + if (edge_within_scc (cs)) + return set_lattice_contains_variable (dest_lat); + + for (src_val = src_lat->values; src_val; src_val = src_val->next) + { + tree t = src_val->value; + + if (TREE_CODE (t) == TREE_BINFO) + t = get_binfo_at_offset (t, jfunc->value.ancestor.offset, + jfunc->value.ancestor.type); + else + t = ipa_get_jf_ancestor_result (jfunc, t); + + if (t) + ret |= add_value_to_lattice (dest_lat, t, cs, src_val, src_idx); + else + ret |= set_lattice_contains_variable (dest_lat); + } + + return ret; +} + +/* Propagate values across jump function JFUNC that is associated with edge CS + and put the values into DEST_LAT. */ + +static bool +propagate_accross_jump_function (struct cgraph_edge *cs, + struct ipa_jump_func *jfunc, + struct ipcp_lattice *dest_lat) +{ + if (dest_lat->bottom) return false; - if (callee_info->params[i].types) + if (jfunc->type == IPA_JF_CONST + || jfunc->type == IPA_JF_KNOWN_TYPE) { - count = VEC_length (tree, callee_info->params[i].types); - for (j = 0; j < count; j++) - if (VEC_index (tree, callee_info->params[i].types, j) == binfo) - return false; + tree val; + + if (jfunc->type == IPA_JF_KNOWN_TYPE) + val = jfunc->value.base_binfo; + else + val = jfunc->value.constant; + return add_value_to_lattice (dest_lat, val, cs, NULL, 0); } + else if (jfunc->type == IPA_JF_PASS_THROUGH + || jfunc->type == IPA_JF_ANCESTOR) + { + struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); + struct ipcp_lattice *src_lat; + int src_idx; + bool ret; - if (VEC_length (tree, callee_info->params[i].types) - == (unsigned) PARAM_VALUE (PARAM_DEVIRT_TYPE_LIST_SIZE)) - return !ipa_set_param_cannot_devirtualize (callee_info, i); + if (jfunc->type == IPA_JF_PASS_THROUGH) + src_idx = jfunc->value.pass_through.formal_id; + else + src_idx = jfunc->value.ancestor.formal_id; - VEC_safe_push (tree, heap, callee_info->params[i].types, binfo); - return true; + src_lat = ipa_get_lattice (caller_info, src_idx); + if (src_lat->bottom) + return set_lattice_contains_variable (dest_lat); + + /* If we would need to clone the caller and cannot, do not propagate. */ + if (!ipcp_versionable_function_p (cs->caller) + && (src_lat->contains_variable + || (src_lat->values_count > 1))) + return set_lattice_contains_variable (dest_lat); + + if (jfunc->type == IPA_JF_PASS_THROUGH) + ret = propagate_vals_accross_pass_through (cs, jfunc, src_lat, + dest_lat, src_idx); + else + ret = propagate_vals_accross_ancestor (cs, jfunc, src_lat, dest_lat, + src_idx); + + if (src_lat->contains_variable) + ret |= set_lattice_contains_variable (dest_lat); + + return ret; + } + + /* TODO: We currently do not handle member method pointers in IPA-CP (we only + use it for indirect inlining), we should propagate them too. */ + return set_lattice_contains_variable (dest_lat); } -/* Copy known types information for parameter number CALLEE_IDX of CALLEE_INFO - from a parameter of CALLER_INFO as described by JF. Return true iff the - type information changed in any way. JF must be a pass-through or an - ancestor jump function. */ +/* Propagate constants from the caller to the callee of CS. INFO describes the + caller. */ static bool -ipcp_copy_types (struct ipa_node_params *caller_info, - struct ipa_node_params *callee_info, - int callee_idx, struct ipa_jump_func *jf) +propagate_constants_accross_call (struct cgraph_edge *cs) { - int caller_idx, j, count; - bool res; + struct ipa_node_params *callee_info; + enum availability availability; + struct cgraph_node *callee, *alias_or_thunk; + struct ipa_edge_args *args; + bool ret = false; + int i, count; - if (ipa_param_cannot_devirtualize_p (callee_info, callee_idx)) + callee = cgraph_function_node (cs->callee, &availability); + if (!callee->analyzed) return false; + gcc_checking_assert (cgraph_function_with_gimple_body_p (callee)); + callee_info = IPA_NODE_REF (callee); + if (ipa_is_called_with_var_arguments (callee_info)) + return false; + + args = IPA_EDGE_REF (cs); + count = ipa_get_cs_argument_count (args); - if (jf->type == IPA_JF_PASS_THROUGH) + /* If this call goes through a thunk we must not propagate to the first (0th) + parameter. However, we might need to uncover a thunk from below a series + of aliases first. */ + alias_or_thunk = cs->callee; + while (alias_or_thunk->alias) + alias_or_thunk = cgraph_alias_aliased_node (alias_or_thunk); + if (alias_or_thunk->thunk.thunk_p) { - if (jf->value.pass_through.operation != NOP_EXPR) - { - ipa_set_param_cannot_devirtualize (callee_info, callee_idx); - return true; - } - caller_idx = jf->value.pass_through.formal_id; + ret |= set_lattice_contains_variable (ipa_get_lattice (callee_info, 0)); + i = 1; } else - caller_idx = jf->value.ancestor.formal_id; + i = 0; - if (ipa_param_cannot_devirtualize_p (caller_info, caller_idx)) + for (; i < count; i++) { - ipa_set_param_cannot_devirtualize (callee_info, callee_idx); - return true; + struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i); + struct ipcp_lattice *dest_lat = ipa_get_lattice (callee_info, i); + + if (availability == AVAIL_OVERWRITABLE) + ret |= set_lattice_contains_variable (dest_lat); + else + ret |= propagate_accross_jump_function (cs, jump_func, dest_lat); } + return ret; +} - if (!caller_info->params[caller_idx].types) - return false; +/* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS + (which can contain both constants and binfos) or KNOWN_BINFOS (which can be + NULL) return the destination. If simple thunk delta must be applied too, + store it to DELTA. */ + +static tree +get_indirect_edge_target (struct cgraph_edge *ie, tree *delta, + VEC (tree, heap) *known_vals, + VEC (tree, heap) *known_binfos) +{ + int param_index = ie->indirect_info->param_index; + HOST_WIDE_INT token, anc_offset; + tree otr_type; + tree t; - res = false; - count = VEC_length (tree, caller_info->params[caller_idx].types); - for (j = 0; j < count; j++) + if (param_index == -1) + return NULL_TREE; + + if (!ie->indirect_info->polymorphic) { - tree binfo = VEC_index (tree, caller_info->params[caller_idx].types, j); - if (jf->type == IPA_JF_ANCESTOR) + tree t = VEC_index (tree, known_vals, param_index); + if (t && + TREE_CODE (t) == ADDR_EXPR + && TREE_CODE (TREE_OPERAND (t, 0)) == FUNCTION_DECL) { - binfo = get_binfo_at_offset (binfo, jf->value.ancestor.offset, - jf->value.ancestor.type); - if (!binfo) - { - ipa_set_param_cannot_devirtualize (callee_info, callee_idx); - return true; - } + *delta = NULL_TREE; + return TREE_OPERAND (t, 0); } - res |= ipcp_add_param_type (callee_info, callee_idx, binfo); + else + return NULL_TREE; + } + + token = ie->indirect_info->otr_token; + anc_offset = ie->indirect_info->anc_offset; + otr_type = ie->indirect_info->otr_type; + + t = VEC_index (tree, known_vals, param_index); + if (!t && known_binfos) + t = VEC_index (tree, known_binfos, param_index); + if (!t) + return NULL_TREE; + + if (TREE_CODE (t) != TREE_BINFO) + { + tree binfo; + binfo = gimple_extract_devirt_binfo_from_cst (t); + if (!binfo) + return NULL_TREE; + binfo = get_binfo_at_offset (binfo, anc_offset, otr_type); + if (!binfo) + return NULL_TREE; + return gimple_get_virt_method_for_binfo (token, binfo, delta); + } + else + { + tree binfo; + + binfo = get_binfo_at_offset (t, anc_offset, otr_type); + if (!binfo) + return NULL_TREE; + return gimple_get_virt_method_for_binfo (token, binfo, delta); } +} + +/* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS + and KNOWN_BINFOS. */ + +static int +devirtualization_time_bonus (struct cgraph_node *node, + VEC (tree, heap) *known_csts, + VEC (tree, heap) *known_binfos) +{ + struct cgraph_edge *ie; + int res = 0; + + for (ie = node->indirect_calls; ie; ie = ie->next_callee) + { + struct cgraph_node *callee; + struct inline_summary *isummary; + tree delta, target; + + target = get_indirect_edge_target (ie, &delta, known_csts, known_binfos); + if (!target) + continue; + + /* Only bare minimum benefit for clearly un-inlineable targets. */ + res += 1; + callee = cgraph_get_node (target); + if (!callee || !callee->analyzed) + continue; + isummary = inline_summary (callee); + if (!isummary->inlinable) + continue; + + /* FIXME: The values below need re-considering and perhaps also + integrating into the cost metrics, at lest in some very basic way. */ + if (isummary->size <= MAX_INLINE_INSNS_AUTO / 4) + res += 31; + else if (isummary->size <= MAX_INLINE_INSNS_AUTO / 2) + res += 15; + else if (isummary->size <= MAX_INLINE_INSNS_AUTO + || DECL_DECLARED_INLINE_P (callee->decl)) + res += 7; + } + return res; } -/* Propagate type information for parameter of CALLEE_INFO number I as - described by JF. CALLER_INFO describes the caller. Return true iff the - type information changed in any way. */ +/* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT + and SIZE_COST and with the sum of frequencies of incoming edges to the + potential new clone in FREQUENCIES. */ static bool -ipcp_propagate_types (struct ipa_node_params *caller_info, - struct ipa_node_params *callee_info, - struct ipa_jump_func *jf, int i) +good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit, + int freq_sum, gcov_type count_sum, int size_cost) { - switch (jf->type) + if (time_benefit == 0 + || !flag_ipa_cp_clone + || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl))) + return false; + + gcc_checking_assert (size_cost >= 0); + + /* FIXME: These decisions need tuning. */ + if (max_count) { - case IPA_JF_UNKNOWN: - case IPA_JF_CONST_MEMBER_PTR: - case IPA_JF_CONST: - break; + int evaluation, factor = (count_sum * 1000) / max_count; + + evaluation = (time_benefit * factor) / size_cost; - case IPA_JF_KNOWN_TYPE: - return ipcp_add_param_type (callee_info, i, jf->value.base_binfo); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " good_cloning_opportunity_p (time: %i, " + "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC + ") -> evaluation: %i, threshold: %i\n", + time_benefit, size_cost, (HOST_WIDE_INT) count_sum, + evaluation, 500); - case IPA_JF_PASS_THROUGH: - case IPA_JF_ANCESTOR: - return ipcp_copy_types (caller_info, callee_info, i, jf); + return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD); } + else + { + int evaluation = (time_benefit * freq_sum) / size_cost; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " good_cloning_opportunity_p (time: %i, " + "size: %i, freq_sum: %i) -> evaluation: %i, threshold: %i\n", + time_benefit, size_cost, freq_sum, evaluation, + CGRAPH_FREQ_BASE /2); - /* If we reach this we cannot use this parameter for devirtualization. */ - return !ipa_set_param_cannot_devirtualize (callee_info, i); + return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD); + } } -/* Interprocedural analysis. The algorithm propagates constants from the - caller's parameters to the callee's arguments. */ + +/* Allocate KNOWN_CSTS and KNOWN_BINFOS and populate them with values of + parameters that are known independent of the context. INFO describes the + function. If REMOVABLE_PARAMS_COST is non-NULL, the movement cost of all + removable parameters will be stored in it. */ + +static bool +gather_context_independent_values (struct ipa_node_params *info, + VEC (tree, heap) **known_csts, + VEC (tree, heap) **known_binfos, + int *removable_params_cost) +{ + int i, count = ipa_get_param_count (info); + bool ret = false; + + *known_csts = NULL; + *known_binfos = NULL; + VEC_safe_grow_cleared (tree, heap, *known_csts, count); + VEC_safe_grow_cleared (tree, heap, *known_binfos, count); + + if (removable_params_cost) + *removable_params_cost = 0; + + for (i = 0; i < count ; i++) + { + struct ipcp_lattice *lat = ipa_get_lattice (info, i); + + if (ipa_lat_is_single_const (lat)) + { + struct ipcp_value *val = lat->values; + if (TREE_CODE (val->value) != TREE_BINFO) + { + VEC_replace (tree, *known_csts, i, val->value); + if (removable_params_cost) + *removable_params_cost + += estimate_move_cost (TREE_TYPE (val->value)); + ret = true; + } + else if (lat->virt_call) + { + VEC_replace (tree, *known_binfos, i, val->value); + ret = true; + } + else if (removable_params_cost + && !ipa_is_param_used (info, i)) + *removable_params_cost + += estimate_move_cost (TREE_TYPE (ipa_get_param (info, i))); + } + else if (removable_params_cost + && !ipa_is_param_used (info, i)) + *removable_params_cost + += estimate_move_cost (TREE_TYPE (ipa_get_param (info, i))); + } + + return ret; +} + +/* Iterate over known values of parameters of NODE and estimate the local + effects in terms of time and size they have. */ + static void -ipcp_propagate_stage (void) +estimate_local_effects (struct cgraph_node *node) { - int i; - struct ipcp_lattice inc_lat = { IPA_BOTTOM, NULL }; - struct ipcp_lattice new_lat = { IPA_BOTTOM, NULL }; - struct ipcp_lattice *dest_lat; - struct cgraph_edge *cs; - struct ipa_jump_func *jump_func; - struct ipa_func_list *wl; - int count; + struct ipa_node_params *info = IPA_NODE_REF (node); + int i, count = ipa_get_param_count (info); + VEC (tree, heap) *known_csts, *known_binfos; + bool always_const; + int base_time = inline_summary (node)->time; + int removable_params_cost; - ipa_check_create_node_params (); - ipa_check_create_edge_args (); + if (!count || !ipcp_versionable_function_p (node)) + return; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "\nEstimating effects for %s/%i, base_time: %i.\n", + cgraph_node_name (node), node->uid, base_time); - /* Initialize worklist to contain all functions. */ - wl = ipa_init_func_list (); - while (wl) + always_const = gather_context_independent_values (info, &known_csts, + &known_binfos, + &removable_params_cost); + if (always_const) { - struct cgraph_node *node = ipa_pop_func_from_list (&wl); - struct ipa_node_params *info = IPA_NODE_REF (node); + struct caller_statistics stats; + int time, size; + + init_caller_stats (&stats); + cgraph_for_node_and_aliases (node, gather_caller_stats, &stats, false); + estimate_ipcp_clone_size_and_time (node, known_csts, &size, &time); + time -= devirtualization_time_bonus (node, known_csts, known_binfos); + time -= removable_params_cost; + size -= stats.n_calls * removable_params_cost; + + if (dump_file) + fprintf (dump_file, " - context independent values, size: %i, " + "time_benefit: %i\n", size, base_time - time); - for (cs = node->callees; cs; cs = cs->next_callee) + if (size <= 0 + || cgraph_will_be_removed_from_program_if_no_direct_calls (node)) { - struct cgraph_node *callee = cgraph_function_or_thunk_node (cs->callee, NULL); - struct ipa_node_params *callee_info = IPA_NODE_REF (callee); - struct ipa_edge_args *args = IPA_EDGE_REF (cs); + info->clone_for_all_contexts = true; + base_time = time; - if (ipa_is_called_with_var_arguments (callee_info) - || !cs->callee->analyzed - || ipa_is_called_with_var_arguments (callee_info)) - continue; + if (dump_file) + fprintf (dump_file, " Decided to specialize for all " + "known contexts, code not going to grow.\n"); + } + else if (good_cloning_opportunity_p (node, base_time - time, + stats.freq_sum, stats.count_sum, + size)) + { + if (size + overall_size <= max_new_size) + { + info->clone_for_all_contexts = true; + base_time = time; + overall_size += size; - count = ipa_get_cs_argument_count (args); - for (i = 0; i < count; i++) + if (dump_file) + fprintf (dump_file, " Decided to specialize for all " + "known contexts, growth deemed beneficial.\n"); + } + else if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " Not cloning for all contexts because " + "max_new_size would be reached with %li.\n", + size + overall_size); + } + } + + for (i = 0; i < count ; i++) + { + struct ipcp_lattice *lat = ipa_get_lattice (info, i); + struct ipcp_value *val; + int emc; + + if (lat->bottom + || !lat->values + || VEC_index (tree, known_csts, i) + || VEC_index (tree, known_binfos, i)) + continue; + + for (val = lat->values; val; val = val->next) + { + int time, size, time_benefit; + + if (TREE_CODE (val->value) != TREE_BINFO) { - jump_func = ipa_get_ith_jump_func (args, i); - ipa_lattice_from_jfunc (info, &inc_lat, jump_func); - dest_lat = ipa_get_lattice (callee_info, i); - ipa_lattice_meet (&new_lat, &inc_lat, dest_lat); - if (ipcp_lattice_changed (&new_lat, dest_lat)) - { - dest_lat->type = new_lat.type; - dest_lat->constant = new_lat.constant; - ipa_push_func_to_list (&wl, callee); - } + VEC_replace (tree, known_csts, i, val->value); + VEC_replace (tree, known_binfos, i, NULL_TREE); + emc = estimate_move_cost (TREE_TYPE (val->value)); + } + else if (lat->virt_call) + { + VEC_replace (tree, known_csts, i, NULL_TREE); + VEC_replace (tree, known_binfos, i, val->value); + emc = 0; + } + else + continue; - if (ipcp_propagate_types (info, callee_info, jump_func, i)) - ipa_push_func_to_list (&wl, callee); + estimate_ipcp_clone_size_and_time (node, known_csts, &size, &time); + time_benefit = base_time - time + + devirtualization_time_bonus (node, known_csts, known_binfos) + + removable_params_cost + emc; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " - estimates for value "); + print_ipcp_constant_value (dump_file, val->value); + fprintf (dump_file, " for parameter "); + print_generic_expr (dump_file, ipa_get_param (info, i), 0); + fprintf (dump_file, ": time_benefit: %i, size: %i\n", + time_benefit, size); } + + val->local_time_benefit = time_benefit; + val->local_size_cost = size; } } + + VEC_free (tree, heap, known_csts); + VEC_free (tree, heap, known_binfos); } -/* Call the constant propagation algorithm and re-call it if necessary - (if there are undetermined values left). */ + +/* Add value CUR_VAL and all yet-unsorted values it is dependent on to the + topological sort of values. */ + static void -ipcp_iterate_stage (void) +add_val_to_toposort (struct ipcp_value *cur_val) { - struct cgraph_node *node; - n_cloning_candidates = 0; + static int dfs_counter = 0; + static struct ipcp_value *stack; + struct ipcp_value_source *src; - if (dump_file) - fprintf (dump_file, "\nIPA iterate stage:\n\n"); + if (cur_val->dfs) + return; - if (in_lto_p) - ipa_update_after_lto_read (); + dfs_counter++; + cur_val->dfs = dfs_counter; + cur_val->low_link = dfs_counter; + + cur_val->topo_next = stack; + stack = cur_val; + cur_val->on_stack = true; - for (node = cgraph_nodes; node; node = node->next) - if (!node->alias) + for (src = cur_val->sources; src; src = src->next) + if (src->val) { - ipcp_initialize_node_lattices (node); - ipcp_compute_node_scale (node); + if (src->val->dfs == 0) + { + add_val_to_toposort (src->val); + if (src->val->low_link < cur_val->low_link) + cur_val->low_link = src->val->low_link; + } + else if (src->val->on_stack + && src->val->dfs < cur_val->low_link) + cur_val->low_link = src->val->dfs; } - if (dump_file && (dump_flags & TDF_DETAILS)) + + if (cur_val->dfs == cur_val->low_link) { - ipcp_print_all_lattices (dump_file); - ipcp_function_scale_print (dump_file); + struct ipcp_value *v, *scc_list = NULL; + + do + { + v = stack; + stack = v->topo_next; + v->on_stack = false; + + v->scc_next = scc_list; + scc_list = v; + } + while (v != cur_val); + + cur_val->topo_next = values_topo; + values_topo = cur_val; } +} - ipcp_propagate_stage (); - if (ipcp_change_tops_to_bottom ()) - /* Some lattices have changed from IPA_TOP to IPA_BOTTOM. - This change should be propagated. */ +/* Add all values in lattices associated with NODE to the topological sort if + they are not there yet. */ + +static void +add_all_node_vals_to_toposort (struct cgraph_node *node) +{ + struct ipa_node_params *info = IPA_NODE_REF (node); + int i, count = ipa_get_param_count (info); + + for (i = 0; i < count ; i++) { - gcc_assert (n_cloning_candidates); - ipcp_propagate_stage (); + struct ipcp_lattice *lat = ipa_get_lattice (info, i); + struct ipcp_value *val; + + if (lat->bottom || !lat->values) + continue; + for (val = lat->values; val; val = val->next) + add_val_to_toposort (val); } - if (dump_file) +} + +/* One pass of constants propagation along the call graph edges, from callers + to callees (requires topological ordering in TOPO), iterate over strongly + connected components. */ + +static void +propagate_constants_topo (struct topo_info *topo) +{ + int i; + + for (i = topo->nnodes - 1; i >= 0; i--) { - fprintf (dump_file, "\nIPA lattices after propagation:\n"); - ipcp_print_all_lattices (dump_file); - if (dump_flags & TDF_DETAILS) - ipcp_print_profile_data (dump_file); + struct cgraph_node *v, *node = topo->order[i]; + struct ipa_dfs_info *node_dfs_info; + + if (!cgraph_function_with_gimple_body_p (node)) + continue; + + node_dfs_info = (struct ipa_dfs_info *) node->aux; + /* First, iteratively propagate within the strongly connected component + until all lattices stabilize. */ + v = node_dfs_info->next_cycle; + while (v) + { + push_node_to_stack (topo, v); + v = ((struct ipa_dfs_info *) v->aux)->next_cycle; + } + + v = node; + while (v) + { + struct cgraph_edge *cs; + + for (cs = v->callees; cs; cs = cs->next_callee) + if (edge_within_scc (cs) + && propagate_constants_accross_call (cs)) + push_node_to_stack (topo, cs->callee); + v = pop_node_from_stack (topo); + } + + /* Afterwards, propagate along edges leading out of the SCC, calculates + the local effects of the discovered constants and all valid values to + their topological sort. */ + v = node; + while (v) + { + struct cgraph_edge *cs; + + estimate_local_effects (v); + add_all_node_vals_to_toposort (v); + for (cs = v->callees; cs; cs = cs->next_callee) + if (!edge_within_scc (cs)) + propagate_constants_accross_call (cs); + + v = ((struct ipa_dfs_info *) v->aux)->next_cycle; + } } } -/* Check conditions to forbid constant insertion to function described by - NODE. */ -static inline bool -ipcp_node_modifiable_p (struct cgraph_node *node) +/* Propagate the estimated effects of individual values along the topological + from the dependant values to those they depend on. */ + +static void +propagate_effects (void) { - /* Once we will be able to do in-place replacement, we can be more - lax here. */ - return ipcp_versionable_function_p (node); + struct ipcp_value *base; + + for (base = values_topo; base; base = base->topo_next) + { + struct ipcp_value_source *src; + struct ipcp_value *val; + int time = 0, size = 0; + + for (val = base; val; val = val->scc_next) + { + time += val->local_time_benefit + val->prop_time_benefit; + size += val->local_size_cost + val->prop_size_cost; + } + + for (val = base; val; val = val->scc_next) + for (src = val->sources; src; src = src->next) + if (src->val + && cgraph_maybe_hot_edge_p (src->cs)) + { + src->val->prop_time_benefit += time; + src->val->prop_size_cost += size; + } + } } -/* Print count scale data structures. */ + +/* Propagate constants, binfos and their effects from the summaries + interprocedurally. */ + static void -ipcp_function_scale_print (FILE * f) +ipcp_propagate_stage (struct topo_info *topo) { struct cgraph_node *node; - for (node = cgraph_nodes; node; node = node->next) + if (dump_file) + fprintf (dump_file, "\n Propagating constants:\n\n"); + + if (in_lto_p) + ipa_update_after_lto_read (); + + + FOR_EACH_DEFINED_FUNCTION (node) + { + struct ipa_node_params *info = IPA_NODE_REF (node); + + determine_versionability (node); + if (cgraph_function_with_gimple_body_p (node)) + { + info->lattices = XCNEWVEC (struct ipcp_lattice, + ipa_get_param_count (info)); + initialize_node_lattices (node); + } + if (node->count > max_count) + max_count = node->count; + overall_size += inline_summary (node)->self_size; + } + + max_new_size = overall_size; + if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS)) + max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS); + max_new_size += max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1; + + if (dump_file) + fprintf (dump_file, "\noverall_size: %li, max_new_size: %li\n", + overall_size, max_new_size); + + propagate_constants_topo (topo); +#ifdef ENABLE_CHECKING + ipcp_verify_propagated_values (); +#endif + propagate_effects (); + + if (dump_file) { - if (!node->analyzed) - continue; - fprintf (f, "printing scale for %s: ", cgraph_node_name (node)); - fprintf (f, "value is " HOST_WIDE_INT_PRINT_DEC - " \n", (HOST_WIDE_INT) ipcp_get_node_scale (node)); + fprintf (dump_file, "\nIPA lattices after all propagation:\n"); + print_all_lattices (dump_file, (dump_flags & TDF_DETAILS), true); } } -/* Print counts of all cgraph nodes. */ +/* Discover newly direct outgoing edges from NODE which is a new clone with + known KNOWN_VALS and make them direct. */ + static void -ipcp_print_func_profile_counts (FILE * f) +ipcp_discover_new_direct_edges (struct cgraph_node *node, + VEC (tree, heap) *known_vals) { - struct cgraph_node *node; + struct cgraph_edge *ie, *next_ie; - for (node = cgraph_nodes; node; node = node->next) + for (ie = node->indirect_calls; ie; ie = next_ie) { - fprintf (f, "function %s: ", cgraph_node_name (node)); - fprintf (f, "count is " HOST_WIDE_INT_PRINT_DEC - " \n", (HOST_WIDE_INT) node->count); + tree delta, target; + + next_ie = ie->next_callee; + target = get_indirect_edge_target (ie, &delta, known_vals, NULL); + if (target) + ipa_make_edge_direct_to_target (ie, target, delta); } } -/* Print counts of all cgraph edges. */ +/* Vector of pointers which for linked lists of clones of an original crgaph + edge. */ + +static VEC (cgraph_edge_p, heap) *next_edge_clone; + +static inline void +grow_next_edge_clone_vector (void) +{ + if (VEC_length (cgraph_edge_p, next_edge_clone) + <= (unsigned) cgraph_edge_max_uid) + VEC_safe_grow_cleared (cgraph_edge_p, heap, next_edge_clone, + cgraph_edge_max_uid + 1); +} + +/* Edge duplication hook to grow the appropriate linked list in + next_edge_clone. */ + static void -ipcp_print_call_profile_counts (FILE * f) +ipcp_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst, + __attribute__((unused)) void *data) { - struct cgraph_node *node; - struct cgraph_edge *cs; + grow_next_edge_clone_vector (); + VEC_replace (cgraph_edge_p, next_edge_clone, dst->uid, + VEC_index (cgraph_edge_p, next_edge_clone, src->uid)); + VEC_replace (cgraph_edge_p, next_edge_clone, src->uid, dst); +} + +/* Get the next clone in the linked list of clones of an edge. */ + +static inline struct cgraph_edge * +get_next_cgraph_edge_clone (struct cgraph_edge *cs) +{ + return VEC_index (cgraph_edge_p, next_edge_clone, cs->uid); +} - for (node = cgraph_nodes; node; node = node->next) +/* Return true if edge CS does bring about the value described by SRC. */ + +static bool +cgraph_edge_brings_value_p (struct cgraph_edge *cs, + struct ipcp_value_source *src) +{ + struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); + + if (IPA_NODE_REF (cs->callee)->ipcp_orig_node + || caller_info->node_dead) + return false; + if (!src->val) + return true; + + if (caller_info->ipcp_orig_node) { - for (cs = node->callees; cs; cs = cs->next_callee) + tree t = VEC_index (tree, caller_info->known_vals, src->index); + return (t != NULL_TREE + && values_equal_for_ipcp_p (src->val->value, t)); + } + else + { + struct ipcp_lattice *lat = ipa_get_lattice (caller_info, src->index); + if (ipa_lat_is_single_const (lat) + && values_equal_for_ipcp_p (src->val->value, lat->values->value)) + return true; + else + return false; + } +} + +/* Given VAL, iterate over all its sources and if they still hold, add their + edge frequency and their number into *FREQUENCY and *CALLER_COUNT + respectively. */ + +static bool +get_info_about_necessary_edges (struct ipcp_value *val, int *freq_sum, + gcov_type *count_sum, int *caller_count) +{ + struct ipcp_value_source *src; + int freq = 0, count = 0; + gcov_type cnt = 0; + bool hot = false; + + for (src = val->sources; src; src = src->next) + { + struct cgraph_edge *cs = src->cs; + while (cs) { - fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller), - cgraph_node_name (cs->callee)); - fprintf (f, "count is " HOST_WIDE_INT_PRINT_DEC " \n", - (HOST_WIDE_INT) cs->count); + if (cgraph_edge_brings_value_p (cs, src)) + { + count++; + freq += cs->frequency; + cnt += cs->count; + hot |= cgraph_maybe_hot_edge_p (cs); + } + cs = get_next_cgraph_edge_clone (cs); } } + + *freq_sum = freq; + *count_sum = cnt; + *caller_count = count; + return hot; } -/* Print profile info for all functions. */ -static void -ipcp_print_profile_data (FILE * f) +/* Return a vector of incoming edges that do bring value VAL. It is assumed + their number is known and equal to CALLER_COUNT. */ + +static VEC (cgraph_edge_p,heap) * +gather_edges_for_value (struct ipcp_value *val, int caller_count) { - fprintf (f, "\nNODE COUNTS :\n"); - ipcp_print_func_profile_counts (f); - fprintf (f, "\nCS COUNTS stage:\n"); - ipcp_print_call_profile_counts (f); + struct ipcp_value_source *src; + VEC (cgraph_edge_p,heap) *ret; + + ret = VEC_alloc (cgraph_edge_p, heap, caller_count); + for (src = val->sources; src; src = src->next) + { + struct cgraph_edge *cs = src->cs; + while (cs) + { + if (cgraph_edge_brings_value_p (cs, src)) + VEC_quick_push (cgraph_edge_p, ret, cs); + cs = get_next_cgraph_edge_clone (cs); + } + } + + return ret; } -/* Build and initialize ipa_replace_map struct according to LAT. This struct is - processed by versioning, which operates according to the flags set. - PARM_TREE is the formal parameter found to be constant. LAT represents the - constant. */ +/* Construct a replacement map for a know VALUE for a formal parameter PARAM. + Return it or NULL if for some reason it cannot be created. */ + static struct ipa_replace_map * -ipcp_create_replace_map (tree parm_tree, struct ipcp_lattice *lat) +get_replacement_map (tree value, tree parm) { + tree req_type = TREE_TYPE (parm); struct ipa_replace_map *replace_map; - tree const_val; - const_val = build_const_val (lat, TREE_TYPE (parm_tree)); - if (const_val == NULL_TREE) + if (!useless_type_conversion_p (req_type, TREE_TYPE (value))) { - if (dump_file) + if (fold_convertible_p (req_type, value)) + value = fold_build1 (NOP_EXPR, req_type, value); + else if (TYPE_SIZE (req_type) == TYPE_SIZE (TREE_TYPE (value))) + value = fold_build1 (VIEW_CONVERT_EXPR, req_type, value); + else { - fprintf (dump_file, " const "); - print_generic_expr (dump_file, lat->constant, 0); - fprintf (dump_file, " can't be converted to param "); - print_generic_expr (dump_file, parm_tree, 0); - fprintf (dump_file, "\n"); + if (dump_file) + { + fprintf (dump_file, " const "); + print_generic_expr (dump_file, value, 0); + fprintf (dump_file, " can't be converted to param "); + print_generic_expr (dump_file, parm, 0); + fprintf (dump_file, "\n"); + } + return NULL; } - return NULL; } + replace_map = ggc_alloc_ipa_replace_map (); if (dump_file) { - fprintf (dump_file, " replacing param "); - print_generic_expr (dump_file, parm_tree, 0); + fprintf (dump_file, " replacing param "); + print_generic_expr (dump_file, parm, 0); fprintf (dump_file, " with const "); - print_generic_expr (dump_file, const_val, 0); + print_generic_expr (dump_file, value, 0); fprintf (dump_file, "\n"); } - replace_map->old_tree = parm_tree; - replace_map->new_tree = const_val; + replace_map->old_tree = parm; + replace_map->new_tree = value; replace_map->replace_p = true; replace_map->ref_p = false; return replace_map; } -/* Return true if this callsite should be redirected to the original callee - (instead of the cloned one). */ -static bool -ipcp_need_redirect_p (struct cgraph_edge *cs) -{ - struct ipa_node_params *orig_callee_info; - int i, count; - struct cgraph_node *node = cgraph_function_or_thunk_node (cs->callee, NULL); - struct cgraph_node *orig; - - if (!n_cloning_candidates) - return false; +/* Dump new profiling counts */ - /* We can't redirect anything in thunks, yet. */ - if (cs->caller->thunk.thunk_p) - return true; - - if ((orig = ipcp_get_orig_node (node)) != NULL) - node = orig; - if (ipcp_get_orig_node (cs->caller)) - return false; - - orig_callee_info = IPA_NODE_REF (node); - count = ipa_get_param_count (orig_callee_info); - for (i = 0; i < count; i++) - { - struct ipcp_lattice *lat = ipa_get_lattice (orig_callee_info, i); - struct ipa_jump_func *jump_func; - - jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i); - if ((ipcp_lat_is_const (lat) - && jump_func->type != IPA_JF_CONST) - || (!ipa_param_cannot_devirtualize_p (orig_callee_info, i) - && !ipa_param_types_vec_empty (orig_callee_info, i) - && jump_func->type != IPA_JF_CONST - && jump_func->type != IPA_JF_KNOWN_TYPE)) - return true; - } - - return false; -} - -/* Fix the callsites and the call graph after function cloning was done. */ static void -ipcp_update_callgraph (void) +dump_profile_updates (struct cgraph_node *orig_node, + struct cgraph_node *new_node) { - struct cgraph_node *node; + struct cgraph_edge *cs; - for (node = cgraph_nodes; node; node = node->next) - if (node->analyzed && ipcp_node_is_clone (node)) - { - bitmap args_to_skip = NULL; - struct cgraph_node *orig_node = ipcp_get_orig_node (node); - struct ipa_node_params *info = IPA_NODE_REF (orig_node); - int i, count = ipa_get_param_count (info); - struct cgraph_edge *cs, *next; + fprintf (dump_file, " setting count of the specialized node to " + HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) new_node->count); + for (cs = new_node->callees; cs ; cs = cs->next_callee) + fprintf (dump_file, " edge to %s has count " + HOST_WIDE_INT_PRINT_DEC "\n", + cgraph_node_name (cs->callee), (HOST_WIDE_INT) cs->count); + + fprintf (dump_file, " setting count of the original node to " + HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) orig_node->count); + for (cs = orig_node->callees; cs ; cs = cs->next_callee) + fprintf (dump_file, " edge to %s is left with " + HOST_WIDE_INT_PRINT_DEC "\n", + cgraph_node_name (cs->callee), (HOST_WIDE_INT) cs->count); +} - if (node->local.can_change_signature) - { - args_to_skip = BITMAP_ALLOC (NULL); - for (i = 0; i < count; i++) - { - struct ipcp_lattice *lat = ipa_get_lattice (info, i); - - /* We can proactively remove obviously unused arguments. */ - if (!ipa_is_param_used (info, i)) - { - bitmap_set_bit (args_to_skip, i); - continue; - } - if (lat->type == IPA_CONST_VALUE) - bitmap_set_bit (args_to_skip, i); - } - } - for (cs = node->callers; cs; cs = next) - { - next = cs->next_caller; - if (!ipcp_node_is_clone (cs->caller) && ipcp_need_redirect_p (cs)) - { - if (dump_file) - fprintf (dump_file, "Redirecting edge %s/%i -> %s/%i " - "back to %s/%i.", - cgraph_node_name (cs->caller), cs->caller->uid, - cgraph_node_name (cs->callee), cs->callee->uid, - cgraph_node_name (orig_node), orig_node->uid); - cgraph_redirect_edge_callee (cs, orig_node); - } - } - } -} +/* After a specialized NEW_NODE version of ORIG_NODE has been created, update + their profile information to reflect this. */ -/* Update profiling info for versioned functions and the functions they were - versioned from. */ static void -ipcp_update_profiling (void) +update_profiling_info (struct cgraph_node *orig_node, + struct cgraph_node *new_node) { - struct cgraph_node *node, *orig_node; - gcov_type scale, scale_complement; struct cgraph_edge *cs; + struct caller_statistics stats; + gcov_type new_sum, orig_sum; + gcov_type remainder, orig_node_count = orig_node->count; + + if (orig_node_count == 0) + return; - for (node = cgraph_nodes; node; node = node->next) + init_caller_stats (&stats); + cgraph_for_node_and_aliases (orig_node, gather_caller_stats, &stats, false); + orig_sum = stats.count_sum; + init_caller_stats (&stats); + cgraph_for_node_and_aliases (new_node, gather_caller_stats, &stats, false); + new_sum = stats.count_sum; + + if (orig_node_count < orig_sum + new_sum) { - if (ipcp_node_is_clone (node)) - { - orig_node = ipcp_get_orig_node (node); - scale = ipcp_get_node_scale (orig_node); - node->count = orig_node->count * scale / REG_BR_PROB_BASE; - scale_complement = REG_BR_PROB_BASE - scale; - - gcc_assert (scale_complement >= 0); - orig_node->count = - orig_node->count * scale_complement / REG_BR_PROB_BASE; - for (cs = node->callees; cs; cs = cs->next_callee) - cs->count = cs->count * scale / REG_BR_PROB_BASE; - for (cs = orig_node->callees; cs; cs = cs->next_callee) - cs->count = cs->count * scale_complement / REG_BR_PROB_BASE; - } + if (dump_file) + fprintf (dump_file, " Problem: node %s/%i has too low count " + HOST_WIDE_INT_PRINT_DEC " while the sum of incoming " + "counts is " HOST_WIDE_INT_PRINT_DEC "\n", + cgraph_node_name (orig_node), orig_node->uid, + (HOST_WIDE_INT) orig_node_count, + (HOST_WIDE_INT) (orig_sum + new_sum)); + + orig_node_count = (orig_sum + new_sum) * 12 / 10; + if (dump_file) + fprintf (dump_file, " proceeding by pretending it was " + HOST_WIDE_INT_PRINT_DEC "\n", + (HOST_WIDE_INT) orig_node_count); } + + new_node->count = new_sum; + remainder = orig_node_count - new_sum; + orig_node->count = remainder; + + for (cs = new_node->callees; cs ; cs = cs->next_callee) + if (cs->frequency) + cs->count = cs->count * new_sum / orig_node_count; + else + cs->count = 0; + + for (cs = orig_node->callees; cs ; cs = cs->next_callee) + cs->count = cs->count * remainder / orig_node_count; + + if (dump_file) + dump_profile_updates (orig_node, new_node); } -/* If NODE was cloned, how much would program grow? */ -static long -ipcp_estimate_growth (struct cgraph_node *node) +/* Update the respective profile of specialized NEW_NODE and the original + ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM + have been redirected to the specialized version. */ + +static void +update_specialized_profile (struct cgraph_node *new_node, + struct cgraph_node *orig_node, + gcov_type redirected_sum) { struct cgraph_edge *cs; - int redirectable_node_callers = 0; - int removable_args = 0; - bool need_original - = !cgraph_will_be_removed_from_program_if_no_direct_calls (node); - VEC (tree, heap) *known_vals = NULL; - struct ipa_node_params *info; - int i, count; - int growth; + gcov_type new_node_count, orig_node_count = orig_node->count; - for (cs = node->callers; cs != NULL; cs = cs->next_caller) - if (cs->caller == node || !ipcp_need_redirect_p (cs)) - redirectable_node_callers++; - else - need_original = true; + if (dump_file) + fprintf (dump_file, " the sum of counts of redirected edges is " + HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) redirected_sum); + if (orig_node_count == 0) + return; - /* If we will be able to fully replace original node, we never increase - program size. */ - if (!need_original) - return 0; + gcc_assert (orig_node_count >= redirected_sum); - info = IPA_NODE_REF (node); - count = ipa_get_param_count (info); - VEC_safe_grow_cleared (tree, heap, known_vals, count); - if (node->local.can_change_signature) - for (i = 0; i < count; i++) - { - struct ipcp_lattice *lat = ipa_get_lattice (info, i); + new_node_count = new_node->count; + new_node->count += redirected_sum; + orig_node->count -= redirected_sum; - /* We can proactively remove obviously unused arguments. */ - if (!ipa_is_param_used (info, i)) - removable_args++; + for (cs = new_node->callees; cs ; cs = cs->next_callee) + if (cs->frequency) + cs->count += cs->count * redirected_sum / new_node_count; + else + cs->count = 0; - if (lat->type == IPA_CONST_VALUE) - { - removable_args++; - VEC_replace (tree, known_vals, i, lat->constant); - } - } + for (cs = orig_node->callees; cs ; cs = cs->next_callee) + { + gcov_type dec = cs->count * redirected_sum / orig_node_count; + if (dec < cs->count) + cs->count -= dec; + else + cs->count = 0; + } - /* We make just very simple estimate of savings for removal of operand from - call site. Precise cost is difficult to get, as our size metric counts - constants and moves as free. Generally we are looking for cases that - small function is called very many times. */ - estimate_ipcp_clone_size_and_time (node, known_vals, &growth, NULL); - VEC_free (tree, heap, known_vals); - growth = growth - - removable_args * redirectable_node_callers; - if (growth < 0) - return 0; - return growth; + if (dump_file) + dump_profile_updates (orig_node, new_node); } +/* Create a specialized version of NODE with known constants and types of + parameters in KNOWN_VALS and redirect all edges in CALLERS to it. */ -/* Estimate cost of cloning NODE. */ -static long -ipcp_estimate_cloning_cost (struct cgraph_node *node) +static struct cgraph_node * +create_specialized_node (struct cgraph_node *node, + VEC (tree, heap) *known_vals, + VEC (cgraph_edge_p,heap) *callers) { - int freq_sum = 1; - gcov_type count_sum = 1; - struct cgraph_edge *e; - int cost; + struct ipa_node_params *new_info, *info = IPA_NODE_REF (node); + VEC (ipa_replace_map_p,gc)* replace_trees = NULL; + struct cgraph_node *new_node; + int i, count = ipa_get_param_count (info); + bitmap args_to_skip; + + gcc_assert (!info->ipcp_orig_node); - cost = ipcp_estimate_growth (node) * 1000; - if (!cost) + if (node->local.can_change_signature) { - if (dump_file) - fprintf (dump_file, "Versioning of %s will save code size\n", - cgraph_node_name (node)); - return 0; + args_to_skip = BITMAP_GGC_ALLOC (); + for (i = 0; i < count; i++) + { + tree t = VEC_index (tree, known_vals, i); + + if ((t && TREE_CODE (t) != TREE_BINFO) + || !ipa_is_param_used (info, i)) + bitmap_set_bit (args_to_skip, i); + } } + else + args_to_skip = NULL; - for (e = node->callers; e; e = e->next_caller) - if (!bitmap_bit_p (dead_nodes, e->caller->uid) - && !ipcp_need_redirect_p (e)) - { - count_sum += e->count; - freq_sum += e->frequency + 1; - } + for (i = 0; i < count ; i++) + { + tree t = VEC_index (tree, known_vals, i); + if (t && TREE_CODE (t) != TREE_BINFO) + { + struct ipa_replace_map *replace_map; - if (max_count) - cost /= count_sum * 1000 / max_count + 1; - else - cost /= freq_sum * 1000 / REG_BR_PROB_BASE + 1; - if (dump_file) - fprintf (dump_file, "Cost of versioning %s is %i, (size: %i, freq: %i)\n", - cgraph_node_name (node), cost, inline_summary (node)->self_size, - freq_sum); - return cost + 1; + replace_map = get_replacement_map (t, ipa_get_param (info, i)); + if (replace_map) + VEC_safe_push (ipa_replace_map_p, gc, replace_trees, replace_map); + } + } + + new_node = cgraph_create_virtual_clone (node, callers, replace_trees, + args_to_skip, "constprop"); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " the new node is %s/%i.\n", + cgraph_node_name (new_node), new_node->uid); + gcc_checking_assert (ipa_node_params_vector + && (VEC_length (ipa_node_params_t, + ipa_node_params_vector) + > (unsigned) cgraph_max_uid)); + update_profiling_info (node, new_node); + new_info = IPA_NODE_REF (new_node); + new_info->ipcp_orig_node = node; + new_info->known_vals = known_vals; + + ipcp_discover_new_direct_edges (new_node, known_vals); + + VEC_free (cgraph_edge_p, heap, callers); + return new_node; } -/* Walk indirect calls of NODE and if any polymorphic can be turned into a - direct one now, do so. */ +/* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in + KNOWN_VALS with constants and types that are also known for all of the + CALLERS. */ static void -ipcp_process_devirtualization_opportunities (struct cgraph_node *node) +find_more_values_for_callers_subset (struct cgraph_node *node, + VEC (tree, heap) *known_vals, + VEC (cgraph_edge_p,heap) *callers) { struct ipa_node_params *info = IPA_NODE_REF (node); - struct cgraph_edge *ie, *next_ie; + int i, count = ipa_get_param_count (info); - for (ie = node->indirect_calls; ie; ie = next_ie) + for (i = 0; i < count ; i++) { - int param_index; - HOST_WIDE_INT token, anc_offset; - tree target, delta, otr_type; - struct ipcp_lattice *lat; + struct cgraph_edge *cs; + tree newval = NULL_TREE; + int j; - next_ie = ie->next_callee; - if (!ie->indirect_info->polymorphic) - continue; - param_index = ie->indirect_info->param_index; - if (param_index == -1) + if (ipa_get_lattice (info, i)->bottom + || VEC_index (tree, known_vals, i)) continue; - lat = ipa_get_lattice (info, param_index); - token = ie->indirect_info->otr_token; - anc_offset = ie->indirect_info->anc_offset; - otr_type = ie->indirect_info->otr_type; - target = NULL_TREE; - if (lat->type == IPA_CONST_VALUE) + FOR_EACH_VEC_ELT (cgraph_edge_p, callers, j, cs) { - tree binfo = gimple_extract_devirt_binfo_from_cst (lat->constant); - if (!binfo) - continue; - binfo = get_binfo_at_offset (binfo, anc_offset, otr_type); - if (!binfo) - continue; - target = gimple_get_virt_method_for_binfo (token, binfo, &delta); - } - else - { - int types_count, j; + struct ipa_jump_func *jump_func; + tree t; - if (ipa_param_cannot_devirtualize_p (info, param_index) - || ipa_param_types_vec_empty (info, param_index)) - continue; + jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i); - types_count = VEC_length (tree, info->params[param_index].types); - for (j = 0; j < types_count; j++) + t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func); + if (!t + || (newval + && !values_equal_for_ipcp_p (t, newval))) { - tree binfo = VEC_index (tree, info->params[param_index].types, j); - tree d, t; - - binfo = get_binfo_at_offset (binfo, anc_offset, otr_type); - if (!binfo) - { - target = NULL_TREE; - break; - } - - t = gimple_get_virt_method_for_binfo (token, binfo, &d); - if (!t) - { - target = NULL_TREE; - break; - } - else if (!target) - { - target = t; - delta = d; - } - else if (target != t || !tree_int_cst_equal (delta, d)) - { - target = NULL_TREE; - break; - } + newval = NULL_TREE; + break; } + else + newval = t; } - if (target) - ipa_make_edge_direct_to_target (ie, target, delta); - } -} - -/* Return number of live constant parameters. */ -static int -ipcp_const_param_count (struct cgraph_node *node) -{ - int const_param = 0; - struct ipa_node_params *info = IPA_NODE_REF (node); - int count = ipa_get_param_count (info); - int i; + if (newval) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " adding an extra known value "); + print_ipcp_constant_value (dump_file, newval); + fprintf (dump_file, " for parameter "); + print_generic_expr (dump_file, ipa_get_param (info, i), 0); + fprintf (dump_file, "\n"); + } - for (i = 0; i < count; i++) - { - struct ipcp_lattice *lat = ipa_get_lattice (info, i); - if ((ipcp_lat_is_insertable (lat) - /* Do not count obviously unused arguments. */ - && ipa_is_param_used (info, i)) - || (!ipa_param_cannot_devirtualize_p (info, i) - && !ipa_param_types_vec_empty (info, i))) - const_param++; + VEC_replace (tree, known_vals, i, newval); + } } - return const_param; } -/* Given that a formal parameter of NODE given by INDEX is known to be constant - CST, try to find any indirect edges that can be made direct and make them - so. Note that INDEX is the number the parameter at the time of analyzing - parameter uses and parameter removals should not be considered for it. (In - fact, the parameter itself has just been removed.) */ +/* Given an original NODE and a VAL for which we have already created a + specialized clone, look whether there are incoming edges that still lead + into the old node but now also bring the requested value and also conform to + all other criteria such that they can be redirected the the special node. + This function can therefore redirect the final edge in a SCC. */ static void -ipcp_discover_new_direct_edges (struct cgraph_node *node, int index, tree cst) +perhaps_add_new_callers (struct cgraph_node *node, struct ipcp_value *val) { - struct cgraph_edge *ie, *next_ie; + struct ipa_node_params *dest_info = IPA_NODE_REF (val->spec_node); + struct ipcp_value_source *src; + int count = ipa_get_param_count (dest_info); + gcov_type redirected_sum = 0; - for (ie = node->indirect_calls; ie; ie = next_ie) + for (src = val->sources; src; src = src->next) { - struct cgraph_indirect_call_info *ici = ie->indirect_info; + struct cgraph_edge *cs = src->cs; + while (cs) + { + enum availability availability; + bool insufficient = false; - next_ie = ie->next_callee; - if (ici->param_index != index - || ici->polymorphic) - continue; + if (cgraph_function_node (cs->callee, &availability) == node + && availability > AVAIL_OVERWRITABLE + && cgraph_edge_brings_value_p (cs, src)) + { + struct ipa_node_params *caller_info; + struct ipa_edge_args *args; + int i; + + caller_info = IPA_NODE_REF (cs->caller); + args = IPA_EDGE_REF (cs); + for (i = 0; i < count; i++) + { + struct ipa_jump_func *jump_func; + tree val, t; + + val = VEC_index (tree, dest_info->known_vals, i); + if (!val) + continue; + + jump_func = ipa_get_ith_jump_func (args, i); + t = ipa_value_from_jfunc (caller_info, jump_func); + if (!t || !values_equal_for_ipcp_p (val, t)) + { + insufficient = true; + break; + } + } - ipa_make_edge_direct_to_target (ie, cst, NULL_TREE); + if (!insufficient) + { + if (dump_file) + fprintf (dump_file, " - adding an extra caller %s/%i" + " of %s/%i\n", + cgraph_node_name (cs->caller), cs->caller->uid, + cgraph_node_name (val->spec_node), + val->spec_node->uid); + + cgraph_redirect_edge_callee (cs, val->spec_node); + redirected_sum += cs->count; + } + } + cs = get_next_cgraph_edge_clone (cs); + } } + + if (redirected_sum) + update_specialized_profile (val->spec_node, node, redirected_sum); } -/* Propagate the constant parameters found by ipcp_iterate_stage() - to the function's code. */ +/* Copy KNOWN_BINFOS to KNOWN_VALS. */ + static void -ipcp_insert_stage (void) +move_binfos_to_values (VEC (tree, heap) *known_vals, + VEC (tree, heap) *known_binfos) { - struct cgraph_node *node, *node1 = NULL; + tree t; int i; - VEC (cgraph_edge_p, heap) * redirect_callers; - VEC (ipa_replace_map_p,gc)* replace_trees; - int count; - tree parm_tree; - struct ipa_replace_map *replace_param; - fibheap_t heap; - long overall_size = 0, new_size = 0; - long max_new_size; - ipa_check_create_node_params (); - ipa_check_create_edge_args (); - if (dump_file) - fprintf (dump_file, "\nIPA insert stage:\n\n"); + for (i = 0; VEC_iterate (tree, known_binfos, i, t); i++) + if (t) + VEC_replace (tree, known_vals, i, t); +} - dead_nodes = BITMAP_ALLOC (NULL); - FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) - { - if (node->count > max_count) - max_count = node->count; - overall_size += inline_summary (node)->self_size; - } +/* Decide whether and what specialized clones of NODE should be created. */ - max_new_size = overall_size; - if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS)) - max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS); - max_new_size = max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1; - - /* First collect all functions we proved to have constant arguments to - heap. */ - heap = fibheap_new (); - for (node = cgraph_nodes; node; node = node->next) - { - struct ipa_node_params *info; - /* Propagation of the constant is forbidden in certain conditions. */ - if (!node->analyzed || !ipcp_node_modifiable_p (node)) - continue; - info = IPA_NODE_REF (node); - if (ipa_is_called_with_var_arguments (info)) - continue; - if (ipcp_const_param_count (node)) - node->aux = fibheap_insert (heap, ipcp_estimate_cloning_cost (node), - node); - } - - /* Now clone in priority order until code size growth limits are met or - heap is emptied. */ - while (!fibheap_empty (heap)) - { - struct ipa_node_params *info; - int growth = 0; - bitmap args_to_skip; - struct cgraph_edge *cs; +static bool +decide_whether_version_node (struct cgraph_node *node) +{ + struct ipa_node_params *info = IPA_NODE_REF (node); + int i, count = ipa_get_param_count (info); + VEC (tree, heap) *known_csts, *known_binfos; + bool ret = false; - node = (struct cgraph_node *)fibheap_extract_min (heap); - node->aux = NULL; - if (dump_file) - fprintf (dump_file, "considering function %s\n", - cgraph_node_name (node)); + if (count == 0) + return false; - growth = ipcp_estimate_growth (node); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "\nEvaluating opportunities for %s/%i.\n", + cgraph_node_name (node), node->uid); - if (new_size + growth > max_new_size) - break; - if (growth - && cgraph_optimize_for_size_p (node)) - { - if (dump_file) - fprintf (dump_file, "Not versioning, cold code would grow"); - continue; - } + gather_context_independent_values (info, &known_csts, &known_binfos, + NULL); - info = IPA_NODE_REF (node); - count = ipa_get_param_count (info); + for (i = 0; i < count ; i++) + { + struct ipcp_lattice *lat = ipa_get_lattice (info, i); + struct ipcp_value *val; - replace_trees = VEC_alloc (ipa_replace_map_p, gc, 1); + if (lat->bottom + || VEC_index (tree, known_csts, i) + || VEC_index (tree, known_binfos, i)) + continue; - if (node->local.can_change_signature) - args_to_skip = BITMAP_GGC_ALLOC (); - else - args_to_skip = NULL; - for (i = 0; i < count; i++) + for (val = lat->values; val; val = val->next) { - struct ipcp_lattice *lat = ipa_get_lattice (info, i); - parm_tree = ipa_get_param (info, i); + int freq_sum, caller_count; + gcov_type count_sum; + VEC (cgraph_edge_p, heap) *callers; + VEC (tree, heap) *kv; - /* We can proactively remove obviously unused arguments. */ - if (!ipa_is_param_used (info, i)) + if (val->spec_node) + { + perhaps_add_new_callers (node, val); + continue; + } + else if (val->local_size_cost + overall_size > max_new_size) { - if (args_to_skip) - bitmap_set_bit (args_to_skip, i); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " Ignoring candidate value because " + "max_new_size would be reached with %li.\n", + val->local_size_cost + overall_size); continue; } + else if (!get_info_about_necessary_edges (val, &freq_sum, &count_sum, + &caller_count)) + continue; - if (lat->type == IPA_CONST_VALUE) + if (dump_file && (dump_flags & TDF_DETAILS)) { - replace_param = - ipcp_create_replace_map (parm_tree, lat); - if (replace_param == NULL) - break; - VEC_safe_push (ipa_replace_map_p, gc, replace_trees, replace_param); - if (args_to_skip) - bitmap_set_bit (args_to_skip, i); + fprintf (dump_file, " - considering value "); + print_ipcp_constant_value (dump_file, val->value); + fprintf (dump_file, " for parameter "); + print_generic_expr (dump_file, ipa_get_param (info, i), 0); + fprintf (dump_file, " (caller_count: %i)\n", caller_count); } - } - if (i < count) - { + + + if (!good_cloning_opportunity_p (node, val->local_time_benefit, + freq_sum, count_sum, + val->local_size_cost) + && !good_cloning_opportunity_p (node, + val->local_time_benefit + + val->prop_time_benefit, + freq_sum, count_sum, + val->local_size_cost + + val->prop_size_cost)) + continue; + if (dump_file) - fprintf (dump_file, "Not versioning, some parameters couldn't be replaced"); - continue; + fprintf (dump_file, " Creating a specialized node of %s/%i.\n", + cgraph_node_name (node), node->uid); + + callers = gather_edges_for_value (val, caller_count); + kv = VEC_copy (tree, heap, known_csts); + move_binfos_to_values (kv, known_binfos); + VEC_replace (tree, kv, i, val->value); + find_more_values_for_callers_subset (node, kv, callers); + val->spec_node = create_specialized_node (node, kv, callers); + overall_size += val->local_size_cost; + info = IPA_NODE_REF (node); + + /* TODO: If for some lattice there is only one other known value + left, make a special node for it too. */ + ret = true; + + VEC_replace (tree, kv, i, val->value); } + } - new_size += growth; + if (info->clone_for_all_contexts) + { + VEC (cgraph_edge_p, heap) *callers; - /* Look if original function becomes dead after cloning. */ - for (cs = node->callers; cs != NULL; cs = cs->next_caller) - if (cs->caller == node || ipcp_need_redirect_p (cs)) - break; - if (!cs && cgraph_will_be_removed_from_program_if_no_direct_calls (node)) - bitmap_set_bit (dead_nodes, node->uid); + if (dump_file) + fprintf (dump_file, " - Creating a specialized node of %s/%i " + "for all known contexts.\n", cgraph_node_name (node), + node->uid); - redirect_callers = collect_callers_of_node (node); + callers = collect_callers_of_node (node); + move_binfos_to_values (known_csts, known_binfos); + create_specialized_node (node, known_csts, callers); + info = IPA_NODE_REF (node); + info->clone_for_all_contexts = false; + ret = true; + } + else + VEC_free (tree, heap, known_csts); - /* Redirecting all the callers of the node to the - new versioned node. */ - node1 = - cgraph_create_virtual_clone (node, redirect_callers, replace_trees, - args_to_skip, "constprop"); - args_to_skip = NULL; - VEC_free (cgraph_edge_p, heap, redirect_callers); - replace_trees = NULL; + VEC_free (tree, heap, known_binfos); + return ret; +} - if (node1 == NULL) - continue; - ipcp_process_devirtualization_opportunities (node1); +/* Transitively mark all callees of NODE within the same SCC as not dead. */ - if (dump_file) - fprintf (dump_file, "versioned function %s with growth %i, overall %i\n", - cgraph_node_name (node), (int)growth, (int)new_size); - ipcp_init_cloned_node (node, node1); +static void +spread_undeadness (struct cgraph_node *node) +{ + struct cgraph_edge *cs; - info = IPA_NODE_REF (node); - for (i = 0; i < count; i++) - { - struct ipcp_lattice *lat = ipa_get_lattice (info, i); - if (lat->type == IPA_CONST_VALUE) - ipcp_discover_new_direct_edges (node1, i, lat->constant); - } + for (cs = node->callees; cs; cs = cs->next_callee) + if (edge_within_scc (cs)) + { + struct cgraph_node *callee; + struct ipa_node_params *info; - if (dump_file) - dump_function_to_file (node1->decl, dump_file, dump_flags); + callee = cgraph_function_node (cs->callee, NULL); + info = IPA_NODE_REF (callee); - for (cs = node->callees; cs; cs = cs->next_callee) - { - struct cgraph_node *callee = cgraph_function_or_thunk_node (cs->callee, NULL); - if (callee->aux) - { - fibheap_delete_node (heap, (fibnode_t) callee->aux); - callee->aux = fibheap_insert (heap, - ipcp_estimate_cloning_cost (callee), - callee); - } - } + if (info->node_dead) + { + info->node_dead = 0; + spread_undeadness (callee); + } + } +} + +/* Return true if NODE has a caller from outside of its SCC that is not + dead. Worker callback for cgraph_for_node_and_aliases. */ + +static bool +has_undead_caller_from_outside_scc_p (struct cgraph_node *node, + void *data ATTRIBUTE_UNUSED) +{ + struct cgraph_edge *cs; + + for (cs = node->callers; cs; cs = cs->next_caller) + if (cs->caller->thunk.thunk_p + && cgraph_for_node_and_aliases (cs->caller, + has_undead_caller_from_outside_scc_p, + NULL, true)) + return true; + else if (!edge_within_scc (cs) + && !IPA_NODE_REF (cs->caller)->node_dead) + return true; + return false; +} + + +/* Identify nodes within the same SCC as NODE which are no longer needed + because of new clones and will be removed as unreachable. */ + +static void +identify_dead_nodes (struct cgraph_node *node) +{ + struct cgraph_node *v; + for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle) + if (cgraph_will_be_removed_from_program_if_no_direct_calls (v) + && !cgraph_for_node_and_aliases (v, + has_undead_caller_from_outside_scc_p, + NULL, true)) + IPA_NODE_REF (v)->node_dead = 1; + + for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle) + if (!IPA_NODE_REF (v)->node_dead) + spread_undeadness (v); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle) + if (IPA_NODE_REF (v)->node_dead) + fprintf (dump_file, " Marking node as dead: %s/%i.\n", + cgraph_node_name (v), v->uid); } +} - while (!fibheap_empty (heap)) +/* The decision stage. Iterate over the topological order of call graph nodes + TOPO and make specialized clones if deemed beneficial. */ + +static void +ipcp_decision_stage (struct topo_info *topo) +{ + int i; + + if (dump_file) + fprintf (dump_file, "\nIPA decision stage:\n\n"); + + for (i = topo->nnodes - 1; i >= 0; i--) { - if (dump_file) - fprintf (dump_file, "skipping function %s\n", - cgraph_node_name (node)); - node = (struct cgraph_node *) fibheap_extract_min (heap); - node->aux = NULL; + struct cgraph_node *node = topo->order[i]; + bool change = false, iterate = true; + + while (iterate) + { + struct cgraph_node *v; + iterate = false; + for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle) + if (cgraph_function_with_gimple_body_p (v) + && ipcp_versionable_function_p (v)) + iterate |= decide_whether_version_node (v); + + change |= iterate; + } + if (change) + identify_dead_nodes (node); } - fibheap_delete (heap); - BITMAP_FREE (dead_nodes); - ipcp_update_callgraph (); - ipcp_update_profiling (); } /* The IPCP driver. */ + static unsigned int ipcp_driver (void) { + struct cgraph_2edge_hook_list *edge_duplication_hook_holder; + struct topo_info topo; + cgraph_remove_unreachable_nodes (true,dump_file); + ipa_check_create_node_params (); + ipa_check_create_edge_args (); + grow_next_edge_clone_vector (); + edge_duplication_hook_holder = + cgraph_add_edge_duplication_hook (&ipcp_edge_duplication_hook, NULL); + ipcp_values_pool = create_alloc_pool ("IPA-CP values", + sizeof (struct ipcp_value), 32); + ipcp_sources_pool = create_alloc_pool ("IPA-CP value sources", + sizeof (struct ipcp_value_source), 64); if (dump_file) { fprintf (dump_file, "\nIPA structures before propagation:\n"); @@ -1501,18 +2434,18 @@ ipcp_driver (void) ipa_print_all_params (dump_file); ipa_print_all_jump_functions (dump_file); } - ipa_check_create_node_params (); - ipa_check_create_edge_args (); - /* 2. Do the interprocedural propagation. */ - ipcp_iterate_stage (); - /* 3. Insert the constants found to the functions. */ - ipcp_insert_stage (); - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "\nProfiling info after insert stage:\n"); - ipcp_print_profile_data (dump_file); - } + + /* Topological sort. */ + build_toporder_info (&topo); + /* Do the interprocedural propagation. */ + ipcp_propagate_stage (&topo); + /* Decide what constant propagation and cloning should be performed. */ + ipcp_decision_stage (&topo); + /* Free all IPCP structures. */ + free_toporder_info (&topo); + VEC_free (cgraph_edge_p, heap, next_edge_clone); + cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder); ipa_free_all_structures_after_ipa_cp (); if (dump_file) fprintf (dump_file, "\nIPA constant propagation end\n"); @@ -1545,6 +2478,7 @@ ipcp_generate_summary (void) } /* Write ipcp summary for nodes in SET. */ + static void ipcp_write_summary (cgraph_node_set set, varpool_node_set vset ATTRIBUTE_UNUSED) @@ -1553,6 +2487,7 @@ ipcp_write_summary (cgraph_node_set set, } /* Read ipcp summary. */ + static void ipcp_read_summary (void) { @@ -1560,6 +2495,7 @@ ipcp_read_summary (void) } /* Gate for IPCP optimization. */ + static bool cgraph_gate_cp (void) { diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c index aec1920c62e..def34c3e6a1 100644 --- a/gcc/ipa-prop.c +++ b/gcc/ipa-prop.c @@ -65,65 +65,6 @@ static struct cgraph_2edge_hook_list *edge_duplication_hook_holder; static struct cgraph_2node_hook_list *node_duplication_hook_holder; static struct cgraph_node_hook_list *function_insertion_hook_holder; -/* Add cgraph NODE described by INFO to the worklist WL regardless of whether - it is in one or not. It should almost never be used directly, as opposed to - ipa_push_func_to_list. */ - -void -ipa_push_func_to_list_1 (struct ipa_func_list **wl, - struct cgraph_node *node, - struct ipa_node_params *info) -{ - struct ipa_func_list *temp; - - info->node_enqueued = 1; - temp = XCNEW (struct ipa_func_list); - temp->node = node; - temp->next = *wl; - *wl = temp; -} - -/* Initialize worklist to contain all functions. */ - -struct ipa_func_list * -ipa_init_func_list (void) -{ - struct cgraph_node *node; - struct ipa_func_list * wl; - - wl = NULL; - for (node = cgraph_nodes; node; node = node->next) - if (node->analyzed && !node->alias) - { - struct ipa_node_params *info = IPA_NODE_REF (node); - /* Unreachable nodes should have been eliminated before ipcp and - inlining. */ - gcc_assert (node->needed || node->reachable); - ipa_push_func_to_list_1 (&wl, node, info); - } - - return wl; -} - -/* Remove a function from the worklist WL and return it. */ - -struct cgraph_node * -ipa_pop_func_from_list (struct ipa_func_list **wl) -{ - struct ipa_node_params *info; - struct ipa_func_list *first; - struct cgraph_node *node; - - first = *wl; - *wl = (*wl)->next; - node = first->node; - free (first); - - info = IPA_NODE_REF (node); - info->node_enqueued = 0; - return node; -} - /* Return index of the formal whose tree is PTREE in function which corresponds to INFO. */ @@ -134,7 +75,7 @@ ipa_get_param_decl_index (struct ipa_node_params *info, tree ptree) count = ipa_get_param_count (info); for (i = 0; i < count; i++) - if (ipa_get_param(info, i) == ptree) + if (ipa_get_param (info, i) == ptree) return i; return -1; @@ -157,7 +98,8 @@ ipa_populate_param_decls (struct cgraph_node *node, param_num = 0; for (parm = fnargs; parm; parm = DECL_CHAIN (parm)) { - info->params[param_num].decl = parm; + VEC_index (ipa_param_descriptor_t, + info->descriptors, param_num)->decl = parm; param_num++; } } @@ -165,7 +107,7 @@ ipa_populate_param_decls (struct cgraph_node *node, /* Return how many formal parameters FNDECL has. */ static inline int -count_formal_params_1 (tree fndecl) +count_formal_params (tree fndecl) { tree parm; int count = 0; @@ -176,19 +118,6 @@ count_formal_params_1 (tree fndecl) return count; } -/* Count number of formal parameters in NOTE. Store the result to the - appropriate field of INFO. */ - -static void -ipa_count_formal_params (struct cgraph_node *node, - struct ipa_node_params *info) -{ - int param_num; - - param_num = count_formal_params_1 (node->decl); - ipa_set_param_count (info, param_num); -} - /* Initialize the ipa_node_params structure associated with NODE by counting the function parameters, creating the descriptors and populating their param_decls. */ @@ -198,12 +127,17 @@ ipa_initialize_node_params (struct cgraph_node *node) { struct ipa_node_params *info = IPA_NODE_REF (node); - if (!info->params) + if (!info->descriptors) { - ipa_count_formal_params (node, info); - info->params = XCNEWVEC (struct ipa_param_descriptor, - ipa_get_param_count (info)); - ipa_populate_param_decls (node, info); + int param_count; + + param_count = count_formal_params (node->decl); + if (param_count) + { + VEC_safe_grow_cleared (ipa_param_descriptor_t, heap, + info->descriptors, param_count); + ipa_populate_param_decls (node, info); + } } } @@ -1497,7 +1431,7 @@ visit_ref_for_mod_analysis (gimple stmt ATTRIBUTE_UNUSED, { int index = ipa_get_param_decl_index (info, op); gcc_assert (index >= 0); - info->params[index].used = true; + ipa_set_param_used (info, index, true); } return false; @@ -1529,7 +1463,7 @@ ipa_analyze_params_uses (struct cgraph_node *node, the flag during modification analysis. */ if (is_gimple_reg (parm) && gimple_default_def (DECL_STRUCT_FUNCTION (node->decl), parm)) - info->params[i].used = true; + ipa_set_param_used (info, i, true); } func = DECL_STRUCT_FUNCTION (decl); @@ -1936,8 +1870,11 @@ ipa_free_all_edge_args (void) void ipa_free_node_params_substructures (struct ipa_node_params *info) { - free (info->params); - + VEC_free (ipa_param_descriptor_t, heap, info->descriptors); + free (info->lattices); + /* Lattice values and their sources are deallocated with their alocation + pool. */ + VEC_free (tree, heap, info->known_vals); memset (info, 0, sizeof (*info)); } @@ -1980,22 +1917,6 @@ ipa_node_removal_hook (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED) ipa_free_node_params_substructures (IPA_NODE_REF (node)); } -/* Helper function to duplicate an array of size N that is at SRC and store a - pointer to it to DST. Nothing is done if SRC is NULL. */ - -static void * -duplicate_array (void *src, size_t n) -{ - void *p; - - if (!src) - return NULL; - - p = xmalloc (n); - memcpy (p, src, n); - return p; -} - static struct ipa_jump_func * duplicate_ipa_jump_func_array (const struct ipa_jump_func * src, size_t n) { @@ -2040,22 +1961,15 @@ ipa_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst, ATTRIBUTE_UNUSED void *data) { struct ipa_node_params *old_info, *new_info; - int param_count, i; ipa_check_create_node_params (); old_info = IPA_NODE_REF (src); new_info = IPA_NODE_REF (dst); - param_count = ipa_get_param_count (old_info); - ipa_set_param_count (new_info, param_count); - new_info->params = (struct ipa_param_descriptor *) - duplicate_array (old_info->params, - sizeof (struct ipa_param_descriptor) * param_count); - for (i = 0; i < param_count; i++) - new_info->params[i].types = VEC_copy (tree, heap, - old_info->params[i].types); + new_info->descriptors = VEC_copy (ipa_param_descriptor_t, heap, + old_info->descriptors); + new_info->lattices = NULL; new_info->ipcp_orig_node = old_info->ipcp_orig_node; - new_info->count_scale = old_info->count_scale; new_info->called_with_var_arguments = old_info->called_with_var_arguments; new_info->uses_analysis_done = old_info->uses_analysis_done; @@ -2127,6 +2041,8 @@ ipa_free_all_structures_after_ipa_cp (void) { ipa_free_all_edge_args (); ipa_free_all_node_params (); + free_alloc_pool (ipcp_sources_pool); + free_alloc_pool (ipcp_values_pool); ipa_unregister_cgraph_hooks (); } } @@ -2142,6 +2058,10 @@ ipa_free_all_structures_after_iinln (void) ipa_free_all_edge_args (); ipa_free_all_node_params (); ipa_unregister_cgraph_hooks (); + if (ipcp_sources_pool) + free_alloc_pool (ipcp_sources_pool); + if (ipcp_values_pool) + free_alloc_pool (ipcp_values_pool); } /* Print ipa_tree_map data structures of all functions in the @@ -2196,7 +2116,7 @@ ipa_get_vector_of_formal_parms (tree fndecl) int count; tree parm; - count = count_formal_params_1 (fndecl); + count = count_formal_params (fndecl); args = VEC_alloc (tree, heap, count); for (parm = DECL_ARGUMENTS (fndecl); parm; parm = DECL_CHAIN (parm)) VEC_quick_push (tree, args, parm); @@ -2859,7 +2779,7 @@ ipa_write_node_info (struct output_block *ob, struct cgraph_node *node) gcc_assert (!info->node_enqueued); gcc_assert (!info->ipcp_orig_node); for (j = 0; j < ipa_get_param_count (info); j++) - bp_pack_value (&bp, info->params[j].used, 1); + bp_pack_value (&bp, ipa_is_param_used (info, j), 1); lto_output_bitpack (&bp); for (e = node->callees; e; e = e->next_callee) { @@ -2900,7 +2820,7 @@ ipa_read_node_info (struct lto_input_block *ib, struct cgraph_node *node, info->uses_analysis_done = true; info->node_enqueued = false; for (k = 0; k < ipa_get_param_count (info); k++) - info->params[k].used = bp_unpack_value (&bp, 1); + ipa_set_param_used (info, k, bp_unpack_value (&bp, 1)); for (e = node->callees; e; e = e->next_callee) { struct ipa_edge_args *args = IPA_EDGE_REF (e); @@ -3064,82 +2984,3 @@ ipa_update_after_lto_read (void) } } -/* Given the jump function JFUNC, compute the lattice LAT that describes the - value coming down the callsite. INFO describes the caller node so that - pass-through jump functions can be evaluated. */ - -void -ipa_lattice_from_jfunc (struct ipa_node_params *info, struct ipcp_lattice *lat, - struct ipa_jump_func *jfunc) -{ - if (jfunc->type == IPA_JF_CONST) - { - lat->type = IPA_CONST_VALUE; - lat->constant = jfunc->value.constant; - } - else if (jfunc->type == IPA_JF_PASS_THROUGH) - { - struct ipcp_lattice *caller_lat; - tree cst; - - caller_lat = ipa_get_lattice (info, jfunc->value.pass_through.formal_id); - lat->type = caller_lat->type; - if (caller_lat->type != IPA_CONST_VALUE) - return; - cst = caller_lat->constant; - - if (jfunc->value.pass_through.operation != NOP_EXPR) - { - tree restype; - if (TREE_CODE_CLASS (jfunc->value.pass_through.operation) - == tcc_comparison) - restype = boolean_type_node; - else - restype = TREE_TYPE (cst); - cst = fold_binary (jfunc->value.pass_through.operation, - restype, cst, jfunc->value.pass_through.operand); - } - if (!cst || !is_gimple_ip_invariant (cst)) - lat->type = IPA_BOTTOM; - lat->constant = cst; - } - else if (jfunc->type == IPA_JF_ANCESTOR) - { - struct ipcp_lattice *caller_lat; - tree t; - - caller_lat = ipa_get_lattice (info, jfunc->value.ancestor.formal_id); - lat->type = caller_lat->type; - if (caller_lat->type != IPA_CONST_VALUE) - return; - if (TREE_CODE (caller_lat->constant) != ADDR_EXPR) - { - /* This can happen when the constant is a NULL pointer. */ - lat->type = IPA_BOTTOM; - return; - } - t = TREE_OPERAND (caller_lat->constant, 0); - t = build_ref_for_offset (EXPR_LOCATION (t), t, - jfunc->value.ancestor.offset, - jfunc->value.ancestor.type, NULL, false); - lat->constant = build_fold_addr_expr (t); - } - else - lat->type = IPA_BOTTOM; -} - -/* Determine whether JFUNC evaluates to a constant and if so, return it. - Otherwise return NULL. INFO describes the caller node so that pass-through - jump functions can be evaluated. */ - -tree -ipa_cst_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc) -{ - struct ipcp_lattice lat; - - ipa_lattice_from_jfunc (info, &lat, jfunc); - if (lat.type == IPA_CONST_VALUE) - return lat.constant; - else - return NULL_TREE; -} diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h index 89a17f4b9d0..994e4ac146d 100644 --- a/gcc/ipa-prop.h +++ b/gcc/ipa-prop.h @@ -25,6 +25,7 @@ along with GCC; see the file COPYING3. If not see #include "vec.h" #include "cgraph.h" #include "gimple.h" +#include "alloc-pool.h" /* The following definitions and interfaces are used by interprocedural analyses or parameters. */ @@ -32,7 +33,10 @@ along with GCC; see the file COPYING3. If not see /* ipa-prop.c stuff (ipa-cp, indirect inlining): */ /* A jump function for a callsite represents the values passed as actual - arguments of the callsite. There are three main types of values : + arguments of the callsite. They were originally proposed in a paper called + "Interprocedural Constant Propagation", by David Callahan, Keith D Cooper, + Ken Kennedy, Linda Torczon in Comp86, pg 152-161. There are three main + types of values : Pass-through - the caller's formal parameter is passed as an actual argument, possibly one simple operation performed on it. @@ -41,7 +45,8 @@ along with GCC; see the file COPYING3. If not see Unknown - neither of the above. IPA_JF_CONST_MEMBER_PTR stands for C++ member pointers, it is a special - constant in this regard. Other constants are represented with IPA_JF_CONST. + constant in this regard because it is in fact a structure consisting of two + values. Other constants are represented with IPA_JF_CONST. IPA_JF_ANCESTOR is a special pass-through jump function, which means that the result is an address of a part of the object pointed to by the formal @@ -130,95 +135,65 @@ struct GTY (()) ipa_jump_func } GTY ((desc ("%1.type"))) value; }; -/* All formal parameters in the program have a lattice associated with it - computed by the interprocedural stage of IPCP. - There are three main values of the lattice: - IPA_TOP - unknown, - IPA_BOTTOM - variable, - IPA_CONST_VALUE - simple scalar constant, - - We also use this type to propagate types accross the call graph for the - purpose of devirtualization. In that case, IPA_CONST_VALUE denotes a known - type, rather than a constant. */ -enum ipa_lattice_type -{ - IPA_BOTTOM, - IPA_CONST_VALUE, - IPA_TOP -}; +/* Summary describing a single formal parameter. */ -/* All formal parameters in the program have a cval computed by - the interprocedural stage of IPCP. See enum ipa_lattice_type for - the various types of lattices supported */ -struct ipcp_lattice -{ - enum ipa_lattice_type type; - tree constant; -}; - -/* Structure describing a single formal parameter. */ struct ipa_param_descriptor { - /* IPA-CP lattice. */ - struct ipcp_lattice ipcp_lattice; /* PARAM_DECL of this parameter. */ tree decl; - /* Vector of BINFOs of types that this argument might encounter. NULL - basically means a top value, bottom is marked by the cannot_devirtualize - flag below.*/ - VEC (tree, heap) *types; /* The parameter is used. */ unsigned used : 1; - /* Set when parameter type cannot be used for devirtualization. */ - unsigned cannot_devirtualize : 1; }; +typedef struct ipa_param_descriptor ipa_param_descriptor_t; +DEF_VEC_O (ipa_param_descriptor_t); +DEF_VEC_ALLOC_O (ipa_param_descriptor_t, heap); +struct ipcp_lattice; + /* ipa_node_params stores information related to formal parameters of functions and some other information for interprocedural passes that operate on parameters (such as ipa-cp). */ + struct ipa_node_params { - /* Number of formal parameters of this function. When set to 0, this - function's parameters would not be analyzed by IPA CP. */ - int param_count; + /* Information about individual formal parameters that are gathered when + summaries are generated. */ + VEC (ipa_param_descriptor_t, heap) *descriptors; + /* Pointer to an array of structures describing individual formal + parameters. */ + struct ipcp_lattice *lattices; + /* Only for versioned nodes this field would not be NULL, + it points to the node that IPA cp cloned from. */ + struct cgraph_node *ipcp_orig_node; + /* If this node is an ipa-cp clone, these are the known values that describe + what it has been specialized for. */ + VEC (tree, heap) *known_vals; /* Whether this function is called with variable number of actual arguments. */ unsigned called_with_var_arguments : 1; + /* Set when it is possible to create specialized versions of this node. */ + unsigned node_versionable : 1; /* Whether the param uses analysis has already been performed. */ unsigned uses_analysis_done : 1; - /* Whether the function is enqueued in an ipa_func_list. */ + /* Whether the function is enqueued in ipa-cp propagation stack. */ unsigned node_enqueued : 1; - /* Pointer to an array of structures describing individual formal - parameters. */ - struct ipa_param_descriptor *params; - /* Only for versioned nodes this field would not be NULL, - it points to the node that IPA cp cloned from. */ - struct cgraph_node *ipcp_orig_node; - /* Meaningful only for original functions. Expresses the - ratio between the direct calls and sum of all invocations of - this function (given by profiling info). It is used to calculate - the profiling information of the original function and the versioned - one. */ - gcov_type count_scale; + /* Whether we should create a specialized version based on values that are + known to be constant in all contexts. */ + unsigned clone_for_all_contexts : 1; + /* Node has been completely replaced by clones and will be removed after + ipa-cp is finished. */ + unsigned node_dead : 1; }; /* ipa_node_params access functions. Please use these to access fields that are or will be shared among various passes. */ -/* Set the number of formal parameters. */ - -static inline void -ipa_set_param_count (struct ipa_node_params *info, int count) -{ - info->param_count = count; -} - /* Return the number of formal parameters. */ static inline int ipa_get_param_count (struct ipa_node_params *info) { - return info->param_count; + return VEC_length (ipa_param_descriptor_t, info->descriptors); } /* Return the declaration of Ith formal parameter of the function corresponding @@ -228,39 +203,25 @@ ipa_get_param_count (struct ipa_node_params *info) static inline tree ipa_get_param (struct ipa_node_params *info, int i) { - gcc_assert (i >= 0 && i <= info->param_count); - return info->params[i].decl; -} - -/* Return the used flag corresponding to the Ith formal parameter of - the function associated with INFO. */ - -static inline bool -ipa_is_param_used (struct ipa_node_params *info, int i) -{ - gcc_assert (i >= 0 && i <= info->param_count); - return info->params[i].used; + return VEC_index (ipa_param_descriptor_t, info->descriptors, i)->decl; } -/* Return the cannot_devirtualize flag corresponding to the Ith formal - parameter of the function associated with INFO. The corresponding function - to set the flag is ipa_set_param_cannot_devirtualize. */ +/* Set the used flag corresponding to the Ith formal parameter of the function + associated with INFO to VAL. */ -static inline bool -ipa_param_cannot_devirtualize_p (struct ipa_node_params *info, int i) +static inline void +ipa_set_param_used (struct ipa_node_params *info, int i, bool val) { - gcc_assert (i >= 0 && i <= info->param_count); - return info->params[i].cannot_devirtualize; + VEC_index (ipa_param_descriptor_t, info->descriptors, i)->used = val; } -/* Return true iff the vector of possible types of the Ith formal parameter of - the function associated with INFO is empty. */ +/* Return the used flag corresponding to the Ith formal parameter of the + function associated with INFO. */ static inline bool -ipa_param_types_vec_empty (struct ipa_node_params *info, int i) +ipa_is_param_used (struct ipa_node_params *info, int i) { - gcc_assert (i >= 0 && i <= info->param_count); - return info->params[i].types == NULL; + return VEC_index (ipa_param_descriptor_t, info->descriptors, i)->used; } /* Flag this node as having callers with variable number of arguments. */ @@ -279,8 +240,6 @@ ipa_is_called_with_var_arguments (struct ipa_node_params *info) return info->called_with_var_arguments; } - - /* ipa_edge_args stores information related to a callsite and particularly its arguments. It can be accessed by the IPA_EDGE_REF macro. */ typedef struct GTY(()) ipa_edge_args @@ -402,33 +361,6 @@ ipa_edge_args_info_available_for_edge_p (struct cgraph_edge *edge) ipa_edge_args_vector)); } -/* A function list element. It is used to create a temporary worklist used in - the propagation stage of IPCP. (can be used for more IPA optimizations) */ -struct ipa_func_list -{ - struct cgraph_node *node; - struct ipa_func_list *next; -}; - -/* ipa_func_list interface. */ -struct ipa_func_list *ipa_init_func_list (void); -void ipa_push_func_to_list_1 (struct ipa_func_list **, struct cgraph_node *, - struct ipa_node_params *); -struct cgraph_node *ipa_pop_func_from_list (struct ipa_func_list **); - -/* Add cgraph NODE to the worklist WL if it is not already in one. */ - -static inline void -ipa_push_func_to_list (struct ipa_func_list **wl, struct cgraph_node *node) -{ - struct ipa_node_params *info = IPA_NODE_REF (node); - - if (!info->node_enqueued) - ipa_push_func_to_list_1 (wl, node, info); -} - -void ipa_analyze_node (struct cgraph_node *); - /* Function formal parameters related computations. */ void ipa_initialize_node_params (struct cgraph_node *node); bool ipa_propagate_indirect_call_infos (struct cgraph_edge *cs, @@ -438,12 +370,18 @@ bool ipa_propagate_indirect_call_infos (struct cgraph_edge *cs, struct cgraph_edge *ipa_make_edge_direct_to_target (struct cgraph_edge *, tree, tree); +/* Functions related to both. */ +void ipa_analyze_node (struct cgraph_node *); /* Debugging interface. */ void ipa_print_node_params (FILE *, struct cgraph_node *node); void ipa_print_all_params (FILE *); void ipa_print_node_jump_functions (FILE *f, struct cgraph_node *node); void ipa_print_all_jump_functions (FILE * f); +void ipcp_verify_propagated_values (void); + +extern alloc_pool ipcp_values_pool; +extern alloc_pool ipcp_sources_pool; /* Structure to describe transformations of formal parameters and actual arguments. Each instance describes one new parameter and they are meant to @@ -521,9 +459,6 @@ void ipa_prop_write_jump_functions (cgraph_node_set set); void ipa_prop_read_jump_functions (void); void ipa_update_after_lto_read (void); int ipa_get_param_decl_index (struct ipa_node_params *, tree); -void ipa_lattice_from_jfunc (struct ipa_node_params *info, - struct ipcp_lattice *lat, - struct ipa_jump_func *jfunc); tree ipa_cst_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc); @@ -532,13 +467,4 @@ tree ipa_cst_from_jfunc (struct ipa_node_params *info, tree build_ref_for_offset (location_t, tree, HOST_WIDE_INT, tree, gimple_stmt_iterator *, bool); -/* Return the lattice corresponding to the Ith formal parameter of the function - described by INFO. */ -static inline struct ipcp_lattice * -ipa_get_lattice (struct ipa_node_params *info, int i) -{ - gcc_assert (i >= 0 && i <= info->param_count); - return &(info->params[i].ipcp_lattice); -} - #endif /* IPA_PROP_H */ diff --git a/gcc/params.def b/gcc/params.def index 78601f6de88..60397c15fb1 100644 --- a/gcc/params.def +++ b/gcc/params.def @@ -860,12 +860,18 @@ DEFPARAM (PARAM_IPA_SRA_PTR_GROWTH_FACTOR, "a pointer to an aggregate with", 2, 0, 0) -DEFPARAM (PARAM_DEVIRT_TYPE_LIST_SIZE, - "devirt-type-list-size", - "Maximum size of a type list associated with each parameter for " - "devirtualization", +DEFPARAM (PARAM_IPA_CP_VALUE_LIST_SIZE, + "ipa-cp-value-list-size", + "Maximum size of a list of values associated with each parameter for " + "interprocedural constant propagation", 8, 0, 0) +DEFPARAM (PARAM_IPA_CP_EVAL_THRESHOLD, + "ipa-cp-eval-threshold", + "Threshold ipa-cp opportunity evaluation that is still considered " + "beneficial to clone.", + 500, 0, 0) + /* WHOPR partitioning configuration. */ DEFPARAM (PARAM_LTO_PARTITIONS, diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 03b4441c29d..7ccdad4a835 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,19 @@ +2011-07-18 Martin Jambor <mjambor@suse.cz> + + * gcc.dg/ipa/ipa-1.c: Updated testcase dump scan. + * gcc.dg/ipa/ipa-2.c: Likewise. + * gcc.dg/ipa/ipa-3.c: Likewise and made functions static. + * gcc.dg/ipa/ipa-4.c: Updated testcase dump scan. + * gcc.dg/ipa/ipa-5.c: Likewise. + * gcc.dg/ipa/ipa-7.c: Likewise. + * gcc.dg/ipa/ipa-8.c: Updated testcase dump scan. + * gcc.dg/ipa/ipacost-1.c: Likewise. + * gcc.dg/ipa/ipacost-2.c: Likewise and increased sizes of some + functions. + * gcc.dg/ipa/ipcp-1.c: New test. + * gcc.dg/ipa/ipcp-2.c: Likewise. + * gcc.dg/tree-ssa/ipa-cp-1.c: Updated testcase. + 2011-07-18 Jakub Jelinek <jakub@redhat.com> PR middle-end/49675 diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-1.c b/gcc/testsuite/gcc.dg/ipa/ipa-1.c index e3212853cf5..3517b035f1c 100644 --- a/gcc/testsuite/gcc.dg/ipa/ipa-1.c +++ b/gcc/testsuite/gcc.dg/ipa/ipa-1.c @@ -24,9 +24,8 @@ int main () } -/* { dg-final { scan-ipa-dump-times "versioned function" 2 "cp" } } */ +/* { dg-final { scan-ipa-dump "Creating a specialized node of f" "cp" } } */ /* { dg-final { scan-ipa-dump "replacing param a with const 7" "cp" } } */ -/* { dg-final { scan-ipa-dump "replacing param b with const 7" "cp" } } */ /* { dg-final { cleanup-ipa-dump "cp" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-2.c b/gcc/testsuite/gcc.dg/ipa/ipa-2.c index 1d57fb00828..122a4a0181a 100644 --- a/gcc/testsuite/gcc.dg/ipa/ipa-2.c +++ b/gcc/testsuite/gcc.dg/ipa/ipa-2.c @@ -22,7 +22,6 @@ int main () } -/* { dg-final { scan-ipa-dump-times "versioned function" 2 "cp" } } */ +/* { dg-final { scan-ipa-dump "Creating a specialized node of f" "cp" } } */ /* { dg-final { scan-ipa-dump "replacing param a with const 7" "cp" } } */ -/* { dg-final { scan-ipa-dump "replacing param c with const 3" "cp" } } */ /* { dg-final { cleanup-ipa-dump "cp" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-3.c b/gcc/testsuite/gcc.dg/ipa/ipa-3.c index a3334c34543..e15f084b400 100644 --- a/gcc/testsuite/gcc.dg/ipa/ipa-3.c +++ b/gcc/testsuite/gcc.dg/ipa/ipa-3.c @@ -7,12 +7,12 @@ #include <stdio.h> void t(void); -int g (double b, double c) +static int g (double b, double c) { t(); return (int)(b+c); } -int f (double a) +static int f (double a) { if (a > 0) g (a, 3.1); @@ -28,8 +28,9 @@ int main () } -/* { dg-final { scan-ipa-dump-times "versioned function" 2 "cp" } } */ +/* { dg-final { scan-ipa-dump "Creating a specialized node of f" "cp" } } */ /* { dg-final { scan-ipa-dump "replacing param a with const 7" "cp" } } */ +/* { dg-final { scan-ipa-dump "Creating a specialized node of g" "cp" } } */ /* { dg-final { scan-ipa-dump "replacing param b with const 7" "cp" } } */ /* { dg-final { scan-ipa-dump "replacing param c with const 3" "cp" } } */ /* { dg-final { cleanup-ipa-dump "cp" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-4.c b/gcc/testsuite/gcc.dg/ipa/ipa-4.c index 3cb0cd4d27e..88716dd8f4c 100644 --- a/gcc/testsuite/gcc.dg/ipa/ipa-4.c +++ b/gcc/testsuite/gcc.dg/ipa/ipa-4.c @@ -25,6 +25,6 @@ int main () } -/* { dg-final { scan-ipa-dump-times "versioned function" 1 "cp" } } */ +/* { dg-final { scan-ipa-dump "Creating a specialized node of f" "cp" } } */ /* { dg-final { scan-ipa-dump-times "replacing param a with const 7" 1 "cp" } } */ /* { dg-final { cleanup-ipa-dump "cp" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-5.c b/gcc/testsuite/gcc.dg/ipa/ipa-5.c index 50af18e2b01..22d1be89c0e 100644 --- a/gcc/testsuite/gcc.dg/ipa/ipa-5.c +++ b/gcc/testsuite/gcc.dg/ipa/ipa-5.c @@ -26,8 +26,7 @@ int main () return 0; } - -/* { dg-final { scan-ipa-dump-times "versioned function" 2 "cp" } } */ +/* { dg-final { scan-ipa-dump-times "Creating a specialized node" 2 "cp" } } */ /* { dg-final { scan-ipa-dump "replacing param c with const 3" "cp" } } */ /* { dg-final { scan-ipa-dump "replacing param a with const 7" "cp" } } */ /* { dg-final { cleanup-ipa-dump "cp" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-7.c b/gcc/testsuite/gcc.dg/ipa/ipa-7.c index 6dcc914c103..c8b510046a1 100644 --- a/gcc/testsuite/gcc.dg/ipa/ipa-7.c +++ b/gcc/testsuite/gcc.dg/ipa/ipa-7.c @@ -26,8 +26,8 @@ int main () } -/* { dg-final { scan-ipa-dump-times "versioned function" 1 "cp" } } */ -/* { dg-final { scan-ipa-dump-times "replacing param a with const 7" 1 "cp" } } */ +/* { dg-final { scan-ipa-dump "Creating a specialized node of f" "cp" } } */ +/* { dg-final { scan-ipa-dump-times "replacing param . with const 7" 1 "cp" } } */ /* { dg-final { cleanup-ipa-dump "cp" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-8.c b/gcc/testsuite/gcc.dg/ipa/ipa-8.c index edea7f900b4..dcbed13a0ed 100644 --- a/gcc/testsuite/gcc.dg/ipa/ipa-8.c +++ b/gcc/testsuite/gcc.dg/ipa/ipa-8.c @@ -22,8 +22,9 @@ int main () } -/* { dg-final { scan-ipa-dump-times "versioned function" 2 "cp" } } */ +/* { dg-final { scan-ipa-dump "Creating a specialized node of f" "cp" } } */ /* { dg-final { scan-ipa-dump "replacing param a with const 7" "cp" } } */ +/* { dg-final { scan-ipa-dump "Creating a specialized node of g" "cp" } } */ /* { dg-final { scan-ipa-dump "replacing param b with const 7" "cp" } } */ /* { dg-final { cleanup-ipa-dump "cp" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/ipacost-1.c b/gcc/testsuite/gcc.dg/ipa/ipacost-1.c index d91546899ea..4fce41e8235 100644 --- a/gcc/testsuite/gcc.dg/ipa/ipacost-1.c +++ b/gcc/testsuite/gcc.dg/ipa/ipacost-1.c @@ -51,10 +51,10 @@ main() i_can_not_be_propagated_fully2 (array); } -/* { dg-final { scan-ipa-dump-times "versioned function i_can_be_propagated_fully2" 1 "cp" } } */ -/* { dg-final { scan-ipa-dump-times "versioned function i_can_be_propagated_fully " 1 "cp" } } */ -/* { dg-final { scan-ipa-dump-not "versioned function i_can_not_be_propagated_fully2" "cp" } } */ -/* { dg-final { scan-ipa-dump-not "versioned function i_can_not_be_propagated_fully " "cp" } } */ +/* { dg-final { scan-ipa-dump-times "Creating a specialized node of i_can_be_propagated_fully2" 1 "cp" } } */ +/* { dg-final { scan-ipa-dump-times "Creating a specialized node of i_can_be_propagated_fully/" 1 "cp" } } */ +/* { dg-final { scan-ipa-dump-not "Creating a specialized node of i_can_not_be_propagated_fully2" "cp" } } */ +/* { dg-final { scan-ipa-dump-not "Creating a specialized node of i_can_not_be_propagated_fully/" "cp" } } */ /* { dg-final { scan-tree-dump-not "i_can_be_propagated_fully " "optimized" } } */ /* { dg-final { scan-tree-dump-not "i_can_be_propagated_fully2 " "optimized" } } */ /* { dg-final { cleanup-ipa-dump "cp" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/ipacost-2.c b/gcc/testsuite/gcc.dg/ipa/ipacost-2.c index 6ebd6d37481..ceb524e00ae 100644 --- a/gcc/testsuite/gcc.dg/ipa/ipacost-2.c +++ b/gcc/testsuite/gcc.dg/ipa/ipacost-2.c @@ -40,8 +40,23 @@ i_can_not_be_propagated_fully (int *a) int i_can_not_be_propagated_fully2 (int *a) { + int i; i_can_not_be_propagated_fully (a); + for (i=0;i<50;i++) + { + t(a[i] + 1); + t(a[i+1] + 1); + t(a[i+2] + 1); + t(a[i+3] + 1); + } i_can_not_be_propagated_fully (a); + for (i=0;i<50;i++) + { + t(a[i] + 2); + t(a[i+1] + 2); + t(a[i+2] + 2); + t(a[i+3] + 2); + } i_can_not_be_propagated_fully (a); } main() @@ -50,15 +65,15 @@ main() i_can_be_propagated_fully2 (array); i_can_be_propagated_fully2 (array); - for (i = 0; i < 100; i++) + for (i = 0; i < 7; i++) i_can_not_be_propagated_fully2 (array); i_can_not_be_propagated_fully2 (array); } -/* { dg-final { scan-ipa-dump-times "versioned function i_can_be_propagated_fully2" 1 "cp" } } */ -/* { dg-final { scan-ipa-dump-times "versioned function i_can_be_propagated_fully " 1 "cp" } } */ -/* { dg-final { scan-ipa-dump-times "versioned function i_can_not_be_propagated_fully2" 1 "cp" } } */ -/* { dg-final { scan-ipa-dump-times "versioned function i_can_not_be_propagated_fully " 1 "cp" } } */ +/* { dg-final { scan-ipa-dump-times "Creating a specialized node of i_can_be_propagated_fully2" 1 "cp" } } */ +/* { dg-final { scan-ipa-dump-times "Creating a specialized node of i_can_be_propagated_fully/" 1 "cp" } } */ +/* { dg-final { scan-ipa-dump-not "Creating a specialized node of i_can_not_be_propagated_fully2" "cp" } } */ +/* { dg-final { scan-ipa-dump-not "Creating a specialized node of i_can_not_be_propagated_fully/" "cp" } } */ /* { dg-final { scan-tree-dump-not "i_can_be_propagated_fully \\(" "optimized" } } */ /* { dg-final { scan-tree-dump-not "i_can_be_propagated_fully2 \\(" "optimized" } } */ /* { dg-final { cleanup-ipa-dump "cp" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/ipcp-1.c b/gcc/testsuite/gcc.dg/ipa/ipcp-1.c new file mode 100644 index 00000000000..0f50ff9276a --- /dev/null +++ b/gcc/testsuite/gcc.dg/ipa/ipcp-1.c @@ -0,0 +1,52 @@ +/* Test that IPA-CP is able to figure out that poth parameters a are constant 7 + even though f and h recursively call each other and specialize them + accordinly. */ + +/* { dg-do compile } */ +/* { dg-options "-O3 -fipa-cp -fipa-cp-clone -fdump-ipa-cp -fno-early-inlining" } */ +/* { dg-add-options bind_pic_locally } */ + +extern void use_stuff (int); + +static +int g (int b, int c) +{ + int i; + + for (i = 0; i < b; i++) + use_stuff (c); +} + +static void f (int a, int x, int z); + +static void h (int z, int a) +{ + use_stuff (z); + f (a, 9, 10); + +} + +static void +f (int a, int x, int z) +{ + if (z > 1) + g (a, x); + else + h (5, a); +} + +int +main (int argc, char *argv[]) +{ + int i; + for (i = 0; i < 100; i++) + f (7, 8, argc); + return 0; +} + + +/* { dg-final { scan-ipa-dump "Creating a specialized node of f.*for all known contexts" "cp" } } */ +/* { dg-final { scan-ipa-dump "replacing param a with const 7" "cp" } } */ +/* { dg-final { cleanup-ipa-dump "cp" } } */ + + diff --git a/gcc/testsuite/gcc.dg/ipa/ipcp-2.c b/gcc/testsuite/gcc.dg/ipa/ipcp-2.c new file mode 100644 index 00000000000..c6dcdf0af52 --- /dev/null +++ b/gcc/testsuite/gcc.dg/ipa/ipcp-2.c @@ -0,0 +1,99 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fipa-cp -fipa-cp-clone -fdump-ipa-cp -fno-early-inlining" } */ +/* { dg-add-options bind_pic_locally } */ + +extern int get_stuff (int); +extern void do_stuff (int); +extern void do_stuff2 (int); +extern void do_other_stuff (void); +extern int get_element (int, int, int); +extern int adjust (int, int, int, int); + +extern int count; + +int +foo (int s, int p) +{ + int c, r = 0; + + for (c = 0 ; c < count; c++) + { + r += get_stuff (s); + /* The following is just something big that can go away. */ + if (p != 0) + { + int a[64][64]; + int i, j, k; + + for (i = 0; i < 64; i++) + for (j = 0; j < 64; j++) + a[i][j] = get_element (p + c, i, j); + + for (k = 0; k < 4; k++) + { + r = r / 2; + + for (i = 1; i < 63; i++) + for (j = 62; j > 0; j--) + a[i][j] += adjust (a[i-1][j], a[i][j-1], + a[i+1][j], a[i][j+1]); + + for (i = 4; i < 64; i += 4) + for (j = 4; j < 64; j += 4) + r += a[i][j] / 4; + } + } + } + return r; +} + +int +bar (int p, int q) +{ + if (q > 0) + do_stuff (q); + else + do_stuff (-q); + + if (q % 2) + do_stuff2 (2 * q); + else + do_stuff2 (2 * (q + 1)); + + return foo (4, p); +} + +int +bah (int p, int q) +{ + int i, j; + + while (q < -20) + q += get_stuff (-q); + + for (i = 0; i < 36; i++) + for (j = 0; j < 36; j++) + do_stuff (get_stuff (q * i + 2)); + + bar (p, q); +} + +int +top1 (int q) +{ + do_other_stuff (); + return bah (0, q); +} + +int +top2 (int q) +{ + do_stuff (200); + do_other_stuff (); + return bah (16, q); +} + +/* { dg-final { scan-ipa-dump-times "Creating a specialized node of foo" 1 "cp" } } */ +/* { dg-final { scan-ipa-dump-times "replacing param p with const 0" 3 "cp" } } */ +/* { dg-final { scan-ipa-dump "replacing param s with const 4" "cp" } } */ +/* { dg-final { cleanup-ipa-dump "cp" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ipa-cp-1.c b/gcc/testsuite/gcc.dg/tree-ssa/ipa-cp-1.c index 7918eb7562d..26b433823ac 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ipa-cp-1.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ipa-cp-1.c @@ -5,9 +5,13 @@ int very_long_function(int a) { - return very_long_function (a)/4; + if (a > 0) + return 2 * a + very_long_function (a)/4; + else + return 2 * -a + very_long_function (a)/4; } -main() + +blah () { very_long_function (1); } |