1 files changed, 272 insertions, 0 deletions
diff --git a/gcc-4.6/function_reordering_plugin/callgraph.h b/gcc-4.6/function_reordering_plugin/callgraph.h
new file mode 100644
index 0000000..66ef5b3
--- /dev/null
+++ b/gcc-4.6/function_reordering_plugin/callgraph.h
@@ -0,0 +1,272 @@
+/* Callgraph implementation.
+   Copyright (C) 2011 Free Software Foundation, Inc.
+   Contributed by Sriraman Tallam (tmsriram@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"
+
+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 (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;
+  /* 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 (Node);
+  node->id = id;
+  node->name = name;
+  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 int 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 int weight)
+{
+  Edge *edge = XNEW (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;
+}
+
+/* Frees the chain of edges.  */
+inline static void
+free_edge_chain (Edge *edge_chain)
+{
+  Edge *edge;
+
+  for (edge = edge_chain; edge != NULL; )
+    {
+      Edge *next_edge = edge->next;
+      free (edge);
+      edge = next_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
+{
+  /* Name of the function.  */
+  char *name;
+  /* Full name of the section.  */
+  char *full_name;
+  void *handle;
+  int shndx;
+} Section_id;
+
+inline static Section_id *
+make_section_id (char *name, char *full_name, void *handle, int shndx)
+{
+  Section_id *s = XNEW (Section_id);
+  s->name = name;
+  s->full_name = full_name;
+  s->handle = handle;
+  s->shndx = shndx;
+
+  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 (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