/* Interprocedural scalar replacement of aggregates Copyright (C) 2008-2020 Free Software Foundation, Inc. Contributed by Martin Jambor This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see . */ /* IPA-SRA is an interprocedural pass that removes unused function return values (turning functions returning a value which is never used into void functions), removes unused function parameters. It can also replace an aggregate parameter by a set of other parameters representing part of the original, turning those passed by reference into new ones which pass the value directly. The pass is a true IPA one, which means that it works in three stages in order to be able to take advantage of LTO. First, summaries about functions and each calls are generated. Function summaries (often called call graph node summaries) contain mainly information about which parameters are potential transformation candidates and which bits of candidates are accessed. We differentiate between accesses done as a part of a call statement (which might be not necessary if the callee is also transformed) and others (which are mandatory). Call summaries (often called call graph edge summaries) contain information about which function formal parameters feed into which actual call arguments so that if two parameters are only used in a sum which is then passed to another function which then however does not use this parameter, all three parameters of the two functions can be eliminated. Edge summaries also have flags whether the return value is used or if it is only returned in the caller too. In LTO mode these summaries are then streamed to the object file in the compilation phase and streamed back in in the WPA analysis stage. The interprocedural analysis phase traverses the graph in topological order in two sweeps, one in each direction. First, from callees to callers for parameter removal and splitting. Each strongly-connected component is processed iteratively until the situation in it stabilizes. The pass from callers to callees is then carried out to remove unused return values in a very similar fashion. Because parameter manipulation has big implications for call redirection which is done only after all call graph nodes materialize, the transformation phase is not part of this patch but is carried out by the clone materialization and edge redirection itself, see comments in ipa-param-manipulation.h for more details. */ #include "config.h" #include "system.h" #include "coretypes.h" #include "backend.h" #include "tree.h" #include "gimple.h" #include "predict.h" #include "tree-pass.h" #include "ssa.h" #include "cgraph.h" #include "gimple-pretty-print.h" #include "alias.h" #include "tree-eh.h" #include "gimple-iterator.h" #include "gimple-walk.h" #include "tree-dfa.h" #include "tree-sra.h" #include "alloc-pool.h" #include "symbol-summary.h" #include "dbgcnt.h" #include "tree-inline.h" #include "ipa-utils.h" #include "builtins.h" #include "cfganal.h" #include "tree-streamer.h" #include "internal-fn.h" /* Bits used to track size of an aggregate in bytes interprocedurally. */ #define ISRA_ARG_SIZE_LIMIT_BITS 16 #define ISRA_ARG_SIZE_LIMIT (1 << ISRA_ARG_SIZE_LIMIT_BITS) /* How many parameters can feed into a call actual argument and still be tracked. */ #define IPA_SRA_MAX_PARAM_FLOW_LEN 7 /* Structure describing accesses to a specific portion of an aggregate parameter, as given by the offset and size. Any smaller accesses that occur within a function that fall within another access form a tree. The pass cannot analyze parameters with only partially overlapping accesses. */ struct GTY(()) param_access { /* Type that a potential replacement should have. This field only has meaning in the summary building and transformation phases, when it is reconstructed from the body. Must not be touched in IPA analysis stage. */ tree type; /* Alias reference type to be used in MEM_REFs when adjusting caller arguments. */ tree alias_ptr_type; /* Values returned by get_ref_base_and_extent but converted to bytes and stored as unsigned ints. */ unsigned unit_offset; unsigned unit_size : ISRA_ARG_SIZE_LIMIT_BITS; /* Set once we are sure that the access will really end up in a potentially transformed function - initially not set for portions of formal parameters that are only used as actual function arguments passed to callees. */ unsigned certain : 1; /* Set if the access has a reversed scalar storage order. */ unsigned reverse : 1; }; /* This structure has the same purpose as the one above and additionally it contains some fields that are only necessary in the summary generation phase. */ struct gensum_param_access { /* Values returned by get_ref_base_and_extent. */ HOST_WIDE_INT offset; HOST_WIDE_INT size; /* if this access has any children (in terms of the definition above), this points to the first one. */ struct gensum_param_access *first_child; /* In intraprocedural SRA, pointer to the next sibling in the access tree as described above. */ struct gensum_param_access *next_sibling; /* Type that a potential replacement should have. This field only has meaning in the summary building and transformation phases, when it is reconstructed from the body. Must not be touched in IPA analysis stage. */ tree type; /* Alias reference type to be used in MEM_REFs when adjusting caller arguments. */ tree alias_ptr_type; /* Have there been writes to or reads from this exact location except for as arguments to a function call that can be tracked. */ bool nonarg; /* Set if the access has a reversed scalar storage order. */ bool reverse; }; /* Summary describing a parameter in the IPA stages. */ struct GTY(()) isra_param_desc { /* List of access representatives to the parameters, sorted according to their offset. */ vec *accesses; /* Unit size limit of total size of all replacements. */ unsigned param_size_limit : ISRA_ARG_SIZE_LIMIT_BITS; /* Sum of unit sizes of all certain replacements. */ unsigned size_reached : ISRA_ARG_SIZE_LIMIT_BITS; /* A parameter that is used only in call arguments and can be removed if all concerned actual arguments are removed. */ unsigned locally_unused : 1; /* An aggregate that is a candidate for breaking up or complete removal. */ unsigned split_candidate : 1; /* Is this a parameter passing stuff by reference? */ unsigned by_ref : 1; }; /* Structure used when generating summaries that describes a parameter. */ struct gensum_param_desc { /* Roots of param_accesses. */ gensum_param_access *accesses; /* Number of accesses in the access tree rooted in field accesses. */ unsigned access_count; /* If the below is non-zero, this is the number of uses as actual arguments. */ int call_uses; /* Number of times this parameter has been directly passed to. */ unsigned ptr_pt_count; /* Size limit of total size of all replacements. */ unsigned param_size_limit; /* Sum of sizes of nonarg accesses. */ unsigned nonarg_acc_size; /* A parameter that is used only in call arguments and can be removed if all concerned actual arguments are removed. */ bool locally_unused; /* An aggregate that is a candidate for breaking up or a pointer passing data by reference that is a candidate for being converted to a set of parameters passing those data by value. */ bool split_candidate; /* Is this a parameter passing stuff by reference? */ bool by_ref; /* The number of this parameter as they are ordered in function decl. */ int param_number; /* For parameters passing data by reference, this is parameter index to compute indices to bb_dereferences. */ int deref_index; }; /* Properly deallocate accesses of DESC. TODO: Since this data structure is not in GC memory, this is not necessary and we can consider removing the function. */ static void free_param_decl_accesses (isra_param_desc *desc) { unsigned len = vec_safe_length (desc->accesses); for (unsigned i = 0; i < len; ++i) ggc_free ((*desc->accesses)[i]); vec_free (desc->accesses); } /* Class used to convey information about functions from the intra-procedural analysis stage to inter-procedural one. */ class GTY((for_user)) isra_func_summary { public: /* initialize the object. */ isra_func_summary () : m_parameters (NULL), m_candidate (false), m_returns_value (false), m_return_ignored (false), m_queued (false) {} /* Destroy m_parameters. */ ~isra_func_summary (); /* Mark the function as not a candidate for any IPA-SRA transformation. Return true if it was a candidate until now. */ bool zap (); /* Vector of parameter descriptors corresponding to the function being analyzed. */ vec *m_parameters; /* Whether the node is even a candidate for any IPA-SRA transformation at all. */ unsigned m_candidate : 1; /* Whether the original function returns any value. */ unsigned m_returns_value : 1; /* Set to true if all call statements do not actually use the returned value. */ unsigned m_return_ignored : 1; /* Whether the node is already queued in IPA SRA stack during processing of call graphs SCCs. */ unsigned m_queued : 1; }; /* Clean up and deallocate isra_func_summary points to. TODO: Since this data structure is not in GC memory, this is not necessary and we can consider removing the destructor. */ isra_func_summary::~isra_func_summary () { unsigned len = vec_safe_length (m_parameters); for (unsigned i = 0; i < len; ++i) free_param_decl_accesses (&(*m_parameters)[i]); vec_free (m_parameters); } /* Mark the function as not a candidate for any IPA-SRA transformation. Return true if it was a candidate until now. */ bool isra_func_summary::zap () { bool ret = m_candidate; m_candidate = false; unsigned len = vec_safe_length (m_parameters); for (unsigned i = 0; i < len; ++i) free_param_decl_accesses (&(*m_parameters)[i]); vec_free (m_parameters); return ret; } /* Structure to describe which formal parameters feed into a particular actual arguments. */ struct isra_param_flow { /* Number of elements in array inputs that contain valid data. */ char length; /* Indices of formal parameters that feed into the described actual argument. If aggregate_pass_through or pointer_pass_through below are true, it must contain exactly one element which is passed through from a formal parameter if the given number. Otherwise, the array contains indices of callee's formal parameters which are used to calculate value of this actual argument. */ unsigned char inputs[IPA_SRA_MAX_PARAM_FLOW_LEN]; /* Offset within the formal parameter. */ unsigned unit_offset; /* Size of the portion of the formal parameter that is being passed. */ unsigned unit_size : ISRA_ARG_SIZE_LIMIT_BITS; /* True when the value of this actual copy is a portion of a formal parameter. */ unsigned aggregate_pass_through : 1; /* True when the value of this actual copy is a verbatim pass through of an obtained pointer. */ unsigned pointer_pass_through : 1; /* True when it is safe to copy access candidates here from the callee, which would mean introducing dereferences into callers of the caller. */ unsigned safe_to_import_accesses : 1; }; /* Structure used to convey information about calls from the intra-procedural analysis stage to inter-procedural one. */ class isra_call_summary { public: isra_call_summary () : m_arg_flow (), m_return_ignored (false), m_return_returned (false), m_bit_aligned_arg (false) {} void init_inputs (unsigned arg_count); void dump (FILE *f); /* Information about what formal parameters of the caller are used to compute individual actual arguments of this call. */ auto_vec m_arg_flow; /* Set to true if the call statement does not have a LHS. */ unsigned m_return_ignored : 1; /* Set to true if the LHS of call statement is only used to construct the return value of the caller. */ unsigned m_return_returned : 1; /* Set when any of the call arguments are not byte-aligned. */ unsigned m_bit_aligned_arg : 1; }; /* Class to manage function summaries. */ class GTY((user)) ipa_sra_function_summaries : public function_summary { public: ipa_sra_function_summaries (symbol_table *table, bool ggc): function_summary (table, ggc) { } virtual void duplicate (cgraph_node *, cgraph_node *, isra_func_summary *old_sum, isra_func_summary *new_sum); }; /* Hook that is called by summary when a node is duplicated. */ void ipa_sra_function_summaries::duplicate (cgraph_node *, cgraph_node *, isra_func_summary *old_sum, isra_func_summary *new_sum) { /* TODO: Somehow stop copying when ISRA is doing the cloning, it is useless. */ new_sum->m_candidate = old_sum->m_candidate; new_sum->m_returns_value = old_sum->m_returns_value; new_sum->m_return_ignored = old_sum->m_return_ignored; gcc_assert (!old_sum->m_queued); new_sum->m_queued = false; unsigned param_count = vec_safe_length (old_sum->m_parameters); if (!param_count) return; vec_safe_reserve_exact (new_sum->m_parameters, param_count); new_sum->m_parameters->quick_grow_cleared (param_count); for (unsigned i = 0; i < param_count; i++) { isra_param_desc *s = &(*old_sum->m_parameters)[i]; isra_param_desc *d = &(*new_sum->m_parameters)[i]; d->param_size_limit = s->param_size_limit; d->size_reached = s->size_reached; d->locally_unused = s->locally_unused; d->split_candidate = s->split_candidate; d->by_ref = s->by_ref; unsigned acc_count = vec_safe_length (s->accesses); vec_safe_reserve_exact (d->accesses, acc_count); for (unsigned j = 0; j < acc_count; j++) { param_access *from = (*s->accesses)[j]; param_access *to = ggc_cleared_alloc (); to->type = from->type; to->alias_ptr_type = from->alias_ptr_type; to->unit_offset = from->unit_offset; to->unit_size = from->unit_size; to->certain = from->certain; d->accesses->quick_push (to); } } } /* Pointer to the pass function summary holder. */ static GTY(()) ipa_sra_function_summaries *func_sums; /* Class to manage call summaries. */ class ipa_sra_call_summaries: public call_summary { public: ipa_sra_call_summaries (symbol_table *table): call_summary (table) { } /* Duplicate info when an edge is cloned. */ virtual void duplicate (cgraph_edge *, cgraph_edge *, isra_call_summary *old_sum, isra_call_summary *new_sum); }; static ipa_sra_call_summaries *call_sums; /* Initialize m_arg_flow of a particular instance of isra_call_summary. ARG_COUNT is the number of actual arguments passed. */ void isra_call_summary::init_inputs (unsigned arg_count) { if (arg_count == 0) { gcc_checking_assert (m_arg_flow.length () == 0); return; } if (m_arg_flow.length () == 0) { m_arg_flow.reserve_exact (arg_count); m_arg_flow.quick_grow_cleared (arg_count); } else gcc_checking_assert (arg_count == m_arg_flow.length ()); } /* Dump all information in call summary to F. */ void isra_call_summary::dump (FILE *f) { if (m_return_ignored) fprintf (f, " return value ignored\n"); if (m_return_returned) fprintf (f, " return value used only to compute caller return value\n"); for (unsigned i = 0; i < m_arg_flow.length (); i++) { fprintf (f, " Parameter %u:\n", i); isra_param_flow *ipf = &m_arg_flow[i]; if (ipf->length) { bool first = true; fprintf (f, " Scalar param sources: "); for (int j = 0; j < ipf->length; j++) { if (!first) fprintf (f, ", "); else first = false; fprintf (f, "%i", (int) ipf->inputs[j]); } fprintf (f, "\n"); } if (ipf->aggregate_pass_through) fprintf (f, " Aggregate pass through from the param given above, " "unit offset: %u , unit size: %u\n", ipf->unit_offset, ipf->unit_size); if (ipf->pointer_pass_through) fprintf (f, " Pointer pass through from the param given above, " "safe_to_import_accesses: %u\n", ipf->safe_to_import_accesses); } } /* Duplicate edge summary when an edge is cloned. */ void ipa_sra_call_summaries::duplicate (cgraph_edge *, cgraph_edge *, isra_call_summary *old_sum, isra_call_summary *new_sum) { unsigned arg_count = old_sum->m_arg_flow.length (); new_sum->init_inputs (arg_count); for (unsigned i = 0; i < arg_count; i++) new_sum->m_arg_flow[i] = old_sum->m_arg_flow[i]; new_sum->m_return_ignored = old_sum->m_return_ignored; new_sum->m_return_returned = old_sum->m_return_returned; new_sum->m_bit_aligned_arg = old_sum->m_bit_aligned_arg; } /* With all GTY stuff done, we can move to anonymous namespace. */ namespace { /* Quick mapping from a decl to its param descriptor. */ hash_map *decl2desc; /* Countdown of allowed Alias analysis steps during summary building. */ int aa_walking_limit; /* This is a table in which for each basic block and parameter there is a distance (offset + size) in that parameter which is dereferenced and accessed in that BB. */ HOST_WIDE_INT *bb_dereferences = NULL; /* How many by-reference parameters there are in the current function. */ int by_ref_count; /* Bitmap of BBs that can cause the function to "stop" progressing by returning, throwing externally, looping infinitely or calling a function which might abort etc.. */ bitmap final_bbs; /* Obstack to allocate various small structures required only when generating summary for a function. */ struct obstack gensum_obstack; /* Return false the function is apparently unsuitable for IPA-SRA based on it's attributes, return true otherwise. NODE is the cgraph node of the current function. */ static bool ipa_sra_preliminary_function_checks (cgraph_node *node) { if (!node->can_change_signature) { if (dump_file) fprintf (dump_file, "Function cannot change signature.\n"); return false; } if (!tree_versionable_function_p (node->decl)) { if (dump_file) fprintf (dump_file, "Function is not versionable.\n"); return false; } if (!opt_for_fn (node->decl, optimize) || !opt_for_fn (node->decl, flag_ipa_sra)) { if (dump_file) fprintf (dump_file, "Not optimizing or IPA-SRA turned off for this " "function.\n"); return false; } if (DECL_VIRTUAL_P (node->decl)) { if (dump_file) fprintf (dump_file, "Function is a virtual method.\n"); return false; } struct function *fun = DECL_STRUCT_FUNCTION (node->decl); if (fun->stdarg) { if (dump_file) fprintf (dump_file, "Function uses stdarg. \n"); return false; } if (TYPE_ATTRIBUTES (TREE_TYPE (node->decl))) { if (dump_file) fprintf (dump_file, "Function type has attributes. \n"); return false; } if (DECL_DISREGARD_INLINE_LIMITS (node->decl)) { if (dump_file) fprintf (dump_file, "Always inline function will be inlined " "anyway. \n"); return false; } return true; } /* Print access tree starting at ACCESS to F. */ static void dump_gensum_access (FILE *f, gensum_param_access *access, unsigned indent) { fprintf (f, " "); for (unsigned i = 0; i < indent; i++) fprintf (f, " "); fprintf (f, " * Access to offset: " HOST_WIDE_INT_PRINT_DEC, access->offset); fprintf (f, ", size: " HOST_WIDE_INT_PRINT_DEC, access->size); fprintf (f, ", type: "); print_generic_expr (f, access->type); fprintf (f, ", alias_ptr_type: "); print_generic_expr (f, access->alias_ptr_type); fprintf (f, ", nonarg: %u, reverse: %u\n", access->nonarg, access->reverse); for (gensum_param_access *ch = access->first_child; ch; ch = ch->next_sibling) dump_gensum_access (f, ch, indent + 2); } /* Print access tree starting at ACCESS to F. */ static void dump_isra_access (FILE *f, param_access *access) { fprintf (f, " * Access to unit offset: %u", access->unit_offset); fprintf (f, ", unit size: %u", access->unit_size); fprintf (f, ", type: "); print_generic_expr (f, access->type); fprintf (f, ", alias_ptr_type: "); print_generic_expr (f, access->alias_ptr_type); if (access->certain) fprintf (f, ", certain"); else fprintf (f, ", not-certain"); if (access->reverse) fprintf (f, ", reverse"); fprintf (f, "\n"); } /* Dump access tree starting at ACCESS to stderr. */ DEBUG_FUNCTION void debug_isra_access (param_access *access) { dump_isra_access (stderr, access); } /* Dump DESC to F. */ static void dump_gensum_param_descriptor (FILE *f, gensum_param_desc *desc) { if (desc->locally_unused) fprintf (f, " unused with %i call_uses\n", desc->call_uses); if (!desc->split_candidate) { fprintf (f, " not a candidate\n"); return; } if (desc->by_ref) fprintf (f, " by_ref with %u pass throughs\n", desc->ptr_pt_count); for (gensum_param_access *acc = desc->accesses; acc; acc = acc->next_sibling) dump_gensum_access (f, acc, 2); } /* Dump all parameter descriptors in IFS, assuming it describes FNDECL, to F. */ static void dump_gensum_param_descriptors (FILE *f, tree fndecl, vec *param_descriptions) { tree parm = DECL_ARGUMENTS (fndecl); for (unsigned i = 0; i < param_descriptions->length (); ++i, parm = DECL_CHAIN (parm)) { fprintf (f, " Descriptor for parameter %i ", i); print_generic_expr (f, parm, TDF_UID); fprintf (f, "\n"); dump_gensum_param_descriptor (f, &(*param_descriptions)[i]); } } /* Dump DESC to F. */ static void dump_isra_param_descriptor (FILE *f, isra_param_desc *desc) { if (desc->locally_unused) { fprintf (f, " (locally) unused\n"); } if (!desc->split_candidate) { fprintf (f, " not a candidate for splitting\n"); return; } fprintf (f, " param_size_limit: %u, size_reached: %u%s\n", desc->param_size_limit, desc->size_reached, desc->by_ref ? ", by_ref" : ""); for (unsigned i = 0; i < vec_safe_length (desc->accesses); ++i) { param_access *access = (*desc->accesses)[i]; dump_isra_access (f, access); } } /* Dump all parameter descriptors in IFS, assuming it describes FNDECL, to F. */ static void dump_isra_param_descriptors (FILE *f, tree fndecl, isra_func_summary *ifs) { tree parm = DECL_ARGUMENTS (fndecl); if (!ifs->m_parameters) { fprintf (f, " parameter descriptors not available\n"); return; } for (unsigned i = 0; i < ifs->m_parameters->length (); ++i, parm = DECL_CHAIN (parm)) { fprintf (f, " Descriptor for parameter %i ", i); print_generic_expr (f, parm, TDF_UID); fprintf (f, "\n"); dump_isra_param_descriptor (f, &(*ifs->m_parameters)[i]); } } /* Add SRC to inputs of PARAM_FLOW, unless it would exceed storage. If the function fails return false, otherwise return true. SRC must fit into an unsigned char. Used for purposes of transitive unused parameter removal. */ static bool add_src_to_param_flow (isra_param_flow *param_flow, int src) { gcc_checking_assert (src >= 0 && src <= UCHAR_MAX); if (param_flow->length == IPA_SRA_MAX_PARAM_FLOW_LEN) return false; param_flow->inputs[(int) param_flow->length] = src; param_flow->length++; return true; } /* Add a SRC to the inputs of PARAM_FLOW unless it is already there and assert it is the only input. Used for purposes of transitive parameter splitting. */ static void set_single_param_flow_source (isra_param_flow *param_flow, int src) { gcc_checking_assert (src >= 0 && src <= UCHAR_MAX); if (param_flow->length == 0) { param_flow->inputs[0] = src; param_flow->length = 1; } else if (param_flow->length == 1) gcc_assert (param_flow->inputs[0] == src); else gcc_unreachable (); } /* Assert that there is only a single value in PARAM_FLOW's inputs and return it. */ static unsigned get_single_param_flow_source (const isra_param_flow *param_flow) { gcc_assert (param_flow->length == 1); return param_flow->inputs[0]; } /* Inspect all uses of NAME and simple arithmetic calculations involving NAME in NODE and return a negative number if any of them is used for something else than either an actual call argument, simple arithmetic operation or debug statement. If there are no such uses, return the number of actual arguments that this parameter eventually feeds to (or zero if there is none). For any such parameter, mark PARM_NUM as one of its sources. ANALYZED is a bitmap that tracks which SSA names we have already started investigating. */ static int isra_track_scalar_value_uses (cgraph_node *node, tree name, int parm_num, bitmap analyzed) { int res = 0; imm_use_iterator imm_iter; gimple *stmt; FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name) { if (is_gimple_debug (stmt)) continue; /* TODO: We could handle at least const builtin functions like arithmetic operations below. */ if (is_gimple_call (stmt)) { int all_uses = 0; use_operand_p use_p; FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter) all_uses++; gcall *call = as_a (stmt); unsigned arg_count; if (gimple_call_internal_p (call) || (arg_count = gimple_call_num_args (call)) == 0) { res = -1; BREAK_FROM_IMM_USE_STMT (imm_iter); } cgraph_edge *cs = node->get_edge (stmt); gcc_checking_assert (cs); isra_call_summary *csum = call_sums->get_create (cs); csum->init_inputs (arg_count); int simple_uses = 0; for (unsigned i = 0; i < arg_count; i++) if (gimple_call_arg (call, i) == name) { if (!add_src_to_param_flow (&csum->m_arg_flow[i], parm_num)) { simple_uses = -1; break; } simple_uses++; } if (simple_uses < 0 || all_uses != simple_uses) { res = -1; BREAK_FROM_IMM_USE_STMT (imm_iter); } res += all_uses; } else if ((is_gimple_assign (stmt) && !gimple_has_volatile_ops (stmt)) || gimple_code (stmt) == GIMPLE_PHI) { tree lhs; if (gimple_code (stmt) == GIMPLE_PHI) lhs = gimple_phi_result (stmt); else lhs = gimple_assign_lhs (stmt); if (TREE_CODE (lhs) != SSA_NAME) { res = -1; BREAK_FROM_IMM_USE_STMT (imm_iter); } gcc_assert (!gimple_vdef (stmt)); if (bitmap_set_bit (analyzed, SSA_NAME_VERSION (lhs))) { int tmp = isra_track_scalar_value_uses (node, lhs, parm_num, analyzed); if (tmp < 0) { res = tmp; BREAK_FROM_IMM_USE_STMT (imm_iter); } res += tmp; } } else { res = -1; BREAK_FROM_IMM_USE_STMT (imm_iter); } } return res; } /* Inspect all uses of PARM, which must be a gimple register, in FUN (which is also described by NODE) and simple arithmetic calculations involving PARM and return false if any of them is used for something else than either an actual call argument, simple arithmetic operation or debug statement. If there are no such uses, return true and store the number of actual arguments that this parameter eventually feeds to (or zero if there is none) to *CALL_USES_P. For any such parameter, mark PARM_NUM as one of its sources. This function is similar to ptr_parm_has_nonarg_uses but its results are meant for unused parameter removal, as opposed to splitting of parameters passed by reference or converting them to passed by value. */ static bool isra_track_scalar_param_local_uses (function *fun, cgraph_node *node, tree parm, int parm_num, int *call_uses_p) { gcc_checking_assert (is_gimple_reg (parm)); tree name = ssa_default_def (fun, parm); if (!name || has_zero_uses (name)) { *call_uses_p = 0; return false; } /* Edge summaries can only handle callers with fewer than 256 parameters. */ if (parm_num > UCHAR_MAX) return true; bitmap analyzed = BITMAP_ALLOC (NULL); int call_uses = isra_track_scalar_value_uses (node, name, parm_num, analyzed); BITMAP_FREE (analyzed); if (call_uses < 0) return true; *call_uses_p = call_uses; return false; } /* Scan immediate uses of a default definition SSA name of a parameter PARM and examine whether there are any nonarg uses that are not actual arguments or otherwise infeasible uses. If so, return true, otherwise return false. Create pass-through IPA flow records for any direct uses as argument calls and if returning false, store their number into *PT_COUNT_P. NODE and FUN must represent the function that is currently analyzed, PARM_NUM must be the index of the analyzed parameter. This function is similar to isra_track_scalar_param_local_uses but its results are meant for splitting of parameters passed by reference or turning them into bits passed by value, as opposed to generic unused parameter removal. */ static bool ptr_parm_has_nonarg_uses (cgraph_node *node, function *fun, tree parm, int parm_num, unsigned *pt_count_p) { imm_use_iterator ui; gimple *stmt; tree name = ssa_default_def (fun, parm); bool ret = false; unsigned pt_count = 0; if (!name || has_zero_uses (name)) return false; /* Edge summaries can only handle callers with fewer than 256 parameters. */ if (parm_num > UCHAR_MAX) return true; FOR_EACH_IMM_USE_STMT (stmt, ui, name) { unsigned uses_ok = 0; use_operand_p use_p; if (is_gimple_debug (stmt)) continue; if (gimple_assign_single_p (stmt)) { tree rhs = gimple_assign_rhs1 (stmt); while (handled_component_p (rhs)) rhs = TREE_OPERAND (rhs, 0); if (TREE_CODE (rhs) == MEM_REF && TREE_OPERAND (rhs, 0) == name && integer_zerop (TREE_OPERAND (rhs, 1)) && types_compatible_p (TREE_TYPE (rhs), TREE_TYPE (TREE_TYPE (name))) && !TREE_THIS_VOLATILE (rhs)) uses_ok++; } else if (is_gimple_call (stmt)) { gcall *call = as_a (stmt); unsigned arg_count; if (gimple_call_internal_p (call) || (arg_count = gimple_call_num_args (call)) == 0) { ret = true; BREAK_FROM_IMM_USE_STMT (ui); } cgraph_edge *cs = node->get_edge (stmt); gcc_checking_assert (cs); isra_call_summary *csum = call_sums->get_create (cs); csum->init_inputs (arg_count); for (unsigned i = 0; i < arg_count; ++i) { tree arg = gimple_call_arg (stmt, i); if (arg == name) { /* TODO: Allow &MEM_REF[name + offset] here, ipa_param_body_adjustments::modify_call_stmt has to be adjusted too. */ csum->m_arg_flow[i].pointer_pass_through = true; set_single_param_flow_source (&csum->m_arg_flow[i], parm_num); pt_count++; uses_ok++; continue; } while (handled_component_p (arg)) arg = TREE_OPERAND (arg, 0); if (TREE_CODE (arg) == MEM_REF && TREE_OPERAND (arg, 0) == name && integer_zerop (TREE_OPERAND (arg, 1)) && types_compatible_p (TREE_TYPE (arg), TREE_TYPE (TREE_TYPE (name))) && !TREE_THIS_VOLATILE (arg)) uses_ok++; } } /* If the number of valid uses does not match the number of uses in this stmt there is an unhandled use. */ unsigned all_uses = 0; FOR_EACH_IMM_USE_ON_STMT (use_p, ui) all_uses++; gcc_checking_assert (uses_ok <= all_uses); if (uses_ok != all_uses) { ret = true; BREAK_FROM_IMM_USE_STMT (ui); } } *pt_count_p = pt_count; return ret; } /* Initialize vector of parameter descriptors of NODE. Return true if there are any candidates for splitting or unused aggregate parameter removal (the function may return false if there are candidates for removal of register parameters) and function body must be scanned. */ static bool create_parameter_descriptors (cgraph_node *node, vec *param_descriptions) { function *fun = DECL_STRUCT_FUNCTION (node->decl); bool ret = false; int num = 0; for (tree parm = DECL_ARGUMENTS (node->decl); parm; parm = DECL_CHAIN (parm), num++) { const char *msg; gensum_param_desc *desc = &(*param_descriptions)[num]; /* param_descriptions vector is grown cleared in the caller. */ desc->param_number = num; decl2desc->put (parm, desc); if (dump_file && (dump_flags & TDF_DETAILS)) print_generic_expr (dump_file, parm, TDF_UID); int scalar_call_uses; tree type = TREE_TYPE (parm); if (TREE_THIS_VOLATILE (parm)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " not a candidate, is volatile\n"); continue; } if (!is_gimple_reg_type (type) && is_va_list_type (type)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " not a candidate, is a va_list type\n"); continue; } if (TREE_ADDRESSABLE (parm)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " not a candidate, is addressable\n"); continue; } if (TREE_ADDRESSABLE (type)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " not a candidate, type cannot be split\n"); continue; } if (is_gimple_reg (parm) && !isra_track_scalar_param_local_uses (fun, node, parm, num, &scalar_call_uses)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " is a scalar with only %i call uses\n", scalar_call_uses); desc->locally_unused = true; desc->call_uses = scalar_call_uses; } if (POINTER_TYPE_P (type)) { type = TREE_TYPE (type); if (TREE_CODE (type) == FUNCTION_TYPE || TREE_CODE (type) == METHOD_TYPE) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " not a candidate, reference to " "a function\n"); continue; } if (TYPE_VOLATILE (type)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " not a candidate, reference to " "a volatile type\n"); continue; } if (TREE_CODE (type) == ARRAY_TYPE && TYPE_NONALIASED_COMPONENT (type)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " not a candidate, reference to " "a nonaliased component array\n"); continue; } if (!is_gimple_reg (parm)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " not a candidate, a reference which is " "not a gimple register (probably addressable)\n"); continue; } if (is_va_list_type (type)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " not a candidate, reference to " "a va list\n"); continue; } if (ptr_parm_has_nonarg_uses (node, fun, parm, num, &desc->ptr_pt_count)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " not a candidate, reference has " "nonarg uses\n"); continue; } desc->by_ref = true; } else if (!AGGREGATE_TYPE_P (type)) { /* This is in an else branch because scalars passed by reference are still candidates to be passed by value. */ if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " not a candidate, not an aggregate\n"); continue; } if (!COMPLETE_TYPE_P (type)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " not a candidate, not a complete type\n"); continue; } if (!tree_fits_uhwi_p (TYPE_SIZE (type))) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " not a candidate, size not representable\n"); continue; } unsigned HOST_WIDE_INT type_size = tree_to_uhwi (TYPE_SIZE (type)) / BITS_PER_UNIT; if (type_size == 0 || type_size >= ISRA_ARG_SIZE_LIMIT) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " not a candidate, has zero or huge size\n"); continue; } if (type_internals_preclude_sra_p (type, &msg)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " not a candidate, %s\n", msg); continue; } if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " is a candidate\n"); ret = true; desc->split_candidate = true; if (desc->by_ref) desc->deref_index = by_ref_count++; } return ret; } /* Return pointer to descriptor of parameter DECL or NULL if it cannot be found, which happens if DECL is for a static chain. */ static gensum_param_desc * get_gensum_param_desc (tree decl) { gcc_checking_assert (TREE_CODE (decl) == PARM_DECL); gensum_param_desc **slot = decl2desc->get (decl); if (!slot) /* This can happen for static chains which we cannot handle so far. */ return NULL; gcc_checking_assert (*slot); return *slot; } /* Remove parameter described by DESC from candidates for IPA-SRA splitting and write REASON to the dump file if there is one. */ static void disqualify_split_candidate (gensum_param_desc *desc, const char *reason) { if (!desc->split_candidate) return; if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "! Disqualifying parameter number %i - %s\n", desc->param_number, reason); desc->split_candidate = false; } /* Remove DECL from candidates for IPA-SRA and write REASON to the dump file if there is one. */ static void disqualify_split_candidate (tree decl, const char *reason) { gensum_param_desc *desc = get_gensum_param_desc (decl); if (desc) disqualify_split_candidate (desc, reason); } /* Allocate a new access to DESC and fill it in with OFFSET and SIZE. But first, check that there are not too many of them already. If so, do not allocate anything and return NULL. */ static gensum_param_access * allocate_access (gensum_param_desc *desc, HOST_WIDE_INT offset, HOST_WIDE_INT size) { if (desc->access_count == (unsigned) param_ipa_sra_max_replacements) { disqualify_split_candidate (desc, "Too many replacement candidates"); return NULL; } gensum_param_access *access = (gensum_param_access *) obstack_alloc (&gensum_obstack, sizeof (gensum_param_access)); memset (access, 0, sizeof (*access)); access->offset = offset; access->size = size; return access; } /* In what context scan_expr_access has been called, whether it deals with a load, a function argument, or a store. Please note that in rare circumstances when it is not clear if the access is a load or store, ISRA_CTX_STORE is used too. */ enum isra_scan_context {ISRA_CTX_LOAD, ISRA_CTX_ARG, ISRA_CTX_STORE}; /* Return an access describing memory access to the variable described by DESC at OFFSET with SIZE in context CTX, starting at pointer to the linked list at a certain tree level FIRST. Attempt to create it and put into the appropriate place in the access tree if does not exist, but fail and return NULL if there are already too many accesses, if it would create a partially overlapping access or if an access would end up within a pre-existing non-call access. */ static gensum_param_access * get_access_1 (gensum_param_desc *desc, gensum_param_access **first, HOST_WIDE_INT offset, HOST_WIDE_INT size, isra_scan_context ctx) { gensum_param_access *access = *first, **ptr = first; if (!access) { /* No pre-existing access at this level, just create it. */ gensum_param_access *a = allocate_access (desc, offset, size); if (!a) return NULL; *first = a; return *first; } if (access->offset >= offset + size) { /* We want to squeeze it in front of the very first access, just do it. */ gensum_param_access *r = allocate_access (desc, offset, size); if (!r) return NULL; r->next_sibling = access; *first = r; return r; } /* Skip all accesses that have to come before us until the next sibling is already too far. */ while (offset >= access->offset + access->size && access->next_sibling && access->next_sibling->offset < offset + size) { ptr = &access->next_sibling; access = access->next_sibling; } /* At this point we know we do not belong before access. */ gcc_assert (access->offset < offset + size); if (access->offset == offset && access->size == size) /* We found what we were looking for. */ return access; if (access->offset <= offset && access->offset + access->size >= offset + size) { /* We fit into access which is larger than us. We need to find/create something below access. But we only allow nesting in call arguments. */ if (access->nonarg) return NULL; return get_access_1 (desc, &access->first_child, offset, size, ctx); } if (offset <= access->offset && offset + size >= access->offset + access->size) /* We are actually bigger than access, which fully fits into us, take its place and make all accesses fitting into it its children. */ { /* But first, we only allow nesting in call arguments so check if that is what we are trying to represent. */ if (ctx != ISRA_CTX_ARG) return NULL; gensum_param_access *r = allocate_access (desc, offset, size); if (!r) return NULL; r->first_child = access; while (access->next_sibling && access->next_sibling->offset < offset + size) access = access->next_sibling; if (access->offset + access->size > offset + size) { /* This must be a different access, which are sorted, so the following must be true and this signals a partial overlap. */ gcc_assert (access->offset > offset); return NULL; } r->next_sibling = access->next_sibling; access->next_sibling = NULL; *ptr = r; return r; } if (offset >= access->offset + access->size) { /* We belong after access. */ gensum_param_access *r = allocate_access (desc, offset, size); if (!r) return NULL; r->next_sibling = access->next_sibling; access->next_sibling = r; return r; } if (offset < access->offset) { /* We know the following, otherwise we would have created a super-access. */ gcc_checking_assert (offset + size < access->offset + access->size); return NULL; } if (offset + size > access->offset + access->size) { /* Likewise. */ gcc_checking_assert (offset > access->offset); return NULL; } gcc_unreachable (); } /* Return an access describing memory access to the variable described by DESC at OFFSET with SIZE in context CTX, mark it as used in context CTX. Attempt to create if it does not exist, but fail and return NULL if there are already too many accesses, if it would create a partially overlapping access or if an access would end up in a non-call access. */ static gensum_param_access * get_access (gensum_param_desc *desc, HOST_WIDE_INT offset, HOST_WIDE_INT size, isra_scan_context ctx) { gcc_checking_assert (desc->split_candidate); gensum_param_access *access = get_access_1 (desc, &desc->accesses, offset, size, ctx); if (!access) { disqualify_split_candidate (desc, "Bad access overlap or too many accesses"); return NULL; } switch (ctx) { case ISRA_CTX_STORE: gcc_assert (!desc->by_ref); /* Fall-through */ case ISRA_CTX_LOAD: access->nonarg = true; break; case ISRA_CTX_ARG: break; } return access; } /* Verify that parameter access tree starting with ACCESS is in good shape. PARENT_OFFSET and PARENT_SIZE are the corresponding fields of parent of ACCESS or zero if there is none. */ static bool verify_access_tree_1 (gensum_param_access *access, HOST_WIDE_INT parent_offset, HOST_WIDE_INT parent_size) { while (access) { gcc_assert (access->offset >= 0 && access->size > 0); if (parent_size != 0) { if (access->offset < parent_offset) { error ("Access offset before parent offset"); return true; } if (access->size >= parent_size) { error ("Access size greater or equal to its parent size"); return true; } if (access->offset + access->size > parent_offset + parent_size) { error ("Access terminates outside of its parent"); return true; } } if (verify_access_tree_1 (access->first_child, access->offset, access->size)) return true; if (access->next_sibling && (access->next_sibling->offset < access->offset + access->size)) { error ("Access overlaps with its sibling"); return true; } access = access->next_sibling; } return false; } /* Verify that parameter access tree starting with ACCESS is in good shape, halt compilation and dump the tree to stderr if not. */ DEBUG_FUNCTION void isra_verify_access_tree (gensum_param_access *access) { if (verify_access_tree_1 (access, 0, 0)) { for (; access; access = access->next_sibling) dump_gensum_access (stderr, access, 2); internal_error ("IPA-SRA access verification failed"); } } /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine GIMPLE_ASM operands with memory constrains which cannot be scalarized. */ static bool asm_visit_addr (gimple *, tree op, tree, void *) { op = get_base_address (op); if (op && TREE_CODE (op) == PARM_DECL) disqualify_split_candidate (op, "Non-scalarizable GIMPLE_ASM operand."); return false; } /* Mark a dereference of parameter identified by DESC of distance DIST in a basic block BB, unless the BB has already been marked as a potentially final. */ static void mark_param_dereference (gensum_param_desc *desc, HOST_WIDE_INT dist, basic_block bb) { gcc_assert (desc->by_ref); gcc_checking_assert (desc->split_candidate); if (bitmap_bit_p (final_bbs, bb->index)) return; int idx = bb->index * by_ref_count + desc->deref_index; if (bb_dereferences[idx] < dist) bb_dereferences[idx] = dist; } /* Return true, if any potential replacements should use NEW_TYPE as opposed to previously recorded OLD_TYPE. */ static bool type_prevails_p (tree old_type, tree new_type) { if (old_type == new_type) return false; /* Non-aggregates are always better. */ if (!is_gimple_reg_type (old_type) && is_gimple_reg_type (new_type)) return true; if (is_gimple_reg_type (old_type) && !is_gimple_reg_type (new_type)) return false; /* Prefer any complex or vector type over any other scalar type. */ if (TREE_CODE (old_type) != COMPLEX_TYPE && TREE_CODE (old_type) != VECTOR_TYPE && (TREE_CODE (new_type) == COMPLEX_TYPE || TREE_CODE (new_type) == VECTOR_TYPE)) return true; if ((TREE_CODE (old_type) == COMPLEX_TYPE || TREE_CODE (old_type) == VECTOR_TYPE) && TREE_CODE (new_type) != COMPLEX_TYPE && TREE_CODE (new_type) != VECTOR_TYPE) return false; /* Use the integral type with the bigger precision. */ if (INTEGRAL_TYPE_P (old_type) && INTEGRAL_TYPE_P (new_type)) return (TYPE_PRECISION (new_type) > TYPE_PRECISION (old_type)); /* Attempt to disregard any integral type with non-full precision. */ if (INTEGRAL_TYPE_P (old_type) && (TREE_INT_CST_LOW (TYPE_SIZE (old_type)) != TYPE_PRECISION (old_type))) return true; if (INTEGRAL_TYPE_P (new_type) && (TREE_INT_CST_LOW (TYPE_SIZE (new_type)) != TYPE_PRECISION (new_type))) return false; /* Stabilize the selection. */ return TYPE_UID (old_type) < TYPE_UID (new_type); } /* When scanning an expression which is a call argument, this structure specifies the call and the position of the argument. */ struct scan_call_info { /* Call graph edge representing the call. */ cgraph_edge *cs; /* Total number of arguments in the call. */ unsigned argument_count; /* Number of the actual argument being scanned. */ unsigned arg_idx; }; /* Record use of ACCESS which belongs to a parameter described by DESC in a call argument described by CALL_INFO. */ static void record_nonregister_call_use (gensum_param_desc *desc, scan_call_info *call_info, unsigned unit_offset, unsigned unit_size) { isra_call_summary *csum = call_sums->get_create (call_info->cs); csum->init_inputs (call_info->argument_count); isra_param_flow *param_flow = &csum->m_arg_flow[call_info->arg_idx]; param_flow->aggregate_pass_through = true; set_single_param_flow_source (param_flow, desc->param_number); param_flow->unit_offset = unit_offset; param_flow->unit_size = unit_size; desc->call_uses++; } /* Callback of walk_aliased_vdefs, just mark that there was a possible modification. */ static bool mark_maybe_modified (ao_ref *, tree, void *data) { bool *maybe_modified = (bool *) data; *maybe_modified = true; return true; } /* Analyze expression EXPR from GIMPLE for accesses to parameters. CTX specifies whether EXPR is used in a load, store or as an argument call. BB must be the basic block in which expr resides. If CTX specifies call argument context, CALL_INFO must describe that call and argument position, otherwise it is ignored. */ static void scan_expr_access (tree expr, gimple *stmt, isra_scan_context ctx, basic_block bb, scan_call_info *call_info = NULL) { poly_int64 poffset, psize, pmax_size; HOST_WIDE_INT offset, size, max_size; tree base; bool deref = false; bool reverse; if (TREE_CODE (expr) == BIT_FIELD_REF || TREE_CODE (expr) == IMAGPART_EXPR || TREE_CODE (expr) == REALPART_EXPR) expr = TREE_OPERAND (expr, 0); base = get_ref_base_and_extent (expr, &poffset, &psize, &pmax_size, &reverse); if (TREE_CODE (base) == MEM_REF) { tree op = TREE_OPERAND (base, 0); if (TREE_CODE (op) != SSA_NAME || !SSA_NAME_IS_DEFAULT_DEF (op)) return; base = SSA_NAME_VAR (op); if (!base) return; deref = true; } if (TREE_CODE (base) != PARM_DECL) return; gensum_param_desc *desc = get_gensum_param_desc (base); if (!desc || !desc->split_candidate) return; if (!poffset.is_constant (&offset) || !psize.is_constant (&size) || !pmax_size.is_constant (&max_size)) { disqualify_split_candidate (desc, "Encountered a polynomial-sized " "access."); return; } if (size < 0 || size != max_size) { disqualify_split_candidate (desc, "Encountered a variable sized access."); return; } if (TREE_CODE (expr) == COMPONENT_REF && DECL_BIT_FIELD (TREE_OPERAND (expr, 1))) { disqualify_split_candidate (desc, "Encountered a bit-field access."); return; } if (offset < 0) { disqualify_split_candidate (desc, "Encountered an access at a " "negative offset."); return; } gcc_assert ((offset % BITS_PER_UNIT) == 0); gcc_assert ((size % BITS_PER_UNIT) == 0); if ((offset / BITS_PER_UNIT) >= (UINT_MAX - ISRA_ARG_SIZE_LIMIT) || (size / BITS_PER_UNIT) >= ISRA_ARG_SIZE_LIMIT) { disqualify_split_candidate (desc, "Encountered an access with too big " "offset or size"); return; } tree type = TREE_TYPE (expr); unsigned int exp_align = get_object_alignment (expr); if (exp_align < TYPE_ALIGN (type)) { disqualify_split_candidate (desc, "Underaligned access."); return; } if (deref) { if (!desc->by_ref) { disqualify_split_candidate (desc, "Dereferencing a non-reference."); return; } else if (ctx == ISRA_CTX_STORE) { disqualify_split_candidate (desc, "Storing to data passed by " "reference."); return; } if (!aa_walking_limit) { disqualify_split_candidate (desc, "Out of alias analysis step " "limit."); return; } gcc_checking_assert (gimple_vuse (stmt)); bool maybe_modified = false; ao_ref ar; ao_ref_init (&ar, expr); bitmap visited = BITMAP_ALLOC (NULL); int walked = walk_aliased_vdefs (&ar, gimple_vuse (stmt), mark_maybe_modified, &maybe_modified, &visited, NULL, aa_walking_limit); BITMAP_FREE (visited); if (walked > 0) { gcc_assert (aa_walking_limit > walked); aa_walking_limit = aa_walking_limit - walked; } if (walked < 0) aa_walking_limit = 0; if (maybe_modified || walked < 0) { disqualify_split_candidate (desc, "Data passed by reference possibly " "modified through an alias."); return; } else mark_param_dereference (desc, offset + size, bb); } else /* Pointer parameters with direct uses should have been ruled out by analyzing SSA default def when looking at the parameters. */ gcc_assert (!desc->by_ref); gensum_param_access *access = get_access (desc, offset, size, ctx); if (!access) return; if (ctx == ISRA_CTX_ARG) { gcc_checking_assert (call_info); if (!deref) record_nonregister_call_use (desc, call_info, offset / BITS_PER_UNIT, size / BITS_PER_UNIT); else /* This is not a pass-through of a pointer, this is a use like any other. */ access->nonarg = true; } if (!access->type) { access->type = type; access->alias_ptr_type = reference_alias_ptr_type (expr); access->reverse = reverse; } else { if (exp_align < TYPE_ALIGN (access->type)) { disqualify_split_candidate (desc, "Reference has lower alignment " "than a previous one."); return; } if (access->alias_ptr_type != reference_alias_ptr_type (expr)) { disqualify_split_candidate (desc, "Multiple alias pointer types."); return; } if (access->reverse != reverse) { disqualify_split_candidate (desc, "Both normal and reverse " "scalar storage order."); return; } if (!deref && (AGGREGATE_TYPE_P (type) || AGGREGATE_TYPE_P (access->type)) && (TYPE_MAIN_VARIANT (access->type) != TYPE_MAIN_VARIANT (type))) { /* We need the same aggregate type on all accesses to be able to distinguish transformation spots from pass-through arguments in the transformation phase. */ disqualify_split_candidate (desc, "We do not support aggregate " "type punning."); return; } if (type_prevails_p (access->type, type)) access->type = type; } } /* Scan body function described by NODE and FUN and create access trees for parameters. */ static void scan_function (cgraph_node *node, struct function *fun) { basic_block bb; FOR_EACH_BB_FN (bb, fun) { gimple_stmt_iterator gsi; for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { gimple *stmt = gsi_stmt (gsi); if (stmt_can_throw_external (fun, stmt)) bitmap_set_bit (final_bbs, bb->index); switch (gimple_code (stmt)) { case GIMPLE_RETURN: { tree t = gimple_return_retval (as_a (stmt)); if (t != NULL_TREE) scan_expr_access (t, stmt, ISRA_CTX_LOAD, bb); bitmap_set_bit (final_bbs, bb->index); } break; case GIMPLE_ASSIGN: if (gimple_assign_single_p (stmt) && !gimple_clobber_p (stmt)) { tree rhs = gimple_assign_rhs1 (stmt); scan_expr_access (rhs, stmt, ISRA_CTX_LOAD, bb); tree lhs = gimple_assign_lhs (stmt); scan_expr_access (lhs, stmt, ISRA_CTX_STORE, bb); } break; case GIMPLE_CALL: { unsigned argument_count = gimple_call_num_args (stmt); isra_scan_context ctx = ISRA_CTX_ARG; scan_call_info call_info, *call_info_p = &call_info; if (gimple_call_internal_p (stmt)) { call_info_p = NULL; ctx = ISRA_CTX_LOAD; internal_fn ifn = gimple_call_internal_fn (stmt); if (internal_store_fn_p (ifn)) ctx = ISRA_CTX_STORE; } else { call_info.cs = node->get_edge (stmt); call_info.argument_count = argument_count; } for (unsigned i = 0; i < argument_count; i++) { call_info.arg_idx = i; scan_expr_access (gimple_call_arg (stmt, i), stmt, ctx, bb, call_info_p); } tree lhs = gimple_call_lhs (stmt); if (lhs) scan_expr_access (lhs, stmt, ISRA_CTX_STORE, bb); int flags = gimple_call_flags (stmt); if ((flags & (ECF_CONST | ECF_PURE)) == 0) bitmap_set_bit (final_bbs, bb->index); } break; case GIMPLE_ASM: { gasm *asm_stmt = as_a (stmt); walk_stmt_load_store_addr_ops (asm_stmt, NULL, NULL, NULL, asm_visit_addr); bitmap_set_bit (final_bbs, bb->index); for (unsigned i = 0; i < gimple_asm_ninputs (asm_stmt); i++) { tree t = TREE_VALUE (gimple_asm_input_op (asm_stmt, i)); scan_expr_access (t, stmt, ISRA_CTX_LOAD, bb); } for (unsigned i = 0; i < gimple_asm_noutputs (asm_stmt); i++) { tree t = TREE_VALUE (gimple_asm_output_op (asm_stmt, i)); scan_expr_access (t, stmt, ISRA_CTX_STORE, bb); } } break; default: break; } } } } /* Return true if SSA_NAME NAME is only used in return statements, or if results of any operations it is involved in are only used in return statements. ANALYZED is a bitmap that tracks which SSA names we have already started investigating. */ static bool ssa_name_only_returned_p (tree name, bitmap analyzed) { bool res = true; imm_use_iterator imm_iter; gimple *stmt; FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name) { if (is_gimple_debug (stmt)) continue; if (gimple_code (stmt) == GIMPLE_RETURN) { tree t = gimple_return_retval (as_a (stmt)); if (t != name) { res = false; BREAK_FROM_IMM_USE_STMT (imm_iter); } } else if ((is_gimple_assign (stmt) && !gimple_has_volatile_ops (stmt)) || gimple_code (stmt) == GIMPLE_PHI) { /* TODO: And perhaps for const function calls too? */ tree lhs; if (gimple_code (stmt) == GIMPLE_PHI) lhs = gimple_phi_result (stmt); else lhs = gimple_assign_lhs (stmt); if (TREE_CODE (lhs) != SSA_NAME) { res = false; BREAK_FROM_IMM_USE_STMT (imm_iter); } gcc_assert (!gimple_vdef (stmt)); if (bitmap_set_bit (analyzed, SSA_NAME_VERSION (lhs)) && !ssa_name_only_returned_p (lhs, analyzed)) { res = false; BREAK_FROM_IMM_USE_STMT (imm_iter); } } else { res = false; BREAK_FROM_IMM_USE_STMT (imm_iter); } } return res; } /* Inspect the uses of the return value of the call associated with CS, and if it is not used or if it is only used to construct the return value of the caller, mark it as such in call or caller summary. Also check for misaligned arguments. */ static void isra_analyze_call (cgraph_edge *cs) { gcall *call_stmt = cs->call_stmt; unsigned count = gimple_call_num_args (call_stmt); isra_call_summary *csum = call_sums->get_create (cs); for (unsigned i = 0; i < count; i++) { tree arg = gimple_call_arg (call_stmt, i); if (is_gimple_reg (arg)) continue; tree offset; poly_int64 bitsize, bitpos; machine_mode mode; int unsignedp, reversep, volatilep = 0; get_inner_reference (arg, &bitsize, &bitpos, &offset, &mode, &unsignedp, &reversep, &volatilep); if (!multiple_p (bitpos, BITS_PER_UNIT)) { csum->m_bit_aligned_arg = true; break; } } tree lhs = gimple_call_lhs (call_stmt); if (lhs) { /* TODO: Also detect aggregates on a LHS of a call that are only returned from this function (without being read anywhere). */ if (TREE_CODE (lhs) == SSA_NAME) { bitmap analyzed = BITMAP_ALLOC (NULL); if (ssa_name_only_returned_p (lhs, analyzed)) csum->m_return_returned = true; BITMAP_FREE (analyzed); } } else csum->m_return_ignored = true; } /* Look at all calls going out of NODE, described also by IFS and perform all analyses necessary for IPA-SRA that are not done at body scan time or done even when body is not scanned because the function is not a candidate. */ static void isra_analyze_all_outgoing_calls (cgraph_node *node) { for (cgraph_edge *cs = node->callees; cs; cs = cs->next_callee) isra_analyze_call (cs); for (cgraph_edge *cs = node->indirect_calls; cs; cs = cs->next_callee) isra_analyze_call (cs); } /* Dump a dereferences table with heading STR to file F. */ static void dump_dereferences_table (FILE *f, struct function *fun, const char *str) { basic_block bb; fprintf (dump_file, "%s", str); FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (fun), EXIT_BLOCK_PTR_FOR_FN (fun), next_bb) { fprintf (f, "%4i %i ", bb->index, bitmap_bit_p (final_bbs, bb->index)); if (bb != EXIT_BLOCK_PTR_FOR_FN (fun)) { int i; for (i = 0; i < by_ref_count; i++) { int idx = bb->index * by_ref_count + i; fprintf (f, " %4" HOST_WIDE_INT_PRINT "d", bb_dereferences[idx]); } } fprintf (f, "\n"); } fprintf (dump_file, "\n"); } /* Propagate distances in bb_dereferences in the opposite direction than the control flow edges, in each step storing the maximum of the current value and the minimum of all successors. These steps are repeated until the table stabilizes. Note that BBs which might terminate the functions (according to final_bbs bitmap) never updated in this way. */ static void propagate_dereference_distances (struct function *fun) { basic_block bb; if (dump_file && (dump_flags & TDF_DETAILS)) dump_dereferences_table (dump_file, fun, "Dereference table before propagation:\n"); auto_vec queue (last_basic_block_for_fn (fun)); queue.quick_push (ENTRY_BLOCK_PTR_FOR_FN (fun)); FOR_EACH_BB_FN (bb, fun) { queue.quick_push (bb); bb->aux = bb; } while (!queue.is_empty ()) { edge_iterator ei; edge e; bool change = false; int i; bb = queue.pop (); bb->aux = NULL; if (bitmap_bit_p (final_bbs, bb->index)) continue; for (i = 0; i < by_ref_count; i++) { int idx = bb->index * by_ref_count + i; bool first = true; HOST_WIDE_INT inh = 0; FOR_EACH_EDGE (e, ei, bb->succs) { int succ_idx = e->dest->index * by_ref_count + i; if (e->dest == EXIT_BLOCK_PTR_FOR_FN (fun)) continue; if (first) { first = false; inh = bb_dereferences [succ_idx]; } else if (bb_dereferences [succ_idx] < inh) inh = bb_dereferences [succ_idx]; } if (!first && bb_dereferences[idx] < inh) { bb_dereferences[idx] = inh; change = true; } } if (change) FOR_EACH_EDGE (e, ei, bb->preds) { if (e->src->aux) continue; e->src->aux = e->src; queue.quick_push (e->src); } } if (dump_file && (dump_flags & TDF_DETAILS)) dump_dereferences_table (dump_file, fun, "Dereference table after propagation:\n"); } /* Perform basic checks on ACCESS to PARM described by DESC and all its children, return true if the parameter cannot be split, otherwise return true and update *TOTAL_SIZE and *ONLY_CALLS. ENTRY_BB_INDEX must be the index of the entry BB in the function of PARM. */ static bool check_gensum_access (tree parm, gensum_param_desc *desc, gensum_param_access *access, HOST_WIDE_INT *nonarg_acc_size, bool *only_calls, int entry_bb_index) { if (access->nonarg) { *only_calls = false; *nonarg_acc_size += access->size; if (access->first_child) { disqualify_split_candidate (desc, "Overlapping non-call uses."); return true; } } /* Do not decompose a non-BLKmode param in a way that would create BLKmode params. Especially for by-reference passing (thus, pointer-type param) this is hardly worthwhile. */ if (DECL_MODE (parm) != BLKmode && TYPE_MODE (access->type) == BLKmode) { disqualify_split_candidate (desc, "Would convert a non-BLK to a BLK."); return true; } if (desc->by_ref) { int idx = (entry_bb_index * by_ref_count + desc->deref_index); if ((access->offset + access->size) > bb_dereferences[idx]) { disqualify_split_candidate (desc, "Would create a possibly " "illegal dereference in a caller."); return true; } } for (gensum_param_access *ch = access->first_child; ch; ch = ch->next_sibling) if (check_gensum_access (parm, desc, ch, nonarg_acc_size, only_calls, entry_bb_index)) return true; return false; } /* Copy data from FROM and all of its children to a vector of accesses in IPA descriptor DESC. */ static void copy_accesses_to_ipa_desc (gensum_param_access *from, isra_param_desc *desc) { param_access *to = ggc_cleared_alloc (); gcc_checking_assert ((from->offset % BITS_PER_UNIT) == 0); gcc_checking_assert ((from->size % BITS_PER_UNIT) == 0); to->unit_offset = from->offset / BITS_PER_UNIT; to->unit_size = from->size / BITS_PER_UNIT; to->type = from->type; to->alias_ptr_type = from->alias_ptr_type; to->certain = from->nonarg; to->reverse = from->reverse; vec_safe_push (desc->accesses, to); for (gensum_param_access *ch = from->first_child; ch; ch = ch->next_sibling) copy_accesses_to_ipa_desc (ch, desc); } /* Analyze function body scan results stored in param_accesses and param_accesses, detect possible transformations and store information of those in function summary. NODE, FUN and IFS are all various structures describing the currently analyzed function. */ static void process_scan_results (cgraph_node *node, struct function *fun, isra_func_summary *ifs, vec *param_descriptions) { bool check_pass_throughs = false; bool dereferences_propagated = false; tree parm = DECL_ARGUMENTS (node->decl); unsigned param_count = param_descriptions->length(); for (unsigned desc_index = 0; desc_index < param_count; desc_index++, parm = DECL_CHAIN (parm)) { gensum_param_desc *desc = &(*param_descriptions)[desc_index]; if (!desc->split_candidate) continue; if (flag_checking) isra_verify_access_tree (desc->accesses); if (!dereferences_propagated && desc->by_ref && desc->accesses) { propagate_dereference_distances (fun); dereferences_propagated = true; } HOST_WIDE_INT nonarg_acc_size = 0; bool only_calls = true; bool check_failed = false; int entry_bb_index = ENTRY_BLOCK_PTR_FOR_FN (fun)->index; for (gensum_param_access *acc = desc->accesses; acc; acc = acc->next_sibling) if (check_gensum_access (parm, desc, acc, &nonarg_acc_size, &only_calls, entry_bb_index)) { check_failed = true; break; } if (check_failed) continue; if (only_calls) desc->locally_unused = true; HOST_WIDE_INT cur_param_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (parm))); HOST_WIDE_INT param_size_limit; if (!desc->by_ref || optimize_function_for_size_p (fun)) param_size_limit = cur_param_size; else param_size_limit = opt_for_fn (node->decl, param_ipa_sra_ptr_growth_factor) * cur_param_size; if (nonarg_acc_size > param_size_limit || (!desc->by_ref && nonarg_acc_size == param_size_limit)) { disqualify_split_candidate (desc, "Would result into a too big set " "of replacements."); } else { /* create_parameter_descriptors makes sure unit sizes of all candidate parameters fit unsigned integers restricted to ISRA_ARG_SIZE_LIMIT. */ desc->param_size_limit = param_size_limit / BITS_PER_UNIT; desc->nonarg_acc_size = nonarg_acc_size / BITS_PER_UNIT; if (desc->split_candidate && desc->ptr_pt_count) { gcc_assert (desc->by_ref); check_pass_throughs = true; } } } /* When a pointer parameter is passed-through to a callee, in which it is only used to read only one or a few items, we can attempt to transform it to obtaining and passing through the items instead of the pointer. But we must take extra care that 1) we do not introduce any segfault by moving dereferences above control flow and that 2) the data is not modified through an alias in this function. The IPA analysis must not introduce any accesses candidates unless it can prove both. The current solution is very crude as it consists of ensuring that the call postdominates entry BB and that the definition of VUSE of the call is default definition. TODO: For non-recursive callees in the same compilation unit we could do better by doing analysis in topological order an looking into access candidates of callees, using their alias_ptr_types to attempt real AA. We could also use the maximum known dereferenced offset in this function at IPA level. TODO: Measure the overhead and the effect of just being pessimistic. Maybe this is only -O3 material? */ bool pdoms_calculated = false; if (check_pass_throughs) for (cgraph_edge *cs = node->callees; cs; cs = cs->next_callee) { gcall *call_stmt = cs->call_stmt; tree vuse = gimple_vuse (call_stmt); /* If the callee is a const function, we don't get a VUSE. In such case there will be no memory accesses in the called function (or the const attribute is wrong) and then we just don't care. */ bool uses_memory_as_obtained = vuse && SSA_NAME_IS_DEFAULT_DEF (vuse); unsigned count = gimple_call_num_args (call_stmt); isra_call_summary *csum = call_sums->get_create (cs); csum->init_inputs (count); for (unsigned argidx = 0; argidx < count; argidx++) { if (!csum->m_arg_flow[argidx].pointer_pass_through) continue; unsigned pidx = get_single_param_flow_source (&csum->m_arg_flow[argidx]); gensum_param_desc *desc = &(*param_descriptions)[pidx]; if (!desc->split_candidate) { csum->m_arg_flow[argidx].pointer_pass_through = false; continue; } if (!uses_memory_as_obtained) continue; /* Post-dominator check placed last, hoping that it usually won't be needed. */ if (!pdoms_calculated) { gcc_checking_assert (cfun); add_noreturn_fake_exit_edges (); connect_infinite_loops_to_exit (); calculate_dominance_info (CDI_POST_DOMINATORS); pdoms_calculated = true; } if (dominated_by_p (CDI_POST_DOMINATORS, gimple_bb (call_stmt), single_succ (ENTRY_BLOCK_PTR_FOR_FN (fun)))) csum->m_arg_flow[argidx].safe_to_import_accesses = true; } } if (pdoms_calculated) { free_dominance_info (CDI_POST_DOMINATORS); remove_fake_exit_edges (); } /* TODO: Add early exit if we disqualified everything. This also requires that we either relax the restriction that ipa_param_adjustments.m_always_copy_start must be the number of PARM_DECLs or store the number of parameters to IPA-SRA function summary and use that when just removing params. */ vec_safe_reserve_exact (ifs->m_parameters, param_count); ifs->m_parameters->quick_grow_cleared (param_count); for (unsigned desc_index = 0; desc_index < param_count; desc_index++) { gensum_param_desc *s = &(*param_descriptions)[desc_index]; isra_param_desc *d = &(*ifs->m_parameters)[desc_index]; d->param_size_limit = s->param_size_limit; d->size_reached = s->nonarg_acc_size; d->locally_unused = s->locally_unused; d->split_candidate = s->split_candidate; d->by_ref = s->by_ref; for (gensum_param_access *acc = s->accesses; acc; acc = acc->next_sibling) copy_accesses_to_ipa_desc (acc, d); } if (dump_file) dump_isra_param_descriptors (dump_file, node->decl, ifs); } /* Return true if there are any overlaps among certain accesses of DESC. If non-NULL, set *CERTAIN_ACCESS_PRESENT_P upon encountering a certain access too. DESC is assumed to be a split candidate that is not locally unused. */ static bool overlapping_certain_accesses_p (isra_param_desc *desc, bool *certain_access_present_p) { unsigned pclen = vec_safe_length (desc->accesses); for (unsigned i = 0; i < pclen; i++) { param_access *a1 = (*desc->accesses)[i]; if (!a1->certain) continue; if (certain_access_present_p) *certain_access_present_p = true; for (unsigned j = i + 1; j < pclen; j++) { param_access *a2 = (*desc->accesses)[j]; if (a2->certain && a1->unit_offset < a2->unit_offset + a2->unit_size && a1->unit_offset + a1->unit_size > a2->unit_offset) return true; } } return false; } /* Check for any overlaps of certain param accesses among splitting candidates and signal an ICE if there are any. If CERTAIN_MUST_EXIST is set, also check that used splitting candidates have at least one certain access. */ static void verify_splitting_accesses (cgraph_node *node, bool certain_must_exist) { isra_func_summary *ifs = func_sums->get (node); if (!ifs || !ifs->m_candidate) return; unsigned param_count = vec_safe_length (ifs->m_parameters); for (unsigned pidx = 0; pidx < param_count; pidx++) { isra_param_desc *desc = &(*ifs->m_parameters)[pidx]; if (!desc->split_candidate || desc->locally_unused) continue; bool certain_access_present = !certain_must_exist; if (overlapping_certain_accesses_p (desc, &certain_access_present)) internal_error ("Function %qs, parameter %u, has IPA-SRA accesses " "which overlap", node->dump_name (), pidx); if (!certain_access_present) internal_error ("Function %s, parameter %u, is used but does not " "have any certain IPA-SRA access", node->dump_name (), pidx); } } /* Intraprocedural part of IPA-SRA analysis. Scan function body of NODE and create a summary structure describing IPA-SRA opportunities and constraints in it. */ static void ipa_sra_summarize_function (cgraph_node *node) { if (dump_file) fprintf (dump_file, "Creating summary for %s/%i:\n", node->name (), node->order); if (!ipa_sra_preliminary_function_checks (node)) return; gcc_obstack_init (&gensum_obstack); isra_func_summary *ifs = func_sums->get_create (node); ifs->m_candidate = true; tree ret = TREE_TYPE (TREE_TYPE (node->decl)); ifs->m_returns_value = (TREE_CODE (ret) != VOID_TYPE); decl2desc = new hash_map; unsigned count = 0; for (tree parm = DECL_ARGUMENTS (node->decl); parm; parm = DECL_CHAIN (parm)) count++; if (count > 0) { auto_vec param_descriptions (count); param_descriptions.reserve_exact (count); param_descriptions.quick_grow_cleared (count); bool cfun_pushed = false; struct function *fun = DECL_STRUCT_FUNCTION (node->decl); if (create_parameter_descriptors (node, ¶m_descriptions)) { push_cfun (fun); cfun_pushed = true; final_bbs = BITMAP_ALLOC (NULL); bb_dereferences = XCNEWVEC (HOST_WIDE_INT, by_ref_count * last_basic_block_for_fn (fun)); aa_walking_limit = opt_for_fn (node->decl, param_ipa_max_aa_steps); scan_function (node, fun); if (dump_file) { dump_gensum_param_descriptors (dump_file, node->decl, ¶m_descriptions); fprintf (dump_file, "----------------------------------------\n"); } } process_scan_results (node, fun, ifs, ¶m_descriptions); if (cfun_pushed) pop_cfun (); if (bb_dereferences) { free (bb_dereferences); bb_dereferences = NULL; BITMAP_FREE (final_bbs); final_bbs = NULL; } } isra_analyze_all_outgoing_calls (node); delete decl2desc; decl2desc = NULL; obstack_free (&gensum_obstack, NULL); if (dump_file) fprintf (dump_file, "\n\n"); if (flag_checking) verify_splitting_accesses (node, false); return; } /* Intraprocedural part of IPA-SRA analysis. Scan bodies of all functions in this compilation unit and create summary structures describing IPA-SRA opportunities and constraints in them. */ static void ipa_sra_generate_summary (void) { struct cgraph_node *node; gcc_checking_assert (!func_sums); gcc_checking_assert (!call_sums); func_sums = (new (ggc_alloc_no_dtor ()) ipa_sra_function_summaries (symtab, true)); call_sums = new ipa_sra_call_summaries (symtab); FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) ipa_sra_summarize_function (node); return; } /* Write intraprocedural analysis information about E and all of its outgoing edges into a stream for LTO WPA. */ static void isra_write_edge_summary (output_block *ob, cgraph_edge *e) { isra_call_summary *csum = call_sums->get (e); unsigned input_count = csum->m_arg_flow.length (); streamer_write_uhwi (ob, input_count); for (unsigned i = 0; i < input_count; i++) { isra_param_flow *ipf = &csum->m_arg_flow[i]; streamer_write_hwi (ob, ipf->length); bitpack_d bp = bitpack_create (ob->main_stream); for (int j = 0; j < ipf->length; j++) bp_pack_value (&bp, ipf->inputs[j], 8); bp_pack_value (&bp, ipf->aggregate_pass_through, 1); bp_pack_value (&bp, ipf->pointer_pass_through, 1); bp_pack_value (&bp, ipf->safe_to_import_accesses, 1); streamer_write_bitpack (&bp); streamer_write_uhwi (ob, ipf->unit_offset); streamer_write_uhwi (ob, ipf->unit_size); } bitpack_d bp = bitpack_create (ob->main_stream); bp_pack_value (&bp, csum->m_return_ignored, 1); bp_pack_value (&bp, csum->m_return_returned, 1); bp_pack_value (&bp, csum->m_bit_aligned_arg, 1); streamer_write_bitpack (&bp); } /* Write intraprocedural analysis information about NODE and all of its outgoing edges into a stream for LTO WPA. */ static void isra_write_node_summary (output_block *ob, cgraph_node *node) { isra_func_summary *ifs = func_sums->get (node); lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder; int node_ref = lto_symtab_encoder_encode (encoder, node); streamer_write_uhwi (ob, node_ref); unsigned param_desc_count = vec_safe_length (ifs->m_parameters); streamer_write_uhwi (ob, param_desc_count); for (unsigned i = 0; i < param_desc_count; i++) { isra_param_desc *desc = &(*ifs->m_parameters)[i]; unsigned access_count = vec_safe_length (desc->accesses); streamer_write_uhwi (ob, access_count); for (unsigned j = 0; j < access_count; j++) { param_access *acc = (*desc->accesses)[j]; stream_write_tree (ob, acc->type, true); stream_write_tree (ob, acc->alias_ptr_type, true); streamer_write_uhwi (ob, acc->unit_offset); streamer_write_uhwi (ob, acc->unit_size); bitpack_d bp = bitpack_create (ob->main_stream); bp_pack_value (&bp, acc->certain, 1); streamer_write_bitpack (&bp); } streamer_write_uhwi (ob, desc->param_size_limit); streamer_write_uhwi (ob, desc->size_reached); bitpack_d bp = bitpack_create (ob->main_stream); bp_pack_value (&bp, desc->locally_unused, 1); bp_pack_value (&bp, desc->split_candidate, 1); bp_pack_value (&bp, desc->by_ref, 1); streamer_write_bitpack (&bp); } bitpack_d bp = bitpack_create (ob->main_stream); bp_pack_value (&bp, ifs->m_candidate, 1); bp_pack_value (&bp, ifs->m_returns_value, 1); bp_pack_value (&bp, ifs->m_return_ignored, 1); gcc_assert (!ifs->m_queued); streamer_write_bitpack (&bp); for (cgraph_edge *e = node->callees; e; e = e->next_callee) isra_write_edge_summary (ob, e); for (cgraph_edge *e = node->indirect_calls; e; e = e->next_callee) isra_write_edge_summary (ob, e); } /* Write intraprocedural analysis information into a stream for LTO WPA. */ static void ipa_sra_write_summary (void) { if (!func_sums || !call_sums) return; struct output_block *ob = create_output_block (LTO_section_ipa_sra); lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder; ob->symbol = NULL; unsigned int count = 0; lto_symtab_encoder_iterator lsei; for (lsei = lsei_start_function_in_partition (encoder); !lsei_end_p (lsei); lsei_next_function_in_partition (&lsei)) { cgraph_node *node = lsei_cgraph_node (lsei); if (node->has_gimple_body_p () && func_sums->get (node) != NULL) count++; } streamer_write_uhwi (ob, count); /* Process all of the functions. */ for (lsei = lsei_start_function_in_partition (encoder); !lsei_end_p (lsei); lsei_next_function_in_partition (&lsei)) { cgraph_node *node = lsei_cgraph_node (lsei); if (node->has_gimple_body_p () && func_sums->get (node) != NULL) isra_write_node_summary (ob, node); } streamer_write_char_stream (ob->main_stream, 0); produce_asm (ob, NULL); destroy_output_block (ob); } /* Read intraprocedural analysis information about E and all of its outgoing edges into a stream for LTO WPA. */ static void isra_read_edge_summary (struct lto_input_block *ib, cgraph_edge *cs) { isra_call_summary *csum = call_sums->get_create (cs); unsigned input_count = streamer_read_uhwi (ib); csum->init_inputs (input_count); for (unsigned i = 0; i < input_count; i++) { isra_param_flow *ipf = &csum->m_arg_flow[i]; ipf->length = streamer_read_hwi (ib); bitpack_d bp = streamer_read_bitpack (ib); for (int j = 0; j < ipf->length; j++) ipf->inputs[j] = bp_unpack_value (&bp, 8); ipf->aggregate_pass_through = bp_unpack_value (&bp, 1); ipf->pointer_pass_through = bp_unpack_value (&bp, 1); ipf->safe_to_import_accesses = bp_unpack_value (&bp, 1); ipf->unit_offset = streamer_read_uhwi (ib); ipf->unit_size = streamer_read_uhwi (ib); } bitpack_d bp = streamer_read_bitpack (ib); csum->m_return_ignored = bp_unpack_value (&bp, 1); csum->m_return_returned = bp_unpack_value (&bp, 1); csum->m_bit_aligned_arg = bp_unpack_value (&bp, 1); } /* Read intraprocedural analysis information about NODE and all of its outgoing edges into a stream for LTO WPA. */ static void isra_read_node_info (struct lto_input_block *ib, cgraph_node *node, struct data_in *data_in) { isra_func_summary *ifs = func_sums->get_create (node); unsigned param_desc_count = streamer_read_uhwi (ib); if (param_desc_count > 0) { vec_safe_reserve_exact (ifs->m_parameters, param_desc_count); ifs->m_parameters->quick_grow_cleared (param_desc_count); } for (unsigned i = 0; i < param_desc_count; i++) { isra_param_desc *desc = &(*ifs->m_parameters)[i]; unsigned access_count = streamer_read_uhwi (ib); for (unsigned j = 0; j < access_count; j++) { param_access *acc = ggc_cleared_alloc (); acc->type = stream_read_tree (ib, data_in); acc->alias_ptr_type = stream_read_tree (ib, data_in); acc->unit_offset = streamer_read_uhwi (ib); acc->unit_size = streamer_read_uhwi (ib); bitpack_d bp = streamer_read_bitpack (ib); acc->certain = bp_unpack_value (&bp, 1); vec_safe_push (desc->accesses, acc); } desc->param_size_limit = streamer_read_uhwi (ib); desc->size_reached = streamer_read_uhwi (ib); bitpack_d bp = streamer_read_bitpack (ib); desc->locally_unused = bp_unpack_value (&bp, 1); desc->split_candidate = bp_unpack_value (&bp, 1); desc->by_ref = bp_unpack_value (&bp, 1); } bitpack_d bp = streamer_read_bitpack (ib); ifs->m_candidate = bp_unpack_value (&bp, 1); ifs->m_returns_value = bp_unpack_value (&bp, 1); ifs->m_return_ignored = bp_unpack_value (&bp, 1); ifs->m_queued = 0; for (cgraph_edge *e = node->callees; e; e = e->next_callee) isra_read_edge_summary (ib, e); for (cgraph_edge *e = node->indirect_calls; e; e = e->next_callee) isra_read_edge_summary (ib, e); } /* Read IPA-SRA summaries from a section in file FILE_DATA of length LEN with data DATA. TODO: This function was copied almost verbatim from ipa-prop.c, it should be possible to unify them somehow. */ static void isra_read_summary_section (struct lto_file_decl_data *file_data, const char *data, size_t len) { const struct lto_function_header *header = (const struct lto_function_header *) data; const int cfg_offset = sizeof (struct lto_function_header); const int main_offset = cfg_offset + header->cfg_size; const int string_offset = main_offset + header->main_size; struct data_in *data_in; unsigned int i; unsigned int count; lto_input_block ib_main ((const char *) data + main_offset, header->main_size, file_data->mode_table); data_in = lto_data_in_create (file_data, (const char *) data + string_offset, header->string_size, vNULL); count = streamer_read_uhwi (&ib_main); for (i = 0; i < count; i++) { unsigned int index; struct cgraph_node *node; lto_symtab_encoder_t encoder; index = streamer_read_uhwi (&ib_main); encoder = file_data->symtab_node_encoder; node = dyn_cast (lto_symtab_encoder_deref (encoder, index)); gcc_assert (node->definition); isra_read_node_info (&ib_main, node, data_in); } lto_free_section_data (file_data, LTO_section_ipa_sra, NULL, data, len); lto_data_in_delete (data_in); } /* Read intraprocedural analysis information into a stream for LTO WPA. */ static void ipa_sra_read_summary (void) { struct lto_file_decl_data **file_data_vec = lto_get_file_decl_data (); struct lto_file_decl_data *file_data; unsigned int j = 0; gcc_checking_assert (!func_sums); gcc_checking_assert (!call_sums); func_sums = (new (ggc_alloc_no_dtor ()) ipa_sra_function_summaries (symtab, true)); call_sums = new ipa_sra_call_summaries (symtab); while ((file_data = file_data_vec[j++])) { size_t len; const char *data = lto_get_summary_section_data (file_data, LTO_section_ipa_sra, &len); if (data) isra_read_summary_section (file_data, data, len); } } /* Dump all IPA-SRA summary data for all cgraph nodes and edges to file F. */ static void ipa_sra_dump_all_summaries (FILE *f) { cgraph_node *node; FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) { fprintf (f, "\nSummary for node %s:\n", node->dump_name ()); isra_func_summary *ifs = func_sums->get (node); if (!ifs) { fprintf (f, " Function does not have any associated IPA-SRA " "summary\n"); continue; } if (!ifs->m_candidate) { fprintf (f, " Not a candidate function\n"); continue; } if (ifs->m_returns_value) fprintf (f, " Returns value\n"); if (vec_safe_is_empty (ifs->m_parameters)) fprintf (f, " No parameter information. \n"); else for (unsigned i = 0; i < ifs->m_parameters->length (); ++i) { fprintf (f, " Descriptor for parameter %i:\n", i); dump_isra_param_descriptor (f, &(*ifs->m_parameters)[i]); } fprintf (f, "\n"); struct cgraph_edge *cs; for (cs = node->callees; cs; cs = cs->next_callee) { fprintf (f, " Summary for edge %s->%s:\n", cs->caller->dump_name (), cs->callee->dump_name ()); isra_call_summary *csum = call_sums->get (cs); if (csum) csum->dump (f); else fprintf (f, " Call summary is MISSING!\n"); } } fprintf (f, "\n\n"); } /* Perform function-scope viability tests that can be only made at IPA level and return false if the function is deemed unsuitable for IPA-SRA. */ static bool ipa_sra_ipa_function_checks (cgraph_node *node) { if (!node->can_be_local_p ()) { if (dump_file) fprintf (dump_file, "Function %s disqualified because it cannot be " "made local.\n", node->dump_name ()); return false; } if (!node->can_change_signature) { if (dump_file) fprintf (dump_file, "Function can not change signature.\n"); return false; } return true; } /* Issues found out by check_callers_for_issues. */ struct caller_issues { /* The candidate being considered. */ cgraph_node *candidate; /* There is a thunk among callers. */ bool thunk; /* Call site with no available information. */ bool unknown_callsite; /* Call from outside the the candidate's comdat group. */ bool call_from_outside_comdat; /* There is a bit-aligned load into one of non-gimple-typed arguments. */ bool bit_aligned_aggregate_argument; }; /* Worker for call_for_symbol_and_aliases, set any flags of passed caller_issues that apply. */ static bool check_for_caller_issues (struct cgraph_node *node, void *data) { struct caller_issues *issues = (struct caller_issues *) data; for (cgraph_edge *cs = node->callers; cs; cs = cs->next_caller) { if (cs->caller->thunk.thunk_p) { issues->thunk = true; /* TODO: We should be able to process at least some types of thunks. */ return true; } if (issues->candidate->calls_comdat_local && issues->candidate->same_comdat_group && !issues->candidate->in_same_comdat_group_p (cs->caller)) { issues->call_from_outside_comdat = true; return true; } isra_call_summary *csum = call_sums->get (cs); if (!csum) { issues->unknown_callsite = true; return true; } if (csum->m_bit_aligned_arg) issues->bit_aligned_aggregate_argument = true; } return false; } /* Look at all incoming edges to NODE, including aliases and thunks and look for problems. Return true if NODE type should not be modified at all. */ static bool check_all_callers_for_issues (cgraph_node *node) { struct caller_issues issues; memset (&issues, 0, sizeof (issues)); issues.candidate = node; node->call_for_symbol_and_aliases (check_for_caller_issues, &issues, true); if (issues.unknown_callsite) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "A call of %s has not been analyzed. Disabling " "all modifications.\n", node->dump_name ()); return true; } /* TODO: We should be able to process at least some types of thunks. */ if (issues.thunk) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "A call of %s is through thunk, which are not" " handled yet. Disabling all modifications.\n", node->dump_name ()); return true; } if (issues.call_from_outside_comdat) { if (dump_file) fprintf (dump_file, "Function would become private comdat called " "outside of its comdat group.\n"); return true; } if (issues.bit_aligned_aggregate_argument) { /* Let's only remove parameters/return values from such functions. TODO: We could only prevent splitting the problematic parameters if anybody thinks it is worth it. */ if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "A call of %s has bit-aligned aggregate argument," " disabling parameter splitting.\n", node->dump_name ()); isra_func_summary *ifs = func_sums->get (node); gcc_checking_assert (ifs); unsigned param_count = vec_safe_length (ifs->m_parameters); for (unsigned i = 0; i < param_count; i++) (*ifs->m_parameters)[i].split_candidate = false; } return false; } /* Find the access with corresponding OFFSET and SIZE among accesses in PARAM_DESC and return it or NULL if such an access is not there. */ static param_access * find_param_access (isra_param_desc *param_desc, unsigned offset, unsigned size) { unsigned pclen = vec_safe_length (param_desc->accesses); /* The search is linear but the number of stored accesses is bound by PARAM_IPA_SRA_MAX_REPLACEMENTS, so most probably 8. */ for (unsigned i = 0; i < pclen; i++) if ((*param_desc->accesses)[i]->unit_offset == offset && (*param_desc->accesses)[i]->unit_size == size) return (*param_desc->accesses)[i]; return NULL; } /* Return iff the total size of definite replacement SIZE would violate the limit set for it in PARAM. */ static bool size_would_violate_limit_p (isra_param_desc *desc, unsigned size) { unsigned limit = desc->param_size_limit; if (size > limit || (!desc->by_ref && size == limit)) return true; return false; } /* Increase reached size of DESC by SIZE or disqualify it if it would violate the set limit. IDX is the parameter number which is dumped when disqualifying. */ static void bump_reached_size (isra_param_desc *desc, unsigned size, unsigned idx) { unsigned after = desc->size_reached + size; if (size_would_violate_limit_p (desc, after)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " ...size limit reached, disqualifying " "candidate parameter %u\n", idx); desc->split_candidate = false; return; } desc->size_reached = after; } /* Take all actions required to deal with an edge CS that represents a call to an unknown or un-analyzed function, for both parameter removal and splitting. */ static void process_edge_to_unknown_caller (cgraph_edge *cs) { isra_func_summary *from_ifs = func_sums->get (cs->caller); gcc_checking_assert (from_ifs); isra_call_summary *csum = call_sums->get (cs); if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "Processing an edge to an unknown caller from %s:\n", cs->caller->dump_name ()); unsigned args_count = csum->m_arg_flow.length (); for (unsigned i = 0; i < args_count; i++) { isra_param_flow *ipf = &csum->m_arg_flow[i]; if (ipf->pointer_pass_through) { isra_param_desc *param_desc = &(*from_ifs->m_parameters)[get_single_param_flow_source (ipf)]; param_desc->locally_unused = false; param_desc->split_candidate = false; continue; } if (ipf->aggregate_pass_through) { unsigned idx = get_single_param_flow_source (ipf); isra_param_desc *param_desc = &(*from_ifs->m_parameters)[idx]; param_desc->locally_unused = false; if (!param_desc->split_candidate) continue; gcc_assert (!param_desc->by_ref); param_access *pacc = find_param_access (param_desc, ipf->unit_offset, ipf->unit_size); gcc_checking_assert (pacc); pacc->certain = true; if (overlapping_certain_accesses_p (param_desc, NULL)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " ...leading to overlap, " " disqualifying candidate parameter %u\n", idx); param_desc->split_candidate = false; } else bump_reached_size (param_desc, pacc->unit_size, idx); ipf->aggregate_pass_through = false; continue; } for (int j = 0; j < ipf->length; j++) { int input_idx = ipf->inputs[j]; (*from_ifs->m_parameters)[input_idx].locally_unused = false; } } } /* Propagate parameter removal information through cross-SCC edge CS, i.e. decrease the use count in the caller parameter descriptor for each use in this call. */ static void param_removal_cross_scc_edge (cgraph_edge *cs) { enum availability availability; cgraph_node *callee = cs->callee->function_symbol (&availability); isra_func_summary *to_ifs = func_sums->get (callee); if (!to_ifs || !to_ifs->m_candidate || (availability < AVAIL_AVAILABLE) || vec_safe_is_empty (to_ifs->m_parameters)) { process_edge_to_unknown_caller (cs); return; } isra_func_summary *from_ifs = func_sums->get (cs->caller); gcc_checking_assert (from_ifs); isra_call_summary *csum = call_sums->get (cs); unsigned args_count = csum->m_arg_flow.length (); unsigned param_count = vec_safe_length (to_ifs->m_parameters); for (unsigned i = 0; i < args_count; i++) { bool unused_in_callee; if (i < param_count) unused_in_callee = (*to_ifs->m_parameters)[i].locally_unused; else unused_in_callee = false; if (!unused_in_callee) { isra_param_flow *ipf = &csum->m_arg_flow[i]; for (int j = 0; j < ipf->length; j++) { int input_idx = ipf->inputs[j]; (*from_ifs->m_parameters)[input_idx].locally_unused = false; } } } } /* Unless it is already there, push NODE which is also described by IFS to STACK. */ static void isra_push_node_to_stack (cgraph_node *node, isra_func_summary *ifs, vec *stack) { if (!ifs->m_queued) { ifs->m_queued = true; stack->safe_push (node); } } /* If parameter with index INPUT_IDX is marked as locally unused, mark it as used and push CALLER on STACK. */ static void isra_mark_caller_param_used (isra_func_summary *from_ifs, int input_idx, cgraph_node *caller, vec *stack) { if ((*from_ifs->m_parameters)[input_idx].locally_unused) { (*from_ifs->m_parameters)[input_idx].locally_unused = false; isra_push_node_to_stack (caller, from_ifs, stack); } } /* Propagate information that any parameter is not used only locally within a SCC across CS to the caller, which must be in the same SCC as the callee. Push any callers that need to be re-processed to STACK. */ static void propagate_used_across_scc_edge (cgraph_edge *cs, vec *stack) { isra_func_summary *from_ifs = func_sums->get (cs->caller); if (!from_ifs || vec_safe_is_empty (from_ifs->m_parameters)) return; isra_call_summary *csum = call_sums->get (cs); gcc_checking_assert (csum); unsigned args_count = csum->m_arg_flow.length (); enum availability availability; cgraph_node *callee = cs->callee->function_symbol (&availability); isra_func_summary *to_ifs = func_sums->get (callee); unsigned param_count = (to_ifs && (availability >= AVAIL_AVAILABLE)) ? vec_safe_length (to_ifs->m_parameters) : 0; for (unsigned i = 0; i < args_count; i++) { if (i < param_count && (*to_ifs->m_parameters)[i].locally_unused) continue; /* The argument is needed in the callee it, we must mark the parameter as used also in the caller and its callers within this SCC. */ isra_param_flow *ipf = &csum->m_arg_flow[i]; for (int j = 0; j < ipf->length; j++) { int input_idx = ipf->inputs[j]; isra_mark_caller_param_used (from_ifs, input_idx, cs->caller, stack); } } } /* Propagate information that any parameter is not used only locally within a SCC (i.e. is used also elsewhere) to all callers of NODE that are in the same SCC. Push any callers that need to be re-processed to STACK. */ static bool propagate_used_to_scc_callers (cgraph_node *node, void *data) { vec *stack = (vec *) data; cgraph_edge *cs; for (cs = node->callers; cs; cs = cs->next_caller) if (ipa_edge_within_scc (cs)) propagate_used_across_scc_edge (cs, stack); return false; } /* Return true iff all certain accesses in ARG_DESC are also present as certain accesses in PARAM_DESC. */ static bool all_callee_accesses_present_p (isra_param_desc *param_desc, isra_param_desc *arg_desc) { unsigned aclen = vec_safe_length (arg_desc->accesses); for (unsigned j = 0; j < aclen; j++) { param_access *argacc = (*arg_desc->accesses)[j]; if (!argacc->certain) continue; param_access *pacc = find_param_access (param_desc, argacc->unit_offset, argacc->unit_size); if (!pacc || !pacc->certain) return false; } return true; } /* Type internal to function pull_accesses_from_callee. Unfortunately gcc 4.8 does not allow instantiating an auto_vec with a type defined within a function so it is a global type. */ enum acc_prop_kind {ACC_PROP_DONT, ACC_PROP_COPY, ACC_PROP_CERTAIN}; /* Attempt to propagate all definite accesses from ARG_DESC to PARAM_DESC, (which belongs to CALLER) if they would not violate some constraint there. If successful, return NULL, otherwise return the string reason for failure (which can be written to the dump file). DELTA_OFFSET is the known offset of the actual argument withing the formal parameter (so of ARG_DESCS within PARAM_DESCS), ARG_SIZE is the size of the actual argument or zero, if not known. In case of success, set *CHANGE_P to true if propagation actually changed anything. */ static const char * pull_accesses_from_callee (cgraph_node *caller, isra_param_desc *param_desc, isra_param_desc *arg_desc, unsigned delta_offset, unsigned arg_size, bool *change_p) { unsigned pclen = vec_safe_length (param_desc->accesses); unsigned aclen = vec_safe_length (arg_desc->accesses); unsigned prop_count = 0; unsigned prop_size = 0; bool change = false; auto_vec prop_kinds (aclen); for (unsigned j = 0; j < aclen; j++) { param_access *argacc = (*arg_desc->accesses)[j]; prop_kinds.safe_push (ACC_PROP_DONT); if (arg_size > 0 && argacc->unit_offset + argacc->unit_size > arg_size) return "callee access outsize size boundary"; if (!argacc->certain) continue; unsigned offset = argacc->unit_offset + delta_offset; /* Given that accesses are initially stored according to increasing offset and decreasing size in case of equal offsets, the following searches could be written more efficiently if we kept the ordering when copying. But the number of accesses is capped at PARAM_IPA_SRA_MAX_REPLACEMENTS (so most likely 8) and the code gets messy quickly, so let's improve on that only if necessary. */ bool exact_match = false; for (unsigned i = 0; i < pclen; i++) { /* Check for overlaps. */ param_access *pacc = (*param_desc->accesses)[i]; if (pacc->unit_offset == offset && pacc->unit_size == argacc->unit_size) { if (argacc->alias_ptr_type != pacc->alias_ptr_type || !types_compatible_p (argacc->type, pacc->type)) return "propagated access types would not match existing ones"; exact_match = true; if (!pacc->certain) { prop_kinds[j] = ACC_PROP_CERTAIN; prop_size += argacc->unit_size; change = true; } continue; } if (offset < pacc->unit_offset + pacc->unit_size && offset + argacc->unit_size > pacc->unit_offset) { /* None permissible with load accesses, possible to fit into argument ones. */ if (pacc->certain || offset < pacc->unit_offset || (offset + argacc->unit_size > pacc->unit_offset + pacc->unit_size)) return "a propagated access would conflict in caller"; } } if (!exact_match) { prop_kinds[j] = ACC_PROP_COPY; prop_count++; prop_size += argacc->unit_size; change = true; } } if (!change) return NULL; if ((prop_count + pclen > (unsigned) opt_for_fn (caller->decl, param_ipa_sra_max_replacements)) || size_would_violate_limit_p (param_desc, param_desc->size_reached + prop_size)) return "propagating accesses would violate the count or size limit"; *change_p = true; for (unsigned j = 0; j < aclen; j++) { if (prop_kinds[j] == ACC_PROP_COPY) { param_access *argacc = (*arg_desc->accesses)[j]; param_access *copy = ggc_cleared_alloc (); copy->unit_offset = argacc->unit_offset + delta_offset; copy->unit_size = argacc->unit_size; copy->type = argacc->type; copy->alias_ptr_type = argacc->alias_ptr_type; copy->certain = true; vec_safe_push (param_desc->accesses, copy); } else if (prop_kinds[j] == ACC_PROP_CERTAIN) { param_access *argacc = (*arg_desc->accesses)[j]; param_access *csp = find_param_access (param_desc, argacc->unit_offset + delta_offset, argacc->unit_size); csp->certain = true; } } param_desc->size_reached += prop_size; return NULL; } /* Propagate parameter splitting information through call graph edge CS. Return true if any changes that might need to be propagated within SCCs have been made. The function also clears the aggregate_pass_through and pointer_pass_through in call summaries which do not need to be processed again if this CS is revisited when iterating while changes are propagated within an SCC. */ static bool param_splitting_across_edge (cgraph_edge *cs) { bool res = false; bool cross_scc = !ipa_edge_within_scc (cs); enum availability availability; cgraph_node *callee = cs->callee->function_symbol (&availability); isra_func_summary *from_ifs = func_sums->get (cs->caller); gcc_checking_assert (from_ifs && from_ifs->m_parameters); isra_call_summary *csum = call_sums->get (cs); gcc_checking_assert (csum); unsigned args_count = csum->m_arg_flow.length (); isra_func_summary *to_ifs = func_sums->get (callee); unsigned param_count = ((to_ifs && to_ifs->m_candidate && (availability >= AVAIL_AVAILABLE)) ? vec_safe_length (to_ifs->m_parameters) : 0); if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "Splitting across %s->%s:\n", cs->caller->dump_name (), callee->dump_name ()); unsigned i; for (i = 0; (i < args_count) && (i < param_count); i++) { isra_param_desc *arg_desc = &(*to_ifs->m_parameters)[i]; isra_param_flow *ipf = &csum->m_arg_flow[i]; if (arg_desc->locally_unused) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " ->%u: unused in callee\n", i); ipf->pointer_pass_through = false; continue; } if (ipf->pointer_pass_through) { int idx = get_single_param_flow_source (ipf); isra_param_desc *param_desc = &(*from_ifs->m_parameters)[idx]; if (!param_desc->split_candidate) continue; gcc_assert (param_desc->by_ref); if (!arg_desc->split_candidate || !arg_desc->by_ref) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " %u->%u: not candidate or not by " "reference in callee\n", idx, i); param_desc->split_candidate = false; ipf->pointer_pass_through = false; res = true; } else if (!ipf->safe_to_import_accesses) { if (!all_callee_accesses_present_p (param_desc, arg_desc)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " %u->%u: cannot import accesses.\n", idx, i); param_desc->split_candidate = false; ipf->pointer_pass_through = false; res = true; } else { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " %u->%u: verified callee accesses " "present.\n", idx, i); if (cross_scc) ipf->pointer_pass_through = false; } } else { const char *pull_failure = pull_accesses_from_callee (cs->caller, param_desc, arg_desc, 0, 0, &res); if (pull_failure) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " %u->%u: by_ref access pull " "failed: %s.\n", idx, i, pull_failure); param_desc->split_candidate = false; ipf->pointer_pass_through = false; res = true; } else { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " %u->%u: by_ref access pull " "succeeded.\n", idx, i); if (cross_scc) ipf->pointer_pass_through = false; } } } else if (ipf->aggregate_pass_through) { int idx = get_single_param_flow_source (ipf); isra_param_desc *param_desc = &(*from_ifs->m_parameters)[idx]; if (!param_desc->split_candidate) continue; gcc_assert (!param_desc->by_ref); param_access *pacc = find_param_access (param_desc, ipf->unit_offset, ipf->unit_size); gcc_checking_assert (pacc); if (pacc->certain) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " %u->%u: already certain\n", idx, i); ipf->aggregate_pass_through = false; } else if (!arg_desc->split_candidate || arg_desc->by_ref) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " %u->%u: not candidate or by " "reference in callee\n", idx, i); pacc->certain = true; if (overlapping_certain_accesses_p (param_desc, NULL)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " ...leading to overlap, " " disqualifying candidate parameter %u\n", idx); param_desc->split_candidate = false; } else bump_reached_size (param_desc, pacc->unit_size, idx); ipf->aggregate_pass_through = false; res = true; } else { const char *pull_failure = pull_accesses_from_callee (cs->caller, param_desc, arg_desc, ipf->unit_offset, ipf->unit_size, &res); if (pull_failure) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " %u->%u: arg access pull " "failed: %s.\n", idx, i, pull_failure); ipf->aggregate_pass_through = false; pacc->certain = true; if (overlapping_certain_accesses_p (param_desc, NULL)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " ...leading to overlap, " " disqualifying candidate parameter %u\n", idx); param_desc->split_candidate = false; } else bump_reached_size (param_desc, pacc->unit_size, idx); res = true; } else { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " %u->%u: arg access pull " "succeeded.\n", idx, i); if (cross_scc) ipf->aggregate_pass_through = false; } } } } /* Handle argument-parameter count mismatches. */ for (; (i < args_count); i++) { isra_param_flow *ipf = &csum->m_arg_flow[i]; if (ipf->pointer_pass_through || ipf->aggregate_pass_through) { int idx = get_single_param_flow_source (ipf); ipf->pointer_pass_through = false; ipf->aggregate_pass_through = false; isra_param_desc *param_desc = &(*from_ifs->m_parameters)[idx]; if (!param_desc->split_candidate) continue; if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " %u->%u: no corresponding formal parameter\n", idx, i); param_desc->split_candidate = false; res = true; } } return res; } /* Worker for call_for_symbol_and_aliases, look at all callers and if all their callers ignore the return value, or come from the same SCC and use the return value only to compute their return value, return false, otherwise return true. */ static bool retval_used_p (cgraph_node *node, void *) { for (cgraph_edge *cs = node->callers; cs; cs = cs->next_caller) { isra_call_summary *csum = call_sums->get (cs); gcc_checking_assert (csum); if (csum->m_return_ignored) continue; if (!csum->m_return_returned) return true; isra_func_summary *from_ifs = func_sums->get (cs->caller); if (!from_ifs || !from_ifs->m_candidate) return true; if (!ipa_edge_within_scc (cs) && !from_ifs->m_return_ignored) return true; } return false; } /* Push into NEW_PARAMS all required parameter adjustment entries to copy or modify parameter which originally had index BASE_INDEX, in the adjustment vector of parent clone (if any) had PREV_CLONE_INDEX and was described by PREV_ADJUSTMENT. If the parent clone is the original function, PREV_ADJUSTMENT is NULL and PREV_CLONE_INDEX is equal to BASE_INDEX. */ static void push_param_adjustments_for_index (isra_func_summary *ifs, unsigned base_index, unsigned prev_clone_index, ipa_adjusted_param *prev_adjustment, vec **new_params) { isra_param_desc *desc = &(*ifs->m_parameters)[base_index]; if (desc->locally_unused) { if (dump_file) fprintf (dump_file, " Will remove parameter %u\n", base_index); return; } if (!desc->split_candidate) { ipa_adjusted_param adj; if (prev_adjustment) { adj = *prev_adjustment; adj.prev_clone_adjustment = true; adj.prev_clone_index = prev_clone_index; } else { memset (&adj, 0, sizeof (adj)); adj.op = IPA_PARAM_OP_COPY; adj.base_index = base_index; adj.prev_clone_index = prev_clone_index; } vec_safe_push ((*new_params), adj); return; } if (dump_file) fprintf (dump_file, " Will split parameter %u\n", base_index); gcc_assert (!prev_adjustment || prev_adjustment->op == IPA_PARAM_OP_COPY); unsigned aclen = vec_safe_length (desc->accesses); for (unsigned j = 0; j < aclen; j++) { param_access *pa = (*desc->accesses)[j]; if (!pa->certain) continue; if (dump_file) fprintf (dump_file, " - component at byte offset %u, " "size %u\n", pa->unit_offset, pa->unit_size); ipa_adjusted_param adj; memset (&adj, 0, sizeof (adj)); adj.op = IPA_PARAM_OP_SPLIT; adj.base_index = base_index; adj.prev_clone_index = prev_clone_index; adj.param_prefix_index = IPA_PARAM_PREFIX_ISRA; adj.reverse = pa->reverse; adj.type = pa->type; adj.alias_ptr_type = pa->alias_ptr_type; adj.unit_offset = pa->unit_offset; vec_safe_push ((*new_params), adj); } } /* Worker for all call_for_symbol_thunks_and_aliases. Set calls_comdat_local flag of all callers of NODE. */ static bool mark_callers_calls_comdat_local (struct cgraph_node *node, void *) { for (cgraph_edge *cs = node->callers; cs; cs = cs->next_caller) cs->caller->calls_comdat_local = true; return false; } /* Do final processing of results of IPA propagation regarding NODE, clone it if appropriate. */ static void process_isra_node_results (cgraph_node *node, hash_map *clone_num_suffixes) { isra_func_summary *ifs = func_sums->get (node); if (!ifs || !ifs->m_candidate) return; auto_vec surviving_params; bool check_surviving = false; if (node->clone.param_adjustments) { check_surviving = true; node->clone.param_adjustments->get_surviving_params (&surviving_params); } unsigned param_count = vec_safe_length (ifs->m_parameters); bool will_change_function = false; if (ifs->m_returns_value && ifs->m_return_ignored) will_change_function = true; else for (unsigned i = 0; i < param_count; i++) { isra_param_desc *desc = &(*ifs->m_parameters)[i]; if ((desc->locally_unused || desc->split_candidate) /* Make sure we do not clone just to attempt to remove an already removed unused argument. */ && (!check_surviving || (i < surviving_params.length () && surviving_params[i]))) { will_change_function = true; break; } } if (!will_change_function) return; if (dump_file) { fprintf (dump_file, "\nEvaluating analysis results for %s\n", node->dump_name ()); if (ifs->m_returns_value && ifs->m_return_ignored) fprintf (dump_file, " Will remove return value.\n"); } vec *new_params = NULL; if (ipa_param_adjustments *old_adjustments = node->clone.param_adjustments) { unsigned old_adj_len = vec_safe_length (old_adjustments->m_adj_params); for (unsigned i = 0; i < old_adj_len; i++) { ipa_adjusted_param *old_adj = &(*old_adjustments->m_adj_params)[i]; push_param_adjustments_for_index (ifs, old_adj->base_index, i, old_adj, &new_params); } } else for (unsigned i = 0; i < param_count; i++) push_param_adjustments_for_index (ifs, i, i, NULL, &new_params); ipa_param_adjustments *new_adjustments = (new (ggc_alloc ()) ipa_param_adjustments (new_params, param_count, ifs->m_returns_value && ifs->m_return_ignored)); if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "\n Created adjustments:\n"); new_adjustments->dump (dump_file); } unsigned &suffix_counter = clone_num_suffixes->get_or_insert ( IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME ( node->decl))); vec callers = node->collect_callers (); cgraph_node *new_node = node->create_virtual_clone (callers, NULL, new_adjustments, "isra", suffix_counter); suffix_counter++; if (node->calls_comdat_local && node->same_comdat_group) { new_node->add_to_same_comdat_group (node); new_node->call_for_symbol_and_aliases (mark_callers_calls_comdat_local, NULL, true); } new_node->calls_comdat_local = node->calls_comdat_local; if (dump_file) fprintf (dump_file, " Created new node %s\n", new_node->dump_name ()); callers.release (); } /* Check which parameters of NODE described by IFS have survived until IPA-SRA and disable transformations for those which have not or which should not transformed because the associated debug counter reached its limit. Return true if none survived or if there were no candidates to begin with. */ static bool disable_unavailable_parameters (cgraph_node *node, isra_func_summary *ifs) { bool ret = true; unsigned len = vec_safe_length (ifs->m_parameters); if (!len) return true; auto_vec surviving_params; bool check_surviving = false; if (node->clone.param_adjustments) { check_surviving = true; node->clone.param_adjustments->get_surviving_params (&surviving_params); } bool dumped_first = false; for (unsigned i = 0; i < len; i++) { isra_param_desc *desc = &(*ifs->m_parameters)[i]; if (!dbg_cnt (ipa_sra_params)) { desc->locally_unused = false; desc->split_candidate = false; } else if (check_surviving && (i >= surviving_params.length () || !surviving_params[i])) { /* Even if the parameter was removed by a previous IPA pass, we do not clear locally_unused because if it really is unused, this information might be useful in callers. */ desc->split_candidate = false; if (dump_file && (dump_flags & TDF_DETAILS)) { if (!dumped_first) { fprintf (dump_file, "The following parameters of %s are dead on " "arrival:", node->dump_name ()); dumped_first = true; } fprintf (dump_file, " %u", i); } } else if (desc->locally_unused || desc->split_candidate) ret = false; } if (dumped_first) fprintf (dump_file, "\n"); return ret; } /* Run the interprocedural part of IPA-SRA. */ static unsigned int ipa_sra_analysis (void) { if (dump_file) { fprintf (dump_file, "\n========== IPA-SRA IPA stage ==========\n"); ipa_sra_dump_all_summaries (dump_file); } gcc_checking_assert (func_sums); gcc_checking_assert (call_sums); cgraph_node **order = XCNEWVEC (cgraph_node *, symtab->cgraph_count); auto_vec stack; int node_scc_count = ipa_reduced_postorder (order, true, NULL); /* One sweep from callees to callers for parameter removal and splitting. */ for (int i = 0; i < node_scc_count; i++) { cgraph_node *scc_rep = order[i]; vec cycle_nodes = ipa_get_nodes_in_cycle (scc_rep); unsigned j; /* Preliminary IPA function level checks and first step of parameter removal. */ cgraph_node *v; FOR_EACH_VEC_ELT (cycle_nodes, j, v) { isra_func_summary *ifs = func_sums->get (v); if (!ifs || !ifs->m_candidate) continue; if (!ipa_sra_ipa_function_checks (v) || check_all_callers_for_issues (v)) { ifs->zap (); continue; } if (disable_unavailable_parameters (v, ifs)) continue; for (cgraph_edge *cs = v->indirect_calls; cs; cs = cs->next_callee) process_edge_to_unknown_caller (cs); for (cgraph_edge *cs = v->callees; cs; cs = cs->next_callee) if (!ipa_edge_within_scc (cs)) param_removal_cross_scc_edge (cs); } /* Look at edges within the current SCC and propagate used-ness across them, pushing onto the stack all notes which might need to be revisited. */ FOR_EACH_VEC_ELT (cycle_nodes, j, v) v->call_for_symbol_thunks_and_aliases (propagate_used_to_scc_callers, &stack, true); /* Keep revisiting and pushing until nothing changes. */ while (!stack.is_empty ()) { cgraph_node *v = stack.pop (); isra_func_summary *ifs = func_sums->get (v); gcc_checking_assert (ifs && ifs->m_queued); ifs->m_queued = false; v->call_for_symbol_thunks_and_aliases (propagate_used_to_scc_callers, &stack, true); } /* Parameter splitting. */ bool repeat_scc_access_propagation; do { repeat_scc_access_propagation = false; FOR_EACH_VEC_ELT (cycle_nodes, j, v) { isra_func_summary *ifs = func_sums->get (v); if (!ifs || !ifs->m_candidate || vec_safe_is_empty (ifs->m_parameters)) continue; for (cgraph_edge *cs = v->callees; cs; cs = cs->next_callee) if (param_splitting_across_edge (cs)) repeat_scc_access_propagation = true; } } while (repeat_scc_access_propagation); if (flag_checking) FOR_EACH_VEC_ELT (cycle_nodes, j, v) verify_splitting_accesses (v, true); cycle_nodes.release (); } /* One sweep from caller to callees for result removal. */ for (int i = node_scc_count - 1; i >= 0 ; i--) { cgraph_node *scc_rep = order[i]; vec cycle_nodes = ipa_get_nodes_in_cycle (scc_rep); unsigned j; cgraph_node *v; FOR_EACH_VEC_ELT (cycle_nodes, j, v) { isra_func_summary *ifs = func_sums->get (v); if (!ifs || !ifs->m_candidate) continue; bool return_needed = (ifs->m_returns_value && (!dbg_cnt (ipa_sra_retvalues) || v->call_for_symbol_and_aliases (retval_used_p, NULL, true))); ifs->m_return_ignored = !return_needed; if (return_needed) isra_push_node_to_stack (v, ifs, &stack); } while (!stack.is_empty ()) { cgraph_node *node = stack.pop (); isra_func_summary *ifs = func_sums->get (node); gcc_checking_assert (ifs && ifs->m_queued); ifs->m_queued = false; for (cgraph_edge *cs = node->callees; cs; cs = cs->next_callee) if (ipa_edge_within_scc (cs) && call_sums->get (cs)->m_return_returned) { enum availability av; cgraph_node *callee = cs->callee->function_symbol (&av); isra_func_summary *to_ifs = func_sums->get (callee); if (to_ifs && to_ifs->m_return_ignored) { to_ifs->m_return_ignored = false; isra_push_node_to_stack (callee, to_ifs, &stack); } } } cycle_nodes.release (); } ipa_free_postorder_info (); free (order); if (dump_file) { if (dump_flags & TDF_DETAILS) { fprintf (dump_file, "\n========== IPA-SRA propagation final state " " ==========\n"); ipa_sra_dump_all_summaries (dump_file); } fprintf (dump_file, "\n========== IPA-SRA decisions ==========\n"); } hash_map *clone_num_suffixes = new hash_map; cgraph_node *node; FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) process_isra_node_results (node, clone_num_suffixes); delete clone_num_suffixes; ggc_delete (func_sums); func_sums = NULL; delete call_sums; call_sums = NULL; if (dump_file) fprintf (dump_file, "\n========== IPA SRA IPA analysis done " "==========\n\n"); return 0; } const pass_data pass_data_ipa_sra = { IPA_PASS, /* type */ "sra", /* name */ OPTGROUP_NONE, /* optinfo_flags */ TV_IPA_SRA, /* tv_id */ 0, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ ( TODO_dump_symtab | TODO_remove_functions ), /* todo_flags_finish */ }; class pass_ipa_sra : public ipa_opt_pass_d { public: pass_ipa_sra (gcc::context *ctxt) : ipa_opt_pass_d (pass_data_ipa_sra, ctxt, ipa_sra_generate_summary, /* generate_summary */ ipa_sra_write_summary, /* write_summary */ ipa_sra_read_summary, /* read_summary */ NULL , /* write_optimization_summary */ NULL, /* read_optimization_summary */ NULL, /* stmt_fixup */ 0, /* function_transform_todo_flags_start */ NULL, /* function_transform */ NULL) /* variable_transform */ {} /* opt_pass methods: */ virtual bool gate (function *) { /* TODO: We should remove the optimize check after we ensure we never run IPA passes when not optimizing. */ return (flag_ipa_sra && optimize); } virtual unsigned int execute (function *) { return ipa_sra_analysis (); } }; // class pass_ipa_sra } // anon namespace ipa_opt_pass_d * make_pass_ipa_sra (gcc::context *ctxt) { return new pass_ipa_sra (ctxt); } #include "gt-ipa-sra.h"