===================================================================
@@ -1,6 +1,7 @@
/* Callgraph implementation.
Copyright (C) 2011 Free Software Foundation, Inc.
- Contributed by Sriraman Tallam (tmsriram@google.com).
+ Contributed by Sriraman Tallam (tmsriram@google.com)
+ and Easwaran Raman (eraman@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
@@ -26,6 +27,9 @@ along with this program; see the file COPYING3. I
#include <string.h>
#include "libiberty.h"
+/* Push a pointer that should be freed after the plugin is done. */
+void push_mm_ptr (void *ptr);
+
struct edge_d;
typedef struct edge_d Edge;
@@ -41,6 +45,7 @@ inline static Edge_list *
make_edge_list (Edge *e)
{
Edge_list *list = XNEW (Edge_list);
+ push_mm_ptr (list);
list->edge = e;
list->next = NULL;
list->prev = NULL;
@@ -69,6 +74,7 @@ inline static Node *
make_node (unsigned int id, char *name)
{
Node *node = XNEW (Node);
+ push_mm_ptr (node);
node->id = id;
node->name = name;
node->is_real_node = 0;
@@ -86,9 +92,9 @@ make_node (unsigned int id, char *name)
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;
+ merger->last_merge_node->merge_next = mergee;
+ merger->last_merge_node = mergee->last_merge_node;
+ mergee->is_merged = 1;
}
inline static void
@@ -136,6 +142,7 @@ inline static Edge *
make_edge (Node *first, Node *second, unsigned int weight)
{
Edge *edge = XNEW (Edge);
+ push_mm_ptr (edge);
edge->first_function = first;
edge->second_function = second;
edge->weight = weight;
@@ -148,21 +155,7 @@ make_edge (Node *first, Node *second, unsigned int
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
@@ -200,7 +193,7 @@ reset_functions (Edge *e, Node *n1, Node *n2)
}
/* A Section is represented by its object handle and the section index. */
-typedef struct
+typedef struct section_id_
{
/* Name of the function. */
char *name;
@@ -208,16 +201,34 @@ reset_functions (Edge *e, Node *n1, Node *n2)
char *full_name;
void *handle;
int shndx;
+ /* Type of prefix in section name. */
+ int section_type;
+ /* Pointer to the next section in the same comdat_group. */
+ struct section_id_ *comdat_group;
+ /* Chain all the sections created. */
+ struct section_id_ *next;
+ /* Used for grouping sections. */
+ struct section_id_ *group;
+ /* Check if this section has been considered for output. */
+ char processed;
} Section_id;
inline static Section_id *
-make_section_id (char *name, char *full_name, void *handle, int shndx)
+make_section_id (char *name, char *full_name,
+ int section_type,
+ void *handle, int shndx)
{
Section_id *s = XNEW (Section_id);
+ push_mm_ptr (s);
s->name = name;
s->full_name = full_name;
+ s->section_type = section_type;
s->handle = handle;
s->shndx = shndx;
+ s->comdat_group = NULL;
+ s->next = NULL;
+ s->group = NULL;
+ s->processed = 0;
return s;
}
@@ -256,8 +267,9 @@ 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);
+parse_callgraph_section_contents (void *handle,
+ unsigned char *section_contents,
+ unsigned int length);
void dump_functions ();
void dump_edges ();
===================================================================
@@ -1,6 +1,7 @@
/* Function re-ordering plugin for gold.
Copyright (C) 2011 Free Software Foundation, Inc.
- Contributed by Sriraman Tallam (tmsriram@google.com).
+ Contributed by Sriraman Tallam (tmsriram@google.com)
+ and Easwaran Raman (eraman@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
@@ -89,6 +90,7 @@ static int no_op = 0;
void get_filename (const char *name)
{
out_file = (char *) malloc (strlen (name) + 1);
+ push_mm_ptr (out_file);
strcpy (out_file, name);
}
@@ -230,6 +232,7 @@ claim_file_hook (const struct ld_plugin_input_file
(*get_input_section_type) (section, &type);
(*get_input_section_name) (section, &name);
+ push_mm_ptr (name);
if (type == SHT_PROGBITS && is_prefix_of (".text.", name))
{
map_section_name_to_index (name, file->handle, shndx);
@@ -244,11 +247,12 @@ claim_file_hook (const struct ld_plugin_input_file
&length);
unsigned char *section_contents;
section_contents = (unsigned char *) malloc (length);
+ push_mm_ptr (section_contents);
memcpy (section_contents, section_contents_ptr, length);
- parse_callgraph_section_contents (section_contents, (unsigned int)length);
+ parse_callgraph_section_contents (file->handle,
+ section_contents,
+ (unsigned int)length);
}
- else if (name != NULL)
- free (name);
}
return LDPS_OK;
@@ -290,6 +294,8 @@ all_symbols_read_hook (void)
num_entries = get_layout (fp, &handles, &shndx);
section_list = (struct ld_plugin_section *)
malloc (num_entries * sizeof (struct ld_plugin_section));
+ push_mm_ptr (section_list);
+
for (i = 0; i < num_entries; i++)
{
section_list[i].handle = handles[i];
@@ -301,9 +307,6 @@ all_symbols_read_hook (void)
fclose (fp);
/* 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;
}
===================================================================
@@ -1,6 +1,7 @@
/* Callgraph implementation.
Copyright (C) 2011 Free Software Foundation, Inc.
- Contributed by Sriraman Tallam (tmsriram@google.com).
+ Contributed by Sriraman Tallam (tmsriram@google.com)
+ and Easwaran Raman (eraman@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
@@ -110,6 +111,25 @@ edge_map_htab_eq_descriptor (const void *p1, const
/*****************************************************************************/
+
+/* Keep track of all allocated memory. */
+typedef struct
+{
+ void *ptr;
+ void *next;
+} mm_node;
+
+mm_node *mm_node_chain = NULL;
+
+void
+push_mm_ptr (void *ptr)
+{
+ mm_node *node = XNEW (mm_node);
+ node->ptr = ptr;
+ node->next = mm_node_chain;
+ mm_node_chain = node;
+}
+
/* Chain of all the created nodes. */
Node *node_chain = NULL;
/* Number of nodes that correspond to functions which will be reordered. */
@@ -275,9 +295,26 @@ void dump_edges (FILE *fp)
}
}
-/* HEADER_LEN is the length of string 'Function '. */
-const int HEADER_LEN = 9;
+/* For file local functions, append a unique identifier corresponding to
+ the file, FILE_HANDLE, to the NAME to keep the name unique. */
+static char *
+canonicalize_function_name (void *file_handle, char *name)
+{
+ /* Number of hexadecimal digits in file_handle, plus length of "0x". */
+ const int FILE_HANDLE_LEN = sizeof (void *) * 2 + 2;
+ char *canonical_name;
+
+ /* File local functions have _ZL prefix in the mangled name. */
+ if (!is_prefix_of ("_ZL", name))
+ return name;
+
+ canonical_name = (char *) malloc (strlen(name) + FILE_HANDLE_LEN + 2);
+ push_mm_ptr (canonical_name);
+ sprintf (canonical_name, "%s.%p", name, file_handle);
+ return canonical_name;
+}
+
/* Parse the section contents of ".gnu.callgraph.text" sections and create
call graph edges with appropriate weights. The section contents have the
following format :
@@ -288,7 +325,8 @@ void dump_edges (FILE *fp)
<edge count between caller and callee_2>
.... */
void
-parse_callgraph_section_contents (unsigned char *section_contents,
+parse_callgraph_section_contents (void *file_handle,
+ unsigned char *section_contents,
unsigned int length)
{
char *contents;
@@ -296,12 +334,15 @@ void
unsigned int read_length = 0, curr_length = 0;
Node *caller_node;
+ /* HEADER_LEN is the length of string 'Function '. */
+ const int HEADER_LEN = 9;
+
/* 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;
+ caller = canonicalize_function_name (file_handle, caller + HEADER_LEN);
curr_length = read_length;
caller_node = get_function_node (caller);
@@ -314,6 +355,7 @@ void
Node *callee_node;
callee = get_next_string (&contents, &read_length);
+ callee = canonicalize_function_name (file_handle, callee);
curr_length += read_length;
callee_node = get_function_node (callee);
@@ -456,6 +498,20 @@ find_pettis_hansen_function_layout (FILE *fp)
}
}
+/* The list of sections created, excluding comdat duplicates. */
+Section_id *first_section = NULL;
+/* The number of sections. */
+int num_sections = 0;
+
+const int NUM_SECTION_TYPES = 5;
+const char *section_types[] = {".text.hot.",
+ ".text.cold.",
+ ".text.unlikely.",
+ ".text.startup.",
+ ".text." };
+
+const int section_priority[] = {0, 3, 4, 2, 1};
+
/* Maps the function name corresponding to section SECTION_NAME to the
object handle and the section index. */
@@ -463,24 +519,23 @@ 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;
+ int i, section_type = -1;
- for (i = 0; i < ARRAY_SIZE (sections); ++i)
+ for (i = 0; i < ARRAY_SIZE (section_types); ++i)
{
- if (is_prefix_of (sections[i], section_name))
+ if (is_prefix_of (section_types[i], section_name))
{
- function_name = section_name + strlen (sections[i]);
+ function_name = section_name + strlen (section_types[i]);
+ section_type = i;
break;
}
}
- assert (function_name != NULL);
+ assert (function_name != NULL && section_type >= 0);
+ function_name = canonicalize_function_name (handle, function_name);
+ num_sections++;
+
/* Allocate section_map. */
if (section_map == NULL)
{
@@ -494,24 +549,67 @@ map_section_name_to_index (char *section_name, voi
htab_hash_string (function_name),
INSERT);
if (*slot == NULL)
- *slot = make_section_id (function_name, section_name, handle, shndx);
+ {
+ Section_id *section = make_section_id (function_name, section_name,
+ section_type, handle, shndx);
+ /* Chain it to the list of sections. */
+ section->next = first_section;
+ first_section = section;
+ *slot = section;
+ }
+ else
+ {
+ /* The function already exists, it must be a COMDAT. Only one section
+ in the comdat group will be kept, we don't know which. Chain all the
+ comdat sections in the same comdat group to be emitted together later.
+ Keep one section as representative (kept) and update its section_type
+ to be equal to the type of the highest priority section in the
+ group. */
+ Section_id *kept = (Section_id *)(*slot);
+ Section_id *section = make_section_id (function_name, section_name,
+ section_type, handle, shndx);
+ if (section_priority[kept->section_type]
+ > section_priority[section_type])
+ kept->section_type = section_type;
+
+ section->comdat_group = kept->comdat_group;
+ kept->comdat_group = section;
+ }
}
+/* Find the section corresponding to function name NAME. If it is a comdat,
+ get all the comdat sections in the group. Chain these sections to
+ SECTION_END. Set SECTION_START if it is NULL. */
+
static void
-write_out_node (FILE *fp, char *name,
- void **handles, unsigned int *shndx, int position)
+write_out_node (char *name, Section_id **section_start,
+ Section_id **section_end)
{
void *slot;
slot = htab_find_with_hash (section_map, name, htab_hash_string (name));
if (slot != NULL)
{
Section_id *s = (Section_id *)slot;
- handles[position] = s->handle;
- shndx[position] = s->shndx;
- if (fp != NULL)
- fprintf (fp, "%s\n", s->full_name);
- /* No more use of full_name */
- free (s->full_name);
+ s->processed = 1;
+ if (*section_start == NULL)
+ {
+ *section_start = s;
+ *section_end = s;
+ }
+ else
+ {
+ (*section_end)->group = s;
+ *section_end = s;
+ }
+
+ /* Print all other sections in the same comdat group. */
+ while (s->comdat_group)
+ {
+ s = s->comdat_group;
+ s->processed = 1;
+ (*section_end)->group = s;
+ *section_end = s;
+ }
}
}
@@ -521,67 +619,95 @@ unsigned int
get_layout (FILE *fp, void*** handles,
unsigned int** shndx)
{
- Node *it;
- int position = 0;
+ Node *n_it;
+ int i = 0;
+ int position;
+ /* Form NUM_SECTION_TYPES + 1 groups of sections. Index 0 corresponds
+ to the list of sections that correspond to functions in the callgraph.
+ For other sections, they are grouped by section_type and stored in
+ index: (section_type + 1). SECTION_START points to the first
+ section in each section group and SECTION_END points to the last. */
+ Section_id *section_start[NUM_SECTION_TYPES + 1];
+ Section_id *section_end[NUM_SECTION_TYPES + 1];
+ Section_id *s_it;
- *handles = XNEWVEC (void *, num_real_nodes);
- *shndx = XNEWVEC (unsigned int, num_real_nodes);
+ *handles = XNEWVEC (void *, num_sections);
+ *shndx = XNEWVEC (unsigned int, num_sections);
- /* Dump edges to the final reordering file. */
+ push_mm_ptr (*handles);
+ push_mm_ptr (*shndx);
- for (it = node_chain; it != NULL; it = it->next)
+ for (i = 0; i < NUM_SECTION_TYPES + 1; i++)
{
+ section_start[i] = NULL;
+ section_end[i] = NULL;
+ }
+
+ /* Dump edges to the final reordering file. */
+ for (n_it = node_chain; n_it != NULL; n_it = n_it->next)
+ {
Node *node;
- if (it->is_merged)
+ /* First, only consider nodes that are real and that have other
+ nodes merged with it. */
+ if (n_it->is_merged || !n_it->is_real_node || !n_it->merge_next)
continue;
- if (it->is_real_node)
- {
- write_out_node (fp, it->name, *handles, *shndx, position);
- position++;
- }
- node = it->merge_next;
+
+ write_out_node (n_it->name, §ion_start[0], §ion_end[0]);
+ node = n_it->merge_next;
while (node != NULL)
{
if (node->is_real_node)
- {
- write_out_node (fp, node->name, *handles, *shndx, position);
- position++;
- }
+ write_out_node (node->name, §ion_start[0], §ion_end[0]);
node = node->merge_next;
}
}
+
+ /* Go through all the sections and sort unprocessed sections into different
+ section_type groups. */
+ s_it = first_section;
+ while (s_it)
+ {
+ if (!s_it->processed)
+ {
+ write_out_node (s_it->name, §ion_start[s_it->section_type + 1],
+ §ion_end[s_it->section_type + 1]);
+ s_it->processed = 1;
+ }
+ s_it = s_it->next;
+ }
+
+
+ position = 0;
+ for (i=0; i < NUM_SECTION_TYPES + 1; i++)
+ {
+ s_it = section_start[i];
+ while (s_it)
+ {
+ assert (position < num_sections);
+ (*handles)[position] = s_it->handle;
+ (*shndx)[position] = s_it->shndx;
+ position++;
+ if (fp != NULL)
+ fprintf (fp, "%s\n", s_it->full_name);
+ s_it = s_it->group;
+ }
+ }
return position;
}
-/* Free all heap objects. */
-
void
cleanup ()
{
- Node *node;
-
- /* Free all nodes and edge_lists. */
- for (node = node_chain; node != NULL; )
+ /* Go through heap allocated objects and free them. */
+ while (mm_node_chain)
{
- 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;
- }
+ mm_node *node = mm_node_chain;
+ free (node->ptr);
+ mm_node_chain = node->next;
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. */
+ /* Delete all htabs. */
htab_delete (section_map);
htab_delete (function_map);
htab_delete (edge_map);