| /* 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) |
| { |
| return (id1 << 16) | 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; |
| |
| /* Initial value of number of functions to allocate hash tables. */ |
| const int NUM_FUNCTIONS = 100; |
| |
| /* 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 ((NUM_FUNCTIONS * 2), |
| 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 (NUM_FUNCTIONS, |
| 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); |
| 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_with_hash (section_map, name, htab_hash_string (name)); |
| 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 (NUM_FUNCTIONS, |
| 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_with_hash (section_map, name, htab_hash_string (name)); |
| if (slot != NULL) |
| { |
| Section_id *s = (Section_id *)slot; |
| handles[position] = s->handle; |
| shndx[position] = s->shndx; |
| fprintf (fp, "%s\n", s->full_name); |
| /* No more use of full_name */ |
| free (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; |
| } |
| } |
| 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; |
| } |