> * Makefile.in: Add ipa-reorder.o. > * cgraph.c (cgraph_node::dump): Dump > text_sorted_order. > (cgraph_node_cmp_by_text_sorted): > New function that sorts functions based > on text_sorted_order. > * cgraph.h (cgraph_node): Add text_sorted_order. > (cgraph_node_cmp_by_text_sorted): New. > * cgraphclones.c (cgraph_node::create_clone): > Clone also text_sorted_order. > * cgraphunit.c (node_cmp): Remove. > (expand_all_functions): Use new function > cgraph_node_cmp_by_text_sorted. > * common.opt: Add new option reorder_functions_algorithm. > * flag-types.h (enum reorder_functions_algorithm): > New enum. > * ipa-reorder.c: New file. > * lto-cgraph.c (lto_output_node): Stream in and out > text_sorted_order. > (input_node): Likewise. > * passes.def: Add pass_ipa_reorder. > * timevar.def (TV_IPA_REORDER): New. > * tree-pass.h (make_pass_ipa_reorder): New. > * varasm.c (default_function_section): Assign text.sorted.X > section. > > gcc/lto/ChangeLog: > > 2019-11-25 Martin Liska <mli...@suse.cz> > > * lto-partition.c (node_cmp): Remove. > (lto_balanced_map): Use new cgraph_node_cmp_by_text_sorted. > +/* Sort cgraph_nodes by text_sorted_order if available, or by order. */ > + > +int > +cgraph_node_cmp_by_text_sorted (const void *pa, const void *pb) > +{ > + const cgraph_node *a = *(const cgraph_node * const *) pa; > + const cgraph_node *b = *(const cgraph_node * const *) pb; > + > + /* Functions with text_sorted_order should be before these > + without profile. */ > + if (a->text_sorted_order == 0 || b->text_sorted_order == 0) > + return a->text_sorted_order - b->text_sorted_order; > + > + return a->text_sorted_order != b->text_sorted_order > + ? b->text_sorted_order - a->text_sorted_order > + : b->order - a->order; > +}
We now have tp_first_run_node_cmp with needs to be updated and renamed isntead of adding new comparator. > /* Time profiler: first run of function. */ > int tp_first_run; > + /* Order in .text.sorted.* section. */ > + int text_sorted_order; tp_first_run probalby should go into summary since it will live from profling to the ipa-reorder pass where it will be copied to text_sorted_order? Or how these two interface? > diff --git a/gcc/cgraphclones.c b/gcc/cgraphclones.c > index a79491e0b88..f624cbee185 100644 > --- a/gcc/cgraphclones.c > +++ b/gcc/cgraphclones.c > @@ -372,6 +372,7 @@ cgraph_node::create_clone (tree new_decl, profile_count > prof_count, > new_node->rtl = rtl; > new_node->frequency = frequency; > new_node->tp_first_run = tp_first_run; > + new_node->text_sorted_order = text_sorted_order; Copy it also in duplicate_thunk_for_node and create_version_node. I think we should refactor the copying code and share it in all places we duplicate function. > +freorder-functions-algorithm= > +Common Joined RejectNegative Enum(reorder_functions_algorithm) > Var(flag_reorder_functions_algorithm) > Init(REORDER_FUNCTIONS_ALGORITHM_CALL_CHAIN_CLUSTERING) Optimization > +-freorder-functions-algorithm=[first-run|call-chain-clustering] Set the > used function reordering algorithm. > + > +Enum > +Name(reorder_functions_algorithm) Type(enum reorder_functions_algorithm) > UnknownError(unknown function reordering algorithm %qs) > + > +EnumValue > +Enum(reorder_functions_algorithm) String(first-run) > Value(REORDER_FUNCTIONS_ALGORITHM_FIRST_RUN) > + > +EnumValue > +Enum(reorder_functions_algorithm) String(call-chain-clustering) > Value(REORDER_FUNCTIONS_ALGORITHM_CALL_CHAIN_CLUSTERING) I think we should also have "definition-order" which will sort by node->order. For testing we may also want to have "random" which will do something stupid like sorting by symbol name checksum so we could see how these compares. > +/* The algorithm used for function reordering. */ > +enum reorder_functions_algorithm > +{ > + REORDER_FUNCTIONS_ALGORITHM_FIRST_RUN, > + REORDER_FUNCTIONS_ALGORITHM_CALL_CHAIN_CLUSTERING > +}; Isn't this supposed to be generated by awk scripts? > + > +#define C3_CLUSTER_THRESHOLD 1024 description + perhaps PARAM? > + > +struct cluster_edge; > + > +/* Cluster is set of functions considered in C3 algorithm. */ Perhaps an high level overview of C3 algorithm with a reference would be nice. > +/* Sort functions based of first execution of the function. */ > + > +static void > +sort_functions_by_first_run (void) > +{ > + cgraph_node *node; > + > + FOR_EACH_DEFINED_FUNCTION (node) > + if (node->tp_first_run && !node->alias) > + node->text_sorted_order = node->tp_first_run; Why you care about excluding aliases? We also have thunks where tp_first_run is ignored. I am just curious if you got some ICE here. > +} > + > +/* Compare clusters by density after that are established. */ > + > +static int > +cluster_cmp (const void *a_p, const void *b_p) > +{ > + const cluster *a = *(cluster * const *)a_p; > + const cluster *b = *(cluster * const *)b_p; > + > + unsigned fncounta = a->m_functions.length (); > + unsigned fncountb = b->m_functions.length (); I think we still do whitespace after declarations. > + if (fncounta <= 1 || fncountb <= 1) > + return fncountb - fncounta; > + > + sreal r = b->m_time * a->m_size - a->m_time * b->m_size; > + return (r < 0) ? -1 : ((r > 0) ? 1 : 0); > +} > + > +/* Visit callgraph edge CS until we reach a real cgraph_node (not a clone). > + Record such edge to EDGES or traverse recursively. */ > + > +static void > +visit_all_edges_for_caller (auto_vec<cluster_edge *> *edges, > + cgraph_node *node, cgraph_edge *cs) > +{ > + if (cs->inline_failed) > + { > + gcov_type count; > + profile_count pcount = cs->count.ipa (); Similarly here. > + /* A real call edge. */ > + if (!cs->callee->alias > + && cs->callee->definition > + && pcount.initialized_p () > + && (count = pcount.to_gcov_type ()) > 0) > + { > + cluster *caller = (cluster *)node->aux; > + cluster *callee = (cluster *)cs->callee->aux; > + cluster_edge **cedge = callee->m_callers.get (caller); > + > + if (dump_file && (dump_flags & TDF_DETAILS)) > + fprintf (dump_file, "Adding edge:%s->%s:%" PRIu64 "\n", > + node->dump_name (), cs->callee->dump_name (), count); > + > + if (cedge != NULL) > + (*cedge)->m_count += count; > + else > + { > + cluster_edge *cedge = new cluster_edge (caller, callee, count); > + edges->safe_push (cedge); > + callee->m_callers.put (caller, cedge); > + } > + } > + } > + else > + { > + cgraph_node *clone = cs->callee; > + for (cgraph_edge *cs = clone->callees; cs; cs = cs->next_callee) > + visit_all_edges_for_caller (edges, node, cs); > + } > +} With FDO we have likely targets for indirect calls which may or may not be speculative calls at this moment. We may want to put that info into summaries and use here, but that is for incremental change. I think not seeing indirect calls target may be one of main reasons for clusters being mistakely broken up. > + > +/* Sort functions based on call chain clustering, which is an algorithm > + mentioned in the following article: > + > https://research.fb.com/wp-content/uploads/2017/01/cgo2017-hfsort-final1.pdf I would use normal citation format - research.fb.com may change :) Ottoni, Guilherme, and Bertrand Maher. "Optimizing function placement for large-scale data-center applications." Proceedings of the 2017 International Symposium on Code Generation and Optimization. IEEE Press, 2017. > + . */ > + > +static void > +sort_functions_by_c3 (void) > +{ > + cgraph_node *node; > + auto_vec<cluster *> clusters; > + > + /* Create a cluster for each function. */ Putting thunks into their own clusters will do no good at least until we learn to output them independently. So I would add !node->thunk > + FOR_EACH_DEFINED_FUNCTION (node) > + if (!node->alias > + && !node->inlined_to) > + { > + if (dump_file && (dump_flags & TDF_DETAILS)) > + fprintf (dump_file, "Adding node:%s\n", node->dump_name ()); > + > + ipa_size_summary *size_summary = ipa_size_summaries->get (node); > + ipa_fn_summary *fn_summary = ipa_fn_summaries->get (node); > + cluster *c = new cluster (node, size_summary->size, fn_summary->time); > + node->aux = c; > + clusters.safe_push (c); > + } Either you want to walk from edge->callee to function_node or you want to insert all associated aliases and thunks to the cluster I think > + > + auto_vec<cluster_edge *> edges; > + > + /* Insert edges between clusters that have a profile. */ > + for (unsigned i = 0; i < clusters.length (); i++) > + { > + cgraph_node *node = clusters[i]->m_functions[0]; > + for (cgraph_edge *cs = node->callees; cs; cs = cs->next_callee) > + visit_all_edges_for_caller (&edges, node, cs); > + } > + > + /* Now insert all created edges into a heap. */ > + fibonacci_heap <uint64_t, cluster_edge> heap (0); > + > + for (unsigned i = 0; i < clusters.length (); i++) > + { > + cluster *c = clusters[i]; > + for (hash_map<cluster *, cluster_edge *>::iterator it > + = c->m_callers.begin (); it != c->m_callers.end (); ++it) > + { > + cluster_edge *cedge = (*it).second; > + cedge->m_heap_node = heap.insert (cedge->inverted_count (), cedge); > + } > + } > + > + while (!heap.empty ()) > + { > + cluster_edge *cedge = heap.extract_min (); > + cluster *caller = cedge->m_caller; > + cluster *callee = cedge->m_callee; > + cedge->m_heap_node = NULL; > + > + if (dump_file && (dump_flags & TDF_DETAILS)) > + { > + fprintf (dump_file, "Processing cluster edge: %p->%p, count: %" > + PRIu64 "\n", (void *)caller, (void *)callee, cedge->m_count); > + fprintf (dump_file, " source functions (%u): ", caller->m_size); > + for (unsigned j = 0; j < caller->m_functions.length (); j++) > + fprintf (dump_file, "%s ", caller->m_functions[j]->dump_name ()); > + fprintf (dump_file, "\n target functions (%u): ", callee->m_size); > + for (unsigned j = 0; j < callee->m_functions.length (); j++) > + fprintf (dump_file, "%s ", callee->m_functions[j]->dump_name ()); > + fprintf (dump_file, "\n"); > + } > + > + if (caller == callee) > + continue; > + if (caller->m_size + callee->m_size <= C3_CLUSTER_THRESHOLD) Did you experiment with the cluster threshold value? In a way since we have so bad idea about size perhaps we may just set it to infinity. > + { > + if (dump_file && (dump_flags & TDF_DETAILS)) > + fprintf (dump_file, " (clusters merged)\n"); > + > + caller->m_size += callee->m_size; > + caller->m_time += callee->m_time; > + > + /* Append all cgraph_nodes from callee to caller. */ > + for (unsigned i = 0; i < callee->m_functions.length (); i++) > + caller->m_functions.safe_push (callee->m_functions[i]); Right datastructure for this is probably union-find. We don't have a function to append one vector to another? > + > + callee->m_functions.truncate (0); don't we want to free it? > + > + /* Sort the candidate clusters. */ > + clusters.qsort (cluster_cmp); We still have info about what code is used at startup, what code is likely/unlikely. After inlining we also may have a lot of functions that have IPA count of 0 but still have tp_first_run set. So i suppose we may want to experiment with this incrementally. Also merging clusters over even edges profiled 0 time at the end could improve locality if profile run is not representative. > + /* Assign .text.sorted.* section names. */ I would say just text_sorted_order since I think the sections is just one way of arranging it. > + int counter = 1; > + for (unsigned i = 0; i < clusters.length (); i++) > + { > + cluster *c = clusters[i]; > + if (c->m_functions.length () <= 1) > + continue; > + > + for (unsigned j = 0; j < c->m_functions.length (); j++) > + { > + cgraph_node *node = c->m_functions[j]; > + > + if (dump_file) > + fprintf (dump_file, "setting: %d for %s with size:%d\n", > + counter, node->dump_asm_name (), > + ipa_size_summaries->get (node)->size); > + node->text_sorted_order = counter++; > + } > + } > + > + /* Release memory. */ > + FOR_EACH_DEFINED_FUNCTION (node) > + if (!node->alias) > + node->aux = NULL; > + > + for (unsigned i = 0; i < clusters.length (); i++) > + delete clusters[i]; > + > + for (unsigned i = 0; i < edges.length (); i++) > + delete edges[i]; > +} > + > +/* The main function for function sorting. */ > + > +static unsigned int > +ipa_reorder (void) > +{ > + switch (flag_reorder_functions_algorithm) > + { > + case REORDER_FUNCTIONS_ALGORITHM_CALL_CHAIN_CLUSTERING: > + sort_functions_by_c3 (); > + break; > + case REORDER_FUNCTIONS_ALGORITHM_FIRST_RUN: > + sort_functions_by_first_run (); > + break; > + default: > + gcc_unreachable (); > + } > + > + return 0; > +} > + > +const pass_data pass_data_ipa_reorder = > +{ > + IPA_PASS, /* type */ > + "reorder", /* name */ > + OPTGROUP_NONE, /* optinfo_flags */ > + TV_IPA_REORDER, /* tv_id */ > + 0, /* properties_required */ > + 0, /* properties_provided */ > + 0, /* properties_destroyed */ > + 0, /* todo_flags_start */ > + 0, /* todo_flags_finish */ > +}; > + > +class pass_ipa_reorder : public ipa_opt_pass_d > +{ > +public: > + pass_ipa_reorder (gcc::context *ctxt) > + : ipa_opt_pass_d (pass_data_ipa_reorder, ctxt, > + NULL, /* generate_summary */ > + NULL, /* write_summary */ > + NULL, /* 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 *); > + virtual unsigned int execute (function *) { return ipa_reorder (); } > + > +}; // class pass_ipa_reorder > + > +bool > +pass_ipa_reorder::gate (function *) > +{ > + return flag_profile_reorder_functions && flag_profile_use && flag_wpa; There is nothing special about flag_wpa. We can also run it meaningfully with -flto-partitions=none or with -fwhole-program. I think we may 1) default to node->order if no FDO is available I think it is better than our current completely backward ordering We may tune clustering to beat node->order too. 2) if FDO but no LTO is available use tp_first_run since the sections combine well across translation units. This also should apply for incremental LTO builds but not for -fwhole-program builds 3) if FDO and non-incremental LTO or -fwhole-program is available use clustering. moreover with current experineces I think flag_profile_reorder_functions and flag_reorder_functions_algorithm needs to be Optimization in the .opt file and thus the code needs to be able to work meaningfully on mixed units. Something like place 1) functions with tp_first_run 2) functions build with clusterings 3) remaining functions and always do all three algorithms depending on opt flags. More funilly becuase the preferred logic is not known until link-time I guess we want to have flag_reorder_functions_algorithm with REORDER_DEFAULT which will do the above choice based on presence of profile (tested by node->count.ipa ().nonzero_p ()), tp_first_run, in_lto_p, flag_whole_proram > + order.qsort (cgraph_node_cmp_by_text_sorted); > + noreorder.qsort (cgraph_node_cmp_by_text_sorted); This also needs updating after my mainline fixes. We do not want to sort noreorder this way. > + cgraph_node *node = cgraph_node::get (decl); > + if (freq != NODE_FREQUENCY_UNLIKELY_EXECUTED && node->text_sorted_order > > 0) > + { > + char section_name[64]; > + sprintf (section_name, ".text.sorted.%010d", > + node->text_sorted_order); > + return get_named_text_section (decl, section_name, NULL); > + } > + I would still control this by a flag (again with bit complicated default). First there are non-GNU linkers and second it only works well for one translation unit in whole DSO unless we do time profiling. Also when we go this way we want to disable sorting in cgraphunit.c so we do not lose late propagators for no benefits. Finally I still think gas fragments would be useful here to save extra cost of alignments and also be able to use short call/jmp instructions across functions. -ffunction-sections is not free. We still have problem with functions in COMDAT group, right? You should be able to see them with -flto -fno-use-linker-plugin Honza