===================================================================
@@ -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,/,/ `
===================================================================
@@ -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;
};
===================================================================
@@ -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
===================================================================
@@ -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
===================================================================
@@ -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 **)§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;
+}
===================================================================
@@ -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
===================================================================
@@ -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;
+}
===================================================================
@@ -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,
===================================================================
@@ -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; };