[google] Linker plugin to do function reordering using callgraph edge profiles (issue5124041)
Sriraman Tallam
tmsriram@google.com
Tue Sep 27 01:32:00 GMT 2011
*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
>> >
>
-------------- next part --------------
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)
@@ -0,0 +1,246 @@
+/* Function re-ordering plugin for gold.
+ Copyright (C) 2011 Free Software Foundation, Inc.
+ Contributed by Sriraman Tallam (tmsriram@google.com).
+
+This program 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.
+
+This program 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 this program; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+/* This plugin should be invoked only when callgraph edge profile
+ information is available in the object files generated using the
+ compiler flag -fcallgraph-profiles-sections. The callgraph edge
+ profiles are stored in special sections marked .gnu.callgraph.*
+
+ This plugin reads the callgraph sections and constructs an annotated
+ callgraph. It then repeatedly groups sections that are connected by
+ hot edges and passes the new function layout to the linker. The
+ layout is based on the procedure reordering algorithm described
+ in the paper :
+
+ "Profile guided code positioning", K. Pettis, R. Hansen
+ Proceedings of PLDI 1990.
+
+ This plugin dumps the final layout order of the functions in a file
+ called "final_layout.txt". To change the output file, pass the new
+ file name with --plugin-opt. To dump to stderr instead, just pass
+ stderr to --plugin-opt. */
+
+#if HAVE_STDINT_H
+#include <stdint.h>
+#endif
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include <string.h>
+#include <elf.h>
+#include "config.h"
+#include "plugin-api.h"
+#include "callgraph.h"
+
+enum ld_plugin_status claim_file_hook (const struct ld_plugin_input_file *file,
+ int *claimed);
+enum ld_plugin_status all_symbols_read_hook ();
+
+static ld_plugin_get_input_section_count get_input_section_count = NULL;
+static ld_plugin_get_input_section_type get_input_section_type = NULL;
+static ld_plugin_get_input_section_name get_input_section_name = NULL;
+static ld_plugin_get_input_section_contents get_input_section_contents = NULL;
+static ld_plugin_update_section_order update_section_order = NULL;
+static ld_plugin_allow_section_ordering allow_section_ordering = NULL;
+
+/* The file where the final function order will be stored.
+ It is "./final_layout.txt". It can be changed by passing
+ new name to --plugin-opt */
+
+char *out_file = "./final_layout.txt";
+
+int is_api_exist = 0;
+
+/* Copies new output file name out_file */
+void get_filename (const char *name)
+{
+ if (strcmp (name, "stderr") == 0)
+ {
+ out_file = NULL;
+ return;
+ }
+ out_file = (char *) malloc (strlen (name) + 1);
+ strcpy (out_file, name);
+}
+
+/* Plugin entry point. */
+enum ld_plugin_status
+onload (struct ld_plugin_tv *tv)
+{
+ struct ld_plugin_tv *entry;
+ for (entry = tv; entry->tv_tag != LDPT_NULL; ++entry)
+ {
+ switch (entry->tv_tag)
+ {
+ case LDPT_API_VERSION:
+ break;
+ case LDPT_GOLD_VERSION:
+ break;
+ case LDPT_OPTION:
+ get_filename (entry->tv_u.tv_string);
+ break;
+ case LDPT_REGISTER_CLAIM_FILE_HOOK:
+ assert ((*entry->tv_u.tv_register_claim_file) (claim_file_hook) == LDPS_OK);
+ break;
+ case LDPT_REGISTER_ALL_SYMBOLS_READ_HOOK:
+ assert ((*entry->tv_u.tv_register_all_symbols_read) (all_symbols_read_hook)
+ == LDPS_OK);
+ break;
+ case LDPT_GET_INPUT_SECTION_COUNT:
+ get_input_section_count = *entry->tv_u.tv_get_input_section_count;
+ break;
+ case LDPT_GET_INPUT_SECTION_TYPE:
+ get_input_section_type = *entry->tv_u.tv_get_input_section_type;
+ break;
+ case LDPT_GET_INPUT_SECTION_NAME:
+ get_input_section_name = *entry->tv_u.tv_get_input_section_name;
+ break;
+ case LDPT_GET_INPUT_SECTION_CONTENTS:
+ get_input_section_contents = *entry->tv_u.tv_get_input_section_contents;
+ break;
+ case LDPT_UPDATE_SECTION_ORDER:
+ update_section_order = *entry->tv_u.tv_update_section_order;
+ break;
+ case LDPT_ALLOW_SECTION_ORDERING:
+ allow_section_ordering = *entry->tv_u.tv_allow_section_ordering;
+ break;
+ default:
+ break;
+ }
+ }
+
+ if (get_input_section_count != NULL
+ && get_input_section_type != NULL
+ && get_input_section_name != NULL
+ && get_input_section_contents != NULL
+ && update_section_order != NULL
+ && allow_section_ordering != NULL)
+ is_api_exist = 1;
+
+ return LDPS_OK;
+}
+
+static int is_ordering_specified = 0;
+
+/* This function is called by the linker for every new object it encounters. */
+
+enum ld_plugin_status
+claim_file_hook (const struct ld_plugin_input_file *file, int *claimed)
+{
+ unsigned int count = 0;
+ struct ld_plugin_section section;
+ unsigned int shndx;
+
+ (void) claimed;
+
+ /* Silently return if the plugin APIs are not supported. */
+ if (!is_api_exist)
+ return LDPS_OK;
+
+ if (is_ordering_specified == 0)
+ {
+ /* Inform the linker to prepare for section reordering. */
+ (*allow_section_ordering) ();
+ is_ordering_specified = 1;
+ }
+
+ (*get_input_section_count) (file->handle, &count);
+
+ for (shndx = 0; shndx < count; ++shndx)
+ {
+ unsigned int type = SHT_NULL;
+ char *name = NULL;
+
+ section.handle = file->handle;
+ section.shndx = shndx;
+ (*get_input_section_type) (section, &type);
+
+ (*get_input_section_name) (section, &name);
+ if (type == SHT_PROGBITS && is_prefix_of (".text.", name))
+ {
+ map_section_name_to_index (name, file->handle, shndx);
+ }
+ else if (is_prefix_of (".gnu.callgraph.text", name))
+ {
+ /* Process callgraph sections. */
+ unsigned char *section_contents_ptr = NULL;
+ size_t length;
+ (*get_input_section_contents) (section,
+ (const unsigned char **)§ion_contents_ptr,
+ &length);
+ unsigned char *section_contents;
+ section_contents = (unsigned char *) malloc (length);
+ memcpy (section_contents, section_contents_ptr, length);
+ parse_callgraph_section_contents (section_contents, (unsigned int)length);
+ }
+ else if (name != NULL)
+ free (name);
+ }
+
+ return LDPS_OK;
+}
+
+/* This function is called by the linker after all the symbols have been read.
+ At this stage, it is fine to tell the linker the desired function order. */
+
+enum ld_plugin_status
+all_symbols_read_hook (void)
+{
+ unsigned int num_entries;
+ unsigned int i;
+ struct ld_plugin_section *section_list;
+ void **handles;
+ unsigned int *shndx;
+ FILE *fp;
+
+ /* Silently return if the plugin APIs are not supported. */
+ if (!is_api_exist)
+ return LDPS_OK;
+
+ if (is_callgraph_empty ())
+ return LDPS_OK;
+
+ /* Open the file to write the final layout */
+ if (out_file == NULL)
+ fp = stderr;
+ else
+ fp = fopen (out_file, "w");
+
+ fprintf (fp, "# Remove lines starting with \'#\' to"
+ " pass to --section-ordering-file\n");
+ fprintf (fp, "# Lines starting with \'#\' are the edge profiles\n");
+
+ find_pettis_hansen_function_layout (fp);
+ num_entries = get_layout (fp, &handles, &shndx);
+ section_list = (struct ld_plugin_section *)
+ malloc (num_entries * sizeof (struct ld_plugin_section));
+ for (i = 0; i < num_entries; i++)
+ {
+ section_list[i].handle = handles[i];
+ section_list[i].shndx = shndx[i];
+ }
+
+ /* Pass the new order of functions to the linker. */
+ update_section_order (section_list, num_entries);
+ free (section_list);
+ free (handles);
+ free (shndx);
+ cleanup ();
+ return LDPS_OK;
+}
Index: function_reordering_plugin/callgraph.h
===================================================================
--- function_reordering_plugin/callgraph.h (revision 0)
+++ function_reordering_plugin/callgraph.h (revision 0)
@@ -0,0 +1,272 @@
+/* Callgraph implementation.
+ Copyright (C) 2011 Free Software Foundation, Inc.
+ Contributed by Sriraman Tallam (tmsriram@google.com).
+
+This program 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.
+
+This program 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 this program; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+#ifndef CALLGRAPH_H
+#define CALLGRAPH_H
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include <hashtab.h>
+#include <string.h>
+#include "libiberty.h"
+
+struct edge_d;
+typedef struct edge_d Edge;
+
+/* Maintain a list of edges. */
+typedef struct edge_list_d
+{
+ Edge *edge;
+ struct edge_list_d *next;
+ struct edge_list_d *prev;
+} Edge_list;
+
+inline static Edge_list *
+make_edge_list (Edge *e)
+{
+ Edge_list *list = XNEW (Edge_list);
+ list->edge = e;
+ list->next = NULL;
+ list->prev = NULL;
+ return list;
+}
+
+/* Represents a node in the call graph. */
+typedef struct node_d
+{
+ unsigned int id;
+ char *name;
+ /* Chain all the Nodes created. */
+ struct node_d *next;
+ /* Pointer to the next node in the chain of merged nodes. */
+ struct node_d *merge_next;
+ /* List of all edges with this node. */
+ Edge_list *edge_list;
+ /* Pointer to the last node in the chain of merged nodes. */
+ struct node_d *last_merge_node;
+ unsigned int is_merged;
+ /* 1 if the function corresponding to this node can be re-ordered. */
+ unsigned int is_real_node;
+} Node;
+
+inline static Node *
+make_node (unsigned int id, char *name)
+{
+ Node *node = XNEW (Node);
+ node->id = id;
+ node->name = name;
+ node->is_real_node = 0;
+ node->next = NULL;
+ node->edge_list = NULL;
+ node->last_merge_node = node;
+ node->is_merged = 0;
+ node->merge_next = NULL;
+ return node;
+}
+
+/* Chain the nodes that are merged. Maintain a pointer to the last
+ node in the chain. After merging at the end, the last node in the
+ current chain is the last node in the chain of the merged node. */
+inline static void
+merge_node (Node *merger, Node *mergee)
+{
+ merger->last_merge_node->merge_next = mergee;
+ merger->last_merge_node = mergee->last_merge_node;
+ mergee->is_merged = 1;
+}
+
+inline static void
+add_edge_to_node (Node *n, Edge *e)
+{
+ Edge_list *list;
+ assert (n != NULL && e != NULL);
+ list = make_edge_list (e);
+ list->next = n->edge_list;
+ if (n->edge_list != NULL)
+ n->edge_list->prev = list;
+ n->edge_list = list;
+}
+
+/* A node is real only if the function can be reordered. */
+inline static void
+set_as_real_node (Node *node)
+{
+ node->is_real_node = 1;
+}
+
+/* WEAK if one of the nodes is not real. STRONG if both
+ nodes are real. */
+typedef enum edge_type_
+{
+ STRONG_EDGE = 0,
+ WEAK_EDGE
+} Edge_type;
+
+/*Represents an edge in the call graph. */
+struct edge_d
+{
+ Node *first_function;
+ Node *second_function;
+ unsigned int weight;
+ Edge_type type;
+ /* 1 if the nodes corresponding to this edge have been merged. */
+ unsigned int is_merged;
+ /* Doubly linked chain of created edges. */
+ struct edge_d *prev;
+ struct edge_d *next;
+};
+
+inline static Edge *
+make_edge (Node *first, Node *second, unsigned int weight)
+{
+ Edge *edge = XNEW (Edge);
+ edge->first_function = first;
+ edge->second_function = second;
+ edge->weight = weight;
+ edge->type = WEAK_EDGE;
+ edge->is_merged = 0;
+ edge->prev = NULL;
+ edge->next = NULL;
+ add_edge_to_node (first, edge);
+ add_edge_to_node (second, edge);
+ return edge;
+}
+
+/* Frees the chain of edges. */
+inline static void
+free_edge_chain (Edge *edge_chain)
+{
+ Edge *edge;
+
+ for (edge = edge_chain; edge != NULL; )
+ {
+ Edge *next_edge = edge->next;
+ free (edge);
+ edge = next_edge;
+ }
+}
+
+inline static void
+set_edge_type (Edge *edge)
+{
+ if (edge->first_function->is_real_node
+ && edge->second_function->is_real_node)
+ edge->type = STRONG_EDGE;
+ else
+ edge->type = WEAK_EDGE;
+}
+
+inline static unsigned int
+edge_lower (Edge *e1, Edge *e2)
+{
+ if (e1->type == e2->type)
+ return (e1->weight < e2->weight) ? 1 : 0;
+ if (e1->type == STRONG_EDGE)
+ return 0;
+ return 1;
+}
+
+inline static void
+reset_functions (Edge *e, Node *n1, Node *n2)
+{
+ /* No self edges. */
+ assert (n1->id != n2->id);
+ if (n1->id < n2->id)
+ {
+ e->first_function = n1;
+ e->second_function = n2;
+ }
+ else
+ {
+ e->first_function = n2;
+ e->second_function = n1;
+ }
+}
+
+/* A Section is represented by its object handle and the section index. */
+typedef struct
+{
+ /* Name of the function. */
+ char *name;
+ /* Full name of the section. */
+ char *full_name;
+ void *handle;
+ int shndx;
+} Section_id;
+
+inline static Section_id *
+make_section_id (char *name, char *full_name, void *handle, int shndx)
+{
+ Section_id *s = XNEW (Section_id);
+ s->name = name;
+ s->full_name = full_name;
+ s->handle = handle;
+ s->shndx = shndx;
+
+ return s;
+}
+
+/* A pair of nodes make a raw edge. Also, N1->id < N2->id. */
+typedef struct
+{
+ Node *n1;
+ Node *n2;
+} Raw_edge;
+
+inline static void
+init_raw_edge (Raw_edge *r, Node *n1, Node *n2)
+{
+ assert (n1 ->id != n2->id);
+ if (n1->id < n2->id)
+ {
+ r->n1 = n1;
+ r->n2 = n2;
+ }
+ else
+ {
+ r->n1 = n2;
+ r->n2 = n1;
+ }
+}
+
+inline static int is_prefix_of (const char *prefix, const char *str)
+{
+ return strncmp (prefix, str, strlen (prefix)) == 0;
+}
+
+/* Maps the function corresponding to section name to its
+ corresponding object handle and the section index. */
+void
+map_section_name_to_index (char *section_name, void *handle, int shndx);
+
+void
+parse_callgraph_section_contents (unsigned char *section_contents,
+ unsigned int length);
+
+void dump_functions ();
+void dump_edges ();
+void find_pettis_hansen_function_layout (FILE *fp);
+
+unsigned int get_layout (FILE *fp, void*** handles,
+ unsigned int** shndx);
+
+void cleanup ();
+/* Returns 1 if callgraph is empty. */
+unsigned int is_callgraph_empty ();
+#endif
Index: function_reordering_plugin/callgraph.c
===================================================================
--- function_reordering_plugin/callgraph.c (revision 0)
+++ function_reordering_plugin/callgraph.c (revision 0)
@@ -0,0 +1,598 @@
+/* Callgraph implementation.
+ Copyright (C) 2011 Free Software Foundation, Inc.
+ Contributed by Sriraman Tallam (tmsriram@google.com).
+
+This program 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.
+
+This program 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 this program; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+#include "callgraph.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include <string.h>
+#include <hashtab.h>
+
+/*****************************************************************************/
+/* section_map hashtable definition and helpers. */
+
+/* Maps section name to its corresponding object handle and section index. */
+static htab_t section_map = NULL;
+
+/* Hashtable helper for section_map htab. */
+static hashval_t
+section_map_htab_hash_descriptor (const void *p)
+{
+ const Section_id *s = (const Section_id *)p;
+ const char *name = s->name;
+ return htab_hash_string(name);
+}
+
+/* Hashtable helper for section_map htab. */
+static int
+section_map_htab_eq_descriptor (const void *p1, const void *p2)
+{
+ const Section_id *s1 = (const Section_id *)p1;
+ const char *c1 = s1->name;
+ const char *c2 = (const char *)p2;
+
+ return (strcmp (c1, c2) == 0);
+}
+/*****************************************************************************/
+
+
+/*****************************************************************************/
+/* function_map hashtable definition and helpers.
+ Maps function name to a unique Node. */
+static htab_t function_map = NULL;
+static unsigned int last_function_id = 0;
+
+/* Hashtable helper for function_map htab. */
+static hashval_t
+function_map_htab_hash_descriptor (const void *p)
+{
+ const Node *s = (const Node *)p;
+ const char *name = s->name;
+ return htab_hash_string(name);
+}
+
+/* Hashtable helper for section_map htab. */
+static int
+function_map_htab_eq_descriptor (const void *p1, const void *p2)
+{
+ const Node *s1 = (const Node *)p1;
+ const char *c1 = s1->name;
+ const char *c2 = (const char *)p2;
+
+ return (strcmp (c1, c2) == 0);
+}
+/*****************************************************************************/
+
+/*****************************************************************************/
+/* edge_map hashtable definition and helpers.
+ Maps two node ids to a unique edge. */
+static htab_t edge_map = NULL;
+
+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;
+}
+
+/* Hashtable helper for edge_map htab. */
+static hashval_t
+edge_map_htab_hash_descriptor (const void *p)
+{
+ Edge *e = (Edge *) p;
+ return edge_hash_function (e->first_function->id, e->second_function->id);
+}
+
+/* Hashtable helper for edge_map htab. */
+static int
+edge_map_htab_eq_descriptor (const void *p1, const void *p2)
+{
+ Edge *e1 = (Edge *) p1;
+ Raw_edge *r1 = (Raw_edge *) p2;
+ return ((e1->first_function->id == r1->n1->id)
+ && (e1->second_function->id == r1->n2->id));
+}
+
+
+/*****************************************************************************/
+
+/* Chain of all the created nodes. */
+Node *node_chain = NULL;
+/* Number of nodes that correspond to functions which will be reordered. */
+unsigned int num_real_nodes = 0;
+/* Chain of all edges in the merged callgraph. */
+Edge *active_edges = NULL;
+/* Chain of all the merged edges. */
+Edge *inactive_edges = NULL;
+
+/* Reads off the next string from the char stream CONTENTS and updates
+ READ_LENGTH to the length of the string read. The value of CONTENTS
+ is updated to start at the next string. */
+
+static char *
+get_next_string (char **contents, unsigned int *read_length)
+{
+ char *s = *contents;
+ *read_length = strlen (*contents) + 1;
+ *contents += *read_length;
+ return s;
+}
+
+/* Add an EDGE to the list of edges in the call graph. */
+
+static void
+add_edge_to_list (Edge *edge)
+{
+ assert (edge != NULL);
+ edge->next = active_edges;
+ if (active_edges != NULL)
+ active_edges->prev = edge;
+ active_edges = edge;
+}
+
+/* Remove the edge from the list of edges in the call graph. This is done
+ when the nodes corresponding to this edge are merged. */
+
+static void
+remove_edge_from_list (Edge * curr_edge)
+{
+ assert (curr_edge != NULL);
+ if (curr_edge->prev != NULL)
+ curr_edge->prev->next = curr_edge->next;
+ if (curr_edge->next != NULL)
+ curr_edge->next->prev = curr_edge->prev;
+ if (active_edges == curr_edge)
+ active_edges = curr_edge->next;
+ curr_edge->next = NULL;
+ curr_edge->prev = NULL;
+
+ /* Add to inactive edges to be freed later. */
+ curr_edge->next = inactive_edges;
+ inactive_edges = curr_edge;
+ return;
+}
+
+/* Adds the WEIGHT value to the edge count of CALLER and CALLEE. */
+
+static void
+update_edge (Node *n1, Node *n2, unsigned int weight)
+{
+ void **slot;
+ Raw_edge re, *r;
+ Edge *e;
+
+ if (n1->id == n2->id)
+ return;
+ if (weight == 0)
+ return;
+
+ if (edge_map == NULL)
+ {
+ edge_map = htab_create (25, edge_map_htab_hash_descriptor,
+ edge_map_htab_eq_descriptor , NULL);
+ assert (edge_map != NULL);
+ }
+
+ r = &re;
+ init_raw_edge (r, n1, n2);
+ slot = htab_find_slot_with_hash (edge_map, r,
+ edge_hash_function (r->n1->id, r->n2->id),
+ INSERT);
+ if (*slot == NULL)
+ {
+ e = make_edge (r->n1, r->n2, weight);
+ *slot = e;
+ add_edge_to_list (e);
+ }
+ else
+ {
+ e = *slot;
+ e->weight += weight;
+ }
+}
+
+/* Create a unique node for a function. */
+
+static Node *
+get_function_node (char *name)
+{
+ void **slot = NULL;
+ Node *node;
+
+ if (function_map == NULL)
+ {
+ function_map = htab_create (25, function_map_htab_hash_descriptor,
+ function_map_htab_eq_descriptor , NULL);
+ assert (function_map != NULL);
+ }
+
+ slot = htab_find_slot_with_hash (function_map, name, htab_hash_string (name),
+ INSERT);
+
+ if (*slot == NULL)
+ {
+ node = make_node (last_function_id, name);
+ /* Chain the node to the node_chain. */
+ node->next = node_chain;
+ node_chain = node;
+ *slot = node;
+ last_function_id++;
+ }
+ else
+ {
+ node = (Node *)*slot;
+ }
+ return node;
+}
+
+/* Dumper funcction to print the list of functions that will be considered for
+ re-ordering. */
+
+void
+dump_functions ()
+{
+ Node *node = node_chain;
+ while (node)
+ {
+ if (node->is_real_node)
+ fprintf (stderr, "Dumping function %s\n", node->name);
+ node = node->next;
+ }
+}
+
+/* Dump all the edges existing in the callgraph. */
+
+void dump_edges (FILE *fp)
+{
+ Edge *it;
+ for (it = active_edges;
+ it != NULL;
+ it = it->next)
+ {
+ fprintf (fp,"# %s ---- (%u)---- %s\n",
+ it->first_function->name,
+ it->weight,
+ it->second_function->name);
+ }
+}
+
+/* HEADER_LEN is the length of string 'Function '. */
+const int HEADER_LEN = 9;
+
+/* Parse the section contents of ".gnu.callgraph.text" sections and create
+ call graph edges with appropriate weights. The section contents have the
+ following format :
+ Function <caller_name>
+ <callee_1>
+ <edge count between caller and callee_1>
+ <callee_2>
+ <edge count between caller and callee_2>
+ .... */
+void
+parse_callgraph_section_contents (unsigned char *section_contents,
+ unsigned int length)
+{
+ char *contents;
+ char *caller;
+ unsigned int read_length = 0, curr_length = 0;
+ Node *caller_node;
+
+ /* First string in contents is 'Function <function-name>'. */
+ assert (length > 0);
+ contents = (char*) (section_contents);
+ caller = get_next_string (&contents, &read_length);
+ assert (read_length > HEADER_LEN);
+ caller = caller + HEADER_LEN;
+ curr_length = read_length;
+ 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);
+ num_real_nodes++;
+
+ while (curr_length < length)
+ {
+ /* Read callee, weight tuples. */
+ char *callee;
+ char *weight_str;
+ unsigned int weight;
+ Node *callee_node;
+
+ callee = get_next_string (&contents, &read_length);
+ curr_length += read_length;
+ callee_node = get_function_node (callee);
+
+ assert (curr_length < length);
+ weight_str = get_next_string (&contents, &read_length);
+ weight = atoi (weight_str);
+ curr_length += read_length;
+ update_edge (caller_node, callee_node, weight);
+ }
+}
+
+/* Traverse the list of edges and find the edge with the maximum weight. */
+
+static Edge *
+find_max_edge ()
+{
+ Edge *it, *max_edge;
+
+ if (active_edges == NULL)
+ return NULL;
+
+ max_edge = active_edges;
+ assert (!active_edges->is_merged);
+
+ it = active_edges->next;
+ for (;it != NULL; it = it->next)
+ {
+ assert (!it->is_merged);
+ if (edge_lower (max_edge , it))
+ max_edge = it;
+ }
+
+ return max_edge;
+}
+
+/* Change the EDGE from OLD_NODE to KEPT_NODE to be between NEW_NODE
+ and KEPT_NODE. */
+
+static void
+merge_edge (Edge *edge, Node *new_node, Node *old_node,
+ Node *kept_node)
+{
+ void **slot;
+ Raw_edge re, *r;
+
+ r = &re;
+ init_raw_edge (r, new_node, kept_node);
+ slot = htab_find_slot_with_hash (edge_map, r,
+ edge_hash_function (r->n1->id, r->n2->id),
+ INSERT);
+
+ if (*slot == NULL)
+ {
+ reset_functions (edge, new_node, kept_node);
+ *slot = edge;
+ add_edge_to_node (new_node, edge);
+ }
+ else
+ {
+ Edge *new_edge = *slot;
+ new_edge->weight += edge->weight;
+ edge->is_merged = 1;
+ remove_edge_from_list (edge);
+ }
+}
+
+/* Merge the two nodes in this EDGE. The new node's edges are the union of
+ the edges of the original nodes. */
+
+static void
+collapse_edge (Edge * edge)
+{
+ Edge_list *it;
+ Node *kept_node = edge->first_function;
+ Node *merged_node = edge->second_function;
+
+ /* Go through all merged_node edges and merge with kept_node. */
+ for (it = merged_node->edge_list; it != NULL; it = it->next)
+ {
+ Node *other_node = NULL;
+ Edge *this_edge = it->edge;
+ if (this_edge->is_merged)
+ continue;
+ if (this_edge == edge)
+ continue;
+ assert (this_edge->first_function->id == merged_node->id
+ || this_edge->second_function->id == merged_node->id);
+ other_node = (this_edge->first_function->id
+ == merged_node->id)
+ ? this_edge->second_function
+ : this_edge->first_function;
+ merge_edge (this_edge, kept_node, merged_node, other_node);
+ }
+
+ merge_node (kept_node, merged_node);
+ edge->is_merged = 1;
+ remove_edge_from_list (edge);
+}
+
+/* Make node N a real node if it can be reordered, that is, its .text
+ section is available. */
+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);
+ if (*slot != NULL)
+ set_as_real_node (n);
+}
+
+void
+find_pettis_hansen_function_layout (FILE *fp)
+{
+ Node *n_it;
+ Edge *it;
+
+ assert (node_chain != NULL);
+ assert (active_edges != NULL);
+ assert (fp != NULL);
+
+ dump_edges (fp);
+
+ /* Go over all the nodes and set it as real node only if a corresponding
+ function section exists. */
+ for (n_it = node_chain; n_it != NULL; n_it = n_it->next)
+ set_node_type (n_it);
+
+ /* Set edge types. A WEAK_EDGE has one of its nodes corresponding to a
+ function that cannot be re-ordered. */
+ for (it = active_edges; it != NULL; it = it->next)
+ set_edge_type (it);
+
+ it = find_max_edge ();
+ while (it != NULL)
+ {
+ collapse_edge (it);
+ it = find_max_edge ();
+ }
+}
+
+/* Maps the function name corresponding to section SECTION_NAME to the
+ object handle and the section index. */
+
+void
+map_section_name_to_index (char *section_name, void *handle, int shndx)
+{
+ void **slot;
+ const char *sections[] = {".text.hot.",
+ ".text.unlikely.",
+ ".text.cold.",
+ ".text.startup.",
+ ".text." };
+ char *function_name = NULL;
+ int i;
+
+ for (i = 0; i < ARRAY_SIZE (sections); ++i)
+ {
+ if (is_prefix_of (sections[i], section_name))
+ {
+ function_name = section_name + strlen (sections[i]);
+ break;
+ }
+ }
+ assert (function_name != NULL);
+
+ /* Allocate section_map. */
+ if (section_map == NULL)
+ {
+ section_map = htab_create (10, section_map_htab_hash_descriptor,
+ section_map_htab_eq_descriptor , NULL);
+ assert (section_map != NULL);
+ }
+
+ slot = htab_find_slot_with_hash (section_map, function_name,
+ htab_hash_string (function_name),
+ INSERT);
+ if (*slot == NULL)
+ *slot = make_section_id (function_name, section_name, handle, shndx);
+}
+
+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);
+ if (*slot != NULL)
+ {
+ Section_id *s = (Section_id *)*slot;
+ handles[position] = s->handle;
+ shndx[position] = s->shndx;
+ fprintf (fp, "%s\n", s->full_name);
+ }
+}
+
+/* Visit each node and print the chain of merged nodes to the file. */
+
+unsigned int
+get_layout (FILE *fp, void*** handles,
+ unsigned int** shndx)
+{
+ Node *it;
+ int position = 0;
+
+ assert (fp != NULL);
+
+ *handles = XNEWVEC (void *, num_real_nodes);
+ *shndx = XNEWVEC (unsigned int, num_real_nodes);
+
+ /* Dump edges to the final reordering file. */
+
+ for (it = node_chain; it != NULL; it = it->next)
+ {
+ Node *node;
+ if (it->is_merged)
+ continue;
+ if (it->is_real_node)
+ {
+ write_out_node (fp, it->name, *handles, *shndx, position);
+ position++;
+ }
+ node = it->merge_next;
+ while (node != NULL)
+ {
+ if (node->is_real_node)
+ {
+ write_out_node (fp, node->name, *handles, *shndx, position);
+ position++;
+ }
+ node = node->merge_next;
+ }
+ }
+ fclose (fp);
+ return position;
+}
+
+/* Free all heap objects. */
+
+void
+cleanup ()
+{
+ Node *node;
+
+ /* 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;
+ }
+ free (node);
+ node = next_node;
+ }
+
+ /* Free all active_edges. */
+ free_edge_chain (active_edges);
+
+ /* Free all inactive edges. */
+ free_edge_chain (inactive_edges);
+
+ /* Delete all htabs. */
+ htab_delete (section_map);
+ htab_delete (function_map);
+ htab_delete (edge_map);
+}
+
+/* Check if the callgraph is empty. */
+unsigned int
+is_callgraph_empty ()
+{
+ if (active_edges == NULL)
+ return 1;
+ return 0;
+}
More information about the Gcc-patches
mailing list