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

login
register
mail settings
Submitter Sriraman Tallam
Date Sept. 23, 2011, 10:03 p.m.
Message ID <20110923220316.0F03FB2195@azwildcat.mtv.corp.google.com>
Download mbox | patch
Permalink /patch/116181/
State New
Headers show

Comments

Sriraman Tallam - Sept. 23, 2011, 10:03 p.m.
This patch adds a new linker plugin to re-order functions.  The plugin constructs an annotated callgraph with edge profile information and then repeatedly groups sections that are connected by  hot edges and passes the new function layout to the linker.  The grouping is done similar to the Pettis Hansen procedure ordering scheme. 

I had earlier reverted a patch for a plugin that was written in C++. I have re-written the same plugin in C.

How to use the plugin:

During Profile use build stage of Feedback-directed builds, use the flags:
-fcallgraph-profiles-sections
-Wl,--plugin,<path_to_plugin>/libfunction_reordering_plugin.so

The first flag generates special .gnu.callgraph.text sections which contain the callgraph profiles that are read by the plugin and an new function layout is generated. The ordering of sections is dumped in file final_layout.txt along with the callgraph edge profile information.

The plugin itself is implemented in the three files: function_ordering_plugin.c, callgraph.c, and callgraph.h. The file include/plugin-api.h has changes which has already been submitted to trunk. The rest is related to Makefiles and configure scripts to build and install the plugin. I have not attached any of the auto-generated files.



--
This patch is available for review at http://codereview.appspot.com/5124041
Michael Witten - Sept. 24, 2011, 1:37 p.m.
> Re: [google] Linker plugin to do function reordering...

Is there a particularly good reason for why you guys
slip `[google]' into all of your `Subject:' lines?

I was under the impresions that this list is for work
on GCC. Consider putting something germane in the
brackets instead.
Diego Novillo - Sept. 24, 2011, 2 p.m.
On 11-09-24 09:37 , Michael Witten wrote:
>> Re: [google] Linker plugin to do function reordering...
>
> Is there a particularly good reason for why you guys
> slip `[google]' into all of your `Subject:' lines?

Yes, labels in brackets tend to be markers for branches, version 
numbers, specific modules.  In this case, they're used to indicate 
patches to one of the google branches (http://gcc.gnu.org/svn.html, 
http://gcc.gnu.org/ml/gcc/2011-01/msg00246.html).


Diego.
Michael Witten - Sept. 24, 2011, 7:19 p.m.
On Sat, 24 Sep 2011 10:00:37 -0400, Diego Novillo wrote:

> On 11-09-24 09:37 , Michael Witten wrote:
>>> Re: [google] Linker plugin to do function reordering...
>>
>> Is there a particularly good reason for why you guys
>> slip `[google]' into all of your `Subject:' lines?
>
> Yes, labels in brackets tend to be markers for branches, version 
> numbers, specific modules.  In this case, they're used to indicate 
> patches to one of the google branches (http://gcc.gnu.org/svn.html, 
> http://gcc.gnu.org/ml/gcc/2011-01/msg00246.html).

From that email:

> google/integration
>    A branch following trunk that contains some minimal patches that
> are likely not useful anywhere outside of Google's build environment.
> These are typically configuration patches.

Why is gnu.gcc.org hosting work that is specific to some company's
build system?

> google/main
>    A branch of google/integration that contains Google local patches
> that we are looking to contribute to trunk.  Some of these patches are
> either in the process of being reviewed, or have not yet been
> proposed.  The intent of this branch is to serve as a staging platform
> to allow collaboration with external developers.  Patches in this
> branch are only expected to remain here until they are reviewed and
> accepted in trunk.

Why is it necessary to announce a patch [series] for this branch when it
is intended that such a patch [series] make it to the trunk? Shouldn't an
employee of your company submit a `trunk'-worthy patch [series] for review
as would anyone else?

Isn't having one branch named `google' (or `google/maint') too ridiculously
generic to be of any use whatsoever? Wouldn't it make far more sense to have
a topic branch if deemed necessary (for, say, a large patch series)?

Why is gnu.gcc.org hosting such a pointless branch? Is it just that the
technical inadequacies of SVN made it easier for your multi-billion-dollar
company to host its essentially private work in GNU's repository?

Furthermore, looking at the `Subject' header of this email:

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

I wonder what `issue5124041' means. Is that a reference that only has
meaning for employees of your company?

Sincerely,
Michael Witten
Diego Novillo - Sept. 24, 2011, 9:30 p.m.
I think you may be trolling, but I'll give you the benefit of the
doubt since you seem to be lacking some background.

On Sat, Sep 24, 2011 at 15:19, Michael Witten <mfwitten@gmail.com> wrote:

> Why is gnu.gcc.org hosting work that is specific to some company's
> build system?

We've long allowed different companies hold branches on gcc.gnu.org.
From one of the links I posted in my previous response:
http://gcc.gnu.org/svn.html#distrobranches

> Why is it necessary to announce a patch [series] for this branch when it
> is intended that such a patch [series] make it to the trunk? Shouldn't an
> employee of your company submit a `trunk'-worthy patch [series] for review
> as would anyone else?

Yes, and you will see several patches from google.com addresses that
are not labeled [google].  Those are meant for trunk or devel
branches.  It is true that if a patch is meant for trunk, it should
not have a branch tag.  I expect slipups like that to occur from time
to time.  Thanks for pointing it out.

> I wonder what `issue5124041' means. Is that a reference that only has
> meaning for employees of your company?

No.  This is Rietveld, an open source code review system.  I suggested
using it for code reviews a while ago and contributed a script to
facilitate using it with GCC.  See http://gcc.gnu.org/wiki/rietveld


Diego.
Mike Stump - Sept. 24, 2011, 9:35 p.m.
On Sep 24, 2011, at 12:19 PM, Michael Witten wrote:
> Why is gnu.gcc.org hosting work that is specific to some company's
> build system?

This list isn't for this topic.  If you want, please, really, go play in gnu.misc.discuss.  This list is for technical patches and the technical review of such.  If your email isn't of that nature, then it is off-topic for this list.  Thanks.

> Why is gnu.gcc.org hosting such a pointless branch? Is it just that the
> technical inadequacies of SVN made it easier for your multi-billion-dollar
> company to host its essentially private work in GNU's repository?

This isn't GNU's repository, this is GCC's repository.
Nathan Froyd - Sept. 26, 2011, 4:22 p.m.
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?

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
Sriraman Tallam - Sept. 26, 2011, 4:53 p.m.
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: configure.ac
===================================================================
--- configure.ac	(revision 178891)
+++ configure.ac	(working copy)
@@ -1738,6 +1738,8 @@ 
 
 ACX_ELF_TARGET_IFELSE([# ELF platforms build the lto-plugin always.
   build_lto_plugin=yes
+  # Allow ELF platforms to build the function_reordering_plugin always.
+  build_function_reordering_plugin=yes
 ],[if test x"$default_enable_lto" = x"yes" ; then
     case $target in
       *-apple-darwin9 | *-cygwin* | *-mingw*) ;;
@@ -1865,6 +1867,11 @@ 
       extra_host_libiberty_configure_flags=--enable-shared
     fi
   fi
+  if test "${build_function_reordering_plugin}" = "yes" ; then
+    configdirs="$configdirs function_reordering_plugin"
+    extra_host_libiberty_configure_flags=--enable-shared
+  fi
+
   AC_SUBST(extra_host_libiberty_configure_flags)
 
   missing_languages=`echo ",$enable_languages," | sed -e s/,all,/,/ -e s/,c,/,/ `
Index: include/plugin-api.h
===================================================================
--- include/plugin-api.h	(revision 178891)
+++ include/plugin-api.h	(working copy)
@@ -93,6 +93,14 @@ 
   int resolution;
 };
 
+/* An object's section.  */
+
+struct ld_plugin_section
+{
+  const void* handle;
+  unsigned int shndx;
+};
+
 /* Whether the symbol is a definition, reference, or common, weak or not.  */
 
 enum ld_plugin_symbol_kind
@@ -203,6 +211,10 @@ 
 (*ld_plugin_get_input_file) (const void *handle,
                              struct ld_plugin_input_file *file);
 
+typedef
+enum ld_plugin_status
+(*ld_plugin_get_view) (const void *handle, const void **viewp);
+
 /* The linker's interface for releasing the input file.  */
 
 typedef
@@ -240,6 +252,65 @@ 
 enum ld_plugin_status
 (*ld_plugin_message) (int level, const char *format, ...);
 
+/* The linker's interface for retrieving the number of sections in an object.
+   The handle is obtained in the claim_file handler.  This interface should
+   only be invoked in the claim_file handler.   This function sets *COUNT to
+   the number of sections in the object.  */
+
+typedef
+enum ld_plugin_status
+(*ld_plugin_get_input_section_count) (const void* handle, unsigned int *count);
+
+/* The linker's interface for retrieving the section type of a specific
+   section in an object.  This interface should only be invoked in the
+   claim_file handler.  This function sets *TYPE to an ELF SHT_xxx value.  */
+
+typedef
+enum ld_plugin_status
+(*ld_plugin_get_input_section_type) (const struct ld_plugin_section section,
+                                     unsigned int *type);
+
+/* The linker's interface for retrieving the name of a specific section in
+   an object. This interface should only be invoked in the claim_file handler.
+   This function sets *SECTION_NAME_PTR to a null-terminated buffer allocated
+   by malloc.  The plugin must free *SECTION_NAME_PTR.  */
+
+typedef
+enum ld_plugin_status
+(*ld_plugin_get_input_section_name) (const struct ld_plugin_section section,
+                                     char **section_name_ptr);
+
+/* The linker's interface for retrieving the contents of a specific section
+   in an object.  This interface should only be invoked in the claim_file
+   handler.  This function sets *SECTION_CONTENTS to point to a buffer that is
+   valid until clam_file handler returns.  It sets *LEN to the size of the
+   buffer.  */
+
+typedef
+enum ld_plugin_status
+(*ld_plugin_get_input_section_contents) (const struct ld_plugin_section section,
+                                         const unsigned char **section_contents,
+                                         size_t* len);
+
+/* The linker's interface for specifying the desired order of sections.
+   The sections should be specifed using the array SECTION_LIST in the
+   order in which they should appear in the final layout.  NUM_SECTIONS
+   specifies the number of entries in each array.  This should be invoked
+   in the all_symbols_read handler.  */
+
+typedef
+enum ld_plugin_status
+(*ld_plugin_update_section_order) (const struct ld_plugin_section *section_list,
+				   unsigned int num_sections);
+
+/* The linker's interface for specifying that reordering of sections is
+   desired so that the linker can prepare for it.  This should be invoked
+   before update_section_order, preferably in the claim_file handler.  */
+
+typedef
+enum ld_plugin_status
+(*ld_plugin_allow_section_ordering) (void);
+
 enum ld_plugin_level
 {
   LDPL_INFO,
@@ -269,7 +340,14 @@ 
   LDPT_ADD_INPUT_LIBRARY,
   LDPT_OUTPUT_NAME,
   LDPT_SET_EXTRA_LIBRARY_PATH,
-  LDPT_GNU_LD_VERSION
+  LDPT_GNU_LD_VERSION,
+  LDPT_GET_VIEW,
+  LDPT_GET_INPUT_SECTION_COUNT,
+  LDPT_GET_INPUT_SECTION_TYPE,
+  LDPT_GET_INPUT_SECTION_NAME,
+  LDPT_GET_INPUT_SECTION_CONTENTS,
+  LDPT_UPDATE_SECTION_ORDER,
+  LDPT_ALLOW_SECTION_ORDERING
 };
 
 /* The plugin transfer vector.  */
@@ -289,9 +367,16 @@ 
     ld_plugin_add_input_file tv_add_input_file;
     ld_plugin_message tv_message;
     ld_plugin_get_input_file tv_get_input_file;
+    ld_plugin_get_view tv_get_view;
     ld_plugin_release_input_file tv_release_input_file;
     ld_plugin_add_input_library tv_add_input_library;
     ld_plugin_set_extra_library_path tv_set_extra_library_path;
+    ld_plugin_get_input_section_count tv_get_input_section_count;
+    ld_plugin_get_input_section_type tv_get_input_section_type;
+    ld_plugin_get_input_section_name tv_get_input_section_name;
+    ld_plugin_get_input_section_contents tv_get_input_section_contents;
+    ld_plugin_update_section_order tv_update_section_order;
+    ld_plugin_allow_section_ordering tv_allow_section_ordering;
   } tv_u;
 };
Index: function_reordering_plugin/configure.ac
===================================================================
--- function_reordering_plugin/configure.ac	(revision 0)
+++ function_reordering_plugin/configure.ac	(revision 0)
@@ -0,0 +1,14 @@ 
+AC_PREREQ(2.64)
+AC_INIT([REORDER plugin for ld], 0.1,,[function_reordering_plugin])
+AC_CANONICAL_SYSTEM
+GCC_TOPLEV_SUBDIRS
+AM_INIT_AUTOMAKE([foreign no-dist])
+AM_MAINTAINER_MODE
+AC_PROG_CC
+AC_SYS_LARGEFILE
+AM_PROG_LIBTOOL
+ACX_LT_HOST_FLAGS
+AC_SUBST(target_noncanonical)
+AC_CONFIG_FILES(Makefile)
+AC_CONFIG_HEADERS(config.h)
+AC_OUTPUT
Index: function_reordering_plugin/callgraph.h
===================================================================
--- function_reordering_plugin/callgraph.h	(revision 0)
+++ function_reordering_plugin/callgraph.h	(revision 0)
@@ -0,0 +1,257 @@ 
+/* 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>
+
+struct __edge__;
+typedef struct __edge__ Edge;
+
+/* Maintain a list of edges.  */
+typedef struct __edge_list_node__
+{
+  Edge *edge;
+  struct __edge_list_node__ *next;
+  struct __edge_list_node__ *prev;
+} Edge_list;
+
+inline static Edge_list *
+make_edge_list (Edge *e)
+{
+  Edge_list *list = (Edge_list *)malloc (sizeof (Edge_list));
+  list->edge = e;
+  list->next = NULL;
+  list->prev = NULL;
+  return list;
+}
+
+/* Represents a node in the call graph. */
+typedef struct _node_
+{
+  unsigned int id;
+  char *name;
+  /* Chain all the Nodes created.  */
+  struct _node_ *next;
+  /* Pointer to the next node in the chain of merged nodes.  */
+  struct _node_ *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_ *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 = (Node *)malloc (sizeof (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__
+{
+  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__ *prev;
+  struct __edge__ *next;
+};
+
+inline static Edge *
+make_edge (Node *first, Node *second, unsigned int weight)
+{
+  Edge *edge = (Edge *) malloc (sizeof (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;
+}
+
+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 = (Section_id *) malloc (sizeof (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/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,247 @@ 
+/* 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))
+        {
+	  /* Length of '.text.' is 6. */
+          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/Makefile.am
===================================================================
--- function_reordering_plugin/Makefile.am	(revision 0)
+++ function_reordering_plugin/Makefile.am	(revision 0)
@@ -0,0 +1,38 @@ 
+# Makefile.am is used by automake 1.11 to generate Makefile.in.
+
+ACLOCAL_AMFLAGS = -I .. -I ../config
+AUTOMAKE_OPTIONS = no-dependencies
+
+gcc_version := $(shell cat $(top_srcdir)/../gcc/BASE-VER)
+target_noncanonical := @target_noncanonical@
+libexecsubdir := $(libexecdir)/gcc/$(target_noncanonical)/$(gcc_version)
+
+AM_CPPFLAGS = -I$(top_srcdir)/../include $(DEFS)
+AM_CFLAGS = -Wall -Werror
+AM_LIBTOOLFLAGS = --tag=disable-static
+
+libexecsub_LTLIBRARIES = libfunction_reordering_plugin.la
+gcc_build_dir = ../$(host_subdir)/gcc
+in_gcc_libs = $(foreach lib, $(libexecsub_LTLIBRARIES), $(gcc_build_dir)/$(lib))
+
+# Can be removed when libiberty becomes a normal convenience library
+Wc=-Wc,
+
+libfunction_reordering_plugin_la_SOURCES =  function_reordering_plugin.c callgraph.c
+libfunction_reordering_plugin_la_LIBADD = \
+	$(if $(wildcard ../libiberty/pic/libiberty.a),$(Wc)../libiberty/pic/libiberty.a,)
+# Note that we intentionally override the bindir supplied by ACX_LT_HOST_FLAGS
+libfunction_reordering_plugin_la_LDFLAGS = $(lt_host_flags) -module -bindir $(libexecsubdir) \
+	$(if $(wildcard ../libiberty/pic/libiberty.a),,-Wc,../libiberty/libiberty.a)
+libfunction_reordering_plugin_la_DEPENDENCIES = $(if $(wildcard \
+	../libiberty/pic/libiberty.a),../libiberty/pic/libiberty.a,) callgraph.h
+
+all-local: $(in_gcc_libs)
+
+$(in_gcc_libs) : $(gcc_build_dir)/%: %
+	@if test "X`dlname=; . ./$*; echo dlname:$$dlname`" = "Xdlname:"; then \
+	  echo WARNING: $* is static, not copying to $@ >&2 ; \
+	else \
+	  $(mkinstalldirs) $(gcc_build_dir) && \
+	  $(LIBTOOL) $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=install $(INSTALL) $(INSTALL_STRIP_FLAG) $* `pwd`/$@ ; \
+	fi
Index: function_reordering_plugin/callgraph.c
===================================================================
--- function_reordering_plugin/callgraph.c	(revision 0)
+++ function_reordering_plugin/callgraph.c	(revision 0)
@@ -0,0 +1,600 @@ 
+/* 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)
+{
+  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)
+{
+  /* If the number of functions is less than 10000, this gives a unique value
+     for every function id combination.  */
+  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 ();
+    }
+}
+
+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.") */;
+
+  /* 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 = (void**) malloc (num_real_nodes * sizeof (void *));
+  *shndx = (unsigned int *) malloc (num_real_nodes * sizeof (unsigned int));
+
+  /* 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;
+  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;
+        }
+      free (node);
+      node = next_node;
+    }
+
+  /* Free all active_edges.  */
+  for (edge = active_edges; edge != NULL; )
+    {
+      Edge *next_edge = edge->next;
+      free (edge);
+      edge = next_edge;
+    }
+
+  /* Free all inactive_edges.  */
+  for (edge = inactive_edges; edge != NULL; )
+    {
+      Edge *next_edge = edge->next;
+      free (edge);
+      edge = next_edge;
+    }
+
+  /* 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;
+}
Index: configure
===================================================================
--- configure	(revision 178891)
+++ configure	(working copy)
@@ -6199,6 +6199,8 @@ 
 if test $target_elf = yes; then :
   # ELF platforms build the lto-plugin always.
   build_lto_plugin=yes
+  # Allow ELF platforms to build the function_reordering_plugin always.
+  build_function_reordering_plugin=yes
 
 else
   if test x"$default_enable_lto" = x"yes" ; then
@@ -6330,8 +6332,13 @@ 
       extra_host_libiberty_configure_flags=--enable-shared
     fi
   fi
+  if test "${build_function_reordering_plugin}" = "yes" ; then
+    configdirs="$configdirs function_reordering_plugin"
+    extra_host_libiberty_configure_flags=--enable-shared
+  fi
 
 
+
   missing_languages=`echo ",$enable_languages," | sed -e s/,all,/,/ -e s/,c,/,/ `
   potential_languages=,c,
Index: Makefile.def
===================================================================
--- Makefile.def	(revision 178891)
+++ Makefile.def	(working copy)
@@ -147,6 +147,8 @@ 
 host_modules= { module= gnattools; };
 host_modules= { module= lto-plugin; bootstrap=true;
 		extra_configure_flags=--enable-shared; };
+host_modules= { module= function_reordering_plugin; bootstrap=true;
+		extra_configure_flags=--enable-shared; };
 
 target_modules = { module= libstdc++-v3;
 		   bootstrap=true;
@@ -322,6 +324,7 @@ 
 // Host modules specific to gcc.
 dependencies = { module=configure-gcc; on=configure-intl; };
 dependencies = { module=configure-gcc; on=all-lto-plugin; };
+dependencies = { module=configure-gcc; on=all-function_reordering_plugin; };
 dependencies = { module=configure-gcc; on=all-binutils; };
 dependencies = { module=configure-gcc; on=all-gas; };
 dependencies = { module=configure-gcc; on=all-ld; };
@@ -346,12 +349,14 @@ 
 dependencies = { module=all-gcc; on=all-libiberty; };
 dependencies = { module=all-gcc; on=all-fixincludes; };
 dependencies = { module=all-gcc; on=all-lto-plugin; };
+dependencies = { module=all-gcc; on=all-function_reordering_plugin; };
 dependencies = { module=info-gcc; on=all-build-libiberty; };
 dependencies = { module=dvi-gcc; on=all-build-libiberty; };
 dependencies = { module=pdf-gcc; on=all-build-libiberty; };
 dependencies = { module=html-gcc; on=all-build-libiberty; };
 dependencies = { module=install-gcc ; on=install-fixincludes; };
 dependencies = { module=install-gcc ; on=install-lto-plugin; };
+dependencies = { module=install-gcc ; on=install-function_reordering_plugin; };
 dependencies = { module=install-strip-gcc ; on=install-strip-fixincludes; };
 
 dependencies = { module=configure-libcpp; on=configure-libiberty; hard=true; };
@@ -364,6 +369,7 @@ 
 dependencies = { module=all-gnattools; on=all-target-libada; };
 
 dependencies = { module=all-lto-plugin; on=all-libiberty; };
+dependencies = { module=all-function_reordering_plugin; on=all-libiberty; };
 
 dependencies = { module=configure-mpfr; on=all-gmp; };
 dependencies = { module=configure-mpc; on=all-mpfr; };