| /* Callgraph implementation. |
| Copyright (C) 2011 Free Software Foundation, Inc. |
| Contributed by Sriraman Tallam (tmsriram@google.com) |
| and Easwaran Raman (eraman@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> |
| #include "libiberty.h" |
| |
| /* All heap allocations are tracked to be cleaned up later. */ |
| #define XNEW_ALLOC(A, T) A = XNEW (T); push_allocated_ptr (A); |
| #define XNEWVEC_ALLOC(A, T, N) A = XNEWVEC (T,N); push_allocated_ptr (A); |
| |
| /* Push a pointer that should be freed after the plugin is done. */ |
| void push_allocated_ptr (void *ptr); |
| |
| 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_ALLOC (list, 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; |
| /* Node weight, execution count of entry bb. */ |
| unsigned long long weight; |
| /* Weight computed by adding weights of incoming edges to |
| this node. */ |
| unsigned long long computed_weight; |
| /* Max count of any bb executed. */ |
| unsigned long long max_count; |
| /* Stores the max count of any bb in the split cold section. */ |
| unsigned long long split_weight; |
| /* 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_ALLOC (node, Node); |
| node->id = id; |
| node->name = name; |
| node->weight = 0; |
| node->computed_weight = 0; |
| node->max_count = 0; |
| node->split_weight = 0; |
| 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 long long 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 long long weight) |
| { |
| Edge *edge; |
| XNEW_ALLOC (edge, 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 section_id_ |
| { |
| /* Name of the function. */ |
| char *name; |
| /* Full name of the section. */ |
| char *full_name; |
| void *handle; |
| int shndx; |
| /* Corresponds to node weight. */ |
| unsigned long long weight; |
| /* Corresponds to node's computed weight. */ |
| unsigned long long computed_weight; |
| /* Max count of bb executed in this function. */ |
| unsigned long long max_count; |
| /* Type of prefix in section name. */ |
| int section_type; |
| /* Pointer to the next section in the same comdat_group. */ |
| struct section_id_ *comdat_group; |
| /* Chain all the sections created. */ |
| struct section_id_ *next; |
| /* Used for grouping sections. */ |
| struct section_id_ *group; |
| /* Pointer to the cold split section if any. If this function |
| is comdat hot and kept, pointer to the kept cold split |
| section. */ |
| struct section_id_ *split_section; |
| /* If this is the cold part of a split section. */ |
| char is_split_cold_section; |
| /* Check if this section has been considered for output. */ |
| char processed; |
| } Section_id; |
| |
| inline static Section_id * |
| make_section_id (char *name, char *full_name, |
| int section_type, |
| void *handle, int shndx) |
| { |
| Section_id *s; |
| XNEW_ALLOC (s, Section_id); |
| s->name = name; |
| s->full_name = full_name; |
| s->section_type = section_type; |
| s->handle = handle; |
| s->shndx = shndx; |
| s->comdat_group = NULL; |
| s->next = NULL; |
| s->group = NULL; |
| s->processed = 0; |
| s->weight = 0; |
| s->computed_weight = 0; |
| s->max_count = 0; |
| s->split_section = NULL; |
| s->is_split_cold_section = 0; |
| |
| 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 (void *handle, |
| 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 |