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

login
register
mail settings
Submitter Sriraman Tallam
Date Sept. 27, 2011, 12:22 a.m.
Message ID <CAAs8HmymLTifDZ7h8pg-Pu=3m_jUkM+Qw+=qTEiOJ6nu0X3L7Q@mail.gmail.com>
Download mbox | patch
Permalink /patch/116524/
State New
Headers show

Comments

Sriraman Tallam - Sept. 27, 2011, 12:22 a.m.
*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
>> >
>
Easwaran Raman - Sept. 27, 2011, 6:26 p.m.
+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

+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
> >> >
> >

Patch

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 **)&section_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;
+}