blob: 66ef5b33b50a5bf7a607bb7e42befbe0d1a268c9 [file] [log] [blame]
/* Callgraph implementation.
Copyright (C) 2011 Free Software Foundation, Inc.
Contributed by Sriraman Tallam (
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
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 <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <hashtab.h>
#include <string.h>
#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_
} 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;
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;
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;
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. */
map_section_name_to_index (char *section_name, void *handle, int shndx);
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 ();