gcc-4_6/function_reordering_plugin/callgraph.h

   1 /* Callgraph implementation.
   2    Copyright (C) 2011 Free Software Foundation, Inc.
   3    Contributed by Sriraman Tallam (tmsriram@google.com)
   4    and Easwaran Raman (eraman@google.com).
   5
   6 This program is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 3, or (at your option)
   9 any later version.
  10
  11 This program is distributed in the hope that it will be useful, but
  12 WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with this program; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #ifndef CALLGRAPH_H
  21 #define CALLGRAPH_H
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <assert.h>
  26 #include <hashtab.h>
  27 #include <string.h>
  28 #include "libiberty.h"
  29
  30 /* All heap allocations are tracked to be cleaned up later.  */
  31 #define XNEW_ALLOC(A, T)        A = XNEW (T); push_allocated_ptr (A);
  32 #define XNEWVEC_ALLOC(A, T, N)  A = XNEWVEC (T,N); push_allocated_ptr (A);
  33
  34 /* Push a pointer that should be freed after the plugin is done.  */
  35 void push_allocated_ptr (void *ptr);
  36
  37 struct edge_d;
  38 typedef struct edge_d Edge;
  39
  40 /* Maintain a list of edges.  */
  41 typedef struct edge_list_d
  42 {
  43   Edge *edge;
  44   struct edge_list_d *next;
  45   struct edge_list_d *prev;
  46 } Edge_list;
  47
  48 inline static Edge_list *
  49 make_edge_list (Edge *e)
  50 {
  51   Edge_list *list;
  52   XNEW_ALLOC (list, Edge_list);
  53   list->edge = e;
  54   list->next = NULL;
  55   list->prev = NULL;
  56   return list;
  57 }
  58
  59 /* Represents a node in the call graph. */
  60 typedef struct node_d
  61 {
  62   unsigned int id;
  63   char *name;
  64   /* Chain all the Nodes created.  */
  65   struct node_d *next;
  66   /* Pointer to the next node in the chain of merged nodes.  */
  67   struct node_d *merge_next;
  68   /* List of all edges with this node.  */
  69   Edge_list *edge_list;
  70   /* Pointer to the last node in the chain of merged nodes.  */
  71   struct node_d *last_merge_node;
  72   unsigned int is_merged;
  73   /* 1 if the function corresponding to this node can be re-ordered.  */
  74   unsigned int is_real_node;
  75 } Node;
  76
  77 inline static Node *
  78 make_node (unsigned int id, char *name)
  79 {
  80   Node *node;
  81   XNEW_ALLOC (node, Node);
  82   node->id = id;
  83   node->name = name;
  84   node->is_real_node = 0;
  85   node->next = NULL;
  86   node->edge_list = NULL;
  87   node->last_merge_node = node;
  88   node->is_merged = 0;
  89   node->merge_next = NULL;
  90   return node;
  91 }
  92
  93 /* Chain the nodes that are merged. Maintain a pointer to the last
  94    node in the chain.  After merging at the end, the last node in the
  95    current chain is the last node in the chain of the merged node.  */
  96 inline static void
  97 merge_node (Node *merger, Node *mergee)
  98 {
  99   merger->last_merge_node->merge_next = mergee;
 100   merger->last_merge_node = mergee->last_merge_node;
 101   mergee->is_merged = 1;
 102 }
 103
 104 inline static void
 105 add_edge_to_node (Node *n, Edge *e)
 106 {
 107   Edge_list *list;
 108   assert (n != NULL && e != NULL);
 109   list = make_edge_list (e);
 110   list->next = n->edge_list;
 111   if (n->edge_list != NULL)
 112     n->edge_list->prev = list;
 113   n->edge_list = list;
 114 }
 115
 116 /* A node is real only if the function can be reordered.  */
 117 inline static void
 118 set_as_real_node (Node *node)
 119 {
 120   node->is_real_node = 1;
 121 }
 122
 123 /* WEAK if one of the nodes is not real. STRONG if both
 124    nodes are real.  */
 125 typedef enum edge_type_
 126 {
 127   STRONG_EDGE = 0,
 128   WEAK_EDGE
 129 } Edge_type;
 130
 131 /*Represents an edge in the call graph.  */
 132 struct edge_d
 133 {
 134   Node *first_function;
 135   Node *second_function;
 136   unsigned int weight;
 137   Edge_type type;
 138   /* 1 if the nodes corresponding to this edge have been merged.  */
 139   unsigned int is_merged;
 140   /* Doubly linked chain of created edges.  */
 141   struct edge_d *prev;
 142   struct edge_d *next;
 143 };
 144
 145 inline static Edge *
 146 make_edge (Node *first, Node *second, unsigned int weight)
 147 {
 148   Edge *edge;
 149   XNEW_ALLOC (edge, Edge);
 150   edge->first_function = first;
 151   edge->second_function = second;
 152   edge->weight = weight;
 153   edge->type = WEAK_EDGE;
 154   edge->is_merged = 0;
 155   edge->prev = NULL;
 156   edge->next = NULL;
 157   add_edge_to_node (first, edge);
 158   add_edge_to_node (second, edge);
 159   return edge;
 160 }
 161
 162 inline static void
 163 set_edge_type (Edge *edge)
 164 {
 165   if (edge->first_function->is_real_node
 166       && edge->second_function->is_real_node)
 167     edge->type = STRONG_EDGE;
 168   else
 169     edge->type = WEAK_EDGE;
 170 }
 171
 172 inline static unsigned int
 173 edge_lower (Edge *e1, Edge *e2)
 174 {
 175   if (e1->type == e2->type)
 176     return (e1->weight < e2->weight) ? 1 : 0;
 177   if (e1->type == STRONG_EDGE)
 178     return 0;
 179   return 1;
 180 }
 181
 182 inline static void
 183 reset_functions (Edge *e, Node *n1, Node *n2)
 184 {
 185   /* No self edges.  */
 186   assert (n1->id != n2->id);
 187   if (n1->id < n2->id)
 188     {
 189       e->first_function = n1;
 190       e->second_function = n2;
 191     }
 192   else
 193     {
 194       e->first_function = n2;
 195       e->second_function = n1;
 196     }
 197 }
 198
 199 /* A Section is represented by its object handle and the section index. */
 200 typedef struct section_id_
 201 {
 202   /* Name of the function.  */
 203   char *name;
 204   /* Full name of the section.  */
 205   char *full_name;
 206   void *handle;
 207   int shndx;
 208   /* Type of prefix in section name.  */
 209   int section_type;
 210   /* Pointer to the next section in the same comdat_group.  */
 211   struct section_id_ *comdat_group;
 212   /* Chain all the sections created.  */
 213   struct section_id_ *next;
 214   /* Used for grouping sections.  */
 215   struct section_id_ *group;
 216   /* Check if this section has been considered for output.  */
 217   char processed;
 218 } Section_id;
 219
 220 inline static Section_id *
 221 make_section_id (char *name, char *full_name,
 222                  int section_type,
 223                  void *handle, int shndx)
 224 {
 225   Section_id *s;
 226   XNEW_ALLOC (s, Section_id);
 227   s->name = name;
 228   s->full_name = full_name;
 229   s->section_type = section_type;
 230   s->handle = handle;
 231   s->shndx = shndx;
 232   s->comdat_group = NULL;
 233   s->next = NULL;
 234   s->group = NULL;
 235   s->processed = 0;
 236
 237   return s;
 238 }
 239
 240 /* A pair of nodes make a raw edge.  Also, N1->id < N2->id.  */
 241 typedef struct
 242 {
 243   Node *n1;
 244   Node *n2;
 245 } Raw_edge;
 246
 247 inline static void
 248 init_raw_edge (Raw_edge *r, Node *n1, Node *n2)
 249 {
 250   assert (n1 ->id != n2->id);
 251   if (n1->id < n2->id)
 252     {
 253       r->n1 = n1;
 254       r->n2 = n2;
 255     }
 256   else
 257     {
 258       r->n1 = n2;
 259       r->n2 = n1;
 260     }
 261 }
 262
 263 inline static int is_prefix_of (const char *prefix, const char *str)
 264 {
 265   return strncmp (prefix, str, strlen (prefix)) == 0;
 266 }
 267
 268 /* Maps the function corresponding to section name to its
 269    corresponding object handle and the section index.  */
 270 void
 271 map_section_name_to_index (char *section_name, void *handle, int shndx);
 272
 273 void
 274 parse_callgraph_section_contents (void *handle,
 275                                   unsigned char *section_contents,
 276                                   unsigned int length);
 277
 278 void dump_functions ();
 279 void dump_edges ();
 280 void find_pettis_hansen_function_layout (FILE *fp);
 281
 282 unsigned int get_layout (FILE *fp, void*** handles,
 283                          unsigned int** shndx);
 284
 285 void cleanup ();
 286 /* Returns 1 if callgraph is empty.  */
 287 unsigned int is_callgraph_empty ();
 288 #endif