#include "config.h"#include "system.h"#include "coretypes.h"#include "tree.h"#include "gimple.h"#include "target.h"#include "ipa-prop.h"#include "bitmap.h"#include "tree-pass.h"#include "flags.h"#include "diagnostic.h"#include "tree-pretty-print.h"#include "tree-inline.h"#include "params.h"#include "ipa-inline.h"#include "ipa-utils.h"
Data Structures | |
| struct | ipcp_value_source |
| struct | ipcp_value |
| struct | ipcp_lattice |
| struct | ipcp_agg_lattice |
| struct | ipcp_param_lattices |
| struct | caller_statistics |
| struct | topo_info |
Variables | |
| alloc_pool | ipcp_values_pool |
| alloc_pool | ipcp_sources_pool |
| alloc_pool | ipcp_agg_lattice_pool |
| static gcov_type | max_count |
| static long | overall_size |
| static long | max_new_size |
| static struct ipcp_value * | values_topo |
| static vec< cgraph_edge_p > | next_edge_clone |
Function Documentation
|
static |
Add all values in lattices associated with NODE to the topological sort if they are not there yet.
|
inlinestatic |
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.
References ipcp_lattice::bottom, IPA_JF_CONST, IPA_JF_KNOWN_TYPE, and ipa_jump_func::type.
Referenced by add_value_to_lattice().
|
static |
Add value CUR_VAL and all yet-unsorted values it is dependent on to the topological sort of values.
|
static |
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.
|
static |
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.
We can only free sources, not the values themselves, because sources of other values in this this SCC might point to them.
References add_scalar_value_to_lattice(), ipa_edge_within_scc(), ipa_get_jf_pass_through_operation(), ipa_get_jf_pass_through_result(), ipcp_value::next, set_lattice_contains_variable(), ipcp_value::value, and ipcp_lattice::values.
|
static |
The current interface in ipa-inline-analysis requires a pointer vector. Create it.
FIXME: That interface should be re-worked, this is slightly silly. Still, I'd like to discuss how to change it first and this demonstrates the issue.
References estimate_move_cost(), NULL_TREE, TREE_CODE, TREE_TYPE, ipcp_value::value, and ipcp_param_lattices::virt_call.
|
static |
Determine whether there is anything to propagate FROM SRC_PLATS through a pass-through JFUNC and if so, whether it has conform and conforms to the rules about propagating values passed by reference.
Referenced by copy_plats_to_inter().
|
static |
Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the vector result while subtracting OFFSET from the individual value offsets.
|
static |
Allocate the arrays in TOPO and topologically sort the nodes into order.
|
static |
Determine whether CS also brings all aggregate values that NODE is specialized for.
Referenced by known_aggs_to_agg_replacement_list().
|
static |
Determine whether CS also brings all scalar values that the NODE is specialized for.
Referenced by known_aggs_to_agg_replacement_list().
|
static |
Return true if edge CS does bring about the value described by SRC.
Referenced by get_clone_agg_value(), and known_aggs_to_agg_replacement_list().
|
static |
Gate for IPCP optimization.
FIXME: We should remove the optimize check after we ensure we never run IPA passes when not optimizing.
|
static |
Return all context independent values from aggregate lattices in PLATS in a vector. Return NULL if there are none.
References FOR_EACH_VEC_ELT.
|
static |
Go through PLATS and create a vector of values consisting of values and offsets (minus OFFSET) of lattices that contain only a single value.
References agg_pass_through_permissible_p(), cgraph_edge::caller, IPA_EDGE_REF, ipa_get_ith_jump_func(), ipa_get_jf_pass_through_formal_id(), ipa_get_jf_pass_through_operation(), ipa_get_parm_lattices(), IPA_JF_PASS_THROUGH, IPA_NODE_REF, ipa_node_params::ipcp_orig_node, and ipa_jump_func::type.
|
staticread |
Create a specialized version of NODE with known constants and types of parameters in KNOWN_VALS and redirect all edges in CALLERS to it.
|
static |
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.
TODO: If for some lattice there is only one other known value left, make a special node for it too.
Referenced by move_binfos_to_values().
|
static |
Decide whether and what specialized clones of NODE should be created.
If the following is false, the one value is in known_aggs.
|
static |
Determine whether it is at all technically possible to create clones of NODE and store this information in the ipa_node_params structure associated with NODE.
There are a number of generic reasons functions cannot be versioned. We also cannot remove parameters if there are type attributes such as fnspec present.
|
static |
Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS and KNOWN_BINFOS.
Only bare minimum benefit for clearly un-inlineable targets.
FIXME: The values below need re-considering and perhaps also
integrating into the cost metrics, at lest in some very basic way.
|
static |
Dump new profiling counts
|
static |
Iterate over known values of parameters of NODE and estimate the local effects in terms of time and size they have.
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 the following is true, the one value is in known_aggs.
|
staticread |
Look at edges in CALLERS and collect all known aggregate values that arrive from all of them.
Among other things, the following check should deal with all by_ref mismatches.
|
static |
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.
References gcc_checking_assert, ipa_agg_jf_item::offset, ipa_agg_replacement_value::offset, offset, ipa_agg_jf_item::value, and ipa_agg_replacement_value::value.
|
static |
Free information about strongly connected components and the arrays in TOPO.
|
static |
Worker callback of cgraph_for_node_and_aliases accumulating statistics of non-thunk incoming edges to NODE.
References cgraph_node_name(), and dump_file.
|
static |
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.
|
static |
Return a vector of incoming edges that do bring value VAL. It is assumed their number is known and equal to CALLER_COUNT.
|
static |
See if NODE is a clone with a known aggregate value at a given OFFSET of a parameter with the given INDEX.
References cgraph_edge_brings_value_p(), ipcp_value_source::cs, and get_next_cgraph_edge_clone().
Referenced by ipcp_discover_new_direct_edges().
|
static |
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.
|
staticread |
Get the next clone in the linked list of clones of an edge.
References cgraph_node::count.
Referenced by get_clone_agg_value().
|
staticread |
Construct a replacement map for a know VALUE for a formal parameter PARAM. Return it or NULL if for some reason it cannot be created.
|
static |
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.
|
inlinestatic |
|
static |
Return true if NODE has a caller from outside of its SCC that is not dead. Worker callback for cgraph_for_node_and_aliases.
|
static |
Return time bonus incurred because of HINTS.
|
static |
Identify nodes within the same SCC as NODE which are no longer needed because of new clones and will be removed as unreachable.
References IPA_PASS, ipa_prop_read_all_agg_replacement(), ipa_prop_write_all_agg_replacement(), ipcp_generate_summary(), ipcp_read_summary(), ipcp_write_summary(), NULL, OPTGROUP_NONE, TODO_dump_symtab, and TODO_remove_functions.
|
inlinestatic |
Initialize fields of STAT to zeroes.
References cgraph_node_name(), and dump_file.
|
static |
Initialize ipcp_lattices.
When cloning is allowed, we can assume that externally visible functions are not called. We will compensate this by cloning later.
|
static |
Intersect values in INTER with aggregate values that come along edge CS to parameter number INDEX and return it. If INTER does not actually exist yet, copy all incoming values to it. If we determine we ended up with no values whatsoever, return a released vector.
Currently we do not produce clobber aggregate jump functions, adjust when we do.
Currently we do not produce clobber aggregate jump functions, adjust when we do.
|
static |
Intersect all values in INTER with those that we have already scheduled to be replaced in parameter number INDEX of NODE, which is an IPA-CP clone (while subtracting OFFSET).
References ipa_jump_func::agg, gcc_checking_assert, ipa_agg_jump_function::items, ipa_agg_jf_item::offset, ipa_agg_jf_item::value, and values_equal_for_ipcp_p().
|
static |
Intersect all values in INTER with single value lattices in PLATS (while subtracting OFFSET).
| tree ipa_get_indirect_edge_target | ( | struct cgraph_edge * | ie, |
| vec< tree > | known_vals, | ||
| vec< tree > | known_binfos, | ||
| vec< ipa_agg_jump_function_p > | known_aggs | ||
| ) |
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.
|
static |
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.
Referenced by safe_add().
|
static |
Return the result of an ancestor jump function JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be determined.
|
static |
Return the result of a (possibly arithmetic) pass through jump function JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be determined or be considered an interprocedural invariant.
Referenced by add_value_to_lattice().
|
staticread |
Return the param lattices structure corresponding to the Ith formal parameter of the function described by INFO.
References DECL_INITIAL, print_generic_expr(), and TREE_OPERAND.
Referenced by copy_plats_to_inter(), propagate_aggs_accross_jump_function(), set_agg_lats_contain_variable(), and set_chain_of_aglats_contains_variable().
|
staticread |
Return the lattice corresponding to the scalar value of the Ith formal parameter of the function described by INFO.
References ipcp_lattice::bottom.
Referenced by update_specialized_profile().
|
inlinestatic |
Return whether LAT is a lattice with a single constant and without an undefined value.
Referenced by move_binfos_to_values().
| tree ipa_value_from_jfunc | ( | ) |
Determine whether JFUNC evaluates to a known value (that is either a constant or a binfo) and if so, return it. Otherwise return NULL. INFO describes the caller node so that pass-through jump functions can be evaluated.
References dump_file, and print_all_lattices().
Referenced by ipa_find_agg_cst_for_param(), and update_specialized_profile().
|
static |
Return true if this NODE is viable candidate for cloning.
When profile is available and function is hot, propagate into it even if calls seems cold; constant propagation can improve function's speed significantly.
|
static |
The decision stage. Iterate over the topological order of call graph nodes TOPO and make specialized clones if deemed beneficial.
|
static |
Discover newly direct outgoing edges from NODE which is a new clone with known KNOWN_VALS and make them direct.
Turning calls to direct calls will improve overall summary.
References cgraph_edge::caller, get_clone_agg_value(), ipcp_value_source::index, ipa_node_params::known_vals, NULL_TREE, ipcp_value_source::offset, ipcp_value_source::val, ipcp_value::value, and values_equal_for_ipcp_p().
|
static |
The IPCP driver.
Topological sort.
Do the interprocedural propagation.
Decide what constant propagation and cloning should be performed.
Free all IPCP structures.
|
static |
Edge duplication hook to grow the appropriate linked list in next_edge_clone.
|
static |
Initialization and computation of IPCP data structures. This is the initial intraprocedural analysis of functions, which gathers information to be propagated later on.
Referenced by identify_dead_nodes().
|
static |
Propagate constants, binfos and their effects from the summaries interprocedurally.
References cgraph_edge_max_uid.
|
static |
Read ipcp summary.
Referenced by identify_dead_nodes().
| DEBUG_FUNCTION bool ipcp_val_in_agg_replacements_p | ( | struct ipa_agg_replacement_value * | aggvals, |
| int | index, | ||
| HOST_WIDE_INT | offset, | ||
| tree | value | ||
| ) |
Return true if there is a replacement equivalent to VALUE, INDEX and OFFSET among those in the AGGVALS list.
| DEBUG_FUNCTION void ipcp_verify_propagated_values | ( | void | ) |
If checking is enabled, verify that no lattice is in the TOP state, i.e. not bottom, not containing a variable component and without any known value at the same time.
|
static |
Return true if it is at all technically possible to create clones of a NODE.
References cgraph_function_with_gimple_body_p(), and gcc_checking_assert.
|
static |
Write ipcp summary for nodes in SET.
Referenced by identify_dead_nodes().
|
staticread |
Turn KNOWN_AGGS into a list of aggreate replacement values.
References AVAIL_OVERWRITABLE, cgraph_edge::callee, cgraph_edge::caller, cgraph_edge_brings_all_agg_vals_for_node(), cgraph_edge_brings_all_scalars_for_node(), cgraph_edge_brings_value_p(), cgraph_function_node(), cgraph_node_name(), cgraph_redirect_edge_callee(), cgraph_edge::count, ipcp_value_source::cs, dump_file, IPA_NODE_REF, symtab_node_base::order, and ipcp_value::spec_node.
| ipa_opt_pass_d* make_pass_ipa_cp | ( | ) |
|
static |
Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an already existing lattice for the given OFFSET and SIZE, marking all skipped lattices as containing variable and checking for overlaps. If there is no already existing lattice for the OFFSET and VAL_SIZE, create one, initialize it with offset, size and contains_variable to PRE_EXISTING, and return true, unless there are too many already. If there are two many, return false. If there are overlaps turn whole DEST_PLATS to bottom and return false. If any skipped lattices were newly marked as containing variable, set *CHANGE to true.
|
static |
Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source parameter used for lattice value sources. Return true if DEST_PLATS changed in any way.
References ipa_jump_func::agg, gcc_assert, and ipa_agg_jump_function::items.
Copy KNOWN_BINFOS to KNOWN_VALS.
References ipcp_param_lattices::aggs, ipcp_param_lattices::aggs_contain_variable, ipcp_lattice::bottom, decide_about_value(), ipa_lat_is_single_const(), ipcp_value::next, ipcp_agg_lattice::next, ipcp_agg_lattice::offset, and ipcp_lattice::values.
|
static |
Given an original NODE and a VAL for which we have already created a specialized clone, look whether there are incoming edges that still lead into the old node but now also bring the requested value and also conform to all other criteria such that they can be redirected the the special node. This function can therefore redirect the final edge in a SCC.
|
staticread |
Pop a node from the stack in TOPO and return it or return NULL if the stack is empty.
References ipcp_param_lattices::aggs_contain_variable, ipcp_lattice::contains_variable, and ipcp_param_lattices::itself.
|
static |
Print all ipcp_lattices of all functions to F.
References symtab_node_base::alias, AVAIL_OVERWRITABLE, cgraph_function_body_availability(), cgraph_node_name(), dump_file, cgraph_node::local, NULL, symtab_node_base::order, cgraph_node::thunk, cgraph_thunk_info::thunk_p, and cgraph_local_info::versionable.
Referenced by ipa_value_from_jfunc().
|
static |
Print V which is extracted from a value in a lattice to F.
Referenced by update_specialized_profile().
|
static |
Print a lattice LAT to F.
|
static |
Propagate scalar values across jump function JFUNC that is associated with edge CS and put the values into DEST_LAT.
Currently we do not produce clobber aggregate jump functions, replace with merging when we do.
Currently we do not produce clobber aggregate jump
functions, replace with merging when we do.
References symtab_node_base::alias, AVAIL_OVERWRITABLE, cgraph_edge::callee, cgraph_alias_target(), cgraph_function_node(), cgraph_function_with_gimple_body_p(), symtab_node_base::definition, gcc_checking_assert, IPA_EDGE_REF, ipa_get_cs_argument_count(), ipa_get_ith_jump_func(), ipa_get_param_count(), ipa_get_parm_lattices(), IPA_NODE_REF, ipcp_param_lattices::itself, propagate_scalar_accross_jump_function(), set_all_contains_variable(), cgraph_node::thunk, and cgraph_thunk_info::thunk_p.
|
static |
Propagate constants from the caller to the callee of CS. INFO describes the caller.
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.
References ipa_agg_replacement_value::value.
|
static |
One pass of constants propagation along the call graph edges, from callers to callees (requires topological ordering in TOPO), iterate over strongly connected components.
First, iteratively propagate within the strongly connected component until all lattices stabilize.
Afterwards, propagate along edges leading out of the SCC, calculates
the local effects of the discovered constants and all valid values to
their topological sort.
|
static |
Propagate the estimated effects of individual values along the topological from the dependent values to those they depend on.
References cgraph_edge::callee, dump_file, dump_flags, ipa_find_reference(), ipa_get_controlled_uses(), IPA_NODE_REF, ipa_remove_reference(), ipa_set_controlled_uses(), IPA_UNDESCRIBED_USE, and NULL.
|
static |
Propagate scalar values across jump function JFUNC that is associated with edge CS and put the values into DEST_LAT.
If we would need to clone the caller and cannot, do not propagate.
TODO: We currently do not handle member method pointers in IPA-CP (we only use it for indirect inlining), we should propagate them too.
Referenced by propagate_aggs_accross_jump_function().
|
static |
Propagate values through an ancestor jump function JFUNC associated with edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX is the index of the source parameter.
|
static |
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.
Do not create new values when propagating within an SCC because if there are arithmetic functions with circular dependencies, there is infinite number of them and we would just make lattices bottom.
References ipa_binfo_from_known_type_jfunc(), and set_lattice_contains_variable().
|
inlinestatic |
Add NODE to the stack in TOPO, unless it is already there.
|
static |
Return the sum of A and B if none of them is bigger than INT_MAX/2, return the bigger one if otherwise.
References cgraph_indirect_call_info::agg_contents, cgraph_edge::indirect_info, ipa_get_indirect_edge_target_1(), ipa_make_edge_direct_to_target(), cgraph_edge::next_callee, cgraph_indirect_call_info::param_index, cgraph_indirect_call_info::polymorphic, and vNULL.
|
inlinestatic |
Mark all aggegate lattices in PLATS as containing an unknown value and return true if they were not previously marked as such.
References gcc_checking_assert, cgraph_edge::indirect_info, ipa_get_parm_lattices(), cgraph_indirect_call_info::param_index, and ipcp_param_lattices::virt_call.
|
inlinestatic |
Set all aggegate lattices in PLATS to bottom and return true if they were not previously set as such.
|
inlinestatic |
Mark bot aggregate and scalar lattices as containing an unknown variable, return true is any of them has not been marked as such so far.
References gcc_checking_assert, ipa_get_jf_pass_through_operation(), ipa_get_jf_pass_through_type_preserved(), and TREE_CODE.
Referenced by propagate_aggs_accross_jump_function().
|
static |
Set all AGLAT and all other aggregate lattices reachable by next pointers as containing an unknown value.
References ipcp_param_lattices::aggs_bottom, cgraph_edge::caller, ipa_get_jf_pass_through_formal_id(), ipa_get_jf_pass_through_operation(), ipa_get_parm_lattices(), IPA_JF_PASS_THROUGH, IPA_NODE_REF, and ipa_jump_func::type.
|
static |
If DEST_PLATS already has aggregate items, check that aggs_by_ref matches NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all other cases, return false). If there are no aggregate items, set aggs_by_ref to NEW_AGGS_BY_REF.
References ipcp_agg_lattice::next, and set_lattice_contains_variable().
|
inlinestatic |
Mark lattice as containing an unknown value and return true if it previously was not marked as such.
Referenced by add_value_to_lattice(), propagate_vals_accross_pass_through(), and set_check_aggs_by_ref().
|
inlinestatic |
Set lattice LAT to bottom and return true if it previously was not set as such.
|
static |
Transitively mark all callees of NODE within the same SCC as not dead.
References symtab_node_base::decl, dump_file, FOR_EACH_FUNCTION_WITH_GIMPLE_BODY, ipa_analyze_node(), ipa_register_cgraph_hooks(), cgraph_node::local, tree_versionable_function_p(), and cgraph_local_info::versionable.
|
static |
After a specialized NEW_NODE version of ORIG_NODE has been created, update their profile information to reflect this.
References bitmap_set_bit, ipa_is_param_used(), and TREE_CODE.
|
static |
Update the respective profile of specialized NEW_NODE and the original ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM have been redirected to the specialized version.
References cgraph_edge::caller, count, dump_file, dump_flags, FOR_EACH_VEC_ELT, ipa_dump_param(), IPA_EDGE_REF, ipa_get_cs_argument_count(), ipa_get_ith_jump_func(), ipa_get_param_count(), ipa_get_scalar_lat(), IPA_NODE_REF, ipa_value_from_jfunc(), NULL_TREE, print_ipcp_constant_value(), and values_equal_for_ipcp_p().
|
static |
Return true iff X and Y should be considered equal values by IPA-CP.
Referenced by intersect_with_agg_replacements(), ipcp_discover_new_direct_edges(), and update_specialized_profile().
Variable Documentation
| alloc_pool ipcp_agg_lattice_pool |
| alloc_pool ipcp_sources_pool |
| alloc_pool ipcp_values_pool |
Allocation pools for values and their sources in ipa-cp.
|
static |
Maximal count found in program.
|
static |
|
static |
Vector of pointers which for linked lists of clones of an original crgaph edge.
|
static |
Original overall size of the program.
Referenced by dump_histogram().
|
static |
Head of the linked list of topologically sorted values.
