function_reordering_plugin/callgraph.c

/* 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/>.  */

#include "callgraph.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <hashtab.h>

/*****************************************************************************/
/* section_map hashtable definition and helpers. */

/* Maps section name to its corresponding object handle and section index.  */
static htab_t section_map = NULL;

/* Hashtable helper for section_map htab.  */
static hashval_t
section_map_htab_hash_descriptor (const void *p)
{
  const Section_id *s = (const Section_id *)p;
  const char *name = s->name;
  return htab_hash_string(name);
}

/* Hashtable helper for section_map htab.  */
static int
section_map_htab_eq_descriptor (const void *p1, const void *p2)
{
  const Section_id *s1 = (const Section_id *)p1;
  const char *c1 = s1->name;
  const char *c2 = (const char *)p2;

  return (strcmp (c1, c2) == 0);
}
/*****************************************************************************/


/*****************************************************************************/
/* function_map hashtable definition and helpers.
   Maps function name to a unique Node.  */
static htab_t function_map = NULL;
static unsigned int last_function_id = 0;

/* Hashtable helper for function_map htab.  */
static hashval_t
function_map_htab_hash_descriptor (const void *p)
{
  const Node *s = (const Node *)p;
  const char *name = s->name;
  return htab_hash_string(name);
}

/* Hashtable helper for section_map htab.  */
static int
function_map_htab_eq_descriptor (const void *p1, const void *p2)
{
  const Node *s1 = (const Node *)p1;
  const char *c1 = s1->name;
  const char *c2 = (const char *)p2;

  return (strcmp (c1, c2) == 0);
}
/*****************************************************************************/

/*****************************************************************************/
/* edge_map hashtable definition and helpers.
   Maps two node ids to a unique edge.  */
static htab_t edge_map = NULL;

static inline hashval_t
edge_hash_function (unsigned int id1, unsigned int id2)
{
  return (id1 << 16) | id2;
}

/* Hashtable helper for edge_map htab.  */
static hashval_t
edge_map_htab_hash_descriptor (const void *p)
{
  Edge *e = (Edge *) p;
  return edge_hash_function (e->first_function->id, e->second_function->id);
}

/* Hashtable helper for edge_map htab.  */
static int
edge_map_htab_eq_descriptor (const void *p1, const void *p2)
{
  Edge *e1 = (Edge *) p1;
  Raw_edge *r1 = (Raw_edge *) p2;
  return ((e1->first_function->id == r1->n1->id)
	  && (e1->second_function->id == r1->n2->id));
}


/*****************************************************************************/


/* Keep track of all allocated memory.  */
typedef struct
{
  void *ptr;
  void *next;
} mm_node;

mm_node *mm_node_chain = NULL;

void
push_allocated_ptr (void *ptr)
{
  mm_node *node = XNEW (mm_node);
  node->ptr = ptr;
  node->next = mm_node_chain;
  mm_node_chain = node;
}

/* Chain of all the created nodes.  */
Node *node_chain = NULL;
/* Number of nodes that correspond to functions which will be reordered.  */
unsigned int num_real_nodes = 0;
/* Chain of all edges in the merged callgraph.  */
Edge *active_edges = NULL;
/* Chain of all the merged edges.  */
Edge *inactive_edges = NULL;

/* Initial value of number of functions to allocate hash tables.  */
const int NUM_FUNCTIONS = 100;

/* Reads off the next string from the char stream CONTENTS and updates
   READ_LENGTH to the length of the string read.  The value of CONTENTS
   is updated to start at the next string.   UPDATE_CONTENTS tells if
   CONTENTS must be moved past the read string to the next string.  To
   peek at the string, UPDATE_CONTENTS can be set to false.  */

static char *
get_next_string (char **contents, unsigned int *read_length,
		 int update_contents)
{
  char *s = *contents;
  *read_length = strlen (*contents) + 1;
  if (update_contents)
    *contents += *read_length;
  return s;
}

/* Add an EDGE to the list of edges in the call graph.  */

static void
add_edge_to_list (Edge *edge)
{
  assert (edge != NULL);
  edge->next = active_edges;
  if (active_edges != NULL)
    active_edges->prev = edge;
  active_edges = edge;
}

/* Remove the edge from the list of edges in the call graph. This is done
   when the nodes corresponding to this edge are merged.  */

static void
remove_edge_from_list (Edge * curr_edge)
{
  assert (curr_edge != NULL);
  if (curr_edge->prev != NULL)
    curr_edge->prev->next = curr_edge->next;
  if (curr_edge->next != NULL)
    curr_edge->next->prev = curr_edge->prev;
  if (active_edges == curr_edge)
    active_edges = curr_edge->next;
  curr_edge->next = NULL;
  curr_edge->prev = NULL;

  /* Add to inactive edges to be freed later.  */
  curr_edge->next = inactive_edges;
  inactive_edges = curr_edge;
  return;
}

/* Adds the WEIGHT value to the edge count of CALLER and CALLEE.  */

static void
update_edge (Node *n1, Node *n2, unsigned long long weight)
{
  void **slot;
  Raw_edge re, *r;
  Edge *e;

  if (n1->id == n2->id)
    return;
  if (weight == 0)
    return;

  if (edge_map == NULL)
    {
      edge_map = htab_create ((NUM_FUNCTIONS * 2),
			      edge_map_htab_hash_descriptor,
			      edge_map_htab_eq_descriptor , NULL);
      assert (edge_map != NULL);
    }

  r = &re;
  init_raw_edge (r, n1, n2);
  slot = htab_find_slot_with_hash (edge_map, r,
				   edge_hash_function (r->n1->id, r->n2->id),
				   INSERT);
  if (*slot == NULL)
    {
      e = make_edge (r->n1, r->n2, weight);
      *slot = e;
      add_edge_to_list (e);
    }
  else
    {
      e = *slot;
      e->weight += weight;
    }
  /* Update the computed node weight for n2,  which is the sum of its incoming
     edge weights.  */
  n2->computed_weight += weight;
}

/* Create a unique node for a function.  */

static Node *
get_function_node (char *name)
{
  void **slot = NULL;
  Node *node;

  if (function_map == NULL)
    {
      function_map = htab_create (NUM_FUNCTIONS,
				  function_map_htab_hash_descriptor,
				  function_map_htab_eq_descriptor , NULL);
      assert (function_map != NULL);
    }

  slot = htab_find_slot_with_hash (function_map, name, htab_hash_string (name),
				   INSERT);

  if (*slot == NULL)
    {
      node = make_node (last_function_id, name);
      /* Chain the node to the node_chain.  */
      node->next = node_chain;
      node_chain = node;
      *slot = node;
      last_function_id++;
    }
  else
    {
      node = (Node *)*slot;
    }
  return node;
}

/* Dumper funcction to print the list of functions that will be considered for
   re-ordering.  */

void
dump_functions ()
{
  Node *node = node_chain;
  while (node)
  {
    if (node->is_real_node)
      fprintf (stderr, "Dumping function %s\n", node->name);
    node = node->next;
  }
}

/* Dump all the edges existing in the callgraph.  */

void dump_edges (FILE *fp)
{
  Edge *it;
  for (it = active_edges;
       it != NULL;
       it = it->next)
    {
      fprintf (fp,"# %s (%llu, %llu) ---- (%llu)---- %s (%llu, %llu)\n",
               it->first_function->name,
	       it->first_function->weight,
	       it->first_function->computed_weight,
	       it->weight,
               it->second_function->name,
	       it->second_function->weight,
	       it->second_function->computed_weight);
    }
}

/* For file local functions, append a unique identifier corresponding to
   the file, FILE_HANDLE, to the NAME to keep the name unique.  */

static char *
canonicalize_function_name (void *file_handle, char *name)
{
  /* Number of hexadecimal digits in file_handle, plus length of "0x".  */
  const int FILE_HANDLE_LEN = sizeof (void *) * 2 + 2;
  char *canonical_name;

  /* File local functions have _ZL prefix in the mangled name.  */
  /* XXX: Handle file local functions exhaustively, like functions in
     anonymous name spaces.  */
  if (!is_prefix_of ("_ZL", name))
    return name;

  XNEWVEC_ALLOC (canonical_name, char, (strlen(name) + FILE_HANDLE_LEN + 2));
  sprintf (canonical_name, "%s.%p", name, file_handle);
  return canonical_name;
}

/* Parse the section contents of ".gnu.callgraph.text"  sections and create
   call graph edges with appropriate weights. The section contents have the
   following format :
   Function  <caller_name>
   Weight <entry_count> <max_count> (optional line)
   ColdWeight <max_count> (optional line)
   <callee_1>
   <edge count between caller and callee_1>
   <callee_2>
   <edge count between caller and callee_2>
   ....  */
void
parse_callgraph_section_contents (void *file_handle,
				  unsigned char *section_contents,
				  unsigned int length)
{
  char *contents;
  char *caller;
  char *node_weight_s = NULL;
  unsigned int read_length = 0, curr_length = 0;
  Node *caller_node;

  /* HEADER_LEN is the length of string 'Function '.  */
  const int HEADER_LEN = 9;

  /* Prefix of line containing node weights.  */
  const char *NODE_WEIGHT_PREFIX = "Weight ";
  /* Prefix of line containing max bb count of cold split part.  */
  const char *SPLIT_FUNCTION_PREFIX = "ColdWeight ";

  /* First string in contents is 'Function <function-name>'.  */
  assert (length > 0);
  contents = (char*) (section_contents);
  caller = get_next_string (&contents, &read_length, 1);
  assert (read_length > HEADER_LEN);
  caller = canonicalize_function_name (file_handle, caller + HEADER_LEN);
  curr_length = read_length;
  caller_node = get_function_node (caller);

  /* Check if next string is a node weight, which has the format
     "Weight <entry_count> <max_count>".  We could have callgraph
     sections with or without node weights.  */

  /* Peek at the next string.  */
  if (curr_length < length)
    node_weight_s = get_next_string (&contents, &read_length, 0);
  if (node_weight_s != NULL
      && is_prefix_of (NODE_WEIGHT_PREFIX, node_weight_s))
    {
      char *max_count_s;
      unsigned long long max_count;
      unsigned long long node_weight
	= atoll (node_weight_s + strlen (NODE_WEIGHT_PREFIX));
      /* Functions like comdats only have one caller_node and can
	 have multiple node weights from multiple modules.  */
      caller_node->weight += node_weight;

      /* Find the space and get the max_count.  */
      max_count_s = strstr (node_weight_s + strlen (NODE_WEIGHT_PREFIX), " ");
      if (max_count_s != NULL)
	{
	  max_count = atoll (max_count_s + 1);
          /* Functions like comdats only have one caller_node and can
	     have multiple node weights from multiple modules.  */
	  caller_node->max_count += max_count;
	}
      /* Actually read the node weight here.  */
      get_next_string (&contents, &read_length, 1);
      curr_length += read_length;
    }

  /* If the function is split it could have the weight of the split cold
     section here as "SplitWeight <max_count>".  */

  /* Peek at the next string.  */
  if (curr_length < length)
    node_weight_s = get_next_string (&contents, &read_length, 0);
  if (node_weight_s != NULL
      && is_prefix_of (SPLIT_FUNCTION_PREFIX, node_weight_s))
    {
      unsigned long long split_weight
	= atoll (node_weight_s + strlen (SPLIT_FUNCTION_PREFIX));
      caller_node->split_weight = split_weight;
      /* Actually read the node weight here.  */
      get_next_string (&contents, &read_length, 1);
      curr_length += read_length;
    }

  while (curr_length < length)
    {
      /* Read callee, weight tuples.  */
      char *callee;
      char *weight_str;
      unsigned long long weight;
      Node *callee_node;

      callee = get_next_string (&contents, &read_length, 1);
      curr_length += read_length;

      /* We can have multiple header lines; such a situation arises when
         we've linked objects into a shared library, and we use that
         library as input to the linker for something else.  Deal
         gracefully with such cases.  */
      if (strncmp (callee, "Function ", HEADER_LEN) == 0)
	continue;

      callee = canonicalize_function_name (file_handle, callee);
      callee_node = get_function_node (callee);

      assert (curr_length < length);
      weight_str = get_next_string (&contents, &read_length, 1);
      weight = atoll (weight_str);
      curr_length += read_length;
      update_edge (caller_node, callee_node, weight);
    }
}

/* Traverse the list of edges and find the edge with the maximum weight.  */

static Edge *
find_max_edge ()
{
  Edge *it, *max_edge;

  if (active_edges == NULL)
    return NULL;

  max_edge = active_edges;
  assert (!active_edges->is_merged);

  it = active_edges->next;
  for (;it != NULL; it = it->next)
    {
      assert (!it->is_merged);
      if (edge_lower (max_edge , it))
          max_edge = it;
    }

  return max_edge;
}

/* Change the EDGE from OLD_NODE to KEPT_NODE to be between NEW_NODE
   and KEPT_NODE.  */

static void
merge_edge (Edge *edge, Node *new_node, Node *old_node,
            Node *kept_node)
{
  void **slot;
  Raw_edge re, *r;

  r = &re;
  init_raw_edge (r, new_node, kept_node);
  slot = htab_find_slot_with_hash (edge_map, r,
				   edge_hash_function (r->n1->id, r->n2->id),
				   INSERT);

  if (*slot == NULL)
    {
      reset_functions (edge, new_node, kept_node);
      *slot = edge;
      add_edge_to_node (new_node, edge);
    }
  else
    {
      Edge *new_edge = *slot;
      new_edge->weight += edge->weight;
      edge->is_merged = 1;
      remove_edge_from_list (edge);
    }
}

/* Merge the two nodes in this EDGE. The new node's edges are the union of
   the edges of the original nodes.  */

static void
collapse_edge (Edge * edge)
{
  Edge_list *it;
  Node *kept_node = edge->first_function;
  Node *merged_node = edge->second_function;

  /* Go through all merged_node edges and merge with kept_node.  */
  for (it = merged_node->edge_list; it != NULL; it = it->next)
    {
      Node *other_node = NULL;
      Edge *this_edge = it->edge;
      if (this_edge->is_merged)
        continue;
      if (this_edge == edge)
        continue;
      assert (this_edge->first_function->id == merged_node->id
              || this_edge->second_function->id == merged_node->id);
      other_node = (this_edge->first_function->id
		    == merged_node->id)
		   ? this_edge->second_function
                   : this_edge->first_function;
      merge_edge (this_edge, kept_node, merged_node, other_node);
    }

  merge_node (kept_node, merged_node);
  edge->is_merged = 1;
  remove_edge_from_list (edge);
}

/* Make node N a real node if it can be reordered, that is, its .text
   section is available.  */
static void set_node_type (Node *n)
{
  void *slot;
  char *name = n->name;
  slot = htab_find_with_hash (section_map, name, htab_hash_string (name));
  if (slot != NULL)
    {
      /* Update the section instance corresponding to the node instance.
	 Assign the weights from the node instance to the section instance.  */
      Section_id *s = (Section_id *)(slot);
      Section_id *s_comdat;
      assert (s->weight == 0 && s->computed_weight == 0 && s->max_count == 0);
      s->weight = n->weight;
      s->computed_weight = n->computed_weight; 
      s->max_count = n->max_count;

      /* If s is split into a cold section, assign the split weight to the
         max count of the split section.   Use this also for the weight of the
         split section.  */
      if (s->split_section)
        {
          s->split_section->max_count = s->split_section->weight = n->split_weight;
          /* If split_section is comdat, update all the comdat
    	     candidates for weight.  */
          s_comdat = s->split_section->comdat_group;
          while (s_comdat != NULL)
            {
	      /* Set the different weights for comdat candidates.  No need to se
		 computed_weight as it is zero for split sections.  A split cold
		 section is never called, it is only jumped into from the parent
		 section.  */
              s_comdat->weight = s->split_section->weight;
              s_comdat->max_count = s->split_section->max_count;
              s_comdat = s_comdat->comdat_group;
            }
	}

      /* If s is comdat, update all the comdat candidates for weight.  */
      s_comdat = s->comdat_group;
      while (s_comdat != NULL)
        {
          s_comdat->weight = s->weight;
          s_comdat->computed_weight = s->computed_weight;
          s_comdat->max_count = s->max_count; 
          s_comdat = s_comdat->comdat_group;
        }
      set_as_real_node (n);
      num_real_nodes++;
    }
}

/* Return true if WEIGHT is more than the cutoff, specified either as
   as percent, CUTOFF_P, of MAX or as an absolute value, CUTOFF_A.   */
int 
edge_over_cutoff (unsigned long long weight, unsigned long long max,
		  unsigned int cutoff_p, unsigned long long cutoff_a)
{
  /* First check if weight if more than cutoff_p% of max.  */
  if (((double)(max) * (cutoff_p/100.0)) >= (double) weight)
    return 0;
  if (cutoff_a >= weight)
    return 0;
  return 1;
}

/* Edge cutoff is used to discard callgraph edges that are not above a
   certain threshold.  cutoff_p is to express this as a percent of the
   maximum value and cutoff_a is used to express this as an absolute
   value.  */
extern unsigned int edge_cutoff_p;
extern unsigned long long edge_cutoff_a;

void
find_pettis_hansen_function_layout (FILE *fp)
{
  Node *n_it;
  Edge *it;
  unsigned int max_edge_value = 0;

  assert (node_chain != NULL);
  assert (active_edges != NULL);
  if (fp != NULL)
    dump_edges (fp);

  /* Go over all the nodes and set it as real node only if a corresponding
     function section exists.  */
  for (n_it = node_chain; n_it != NULL; n_it = n_it->next)
    set_node_type (n_it);

  /* Set edge types. A WEAK_EDGE has one of its nodes corresponding to a
     function that cannot be re-ordered.  */
  for (it = active_edges; it != NULL; it = it->next)
    set_edge_type (it);

  it = find_max_edge ();
  if (it != NULL)
    max_edge_value = it->weight;
  while (it != NULL)
    {
      if (!edge_over_cutoff (it->weight, max_edge_value, edge_cutoff_p,
			     edge_cutoff_a))
	{
	  if (fp !=NULL)
	    fprintf (fp, "Not considering edge with weight %llu and below\n",
		     it->weight);
          break;
	}
      collapse_edge (it);
      it = find_max_edge ();
    }
}

/* The list of sections created, excluding comdat duplicates.  */
Section_id *first_section = NULL;
/* The number of sections.  */
int num_sections = 0;

const int NUM_SECTION_TYPES = 4;
const char *section_types[] = {".text.hot.",
			       ".text.unlikely.",
			       ".text.startup.",
			       ".text." };

/* For sections that are not in the callgraph, the priority gives the
   importance of each section type.  Sections are grouped according to
   priority, higher priority (lower number).  */
const int section_priority[] = {0, 3, 1, 2};

/* Order in which the sections must be laid out is given by
   section_position[section_type].  The order in which the section
   types are laid out from address low to high are: .text.unlikely,
   .text.startup, .text., .text.hot followed by the sections grouped
   by the callgraph.  */
const int section_position[] = {3, 0, 1, 2};

/* The position of the sections grouped using the callgraph.  It comes after
   all the sections not present in the callgraph are laid out.  */
#define CALLGRAPH_POSITION NUM_SECTION_TYPES

/* Maps the function name corresponding to section SECTION_NAME to the
   object handle and the section index.  */

void
map_section_name_to_index (char *section_name, void *handle, int shndx)
{
  void **slot;
  char *function_name = NULL;
  int i, section_type = -1;

  for (i = 0; i < ARRAY_SIZE (section_types); ++i)
    {
      if (is_prefix_of (section_types[i], section_name))
        {
          function_name = section_name + strlen (section_types[i]);
  	  section_type = i;
	  break;
        }
    }

  assert (function_name != NULL && section_type >= 0);
  function_name = canonicalize_function_name (handle, function_name);
  num_sections++;

  /* Allocate section_map.  */
  if (section_map == NULL)
    {
      section_map = htab_create (NUM_FUNCTIONS,
				 section_map_htab_hash_descriptor,
				 section_map_htab_eq_descriptor , NULL);
      assert (section_map != NULL);
    }

  slot = htab_find_slot_with_hash (section_map, function_name,
				   htab_hash_string (function_name),
				   INSERT);
  if (*slot == NULL)
    {
      Section_id *section = make_section_id (function_name, section_name,
					     section_type, handle, shndx);
      /* Chain it to the list of sections.  */
      section->next = first_section;
      first_section = section;
      *slot = section;
    }
  else
    {
      /* Handle function splitting here.  With function splitting, the split
         function sections have the same name and they are in the same module.
	 Here, we only care about the section that is marked with prefix
	 like ".text.hot".  The other section is cold.  The plugin should not
	 be adding this cold section to the section_map.  In get_layout it will
	 later be picked up when processing the non-callgraph sections and it
	 will laid out appropriately.  */
      Section_id *kept = (Section_id *)(*slot);
      Section_id *section = make_section_id (function_name, section_name,
                                             section_type, handle, shndx);
      int is_split_function = 0;
      Section_id *split_comdat = NULL;
      /* Check if this is a split function. The modules are the same means this
	 is not comdat and we assume it is split.  It can be split and comdat
	 too, in which case we have to search the comdat list of kept.  */
      if (kept->handle == handle)
	is_split_function = 1;
      else if (kept->comdat_group != NULL)
	{
	  split_comdat = kept;
	  do
	    {
	      if (split_comdat->comdat_group->handle == handle)
		break;
	      split_comdat = split_comdat->comdat_group;
	    }
	  while (split_comdat->comdat_group != NULL);
	}

      /* It is split and it is comdat.  */
      if (split_comdat != NULL
	  && split_comdat->comdat_group != NULL)
	{
	  /* The comdat_section that is split.  */
	  Section_id *comdat_section = split_comdat->comdat_group;
	  Section_id *cold_section = NULL;
	  /* If the existing section is cold, the newly detected split must 
	     be hot.  */
	  if (is_prefix_of (".text.unlikely", comdat_section->full_name))
	    {
	      assert (!is_prefix_of (".text.unlikely", section_name));
	      cold_section = comdat_section;
	      /* Replace the comdat_section in the kept section list with the
		 new section.  */
	      split_comdat->comdat_group = section;
	      section->comdat_group = comdat_section->comdat_group;
	      comdat_section->comdat_group = NULL;
	    }
	  else
	    {
	      assert (is_prefix_of (".text.unlikely", section_name));
	      cold_section = section;
	    }
	  assert (cold_section != NULL && cold_section->comdat_group == NULL);
	  cold_section->is_split_cold_section = 1;
	  /* The cold section must be added to the unlikely chain of comdat
	     groups.  */
	  if (kept->split_section == NULL)
	    {	
	      /* This happens if no comdat function in this group so far has
		 been split.  */
	      kept->split_section = cold_section;
	    }
	  else
	    {
	      /* Add the cold_section to the unlikely chain of comdats.  */
	      cold_section->comdat_group = kept->split_section->comdat_group;
	      kept->split_section->comdat_group = cold_section;
	    }
	}
      /* It is split and it is not comdat.  */
      else if (is_split_function)
	{
	  Section_id *cold_section = NULL;
	  /* Function splitting means that the "hot" part is really the
	     relevant section and the other section is unlikely executed and
	     should not be part of the callgraph.  */

	  /* Store the new section in the section list.  */
	  section->next = first_section;
	  first_section = section;
	  /* If the existing section is cold, the newly detected split must 
	     be hot.  */
          if (is_prefix_of (".text.unlikely", kept->full_name))
	    {
	      assert (!is_prefix_of (".text.unlikely", section_name));
	      /* The kept section was the unlikely section.  Change the section
		 in section_map to be the new section which is the hot one.  */
	      *slot = section;
	      /* Record the split cold section in the hot section.  */
	      section->split_section = kept;
	      /* Comdats and function splitting are already handled.  */
	      assert (kept->comdat_group == NULL);
	      cold_section = kept;
	    }
	  else
	    {
	      /* Record the split cold section in the hot section.  */
	      assert (is_prefix_of (".text.unlikely", section_name));
	      kept->split_section = section;
	      cold_section = section;
	    }
	  assert (cold_section != NULL && cold_section->comdat_group == NULL);
	  cold_section->is_split_cold_section = 1;
	}
      else
	{
          /* The function already exists, it must be a COMDAT.  Only one section
	     in the comdat group will be kept, we don't know which.  Chain all
	     the comdat sections in the same comdat group to be emitted
	     together later.  Keep one section as representative (kept) and
	     update its section_type to be equal to the type of the highest
	     priority section in the group.  */

          /* Two comdats in the same group can have different priorities.  This
	     ensures that the "kept" comdat section has the priority of the
	     highest section in that comdat group.   This is necessary because
	     the plugin does not know which section will be kept.  */
          if (section_priority[kept->section_type]
	      > section_priority[section_type])
            kept->section_type = section_type;

          section->comdat_group = kept->comdat_group;
          kept->comdat_group = section;
	}
    }
}

/* Add section S to the chain SECTION_START ... SECTION_END.
   If it is a comdat, get all the comdat sections in the group.
   Chain these sections to SECTION_END.  Set SECTION_START if it
   is NULL.  */

static void
write_out_node (Section_id *s, Section_id **section_start,
	        Section_id **section_end)
{
  assert (s != NULL && s->processed == 0);
  s->processed = 1;
  if (*section_start == NULL)
    {
      *section_start = s;
      *section_end = s;
    }
  else
    {
      (*section_end)->group = s;
      *section_end = s;
    }

  /* Print all other sections in the same comdat group.  */
  while (s->comdat_group)
    {
      s = s->comdat_group;
      s->processed = 1;
      (*section_end)->group = s;
      *section_end = s;
    }
}

/* Find the max of a, b and c.  */
static unsigned long long
get_max (unsigned long long a, unsigned long long b, unsigned long long c)
{
  unsigned long long max = a;
  if (b > max)
    max = b;
  if (c > max)
    max = c;
  return max;
}

/* This is true if the max count of any bb in a function should be used as
   the node weight rather than the count of the entry bb.  */
extern int use_max_count;

/* Comparison function for sorting two sections a and b by their
   weight.  */
static 
int section_weight_compare (const void *a, const void *b)
{
  Section_id *s_a = *(Section_id **)a;
  Section_id *s_b = *(Section_id **)b;
  assert (use_max_count <= 1);
  unsigned long long max_sa_weight = get_max (s_a->weight, s_a->computed_weight,
					      s_a->max_count * use_max_count);
  unsigned long long max_sb_weight = get_max (s_b->weight, s_b->computed_weight,
					      s_b->max_count * use_max_count);

  if (max_sa_weight < max_sb_weight)
    return -1;
  else if (max_sa_weight == max_sb_weight)
    return 0;

  return 1;
}

/* s is a pointer to a section and the group of sections is linked
   via s->group.  The output is the list of sections sorted by their
   node weights (which is the maximum of their profile count, computed
   weights or the max bb count if use_max_count is true).  */
static Section_id *
sort_section_group (Section_id *s)
{
  Section_id **sort_array;
  Section_id *s_tmp;
  int num_elements = 0;
  int i;

  if (s == NULL)
    return s;

  s_tmp = s;
  while (s_tmp != NULL)
    {
      num_elements++;
      s_tmp = s_tmp->group;
    }

  if (num_elements == 1)
    return s;

  XNEWVEC_ALLOC (sort_array, Section_id *, num_elements);
  s_tmp = s;
  for (i = 0; i < num_elements; ++i)
    {
      sort_array[i] = s_tmp;
      s_tmp = s_tmp->group;
    }

  for (i = 0; i < num_elements; ++i)
    {
      sort_array[i]->group = NULL;
    }

  qsort (sort_array, num_elements, sizeof (Section_id *),
	 section_weight_compare);

  s_tmp = sort_array[0];
  for (i = 1; i < num_elements; ++i)
    {
      s_tmp->group = sort_array[i];
      s_tmp = s_tmp->group;
    }
  s_tmp->group = NULL;
  return sort_array[0];
}

/* If sort_name_prefix is true then the sections not touched by the callgraph
   are grouped according to their name prefix.  When sort_name_prefix is zero,
   all the sections are put together and sorted according to their node
   weights.  The default value of sort_name_prefix is 0.  Even when sections
   are grouped by their prefix, each group is sorted by the node weights.  */
extern int sort_name_prefix;
static int section_position_index (int section_type)
{
  assert (section_type >= 0  && section_type < NUM_SECTION_TYPES);
  if (!sort_name_prefix)
    return 0;
  else
    return section_position[section_type];
}

/* Track where the unlikely sections start and end.  This will be needed if
   the unlikely sections need to be split into a separate segment.  */
int unlikely_segment_start = -1;
int unlikely_segment_end = -1;

/* This value is used to determine the profile threshold below which the
   section is considered unlikely.  The default is zero.  */
extern unsigned long long unlikely_segment_profile_cutoff;

/* Visit each node and print the chain of merged nodes to the file.  Update
   HANDLES and SHNDX to contain the ordered list of sections.  */

unsigned int
get_layout (FILE *fp, void*** handles,
            unsigned int** shndx)
{
  Node *n_it;
  int  i = 0;
  int position;
  void *slot;
  int unlikely_section_index;

  /* Form NUM_SECTION_TYPES + 1 groups of sections.  Index 5 corresponds
     to the list of sections that correspond to functions in the callgraph.
     For other sections, they are grouped by section_type and stored in
     index: section_position[section_type]).
     SECTION_START points to the first section in each section group and
     SECTION_END points to the last.  */
  Section_id *section_start[NUM_SECTION_TYPES + 1];
  Section_id *section_end[NUM_SECTION_TYPES + 1];
  Section_id *s_it;

  XNEWVEC_ALLOC (*handles, void *, num_sections);
  XNEWVEC_ALLOC (*shndx, unsigned int, num_sections);

  for (i = 0; i < NUM_SECTION_TYPES + 1; i++)
    {
      section_start[i] = NULL;
      section_end[i] = NULL;
    }

  /* Dump edges to the final reordering file.  */
  for (n_it = node_chain; n_it != NULL; n_it = n_it->next)
    {
      Section_id *s;
      Node *node;
      /* First, only consider nodes that are real and that have other
	 nodes merged with it. */
      if (n_it->is_merged || !n_it->is_real_node || !n_it->merge_next)
        continue;

      slot = htab_find_with_hash (section_map, n_it->name,
				  htab_hash_string (n_it->name));
      assert (slot != NULL);
      s = (Section_id *)slot;
      write_out_node (s, &section_start[CALLGRAPH_POSITION],
		      &section_end[CALLGRAPH_POSITION]);

      if (fp)
	fprintf (fp, "# Callgraph group : %s", n_it->name);

      node = n_it->merge_next;
      while (node != NULL)
        {
          if (node->is_real_node)
	    {
	      slot = htab_find_with_hash (section_map, node->name,
					  htab_hash_string (node->name));
	      assert (slot != NULL);
	      s = (Section_id *)slot;
	      write_out_node (s, &section_start[CALLGRAPH_POSITION],
			      &section_end[CALLGRAPH_POSITION]);
	      if (fp)
		fprintf (fp, " %s", node->name);
	    }
          node = node->merge_next;
	}

      if (fp)
	fprintf (fp, "\n");
    }

  
  /*  Now handle all the sections that were not processed above during
      callgraph handling.  Go through all the sections and sort unprocessed
      sections into different section_type groups.  */
  s_it = first_section;
  while (s_it)
    {
      if (!s_it->processed)
	{
	  int index = section_position_index(s_it->section_type);
	  write_out_node (s_it, &section_start[index], &section_end[index]);
	}
      s_it = s_it->next;
    } 
     
  /* Determine the unlikely section index  */
  unlikely_section_index = -1;
  for (i = 0; i < ARRAY_SIZE (section_types); ++i)
    if (strcmp (".text.unlikely.", section_types[i]) == 0)
      break;

  assert (i < ARRAY_SIZE (section_types));
  unlikely_section_index = section_position_index(i);

  position = 0;
  for (i = 0; i < NUM_SECTION_TYPES + 1; ++i)
    {
      s_it = section_start[i];

      if (s_it == NULL)
	continue;

      /* Sort all section groups by weight except the callgraph group.  */
      if (i != CALLGRAPH_POSITION)
	s_it = sort_section_group (s_it);

      /* Start the unlikely segment if necessary.  */
      assert (use_max_count <= 1);
      if (i == unlikely_section_index
	  && (get_max (s_it->weight, s_it->computed_weight,
		       s_it->max_count * use_max_count)
		<= unlikely_segment_profile_cutoff))
	{
	  assert (unlikely_segment_start == -1);
	  unlikely_segment_start = position;
	  if (fp != NULL)
	    fprintf (fp, "=== Unlikely sections start ===\n");
	}

      do
        {
	  assert (position < num_sections);
          (*handles)[position] = s_it->handle;
          (*shndx)[position] = s_it->shndx;

	  /* Check if this section will end the unlikely segment.  */
	  if (i == unlikely_section_index
	      && unlikely_segment_start >= 0
              && unlikely_segment_start != position
	      && unlikely_segment_end == -1
	      && (get_max (s_it->weight, s_it->computed_weight,
		           s_it->max_count * use_max_count)
		    > unlikely_segment_profile_cutoff))
	    {
	      unlikely_segment_end = position - 1;
	      if (fp != NULL)
		fprintf (fp, "=== Unlikely sections end ===\n");
	    }

          position++;
	  if (fp != NULL)
	    {
	      fprintf (fp, "%s entry count = %llu computed = %llu "
		       "max count = %llu split = %d\n", 
		       s_it->full_name, s_it->weight,
		       s_it->computed_weight, s_it->max_count,
		       s_it->is_split_cold_section);
	    }
	  s_it = s_it->group;
        }
      while (s_it);

      /* End the unlikely segment if it has not been done already.  */
      if (i == unlikely_section_index
	  && unlikely_segment_start != -1
	  && unlikely_segment_end == -1)
	{
	  unlikely_segment_end = position - 1;
	  if (fp != NULL)
	    fprintf (fp, "=== Unlikely sections end ===\n");
	}
    }
  return position;
}

void
cleanup ()
{
  /* Go through heap allocated objects and free them.  */
  while (mm_node_chain)
    {
      mm_node *node = mm_node_chain;
      free (node->ptr);
      mm_node_chain = node->next;
      free (node);
    }

  /*  Delete all htabs. */
  htab_delete (section_map);
  htab_delete (function_map);
  htab_delete (edge_map);
}

/* Check if the callgraph is empty.  */
unsigned int
is_callgraph_empty ()
{
  if (active_edges == NULL)
    return 1;
  return 0;
}