gcc-4_6/function_reordering_plugin/callgraph.c

   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 #include "callgraph.h"
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <assert.h>
  24 #include <string.h>
  25 #include <hashtab.h>
  26
  27 /*****************************************************************************/
  28 /* section_map hashtable definition and helpers. */
  29
  30 /* Maps section name to its corresponding object handle and section index.  */
  31 static htab_t section_map = NULL;
  32
  33 /* Hashtable helper for section_map htab.  */
  34 static hashval_t
  35 section_map_htab_hash_descriptor (const void *p)
  36 {
  37   const Section_id *s = (const Section_id *)p;
  38   const char *name = s->name;
  39   return htab_hash_string(name);
  40 }
  41
  42 /* Hashtable helper for section_map htab.  */
  43 static int
  44 section_map_htab_eq_descriptor (const void *p1, const void *p2)
  45 {
  46   const Section_id *s1 = (const Section_id *)p1;
  47   const char *c1 = s1->name;
  48   const char *c2 = (const char *)p2;
  49
  50   return (strcmp (c1, c2) == 0);
  51 }
  52 /*****************************************************************************/
  53
  54
  55 /*****************************************************************************/
  56 /* function_map hashtable definition and helpers.
  57    Maps function name to a unique Node.  */
  58 static htab_t function_map = NULL;
  59 static unsigned int last_function_id = 0;
  60
  61 /* Hashtable helper for function_map htab.  */
  62 static hashval_t
  63 function_map_htab_hash_descriptor (const void *p)
  64 {
  65   const Node *s = (const Node *)p;
  66   const char *name = s->name;
  67   return htab_hash_string(name);
  68 }
  69
  70 /* Hashtable helper for section_map htab.  */
  71 static int
  72 function_map_htab_eq_descriptor (const void *p1, const void *p2)
  73 {
  74   const Node *s1 = (const Node *)p1;
  75   const char *c1 = s1->name;
  76   const char *c2 = (const char *)p2;
  77
  78   return (strcmp (c1, c2) == 0);
  79 }
  80 /*****************************************************************************/
  81
  82 /*****************************************************************************/
  83 /* edge_map hashtable definition and helpers.
  84    Maps two node ids to a unique edge.  */
  85 static htab_t edge_map = NULL;
  86
  87 static inline hashval_t
  88 edge_hash_function (unsigned int id1, unsigned int id2)
  89 {
  90   return (id1 << 16) | id2;
  91 }
  92
  93 /* Hashtable helper for edge_map htab.  */
  94 static hashval_t
  95 edge_map_htab_hash_descriptor (const void *p)
  96 {
  97   Edge *e = (Edge *) p;
  98   return edge_hash_function (e->first_function->id, e->second_function->id);
  99 }
 100
 101 /* Hashtable helper for edge_map htab.  */
 102 static int
 103 edge_map_htab_eq_descriptor (const void *p1, const void *p2)
 104 {
 105   Edge *e1 = (Edge *) p1;
 106   Raw_edge *r1 = (Raw_edge *) p2;
 107   return ((e1->first_function->id == r1->n1->id)
 108           && (e1->second_function->id == r1->n2->id));
 109 }
 110
 111
 112 /*****************************************************************************/
 113
 114
 115 /* Keep track of all allocated memory.  */
 116 typedef struct
 117 {
 118   void *ptr;
 119   void *next;
 120 } mm_node;
 121
 122 mm_node *mm_node_chain = NULL;
 123
 124 void
 125 push_allocated_ptr (void *ptr)
 126 {
 127   mm_node *node = XNEW (mm_node);
 128   node->ptr = ptr;
 129   node->next = mm_node_chain;
 130   mm_node_chain = node;
 131 }
 132
 133 /* Chain of all the created nodes.  */
 134 Node *node_chain = NULL;
 135 /* Number of nodes that correspond to functions which will be reordered.  */
 136 unsigned int num_real_nodes = 0;
 137 /* Chain of all edges in the merged callgraph.  */
 138 Edge *active_edges = NULL;
 139 /* Chain of all the merged edges.  */
 140 Edge *inactive_edges = NULL;
 141
 142 /* Initial value of number of functions to allocate hash tables.  */
 143 const int NUM_FUNCTIONS = 100;
 144
 145 /* Reads off the next string from the char stream CONTENTS and updates
 146    READ_LENGTH to the length of the string read.  The value of CONTENTS
 147    is updated to start at the next string.  */
 148
 149 static char *
 150 get_next_string (char **contents, unsigned int *read_length)
 151 {
 152   char *s = *contents;
 153   *read_length = strlen (*contents) + 1;
 154   *contents += *read_length;
 155   return s;
 156 }
 157
 158 /* Add an EDGE to the list of edges in the call graph.  */
 159
 160 static void
 161 add_edge_to_list (Edge *edge)
 162 {
 163   assert (edge != NULL);
 164   edge->next = active_edges;
 165   if (active_edges != NULL)
 166     active_edges->prev = edge;
 167   active_edges = edge;
 168 }
 169
 170 /* Remove the edge from the list of edges in the call graph. This is done
 171    when the nodes corresponding to this edge are merged.  */
 172
 173 static void
 174 remove_edge_from_list (Edge * curr_edge)
 175 {
 176   assert (curr_edge != NULL);
 177   if (curr_edge->prev != NULL)
 178     curr_edge->prev->next = curr_edge->next;
 179   if (curr_edge->next != NULL)
 180     curr_edge->next->prev = curr_edge->prev;
 181   if (active_edges == curr_edge)
 182     active_edges = curr_edge->next;
 183   curr_edge->next = NULL;
 184   curr_edge->prev = NULL;
 185
 186   /* Add to inactive edges to be freed later.  */
 187   curr_edge->next = inactive_edges;
 188   inactive_edges = curr_edge;
 189   return;
 190 }
 191
 192 /* Adds the WEIGHT value to the edge count of CALLER and CALLEE.  */
 193
 194 static void
 195 update_edge (Node *n1, Node *n2, unsigned int weight)
 196 {
 197   void **slot;
 198   Raw_edge re, *r;
 199   Edge *e;
 200
 201   if (n1->id == n2->id)
 202     return;
 203   if (weight == 0)
 204     return;
 205
 206   if (edge_map == NULL)
 207     {
 208       edge_map = htab_create ((NUM_FUNCTIONS * 2),
 209                               edge_map_htab_hash_descriptor,
 210                               edge_map_htab_eq_descriptor , NULL);
 211       assert (edge_map != NULL);
 212     }
 213
 214   r = &re;
 215   init_raw_edge (r, n1, n2);
 216   slot = htab_find_slot_with_hash (edge_map, r,
 217                                    edge_hash_function (r->n1->id, r->n2->id),
 218                                    INSERT);
 219   if (*slot == NULL)
 220     {
 221       e = make_edge (r->n1, r->n2, weight);
 222       *slot = e;
 223       add_edge_to_list (e);
 224     }
 225   else
 226     {
 227       e = *slot;
 228       e->weight += weight;
 229     }
 230 }
 231
 232 /* Create a unique node for a function.  */
 233
 234 static Node *
 235 get_function_node (char *name)
 236 {
 237   void **slot = NULL;
 238   Node *node;
 239
 240   if (function_map == NULL)
 241     {
 242       function_map = htab_create (NUM_FUNCTIONS,
 243                                   function_map_htab_hash_descriptor,
 244                                   function_map_htab_eq_descriptor , NULL);
 245       assert (function_map != NULL);
 246     }
 247
 248   slot = htab_find_slot_with_hash (function_map, name, htab_hash_string (name),
 249                                    INSERT);
 250
 251   if (*slot == NULL)
 252     {
 253       node = make_node (last_function_id, name);
 254       /* Chain the node to the node_chain.  */
 255       node->next = node_chain;
 256       node_chain = node;
 257       *slot = node;
 258       last_function_id++;
 259     }
 260   else
 261     {
 262       node = (Node *)*slot;
 263     }
 264   return node;
 265 }
 266
 267 /* Dumper funcction to print the list of functions that will be considered for
 268    re-ordering.  */
 269
 270 void
 271 dump_functions ()
 272 {
 273   Node *node = node_chain;
 274   while (node)
 275   {
 276     if (node->is_real_node)
 277       fprintf (stderr, "Dumping function %s\n", node->name);
 278     node = node->next;
 279   }
 280 }
 281
 282 /* Dump all the edges existing in the callgraph.  */
 283
 284 void dump_edges (FILE *fp)
 285 {
 286   Edge *it;
 287   for (it = active_edges;
 288        it != NULL;
 289        it = it->next)
 290     {
 291       fprintf (fp,"# %s ---- (%u)---- %s\n",
 292                it->first_function->name,
 293                it->weight,
 294                it->second_function->name);
 295     }
 296 }
 297
 298 /* For file local functions, append a unique identifier corresponding to
 299    the file, FILE_HANDLE, to the NAME to keep the name unique.  */
 300
 301 static char *
 302 canonicalize_function_name (void *file_handle, char *name)
 303 {
 304   /* Number of hexadecimal digits in file_handle, plus length of "0x".  */
 305   const int FILE_HANDLE_LEN = sizeof (void *) * 2 + 2;
 306   char *canonical_name;
 307
 308   /* File local functions have _ZL prefix in the mangled name.  */
 309   /* XXX: Handle file local functions exhaustively, like functions in
 310      anonymous name spaces.  */
 311   if (!is_prefix_of ("_ZL", name))
 312     return name;
 313
 314   XNEWVEC_ALLOC (canonical_name, char, (strlen(name) + FILE_HANDLE_LEN + 2));
 315   sprintf (canonical_name, "%s.%p", name, file_handle);
 316   return canonical_name;
 317 }
 318
 319 /* Parse the section contents of ".gnu.callgraph.text"  sections and create
 320    call graph edges with appropriate weights. The section contents have the
 321    following format :
 322    Function  <caller_name>
 323    <callee_1>
 324    <edge count between caller and callee_1>
 325    <callee_2>
 326    <edge count between caller and callee_2>
 327    ....  */
 328 void
 329 parse_callgraph_section_contents (void *file_handle,
 330                                   unsigned char *section_contents,
 331                                   unsigned int length)
 332 {
 333   char *contents;
 334   char *caller;
 335   unsigned int read_length = 0, curr_length = 0;
 336   Node *caller_node;
 337
 338   /* HEADER_LEN is the length of string 'Function '.  */
 339   const int HEADER_LEN = 9;
 340
 341    /* First string in contents is 'Function <function-name>'.  */
 342   assert (length > 0);
 343   contents = (char*) (section_contents);
 344   caller = get_next_string (&contents, &read_length);
 345   assert (read_length > HEADER_LEN);
 346   caller = canonicalize_function_name (file_handle, caller + HEADER_LEN);
 347   curr_length = read_length;
 348   caller_node = get_function_node (caller);
 349
 350   while (curr_length < length)
 351     {
 352       /* Read callee, weight tuples.  */
 353       char *callee;
 354       char *weight_str;
 355       unsigned int weight;
 356       Node *callee_node;
 357
 358       callee = get_next_string (&contents, &read_length);
 359       callee = canonicalize_function_name (file_handle, callee);
 360       curr_length += read_length;
 361       callee_node = get_function_node (callee);
 362
 363       assert (curr_length < length);
 364       weight_str = get_next_string (&contents, &read_length);
 365       weight = atoi (weight_str);
 366       curr_length += read_length;
 367       update_edge (caller_node, callee_node, weight);
 368     }
 369 }
 370
 371 /* Traverse the list of edges and find the edge with the maximum weight.  */
 372
 373 static Edge *
 374 find_max_edge ()
 375 {
 376   Edge *it, *max_edge;
 377
 378   if (active_edges == NULL)
 379     return NULL;
 380
 381   max_edge = active_edges;
 382   assert (!active_edges->is_merged);
 383
 384   it = active_edges->next;
 385   for (;it != NULL; it = it->next)
 386     {
 387       assert (!it->is_merged);
 388       if (edge_lower (max_edge , it))
 389           max_edge = it;
 390     }
 391
 392   return max_edge;
 393 }
 394
 395 /* Change the EDGE from OLD_NODE to KEPT_NODE to be between NEW_NODE
 396    and KEPT_NODE.  */
 397
 398 static void
 399 merge_edge (Edge *edge, Node *new_node, Node *old_node,
 400             Node *kept_node)
 401 {
 402   void **slot;
 403   Raw_edge re, *r;
 404
 405   r = &re;
 406   init_raw_edge (r, new_node, kept_node);
 407   slot = htab_find_slot_with_hash (edge_map, r,
 408                                    edge_hash_function (r->n1->id, r->n2->id),
 409                                    INSERT);
 410
 411   if (*slot == NULL)
 412     {
 413       reset_functions (edge, new_node, kept_node);
 414       *slot = edge;
 415       add_edge_to_node (new_node, edge);
 416     }
 417   else
 418     {
 419       Edge *new_edge = *slot;
 420       new_edge->weight += edge->weight;
 421       edge->is_merged = 1;
 422       remove_edge_from_list (edge);
 423     }
 424 }
 425
 426 /* Merge the two nodes in this EDGE. The new node's edges are the union of
 427    the edges of the original nodes.  */
 428
 429 static void
 430 collapse_edge (Edge * edge)
 431 {
 432   Edge_list *it;
 433   Node *kept_node = edge->first_function;
 434   Node *merged_node = edge->second_function;
 435
 436   /* Go through all merged_node edges and merge with kept_node.  */
 437   for (it = merged_node->edge_list; it != NULL; it = it->next)
 438     {
 439       Node *other_node = NULL;
 440       Edge *this_edge = it->edge;
 441       if (this_edge->is_merged)
 442         continue;
 443       if (this_edge == edge)
 444         continue;
 445       assert (this_edge->first_function->id == merged_node->id
 446               || this_edge->second_function->id == merged_node->id);
 447       other_node = (this_edge->first_function->id
 448                     == merged_node->id)
 449                    ? this_edge->second_function
 450                    : this_edge->first_function;
 451       merge_edge (this_edge, kept_node, merged_node, other_node);
 452     }
 453
 454   merge_node (kept_node, merged_node);
 455   edge->is_merged = 1;
 456   remove_edge_from_list (edge);
 457 }
 458
 459 /* Make node N a real node if it can be reordered, that is, its .text
 460    section is available.  */
 461 static void set_node_type (Node *n)
 462 {
 463   void *slot;
 464   char *name = n->name;
 465   slot = htab_find_with_hash (section_map, name, htab_hash_string (name));
 466   if (slot != NULL)
 467     {
 468       set_as_real_node (n);
 469       num_real_nodes++;
 470     }
 471 }
 472
 473 void
 474 find_pettis_hansen_function_layout (FILE *fp)
 475 {
 476   Node *n_it;
 477   Edge *it;
 478
 479   assert (node_chain != NULL);
 480   assert (active_edges != NULL);
 481   if (fp != NULL)
 482     dump_edges (fp);
 483
 484   /* Go over all the nodes and set it as real node only if a corresponding
 485      function section exists.  */
 486   for (n_it = node_chain; n_it != NULL; n_it = n_it->next)
 487     set_node_type (n_it);
 488
 489   /* Set edge types. A WEAK_EDGE has one of its nodes corresponding to a
 490      function that cannot be re-ordered.  */
 491   for (it = active_edges; it != NULL; it = it->next)
 492     set_edge_type (it);
 493
 494   it = find_max_edge ();
 495   while (it != NULL)
 496     {
 497       collapse_edge (it);
 498       it = find_max_edge ();
 499     }
 500 }
 501
 502 /* The list of sections created, excluding comdat duplicates.  */
 503 Section_id *first_section = NULL;
 504 /* The number of sections.  */
 505 int num_sections = 0;
 506
 507 const int NUM_SECTION_TYPES = 5;
 508 const char *section_types[] = {".text.hot.",
 509                                 ".text.cold.",
 510                                 ".text.unlikely.",
 511                                 ".text.startup.",
 512                                 ".text." };
 513
 514 /* For sections that are not in the callgraph, the priority gives the
 515    order in which the sections should be laid out.  Sections are grouped
 516    according to priority, higher priority (lower number), and then laid
 517    out in priority order.  */
 518 const int section_priority[] = {0, 3, 4, 2, 1};
 519
 520 /* Maps the function name corresponding to section SECTION_NAME to the
 521    object handle and the section index.  */
 522
 523 void
 524 map_section_name_to_index (char *section_name, void *handle, int shndx)
 525 {
 526   void **slot;
 527   char *function_name = NULL;
 528   int i, section_type = -1;
 529
 530   for (i = 0; i < ARRAY_SIZE (section_types); ++i)
 531     {
 532       if (is_prefix_of (section_types[i], section_name))
 533         {
 534           function_name = section_name + strlen (section_types[i]);
 535           section_type = i;
 536           break;
 537         }
 538     }
 539
 540   assert (function_name != NULL && section_type >= 0);
 541   function_name = canonicalize_function_name (handle, function_name);
 542   num_sections++;
 543
 544   /* Allocate section_map.  */
 545   if (section_map == NULL)
 546     {
 547       section_map = htab_create (NUM_FUNCTIONS,
 548                                  section_map_htab_hash_descriptor,
 549                                  section_map_htab_eq_descriptor , NULL);
 550       assert (section_map != NULL);
 551     }
 552
 553   slot = htab_find_slot_with_hash (section_map, function_name,
 554                                    htab_hash_string (function_name),
 555                                    INSERT);
 556   if (*slot == NULL)
 557     {
 558       Section_id *section = make_section_id (function_name, section_name,
 559                                              section_type, handle, shndx);
 560       /* Chain it to the list of sections.  */
 561       section->next = first_section;
 562       first_section = section;
 563       *slot = section;
 564     }
 565   else
 566     {
 567       /* The function already exists, it must be a COMDAT.  Only one section
 568          in the comdat group will be kept, we don't know which.  Chain all the
 569          comdat sections in the same comdat group to be emitted together later.
 570          Keep one section as representative (kept) and update its section_type
 571          to be equal to the type of the highest priority section in the
 572          group.  */
 573       Section_id *kept = (Section_id *)(*slot);
 574       Section_id *section = make_section_id (function_name, section_name,
 575                                              section_type, handle, shndx);
 576
 577       /* Two comdats in the same group can have different priorities.  This
 578          ensures that the "kept" comdat section has the priority of the higest
 579          section in that comdat group.   This is necessary because the plugin
 580          does not know which section will be kept.  */
 581       if (section_priority[kept->section_type]
 582           > section_priority[section_type])
 583         kept->section_type = section_type;
 584
 585       section->comdat_group = kept->comdat_group;
 586       kept->comdat_group = section;
 587     }
 588 }
 589
 590 /* If SECN is NULL find the section corresponding to function name NAME.
 591    If it is a comdat, get all the comdat sections in the group.  Chain these
 592    sections to SECTION_END.  Set SECTION_START if it is NULL.  */
 593
 594 static void
 595 write_out_node (Section_id *s, Section_id **section_start,
 596                 Section_id **section_end)
 597 {
 598   assert (s != NULL);
 599   s->processed = 1;
 600   if (*section_start == NULL)
 601     {
 602       *section_start = s;
 603       *section_end = s;
 604     }
 605   else
 606     {
 607       (*section_end)->group = s;
 608       *section_end = s;
 609     }
 610
 611   /* Print all other sections in the same comdat group.  */
 612   while (s->comdat_group)
 613     {
 614       s = s->comdat_group;
 615       s->processed = 1;
 616       (*section_end)->group = s;
 617       *section_end = s;
 618     }
 619 }
 620
 621 /* Visit each node and print the chain of merged nodes to the file.  Update
 622    HANDLES and SHNDX to contain the ordered list of sections.  */
 623
 624 unsigned int
 625 get_layout (FILE *fp, void*** handles,
 626             unsigned int** shndx)
 627 {
 628   Node *n_it;
 629   int  i = 0;
 630   int position;
 631   void *slot;
 632
 633   /* Form NUM_SECTION_TYPES + 1 groups of sections.  Index 0 corresponds
 634      to the list of sections that correspond to functions in the callgraph.
 635      For other sections, they are grouped by section_type and stored in
 636      index: (section_type + 1).   SECTION_START points to the first
 637      section in each section group and SECTION_END points to the last.  */
 638   Section_id *section_start[NUM_SECTION_TYPES + 1];
 639   Section_id *section_end[NUM_SECTION_TYPES + 1];
 640   Section_id *s_it;
 641
 642   XNEWVEC_ALLOC (*handles, void *, num_sections);
 643   XNEWVEC_ALLOC (*shndx, unsigned int, num_sections);
 644
 645   for (i = 0; i < NUM_SECTION_TYPES + 1; i++)
 646     {
 647       section_start[i] = NULL;
 648       section_end[i] = NULL;
 649     }
 650
 651   /* Dump edges to the final reordering file.  */
 652   for (n_it = node_chain; n_it != NULL; n_it = n_it->next)
 653     {
 654       Section_id *s;
 655       Node *node;
 656       /* First, only consider nodes that are real and that have other
 657          nodes merged with it. */
 658       if (n_it->is_merged || !n_it->is_real_node || !n_it->merge_next)
 659         continue;
 660
 661       slot = htab_find_with_hash (section_map, n_it->name,
 662                                   htab_hash_string (n_it->name));
 663       assert (slot != NULL);
 664       s = (Section_id *)slot;
 665       write_out_node (s, &section_start[0], &section_end[0]);
 666
 667       if (fp)
 668         fprintf (fp, "# Callgraph group : %s", n_it->name);
 669
 670       node = n_it->merge_next;
 671       while (node != NULL)
 672         {
 673           if (node->is_real_node)
 674             {
 675               slot = htab_find_with_hash (section_map, node->name,
 676                                           htab_hash_string (node->name));
 677               assert (slot != NULL);
 678               s = (Section_id *)slot;
 679               write_out_node (s, &section_start[0],
 680                               &section_end[0]);
 681               if (fp)
 682                 fprintf (fp, " %s", node->name);
 683             }
 684           node = node->merge_next;
 685         }
 686
 687       if (fp)
 688         fprintf (fp, "\n");
 689     }
 690
 691   /* Go through all the sections and sort unprocessed sections into different
 692      section_type groups.  */
 693   s_it = first_section;
 694   while (s_it)
 695     {
 696       if (!s_it->processed)
 697         write_out_node (s_it, &section_start[s_it->section_type + 1],
 698                         &section_end[s_it->section_type + 1]);
 699       s_it = s_it->next;
 700     }
 701
 702
 703   position = 0;
 704   for (i = 0; i < NUM_SECTION_TYPES + 1; ++i)
 705     {
 706       s_it = section_start[i];
 707       while (s_it)
 708         {
 709           assert (position < num_sections);
 710           (*handles)[position] = s_it->handle;
 711           (*shndx)[position] = s_it->shndx;
 712           position++;
 713           if (fp != NULL)
 714             fprintf (fp, "%s\n", s_it->full_name);
 715           s_it = s_it->group;
 716         }
 717     }
 718   return position;
 719 }
 720
 721 void
 722 cleanup ()
 723 {
 724   /* Go through heap allocated objects and free them.  */
 725   while (mm_node_chain)
 726     {
 727       mm_node *node = mm_node_chain;
 728       free (node->ptr);
 729       mm_node_chain = node->next;
 730       free (node);
 731     }
 732
 733   /*  Delete all htabs. */
 734   htab_delete (section_map);
 735   htab_delete (function_map);
 736   htab_delete (edge_map);
 737 }
 738
 739 /* Check if the callgraph is empty.  */
 740 unsigned int
 741 is_callgraph_empty ()
 742 {
 743   if (active_edges == NULL)
 744     return 1;
 745   return 0;
 746 }