X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=gcc%2Fipa-cp.c;h=d23c1d8ba3eca35cdcb4ab550e5edd9aa06fdd21;hb=9e878cf1bae7eba3a097dbb6b04d0bbca5bdb0e4;hp=d36563490160d1940ae20e419078627b74aff828;hpb=c8f403525ae53bc8cdba13ea5f8d8f9a95ed08d6;p=gcc.git diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c index d3656349016..d23c1d8ba3e 100644 --- a/gcc/ipa-cp.c +++ b/gcc/ipa-cp.c @@ -1,5 +1,5 @@ /* Interprocedural constant propagation - Copyright (C) 2005-2014 Free Software Foundation, Inc. + Copyright (C) 2005-2017 Free Software Foundation, Inc. Contributed by Razya Ladelsky and Martin Jambor @@ -61,7 +61,7 @@ along with GCC; see the file COPYING3. If not see values: Pass through - the caller's formal parameter is passed as an actual - argument, plus an operation on it can be performed. + argument, plus an operation on it can be performed. Constant - a constant is passed as an actual argument. Unknown - neither of the above. @@ -103,90 +103,119 @@ along with GCC; see the file COPYING3. If not see #include "config.h" #include "system.h" #include "coretypes.h" +#include "backend.h" #include "tree.h" -#include "gimple-fold.h" #include "gimple-expr.h" -#include "target.h" -#include "ipa-prop.h" -#include "bitmap.h" +#include "predict.h" +#include "alloc-pool.h" #include "tree-pass.h" -#include "flags.h" +#include "cgraph.h" #include "diagnostic.h" +#include "fold-const.h" +#include "gimple-fold.h" +#include "symbol-summary.h" +#include "tree-vrp.h" +#include "ipa-prop.h" #include "tree-pretty-print.h" #include "tree-inline.h" #include "params.h" -#include "ipa-inline.h" +#include "ipa-fnsummary.h" #include "ipa-utils.h" +#include "tree-ssa-ccp.h" +#include "stringpool.h" +#include "attribs.h" -struct ipcp_value; +template class ipcp_value; /* Describes a particular source for an IPA-CP value. */ -struct ipcp_value_source +template +class ipcp_value_source { +public: /* Aggregate offset of the source, negative if the source is scalar value of the argument itself. */ HOST_WIDE_INT offset; /* The incoming edge that brought the value. */ - struct cgraph_edge *cs; + 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; + ipcp_value *val; /* Next pointer in a linked list of sources of a value. */ - struct ipcp_value_source *next; + 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; }; +/* Common ancestor for all ipcp_value instantiations. */ + +class ipcp_value_base +{ +public: + /* 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; + + ipcp_value_base () + : local_time_benefit (0), local_size_cost (0), + prop_time_benefit (0), prop_size_cost (0) {} +}; + /* Describes one particular value stored in struct ipcp_lattice. */ -struct ipcp_value +template +class ipcp_value : public ipcp_value_base { - /* 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; +public: + /* The actual value for the given parameter. */ + valtype value; /* The list of sources from which this value originates. */ - struct ipcp_value_source *sources; + ipcp_value_source *sources; /* Next pointers in a linked list of all values in a lattice. */ - struct ipcp_value *next; + ipcp_value *next; /* Next pointers in a linked list of values in a strongly connected component of values. */ - struct ipcp_value *scc_next; + ipcp_value *scc_next; /* Next pointers in a linked list of SCCs of values sorted topologically according their sources. */ - struct ipcp_value *topo_next; + ipcp_value *topo_next; /* A specialized node created for this value, NULL if none has been (so far) created. */ - struct cgraph_node *spec_node; + 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; + + ipcp_value() + : sources (0), next (0), scc_next (0), topo_next (0), + spec_node (0), dfs (0), low_link (0), on_stack (false) {} + + void add_source (cgraph_edge *cs, ipcp_value *src_val, int src_idx, + HOST_WIDE_INT offset); }; /* Lattice describing potential values of a formal parameter of a function, or - a part of an aggreagate. TOP is represented by a lattice with zero values + a part of an aggregate. 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 +template +class ipcp_lattice { +public: /* 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; + 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). */ @@ -194,12 +223,22 @@ struct ipcp_lattice /* The value of the lattice is bottom (i.e. variable and unusable for any propagation). */ bool bottom; + + inline bool is_single_const (); + inline bool set_to_bottom (); + inline bool set_contains_variable (); + bool add_value (valtype newval, cgraph_edge *cs, + ipcp_value *src_val = NULL, + int src_idx = 0, HOST_WIDE_INT offset = -1); + void print (FILE * f, bool dump_sources, bool dump_benefits); }; -/* Lattice with an offset to describe a part of an aggregate. */ +/* Lattice of tree values with an offset to describe a part of an + aggregate. */ -struct ipcp_agg_lattice : public ipcp_lattice +class ipcp_agg_lattice : public ipcp_lattice { +public: /* Offset that is being described by this lattice. */ HOST_WIDE_INT offset; /* Size so that we don't have to re-compute it every time we traverse the @@ -209,16 +248,96 @@ struct ipcp_agg_lattice : public ipcp_lattice struct ipcp_agg_lattice *next; }; +/* Lattice of known bits, only capable of holding one value. + Bitwise constant propagation propagates which bits of a + value are constant. + For eg: + int f(int x) + { + return some_op (x); + } + + int f1(int y) + { + if (cond) + return f (y & 0xff); + else + return f (y & 0xf); + } + + In the above case, the param 'x' will always have all + the bits (except the bits in lsb) set to 0. + Hence the mask of 'x' would be 0xff. The mask + reflects that the bits in lsb are unknown. + The actual propagated value is given by m_value & ~m_mask. */ + +class ipcp_bits_lattice +{ +public: + bool bottom_p () { return m_lattice_val == IPA_BITS_VARYING; } + bool top_p () { return m_lattice_val == IPA_BITS_UNDEFINED; } + bool constant_p () { return m_lattice_val == IPA_BITS_CONSTANT; } + bool set_to_bottom (); + bool set_to_constant (widest_int, widest_int); + + widest_int get_value () { return m_value; } + widest_int get_mask () { return m_mask; } + + bool meet_with (ipcp_bits_lattice& other, unsigned, signop, + enum tree_code, tree); + + bool meet_with (widest_int, widest_int, unsigned); + + void print (FILE *); + +private: + enum { IPA_BITS_UNDEFINED, IPA_BITS_CONSTANT, IPA_BITS_VARYING } m_lattice_val; + + /* Similar to ccp_lattice_t, mask represents which bits of value are constant. + If a bit in mask is set to 0, then the corresponding bit in + value is known to be constant. */ + widest_int m_value, m_mask; + + bool meet_with_1 (widest_int, widest_int, unsigned); + void get_value_and_mask (tree, widest_int *, widest_int *); +}; + +/* Lattice of value ranges. */ + +class ipcp_vr_lattice +{ +public: + value_range m_vr; + + inline bool bottom_p () const; + inline bool top_p () const; + inline bool set_to_bottom (); + bool meet_with (const value_range *p_vr); + bool meet_with (const ipcp_vr_lattice &other); + void init () { m_vr.type = VR_UNDEFINED; } + void print (FILE * f); + +private: + bool meet_with_1 (const value_range *other_vr); +}; + /* Structure containing lattices for a parameter itself and for pieces of aggregates that are passed in the parameter or by a reference in a parameter plus some other useful flags. */ -struct ipcp_param_lattices +class ipcp_param_lattices { +public: /* Lattice describing the value of the parameter itself. */ - struct ipcp_lattice itself; + ipcp_lattice itself; + /* Lattice describing the polymorphic contexts of a parameter. */ + ipcp_lattice ctxlat; /* Lattices describing aggregate parts. */ - struct ipcp_agg_lattice *aggs; + ipcp_agg_lattice *aggs; + /* Lattice describing known bits. */ + ipcp_bits_lattice bits_lattice; + /* Lattice describing value range. */ + ipcp_vr_lattice m_value_range; /* Number of aggregate lattices */ int aggs_count; /* True if aggregate data were passed by reference (as opposed to by @@ -237,22 +356,26 @@ struct ipcp_param_lattices /* Allocation pools for values and their sources in ipa-cp. */ -alloc_pool ipcp_values_pool; -alloc_pool ipcp_sources_pool; -alloc_pool ipcp_agg_lattice_pool; +object_allocator > ipcp_cst_values_pool + ("IPA-CP constant values"); + +object_allocator > + ipcp_poly_ctx_values_pool ("IPA-CP polymorphic contexts"); + +object_allocator > ipcp_sources_pool + ("IPA-CP value sources"); + +object_allocator ipcp_agg_lattice_pool + ("IPA_CP aggregate lattices"); /* Maximal count found in program. */ -static gcov_type max_count; +static profile_count 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 param lattices structure corresponding to the Ith formal parameter of the function described by INFO. */ static inline struct ipcp_param_lattices * @@ -266,22 +389,40 @@ ipa_get_parm_lattices (struct ipa_node_params *info, int i) /* Return the lattice corresponding to the scalar value of the Ith formal parameter of the function described by INFO. */ -static inline struct ipcp_lattice * +static inline ipcp_lattice * ipa_get_scalar_lat (struct ipa_node_params *info, int i) { struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); return &plats->itself; } +/* Return the lattice corresponding to the scalar value of the Ith formal + parameter of the function described by INFO. */ +static inline ipcp_lattice * +ipa_get_poly_ctx_lat (struct ipa_node_params *info, int i) +{ + struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); + return &plats->ctxlat; +} + +/* Return the lattice corresponding to the value range of the Ith formal + parameter of the function described by INFO. */ + +static inline ipcp_vr_lattice * +ipa_get_vr_lat (struct ipa_node_params *info, int i) +{ + struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); + return &plats->m_value_range; +} + /* Return whether LAT is a lattice with a single constant and without an undefined value. */ -static inline bool -ipa_lat_is_single_const (struct ipcp_lattice *lat) +template +inline bool +ipcp_lattice::is_single_const () { - if (lat->bottom - || lat->contains_variable - || lat->values_count != 1) + if (bottom || contains_variable || values_count != 1) return false; else return true; @@ -292,43 +433,46 @@ ipa_lat_is_single_const (struct ipcp_lattice *lat) static void print_ipcp_constant_value (FILE * f, tree v) { - if (TREE_CODE (v) == TREE_BINFO) - { - fprintf (f, "BINFO "); - print_generic_expr (f, BINFO_TYPE (v), 0); - } - else if (TREE_CODE (v) == ADDR_EXPR - && TREE_CODE (TREE_OPERAND (v, 0)) == CONST_DECL) + if (TREE_CODE (v) == ADDR_EXPR + && TREE_CODE (TREE_OPERAND (v, 0)) == CONST_DECL) { fprintf (f, "& "); - print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (v, 0)), 0); + print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (v, 0))); } else - print_generic_expr (f, v, 0); + print_generic_expr (f, v); } -/* Print a lattice LAT to F. */ +/* Print V which is extracted from a value in a lattice to F. */ static void -print_lattice (FILE * f, struct ipcp_lattice *lat, - bool dump_sources, bool dump_benefits) +print_ipcp_constant_value (FILE * f, ipa_polymorphic_call_context v) { - struct ipcp_value *val; + v.dump(f, false); +} + +/* Print a lattice LAT to F. */ + +template +void +ipcp_lattice::print (FILE * f, bool dump_sources, bool dump_benefits) +{ + ipcp_value *val; bool prev = false; - if (lat->bottom) + if (bottom) { fprintf (f, "BOTTOM\n"); return; } - if (!lat->values_count && !lat->contains_variable) + if (!values_count && !contains_variable) { fprintf (f, "TOP\n"); return; } - if (lat->contains_variable) + if (contains_variable) { fprintf (f, "VARIABLE"); prev = true; @@ -336,7 +480,7 @@ print_lattice (FILE * f, struct ipcp_lattice *lat, fprintf (f, "\n"); } - for (val = lat->values; val; val = val->next) + for (val = values; val; val = val->next) { if (dump_benefits && prev) fprintf (f, " "); @@ -349,7 +493,7 @@ print_lattice (FILE * f, struct ipcp_lattice *lat, if (dump_sources) { - struct ipcp_value_source *s; + ipcp_value_source *s; fprintf (f, " [from:"); for (s = val->sources; s; s = s->next) @@ -368,6 +512,29 @@ print_lattice (FILE * f, struct ipcp_lattice *lat, fprintf (f, "\n"); } +void +ipcp_bits_lattice::print (FILE *f) +{ + if (top_p ()) + fprintf (f, " Bits unknown (TOP)\n"); + else if (bottom_p ()) + fprintf (f, " Bits unusable (BOTTOM)\n"); + else + { + fprintf (f, " Bits: value = "); print_hex (get_value (), f); + fprintf (f, ", mask = "); print_hex (get_mask (), f); + fprintf (f, "\n"); + } +} + +/* Print value range lattice to F. */ + +void +ipcp_vr_lattice::print (FILE * f) +{ + dump_value_range (f, &m_vr); +} + /* Print all ipcp_lattices of all functions to F. */ static void @@ -382,16 +549,20 @@ print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits) struct ipa_node_params *info; info = IPA_NODE_REF (node); - fprintf (f, " Node: %s/%i:\n", node->name (), - node->order); + fprintf (f, " Node: %s:\n", node->dump_name ()); count = ipa_get_param_count (info); for (i = 0; i < count; i++) { struct ipcp_agg_lattice *aglat; struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); fprintf (f, " param [%d]: ", i); - print_lattice (f, &plats->itself, dump_sources, dump_benefits); - + plats->itself.print (f, dump_sources, dump_benefits); + fprintf (f, " ctxs: "); + plats->ctxlat.print (f, dump_sources, dump_benefits); + plats->bits_lattice.print (f); + fprintf (f, " "); + plats->m_value_range.print (f); + fprintf (f, "\n"); if (plats->virt_call) fprintf (f, " virt_call flag set\n"); @@ -406,7 +577,7 @@ print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits) { fprintf (f, " %soffset " HOST_WIDE_INT_PRINT_DEC ": ", plats->aggs_by_ref ? "ref " : "", aglat->offset); - print_lattice (f, aglat, dump_sources, dump_benefits); + aglat->print (f, dump_sources, dump_benefits); } } } @@ -417,7 +588,8 @@ print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits) with NODE. */ static void -determine_versionability (struct cgraph_node *node) +determine_versionability (struct cgraph_node *node, + struct ipa_node_params *info) { const char *reason = NULL; @@ -440,16 +612,29 @@ determine_versionability (struct cgraph_node *node) coexist, but that may not be worth the effort. */ reason = "function has SIMD clones"; } + else if (lookup_attribute ("target_clones", DECL_ATTRIBUTES (node->decl))) + { + /* Ideally we should clone the target clones themselves and create + copies of them, so IPA-cp and target clones can happily + coexist, but that may not be worth the effort. */ + reason = "function target_clones attribute"; + } /* Don't clone decls local to a comdat group; it breaks and for C++ decloned constructors, inlining is always better anyway. */ else if (node->comdat_local_p ()) reason = "comdat-local function"; + else if (node->calls_comdat_local) + { + /* TODO: call is versionable if we make sure that all + callers are inside of a comdat group. */ + reason = "calls comdat-local function"; + } if (reason && dump_file && !node->alias && !node->thunk.thunk_p) - fprintf (dump_file, "Function %s/%i is not versionable, reason: %s.\n", - node->name (), node->order, reason); + fprintf (dump_file, "Function %s is not versionable, reason: %s.\n", + node->dump_name (), reason); - node->local.versionable = (reason == NULL); + info->versionable = (reason == NULL); } /* Return true if it is at all technically possible to create clones of a @@ -458,14 +643,14 @@ determine_versionability (struct cgraph_node *node) static bool ipcp_versionable_function_p (struct cgraph_node *node) { - return node->local.versionable; + return IPA_NODE_REF (node)->versionable; } /* Structure holding accumulated information about callers of a node. */ struct caller_statistics { - gcov_type count_sum; + profile_count count_sum; int n_calls, n_hot_calls, freq_sum; }; @@ -474,7 +659,7 @@ struct caller_statistics static inline void init_caller_stats (struct caller_statistics *stats) { - stats->count_sum = 0; + stats->count_sum = profile_count::zero (); stats->n_calls = 0; stats->n_hot_calls = 0; stats->freq_sum = 0; @@ -490,12 +675,10 @@ gather_caller_stats (struct cgraph_node *node, void *data) struct cgraph_edge *cs; for (cs = node->callers; cs; cs = cs->next_caller) - if (cs->caller->thunk.thunk_p) - cs->caller->call_for_symbol_thunks_and_aliases (gather_caller_stats, - stats, false); - else + if (!cs->caller->thunk.thunk_p) { - stats->count_sum += cs->count; + if (cs->count.initialized_p ()) + stats->count_sum += cs->count; stats->freq_sum += cs->frequency; stats->n_calls++; if (cs->maybe_hot_p ()) @@ -514,48 +697,48 @@ ipcp_cloning_candidate_p (struct cgraph_node *node) gcc_checking_assert (node->has_gimple_body_p ()); - if (!flag_ipa_cp_clone) + if (!opt_for_fn (node->decl, flag_ipa_cp_clone)) { if (dump_file) - fprintf (dump_file, "Not considering %s for cloning; " + fprintf (dump_file, "Not considering %s for cloning; " "-fipa-cp-clone disabled.\n", - node->name ()); + node->name ()); return false; } - if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl))) + if (node->optimize_for_size_p ()) { if (dump_file) - fprintf (dump_file, "Not considering %s for cloning; " + fprintf (dump_file, "Not considering %s for cloning; " "optimizing it for size.\n", - node->name ()); + node->name ()); return false; } init_caller_stats (&stats); node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats, false); - if (inline_summary (node)->self_size < stats.n_calls) + if (ipa_fn_summaries->get (node)->self_size < stats.n_calls) { if (dump_file) - fprintf (dump_file, "Considering %s for cloning; code might shrink.\n", - node->name ()); + fprintf (dump_file, "Considering %s for cloning; code might shrink.\n", + node->name ()); return true; } /* When profile is available and function is hot, propagate into it even if calls seems cold; constant propagation can improve function's speed significantly. */ - if (max_count) + if (max_count > profile_count::zero ()) { - if (stats.count_sum > node->count * 90 / 100) + if (stats.count_sum > node->count.apply_scale (90, 100)) { if (dump_file) fprintf (dump_file, "Considering %s for cloning; " "usually called directly.\n", node->name ()); return true; - } + } } if (!stats.n_hot_calls) { @@ -570,25 +753,55 @@ ipcp_cloning_candidate_p (struct cgraph_node *node) return true; } +template +class value_topo_info +{ +public: + /* Head of the linked list of topologically sorted values. */ + ipcp_value *values_topo; + /* Stack for creating SCCs, represented by a linked list too. */ + ipcp_value *stack; + /* Counter driving the algorithm in add_val_to_toposort. */ + int dfs_counter; + + value_topo_info () : values_topo (NULL), stack (NULL), dfs_counter (0) + {} + void add_val (ipcp_value *cur_val); + void propagate_effects (); +}; + /* Arrays representing a topological ordering of call graph nodes and a stack - of noes used during constant propagation. */ + of nodes used during constant propagation and also data required to perform + topological sort of values and propagation of benefits in the determined + order. */ -struct topo_info +class ipa_topo_info { +public: + /* Array with obtained topological order of cgraph nodes. */ struct cgraph_node **order; + /* Stack of cgraph nodes used during propagation within SCC until all values + in the SCC stabilize. */ struct cgraph_node **stack; int nnodes, stack_top; + + value_topo_info constants; + value_topo_info contexts; + + ipa_topo_info () : order(NULL), stack(NULL), nnodes(0), stack_top(0), + constants () + {} }; /* Allocate the arrays in TOPO and topologically sort the nodes into order. */ static void -build_toporder_info (struct topo_info *topo) +build_toporder_info (struct ipa_topo_info *topo) { topo->order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count); topo->stack = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count); - topo->stack_top = 0; + gcc_checking_assert (topo->stack_top == 0); topo->nnodes = ipa_reduced_postorder (topo->order, true, true, NULL); } @@ -596,7 +809,7 @@ build_toporder_info (struct topo_info *topo) TOPO. */ static void -free_toporder_info (struct topo_info *topo) +free_toporder_info (struct ipa_topo_info *topo) { ipa_free_postorder_info (); free (topo->order); @@ -606,7 +819,7 @@ free_toporder_info (struct topo_info *topo) /* 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) +push_node_to_stack (struct ipa_topo_info *topo, struct cgraph_node *node) { struct ipa_node_params *info = IPA_NODE_REF (node); if (info->node_enqueued) @@ -619,7 +832,7 @@ push_node_to_stack (struct topo_info *topo, struct cgraph_node *node) is empty. */ static struct cgraph_node * -pop_node_from_stack (struct topo_info *topo) +pop_node_from_stack (struct ipa_topo_info *topo) { if (topo->stack_top) { @@ -636,22 +849,24 @@ pop_node_from_stack (struct topo_info *topo) /* 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) +template +inline bool +ipcp_lattice::set_to_bottom () { - bool ret = !lat->bottom; - lat->bottom = true; + bool ret = !bottom; + bottom = true; return ret; } /* 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) +template +inline bool +ipcp_lattice::set_contains_variable () { - bool ret = !lat->contains_variable; - lat->contains_variable = true; + bool ret = !contains_variable; + contains_variable = true; return ret; } @@ -677,18 +892,262 @@ set_agg_lats_contain_variable (struct ipcp_param_lattices *plats) return ret; } +bool +ipcp_vr_lattice::meet_with (const ipcp_vr_lattice &other) +{ + return meet_with_1 (&other.m_vr); +} + +/* Meet the current value of the lattice with value ranfge described by VR + lattice. */ + +bool +ipcp_vr_lattice::meet_with (const value_range *p_vr) +{ + return meet_with_1 (p_vr); +} + +/* Meet the current value of the lattice with value ranfge described by + OTHER_VR lattice. */ + +bool +ipcp_vr_lattice::meet_with_1 (const value_range *other_vr) +{ + tree min = m_vr.min, max = m_vr.max; + value_range_type type = m_vr.type; + + if (bottom_p ()) + return false; + + if (other_vr->type == VR_VARYING) + return set_to_bottom (); + + vrp_meet (&m_vr, other_vr); + if (type != m_vr.type + || min != m_vr.min + || max != m_vr.max) + return true; + else + return false; +} + +/* Return true if value range information in the lattice is yet unknown. */ + +bool +ipcp_vr_lattice::top_p () const +{ + return m_vr.type == VR_UNDEFINED; +} + +/* Return true if value range information in the lattice is known to be + unusable. */ + +bool +ipcp_vr_lattice::bottom_p () const +{ + return m_vr.type == VR_VARYING; +} + +/* Set value range information in the lattice to bottom. Return true if it + previously was in a different state. */ + +bool +ipcp_vr_lattice::set_to_bottom () +{ + if (m_vr.type == VR_VARYING) + return false; + m_vr.type = VR_VARYING; + return true; +} + +/* Set lattice value to bottom, if it already isn't the case. */ + +bool +ipcp_bits_lattice::set_to_bottom () +{ + if (bottom_p ()) + return false; + m_lattice_val = IPA_BITS_VARYING; + m_value = 0; + m_mask = -1; + return true; +} + +/* Set to constant if it isn't already. Only meant to be called + when switching state from TOP. */ + +bool +ipcp_bits_lattice::set_to_constant (widest_int value, widest_int mask) +{ + gcc_assert (top_p ()); + m_lattice_val = IPA_BITS_CONSTANT; + m_value = value; + m_mask = mask; + return true; +} + +/* Convert operand to value, mask form. */ + +void +ipcp_bits_lattice::get_value_and_mask (tree operand, widest_int *valuep, widest_int *maskp) +{ + wide_int get_nonzero_bits (const_tree); + + if (TREE_CODE (operand) == INTEGER_CST) + { + *valuep = wi::to_widest (operand); + *maskp = 0; + } + else + { + *valuep = 0; + *maskp = -1; + } +} + +/* Meet operation, similar to ccp_lattice_meet, we xor values + if this->value, value have different values at same bit positions, we want + to drop that bit to varying. Return true if mask is changed. + This function assumes that the lattice value is in CONSTANT state */ + +bool +ipcp_bits_lattice::meet_with_1 (widest_int value, widest_int mask, + unsigned precision) +{ + gcc_assert (constant_p ()); + + widest_int old_mask = m_mask; + m_mask = (m_mask | mask) | (m_value ^ value); + + if (wi::sext (m_mask, precision) == -1) + return set_to_bottom (); + + return m_mask != old_mask; +} + +/* Meet the bits lattice with operand + described by itself.contains_variable || !plats->aggs_contain_variable; - plats->itself.contains_variable = true; - plats->aggs_contain_variable = true; + bool ret; + ret = plats->itself.set_contains_variable (); + ret |= plats->ctxlat.set_contains_variable (); + ret |= set_agg_lats_contain_variable (plats); + ret |= plats->bits_lattice.set_to_bottom (); + ret |= plats->m_value_range.set_to_bottom (); return ret; } +/* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA + points to by the number of callers to NODE. */ + +static bool +count_callers (cgraph_node *node, void *data) +{ + int *caller_count = (int *) data; + + for (cgraph_edge *cs = node->callers; cs; cs = cs->next_caller) + /* Local thunks can be handled transparently, but if the thunk can not + be optimized out, count it as a real use. */ + if (!cs->caller->thunk.thunk_p || !cs->caller->local.local) + ++*caller_count; + return false; +} + +/* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on + the one caller of some other node. Set the caller's corresponding flag. */ + +static bool +set_single_call_flag (cgraph_node *node, void *) +{ + cgraph_edge *cs = node->callers; + /* Local thunks can be handled transparently, skip them. */ + while (cs && cs->caller->thunk.thunk_p && cs->caller->local.local) + cs = cs->next_caller; + if (cs) + { + IPA_NODE_REF (cs->caller)->node_calling_single_call = true; + return true; + } + return false; +} + /* Initialize ipcp_lattices. */ static void @@ -700,7 +1159,17 @@ initialize_node_lattices (struct cgraph_node *node) int i; gcc_checking_assert (node->has_gimple_body_p ()); - if (!node->local.local) + if (cgraph_local_p (node)) + { + int caller_count = 0; + node->call_for_symbol_thunks_and_aliases (count_callers, &caller_count, + true); + gcc_checking_assert (caller_count > 0); + if (caller_count == 1) + node->call_for_symbol_thunks_and_aliases (set_single_call_flag, + NULL, true); + } + else { /* When cloning is allowed, we can assume that externally visible functions are not called. We will compensate this by cloning @@ -712,29 +1181,37 @@ initialize_node_lattices (struct cgraph_node *node) disable = true; } + for (i = 0; i < ipa_get_param_count (info); i++) + { + struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); + plats->m_value_range.init (); + } + if (disable || variable) { - for (i = 0; i < ipa_get_param_count (info) ; i++) + for (i = 0; i < ipa_get_param_count (info); i++) { struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); if (disable) { - set_lattice_to_bottom (&plats->itself); + plats->itself.set_to_bottom (); + plats->ctxlat.set_to_bottom (); set_agg_lats_to_bottom (plats); + plats->bits_lattice.set_to_bottom (); + plats->m_value_range.set_to_bottom (); } else set_all_contains_variable (plats); } 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", - node->name (), node->order, - disable ? "BOTTOM" : "VARIABLE"); + fprintf (dump_file, "Marking all lattices of %s as %s\n", + node->dump_name (), disable ? "BOTTOM" : "VARIABLE"); } for (ie = node->indirect_calls; ie; ie = ie->next_callee) if (ie->indirect_info->polymorphic - && ie->indirect_info->param_index >= 0) + && ie->indirect_info->param_index >= 0) { gcc_checking_assert (ie->indirect_info->param_index >= 0); ipa_get_parm_lattices (info, @@ -751,29 +1228,25 @@ ipa_get_jf_pass_through_result (struct ipa_jump_func *jfunc, tree input) { tree restype, res; - if (TREE_CODE (input) == TREE_BINFO) - { - if (ipa_get_jf_pass_through_type_preserved (jfunc)) - { - gcc_checking_assert (ipa_get_jf_pass_through_operation (jfunc) - == NOP_EXPR); - return input; - } - return NULL_TREE; - } - if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR) return input; + if (!is_gimple_ip_invariant (input)) + return NULL_TREE; - gcc_checking_assert (is_gimple_ip_invariant (input)); if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc)) - == tcc_comparison) - restype = boolean_type_node; + == tcc_unary) + res = fold_unary (ipa_get_jf_pass_through_operation (jfunc), + TREE_TYPE (input), input); else - restype = TREE_TYPE (input); - res = fold_binary (ipa_get_jf_pass_through_operation (jfunc), restype, - input, ipa_get_jf_pass_through_operand (jfunc)); - + { + if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc)) + == tcc_comparison) + restype = boolean_type_node; + else + restype = TREE_TYPE (input); + res = fold_binary (ipa_get_jf_pass_through_operation (jfunc), restype, + input, ipa_get_jf_pass_through_operand (jfunc)); + } if (res && !is_gimple_ip_invariant (res)) return NULL_TREE; @@ -786,44 +1259,22 @@ ipa_get_jf_pass_through_result (struct ipa_jump_func *jfunc, tree input) static tree ipa_get_jf_ancestor_result (struct ipa_jump_func *jfunc, tree input) { - if (TREE_CODE (input) == TREE_BINFO) - { - if (!ipa_get_jf_ancestor_type_preserved (jfunc)) - return NULL; - /* FIXME: At LTO we can't propagate to non-polymorphic type, because - we have no ODR equivalency on those. This should be fixed by - propagating on types rather than binfos that would make type - matching here unnecesary. */ - if (in_lto_p - && (TREE_CODE (ipa_get_jf_ancestor_type (jfunc)) != RECORD_TYPE - || !TYPE_BINFO (ipa_get_jf_ancestor_type (jfunc)) - || !BINFO_VTABLE (TYPE_BINFO (ipa_get_jf_ancestor_type (jfunc))))) - { - if (!ipa_get_jf_ancestor_offset (jfunc)) - return input; - return NULL; - } - return get_binfo_at_offset (input, - ipa_get_jf_ancestor_offset (jfunc), - ipa_get_jf_ancestor_type (jfunc)); - } - else if (TREE_CODE (input) == ADDR_EXPR) + gcc_checking_assert (TREE_CODE (input) != TREE_BINFO); + if (TREE_CODE (input) == ADDR_EXPR) { tree t = TREE_OPERAND (input, 0); t = build_ref_for_offset (EXPR_LOCATION (t), t, - ipa_get_jf_ancestor_offset (jfunc), - ipa_get_jf_ancestor_type (jfunc) - ? ipa_get_jf_ancestor_type (jfunc) - : ptr_type_node, NULL, false); + ipa_get_jf_ancestor_offset (jfunc), false, + ptr_type_node, NULL, false); return build_fold_addr_expr (t); } else return NULL_TREE; } -/* 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 +/* Determine whether JFUNC evaluates to a single known constant value and if + so, return it. Otherwise return NULL. INFO describes the caller node or + the one it is inlined to, so that pass-through jump functions can be evaluated. */ tree @@ -831,8 +1282,6 @@ ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc) { if (jfunc->type == IPA_JF_CONST) return ipa_get_jf_constant (jfunc); - else if (jfunc->type == IPA_JF_KNOWN_TYPE) - return ipa_binfo_from_known_type_jfunc (jfunc); else if (jfunc->type == IPA_JF_PASS_THROUGH || jfunc->type == IPA_JF_ANCESTOR) { @@ -845,18 +1294,16 @@ ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc) idx = ipa_get_jf_ancestor_formal_id (jfunc); if (info->ipcp_orig_node) - input = info->known_vals[idx]; + input = info->known_csts[idx]; else { - struct ipcp_lattice *lat; + ipcp_lattice *lat; - if (!info->lattices) - { - gcc_checking_assert (!flag_ipa_cp); - return NULL_TREE; - } + if (!info->lattices + || idx >= ipa_get_param_count (info)) + return NULL_TREE; lat = ipa_get_scalar_lat (info, idx); - if (!ipa_lat_is_single_const (lat)) + if (!lat->is_single_const ()) return NULL_TREE; input = lat->values->value; } @@ -873,6 +1320,69 @@ ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc) return NULL_TREE; } +/* Determie whether JFUNC evaluates to single known polymorphic context, given + that INFO describes the caller node or the one it is inlined to, CS is the + call graph edge corresponding to JFUNC and CSIDX index of the described + parameter. */ + +ipa_polymorphic_call_context +ipa_context_from_jfunc (ipa_node_params *info, cgraph_edge *cs, int csidx, + ipa_jump_func *jfunc) +{ + ipa_edge_args *args = IPA_EDGE_REF (cs); + ipa_polymorphic_call_context ctx; + ipa_polymorphic_call_context *edge_ctx + = cs ? ipa_get_ith_polymorhic_call_context (args, csidx) : NULL; + + if (edge_ctx && !edge_ctx->useless_p ()) + ctx = *edge_ctx; + + if (jfunc->type == IPA_JF_PASS_THROUGH + || jfunc->type == IPA_JF_ANCESTOR) + { + ipa_polymorphic_call_context srcctx; + int srcidx; + bool type_preserved = true; + if (jfunc->type == IPA_JF_PASS_THROUGH) + { + if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR) + return ctx; + type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc); + srcidx = ipa_get_jf_pass_through_formal_id (jfunc); + } + else + { + type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc); + srcidx = ipa_get_jf_ancestor_formal_id (jfunc); + } + if (info->ipcp_orig_node) + { + if (info->known_contexts.exists ()) + srcctx = info->known_contexts[srcidx]; + } + else + { + if (!info->lattices + || srcidx >= ipa_get_param_count (info)) + return ctx; + ipcp_lattice *lat; + lat = ipa_get_poly_ctx_lat (info, srcidx); + if (!lat->is_single_const ()) + return ctx; + srcctx = lat->values->value; + } + if (srcctx.useless_p ()) + return ctx; + if (jfunc->type == IPA_JF_ANCESTOR) + srcctx.offset_by (ipa_get_jf_ancestor_offset (jfunc)); + if (!type_preserved) + srcctx.possible_dynamic_type_change (cs->in_polymorphic_cdtor); + srcctx.combine_with (ctx); + return srcctx; + } + + return ctx; +} /* 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 @@ -890,7 +1400,7 @@ ipcp_verify_propagated_values (void) for (i = 0; i < count; i++) { - struct ipcp_lattice *lat = ipa_get_scalar_lat (info, i); + ipcp_lattice *lat = ipa_get_scalar_lat (info, i); if (!lat->bottom && !lat->contains_variable @@ -898,7 +1408,7 @@ ipcp_verify_propagated_values (void) { if (dump_file) { - symtab_node::dump_table (dump_file); + symtab->dump (dump_file); fprintf (dump_file, "\nIPA lattices after constant " "propagation, before gcc_unreachable:\n"); print_all_lattices (dump_file, true, false); @@ -920,9 +1430,6 @@ values_equal_for_ipcp_p (tree x, tree y) 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 @@ -933,112 +1440,136 @@ values_equal_for_ipcp_p (tree x, tree y) 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. OFFSET - is negative if the source was the scalar value of the parameter itself or - the offset within an aggregate. */ +/* Return true iff X and Y should be considered equal contexts by IPA-CP. */ -static void -add_value_source (struct ipcp_value *val, struct cgraph_edge *cs, - struct ipcp_value *src_val, int src_idx, HOST_WIDE_INT offset) +static bool +values_equal_for_ipcp_p (ipa_polymorphic_call_context x, + ipa_polymorphic_call_context y) { - struct ipcp_value_source *src; + return x.equal_to (y); +} + - src = (struct ipcp_value_source *) pool_alloc (ipcp_sources_pool); +/* Add a new value source to the value represented by THIS, 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. OFFSET is negative if the source was the + scalar value of the parameter itself or the offset within an aggregate. */ + +template +void +ipcp_value::add_source (cgraph_edge *cs, ipcp_value *src_val, + int src_idx, HOST_WIDE_INT offset) +{ + ipcp_value_source *src; + + src = new (ipcp_sources_pool.allocate ()) ipcp_value_source; src->offset = offset; src->cs = cs; src->val = src_val; src->index = src_idx; - src->next = val->sources; - val->sources = src; + src->next = sources; + sources = src; } -/* Try to add NEWVAL to LAT, potentially creating a new struct ipcp_value for - it. CS, SRC_VAL SRC_INDEX and OFFSET are meant for add_value_source and - have the same meaning. */ +/* Allocate a new ipcp_value holding a tree constant, initialize its value to + SOURCE and clear all other fields. */ -static bool -add_value_to_lattice (struct ipcp_lattice *lat, tree newval, - struct cgraph_edge *cs, struct ipcp_value *src_val, - int src_idx, HOST_WIDE_INT offset) +static ipcp_value * +allocate_and_init_ipcp_value (tree source) +{ + ipcp_value *val; + + val = new (ipcp_cst_values_pool.allocate ()) ipcp_value(); + val->value = source; + return val; +} + +/* Allocate a new ipcp_value holding a polymorphic context, initialize its + value to SOURCE and clear all other fields. */ + +static ipcp_value * +allocate_and_init_ipcp_value (ipa_polymorphic_call_context source) +{ + ipcp_value *val; + + // TODO + val = new (ipcp_poly_ctx_values_pool.allocate ()) + ipcp_value(); + val->value = source; + return val; +} + +/* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS, + SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same + meaning. OFFSET -1 means the source is scalar and not a part of an + aggregate. */ + +template +bool +ipcp_lattice::add_value (valtype newval, cgraph_edge *cs, + ipcp_value *src_val, + int src_idx, HOST_WIDE_INT offset) { - struct ipcp_value *val; + ipcp_value *val; - if (lat->bottom) + if (bottom) return false; - for (val = lat->values; val; val = val->next) + for (val = values; val; val = val->next) if (values_equal_for_ipcp_p (val->value, newval)) { if (ipa_edge_within_scc (cs)) { - struct ipcp_value_source *s; - for (s = val->sources; s ; s = s->next) + 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, offset); + val->add_source (cs, src_val, src_idx, offset); return false; } - if (lat->values_count == PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE)) + if (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) + of other values in this SCC might point to them. */ + for (val = values; val; val = val->next) { while (val->sources) { - struct ipcp_value_source *src = val->sources; + ipcp_value_source *src = val->sources; val->sources = src->next; - pool_free (ipcp_sources_pool, src); + ipcp_sources_pool.remove ((ipcp_value_source*)src); } } - lat->values = NULL; - return set_lattice_to_bottom (lat); + values = NULL; + return set_to_bottom (); } - 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, offset); - val->value = newval; - val->next = lat->values; - lat->values = val; + values_count++; + val = allocate_and_init_ipcp_value (newval); + val->add_source (cs, src_val, src_idx, offset); + val->next = values; + values = val; return true; } -/* Like above but passes a special value of offset to distinguish that the - origin is the scalar value of the parameter rather than a part of an - aggregate. */ - -static inline bool -add_scalar_value_to_lattice (struct ipcp_lattice *lat, tree newval, - struct cgraph_edge *cs, - struct ipcp_value *src_val, int src_idx) -{ - return add_value_to_lattice (lat, newval, cs, src_val, src_idx, -1); -} - /* 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) +propagate_vals_across_pass_through (cgraph_edge *cs, ipa_jump_func *jfunc, + ipcp_lattice *src_lat, + ipcp_lattice *dest_lat, int src_idx) { - struct ipcp_value *src_val; + ipcp_value *src_val; bool ret = false; /* Do not create new values when propagating within an SCC because if there @@ -1046,17 +1577,16 @@ propagate_vals_accross_pass_through (struct cgraph_edge *cs, number of them and we would just make lattices bottom. */ if ((ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR) && ipa_edge_within_scc (cs)) - ret = set_lattice_contains_variable (dest_lat); + ret = dest_lat->set_contains_variable (); else for (src_val = src_lat->values; src_val; src_val = src_val->next) { tree cstval = ipa_get_jf_pass_through_result (jfunc, src_val->value); if (cstval) - ret |= add_scalar_value_to_lattice (dest_lat, cstval, cs, src_val, - src_idx); + ret |= dest_lat->add_value (cstval, cs, src_val, src_idx); else - ret |= set_lattice_contains_variable (dest_lat); + ret |= dest_lat->set_contains_variable (); } return ret; @@ -1067,26 +1597,25 @@ propagate_vals_accross_pass_through (struct cgraph_edge *cs, is the index of the source parameter. */ static bool -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) +propagate_vals_across_ancestor (struct cgraph_edge *cs, + struct ipa_jump_func *jfunc, + ipcp_lattice *src_lat, + ipcp_lattice *dest_lat, int src_idx) { - struct ipcp_value *src_val; + ipcp_value *src_val; bool ret = false; if (ipa_edge_within_scc (cs)) - return set_lattice_contains_variable (dest_lat); + return dest_lat->set_contains_variable (); for (src_val = src_lat->values; src_val; src_val = src_val->next) { tree t = ipa_get_jf_ancestor_result (jfunc, src_val->value); if (t) - ret |= add_scalar_value_to_lattice (dest_lat, t, cs, src_val, src_idx); + ret |= dest_lat->add_value (t, cs, src_val, src_idx); else - ret |= set_lattice_contains_variable (dest_lat); + ret |= dest_lat->set_contains_variable (); } return ret; @@ -1096,33 +1625,23 @@ propagate_vals_accross_ancestor (struct cgraph_edge *cs, edge CS and put the values into DEST_LAT. */ static bool -propagate_scalar_accross_jump_function (struct cgraph_edge *cs, - struct ipa_jump_func *jfunc, - struct ipcp_lattice *dest_lat) +propagate_scalar_across_jump_function (struct cgraph_edge *cs, + struct ipa_jump_func *jfunc, + ipcp_lattice *dest_lat) { if (dest_lat->bottom) return false; - if (jfunc->type == IPA_JF_CONST - || jfunc->type == IPA_JF_KNOWN_TYPE) + if (jfunc->type == IPA_JF_CONST) { - tree val; - - if (jfunc->type == IPA_JF_KNOWN_TYPE) - { - val = ipa_binfo_from_known_type_jfunc (jfunc); - if (!val) - return set_lattice_contains_variable (dest_lat); - } - else - val = ipa_get_jf_constant (jfunc); - return add_scalar_value_to_lattice (dest_lat, val, cs, NULL, 0); + tree val = ipa_get_jf_constant (jfunc); + return dest_lat->add_value (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; + ipcp_lattice *src_lat; int src_idx; bool ret; @@ -1133,30 +1652,288 @@ propagate_scalar_accross_jump_function (struct cgraph_edge *cs, src_lat = ipa_get_scalar_lat (caller_info, src_idx); if (src_lat->bottom) - return set_lattice_contains_variable (dest_lat); + return dest_lat->set_contains_variable (); /* 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); + return dest_lat->set_contains_variable (); if (jfunc->type == IPA_JF_PASS_THROUGH) - ret = propagate_vals_accross_pass_through (cs, jfunc, src_lat, - dest_lat, src_idx); + ret = propagate_vals_across_pass_through (cs, jfunc, src_lat, + dest_lat, src_idx); else - ret = propagate_vals_accross_ancestor (cs, jfunc, src_lat, dest_lat, - src_idx); + ret = propagate_vals_across_ancestor (cs, jfunc, src_lat, dest_lat, + src_idx); if (src_lat->contains_variable) - ret |= set_lattice_contains_variable (dest_lat); + ret |= dest_lat->set_contains_variable (); 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); + return dest_lat->set_contains_variable (); +} + +/* Propagate scalar values across jump function JFUNC that is associated with + edge CS and describes argument IDX and put the values into DEST_LAT. */ + +static bool +propagate_context_across_jump_function (cgraph_edge *cs, + ipa_jump_func *jfunc, int idx, + ipcp_lattice *dest_lat) +{ + ipa_edge_args *args = IPA_EDGE_REF (cs); + if (dest_lat->bottom) + return false; + bool ret = false; + bool added_sth = false; + bool type_preserved = true; + + ipa_polymorphic_call_context edge_ctx, *edge_ctx_ptr + = ipa_get_ith_polymorhic_call_context (args, idx); + + if (edge_ctx_ptr) + edge_ctx = *edge_ctx_ptr; + + if (jfunc->type == IPA_JF_PASS_THROUGH + || jfunc->type == IPA_JF_ANCESTOR) + { + struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); + int src_idx; + ipcp_lattice *src_lat; + + /* TODO: Once we figure out how to propagate speculations, it will + probably be a good idea to switch to speculation if type_preserved is + not set instead of punting. */ + if (jfunc->type == IPA_JF_PASS_THROUGH) + { + if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR) + goto prop_fail; + type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc); + src_idx = ipa_get_jf_pass_through_formal_id (jfunc); + } + else + { + type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc); + src_idx = ipa_get_jf_ancestor_formal_id (jfunc); + } + + src_lat = ipa_get_poly_ctx_lat (caller_info, src_idx); + /* 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))) + goto prop_fail; + + ipcp_value *src_val; + for (src_val = src_lat->values; src_val; src_val = src_val->next) + { + ipa_polymorphic_call_context cur = src_val->value; + + if (!type_preserved) + cur.possible_dynamic_type_change (cs->in_polymorphic_cdtor); + if (jfunc->type == IPA_JF_ANCESTOR) + cur.offset_by (ipa_get_jf_ancestor_offset (jfunc)); + /* TODO: In cases we know how the context is going to be used, + we can improve the result by passing proper OTR_TYPE. */ + cur.combine_with (edge_ctx); + if (!cur.useless_p ()) + { + if (src_lat->contains_variable + && !edge_ctx.equal_to (cur)) + ret |= dest_lat->set_contains_variable (); + ret |= dest_lat->add_value (cur, cs, src_val, src_idx); + added_sth = true; + } + } + + } + + prop_fail: + if (!added_sth) + { + if (!edge_ctx.useless_p ()) + ret |= dest_lat->add_value (edge_ctx, cs); + else + ret |= dest_lat->set_contains_variable (); + } + + return ret; +} + +/* Propagate bits across jfunc that is associated with + edge cs and update dest_lattice accordingly. */ + +bool +propagate_bits_across_jump_function (cgraph_edge *cs, int idx, + ipa_jump_func *jfunc, + ipcp_bits_lattice *dest_lattice) +{ + if (dest_lattice->bottom_p ()) + return false; + + enum availability availability; + cgraph_node *callee = cs->callee->function_symbol (&availability); + struct ipa_node_params *callee_info = IPA_NODE_REF (callee); + tree parm_type = ipa_get_type (callee_info, idx); + + /* For K&R C programs, ipa_get_type() could return NULL_TREE. + Avoid the transform for these cases. */ + if (!parm_type) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Setting dest_lattice to bottom, because" + " param %i type is NULL for %s\n", idx, + cs->callee->name ()); + + return dest_lattice->set_to_bottom (); + } + + unsigned precision = TYPE_PRECISION (parm_type); + signop sgn = TYPE_SIGN (parm_type); + + if (jfunc->type == IPA_JF_PASS_THROUGH + || jfunc->type == IPA_JF_ANCESTOR) + { + struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); + tree operand = NULL_TREE; + enum tree_code code; + unsigned src_idx; + + if (jfunc->type == IPA_JF_PASS_THROUGH) + { + code = ipa_get_jf_pass_through_operation (jfunc); + src_idx = ipa_get_jf_pass_through_formal_id (jfunc); + if (code != NOP_EXPR) + operand = ipa_get_jf_pass_through_operand (jfunc); + } + else + { + code = POINTER_PLUS_EXPR; + src_idx = ipa_get_jf_ancestor_formal_id (jfunc); + unsigned HOST_WIDE_INT offset = ipa_get_jf_ancestor_offset (jfunc) / BITS_PER_UNIT; + operand = build_int_cstu (size_type_node, offset); + } + + struct ipcp_param_lattices *src_lats + = ipa_get_parm_lattices (caller_info, src_idx); + + /* Try to propagate bits if src_lattice is bottom, but jfunc is known. + for eg consider: + int f(int x) + { + g (x & 0xff); + } + Assume lattice for x is bottom, however we can still propagate + result of x & 0xff == 0xff, which gets computed during ccp1 pass + and we store it in jump function during analysis stage. */ + + if (src_lats->bits_lattice.bottom_p () + && jfunc->bits) + return dest_lattice->meet_with (jfunc->bits->value, jfunc->bits->mask, + precision); + else + return dest_lattice->meet_with (src_lats->bits_lattice, precision, sgn, + code, operand); + } + + else if (jfunc->type == IPA_JF_ANCESTOR) + return dest_lattice->set_to_bottom (); + else if (jfunc->bits) + return dest_lattice->meet_with (jfunc->bits->value, jfunc->bits->mask, + precision); + else + return dest_lattice->set_to_bottom (); +} + +/* Emulate effects of unary OPERATION and/or conversion from SRC_TYPE to + DST_TYPE on value range in SRC_VR and store it to DST_VR. Return true if + the result is a range or an anti-range. */ + +static bool +ipa_vr_operation_and_type_effects (value_range *dst_vr, value_range *src_vr, + enum tree_code operation, + tree dst_type, tree src_type) +{ + memset (dst_vr, 0, sizeof (*dst_vr)); + extract_range_from_unary_expr (dst_vr, operation, dst_type, src_vr, src_type); + if (dst_vr->type == VR_RANGE || dst_vr->type == VR_ANTI_RANGE) + return true; + else + return false; +} + +/* Propagate value range across jump function JFUNC that is associated with + edge CS with param of callee of PARAM_TYPE and update DEST_PLATS + accordingly. */ + +static bool +propagate_vr_across_jump_function (cgraph_edge *cs, ipa_jump_func *jfunc, + struct ipcp_param_lattices *dest_plats, + tree param_type) +{ + ipcp_vr_lattice *dest_lat = &dest_plats->m_value_range; + + if (dest_lat->bottom_p ()) + return false; + + if (!param_type + || (!INTEGRAL_TYPE_P (param_type) + && !POINTER_TYPE_P (param_type))) + return dest_lat->set_to_bottom (); + + if (jfunc->type == IPA_JF_PASS_THROUGH) + { + enum tree_code operation = ipa_get_jf_pass_through_operation (jfunc); + + if (TREE_CODE_CLASS (operation) == tcc_unary) + { + struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); + int src_idx = ipa_get_jf_pass_through_formal_id (jfunc); + tree operand_type = ipa_get_type (caller_info, src_idx); + struct ipcp_param_lattices *src_lats + = ipa_get_parm_lattices (caller_info, src_idx); + + if (src_lats->m_value_range.bottom_p ()) + return dest_lat->set_to_bottom (); + value_range vr; + if (ipa_vr_operation_and_type_effects (&vr, + &src_lats->m_value_range.m_vr, + operation, param_type, + operand_type)) + return dest_lat->meet_with (&vr); + } + } + else if (jfunc->type == IPA_JF_CONST) + { + tree val = ipa_get_jf_constant (jfunc); + if (TREE_CODE (val) == INTEGER_CST) + { + val = fold_convert (param_type, val); + if (TREE_OVERFLOW_P (val)) + val = drop_tree_overflow (val); + + value_range tmpvr; + memset (&tmpvr, 0, sizeof (tmpvr)); + tmpvr.type = VR_RANGE; + tmpvr.min = val; + tmpvr.max = val; + return dest_lat->meet_with (&tmpvr); + } + } + + value_range vr; + if (jfunc->m_vr + && ipa_vr_operation_and_type_effects (&vr, jfunc->m_vr, NOP_EXPR, + param_type, + TREE_TYPE (jfunc->m_vr->min))) + return dest_lat->meet_with (&vr); + else + return dest_lat->set_to_bottom (); } /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches @@ -1206,15 +1983,15 @@ merge_agg_lats_step (struct ipcp_param_lattices *dest_plats, set_agg_lats_to_bottom (dest_plats); return false; } - *change |= set_lattice_contains_variable (**aglat); + *change |= (**aglat)->set_contains_variable (); *aglat = &(**aglat)->next; } if (**aglat && (**aglat)->offset == offset) { if ((**aglat)->size != val_size - || ((**aglat)->next - && (**aglat)->next->offset < offset + val_size)) + || ((**aglat)->next + && (**aglat)->next->offset < offset + val_size)) { set_agg_lats_to_bottom (dest_plats); return false; @@ -1235,7 +2012,7 @@ merge_agg_lats_step (struct ipcp_param_lattices *dest_plats, if (dest_plats->aggs_count == PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS)) return false; dest_plats->aggs_count++; - new_al = (struct ipcp_agg_lattice *) pool_alloc (ipcp_agg_lattice_pool); + new_al = ipcp_agg_lattice_pool.allocate (); memset (new_al, 0, sizeof (*new_al)); new_al->offset = offset; @@ -1257,7 +2034,7 @@ set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice *aglat) bool ret = false; while (aglat) { - ret |= set_lattice_contains_variable (aglat); + ret |= aglat->set_contains_variable (); aglat = aglat->next; } return ret; @@ -1302,16 +2079,16 @@ merge_aggregate_lattices (struct cgraph_edge *cs, dst_aglat = &(*dst_aglat)->next; if (src_aglat->bottom) { - ret |= set_lattice_contains_variable (new_al); + ret |= new_al->set_contains_variable (); continue; } if (src_aglat->contains_variable) - ret |= set_lattice_contains_variable (new_al); - for (struct ipcp_value *val = src_aglat->values; + ret |= new_al->set_contains_variable (); + for (ipcp_value *val = src_aglat->values; val; val = val->next) - ret |= add_value_to_lattice (new_al, val->value, cs, val, src_idx, - src_aglat->offset); + ret |= new_al->add_value (val->value, cs, val, src_idx, + src_aglat->offset); } else if (dest_plats->aggs_bottom) return true; @@ -1337,9 +2114,9 @@ agg_pass_through_permissible_p (struct ipcp_param_lattices *src_plats, edge CS and put the values into DEST_LAT. */ static bool -propagate_aggs_accross_jump_function (struct cgraph_edge *cs, - struct ipa_jump_func *jfunc, - struct ipcp_param_lattices *dest_plats) +propagate_aggs_across_jump_function (struct cgraph_edge *cs, + struct ipa_jump_func *jfunc, + struct ipcp_param_lattices *dest_plats) { bool ret = false; @@ -1408,7 +2185,7 @@ propagate_aggs_accross_jump_function (struct cgraph_edge *cs, if (merge_agg_lats_step (dest_plats, item->offset, val_size, &aglat, pre_existing, &ret)) { - ret |= add_value_to_lattice (*aglat, item->value, cs, NULL, 0, 0); + ret |= (*aglat)->add_value (item->value, cs, NULL, 0, 0); aglat = &(*aglat)->next; } else if (dest_plats->aggs_bottom) @@ -1423,15 +2200,27 @@ propagate_aggs_accross_jump_function (struct cgraph_edge *cs, return ret; } +/* Return true if on the way cfrom CS->caller to the final (non-alias and + non-thunk) destination, the call passes through a thunk. */ + +static bool +call_passes_through_thunk_p (cgraph_edge *cs) +{ + cgraph_node *alias_or_thunk = cs->callee; + while (alias_or_thunk->alias) + alias_or_thunk = alias_or_thunk->get_alias_target (); + return alias_or_thunk->thunk.thunk_p; +} + /* Propagate constants from the caller to the callee of CS. INFO describes the caller. */ static bool -propagate_constants_accross_call (struct cgraph_edge *cs) +propagate_constants_across_call (struct cgraph_edge *cs) { struct ipa_node_params *callee_info; enum availability availability; - struct cgraph_node *callee, *alias_or_thunk; + cgraph_node *callee; struct ipa_edge_args *args; bool ret = false; int i, args_count, parms_count; @@ -1448,13 +2237,28 @@ propagate_constants_accross_call (struct cgraph_edge *cs) if (parms_count == 0) return false; + /* No propagation through instrumentation thunks is available yet. + It should be possible with proper mapping of call args and + instrumented callee params in the propagation loop below. But + this case mostly occurs when legacy code calls instrumented code + and it is not a primary target for optimizations. + We detect instrumentation thunks in aliases and thunks chain by + checking instrumentation_clone flag for chain source and target. + Going through instrumentation thunks we always have it changed + from 0 to 1 and all other nodes do not change it. */ + if (!cs->callee->instrumentation_clone + && callee->instrumentation_clone) + { + for (i = 0; i < parms_count; i++) + ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, + i)); + return ret; + } + /* 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 = alias_or_thunk->get_alias_target (); - if (alias_or_thunk->thunk.thunk_p) + if (call_passes_through_thunk_p (cs)) { ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, 0)); @@ -1467,16 +2271,27 @@ propagate_constants_accross_call (struct cgraph_edge *cs) { struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i); struct ipcp_param_lattices *dest_plats; + tree param_type = ipa_get_type (callee_info, i); dest_plats = ipa_get_parm_lattices (callee_info, i); if (availability == AVAIL_INTERPOSABLE) ret |= set_all_contains_variable (dest_plats); else { - ret |= propagate_scalar_accross_jump_function (cs, jump_func, - &dest_plats->itself); - ret |= propagate_aggs_accross_jump_function (cs, jump_func, - dest_plats); + ret |= propagate_scalar_across_jump_function (cs, jump_func, + &dest_plats->itself); + ret |= propagate_context_across_jump_function (cs, jump_func, i, + &dest_plats->ctxlat); + ret + |= propagate_bits_across_jump_function (cs, i, jump_func, + &dest_plats->bits_lattice); + ret |= propagate_aggs_across_jump_function (cs, jump_func, + dest_plats); + if (opt_for_fn (callee->decl, flag_ipa_vrp)) + ret |= propagate_vr_across_jump_function (cs, jump_func, + dest_plats, param_type); + else + ret |= dest_plats->m_value_range.set_to_bottom (); } } for (; i < parms_count; i++) @@ -1486,25 +2301,26 @@ propagate_constants_accross_call (struct cgraph_edge *cs) } /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS - (which can contain both constants and binfos), KNOWN_BINFOS, KNOWN_AGGS or - AGG_REPS return the destination. The latter three can be NULL. If AGG_REPS - is not NULL, KNOWN_AGGS is ignored. */ + KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter + three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */ static tree ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie, - vec known_vals, - vec known_binfos, + vec known_csts, + vec known_contexts, vec known_aggs, - struct ipa_agg_replacement_value *agg_reps) + struct ipa_agg_replacement_value *agg_reps, + bool *speculative) { int param_index = ie->indirect_info->param_index; - HOST_WIDE_INT token, anc_offset; - tree otr_type; + HOST_WIDE_INT anc_offset; tree t; tree target = NULL; + *speculative = false; + if (param_index == -1 - || known_vals.length () <= (unsigned int) param_index) + || known_csts.length () <= (unsigned int) param_index) return NULL_TREE; if (!ie->indirect_info->polymorphic) @@ -1513,9 +2329,9 @@ ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie, if (ie->indirect_info->agg_contents) { - if (agg_reps) + t = NULL; + if (agg_reps && ie->indirect_info->guaranteed_unmodified) { - t = NULL; while (agg_reps) { if (agg_reps->index == param_index @@ -1528,34 +2344,40 @@ ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie, agg_reps = agg_reps->next; } } - else if (known_aggs.length () > (unsigned int) param_index) + if (!t) { struct ipa_agg_jump_function *agg; - agg = known_aggs[param_index]; - t = ipa_find_agg_cst_for_param (agg, ie->indirect_info->offset, - ie->indirect_info->by_ref); + if (known_aggs.length () > (unsigned int) param_index) + agg = known_aggs[param_index]; + else + agg = NULL; + bool from_global_constant; + t = ipa_find_agg_cst_for_param (agg, known_csts[param_index], + ie->indirect_info->offset, + ie->indirect_info->by_ref, + &from_global_constant); + if (t + && !from_global_constant + && !ie->indirect_info->guaranteed_unmodified) + t = NULL_TREE; } - else - t = NULL; } else - t = known_vals[param_index]; + t = known_csts[param_index]; - if (t && - TREE_CODE (t) == ADDR_EXPR + if (t + && TREE_CODE (t) == ADDR_EXPR && TREE_CODE (TREE_OPERAND (t, 0)) == FUNCTION_DECL) return TREE_OPERAND (t, 0); else return NULL_TREE; } - if (!flag_devirtualize) + if (!opt_for_fn (ie->caller->decl, flag_devirtualize)) return NULL_TREE; gcc_assert (!ie->indirect_info->agg_contents); - token = ie->indirect_info->otr_token; anc_offset = ie->indirect_info->offset; - otr_type = ie->indirect_info->otr_type; t = NULL; @@ -1580,10 +2402,10 @@ ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie, if (!t && known_aggs.length () > (unsigned int) param_index && !ie->indirect_info->by_ref) { - struct ipa_agg_jump_function *agg; - agg = known_aggs[param_index]; - t = ipa_find_agg_cst_for_param (agg, ie->indirect_info->offset, - true); + struct ipa_agg_jump_function *agg; + agg = known_aggs[param_index]; + t = ipa_find_agg_cst_for_param (agg, known_csts[param_index], + ie->indirect_info->offset, true); } /* If we found the virtual table pointer, lookup the target. */ @@ -1593,89 +2415,131 @@ ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie, unsigned HOST_WIDE_INT offset; if (vtable_pointer_value_to_vtable (t, &vtable, &offset)) { + bool can_refer; target = gimple_get_virt_method_for_vtable (ie->indirect_info->otr_token, - vtable, offset); - if (target) + vtable, offset, &can_refer); + if (can_refer) { - if ((TREE_CODE (TREE_TYPE (target)) == FUNCTION_TYPE - && DECL_FUNCTION_CODE (target) == BUILT_IN_UNREACHABLE) + if (!target + || (TREE_CODE (TREE_TYPE (target)) == FUNCTION_TYPE + && DECL_FUNCTION_CODE (target) == BUILT_IN_UNREACHABLE) || !possible_polymorphic_call_target_p (ie, cgraph_node::get (target))) - target = ipa_impossible_devirt_target (ie, target); - return target; + { + /* Do not speculate builtin_unreachable, it is stupid! */ + if (ie->indirect_info->vptr_changed) + return NULL; + target = ipa_impossible_devirt_target (ie, target); + } + *speculative = ie->indirect_info->vptr_changed; + if (!*speculative) + return target; } } } - /* Did we work out BINFO via type propagation? */ - if (!t && known_binfos.length () > (unsigned int) param_index) - t = known_binfos[param_index]; - /* Or do we know the constant value of pointer? */ + /* Do we know the constant value of pointer? */ if (!t) - t = known_vals[param_index]; - if (!t) - return NULL_TREE; + t = known_csts[param_index]; - if (TREE_CODE (t) != TREE_BINFO) + gcc_checking_assert (!t || TREE_CODE (t) != TREE_BINFO); + + ipa_polymorphic_call_context context; + if (known_contexts.length () > (unsigned int) param_index) { - ipa_polymorphic_call_context context; - vec targets; - bool final; + context = known_contexts[param_index]; + context.offset_by (anc_offset); + if (ie->indirect_info->vptr_changed) + context.possible_dynamic_type_change (ie->in_polymorphic_cdtor, + ie->indirect_info->otr_type); + if (t) + { + ipa_polymorphic_call_context ctx2 = ipa_polymorphic_call_context + (t, ie->indirect_info->otr_type, anc_offset); + if (!ctx2.useless_p ()) + context.combine_with (ctx2, ie->indirect_info->otr_type); + } + } + else if (t) + { + context = ipa_polymorphic_call_context (t, ie->indirect_info->otr_type, + anc_offset); + if (ie->indirect_info->vptr_changed) + context.possible_dynamic_type_change (ie->in_polymorphic_cdtor, + ie->indirect_info->otr_type); + } + else + return NULL_TREE; - if (!get_polymorphic_call_info_from_invariant - (&context, t, ie->indirect_info->otr_type, - anc_offset)) - return NULL_TREE; - targets = possible_polymorphic_call_targets - (ie->indirect_info->otr_type, - ie->indirect_info->otr_token, - context, &final); - if (!final || targets.length () > 1) - return NULL_TREE; - if (targets.length () == 1) - target = targets[0]->decl; + vec targets; + bool final; + + targets = possible_polymorphic_call_targets + (ie->indirect_info->otr_type, + ie->indirect_info->otr_token, + context, &final); + if (!final || targets.length () > 1) + { + struct cgraph_node *node; + if (*speculative) + return target; + if (!opt_for_fn (ie->caller->decl, flag_devirtualize_speculatively) + || ie->speculative || !ie->maybe_hot_p ()) + return NULL; + node = try_speculative_devirtualization (ie->indirect_info->otr_type, + ie->indirect_info->otr_token, + context); + if (node) + { + *speculative = true; + target = node->decl; + } else - target = ipa_impossible_devirt_target (ie, NULL_TREE); + return NULL; } else { - tree binfo; - - binfo = get_binfo_at_offset (t, anc_offset, otr_type); - if (!binfo) - return NULL_TREE; - target = gimple_get_virt_method_for_binfo (token, binfo); + *speculative = false; + if (targets.length () == 1) + target = targets[0]->decl; + else + target = ipa_impossible_devirt_target (ie, NULL_TREE); } if (target && !possible_polymorphic_call_target_p (ie, cgraph_node::get (target))) - target = ipa_impossible_devirt_target (ie, target); + { + if (*speculative) + return NULL; + target = ipa_impossible_devirt_target (ie, target); + } return target; } -/* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS - (which can contain both constants and binfos), KNOWN_BINFOS (which can be - NULL) or KNOWN_AGGS (which also can be NULL) return the destination. */ +/* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS, + KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL) + return the destination. */ tree ipa_get_indirect_edge_target (struct cgraph_edge *ie, - vec known_vals, - vec known_binfos, - vec known_aggs) + vec known_csts, + vec known_contexts, + vec known_aggs, + bool *speculative) { - return ipa_get_indirect_edge_target_1 (ie, known_vals, known_binfos, - known_aggs, NULL); + return ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts, + known_aggs, NULL, speculative); } /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS - and KNOWN_BINFOS. */ + and KNOWN_CONTEXTS. */ static int devirtualization_time_bonus (struct cgraph_node *node, vec known_csts, - vec known_binfos, + vec known_contexts, vec known_aggs) { struct cgraph_edge *ie; @@ -1684,12 +2548,13 @@ devirtualization_time_bonus (struct cgraph_node *node, for (ie = node->indirect_calls; ie; ie = ie->next_callee) { struct cgraph_node *callee; - struct inline_summary *isummary; + struct ipa_fn_summary *isummary; enum availability avail; tree target; + bool speculative; - target = ipa_get_indirect_edge_target (ie, known_csts, known_binfos, - known_aggs); + target = ipa_get_indirect_edge_target (ie, known_csts, known_contexts, + known_aggs, &speculative); if (!target) continue; @@ -1701,19 +2566,19 @@ devirtualization_time_bonus (struct cgraph_node *node, callee = callee->function_symbol (&avail); if (avail < AVAIL_AVAILABLE) continue; - isummary = inline_summary (callee); + isummary = ipa_fn_summaries->get (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; + res += 31 / ((int)speculative + 1); else if (isummary->size <= MAX_INLINE_INSNS_AUTO / 2) - res += 15; + res += 15 / ((int)speculative + 1); else if (isummary->size <= MAX_INLINE_INSNS_AUTO || DECL_DECLARED_INLINE_P (callee->decl)) - res += 7; + res += 7 / ((int)speculative + 1); } return res; @@ -1722,7 +2587,7 @@ devirtualization_time_bonus (struct cgraph_node *node, /* Return time bonus incurred because of HINTS. */ static int -hint_time_bonus (inline_hints hints) +hint_time_bonus (ipa_hints hints) { int result = 0; if (hints & (INLINE_HINT_loop_iterations | INLINE_HINT_loop_stride)) @@ -1732,34 +2597,60 @@ hint_time_bonus (inline_hints hints) return result; } +/* If there is a reason to penalize the function described by INFO in the + cloning goodness evaluation, do so. */ + +static inline int64_t +incorporate_penalties (ipa_node_params *info, int64_t evaluation) +{ + if (info->node_within_scc) + evaluation = (evaluation + * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY))) / 100; + + if (info->node_calling_single_call) + evaluation = (evaluation + * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY))) + / 100; + + return evaluation; +} + /* 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 good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit, - int freq_sum, gcov_type count_sum, int size_cost) + int freq_sum, profile_count count_sum, int size_cost) { if (time_benefit == 0 - || !flag_ipa_cp_clone - || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl))) + || !opt_for_fn (node->decl, flag_ipa_cp_clone) + || node->optimize_for_size_p ()) return false; gcc_assert (size_cost > 0); - if (max_count) + struct ipa_node_params *info = IPA_NODE_REF (node); + if (max_count > profile_count::zero ()) { - int factor = (count_sum * 1000) / max_count; + int factor = RDIV (count_sum.probability_in + (max_count).to_reg_br_prob_base () + * 1000, REG_BR_PROB_BASE); int64_t evaluation = (((int64_t) time_benefit * factor) / size_cost); + evaluation = incorporate_penalties (info, evaluation); 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: " "%"PRId64 + { + fprintf (dump_file, " good_cloning_opportunity_p (time: %i, " + "size: %i, count_sum: ", time_benefit, size_cost); + count_sum.dump (dump_file); + fprintf (dump_file, "%s%s) -> evaluation: " "%" PRId64 ", threshold: %i\n", - time_benefit, size_cost, (HOST_WIDE_INT) count_sum, + info->node_within_scc ? ", scc" : "", + info->node_calling_single_call ? ", single_call" : "", evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD)); + } return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD); } @@ -1767,13 +2658,16 @@ good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit, { int64_t evaluation = (((int64_t) time_benefit * freq_sum) / size_cost); + evaluation = incorporate_penalties (info, evaluation); if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " good_cloning_opportunity_p (time: %i, " - "size: %i, freq_sum: %i) -> evaluation: " - "%"PRId64 ", threshold: %i\n", - time_benefit, size_cost, freq_sum, evaluation, - PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD)); + "size: %i, freq_sum: %i%s%s) -> evaluation: " + "%" PRId64 ", threshold: %i\n", + time_benefit, size_cost, freq_sum, + info->node_within_scc ? ", scc" : "", + info->node_calling_single_call ? ", single_call" : "", + evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD)); return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD); } @@ -1795,7 +2689,7 @@ context_independent_aggregate_values (struct ipcp_param_lattices *plats) for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next) - if (ipa_lat_is_single_const (aglat)) + if (aglat->is_single_const ()) { struct ipa_agg_jf_item item; item.offset = aglat->offset; @@ -1805,25 +2699,27 @@ context_independent_aggregate_values (struct ipcp_param_lattices *plats) return res; } -/* Allocate KNOWN_CSTS, KNOWN_BINFOS and, if non-NULL, KNOWN_AGGS 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. */ +/* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS 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 *known_csts, - vec *known_binfos, - vec *known_aggs, - int *removable_params_cost) + vec *known_csts, + vec + *known_contexts, + vec *known_aggs, + int *removable_params_cost) { int i, count = ipa_get_param_count (info); bool ret = false; known_csts->create (0); - known_binfos->create (0); + known_contexts->create (0); known_csts->safe_grow_cleared (count); - known_binfos->safe_grow_cleared (count); + known_contexts->safe_grow_cleared (count); if (known_aggs) { known_aggs->create (0); @@ -1833,36 +2729,35 @@ gather_context_independent_values (struct ipa_node_params *info, if (removable_params_cost) *removable_params_cost = 0; - for (i = 0; i < count ; i++) + for (i = 0; i < count; i++) { struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); - struct ipcp_lattice *lat = &plats->itself; + ipcp_lattice *lat = &plats->itself; - if (ipa_lat_is_single_const (lat)) + if (lat->is_single_const ()) { - struct ipcp_value *val = lat->values; - if (TREE_CODE (val->value) != TREE_BINFO) - { - (*known_csts)[i] = val->value; - if (removable_params_cost) - *removable_params_cost - += estimate_move_cost (TREE_TYPE (val->value), false); - ret = true; - } - else if (plats->virt_call) - { - (*known_binfos)[i] = val->value; - ret = true; - } - else if (removable_params_cost - && !ipa_is_param_used (info, i)) - *removable_params_cost += ipa_get_param_move_cost (info, i); + ipcp_value *val = lat->values; + gcc_checking_assert (TREE_CODE (val->value) != TREE_BINFO); + (*known_csts)[i] = val->value; + if (removable_params_cost) + *removable_params_cost + += estimate_move_cost (TREE_TYPE (val->value), false); + ret = true; } else if (removable_params_cost && !ipa_is_param_used (info, i)) *removable_params_cost += ipa_get_param_move_cost (info, i); + if (!ipa_is_param_used (info, i)) + continue; + + ipcp_lattice *ctxlat = &plats->ctxlat; + /* Do not account known context as reason for cloning. We can see + if it permits devirtualization. */ + if (ctxlat->is_single_const ()) + (*known_contexts)[i] = ctxlat->values->value; + if (known_aggs) { vec *agg_items; @@ -1899,6 +2794,47 @@ agg_jmp_p_vec_for_t_vec (vec known_aggs) return ret; } +/* Perform time and size measurement of NODE with the context given in + KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost + given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of + all context-independent removable parameters and EST_MOVE_COST of estimated + movement of the considered parameter and store it into VAL. */ + +static void +perform_estimation_of_a_value (cgraph_node *node, vec known_csts, + vec known_contexts, + vec known_aggs_ptrs, + int removable_params_cost, + int est_move_cost, ipcp_value_base *val) +{ + int size, time_benefit; + sreal time, base_time; + ipa_hints hints; + + estimate_ipcp_clone_size_and_time (node, known_csts, known_contexts, + known_aggs_ptrs, &size, &time, + &base_time, &hints); + base_time -= time; + if (base_time > 65535) + base_time = 65535; + time_benefit = base_time.to_int () + + devirtualization_time_bonus (node, known_csts, known_contexts, + known_aggs_ptrs) + + hint_time_bonus (hints) + + removable_params_cost + est_move_cost; + + gcc_checking_assert (size >=0); + /* The inliner-heuristics based estimates may think that in certain + contexts some functions do not have any size at all but we want + all specializations to have at least a tiny cost, not least not to + divide by zero. */ + if (size == 0) + size = 1; + + val->local_time_benefit = time_benefit; + val->local_size_cost = size; +} + /* Iterate over known values of parameters of NODE and estimate the local effects in terms of time and size they have. */ @@ -1907,63 +2843,65 @@ estimate_local_effects (struct cgraph_node *node) { struct ipa_node_params *info = IPA_NODE_REF (node); int i, count = ipa_get_param_count (info); - vec known_csts, known_binfos; + vec known_csts; + vec known_contexts; vec known_aggs; vec known_aggs_ptrs; bool always_const; - int base_time = inline_summary (node)->time; int removable_params_cost; 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", - node->name (), node->order, base_time); + fprintf (dump_file, "\nEstimating effects for %s.\n", node->dump_name ()); always_const = gather_context_independent_values (info, &known_csts, - &known_binfos, &known_aggs, + &known_contexts, &known_aggs, &removable_params_cost); known_aggs_ptrs = agg_jmp_p_vec_for_t_vec (known_aggs); - if (always_const) + int devirt_bonus = devirtualization_time_bonus (node, known_csts, + known_contexts, known_aggs_ptrs); + if (always_const || devirt_bonus + || (removable_params_cost && node->local.can_change_signature)) { struct caller_statistics stats; - inline_hints hints; - int time, size; + ipa_hints hints; + sreal time, base_time; + int size; init_caller_stats (&stats); node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats, false); - estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos, - known_aggs_ptrs, &size, &time, &hints); - time -= devirtualization_time_bonus (node, known_csts, known_binfos, - known_aggs_ptrs); + estimate_ipcp_clone_size_and_time (node, known_csts, known_contexts, + known_aggs_ptrs, &size, &time, + &base_time, &hints); + time -= devirt_bonus; time -= hint_time_bonus (hints); 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); + "time_benefit: %f\n", size, (base_time - time).to_double ()); - if (size <= 0 - || node->will_be_removed_from_program_if_no_direct_calls_p ()) + if (size <= 0 || node->local.local) { info->do_clone_for_all_contexts = true; - base_time = time; 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, + else if (good_cloning_opportunity_p (node, + MAX ((base_time - time).to_int (), + 65536), stats.freq_sum, stats.count_sum, size)) { if (size + overall_size <= max_new_size) { info->do_clone_for_all_contexts = true; - base_time = time; overall_size += size; if (dump_file) @@ -1975,76 +2913,82 @@ estimate_local_effects (struct cgraph_node *node) "max_new_size would be reached with %li.\n", size + overall_size); } + else if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " Not cloning for all contexts because " + "!good_cloning_opportunity_p.\n"); + } - for (i = 0; i < count ; i++) + for (i = 0; i < count; i++) { struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); - struct ipcp_lattice *lat = &plats->itself; - struct ipcp_value *val; - int emc; + ipcp_lattice *lat = &plats->itself; + ipcp_value *val; if (lat->bottom || !lat->values - || known_csts[i] - || known_binfos[i]) + || known_csts[i]) continue; for (val = lat->values; val; val = val->next) { - int time, size, time_benefit; - inline_hints hints; + gcc_checking_assert (TREE_CODE (val->value) != TREE_BINFO); + known_csts[i] = val->value; - if (TREE_CODE (val->value) != TREE_BINFO) - { - known_csts[i] = val->value; - known_binfos[i] = NULL_TREE; - emc = estimate_move_cost (TREE_TYPE (val->value), true); - } - else if (plats->virt_call) + int emc = estimate_move_cost (TREE_TYPE (val->value), true); + perform_estimation_of_a_value (node, known_csts, known_contexts, + known_aggs_ptrs, + removable_params_cost, emc, val); + + if (dump_file && (dump_flags & TDF_DETAILS)) { - known_csts[i] = NULL_TREE; - known_binfos[i] = val->value; - emc = 0; + fprintf (dump_file, " - estimates for value "); + print_ipcp_constant_value (dump_file, val->value); + fprintf (dump_file, " for "); + ipa_dump_param (dump_file, info, i); + fprintf (dump_file, ": time_benefit: %i, size: %i\n", + val->local_time_benefit, val->local_size_cost); } - else - continue; + } + known_csts[i] = NULL_TREE; + } + + for (i = 0; i < count; i++) + { + struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); + + if (!plats->virt_call) + continue; + + ipcp_lattice *ctxlat = &plats->ctxlat; + ipcp_value *val; + + if (ctxlat->bottom + || !ctxlat->values + || !known_contexts[i].useless_p ()) + continue; - estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos, - known_aggs_ptrs, &size, &time, - &hints); - time_benefit = base_time - time - + devirtualization_time_bonus (node, known_csts, known_binfos, - known_aggs_ptrs) - + hint_time_bonus (hints) - + removable_params_cost + emc; - - gcc_checking_assert (size >=0); - /* The inliner-heuristics based estimates may think that in certain - contexts some functions do not have any size at all but we want - all specializations to have at least a tiny cost, not least not to - divide by zero. */ - if (size == 0) - size = 1; + for (val = ctxlat->values; val; val = val->next) + { + known_contexts[i] = val->value; + perform_estimation_of_a_value (node, known_csts, known_contexts, + known_aggs_ptrs, + removable_params_cost, 0, val); if (dump_file && (dump_flags & TDF_DETAILS)) { - fprintf (dump_file, " - estimates for value "); + fprintf (dump_file, " - estimates for polymorphic context "); print_ipcp_constant_value (dump_file, val->value); fprintf (dump_file, " for "); ipa_dump_param (dump_file, info, i); fprintf (dump_file, ": time_benefit: %i, size: %i\n", - time_benefit, size); + val->local_time_benefit, val->local_size_cost); } - - val->local_time_benefit = time_benefit; - val->local_size_cost = size; } - known_binfos[i] = NULL_TREE; - known_csts[i] = NULL_TREE; + known_contexts[i] = ipa_polymorphic_call_context (); } - for (i = 0; i < count ; i++) + for (i = 0; i < count; i++) { struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); struct ipa_agg_jump_function *ajf; @@ -2056,58 +3000,48 @@ estimate_local_effects (struct cgraph_node *node) ajf = &known_aggs[i]; for (aglat = plats->aggs; aglat; aglat = aglat->next) { - struct ipcp_value *val; + ipcp_value *val; if (aglat->bottom || !aglat->values /* If the following is true, the one value is in known_aggs. */ || (!plats->aggs_contain_variable - && ipa_lat_is_single_const (aglat))) + && aglat->is_single_const ())) continue; for (val = aglat->values; val; val = val->next) { - int time, size, time_benefit; struct ipa_agg_jf_item item; - inline_hints hints; item.offset = aglat->offset; item.value = val->value; vec_safe_push (ajf->items, item); - estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos, - known_aggs_ptrs, &size, &time, - &hints); - time_benefit = base_time - time - + devirtualization_time_bonus (node, known_csts, known_binfos, - known_aggs_ptrs) - + hint_time_bonus (hints); - gcc_checking_assert (size >=0); - if (size == 0) - size = 1; + perform_estimation_of_a_value (node, known_csts, known_contexts, + known_aggs_ptrs, + removable_params_cost, 0, val); 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 "); - ipa_dump_param (dump_file, info, i); + ipa_dump_param (dump_file, info, i); fprintf (dump_file, "[%soffset: " HOST_WIDE_INT_PRINT_DEC - "]: time_benefit: %i, size: %i\n", - plats->aggs_by_ref ? "ref " : "", - aglat->offset, time_benefit, size); + "]: time_benefit: %i, size: %i\n", + plats->aggs_by_ref ? "ref " : "", + aglat->offset, + val->local_time_benefit, val->local_size_cost); } - val->local_time_benefit = time_benefit; - val->local_size_cost = size; ajf->items->pop (); } } } - for (i = 0; i < count ; i++) + for (i = 0; i < count; i++) vec_free (known_aggs[i].items); known_csts.release (); - known_binfos.release (); + known_contexts.release (); known_aggs.release (); known_aggs_ptrs.release (); } @@ -2116,12 +3050,11 @@ estimate_local_effects (struct cgraph_node *node) /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the topological sort of values. */ -static void -add_val_to_toposort (struct ipcp_value *cur_val) +template +void +value_topo_info::add_val (ipcp_value *cur_val) { - static int dfs_counter = 0; - static struct ipcp_value *stack; - struct ipcp_value_source *src; + ipcp_value_source *src; if (cur_val->dfs) return; @@ -2139,7 +3072,7 @@ add_val_to_toposort (struct ipcp_value *cur_val) { if (src->val->dfs == 0) { - add_val_to_toposort (src->val); + add_val (src->val); if (src->val->low_link < cur_val->low_link) cur_val->low_link = src->val->low_link; } @@ -2150,7 +3083,7 @@ add_val_to_toposort (struct ipcp_value *cur_val) if (cur_val->dfs == cur_val->low_link) { - struct ipcp_value *v, *scc_list = NULL; + ipcp_value *v, *scc_list = NULL; do { @@ -2172,27 +3105,40 @@ add_val_to_toposort (struct ipcp_value *cur_val) they are not there yet. */ static void -add_all_node_vals_to_toposort (struct cgraph_node *node) +add_all_node_vals_to_toposort (cgraph_node *node, ipa_topo_info *topo) { struct ipa_node_params *info = IPA_NODE_REF (node); int i, count = ipa_get_param_count (info); - for (i = 0; i < count ; i++) + for (i = 0; i < count; i++) { struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); - struct ipcp_lattice *lat = &plats->itself; + ipcp_lattice *lat = &plats->itself; struct ipcp_agg_lattice *aglat; - struct ipcp_value *val; if (!lat->bottom) - for (val = lat->values; val; val = val->next) - add_val_to_toposort (val); + { + ipcp_value *val; + for (val = lat->values; val; val = val->next) + topo->constants.add_val (val); + } if (!plats->aggs_bottom) for (aglat = plats->aggs; aglat; aglat = aglat->next) if (!aglat->bottom) - for (val = aglat->values; val; val = val->next) - add_val_to_toposort (val); + { + ipcp_value *val; + for (val = aglat->values; val; val = val->next) + topo->constants.add_val (val); + } + + ipcp_lattice *ctxlat = &plats->ctxlat; + if (!ctxlat->bottom) + { + ipcp_value *ctxval; + for (ctxval = ctxlat->values; ctxval; ctxval = ctxval->next) + topo->contexts.add_val (ctxval); + } } } @@ -2201,7 +3147,7 @@ add_all_node_vals_to_toposort (struct cgraph_node *node) connected components. */ static void -propagate_constants_topo (struct topo_info *topo) +propagate_constants_topo (struct ipa_topo_info *topo) { int i; @@ -2223,9 +3169,12 @@ propagate_constants_topo (struct topo_info *topo) struct cgraph_edge *cs; for (cs = v->callees; cs; cs = cs->next_callee) - if (ipa_edge_within_scc (cs) - && propagate_constants_accross_call (cs)) - push_node_to_stack (topo, cs->callee); + if (ipa_edge_within_scc (cs)) + { + IPA_NODE_REF (v)->node_within_scc = true; + if (propagate_constants_across_call (cs)) + push_node_to_stack (topo, cs->callee->function_symbol ()); + } v = pop_node_from_stack (topo); } @@ -2238,10 +3187,10 @@ propagate_constants_topo (struct topo_info *topo) struct cgraph_edge *cs; estimate_local_effects (v); - add_all_node_vals_to_toposort (v); + add_all_node_vals_to_toposort (v, topo); for (cs = v->callees; cs; cs = cs->next_callee) if (!ipa_edge_within_scc (cs)) - propagate_constants_accross_call (cs); + propagate_constants_across_call (cs); } cycle_nodes.release (); } @@ -2264,15 +3213,16 @@ safe_add (int a, int b) /* Propagate the estimated effects of individual values along the topological from the dependent values to those they depend on. */ -static void -propagate_effects (void) +template +void +value_topo_info::propagate_effects () { - struct ipcp_value *base; + ipcp_value *base; for (base = values_topo; base; base = base->topo_next) { - struct ipcp_value_source *src; - struct ipcp_value *val; + ipcp_value_source *src; + ipcp_value *val; int time = 0, size = 0; for (val = base; val; val = val->scc_next) @@ -2296,26 +3246,22 @@ propagate_effects (void) } -/* Propagate constants, binfos and their effects from the summaries - interprocedurally. */ +/* Propagate constants, polymorphic contexts and their effects from the + summaries interprocedurally. */ static void -ipcp_propagate_stage (struct topo_info *topo) +ipcp_propagate_stage (struct ipa_topo_info *topo) { struct cgraph_node *node; 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); + determine_versionability (node, info); if (node->has_gimple_body_p ()) { info->lattices = XCNEWVEC (struct ipcp_param_lattices, @@ -2323,7 +3269,7 @@ ipcp_propagate_stage (struct topo_info *topo) initialize_node_lattices (node); } if (node->definition && !node->alias) - overall_size += inline_summary (node)->self_size; + overall_size += ipa_fn_summaries->get (node)->self_size; if (node->count > max_count) max_count = node->count; } @@ -2338,10 +3284,10 @@ ipcp_propagate_stage (struct topo_info *topo) overall_size, max_new_size); propagate_constants_topo (topo); -#ifdef ENABLE_CHECKING - ipcp_verify_propagated_values (); -#endif - propagate_effects (); + if (flag_checking) + ipcp_verify_propagated_values (); + topo->constants.propagate_effects (); + topo->contexts.propagate_effects (); if (dump_file) { @@ -2351,11 +3297,13 @@ ipcp_propagate_stage (struct topo_info *topo) } /* Discover newly direct outgoing edges from NODE which is a new clone with - known KNOWN_VALS and make them direct. */ + known KNOWN_CSTS and make them direct. */ static void ipcp_discover_new_direct_edges (struct cgraph_node *node, - vec known_vals, + vec known_csts, + vec + known_contexts, struct ipa_agg_replacement_value *aggvals) { struct cgraph_edge *ie, *next_ie; @@ -2364,16 +3312,18 @@ ipcp_discover_new_direct_edges (struct cgraph_node *node, for (ie = node->indirect_calls; ie; ie = next_ie) { tree target; + bool speculative; next_ie = ie->next_callee; - target = ipa_get_indirect_edge_target_1 (ie, known_vals, vNULL, vNULL, - aggvals); + target = ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts, + vNULL, aggvals, &speculative); if (target) { bool agg_contents = ie->indirect_info->agg_contents; bool polymorphic = ie->indirect_info->polymorphic; int param_index = ie->indirect_info->param_index; - struct cgraph_edge *cs = ipa_make_edge_direct_to_target (ie, target); + struct cgraph_edge *cs = ipa_make_edge_direct_to_target (ie, target, + speculative); found = true; if (cs && !agg_contents && !polymorphic) @@ -2403,7 +3353,7 @@ ipcp_discover_new_direct_edges (struct cgraph_node *node, } /* Turning calls to direct calls will improve overall summary. */ if (found) - inline_update_overall_summary (node); + ipa_update_overall_fn_summary (node); } /* Vector of pointers which for linked lists of clones of an original crgaph @@ -2476,17 +3426,31 @@ get_clone_agg_value (struct cgraph_node *node, HOST_WIDE_INT offset, return NULL_TREE; } -/* Return true if edge CS does bring about the value described by SRC. */ +/* Return true is NODE is DEST or its clone for all contexts. */ + +static bool +same_node_or_its_all_contexts_clone_p (cgraph_node *node, cgraph_node *dest) +{ + if (node == dest) + return true; + + struct ipa_node_params *info = IPA_NODE_REF (node); + return info->is_all_contexts_clone && info->ipcp_orig_node == dest; +} + +/* Return true if edge CS does bring about the value described by SRC to node + DEST or its clone for all contexts. */ static bool -cgraph_edge_brings_value_p (struct cgraph_edge *cs, - struct ipcp_value_source *src) +cgraph_edge_brings_value_p (cgraph_edge *cs, ipcp_value_source *src, + cgraph_node *dest) { struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); - cgraph_node *real_dest = cs->callee->function_symbol (); - struct ipa_node_params *dst_info = IPA_NODE_REF (real_dest); + enum availability availability; + cgraph_node *real_dest = cs->callee->function_symbol (&availability); - if ((dst_info->ipcp_orig_node && !dst_info->is_all_contexts_clone) + if (!same_node_or_its_all_contexts_clone_p (real_dest, dest) + || availability <= AVAIL_INTERPOSABLE || caller_info->node_dead) return false; if (!src->val) @@ -2496,7 +3460,7 @@ cgraph_edge_brings_value_p (struct cgraph_edge *cs, { tree t; if (src->offset == -1) - t = caller_info->known_vals[src->index]; + t = caller_info->known_csts[src->index]; else t = get_clone_agg_value (cs->caller, src->offset, src->index); return (t != NULL_TREE @@ -2508,7 +3472,7 @@ cgraph_edge_brings_value_p (struct cgraph_edge *cs, struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info, src->index); if (src->offset == -1) - return (ipa_lat_is_single_const (&plats->itself) + return (plats->itself.is_single_const () && values_equal_for_ipcp_p (src->val->value, plats->itself.values->value)); else @@ -2517,7 +3481,7 @@ cgraph_edge_brings_value_p (struct cgraph_edge *cs, return false; for (aglat = plats->aggs; aglat; aglat = aglat->next) if (aglat->offset == src->offset) - return (ipa_lat_is_single_const (aglat) + return (aglat->is_single_const () && values_equal_for_ipcp_p (src->val->value, aglat->values->value)); } @@ -2525,6 +3489,35 @@ cgraph_edge_brings_value_p (struct cgraph_edge *cs, } } +/* Return true if edge CS does bring about the value described by SRC to node + DEST or its clone for all contexts. */ + +static bool +cgraph_edge_brings_value_p (cgraph_edge *cs, + ipcp_value_source *src, + cgraph_node *dest) +{ + struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); + cgraph_node *real_dest = cs->callee->function_symbol (); + + if (!same_node_or_its_all_contexts_clone_p (real_dest, dest) + || caller_info->node_dead) + return false; + if (!src->val) + return true; + + if (caller_info->ipcp_orig_node) + return (caller_info->known_contexts.length () > (unsigned) src->index) + && values_equal_for_ipcp_p (src->val->value, + caller_info->known_contexts[src->index]); + + struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info, + src->index); + return plats->ctxlat.is_single_const () + && values_equal_for_ipcp_p (src->val->value, + plats->ctxlat.values->value); +} + /* Get the next clone in the linked list of clones of an edge. */ static inline struct cgraph_edge * @@ -2533,17 +3526,19 @@ get_next_cgraph_edge_clone (struct cgraph_edge *cs) return next_edge_clone[cs->uid]; } -/* 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. */ +/* Given VAL that is intended for DEST, iterate over all its sources and if + they still hold, add their edge frequency and their number into *FREQUENCY + and *CALLER_COUNT respectively. */ +template static bool -get_info_about_necessary_edges (struct ipcp_value *val, int *freq_sum, - gcov_type *count_sum, int *caller_count) +get_info_about_necessary_edges (ipcp_value *val, cgraph_node *dest, + int *freq_sum, + profile_count *count_sum, int *caller_count) { - struct ipcp_value_source *src; + ipcp_value_source *src; int freq = 0, count = 0; - gcov_type cnt = 0; + profile_count cnt = profile_count::zero (); bool hot = false; for (src = val->sources; src; src = src->next) @@ -2551,11 +3546,12 @@ get_info_about_necessary_edges (struct ipcp_value *val, int *freq_sum, struct cgraph_edge *cs = src->cs; while (cs) { - if (cgraph_edge_brings_value_p (cs, src)) + if (cgraph_edge_brings_value_p (cs, src, dest)) { count++; freq += cs->frequency; - cnt += cs->count; + if (cs->count.initialized_p ()) + cnt += cs->count; hot |= cs->maybe_hot_p (); } cs = get_next_cgraph_edge_clone (cs); @@ -2568,13 +3564,15 @@ get_info_about_necessary_edges (struct ipcp_value *val, int *freq_sum, return hot; } -/* Return a vector of incoming edges that do bring value VAL. It is assumed - their number is known and equal to CALLER_COUNT. */ +/* Return a vector of incoming edges that do bring value VAL to node DEST. It + is assumed their number is known and equal to CALLER_COUNT. */ +template static vec -gather_edges_for_value (struct ipcp_value *val, int caller_count) +gather_edges_for_value (ipcp_value *val, cgraph_node *dest, + int caller_count) { - struct ipcp_value_source *src; + ipcp_value_source *src; vec ret; ret.create (caller_count); @@ -2583,7 +3581,7 @@ gather_edges_for_value (struct ipcp_value *val, int caller_count) struct cgraph_edge *cs = src->cs; while (cs) { - if (cgraph_edge_brings_value_p (cs, src)) + if (cgraph_edge_brings_value_p (cs, src, dest)) ret.quick_push (cs); cs = get_next_cgraph_edge_clone (cs); } @@ -2606,9 +3604,9 @@ get_replacement_map (struct ipa_node_params *info, tree value, int parm_num) { fprintf (dump_file, " replacing "); ipa_dump_param (dump_file, info, parm_num); - + fprintf (dump_file, " with const "); - print_generic_expr (dump_file, value, 0); + print_generic_expr (dump_file, value); fprintf (dump_file, "\n"); } replace_map->old_tree = NULL; @@ -2628,19 +3626,27 @@ dump_profile_updates (struct cgraph_node *orig_node, { struct cgraph_edge *cs; - 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", - cs->callee->name (), (HOST_WIDE_INT) cs->count); + fprintf (dump_file, " setting count of the specialized node to "); + new_node->count.dump (dump_file); + fprintf (dump_file, "\n"); + for (cs = new_node->callees; cs; cs = cs->next_callee) + { + fprintf (dump_file, " edge to %s has count ", + cs->callee->name ()); + cs->count.dump (dump_file); + fprintf (dump_file, "\n"); + } - 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", - cs->callee->name (), (HOST_WIDE_INT) cs->count); + fprintf (dump_file, " setting count of the original node to "); + orig_node->count.dump (dump_file); + fprintf (dump_file, "\n"); + for (cs = orig_node->callees; cs; cs = cs->next_callee) + { + fprintf (dump_file, " edge to %s is left with ", + cs->callee->name ()); + cs->count.dump (dump_file); + fprintf (dump_file, "\n"); + } } /* After a specialized NEW_NODE version of ORIG_NODE has been created, update @@ -2652,10 +3658,10 @@ update_profiling_info (struct cgraph_node *orig_node, { struct cgraph_edge *cs; struct caller_statistics stats; - gcov_type new_sum, orig_sum; - gcov_type remainder, orig_node_count = orig_node->count; + profile_count new_sum, orig_sum; + profile_count remainder, orig_node_count = orig_node->count; - if (orig_node_count == 0) + if (!(orig_node_count > profile_count::zero ())) return; init_caller_stats (&stats); @@ -2670,36 +3676,37 @@ update_profiling_info (struct cgraph_node *orig_node, if (orig_node_count < orig_sum + new_sum) { 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", - orig_node->name (), orig_node->order, - (HOST_WIDE_INT) orig_node_count, - (HOST_WIDE_INT) (orig_sum + new_sum)); - - orig_node_count = (orig_sum + new_sum) * 12 / 10; + { + fprintf (dump_file, " Problem: node %s has too low count ", + orig_node->dump_name ()); + orig_node_count.dump (dump_file); + fprintf (dump_file, "while the sum of incoming count is "); + (orig_sum + new_sum).dump (dump_file); + fprintf (dump_file, "\n"); + } + + orig_node_count = (orig_sum + new_sum).apply_scale (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); + { + fprintf (dump_file, " proceeding by pretending it was "); + orig_node_count.dump (dump_file); + fprintf (dump_file, "\n"); + } } 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) + for (cs = new_node->callees; cs; cs = cs->next_callee) + /* FIXME: why we care about non-zero frequency here? */ if (cs->frequency) - cs->count = apply_probability (cs->count, - GCOV_COMPUTE_SCALE (new_sum, - orig_node_count)); + cs->count = cs->count.apply_scale (new_sum, orig_node_count); else - cs->count = 0; + cs->count = profile_count::zero (); - for (cs = orig_node->callees; cs ; cs = cs->next_callee) - cs->count = apply_probability (cs->count, - GCOV_COMPUTE_SCALE (remainder, - orig_node_count)); + for (cs = orig_node->callees; cs; cs = cs->next_callee) + cs->count = cs->count.apply_scale (remainder, orig_node_count); if (dump_file) dump_profile_updates (orig_node, new_node); @@ -2712,15 +3719,18 @@ update_profiling_info (struct cgraph_node *orig_node, static void update_specialized_profile (struct cgraph_node *new_node, struct cgraph_node *orig_node, - gcov_type redirected_sum) + profile_count redirected_sum) { struct cgraph_edge *cs; - gcov_type new_node_count, orig_node_count = orig_node->count; + profile_count new_node_count, orig_node_count = orig_node->count; 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) + { + fprintf (dump_file, " the sum of counts of redirected edges is "); + redirected_sum.dump (dump_file); + fprintf (dump_file, "\n"); + } + if (!(orig_node_count > profile_count::zero ())) return; gcc_assert (orig_node_count >= redirected_sum); @@ -2729,35 +3739,31 @@ update_specialized_profile (struct cgraph_node *new_node, new_node->count += redirected_sum; orig_node->count -= redirected_sum; - for (cs = new_node->callees; cs ; cs = cs->next_callee) + for (cs = new_node->callees; cs; cs = cs->next_callee) if (cs->frequency) - cs->count += apply_probability (cs->count, - GCOV_COMPUTE_SCALE (redirected_sum, - new_node_count)); + cs->count += cs->count.apply_scale (redirected_sum, new_node_count); else - cs->count = 0; + cs->count = profile_count::zero (); - for (cs = orig_node->callees; cs ; cs = cs->next_callee) + for (cs = orig_node->callees; cs; cs = cs->next_callee) { - gcov_type dec = apply_probability (cs->count, - GCOV_COMPUTE_SCALE (redirected_sum, - orig_node_count)); - if (dec < cs->count) - cs->count -= dec; - else - cs->count = 0; + profile_count dec = cs->count.apply_scale (redirected_sum, + orig_node_count); + cs->count -= dec; } 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. */ +/* Create a specialized version of NODE with known constants in KNOWN_CSTS, + known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and + redirect all edges in CALLERS to it. */ static struct cgraph_node * create_specialized_node (struct cgraph_node *node, - vec known_vals, + vec known_csts, + vec known_contexts, struct ipa_agg_replacement_value *aggvals, vec callers) { @@ -2775,10 +3781,9 @@ create_specialized_node (struct cgraph_node *node, args_to_skip = BITMAP_GGC_ALLOC (); for (i = 0; i < count; i++) { - tree t = known_vals[i]; + tree t = known_csts[i]; - if ((t && TREE_CODE (t) != TREE_BINFO) - || !ipa_is_param_used (info, i)) + if (t || !ipa_is_param_used (info, i)) bitmap_set_bit (args_to_skip, i); } } @@ -2789,13 +3794,14 @@ create_specialized_node (struct cgraph_node *node, fprintf (dump_file, " cannot change function signature\n"); } - for (i = 0; i < count ; i++) + for (i = 0; i < count; i++) { - tree t = known_vals[i]; - if (t && TREE_CODE (t) != TREE_BINFO) + tree t = known_csts[i]; + if (t) { struct ipa_replace_map *replace_map; + gcc_checking_assert (TREE_CODE (t) != TREE_BINFO); replace_map = get_replacement_map (info, t, i); if (replace_map) vec_safe_push (replace_trees, replace_map); @@ -2806,12 +3812,20 @@ create_specialized_node (struct cgraph_node *node, args_to_skip, "constprop"); ipa_set_node_agg_value_chain (new_node, aggvals); for (av = aggvals; av; av = av->next) - new_node->maybe_create_reference (av->value, IPA_REF_ADDR, NULL); + new_node->maybe_create_reference (av->value, NULL); if (dump_file && (dump_flags & TDF_DETAILS)) { - fprintf (dump_file, " the new node is %s/%i.\n", - new_node->name (), new_node->order); + fprintf (dump_file, " the new node is %s.\n", new_node->dump_name ()); + if (known_contexts.exists ()) + { + for (i = 0; i < count; i++) + if (!known_contexts[i].useless_p ()) + { + fprintf (dump_file, " known ctx %i is ", i); + known_contexts[i].dump (dump_file); + } + } if (aggvals) ipa_dump_agg_replacement_values (dump_file, aggvals); } @@ -2819,33 +3833,34 @@ create_specialized_node (struct cgraph_node *node, 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; + new_info->known_csts = known_csts; + new_info->known_contexts = known_contexts; - ipcp_discover_new_direct_edges (new_node, known_vals, aggvals); + ipcp_discover_new_direct_edges (new_node, known_csts, known_contexts, aggvals); callers.release (); return new_node; } /* 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. */ + KNOWN_CSTS with constants that are also known for all of the CALLERS. */ static void find_more_scalar_values_for_callers_subset (struct cgraph_node *node, - vec known_vals, + vec known_csts, vec callers) { struct ipa_node_params *info = IPA_NODE_REF (node); int i, count = ipa_get_param_count (info); - for (i = 0; i < count ; i++) + for (i = 0; i < count; i++) { struct cgraph_edge *cs; tree newval = NULL_TREE; int j; + bool first = true; - if (ipa_get_scalar_lat (info, i)->bottom || known_vals[i]) + if (ipa_get_scalar_lat (info, i)->bottom || known_csts[i]) continue; FOR_EACH_VEC_ELT (callers, j, cs) @@ -2853,22 +3868,28 @@ find_more_scalar_values_for_callers_subset (struct cgraph_node *node, struct ipa_jump_func *jump_func; tree t; - if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs))) - { - newval = NULL_TREE; - break; - } + if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs)) + || (i == 0 + && call_passes_through_thunk_p (cs)) + || (!cs->callee->instrumentation_clone + && cs->callee->function_symbol ()->instrumentation_clone)) + { + newval = NULL_TREE; + break; + } jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i); t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func); if (!t || (newval - && !values_equal_for_ipcp_p (t, newval))) + && !values_equal_for_ipcp_p (t, newval)) + || (!first && !newval)) { newval = NULL_TREE; break; } else newval = t; + first = false; } if (newval) @@ -2882,8 +3903,74 @@ find_more_scalar_values_for_callers_subset (struct cgraph_node *node, fprintf (dump_file, "\n"); } - known_vals[i] = newval; + known_csts[i] = newval; + } + } +} + +/* Given a NODE and a subset of its CALLERS, try to populate plank slots in + KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the + CALLERS. */ + +static void +find_more_contexts_for_caller_subset (cgraph_node *node, + vec + *known_contexts, + vec callers) +{ + ipa_node_params *info = IPA_NODE_REF (node); + int i, count = ipa_get_param_count (info); + + for (i = 0; i < count; i++) + { + cgraph_edge *cs; + + if (ipa_get_poly_ctx_lat (info, i)->bottom + || (known_contexts->exists () + && !(*known_contexts)[i].useless_p ())) + continue; + + ipa_polymorphic_call_context newval; + bool first = true; + int j; + + FOR_EACH_VEC_ELT (callers, j, cs) + { + if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs))) + return; + ipa_jump_func *jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), + i); + ipa_polymorphic_call_context ctx; + ctx = ipa_context_from_jfunc (IPA_NODE_REF (cs->caller), cs, i, + jfunc); + if (first) + { + newval = ctx; + first = false; + } + else + newval.meet_with (ctx); + if (newval.useless_p ()) + break; + } + + if (!newval.useless_p ()) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " adding an extra known polymorphic " + "context "); + print_ipcp_constant_value (dump_file, newval); + fprintf (dump_file, " for "); + ipa_dump_param (dump_file, info, i); + fprintf (dump_file, "\n"); + } + + if (!known_contexts->exists ()) + known_contexts->safe_grow_cleared (ipa_get_param_count (info)); + (*known_contexts)[i] = newval; } + } } @@ -2899,7 +3986,7 @@ copy_plats_to_inter (struct ipcp_param_lattices *plats, HOST_WIDE_INT offset) return vNULL; for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next) - if (ipa_lat_is_single_const (aglat)) + if (aglat->is_single_const ()) { struct ipa_agg_jf_item ti; ti.offset = aglat->offset - offset; @@ -2951,7 +4038,7 @@ intersect_with_plats (struct ipcp_param_lattices *plats, } } -/* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the +/* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the vector result while subtracting OFFSET from the individual value offsets. */ static vec @@ -3168,7 +4255,7 @@ find_aggregate_values_for_callers_subset (struct cgraph_node *node, count = c; } - for (i = 0; i < count ; i++) + for (i = 0; i < count; i++) { struct cgraph_edge *cs; vec inter = vNULL; @@ -3213,7 +4300,7 @@ find_aggregate_values_for_callers_subset (struct cgraph_node *node, return res; } -/* Turn KNOWN_AGGS into a list of aggreate replacement values. */ +/* Turn KNOWN_AGGS into a list of aggregate replacement values. */ static struct ipa_agg_replacement_value * known_aggs_to_agg_replacement_list (vec known_aggs) @@ -3260,7 +4347,7 @@ cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge *cs, struct ipa_jump_func *jump_func; tree val, t; - val = dest_info->known_vals[i]; + val = dest_info->known_csts[i]; if (!val) continue; @@ -3349,72 +4436,107 @@ cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge *cs, /* 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. + all other criteria such that they can be redirected the special node. This function can therefore redirect the final edge in a SCC. */ +template static void -perhaps_add_new_callers (struct cgraph_node *node, struct ipcp_value *val) +perhaps_add_new_callers (cgraph_node *node, ipcp_value *val) { - struct ipcp_value_source *src; - gcov_type redirected_sum = 0; + ipcp_value_source *src; + profile_count redirected_sum = profile_count::zero (); for (src = val->sources; src; src = src->next) { struct cgraph_edge *cs = src->cs; while (cs) { - enum availability availability; - struct cgraph_node *dst = cs->callee->function_symbol (&availability); - if ((dst == node || IPA_NODE_REF (dst)->is_all_contexts_clone) - && availability > AVAIL_INTERPOSABLE - && cgraph_edge_brings_value_p (cs, src)) + if (cgraph_edge_brings_value_p (cs, src, node) + && cgraph_edge_brings_all_scalars_for_node (cs, val->spec_node) + && cgraph_edge_brings_all_agg_vals_for_node (cs, val->spec_node)) { - if (cgraph_edge_brings_all_scalars_for_node (cs, val->spec_node) - && cgraph_edge_brings_all_agg_vals_for_node (cs, - val->spec_node)) - { - if (dump_file) - fprintf (dump_file, " - adding an extra caller %s/%i" - " of %s/%i\n", - xstrdup (cs->caller->name ()), - cs->caller->order, - xstrdup (val->spec_node->name ()), - val->spec_node->order); - - cs->redirect_callee (val->spec_node); - redirected_sum += cs->count; - } + if (dump_file) + fprintf (dump_file, " - adding an extra caller %s of %s\n", + cs->caller->dump_name (), + val->spec_node->dump_name ()); + + cs->redirect_callee_duplicating_thunks (val->spec_node); + val->spec_node->expand_all_artificial_thunks (); + if (cs->count.initialized_p ()) + redirected_sum = redirected_sum + cs->count; } cs = get_next_cgraph_edge_clone (cs); } } - if (redirected_sum) + if (redirected_sum > profile_count::zero ()) update_specialized_profile (val->spec_node, node, redirected_sum); } +/* Return true if KNOWN_CONTEXTS contain at least one useful context. */ + +static bool +known_contexts_useful_p (vec known_contexts) +{ + ipa_polymorphic_call_context *ctx; + int i; + + FOR_EACH_VEC_ELT (known_contexts, i, ctx) + if (!ctx->useless_p ()) + return true; + return false; +} + +/* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */ + +static vec +copy_useful_known_contexts (vec known_contexts) +{ + if (known_contexts_useful_p (known_contexts)) + return known_contexts.copy (); + else + return vNULL; +} -/* Copy KNOWN_BINFOS to KNOWN_VALS. */ +/* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If + non-empty, replace KNOWN_CONTEXTS with its copy too. */ static void -move_binfos_to_values (vec known_vals, - vec known_binfos) +modify_known_vectors_with_val (vec *known_csts, + vec *known_contexts, + ipcp_value *val, + int index) { - tree t; - int i; + *known_csts = known_csts->copy (); + *known_contexts = copy_useful_known_contexts (*known_contexts); + (*known_csts)[index] = val->value; +} + +/* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the + copy according to VAL and INDEX. */ - for (i = 0; known_binfos.iterate (i, &t); i++) - if (t) - known_vals[i] = t; +static void +modify_known_vectors_with_val (vec *known_csts, + vec *known_contexts, + ipcp_value *val, + int index) +{ + *known_csts = known_csts->copy (); + *known_contexts = known_contexts->copy (); + (*known_contexts)[index] = val->value; } -/* Return true if there is a replacement equivalent to VALUE, INDEX and OFFSET - among those in the AGGVALS list. */ +/* Return true if OFFSET indicates this was not an aggregate value or there is + a replacement equivalent to VALUE, INDEX and OFFSET among those in the + AGGVALS list. */ DEBUG_FUNCTION bool -ipcp_val_in_agg_replacements_p (struct ipa_agg_replacement_value *aggvals, - int index, HOST_WIDE_INT offset, tree value) +ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *aggvals, + int index, HOST_WIDE_INT offset, tree value) { + if (offset == -1) + return true; + while (aggvals) { if (aggvals->index == index @@ -3426,21 +4548,32 @@ ipcp_val_in_agg_replacements_p (struct ipa_agg_replacement_value *aggvals, return false; } +/* Return true if offset is minus one because source of a polymorphic contect + cannot be an aggregate value. */ + +DEBUG_FUNCTION bool +ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *, + int , HOST_WIDE_INT offset, + ipa_polymorphic_call_context) +{ + return offset == -1; +} + /* Decide wheter to create a special version of NODE for value VAL of parameter at the given INDEX. If OFFSET is -1, the value is for the parameter itself, otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS, - KNOWN_BINFOS and KNOWN_AGGS describe the other already known values. */ + KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */ +template static bool decide_about_value (struct cgraph_node *node, int index, HOST_WIDE_INT offset, - struct ipcp_value *val, vec known_csts, - vec known_binfos) + ipcp_value *val, vec known_csts, + vec known_contexts) { struct ipa_agg_replacement_value *aggvals; int freq_sum, caller_count; - gcov_type count_sum; + profile_count count_sum; vec callers; - vec kv; if (val->spec_node) { @@ -3455,7 +4588,7 @@ decide_about_value (struct cgraph_node *node, int index, HOST_WIDE_INT offset, val->local_size_cost + overall_size); return false; } - else if (!get_info_about_necessary_edges (val, &freq_sum, &count_sum, + else if (!get_info_about_necessary_edges (val, node, &freq_sum, &count_sum, &caller_count)) return false; @@ -3482,20 +4615,24 @@ decide_about_value (struct cgraph_node *node, int index, HOST_WIDE_INT offset, return false; if (dump_file) - fprintf (dump_file, " Creating a specialized node of %s/%i.\n", - node->name (), node->order); + fprintf (dump_file, " Creating a specialized node of %s.\n", + node->dump_name ()); - callers = gather_edges_for_value (val, caller_count); - kv = known_csts.copy (); - move_binfos_to_values (kv, known_binfos); + callers = gather_edges_for_value (val, node, caller_count); if (offset == -1) - kv[index] = val->value; - find_more_scalar_values_for_callers_subset (node, kv, callers); + modify_known_vectors_with_val (&known_csts, &known_contexts, val, index); + else + { + known_csts = known_csts.copy (); + known_contexts = copy_useful_known_contexts (known_contexts); + } + find_more_scalar_values_for_callers_subset (node, known_csts, callers); + find_more_contexts_for_caller_subset (node, &known_contexts, callers); aggvals = find_aggregate_values_for_callers_subset (node, callers); - gcc_checking_assert (offset == -1 - || ipcp_val_in_agg_replacements_p (aggvals, index, - offset, val->value)); - val->spec_node = create_specialized_node (node, kv, aggvals, callers); + gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals, index, + offset, val->value)); + val->spec_node = create_specialized_node (node, known_csts, known_contexts, + aggvals, callers); overall_size += val->local_size_cost; /* TODO: If for some lattice there is only one other known value @@ -3511,7 +4648,8 @@ 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 known_csts, known_binfos; + vec known_csts; + vec known_contexts; vec known_aggs = vNULL; bool ret = false; @@ -3519,41 +4657,53 @@ decide_whether_version_node (struct cgraph_node *node) return false; if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "\nEvaluating opportunities for %s/%i.\n", - node->name (), node->order); + fprintf (dump_file, "\nEvaluating opportunities for %s.\n", + node->dump_name ()); - gather_context_independent_values (info, &known_csts, &known_binfos, + gather_context_independent_values (info, &known_csts, &known_contexts, info->do_clone_for_all_contexts ? &known_aggs : NULL, NULL); - for (i = 0; i < count ;i++) + for (i = 0; i < count;i++) { struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); - struct ipcp_lattice *lat = &plats->itself; - struct ipcp_value *val; + ipcp_lattice *lat = &plats->itself; + ipcp_lattice *ctxlat = &plats->ctxlat; if (!lat->bottom - && !known_csts[i] - && !known_binfos[i]) - for (val = lat->values; val; val = val->next) - ret |= decide_about_value (node, i, -1, val, known_csts, - known_binfos); + && !known_csts[i]) + { + ipcp_value *val; + for (val = lat->values; val; val = val->next) + ret |= decide_about_value (node, i, -1, val, known_csts, + known_contexts); + } if (!plats->aggs_bottom) { struct ipcp_agg_lattice *aglat; - struct ipcp_value *val; + ipcp_value *val; for (aglat = plats->aggs; aglat; aglat = aglat->next) if (!aglat->bottom && aglat->values /* If the following is false, the one value is in known_aggs. */ && (plats->aggs_contain_variable - || !ipa_lat_is_single_const (aglat))) + || !aglat->is_single_const ())) for (val = aglat->values; val; val = val->next) ret |= decide_about_value (node, i, aglat->offset, val, - known_csts, known_binfos); + known_csts, known_contexts); + } + + if (!ctxlat->bottom + && known_contexts[i].useless_p ()) + { + ipcp_value *val; + for (val = ctxlat->values; val; val = val->next) + ret |= decide_about_value (node, i, -1, val, known_csts, + known_contexts); } - info = IPA_NODE_REF (node); + + info = IPA_NODE_REF (node); } if (info->do_clone_for_all_contexts) @@ -3562,27 +4712,33 @@ decide_whether_version_node (struct cgraph_node *node) vec callers; if (dump_file) - fprintf (dump_file, " - Creating a specialized node of %s/%i " - "for all known contexts.\n", node->name (), - node->order); + fprintf (dump_file, " - Creating a specialized node of %s " + "for all known contexts.\n", node->dump_name ()); callers = node->collect_callers (); - move_binfos_to_values (known_csts, known_binfos); - clone = create_specialized_node (node, known_csts, + + if (!known_contexts_useful_p (known_contexts)) + { + known_contexts.release (); + known_contexts = vNULL; + } + clone = create_specialized_node (node, known_csts, known_contexts, known_aggs_to_agg_replacement_list (known_aggs), callers); info = IPA_NODE_REF (node); info->do_clone_for_all_contexts = false; IPA_NODE_REF (clone)->is_all_contexts_clone = true; - for (i = 0; i < count ; i++) + for (i = 0; i < count; i++) vec_free (known_aggs[i].items); known_aggs.release (); ret = true; } else - known_csts.release (); + { + known_csts.release (); + known_contexts.release (); + } - known_binfos.release (); return ret; } @@ -3615,7 +4771,7 @@ spread_undeadness (struct cgraph_node *node) static bool has_undead_caller_from_outside_scc_p (struct cgraph_node *node, - void *data ATTRIBUTE_UNUSED) + void *data ATTRIBUTE_UNUSED) { struct cgraph_edge *cs; @@ -3638,22 +4794,21 @@ 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 (v->will_be_removed_from_program_if_no_direct_calls_p () + for (v = node; v; v = ((struct ipa_dfs_info *) v->aux)->next_cycle) + if (v->local.local && !v->call_for_symbol_thunks_and_aliases (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) + 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) + 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", - v->name (), v->order); + fprintf (dump_file, " Marking node as dead: %s.\n", v->dump_name ()); } } @@ -3661,7 +4816,7 @@ identify_dead_nodes (struct cgraph_node *node) TOPO and make specialized clones if deemed beneficial. */ static void -ipcp_decision_stage (struct topo_info *topo) +ipcp_decision_stage (struct ipa_topo_info *topo) { int i; @@ -3677,7 +4832,7 @@ ipcp_decision_stage (struct topo_info *topo) { struct cgraph_node *v; iterate = false; - for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle) + for (v = node; v; v = ((struct ipa_dfs_info *) v->aux)->next_cycle) if (v->has_gimple_body_p () && ipcp_versionable_function_p (v)) iterate |= decide_whether_version_node (v); @@ -3689,6 +4844,147 @@ ipcp_decision_stage (struct topo_info *topo) } } +/* Look up all the bits information that we have discovered and copy it over + to the transformation summary. */ + +static void +ipcp_store_bits_results (void) +{ + cgraph_node *node; + + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) + { + ipa_node_params *info = IPA_NODE_REF (node); + bool dumped_sth = false; + bool found_useful_result = false; + + if (!opt_for_fn (node->decl, flag_ipa_bit_cp)) + { + if (dump_file) + fprintf (dump_file, "Not considering %s for ipa bitwise propagation " + "; -fipa-bit-cp: disabled.\n", + node->name ()); + continue; + } + + if (info->ipcp_orig_node) + info = IPA_NODE_REF (info->ipcp_orig_node); + + unsigned count = ipa_get_param_count (info); + for (unsigned i = 0; i < count; i++) + { + ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); + if (plats->bits_lattice.constant_p ()) + { + found_useful_result = true; + break; + } + } + + if (!found_useful_result) + continue; + + ipcp_grow_transformations_if_necessary (); + ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node); + vec_safe_reserve_exact (ts->bits, count); + + for (unsigned i = 0; i < count; i++) + { + ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); + ipa_bits *jfbits; + + if (plats->bits_lattice.constant_p ()) + jfbits + = ipa_get_ipa_bits_for_value (plats->bits_lattice.get_value (), + plats->bits_lattice.get_mask ()); + else + jfbits = NULL; + + ts->bits->quick_push (jfbits); + if (!dump_file || !jfbits) + continue; + if (!dumped_sth) + { + fprintf (dump_file, "Propagated bits info for function %s:\n", + node->dump_name ()); + dumped_sth = true; + } + fprintf (dump_file, " param %i: value = ", i); + print_hex (jfbits->value, dump_file); + fprintf (dump_file, ", mask = "); + print_hex (jfbits->mask, dump_file); + fprintf (dump_file, "\n"); + } + } +} + +/* Look up all VR information that we have discovered and copy it over + to the transformation summary. */ + +static void +ipcp_store_vr_results (void) +{ + cgraph_node *node; + + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) + { + ipa_node_params *info = IPA_NODE_REF (node); + bool found_useful_result = false; + + if (!opt_for_fn (node->decl, flag_ipa_vrp)) + { + if (dump_file) + fprintf (dump_file, "Not considering %s for VR discovery " + "and propagate; -fipa-ipa-vrp: disabled.\n", + node->name ()); + continue; + } + + if (info->ipcp_orig_node) + info = IPA_NODE_REF (info->ipcp_orig_node); + + unsigned count = ipa_get_param_count (info); + for (unsigned i = 0; i < count; i++) + { + ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); + if (!plats->m_value_range.bottom_p () + && !plats->m_value_range.top_p ()) + { + found_useful_result = true; + break; + } + } + if (!found_useful_result) + continue; + + ipcp_grow_transformations_if_necessary (); + ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node); + vec_safe_reserve_exact (ts->m_vr, count); + + for (unsigned i = 0; i < count; i++) + { + ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); + ipa_vr vr; + + if (!plats->m_value_range.bottom_p () + && !plats->m_value_range.top_p ()) + { + vr.known = true; + vr.type = plats->m_value_range.m_vr.type; + vr.min = wi::to_wide (plats->m_value_range.m_vr.min); + vr.max = wi::to_wide (plats->m_value_range.m_vr.max); + } + else + { + vr.known = false; + vr.type = VR_VARYING; + vr.min = vr.max = wi::zero (INT_TYPE_SIZE); + } + ts->m_vr->quick_push (vr); + } + } +} + /* The IPCP driver. */ static unsigned int @@ -3696,28 +4992,21 @@ ipcp_driver (void) { struct cgraph_2edge_hook_list *edge_duplication_hook_holder; struct cgraph_edge_hook_list *edge_removal_hook_holder; - struct topo_info topo; + struct ipa_topo_info topo; ipa_check_create_node_params (); ipa_check_create_edge_args (); grow_edge_clone_vectors (); - edge_duplication_hook_holder = - symtab->add_edge_duplication_hook (&ipcp_edge_duplication_hook, NULL); - edge_removal_hook_holder = - symtab->add_edge_removal_hook (&ipcp_edge_removal_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); - ipcp_agg_lattice_pool = create_alloc_pool ("IPA_CP aggregate lattices", - sizeof (struct ipcp_agg_lattice), - 32); + edge_duplication_hook_holder + = symtab->add_edge_duplication_hook (&ipcp_edge_duplication_hook, NULL); + edge_removal_hook_holder + = symtab->add_edge_removal_hook (&ipcp_edge_removal_hook, NULL); + if (dump_file) { fprintf (dump_file, "\nIPA structures before propagation:\n"); if (dump_flags & TDF_DETAILS) - ipa_print_all_params (dump_file); + ipa_print_all_params (dump_file); ipa_print_all_jump_functions (dump_file); } @@ -3727,10 +5016,15 @@ ipcp_driver (void) ipcp_propagate_stage (&topo); /* Decide what constant propagation and cloning should be performed. */ ipcp_decision_stage (&topo); + /* Store results of bits propagation. */ + ipcp_store_bits_results (); + /* Store results of value range propagation. */ + ipcp_store_vr_results (); /* Free all IPCP structures. */ free_toporder_info (&topo); next_edge_clone.release (); + prev_edge_clone.release (); symtab->remove_edge_removal_hook (edge_removal_hook_holder); symtab->remove_edge_duplication_hook (edge_duplication_hook_holder); ipa_free_all_structures_after_ipa_cp (); @@ -3753,11 +5047,7 @@ ipcp_generate_summary (void) ipa_register_cgraph_hooks (); FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) - { - node->local.versionable - = tree_versionable_function_p (node->decl); - ipa_analyze_node (node); - } + ipa_analyze_node (node); } /* Write ipcp summary for nodes in SET. */ @@ -3799,9 +5089,9 @@ public: ipcp_generate_summary, /* generate_summary */ ipcp_write_summary, /* write_summary */ ipcp_read_summary, /* read_summary */ - ipa_prop_write_all_agg_replacement, /* + ipcp_write_transformation_summaries, /* write_optimization_summary */ - ipa_prop_read_all_agg_replacement, /* + ipcp_read_transformation_summaries, /* read_optimization_summary */ NULL, /* stmt_fixup */ 0, /* function_transform_todo_flags_start */ @@ -3814,7 +5104,7 @@ public: { /* FIXME: We should remove the optimize check after we ensure we never run IPA passes when not optimizing. */ - return flag_ipa_cp && optimize; + return (flag_ipa_cp && optimize) || in_lto_p; } virtual unsigned int execute (function *) { return ipcp_driver (); } @@ -3828,3 +5118,14 @@ make_pass_ipa_cp (gcc::context *ctxt) { return new pass_ipa_cp (ctxt); } + +/* Reset all state within ipa-cp.c so that we can rerun the compiler + within the same process. For use by toplev::finalize. */ + +void +ipa_cp_c_finalize (void) +{ + max_count = profile_count::zero (); + overall_size = 0; + max_new_size = 0; +}