Re: [google] Linker plugin to do function reordering using callgraph edge profiles (issue5124041)

[Sriraman Tallam <tmsriram at google dot com>]

Made all the changes. Attaching new patch of updated files.

On Tue, Sep 27, 2011 at 11:26 AM, Easwaran Raman <eraman@google.com> wrote:
>
> +static inline hashval_t
> +edge_hash_function (unsigned int id1, unsigned int id2)
> +{
> + ?/* If the number of functions is less than 1000, this gives a unique value
> + ? ? for every function id combination. ?*/
> + ?const int MULTIPLIER = 1000;
> + ?return id1* MULTIPLIER + id2;
>
> Change to id1 << 16 | id2
>
> + ?if (edge_map == NULL)
> + ? ?{
> + ? ? ?edge_map = htab_create (25, edge_map_htab_hash_descriptor,
> + ?edge_map_htab_eq_descriptor , NULL);
>
> ?Use a ?larger size and don't hardcode the value.
>
> + ?if (function_map == NULL)
> + ? ?{
> + ? ? ?function_map = htab_create (25, function_map_htab_hash_descriptor,
> + ?function_map_htab_eq_descriptor , NULL);
>
> ?Use a ?larger size and don't hardcode the value.
>
> + ?caller_node = get_function_node (caller);
> + ?/* Real nodes are nodes that correspond to .text sections found. ?These will
> + ? ? definitely be sorted. ?*/
> + ?set_as_real_node (caller_node);
>
> This is redundant as set_node_type sets the type correctly.
>
> + ?if (*slot == NULL)
> + ? ?{
> + ? ? ?reset_functions (edge, new_node, kept_node);
> + ? ? ?*slot = edge;
> + ? ? ?add_edge_to_node (new_node, edge);
>
> edge will still be in old_node's edge_list

I do not have to explicitly delete this as the merged node's edge_list
will never be traversed except when cleaning up.

>
> +static void set_node_type (Node *n)
> +{
> + ?void **slot;
> + ?char *name = n->name;
> + ?slot = htab_find_slot_with_hash (section_map, name, htab_hash_string (name),
> + ? INSERT);
>
> Use htab_find_with_hash or pass NOINSERT.
>
> + ?/* Allocate section_map. ?*/
> + ?if (section_map == NULL)
> + ? ?{
> + ? ? ?section_map = htab_create (10, section_map_htab_hash_descriptor,
> + section_map_htab_eq_descriptor , NULL);
>
> With -ffunction-sections, this should be roughly equal to size of function_map.
>
> +static void
> +write_out_node (FILE *fp, char *name,
> + void **handles, unsigned int *shndx, int position)
> +{
> + ?void **slot;
> + ?slot = htab_find_slot_with_hash (section_map, name, htab_hash_string (name),
> + ? INSERT);
>
> Use htab_find_with_hash or pass NOINSERT.
>
> Index: function_reordering_plugin/function_reordering_plugin.c
> ===================================================================
> --- function_reordering_plugin/function_reordering_plugin.c ? ? (revision 0)
> +++ function_reordering_plugin/function_reordering_plugin.c ? ? (revision 0)
>
> + ? ? ? ? ?parse_callgraph_section_contents (section_contents,
> (unsigned int)length);
> + ? ? ? ?}
> + ? ? ?else if (name != NULL)
> + ? ? ? ?free (name);
>
> name should be freed in the body of then and else-if ?as well.
>
> -Easwaran
> On Mon, Sep 26, 2011 at 5:22 PM, Sriraman Tallam <tmsriram@google.com> wrote:
> >
> > *Resending as plain text*
> >
> > I am attaching a patch of the updated files. This patch was meant for
> > the google gcc-4_6 branch. Sorry for not mentioning this upfront in my
> > original mail.
> > Thanks,
> > ?-Sri.
> >
> >
> >
> > > On Mon, Sep 26, 2011 at 9:53 AM, Sriraman Tallam <tmsriram@google.com> wrote:
> > >>
> > >> On Mon, Sep 26, 2011 at 9:22 AM, Nathan Froyd <nfroyd@mozilla.com> wrote:
> > >> > On 9/23/2011 6:03 PM, Sriraman Tallam wrote:
> > >> >>
> > >> >> This patch adds a new linker plugin to re-order functions.
> > >> >
> > >> > This is great stuff. ?We were experimenting with using the coverage files to
> > >> > generate an ordering for --section-ordering-file, but this might be even
> > >> > better, will have to experiment with it.
> > >> >
> > >> > A couple of comments on the code itself:
> > >> >
> > >> >> Index: function_reordering_plugin/callgraph.h
> > >> >> +inline static Edge_list *
> > >> >> +make_edge_list (Edge *e)
> > >> >> +{
> > >> >> + ?Edge_list *list = (Edge_list *)malloc (sizeof (Edge_list));
> > >> >
> > >> > If you are going to use libiberty via hashtab.h, you might as well make use
> > >> > of the *ALLOC family of macros to make this and other allocations a little
> > >> > neater.
> > >> >
> > >> >> +/*Represents an edge in the call graph. ?*/
> > >> >> +struct __edge__
> > >> >
> > >> > I think the usual convention is to call this edge_d or something similar,
> > >> > avoiding the profusion of underscores.
> > >> >
> > >> >> +void
> > >> >> +map_section_name_to_index (char *section_name, void *handle, int shndx)
> > >> >> +{
> > >> >> + ?void **slot;
> > >> >> + ?char *function_name;
> > >> >> +
> > >> >> + ?if (is_prefix_of (".text.hot.", section_name))
> > >> >> + ? ?function_name = section_name + 10 /* strlen (".text.hot.") */;
> > >> >> + ?else if (is_prefix_of (".text.unlikely.", section_name))
> > >> >> + ? ?function_name = section_name + 15 /* strlen (".text.unlikely.") */;
> > >> >> + ?else if (is_prefix_of (".text.cold.", section_name))
> > >> >> + ? ?function_name = section_name + 11 /* strlen (".text.cold.") */;
> > >> >> + ?else if (is_prefix_of (".text.startup.", section_name))
> > >> >> + ? ?function_name = section_name + 14 /* strlen (".text.startup.") */;
> > >> >> + ?else
> > >> >> + ? ?function_name = section_name + 6 /*strlen (".text.") */;
> > >> >
> > >> > You don't handle plain .text; this is assuming -ffunction-sections, right?
> > >> > ?Can this limitation be easily removed?
> > >>
> > >> You need to compile with -ffunction-sections or the individual
> > >> sections cannot be re-ordered. That is why I assumed a .text.* prefix
> > >> before every function section. Did you have something else in mind?
> > >>
> > >> Thanks for your other comments. I will make those changes.
> > >>
> > >> -Sri.
> > >>
> > >> >
> > >> > I think it is customary to put the comment after the semicolon.
> > >> >
> > >> > Might just be easier to say something like:
> > >> >
> > >> > ?const char *sections[] = { ".text.hot", ... }
> > >> > ?char *function_name = NULL;
> > >> >
> > >> > ?for (i = 0; i < ARRAY_SIZE (sections); i++)
> > >> > ? ?if (is_prefix_of (sections[i], section_name))
> > >> > ? ? ?{
> > >> > ? ? ? ? function_name = section_name + strlen (sections[i]);
> > >> > ? ? ? ? break;
> > >> > ? ? ?}
> > >> >
> > >> > ?if (!function_name)
> > >> > ? ?function_name = section_name + 6; /* strlen (".text.") */
> > >> >
> > >> > I guess that's not much shorter.
> > >> >
> > >> >> +void
> > >> >> +cleanup ()
> > >> >> +{
> > >> >> + ?Node *node;
> > >> >> + ?Edge *edge;
> > >> >> +
> > >> >> + ?/* Free all nodes and edge_lists. ?*/
> > >> >> + ?for (node = node_chain; node != NULL; )
> > >> >> + ? ?{
> > >> >> + ? ? ?Node *next_node = node->next;
> > >> >> + ? ? ?Edge_list *it;
> > >> >> + ? ? ?for (it = node->edge_list; it != NULL; )
> > >> >> + ? ? ? ?{
> > >> >> + ? ? ? ? ?Edge_list *next_it = it->next;
> > >> >> + ? ? ? ? ?free (it);
> > >> >> + ? ? ? ? ?it = next_it;
> > >> >> + ? ? ? ?}
> > >> >
> > >> > Write a free_edge_list function, since you do this once here and twice
> > >> > below.
> > >> >
> > >> > -Nathan
> > >> >
> > >

Attachment: patch_new.txt
Description: Text document