From patchwork Tue Sep 27 00:22:21 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Sriraman Tallam X-Patchwork-Id: 116524 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id F39EDB6F72 for ; Tue, 27 Sep 2011 10:22:57 +1000 (EST) Received: (qmail 20257 invoked by alias); 27 Sep 2011 00:22:54 -0000 Received: (qmail 20220 invoked by uid 22791); 27 Sep 2011 00:22:49 -0000 X-SWARE-Spam-Status: No, hits=1.1 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, KAM_STOCKTIP, RP_MATCHES_RCVD, SPF_HELO_PASS, TW_CP X-Spam-Check-By: sourceware.org Received: from smtp-out.google.com (HELO smtp-out.google.com) (74.125.121.67) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 27 Sep 2011 00:22:28 +0000 Received: from wpaz24.hot.corp.google.com (wpaz24.hot.corp.google.com [172.24.198.88]) by smtp-out.google.com with ESMTP id p8R0MPYF009550 for ; Mon, 26 Sep 2011 17:22:26 -0700 Received: from yib25 (yib25.prod.google.com [10.243.65.89]) by wpaz24.hot.corp.google.com with ESMTP id p8R0MO1n031094 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for ; Mon, 26 Sep 2011 17:22:24 -0700 Received: by yib25 with SMTP id 25so6723793yib.37 for ; Mon, 26 Sep 2011 17:22:24 -0700 (PDT) Received: by 10.150.210.14 with SMTP id i14mr7078947ybg.119.1317082943165; Mon, 26 Sep 2011 17:22:23 -0700 (PDT) MIME-Version: 1.0 Received: by 10.150.210.14 with SMTP id i14mr7078932ybg.119.1317082941921; Mon, 26 Sep 2011 17:22:21 -0700 (PDT) Received: by 10.151.13.6 with HTTP; Mon, 26 Sep 2011 17:22:21 -0700 (PDT) In-Reply-To: References: <20110923220316.0F03FB2195@azwildcat.mtv.corp.google.com> <4E80A6DF.90806@mozilla.com> Date: Mon, 26 Sep 2011 17:22:21 -0700 Message-ID: Subject: Re: [google] Linker plugin to do function reordering using callgraph edge profiles (issue5124041) From: Sriraman Tallam To: Nathan Froyd Cc: reply@codereview.appspotmail.com, eraman@google.com, gcc-patches@gcc.gnu.org, tglek@mozilla.com X-System-Of-Record: true X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org *Resending as plain text* I am attaching a patch of the updated files. This patch was meant for the google gcc-4_6 branch. Sorry for not mentioning this upfront in my original mail. Thanks, -Sri. > On Mon, Sep 26, 2011 at 9:53 AM, Sriraman Tallam wrote: >> >> On Mon, Sep 26, 2011 at 9:22 AM, Nathan Froyd 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 >> > > Index: function_reordering_plugin/function_reordering_plugin.c =================================================================== --- function_reordering_plugin/function_reordering_plugin.c (revision 0) +++ function_reordering_plugin/function_reordering_plugin.c (revision 0) @@ -0,0 +1,246 @@ +/* Function re-ordering plugin for gold. + Copyright (C) 2011 Free Software Foundation, Inc. + Contributed by Sriraman Tallam (tmsriram@google.com). + +This program is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +This program is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program; see the file COPYING3. If not see +. */ + +/* 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 +#endif +#include +#include +#include +#include +#include +#include +#include "config.h" +#include "plugin-api.h" +#include "callgraph.h" + +enum ld_plugin_status claim_file_hook (const struct ld_plugin_input_file *file, + int *claimed); +enum ld_plugin_status all_symbols_read_hook (); + +static ld_plugin_get_input_section_count get_input_section_count = NULL; +static ld_plugin_get_input_section_type get_input_section_type = NULL; +static ld_plugin_get_input_section_name get_input_section_name = NULL; +static ld_plugin_get_input_section_contents get_input_section_contents = NULL; +static ld_plugin_update_section_order update_section_order = NULL; +static ld_plugin_allow_section_ordering allow_section_ordering = NULL; + +/* The file where the final function order will be stored. + It is "./final_layout.txt". It can be changed by passing + new name to --plugin-opt */ + +char *out_file = "./final_layout.txt"; + +int is_api_exist = 0; + +/* Copies new output file name out_file */ +void get_filename (const char *name) +{ + if (strcmp (name, "stderr") == 0) + { + out_file = NULL; + return; + } + out_file = (char *) malloc (strlen (name) + 1); + strcpy (out_file, name); +} + +/* Plugin entry point. */ +enum ld_plugin_status +onload (struct ld_plugin_tv *tv) +{ + struct ld_plugin_tv *entry; + for (entry = tv; entry->tv_tag != LDPT_NULL; ++entry) + { + switch (entry->tv_tag) + { + case LDPT_API_VERSION: + break; + case LDPT_GOLD_VERSION: + break; + case LDPT_OPTION: + get_filename (entry->tv_u.tv_string); + break; + case LDPT_REGISTER_CLAIM_FILE_HOOK: + assert ((*entry->tv_u.tv_register_claim_file) (claim_file_hook) == LDPS_OK); + break; + case LDPT_REGISTER_ALL_SYMBOLS_READ_HOOK: + assert ((*entry->tv_u.tv_register_all_symbols_read) (all_symbols_read_hook) + == LDPS_OK); + break; + case LDPT_GET_INPUT_SECTION_COUNT: + get_input_section_count = *entry->tv_u.tv_get_input_section_count; + break; + case LDPT_GET_INPUT_SECTION_TYPE: + get_input_section_type = *entry->tv_u.tv_get_input_section_type; + break; + case LDPT_GET_INPUT_SECTION_NAME: + get_input_section_name = *entry->tv_u.tv_get_input_section_name; + break; + case LDPT_GET_INPUT_SECTION_CONTENTS: + get_input_section_contents = *entry->tv_u.tv_get_input_section_contents; + break; + case LDPT_UPDATE_SECTION_ORDER: + update_section_order = *entry->tv_u.tv_update_section_order; + break; + case LDPT_ALLOW_SECTION_ORDERING: + allow_section_ordering = *entry->tv_u.tv_allow_section_ordering; + break; + default: + break; + } + } + + if (get_input_section_count != NULL + && get_input_section_type != NULL + && get_input_section_name != NULL + && get_input_section_contents != NULL + && update_section_order != NULL + && allow_section_ordering != NULL) + is_api_exist = 1; + + return LDPS_OK; +} + +static int is_ordering_specified = 0; + +/* This function is called by the linker for every new object it encounters. */ + +enum ld_plugin_status +claim_file_hook (const struct ld_plugin_input_file *file, int *claimed) +{ + unsigned int count = 0; + struct ld_plugin_section section; + unsigned int shndx; + + (void) claimed; + + /* Silently return if the plugin APIs are not supported. */ + if (!is_api_exist) + return LDPS_OK; + + if (is_ordering_specified == 0) + { + /* Inform the linker to prepare for section reordering. */ + (*allow_section_ordering) (); + is_ordering_specified = 1; + } + + (*get_input_section_count) (file->handle, &count); + + for (shndx = 0; shndx < count; ++shndx) + { + unsigned int type = SHT_NULL; + char *name = NULL; + + section.handle = file->handle; + section.shndx = shndx; + (*get_input_section_type) (section, &type); + + (*get_input_section_name) (section, &name); + if (type == SHT_PROGBITS && is_prefix_of (".text.", name)) + { + map_section_name_to_index (name, file->handle, shndx); + } + else if (is_prefix_of (".gnu.callgraph.text", name)) + { + /* Process callgraph sections. */ + unsigned char *section_contents_ptr = NULL; + size_t length; + (*get_input_section_contents) (section, + (const unsigned char **)§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/callgraph.h =================================================================== --- function_reordering_plugin/callgraph.h (revision 0) +++ function_reordering_plugin/callgraph.h (revision 0) @@ -0,0 +1,272 @@ +/* Callgraph implementation. + Copyright (C) 2011 Free Software Foundation, Inc. + Contributed by Sriraman Tallam (tmsriram@google.com). + +This program is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +This program is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program; see the file COPYING3. If not see +. */ + +#ifndef CALLGRAPH_H +#define CALLGRAPH_H + +#include +#include +#include +#include +#include +#include "libiberty.h" + +struct edge_d; +typedef struct edge_d Edge; + +/* Maintain a list of edges. */ +typedef struct edge_list_d +{ + Edge *edge; + struct edge_list_d *next; + struct edge_list_d *prev; +} Edge_list; + +inline static Edge_list * +make_edge_list (Edge *e) +{ + Edge_list *list = XNEW (Edge_list); + list->edge = e; + list->next = NULL; + list->prev = NULL; + return list; +} + +/* Represents a node in the call graph. */ +typedef struct node_d +{ + unsigned int id; + char *name; + /* Chain all the Nodes created. */ + struct node_d *next; + /* Pointer to the next node in the chain of merged nodes. */ + struct node_d *merge_next; + /* List of all edges with this node. */ + Edge_list *edge_list; + /* Pointer to the last node in the chain of merged nodes. */ + struct node_d *last_merge_node; + unsigned int is_merged; + /* 1 if the function corresponding to this node can be re-ordered. */ + unsigned int is_real_node; +} Node; + +inline static Node * +make_node (unsigned int id, char *name) +{ + Node *node = XNEW (Node); + node->id = id; + node->name = name; + node->is_real_node = 0; + node->next = NULL; + node->edge_list = NULL; + node->last_merge_node = node; + node->is_merged = 0; + node->merge_next = NULL; + return node; +} + +/* Chain the nodes that are merged. Maintain a pointer to the last + node in the chain. After merging at the end, the last node in the + current chain is the last node in the chain of the merged node. */ +inline static void +merge_node (Node *merger, Node *mergee) +{ + merger->last_merge_node->merge_next = mergee; + merger->last_merge_node = mergee->last_merge_node; + mergee->is_merged = 1; +} + +inline static void +add_edge_to_node (Node *n, Edge *e) +{ + Edge_list *list; + assert (n != NULL && e != NULL); + list = make_edge_list (e); + list->next = n->edge_list; + if (n->edge_list != NULL) + n->edge_list->prev = list; + n->edge_list = list; +} + +/* A node is real only if the function can be reordered. */ +inline static void +set_as_real_node (Node *node) +{ + node->is_real_node = 1; +} + +/* WEAK if one of the nodes is not real. STRONG if both + nodes are real. */ +typedef enum edge_type_ +{ + STRONG_EDGE = 0, + WEAK_EDGE +} Edge_type; + +/*Represents an edge in the call graph. */ +struct edge_d +{ + Node *first_function; + Node *second_function; + unsigned int weight; + Edge_type type; + /* 1 if the nodes corresponding to this edge have been merged. */ + unsigned int is_merged; + /* Doubly linked chain of created edges. */ + struct edge_d *prev; + struct edge_d *next; +}; + +inline static Edge * +make_edge (Node *first, Node *second, unsigned int weight) +{ + Edge *edge = XNEW (Edge); + edge->first_function = first; + edge->second_function = second; + edge->weight = weight; + edge->type = WEAK_EDGE; + edge->is_merged = 0; + edge->prev = NULL; + edge->next = NULL; + add_edge_to_node (first, edge); + add_edge_to_node (second, edge); + return edge; +} + +/* Frees the chain of edges. */ +inline static void +free_edge_chain (Edge *edge_chain) +{ + Edge *edge; + + for (edge = edge_chain; edge != NULL; ) + { + Edge *next_edge = edge->next; + free (edge); + edge = next_edge; + } +} + +inline static void +set_edge_type (Edge *edge) +{ + if (edge->first_function->is_real_node + && edge->second_function->is_real_node) + edge->type = STRONG_EDGE; + else + edge->type = WEAK_EDGE; +} + +inline static unsigned int +edge_lower (Edge *e1, Edge *e2) +{ + if (e1->type == e2->type) + return (e1->weight < e2->weight) ? 1 : 0; + if (e1->type == STRONG_EDGE) + return 0; + return 1; +} + +inline static void +reset_functions (Edge *e, Node *n1, Node *n2) +{ + /* No self edges. */ + assert (n1->id != n2->id); + if (n1->id < n2->id) + { + e->first_function = n1; + e->second_function = n2; + } + else + { + e->first_function = n2; + e->second_function = n1; + } +} + +/* A Section is represented by its object handle and the section index. */ +typedef struct +{ + /* Name of the function. */ + char *name; + /* Full name of the section. */ + char *full_name; + void *handle; + int shndx; +} Section_id; + +inline static Section_id * +make_section_id (char *name, char *full_name, void *handle, int shndx) +{ + Section_id *s = XNEW (Section_id); + s->name = name; + s->full_name = full_name; + s->handle = handle; + s->shndx = shndx; + + return s; +} + +/* A pair of nodes make a raw edge. Also, N1->id < N2->id. */ +typedef struct +{ + Node *n1; + Node *n2; +} Raw_edge; + +inline static void +init_raw_edge (Raw_edge *r, Node *n1, Node *n2) +{ + assert (n1 ->id != n2->id); + if (n1->id < n2->id) + { + r->n1 = n1; + r->n2 = n2; + } + else + { + r->n1 = n2; + r->n2 = n1; + } +} + +inline static int is_prefix_of (const char *prefix, const char *str) +{ + return strncmp (prefix, str, strlen (prefix)) == 0; +} + +/* Maps the function corresponding to section name to its + corresponding object handle and the section index. */ +void +map_section_name_to_index (char *section_name, void *handle, int shndx); + +void +parse_callgraph_section_contents (unsigned char *section_contents, + unsigned int length); + +void dump_functions (); +void dump_edges (); +void find_pettis_hansen_function_layout (FILE *fp); + +unsigned int get_layout (FILE *fp, void*** handles, + unsigned int** shndx); + +void cleanup (); +/* Returns 1 if callgraph is empty. */ +unsigned int is_callgraph_empty (); +#endif Index: function_reordering_plugin/callgraph.c =================================================================== --- function_reordering_plugin/callgraph.c (revision 0) +++ function_reordering_plugin/callgraph.c (revision 0) @@ -0,0 +1,598 @@ +/* Callgraph implementation. + Copyright (C) 2011 Free Software Foundation, Inc. + Contributed by Sriraman Tallam (tmsriram@google.com). + +This program is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +This program is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program; see the file COPYING3. If not see +. */ + +#include "callgraph.h" +#include +#include +#include +#include +#include + +/*****************************************************************************/ +/* section_map hashtable definition and helpers. */ + +/* Maps section name to its corresponding object handle and section index. */ +static htab_t section_map = NULL; + +/* Hashtable helper for section_map htab. */ +static hashval_t +section_map_htab_hash_descriptor (const void *p) +{ + const Section_id *s = (const Section_id *)p; + const char *name = s->name; + return htab_hash_string(name); +} + +/* Hashtable helper for section_map htab. */ +static int +section_map_htab_eq_descriptor (const void *p1, const void *p2) +{ + const Section_id *s1 = (const Section_id *)p1; + const char *c1 = s1->name; + const char *c2 = (const char *)p2; + + return (strcmp (c1, c2) == 0); +} +/*****************************************************************************/ + + +/*****************************************************************************/ +/* function_map hashtable definition and helpers. + Maps function name to a unique Node. */ +static htab_t function_map = NULL; +static unsigned int last_function_id = 0; + +/* Hashtable helper for function_map htab. */ +static hashval_t +function_map_htab_hash_descriptor (const void *p) +{ + const Node *s = (const Node *)p; + const char *name = s->name; + return htab_hash_string(name); +} + +/* Hashtable helper for section_map htab. */ +static int +function_map_htab_eq_descriptor (const void *p1, const void *p2) +{ + const Node *s1 = (const Node *)p1; + const char *c1 = s1->name; + const char *c2 = (const char *)p2; + + return (strcmp (c1, c2) == 0); +} +/*****************************************************************************/ + +/*****************************************************************************/ +/* edge_map hashtable definition and helpers. + Maps two node ids to a unique edge. */ +static htab_t edge_map = NULL; + +static inline hashval_t +edge_hash_function (unsigned int id1, unsigned int id2) +{ + /* If the number of functions is less than 1000, this gives a unique value + for every function id combination. */ + const int MULTIPLIER = 1000; + return id1* MULTIPLIER + id2; +} + +/* Hashtable helper for edge_map htab. */ +static hashval_t +edge_map_htab_hash_descriptor (const void *p) +{ + Edge *e = (Edge *) p; + return edge_hash_function (e->first_function->id, e->second_function->id); +} + +/* Hashtable helper for edge_map htab. */ +static int +edge_map_htab_eq_descriptor (const void *p1, const void *p2) +{ + Edge *e1 = (Edge *) p1; + Raw_edge *r1 = (Raw_edge *) p2; + return ((e1->first_function->id == r1->n1->id) + && (e1->second_function->id == r1->n2->id)); +} + + +/*****************************************************************************/ + +/* Chain of all the created nodes. */ +Node *node_chain = NULL; +/* Number of nodes that correspond to functions which will be reordered. */ +unsigned int num_real_nodes = 0; +/* Chain of all edges in the merged callgraph. */ +Edge *active_edges = NULL; +/* Chain of all the merged edges. */ +Edge *inactive_edges = NULL; + +/* Reads off the next string from the char stream CONTENTS and updates + READ_LENGTH to the length of the string read. The value of CONTENTS + is updated to start at the next string. */ + +static char * +get_next_string (char **contents, unsigned int *read_length) +{ + char *s = *contents; + *read_length = strlen (*contents) + 1; + *contents += *read_length; + return s; +} + +/* Add an EDGE to the list of edges in the call graph. */ + +static void +add_edge_to_list (Edge *edge) +{ + assert (edge != NULL); + edge->next = active_edges; + if (active_edges != NULL) + active_edges->prev = edge; + active_edges = edge; +} + +/* Remove the edge from the list of edges in the call graph. This is done + when the nodes corresponding to this edge are merged. */ + +static void +remove_edge_from_list (Edge * curr_edge) +{ + assert (curr_edge != NULL); + if (curr_edge->prev != NULL) + curr_edge->prev->next = curr_edge->next; + if (curr_edge->next != NULL) + curr_edge->next->prev = curr_edge->prev; + if (active_edges == curr_edge) + active_edges = curr_edge->next; + curr_edge->next = NULL; + curr_edge->prev = NULL; + + /* Add to inactive edges to be freed later. */ + curr_edge->next = inactive_edges; + inactive_edges = curr_edge; + return; +} + +/* Adds the WEIGHT value to the edge count of CALLER and CALLEE. */ + +static void +update_edge (Node *n1, Node *n2, unsigned int weight) +{ + void **slot; + Raw_edge re, *r; + Edge *e; + + if (n1->id == n2->id) + return; + if (weight == 0) + return; + + if (edge_map == NULL) + { + edge_map = htab_create (25, edge_map_htab_hash_descriptor, + edge_map_htab_eq_descriptor , NULL); + assert (edge_map != NULL); + } + + r = &re; + init_raw_edge (r, n1, n2); + slot = htab_find_slot_with_hash (edge_map, r, + edge_hash_function (r->n1->id, r->n2->id), + INSERT); + if (*slot == NULL) + { + e = make_edge (r->n1, r->n2, weight); + *slot = e; + add_edge_to_list (e); + } + else + { + e = *slot; + e->weight += weight; + } +} + +/* Create a unique node for a function. */ + +static Node * +get_function_node (char *name) +{ + void **slot = NULL; + Node *node; + + if (function_map == NULL) + { + function_map = htab_create (25, function_map_htab_hash_descriptor, + function_map_htab_eq_descriptor , NULL); + assert (function_map != NULL); + } + + slot = htab_find_slot_with_hash (function_map, name, htab_hash_string (name), + INSERT); + + if (*slot == NULL) + { + node = make_node (last_function_id, name); + /* Chain the node to the node_chain. */ + node->next = node_chain; + node_chain = node; + *slot = node; + last_function_id++; + } + else + { + node = (Node *)*slot; + } + return node; +} + +/* Dumper funcction to print the list of functions that will be considered for + re-ordering. */ + +void +dump_functions () +{ + Node *node = node_chain; + while (node) + { + if (node->is_real_node) + fprintf (stderr, "Dumping function %s\n", node->name); + node = node->next; + } +} + +/* Dump all the edges existing in the callgraph. */ + +void dump_edges (FILE *fp) +{ + Edge *it; + for (it = active_edges; + it != NULL; + it = it->next) + { + fprintf (fp,"# %s ---- (%u)---- %s\n", + it->first_function->name, + it->weight, + it->second_function->name); + } +} + +/* HEADER_LEN is the length of string 'Function '. */ +const int HEADER_LEN = 9; + +/* Parse the section contents of ".gnu.callgraph.text" sections and create + call graph edges with appropriate weights. The section contents have the + following format : + Function + + + + + .... */ +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 '. */ + assert (length > 0); + contents = (char*) (section_contents); + caller = get_next_string (&contents, &read_length); + assert (read_length > HEADER_LEN); + caller = caller + HEADER_LEN; + curr_length = read_length; + caller_node = get_function_node (caller); + /* Real nodes are nodes that correspond to .text sections found. These will + definitely be sorted. */ + set_as_real_node (caller_node); + num_real_nodes++; + + while (curr_length < length) + { + /* Read callee, weight tuples. */ + char *callee; + char *weight_str; + unsigned int weight; + Node *callee_node; + + callee = get_next_string (&contents, &read_length); + curr_length += read_length; + callee_node = get_function_node (callee); + + assert (curr_length < length); + weight_str = get_next_string (&contents, &read_length); + weight = atoi (weight_str); + curr_length += read_length; + update_edge (caller_node, callee_node, weight); + } +} + +/* Traverse the list of edges and find the edge with the maximum weight. */ + +static Edge * +find_max_edge () +{ + Edge *it, *max_edge; + + if (active_edges == NULL) + return NULL; + + max_edge = active_edges; + assert (!active_edges->is_merged); + + it = active_edges->next; + for (;it != NULL; it = it->next) + { + assert (!it->is_merged); + if (edge_lower (max_edge , it)) + max_edge = it; + } + + return max_edge; +} + +/* Change the EDGE from OLD_NODE to KEPT_NODE to be between NEW_NODE + and KEPT_NODE. */ + +static void +merge_edge (Edge *edge, Node *new_node, Node *old_node, + Node *kept_node) +{ + void **slot; + Raw_edge re, *r; + + r = &re; + init_raw_edge (r, new_node, kept_node); + slot = htab_find_slot_with_hash (edge_map, r, + edge_hash_function (r->n1->id, r->n2->id), + INSERT); + + if (*slot == NULL) + { + reset_functions (edge, new_node, kept_node); + *slot = edge; + add_edge_to_node (new_node, edge); + } + else + { + Edge *new_edge = *slot; + new_edge->weight += edge->weight; + edge->is_merged = 1; + remove_edge_from_list (edge); + } +} + +/* Merge the two nodes in this EDGE. The new node's edges are the union of + the edges of the original nodes. */ + +static void +collapse_edge (Edge * edge) +{ + Edge_list *it; + Node *kept_node = edge->first_function; + Node *merged_node = edge->second_function; + + /* Go through all merged_node edges and merge with kept_node. */ + for (it = merged_node->edge_list; it != NULL; it = it->next) + { + Node *other_node = NULL; + Edge *this_edge = it->edge; + if (this_edge->is_merged) + continue; + if (this_edge == edge) + continue; + assert (this_edge->first_function->id == merged_node->id + || this_edge->second_function->id == merged_node->id); + other_node = (this_edge->first_function->id + == merged_node->id) + ? this_edge->second_function + : this_edge->first_function; + merge_edge (this_edge, kept_node, merged_node, other_node); + } + + merge_node (kept_node, merged_node); + edge->is_merged = 1; + remove_edge_from_list (edge); +} + +/* Make node N a real node if it can be reordered, that is, its .text + section is available. */ +static void set_node_type (Node *n) +{ + void **slot; + char *name = n->name; + slot = htab_find_slot_with_hash (section_map, name, htab_hash_string (name), + INSERT); + if (*slot != NULL) + set_as_real_node (n); +} + +void +find_pettis_hansen_function_layout (FILE *fp) +{ + Node *n_it; + Edge *it; + + assert (node_chain != NULL); + assert (active_edges != NULL); + assert (fp != NULL); + + dump_edges (fp); + + /* Go over all the nodes and set it as real node only if a corresponding + function section exists. */ + for (n_it = node_chain; n_it != NULL; n_it = n_it->next) + set_node_type (n_it); + + /* Set edge types. A WEAK_EDGE has one of its nodes corresponding to a + function that cannot be re-ordered. */ + for (it = active_edges; it != NULL; it = it->next) + set_edge_type (it); + + it = find_max_edge (); + while (it != NULL) + { + collapse_edge (it); + it = find_max_edge (); + } +} + +/* Maps the function name corresponding to section SECTION_NAME to the + object handle and the section index. */ + +void +map_section_name_to_index (char *section_name, void *handle, int shndx) +{ + void **slot; + const char *sections[] = {".text.hot.", + ".text.unlikely.", + ".text.cold.", + ".text.startup.", + ".text." }; + char *function_name = NULL; + int i; + + for (i = 0; i < ARRAY_SIZE (sections); ++i) + { + if (is_prefix_of (sections[i], section_name)) + { + function_name = section_name + strlen (sections[i]); + break; + } + } + assert (function_name != NULL); + + /* Allocate section_map. */ + if (section_map == NULL) + { + section_map = htab_create (10, section_map_htab_hash_descriptor, + section_map_htab_eq_descriptor , NULL); + assert (section_map != NULL); + } + + slot = htab_find_slot_with_hash (section_map, function_name, + htab_hash_string (function_name), + INSERT); + if (*slot == NULL) + *slot = make_section_id (function_name, section_name, handle, shndx); +} + +static void +write_out_node (FILE *fp, char *name, + void **handles, unsigned int *shndx, int position) +{ + void **slot; + slot = htab_find_slot_with_hash (section_map, name, htab_hash_string (name), + INSERT); + if (*slot != NULL) + { + Section_id *s = (Section_id *)*slot; + handles[position] = s->handle; + shndx[position] = s->shndx; + fprintf (fp, "%s\n", s->full_name); + } +} + +/* Visit each node and print the chain of merged nodes to the file. */ + +unsigned int +get_layout (FILE *fp, void*** handles, + unsigned int** shndx) +{ + Node *it; + int position = 0; + + assert (fp != NULL); + + *handles = XNEWVEC (void *, num_real_nodes); + *shndx = XNEWVEC (unsigned int, num_real_nodes); + + /* Dump edges to the final reordering file. */ + + for (it = node_chain; it != NULL; it = it->next) + { + Node *node; + if (it->is_merged) + continue; + if (it->is_real_node) + { + write_out_node (fp, it->name, *handles, *shndx, position); + position++; + } + node = it->merge_next; + while (node != NULL) + { + if (node->is_real_node) + { + write_out_node (fp, node->name, *handles, *shndx, position); + position++; + } + node = node->merge_next; + } + } + fclose (fp); + return position; +} + +/* Free all heap objects. */ + +void +cleanup () +{ + Node *node; + + /* Free all nodes and edge_lists. */ + for (node = node_chain; node != NULL; ) + { + Node *next_node = node->next; + Edge_list *it; + for (it = node->edge_list; it != NULL; ) + { + Edge_list *next_it = it->next; + free (it); + it = next_it; + } + free (node); + node = next_node; + } + + /* Free all active_edges. */ + free_edge_chain (active_edges); + + /* Free all inactive edges. */ + free_edge_chain (inactive_edges); + + /* Delete all htabs. */ + htab_delete (section_map); + htab_delete (function_map); + htab_delete (edge_map); +} + +/* Check if the callgraph is empty. */ +unsigned int +is_callgraph_empty () +{ + if (active_edges == NULL) + return 1; + return 0; +}