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.
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 (tmsri...@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 (tmsri...@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 **)§ion_contents_ptr,
+ &length);
+ unsigned char *section_contents;
+ section_contents = (unsigned char *) malloc (length);
+ memcpy (section_contents, section_contents_ptr, length);
+ parse_callgraph_section_contents (section_contents, (unsigned
int)length);
+ }
+ else if (name != NULL)
+ free (name);
+ }
+
+ return LDPS_OK;
+}
+
+/* This function is called by the linker after all the symbols have been read.
+ At this stage, it is fine to tell the linker the desired function order. */
+
+enum ld_plugin_status
+all_symbols_read_hook (void)
+{
+ unsigned int num_entries;
+ unsigned int i;
+ struct ld_plugin_section *section_list;
+ void **handles;
+ unsigned int *shndx;
+ FILE *fp;
+
+ /* Silently return if the plugin APIs are not supported. */
+ if (!is_api_exist)
+ return LDPS_OK;
+
+ if (is_callgraph_empty ())
+ return LDPS_OK;
+
+ /* Open the file to write the final layout */
+ if (out_file == NULL)
+ fp = stderr;
+ else
+ fp = fopen (out_file, "w");
+
+ fprintf (fp, "# Remove lines starting with \'#\' to"
+ " pass to --section-ordering-file\n");
+ fprintf (fp, "# Lines starting with \'#\' are the edge profiles\n");
+
+ find_pettis_hansen_function_layout (fp);
+ num_entries = get_layout (fp, &handles, &shndx);
+ section_list = (struct ld_plugin_section *)
+ malloc (num_entries * sizeof (struct ld_plugin_section));
+ for (i = 0; i < num_entries; i++)
+ {
+ section_list[i].handle = handles[i];
+ section_list[i].shndx = shndx[i];
+ }
+
+ /* Pass the new order of functions to the linker. */
+ update_section_order (section_list, num_entries);
+ free (section_list);
+ free (handles);
+ free (shndx);
+ cleanup ();
+ return LDPS_OK;
+}
Index: function_reordering_plugin/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 (tmsri...@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; };
--
This patch is available for review at http://codereview.appspot.com/5124041
