diff options
Diffstat (limited to 'gcc-4.9/function_reordering_plugin/callgraph.h')
| -rw-r--r-- | gcc-4.9/function_reordering_plugin/callgraph.h | 318 |
1 files changed, 318 insertions, 0 deletions
diff --git a/gcc-4.9/function_reordering_plugin/callgraph.h b/gcc-4.9/function_reordering_plugin/callgraph.h new file mode 100644 index 000000000..5d6e1e24d --- /dev/null +++ b/gcc-4.9/function_reordering_plugin/callgraph.h @@ -0,0 +1,318 @@ +/* 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 |