Clean up our data structures.

git-svn-id: https://gcc.gnu.org/svn/gcc/branches/google/gcc-4_6-mobile@188273 138bc75d-0d04-0410-961f-82ee72b054a4

4 files changed, 771 insertions, 533 deletions

diff --git a/vtable-security/ChangeLog.vtable-security b/vtable-security/ChangeLog.vtable-security
index 2f774046e2d..7f5c5308d25 100644
--- a/vtable-security/ChangeLog.vtable-security
+++ b/vtable-security/ChangeLog.vtable-security
@@ -1,3 +1,77 @@
+2012-06--4  Caroline Tice  <cmtice@google.com>
+
+	* gcc/cp/vtable-class-hierarchy.c (struct list_node, struct node,
+	struct node2): Delete struct definitions.
+	(tree-vtable-verify.h): New include statement.
+	(struct work_node): New struct defintion.
+	(num_classes): New global variable.
+	(vlt_class_hierarchy_info, registered_pairs):  Delete global vars.
+	(linked_list_insert):  Delete function.
+	(binary_tree_insert):  Delete function.
+	(binary_tree_find):  Delete function.
+	(build_transitive_closure):  Delete function.
+	(tree_three_key_insert):  Delete function.
+	(vtable_find_map_decl):  Delete function.
+	(dump_class_hierarchy_information): Remove parameter; completely
+	re-write to use new data structures.
+	(register_all_pairs): Remove first parameter; make non-recursive;
+	modify to iterate through new data structure.  (Main body of code
+	remains the same).  Fix arguments for calls to record_register_pairs
+	and register_vptr_fields.
+	(add_hierarchy_pair):  New function.
+	(add_to_worklist):  New function.
+	(find_and_remove_next_leaf_node):  New function.
+	(record_register_pairs):  Completely rewrite to use new data
+	structures; Remove base_ptr_decl parameter and add base_class
+	parameter.
+	(register_vptr_fields):  Add base_class parameter.  Fix arguments for
+	call to record_register_pairs.
+	(find_graph_node):  New function.
+	(add_edge_to_graph):  New function.
+	(update_class_hierarchy_information):  Remove base_class_ptr_decl
+	parameter. Use new data structures; call add_hierarchy_pair instead
+	of binary_tree_insert.
+	(vtv_register_class_hierarchy_information):  Use new global
+	variable, any_verification_calls_generated, to decide whether or not
+	to register pairs; remove argument from call to
+	dump_class_hierarchy_information; remove vlt_class_hierarchy_info
+	from call to register_all_pairs.
+	(vtable_find_or_create_map_decl):  Modify to use new hash table for
+	accessing *.vtable_map variables; return hash table node rather than
+	var decl.
+	(vtv_save_base_class_info): Modify to use new hash table data
+	structure for vtable_map variables.
+	* gcc/tree-vtable-verify.c: Remove comment from top about code
+	being contributed by Razya Ladelsky (it was accidentally copied in
+	along with the copyright info).
+	(tree-vtable-verify.h):  New include statement.
+	(num_vtable_map_nodes): New global variable.
+	(any_verification_calls_generated):  New global variable.
+	(vtbl_map_node_registration_find): New function.
+	(vtbl_map_node_registration_insert):  New function.
+	(hash_vtable_registration): New function.
+	(eq_vtable_registration):  New function.
+	(vtbl_map_hash): New static global variable.
+	(vtbl_map_nodes): New global variable.
+	(vtbl_map_nodes_array):  New global variable.
+	(vtbl_map_array_insert): New function.
+	(hash_vtbl_map_node):  New function.
+	(eq_vtbl_map_node):  New function.
+	(vtbl_map_get_node):  New function.
+	(vtbl_map_node):  New function.
+	(vtable_var_decl_array):  Delete global variable.
+	(vtable_var_decl_array_max):  Delete global variable.
+	(vtable_var_decl_array_entries):  Delete global variable.
+	(find_vtable_map_decl):  Delete function.
+	(save_vtable_map_decl):  Delete function.
+	(verify_bb_vtables):  Delete unused local variables vtbl_ptr & t;
+	modify to use vtbl_map_hash and hash functions to find/store
+	vtable_map variables; update any_verification_calls_generated; fix
+	formatting (no line longer than 80 chars).
+	(build_vtable_verify_fndecl): Fix line formatting so no line is longer
+	than 80 chars.
+	* gcc/tree-vtable-verify.h: New file.
+
 2012-06-04  Caroline Tice  <cmtice@google.com>
 
 	* gcc/flag-types.h (enum vtv_priority): Add VTV_NO_PRIORITY,
@@ -5,7 +79,7 @@
 	* gcc/common.opt (fvtable-verify):  Set the default
 	initialization to VTV_NO_PRIORITY, so the vtable verification
 	is not turned on by default.
-	
+
 2012-06-03  Caroline Tice  <cmtice@google.com>
 
 	* gcc/cp/decl2.c (cp_write_global_declarations):  Change vtable
diff --git a/vtable-security/gcc/cp/vtable-class-hierarchy.c b/vtable-security/gcc/cp/vtable-class-hierarchy.c
index 958201cbf72..4d66b07d01f 100644
--- a/vtable-security/gcc/cp/vtable-class-hierarchy.c
+++ b/vtable-security/gcc/cp/vtable-class-hierarchy.c
@@ -41,41 +41,29 @@ along with GCC; see the file COPYING3.  If not see
 #include "plugin.h"
 #include "tree-threadsafe-analyze.h"
 #include "tree-iterator.h"
+#include "tree-vtable-verify.h"
 
 static GTY(()) tree vlt_register_pairs_fndecl = NULL_TREE;
 static GTY(()) tree vlt_change_permission_fndecl = NULL_TREE;
 
-struct list_node {
-  tree class_type;
-  struct list_node *next;
+struct work_node {
+  struct vtv_graph_node *node;
+  struct work_node *next;
 };
 
-struct node {
-  tree ptr_decl;
-  struct list_node *class_list;
-  struct node *left;
-  struct node *right;
-};
-
-struct node2 {
-  tree base_map_var_decl;
-  tree vtable_decl;
-  unsigned offset;
-  struct node2 *left;
-  struct node2 *right;
-};
+static int num_classes = 0;
 
 static void init_functions (void);
-static void linked_list_insert (struct list_node **, tree);
-static void binary_tree_insert (struct node **, tree, tree, tree);
-static struct node *binary_tree_find (struct node *, tree);
-static tree vtable_find_map_decl (tree var_id);
-static void dump_class_hierarchy_information (struct node *root);
-static void register_all_pairs (struct node *root, tree body);
-
-static struct node *vlt_class_hierarchy_info = NULL;
-static struct node2 *registered_pairs = NULL;
+static void dump_class_hierarchy_information (void);
+static void register_all_pairs (tree body);
+static void add_hierarchy_pair (struct vtv_graph_node *,
+                                struct vtv_graph_node *);
+static struct vtv_graph_node *find_graph_node (tree);
+static struct vtv_graph_node *
+                  find_and_remove_next_leaf_node (struct work_node **worklist);
 
+void update_class_hierarchy_information (tree, tree);
+struct vtbl_map_node *vtable_find_or_create_map_decl (tree);
 
 static void
 init_functions (void)
@@ -87,7 +75,8 @@ init_functions (void)
   tree char_ptr_type = build_pointer_type (char_type_node);
 
   arg_types = build_tree_list (NULL_TREE, char_ptr_type);
-  arg_types = chainon (arg_types, build_tree_list (NULL_TREE, integer_type_node));
+  arg_types = chainon (arg_types, build_tree_list (NULL_TREE,
+                                                   integer_type_node));
   arg_types = chainon (arg_types, build_tree_list (NULL_TREE, void_type_node));
 
   change_permission_type = build_function_type (change_permission_type,
@@ -108,9 +97,11 @@ init_functions (void)
   /* Start: Arg types to be removed when we remove debugging parameters from
      the library function. */
   arg_types = chainon (arg_types, build_tree_list (NULL_TREE, char_ptr_type));
-  arg_types = chainon (arg_types, build_tree_list (NULL_TREE, integer_type_node));
+  arg_types = chainon (arg_types, build_tree_list (NULL_TREE,
+                                                   integer_type_node));
   arg_types = chainon (arg_types, build_tree_list (NULL_TREE, char_ptr_type));
-  arg_types = chainon (arg_types, build_tree_list (NULL_TREE, integer_type_node));
+  arg_types = chainon (arg_types, build_tree_list (NULL_TREE,
+                                                   integer_type_node));
   /* End: Arg types to be removed...*/
   arg_types = chainon (arg_types, build_tree_list (NULL_TREE, void_type_node));
 
@@ -128,247 +119,151 @@ init_functions (void)
 }
 
 static void
-dump_class_hierarchy_information (struct node *root)
+dump_class_hierarchy_information (void)
 {
-  struct list_node *current;
-
-  /* Dump current node */
-  if (!root || ! root->ptr_decl)
-    return;
+  struct vtbl_map_node *cur;
+  unsigned i;
 
-  fprintf (stdout, "Base class '%s' is inherited by: ",
-           IDENTIFIER_POINTER (DECL_NAME (root->ptr_decl)));
-
-  current = root->class_list;
-  while (current)
+  for (cur = vtbl_map_nodes; cur; cur = cur->next)
     {
-      if (current->class_type)
-	fprintf (stdout, " (%s, %s)",
-		 IDENTIFIER_POINTER (DECL_NAME
-				     (TYPE_NAME (current->class_type))),
-                 IDENTIFIER_POINTER (get_mangled_id(TREE_CHAIN(current->class_type))));
-      current = current->next;
-    }
-  fprintf (stdout, "\n");
-
-  /* Dump left child */
-  dump_class_hierarchy_information (root->left);
+      fprintf (stdout, "Base class '%s' is inherited by: ",
+               IDENTIFIER_POINTER
+                   (DECL_NAME
+                        (TREE_CHAIN (cur->class_info->class_type))));
 
-  /* Dump right child */
-  dump_class_hierarchy_information (root->right);
+      for (i = 0; i < num_vtable_map_nodes; ++i)
+        if (TEST_BIT (cur->class_info->descendants, i))
+          {
+            struct vtbl_map_node *descendant = vtbl_map_nodes_array[i];
+            tree class_type = descendant->class_info->class_type;
+            fprintf (stdout, " (%s, %s)",
+                     IDENTIFIER_POINTER (DECL_NAME
+                                         TYPE_NAME (class_type)),
+                     IDENTIFIER_POINTER (get_mangled_id
+                                         (TREE_CHAIN (class_type))));
+          }
+      fprintf (stdout, "\n");
+    }
 }
 
 static void
-list_append (struct list_node *old_list, struct list_node *new_list)
+add_to_worklist (struct work_node **worklist, struct vtv_graph_node *node,
+                 sbitmap inserted)
 {
-  struct list_node *old_cur;
-  struct list_node *old_end;
-  struct list_node *new_cur;
-  struct list_node *new_node;
+  struct work_node *new_work_node;
 
-  /* Append to the old list anything in the new list that isn't
-     already there.*/
-
-  /* Find the end of the old list */
-  old_end = old_list;
-  while (old_end->next != NULL)
-    old_end = old_end->next;
-
-  /* Look at each elemement in new list */
-  for (new_cur = new_list; new_cur; new_cur = new_cur->next)
-    {
-      /* Look for 'new_cur' in the old list.  */
-      bool found = false;
-
-      for (old_cur = old_list; old_cur && !found; old_cur = old_cur->next)
-        if (get_mangled_id (TREE_CHAIN (new_cur->class_type))
-            == get_mangled_id (TREE_CHAIN (old_cur->class_type)))
-          found = true;
+  if (TEST_BIT (inserted, node->class_uid))
+    return;
 
-      /* if not found, copy new node and append to end of old list */
-      if (!found)
-        {
-          new_node = (struct list_node *) xmalloc (sizeof (struct list_node));
-          new_node->class_type = new_cur->class_type;
-          new_node->next = NULL;
-
-          old_end->next = new_node;
-          old_end = old_end->next;
-        }
-    }
+  new_work_node = (struct work_node *) xmalloc (sizeof (struct work_node));
+  new_work_node->next = *worklist;
+  new_work_node->node = node;
+  *worklist = new_work_node;
 
+  SET_BIT (inserted, node->class_uid);
 }
 
-static struct node *
-binary_tree_find (struct node *root, tree var_decl)
+static struct vtv_graph_node *
+find_and_remove_next_leaf_node (struct work_node **worklist)
 {
-  if (!root)
-    return NULL;
+  struct work_node *prev, *cur;
 
-  if (DECL_NAME (root->ptr_decl) == DECL_NAME (var_decl))
-    return root;
-
-  else if (var_decl < root->ptr_decl)
-    return binary_tree_find (root->left, var_decl);
-  else
-    return binary_tree_find (root->right, var_decl);
-}
-
-static bool
-build_transitive_closure (struct node *root, struct node *cur_node)
-{
-  bool current_changed = false;
-  bool left_changed = false;
-  bool right_changed = false;
-  struct list_node *cur_list;
-  char * cur_node_name;
-  char *cptr;
-
-  if (!cur_node)
-    return false;
-
-  /* DEBUG
-  fprintf(stderr, "build_transitive_closure: cur_node: ");
-  debug_c_tree(cur_node->ptr_decl);
-  */
-
-  cur_node_name = xstrdup (IDENTIFIER_POINTER
-			         (DECL_NAME
-                                    (cur_node->ptr_decl)));
-  cptr = strstr (cur_node_name, ".vtable_map");
-  if (cptr)
-    cptr[0] = '\0';
-  /* Handle current tree node */
-  for (cur_list = cur_node->class_list; cur_list; cur_list = cur_list->next)
+  for (prev = NULL, cur = *worklist; cur; prev = cur, cur = cur->next)
     {
-      const char *cur_list_name = NULL;
-      char *var_id_name = NULL;
-      tree var_id = NULL_TREE;
-      tree var_decl = NULL_TREE;
-      struct node *tmp_node = NULL;
-      tree vtbl_var_decl;
-
-      /* DEBUG
-      fprintf(stderr, "build_transitive_closure: cur_list:");
-      debug_c_tree(cur_list->class_type);
-      */
-
-      if ((! cur_list->class_type)
-          || (! TYPE_BINFO (cur_list->class_type))
-          || (! BINFO_VTABLE (TYPE_BINFO (cur_list->class_type))))
-        continue;
-
-      vtbl_var_decl = TREE_OPERAND
-          (TREE_OPERAND
-           (BINFO_VTABLE
-            (TYPE_BINFO
-             (cur_list->class_type)), 0), 0);
-
-      if (!vtbl_var_decl)
-        continue;
-      cur_list_name = (const char *) IDENTIFIER_POINTER
-          (DECL_NAME (vtbl_var_decl));
-
-      if (!cur_list_name)
-        continue;
-
-      /* TODO: avoid comparing by name */
-      if (strcmp (cur_list_name, cur_node_name) == 0)
-        continue;
-
-      var_id_name = (char *) xmalloc (strlen (cur_list_name) + 12);
-      sprintf (var_id_name, "%s.vtable_map", cur_list_name);
-      var_id = get_identifier (var_id_name);
-      free (var_id_name);
-
-      var_decl = vtable_find_map_decl (var_id);
-      if (!var_decl)
-        continue;
-
-      tmp_node = binary_tree_find (root, var_decl);
-
-      if (!tmp_node)
-        continue;
-      else
+      if (cur->node->num_children == cur->node->num_processed_children)
         {
-          list_append (cur_node->class_list, tmp_node->class_list);
-          current_changed = true;
+          if (prev == NULL)
+            (*worklist) = cur->next;
+          else
+            prev->next = cur->next;
+
+          cur->next = NULL;
+          return cur->node;
         }
     }
 
-  free(cur_node_name);
-
-  /* Handle left child */
-  left_changed = build_transitive_closure (root, cur_node->left);
-
-  /* Handle right child */
-  right_changed = build_transitive_closure (root, cur_node->right);
-
-  return (current_changed || left_changed || right_changed);
+  return NULL;
 }
 
-
 void
 vtv_compute_class_hierarchy_transitive_closure (void)
 {
-  build_transitive_closure (vlt_class_hierarchy_info,
-			    vlt_class_hierarchy_info);
-}
-
-static bool
-tree_three_key_insert (struct node2 **root, tree key1, tree key2, unsigned key3)
-{
-  /* In "struct node2", base_map_var_decl is the primary sort key (the base
-     class .vtable_map variable decl), and vtable_decl is the secondary sort
-     key (the var decl the vtable). The third key is the offset added to the
-     vtable to get the actual recorded vtable pointer address.  */
-
-  struct node2 *new_node;
-
-  if (!(*root))
+  struct work_node *worklist = NULL;
+  struct vtbl_map_node *cur;
+  sbitmap inserted = sbitmap_alloc (num_vtable_map_nodes);
+  unsigned i;
+
+  /* Note: Every node in the graph gets added to the worklist exactly
+   once and removed from the worklist exactly once (when all of its
+   children have been processed).  Each node's children edges are
+   followed exactly once, and each node's parent edges are followed
+   exactly once.  So this algorithm is roughly O(V + 2E), i.e.
+   O(E + V). */
+
+  /* Set-up:                                                                */
+  /* Find all the "leaf" nodes in the graph, and add them to the worklist.  */
+  sbitmap_zero (inserted);
+  for (cur = vtbl_map_nodes; cur; cur = cur->next)
     {
-      new_node = (struct node2 *) xmalloc (sizeof (struct node2));
-      new_node->base_map_var_decl = key1;
-      new_node->vtable_decl = key2;
-      new_node->offset = key3;
-      new_node->left = NULL;
-      new_node->right = NULL;
-      (*root) = new_node;
-      return false;
+      if (cur->class_info
+          && (cur->class_info->num_children == 0)
+          && ! (TEST_BIT (inserted, cur->class_info->class_uid)))
+        add_to_worklist (&worklist, cur->class_info, inserted);
     }
-  else if ((*root)->base_map_var_decl == key1)
+
+
+  /* Main work: pull next leaf node off work list, process it, add its
+     parents to the worklist, where a 'leaf' node is one that has no
+     children, or all of its children have been processed. */
+  while (worklist)
     {
-      if ((*root)->vtable_decl == key2)
+      struct vtv_graph_node *temp_node =
+                                  find_and_remove_next_leaf_node (&worklist);
+
+      gcc_assert (temp_node != NULL);
+      temp_node->descendants = sbitmap_alloc (num_vtable_map_nodes);
+      sbitmap_zero (temp_node->descendants);
+      SET_BIT (temp_node->descendants, temp_node->class_uid);
+      for (i = 0; i < temp_node->num_children; ++i)
+        sbitmap_a_or_b (temp_node->descendants, temp_node->descendants,
+                        temp_node->children[i]->descendants);
+      for (i = 0; i < temp_node->num_parents; ++i)
         {
-          if ((*root)->offset == key3)
-            return true;
-          else if (key3 < (*root)->offset)
-            return tree_three_key_insert (&((*root)->left), key1, key2, key3);
-          else if (key3 > (*root)->offset)
-            return tree_three_key_insert (&((*root)->right), key1, key2, key3);
+          temp_node->parents[i]->num_processed_children =
+                    temp_node->parents[i]->num_processed_children + 1;
+          if (!TEST_BIT (inserted, temp_node->parents[i]->class_uid))
+            add_to_worklist (&worklist, temp_node->parents[i], inserted);
         }
-      else if (key2 < (*root)->vtable_decl)
-        return tree_three_key_insert (&((*root)->left), key1, key2, key3);
-      else if (key2 > (*root)->vtable_decl)
-        return tree_three_key_insert (&((*root)->right), key1, key2, key3);
     }
-  else if (key1 < (*root)->base_map_var_decl)
-    return tree_three_key_insert (&((*root)->left), key1, key2, key3);
-  else if (key1 > (*root)->base_map_var_decl)
-    return tree_three_key_insert (&((*root)->right), key1, key2, key3);
-
-  return false;
 }
 
 static bool
-record_register_pairs (tree base_ptr_decl, tree vtable_decl, tree vptr_address)
+record_register_pairs (tree vtable_decl, tree vptr_address,
+                       tree base_class)
 {
   unsigned offset = TREE_INT_CST_LOW (TREE_OPERAND (vptr_address, 1));
-  return tree_three_key_insert (&registered_pairs, base_ptr_decl, vtable_decl, offset);
+  tree base_id;
+  struct vtbl_map_node *base_vtable_map_node;
+
+  if (TREE_CHAIN (base_class))
+    base_id = DECL_ASSEMBLER_NAME (TREE_CHAIN (base_class));
+  else
+    base_id = DECL_ASSEMBLER_NAME (TYPE_NAME (base_class));
+
+  base_vtable_map_node = vtbl_map_get_node (base_id);
+
+  if (vtbl_map_node_registration_find (base_vtable_map_node, vtable_decl,
+                                       offset))
+    return true;
+
+  vtbl_map_node_registration_insert (base_vtable_map_node, vtable_decl,
+                                       offset);
+  return false;
 }
 
 static void
-register_vptr_fields (tree base_class_decl_arg, tree record_type, tree body)
+register_vptr_fields (tree base_class_decl_arg, tree base_class,
+                      tree record_type, tree body)
 {
   /* A class may contain secondary vtables in it, for various
      reasons.  This function goes through the decl chain of a class
@@ -398,7 +293,7 @@ register_vptr_fields (tree base_class_decl_arg, tree record_type, tree body)
         {
           tree values = DECL_INITIAL (ztt_decl);
           struct varpool_node * vp_node = varpool_node (ztt_decl);
-          if ( vp_node->needed && vp_node->finalized 
+          if ( vp_node->needed && vp_node->finalized
 	       && (values != NULL_TREE)
               && (TREE_CODE (values) == CONSTRUCTOR)
               && (TREE_CODE (TREE_TYPE (values)) == ARRAY_TYPE))
@@ -413,7 +308,8 @@ register_vptr_fields (tree base_class_decl_arg, tree record_type, tree body)
                    cnt++)
                 {
                   tree value = ce->value;
-                  tree val_vtbl_decl = TREE_OPERAND (TREE_OPERAND (value, 0), 0);
+                  tree val_vtbl_decl = TREE_OPERAND (TREE_OPERAND (value, 0),
+                                                     0);
                   int len1 = strlen (IDENTIFIER_POINTER
 				     (DECL_NAME
 				          (TREE_OPERAND
@@ -429,10 +325,9 @@ register_vptr_fields (tree base_class_decl_arg, tree record_type, tree body)
                                                IDENTIFIER_POINTER
 					        (DECL_NAME (val_vtbl_decl)));
 
-                  already_registered = record_register_pairs (TREE_OPERAND
-                                                               (base_class_decl_arg, 0),
-                                                              val_vtbl_decl,
-                                                              value);
+                  already_registered = record_register_pairs (val_vtbl_decl,
+                                                              value,
+                                                              base_class);
 
                   if (already_registered)
                     continue;
@@ -463,7 +358,7 @@ register_vptr_fields (tree base_class_decl_arg, tree record_type, tree body)
 
 static void
 register_other_binfo_vtables (tree binfo, tree body, tree arg1, tree str1,
-                              int len1, tree str2, int len2)
+                              int len1, tree str2, int len2, tree base_class)
 {
   unsigned ix;
   tree base_binfo;
@@ -478,14 +373,15 @@ register_other_binfo_vtables (tree binfo, tree body, tree arg1, tree str1,
       if ((!BINFO_PRIMARY_P (base_binfo)
            || BINFO_VIRTUAL_P (base_binfo))
           && (vtable_decl=get_vtbl_decl_for_binfo (base_binfo))
-          && !(DECL_VTABLE_OR_VTT_P(vtable_decl) && DECL_CONSTRUCTION_VTABLE_P(vtable_decl)))
+          && !(DECL_VTABLE_OR_VTT_P(vtable_decl)
+               && DECL_CONSTRUCTION_VTABLE_P(vtable_decl)))
         {
           tree vtable_address = build_vtbl_address (base_binfo);
           tree call_expr;
 
-          already_registered = record_register_pairs (TREE_OPERAND (arg1, 0),
-                                                      vtable_decl,
-                                                      vtable_address);
+          already_registered = record_register_pairs (vtable_decl,
+                                                      vtable_address,
+                                                      base_class);
           if (!already_registered)
             {
               call_expr = build_call_expr (vlt_register_pairs_fndecl, 6,
@@ -501,203 +397,173 @@ register_other_binfo_vtables (tree binfo, tree body, tree arg1, tree str1,
         }
 
       register_other_binfo_vtables (base_binfo, body, arg1, str1, len1, str2,
-                                    len2);
+                                    len2, base_class);
     }
 }
-
 static void
-register_all_pairs (struct node *root, tree body)
+register_all_pairs (tree body)
 {
-  struct list_node *current;
+  /* struct list_node *current; */
+  struct vtbl_map_node *current;
   tree base_ptr_var_decl;
 
-  /* Handle current node */
-  if (!root || ! root->ptr_decl)
-    return;
-
-  base_ptr_var_decl = root->ptr_decl;
 
-  current = root->class_list;
-  while (current)
+  for (current = vtbl_map_nodes; current; current = current->next)
     {
-      if (current->class_type
-          && (TREE_CODE (current->class_type) == RECORD_TYPE))
-        {
-          tree new_type;
-          tree arg1;
-          tree call_expr;
-          bool already_registered;
+      unsigned i;
+      tree base_class = current->class_info->class_type;
+      base_ptr_var_decl = current->vtbl_map_decl;
 
-          tree binfo = TYPE_BINFO (current->class_type);
-	  tree vtable = NULL_TREE;
-          tree vtable_decl;
-          bool vtable_should_be_output = false;
-          bool debug = false;
+      gcc_assert (current->class_info != NULL);
 
-	  if (binfo)
-	    vtable = BINFO_VTABLE (binfo);
-
-          if (debug)
+      for (i = 0; i < num_vtable_map_nodes; ++i)
+        if (TEST_BIT (current->class_info->descendants, i))
           {
-            fprintf(stderr, "register_all_pairs: looking at class:\n");
-            debug_tree(current->class_type);
-          }
-          
-          vtable_decl = CLASSTYPE_VTABLES (current->class_type);
+            struct vtbl_map_node *vtbl_class_node = vtbl_map_nodes_array[i];
+            tree class_type = vtbl_class_node->class_info->class_type;
 
-          /* Handle main vtable for this class. */
-          if (vtable_decl)
+            if (class_type
+                && (TREE_CODE (class_type) == RECORD_TYPE))
             {
-              struct varpool_node *node = varpool_node (vtable_decl);
-              if (debug)
-              {
-                fprintf(stderr,"Varpool node:\n");
-                debug_varpool_node(node);
-              }
-              vtable_should_be_output = node->needed; 
-            }
+              tree new_type;
+              tree arg1;
+              tree call_expr;
+              bool already_registered;
 
-          if (debug)
-          {
-            fprintf(stderr, "register_all_pairs: the vtable is (should be output=%s):\n", vtable_should_be_output ? "yes": "no");
-            debug_tree(vtable_decl);
-          }
+              tree binfo = TYPE_BINFO (class_type);
+              tree vtable_decl;
+              bool vtable_should_be_output = false;
 
-          if (vtable_decl && vtable_should_be_output && BINFO_VTABLE (binfo))
-            {
-              tree vtable_address = build_vtbl_address (binfo);
-              int len1  = IDENTIFIER_LENGTH (DECL_NAME (base_ptr_var_decl));
-              int len2  = IDENTIFIER_LENGTH (DECL_NAME (vtable_decl));
-              tree str1 = build_string_literal (len1,
-                                                IDENTIFIER_POINTER
-                                                  (DECL_NAME
-                                                     (base_ptr_var_decl)));
-              tree str2 = build_string_literal (len2,
-                                                IDENTIFIER_POINTER
-                                                  (DECL_NAME (vtable_decl)));
+              vtable_decl = CLASSTYPE_VTABLES (class_type);
 
-              already_registered = record_register_pairs (base_ptr_var_decl,
-                                                          vtable_decl,
-                                                          vtable_address);
+              /* Handle main vtable for this class. */
 
-              if (!already_registered)
+              if (vtable_decl)
                 {
-                  if (debug)
-                  {
-                    fprintf(stderr, "register_all_pairs: building register pair call for vtable:\n");
-                    debug_tree(vtable_decl);
-                  }
-
-                  new_type = build_pointer_type (TREE_TYPE
-                                                   (base_ptr_var_decl));
-                  arg1 = build1 (ADDR_EXPR, new_type, base_ptr_var_decl);
-
-                  /* This call expr has the 2 "real" arguments, plus 4
-                     debugging arguments.  Eventually it will be replaced
-                     with the one just below it, which only has the 2 real
-                     arguments.  */
-                  call_expr = build_call_expr
-                      (vlt_register_pairs_fndecl, 6,
-                       arg1, vtable_address,
-                       str1, build_int_cst (integer_type_node,
-                                            len1),
-                       str2,  build_int_cst (integer_type_node,
-                                             len2));
-                  /* See comments above.  call_expr = build_call_expr
-                     (vlt_register_pairs_fndecl, 2, arg1, vtable);  */
-
-                  append_to_statement_list (call_expr, &body);
-
-                  /* Find and handle any 'extra' vtables associated
-                     with this class, via virtual inheritance.   */
-                  register_vptr_fields (arg1, current->class_type, body);
-
-                  /* Find and handle any 'extra' vtables associated
-                     with this class, via multiple inheritance.   */
-                  register_other_binfo_vtables (binfo, body, arg1, str1, len1,
-                                                str2, len2);
+                  struct varpool_node *node = varpool_node (vtable_decl);
+                  vtable_should_be_output = node->needed;
                 }
-            } /* if vtable_decl && vtable_should_be_output */
-        }
-      current = current->next;
 
-    } /* while there's a node in the linked list */
-
-  /* Handle left child */
-  register_all_pairs (root->left, body);
-
-  /* Handle right child */
-  register_all_pairs (root->right, body);
+              if (vtable_decl && vtable_should_be_output
+                  && BINFO_VTABLE (binfo))
+                {
+                  tree vtable_address = build_vtbl_address (binfo);
+                  int len1  = IDENTIFIER_LENGTH
+                                               (DECL_NAME (base_ptr_var_decl));
+                  int len2  = IDENTIFIER_LENGTH (DECL_NAME (vtable_decl));
+                  tree str1 = build_string_literal (len1,
+                                                    IDENTIFIER_POINTER
+                                                    (DECL_NAME
+                                                     (base_ptr_var_decl)));
+                  tree str2 = build_string_literal (len2,
+                                                    IDENTIFIER_POINTER
+                                                    (DECL_NAME (vtable_decl)));
+
+                  already_registered = record_register_pairs (vtable_decl,
+                                                              vtable_address,
+                                                              base_class);
+
+                  if (!already_registered)
+                    {
+                      new_type = build_pointer_type (TREE_TYPE
+                                                     (base_ptr_var_decl));
+                      arg1 = build1 (ADDR_EXPR, new_type, base_ptr_var_decl);
+
+                      /* This call expr has the 2 "real" arguments, plus 4
+                         debugging arguments.  Eventually it will be replaced
+                         with the one just below it, which only has the 2 real
+                         arguments.  */
+                      call_expr = build_call_expr
+                          (vlt_register_pairs_fndecl, 6,
+                           arg1, vtable_address,
+                           str1, build_int_cst (integer_type_node,
+                                                len1),
+                           str2,  build_int_cst (integer_type_node,
+                                                 len2));
+                      /* See comments above.  call_expr = build_call_expr
+                         (vlt_register_pairs_fndecl, 2, arg1, vtable);  */
+
+                      append_to_statement_list (call_expr, &body);
+
+                      /* Find and handle any 'extra' vtables associated
+                         with this class, via virtual inheritance.   */
+                      register_vptr_fields (arg1, base_class, class_type,
+                                            body);
+
+                      /* Find and handle any 'extra' vtables associated
+                         with this class, via multiple inheritance.   */
+                      register_other_binfo_vtables (binfo, body, arg1, str1,
+                                                    len1, str2, len2,
+                                                    base_class);
+                    }
+                } /* if vtable_decl && vtable_should_be_output */
+            } /* if TREE_TYPE (class_type) == RECORD... */
+          } /* if TEST_BIT (descendants, i) */
+    } /* for cur = vtbl_map_nodes... */
 }
 
-static void
-linked_list_insert (struct list_node **root, tree new_class)
+static struct vtv_graph_node *
+find_graph_node (tree class_type)
 {
-  struct list_node *current;
-  struct list_node *prev;
-  bool found = false;
-
-  for (prev = NULL, current = (*root); 
-       current && !found; 
-       prev = current, current = current->next)
-    if (current 
-	&& current->class_type == new_class)
-      found = true;
-
-  if (!found)
-    {
-      struct list_node *new_node = (struct list_node *)
-                                           xmalloc (sizeof (struct list_node));
+  tree class_decl = TREE_CHAIN (class_type);
+  tree class_name_id;
+  struct vtbl_map_node *vtbl_node;
 
-      new_node->class_type = new_class;
-      new_node->next = NULL;
+  if (class_decl)
+    class_name_id = DECL_ASSEMBLER_NAME (class_decl);
+  else
+    class_name_id = DECL_ASSEMBLER_NAME (TYPE_NAME (class_type));
 
-      if (!prev)
-	(*root) = new_node;
-      else
-	prev->next = new_node;
-    }
+  vtbl_node = vtbl_map_get_node (class_name_id);
+
+  if (vtbl_node)
+    return vtbl_node->class_info;
+
+  return NULL;
 }
 
 static void
-binary_tree_insert (struct node **root, tree ptr_decl, tree base_class,
-                    tree new_class)
+add_edge_to_graph (struct vtv_graph_node ***edge_array, unsigned *num_entries,
+                   unsigned *max_entries, struct vtv_graph_node *new_entry)
 {
-  /* DEBUG
-  fprintf(stderr, "binary_tree_insert: base_class: \n");
-  debug_tree(base_class);
-  fprintf(stderr, "binary_tree_insert, derived_class: \n");
-  debug_tree(new_class);
-  */
-
-  if (!(*root))
+  /* Check array size, and re-size it if necessary.  */
+  if (*num_entries >= ((*max_entries) - 1))
     {
-      struct node *new_node = (struct node *) xmalloc (sizeof (struct node));
-      new_node->ptr_decl = ptr_decl;
-      new_node->left = NULL;
-      new_node->right = NULL;
-      new_node->class_list = NULL;
-      linked_list_insert (&(new_node->class_list), base_class);
-      linked_list_insert (&(new_node->class_list), new_class);
-      (*root) = new_node;
+      unsigned new_size = 2 * (*max_entries);
+      unsigned i;
+      *edge_array = (struct vtv_graph_node **)
+          xrealloc (*edge_array, new_size * sizeof (struct vtv_graph_node *));
+
+      for (i = *max_entries; i < new_size; ++i)
+        (*edge_array)[i] = NULL;
+      *max_entries = new_size;
     }
-  else if ((DECL_NAME ((*root)->ptr_decl)) == (DECL_NAME (ptr_decl)))
-    linked_list_insert (&((*root)->class_list), new_class);
-  else if (ptr_decl < (*root)->ptr_decl)
-    binary_tree_insert (&((*root)->left), ptr_decl, base_class, new_class);
-  else
-    binary_tree_insert (&((*root)->right), ptr_decl, base_class, new_class);
+
+  (*edge_array)[*num_entries] = new_entry;
+  *num_entries = (*num_entries) + 1;
 }
 
 static void
-update_class_hierarchy_information (tree base_class_ptr_decl,
-                                    tree base_class,
+add_hierarchy_pair (struct vtv_graph_node *base_node,
+                    struct vtv_graph_node *derived_node)
+{
+  add_edge_to_graph (&(base_node->children), &(base_node->num_children),
+                     &(base_node->max_children), derived_node);
+  add_edge_to_graph (&(derived_node->parents), &(derived_node->num_parents),
+                     &(derived_node->max_parents), base_node);
+}
+
+void
+update_class_hierarchy_information (tree base_class,
                                     tree derived_class)
 {
-  binary_tree_insert (&vlt_class_hierarchy_info, base_class_ptr_decl,
-		      base_class, derived_class);
+  struct vtv_graph_node *base_node = find_graph_node (base_class);
+  struct vtv_graph_node *derived_node = find_graph_node (derived_class);
+
+  add_hierarchy_pair (base_node, derived_node);
 }
 
+
 bool
 vtv_register_class_hierarchy_information (tree body)
 {
@@ -710,9 +576,9 @@ vtv_register_class_hierarchy_information (tree body)
 
   /* DEBUG */
   if (false)  /* This is here for debugging purposes. */
-    dump_class_hierarchy_information (vlt_class_hierarchy_info);
+    dump_class_hierarchy_information ();
 
-  if (vlt_class_hierarchy_info != NULL)
+  if (any_verification_calls_generated)
     {
       /* Set permissions on vtable map data structure to be Read/Write. */
 
@@ -723,8 +589,7 @@ vtv_register_class_hierarchy_information (tree body)
 
       /* Add class hierarchy pairs to the vtable map data structure. */
 
-      /* compute_hierarchy_transitive_closure (); */
-      register_all_pairs (vlt_class_hierarchy_info, body);
+      register_all_pairs (body);
 
       /* Set permission on vtable map data structure to be Read-only.  */
 
@@ -738,41 +603,33 @@ vtv_register_class_hierarchy_information (tree body)
   return ret_val;
 }
 
-static tree
-vtable_find_map_decl (tree var_id)
-{
-  struct varpool_node *node;
-
-  for (node = varpool_nodes; node; node = node->next)
-    {
-      tree var_decl = node->decl;
-      if (DECL_NAME (var_decl) == var_id)
-        return var_decl;
-    }
-  return NULL_TREE;
-}
-
-static tree 
+struct vtbl_map_node *
 vtable_find_or_create_map_decl (tree base_type)
 {
   tree base_decl = TREE_CHAIN (base_type);
-  tree base_id = get_mangled_id (base_decl);
-  tree var_id;
+  tree base_id;
   tree var_decl = NULL;
   char *var_name = NULL;
+  struct vtbl_map_node *vtable_map_node = NULL;
+
 
   /* Verify the type has an associated vtable */
-  if (!TYPE_BINFO(base_type) || !BINFO_VTABLE (TYPE_BINFO (base_type)))
+  if (!TYPE_BINFO (base_type) || !BINFO_VTABLE (TYPE_BINFO (base_type)))
     return NULL;
 
+  if (base_decl)
+    base_id = DECL_ASSEMBLER_NAME (base_decl);
+  else
+    base_id = DECL_ASSEMBLER_NAME (TYPE_NAME (base_type));
+
   /* Create map lookup symbol for base class */
   var_name = ACONCAT (("_ZTV", IDENTIFIER_POINTER (base_id),
                        ".vtable_map", NULL));
-  var_id = maybe_get_identifier (var_name);
-  if (var_id)
-    /* We've already created the variable; just look for it */
-    var_decl = vtable_find_map_decl (var_id);
-  else
+  if (base_id)
+    /* We've already created the variable; just look it.  */
+    vtable_map_node = vtbl_map_get_node (base_id);
+
+  if (!vtable_map_node || (vtable_map_node->vtbl_map_decl == NULL_TREE))
     {
       /* If we haven't already created the *.vtable_map
          global variable for this class, do so now, and
@@ -800,7 +657,7 @@ vtable_find_or_create_map_decl (tree base_type)
          shown here.
       sect_name = ACONCAT ((".data.rel.ro.", var_name,
                             NULL));
-      */
+       */
       sect_name = ACONCAT ((".data.", var_name,
                             NULL));
 
@@ -811,41 +668,45 @@ vtable_find_or_create_map_decl (tree base_type)
       DECL_INITIAL (var_decl) = initial_value;
 
       varpool_finalize_decl (var_decl);
-      save_vtable_map_decl (var_decl);
-
-      update_class_hierarchy_information (var_decl, base_type, base_type);
+      if (!vtable_map_node)
+        vtable_map_node = vtbl_map_node (base_type);
+      if (vtable_map_node->vtbl_map_decl == NULL_TREE)
+        vtable_map_node->vtbl_map_decl = var_decl;
     }
 
-  gcc_assert(var_decl);
-  return var_decl;
+  gcc_assert (vtable_map_node);
+  return vtable_map_node;
 }
 
-void 
+void
 vtv_save_base_class_info (tree type)
 {
-  tree binfo =  TYPE_BINFO(type);
-  tree base_binfo;
-  tree own_map;
-  int i;
-
-  /* first make sure to create the map for this record type */
-  own_map = vtable_find_or_create_map_decl(type);
-  if (own_map == NULL)
-    return;
-
-  /* Go through the list of all base classes for the current (derived)
-     type, make sure the *.vtable_map global variable for the base class
-     exists, and add the base class/derived class pair to the class
-     hierarchy information we are accumulating (for vtable pointer
-     verification).  */
-  for (i = 0; BINFO_BASE_ITERATE(binfo, i, base_binfo); i++)
+  if (flag_vtable_verify)
     {
-      tree tree_val = BINFO_TYPE(base_binfo);
-      tree var_decl = NULL_TREE;
+      tree binfo =  TYPE_BINFO (type);
+      tree base_binfo;
+      struct vtbl_map_node *own_map;
+      int i;
+
+      /* first make sure to create the map for this record type */
+      own_map = vtable_find_or_create_map_decl (type);
+      if (own_map == NULL)
+        return;
+
+      /* Go through the list of all base classes for the current (derived)
+         type, make sure the *.vtable_map global variable for the base class
+	 exists, and add the base class/derived class pair to the class
+	 hierarchy information we are accumulating (for vtable pointer
+	 verification).  */
+      for (i = 0; BINFO_BASE_ITERATE(binfo, i, base_binfo); i++)
+        {
+          tree tree_val = BINFO_TYPE(base_binfo);
+          struct vtbl_map_node *vtable_map_node = NULL;
+
+          vtable_map_node = vtable_find_or_create_map_decl (tree_val);
 
-      var_decl = vtable_find_or_create_map_decl(tree_val);
-      if (var_decl != NULL)
-        update_class_hierarchy_information (var_decl, tree_val,
-                                            type);
+          if (vtable_map_node != NULL)
+            update_class_hierarchy_information (tree_val, type);
+        }
     }
 }
diff --git a/vtable-security/gcc/tree-vtable-verify.c b/vtable-security/gcc/tree-vtable-verify.c
index d03363ba90e..ba720689255 100644
--- a/vtable-security/gcc/tree-vtable-verify.c
+++ b/vtable-security/gcc/tree-vtable-verify.c
@@ -2,9 +2,6 @@
    Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
    Free Software Foundation, Inc.
 
-   Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
-   <mjambor@suse.cz>
-
 This file is part of GCC.
 
 GCC is free software; you can redistribute it and/or modify it under
@@ -45,6 +42,11 @@ along with GCC; see the file COPYING3.  If not see
 #include "toplev.h"
 #include "langhooks.h"
 
+#include "tree-vtable-verify.h"
+
+unsigned num_vtable_map_nodes = 0;
+bool any_verification_calls_generated = false;
+
 static GTY(()) tree verify_vtbl_ptr_fndecl = NULL_TREE;
 
 unsigned int vtable_verify_main (void);
@@ -52,6 +54,250 @@ static bool gate_tree_vtable_verify (void);
 static void build_vtable_verify_fndecl (void);
 static tree my_build1 (enum tree_code, tree, tree);
 
+bool
+vtbl_map_node_registration_find (struct vtbl_map_node *node,
+                                 tree vtable_decl,
+                                 unsigned offset)
+{
+  struct vtable_registration key;
+  struct vtable_registration **slot;
+
+  gcc_assert (node);
+  gcc_assert (node->registered);
+
+  key.vtable_decl = vtable_decl;
+  slot = (struct vtable_registration **) htab_find_slot (node->registered,
+                                                         &key, NO_INSERT);
+
+  if (slot && (*slot) && (*slot)->offsets)
+    {
+      unsigned i;
+      for (i = 0; i < (*slot)->cur_offset; ++i)
+        if ((*slot)->offsets[i] == offset)
+          return true;
+    }
+
+  return false;
+}
+
+void
+vtbl_map_node_registration_insert (struct vtbl_map_node *node,
+                                   tree vtable_decl,
+                                   unsigned offset)
+{
+  struct vtable_registration key;
+  struct vtable_registration **slot;
+
+  if (!node || !(node->registered))
+    return;
+
+  key.vtable_decl = vtable_decl;
+  slot = (struct vtable_registration **) htab_find_slot (node->registered,
+                                                         &key, INSERT);
+
+  if (!(*slot))
+    {
+      unsigned i;
+      struct vtable_registration *node;
+      node = (struct vtable_registration *)
+                                 xmalloc (sizeof (struct vtable_registration));
+      node->vtable_decl = vtable_decl;
+      node->offsets = (unsigned *) xmalloc (10 * sizeof (unsigned));
+      for (i= 0; i < 10; ++i)
+        node->offsets[i] = 0;
+      node->offsets[0] = offset;
+      node->cur_offset = 1;
+      node->max_offsets = 10;
+      *slot = node;
+    }
+  else
+    {
+      /* We found the vtable_decl slot; we need to see if it already
+         contains the offset.  If not, we need to add the offset.  */
+      unsigned i;
+      bool found = false;
+      for (i = 0; (i < (*slot)->cur_offset) && !found; ++i)
+        if ((*slot)->offsets[i] == offset)
+          found = true;
+
+      if (!found)
+        {
+          if ((*slot)->cur_offset == (*slot)->max_offsets)
+            {
+              unsigned new_max = 2 * (*slot)->max_offsets;
+              (*slot)->offsets = (unsigned *)
+                  xrealloc ((*slot)->offsets, new_max * sizeof (unsigned));
+
+              for (i = (*slot)->max_offsets; i < new_max; ++i)
+                (*slot)->offsets[i] = 0;
+              (*slot)->max_offsets = new_max;
+            }
+          (*slot)->offsets[(*slot)->cur_offset] = offset;
+          (*slot)->cur_offset = (*slot)->cur_offset + 1;
+        }
+    }
+}
+
+/* Hashtable functions for vtable_registration hashtables.  */
+
+static hashval_t
+hash_vtable_registration (const void * p)
+{
+  const struct vtable_registration *n = (const struct vtable_registration *) p;
+  return (hashval_t) (DECL_UID (n->vtable_decl));
+}
+
+static int
+eq_vtable_registration (const void *p1, const void *p2)
+{
+  const struct vtable_registration *n1 =
+                                    (const struct vtable_registration *) p1;
+  const struct vtable_registration *n2 =
+                                    (const struct vtable_registration *) p2;
+  return (DECL_UID (n1->vtable_decl) == DECL_UID (n2->vtable_decl));
+}
+
+/* End of hashtable functions for "registered" hashtables*/
+
+/* Hashtable functions for vtable_map variables hashtable.  */
+
+static htab_t vtbl_map_hash = NULL;
+struct vtbl_map_node *vtbl_map_nodes = NULL;
+struct vtbl_map_node **vtbl_map_nodes_array = NULL;
+
+static void
+vtable_map_array_insert (struct vtbl_map_node *node)
+{
+  static unsigned array_size = 0;
+  unsigned i;
+
+  if (vtbl_map_nodes_array == NULL
+      || array_size == 0)
+    {
+      array_size = 16;
+      vtbl_map_nodes_array = (struct vtbl_map_node **)
+                       xmalloc (array_size * sizeof (struct vtbl_map_node *));
+      memset (vtbl_map_nodes_array, 0,
+              array_size * sizeof (struct vtbl_map_node *));
+    }
+  else if (node->uid >= array_size)
+    {
+      unsigned new_size = 2 * array_size;
+      vtbl_map_nodes_array = (struct vtbl_map_node **)
+          xrealloc (vtbl_map_nodes_array,
+                    new_size * sizeof (struct vtbl_map_node *));
+
+      for (i = array_size; i < new_size; ++i)
+        vtbl_map_nodes_array[i] = NULL;
+
+      array_size = new_size;
+    }
+
+  gcc_assert (node->uid < array_size);
+  gcc_assert (vtbl_map_nodes_array[node->uid] == NULL);
+
+  vtbl_map_nodes_array[node->uid] = node;
+}
+
+/* Returns a hash code for P.  */
+static hashval_t
+hash_vtbl_map_node (const void *p)
+{
+  const struct vtbl_map_node *n = (const struct vtbl_map_node *) p;
+  return (hashval_t) IDENTIFIER_HASH_VALUE (n->class_name);
+}
+
+/* Returns nonzero if P1 and P2 are equal.  */
+static int
+eq_vtbl_map_node (const void *p1, const void *p2)
+{
+  const struct vtbl_map_node *n1 = (const struct vtbl_map_node *) p1;
+  const struct vtbl_map_node *n2 = (const struct vtbl_map_node *) p2;
+  return (IDENTIFIER_HASH_VALUE (n1->class_name) ==
+          IDENTIFIER_HASH_VALUE (n2->class_name));
+}
+
+/* Return vtbl_map node assigned to DECL without creating a new one.  */
+struct vtbl_map_node *
+vtbl_map_get_node (const_tree class_name)
+{
+  struct vtbl_map_node key;
+  struct vtbl_map_node **slot;
+
+  if (!vtbl_map_hash)
+    return NULL;
+
+  key.class_name = CONST_CAST2 (tree, const_tree, class_name);
+  slot = (struct vtbl_map_node **) htab_find_slot (vtbl_map_hash, &key,
+                                                   NO_INSERT);
+  if (!slot)
+    return NULL;
+  return *slot;
+}
+
+/* Return vtbl_map node assigned to BASE_CLASS_TYPE.  Create new one
+ * when needed.  */
+struct vtbl_map_node *
+vtbl_map_node (tree base_class_type)
+{
+  struct vtbl_map_node key;
+  struct vtbl_map_node *node;
+  struct vtbl_map_node **slot;
+  unsigned i;
+
+  if (!vtbl_map_hash)
+    vtbl_map_hash = htab_create (10, hash_vtbl_map_node,
+                                 eq_vtbl_map_node, NULL);
+
+  if (TREE_CHAIN (base_class_type))
+    key.class_name = DECL_ASSEMBLER_NAME (TREE_CHAIN (base_class_type));
+  else
+    key.class_name = DECL_ASSEMBLER_NAME (TYPE_NAME (base_class_type));
+  slot = (struct vtbl_map_node **) htab_find_slot (vtbl_map_hash, &key,
+                                                   INSERT);
+  if (*slot)
+    return *slot;
+
+  node = (struct vtbl_map_node *) xmalloc (sizeof (struct vtbl_map_node));
+  node->vtbl_map_decl = NULL_TREE;
+  node->class_name = key.class_name;
+  node->uid = num_vtable_map_nodes++;
+
+  node->class_info = (struct vtv_graph_node *)
+                                      xmalloc (sizeof (struct vtv_graph_node));
+  node->class_info->class_type = base_class_type;
+  node->class_info->class_uid = node->uid;
+  node->class_info->max_parents = 4;
+  node->class_info->max_children = 4;
+  node->class_info->num_parents = 0;
+  node->class_info->num_children = 0;
+  node->class_info->num_processed_children = 0;
+  node->class_info->parents = (struct vtv_graph_node **)
+                                xmalloc (4 * sizeof (struct vtv_graph_node *));
+  node->class_info->children = (struct vtv_graph_node **)
+                                xmalloc (4 * sizeof (struct vtv_graph_node *));
+  for (i = 0; i < 4; ++i)
+    {
+      node->class_info->parents[i] = NULL;
+      node->class_info->children[i] = NULL;
+    }
+
+  node->registered = htab_create (16, hash_vtable_registration,
+                                  eq_vtable_registration, NULL);
+  node->is_used = false;
+  node->next = vtbl_map_nodes;
+  if (vtbl_map_nodes)
+    vtbl_map_nodes->prev = node;
+
+  vtable_map_array_insert (node);
+
+  vtbl_map_nodes = node;
+  *slot = node;
+  return node;
+}
+
+/* End of hashtable functions for vtable_map variables hash table.   */
+
 static tree
 my_build1 (enum tree_code code, tree type, tree node MEM_STAT_DECL)
 {
@@ -222,54 +468,6 @@ my_get_vtbl_decl_for_binfo (tree binfo)
   return decl;
 }
 
-
-static tree *vtable_var_decl_array;
-static int vtable_var_decl_array_max = 0;
-static int vtable_var_decl_array_entries = 0;
-
-static tree
-find_vtable_map_decl (tree var_id)
-{
-  int idx;
-
-  for (idx = 0; idx < vtable_var_decl_array_entries; idx++)
-    if ((DECL_NAME (vtable_var_decl_array[idx])) == var_id)
-      return vtable_var_decl_array[idx];
-
-  return NULL_TREE;
-}
-
-void
-save_vtable_map_decl (tree var_decl)
-{
-  int idx;
-
-  /* TO DO:  This is not very efficient; consider improving this.  */
-
-  if (vtable_var_decl_array_max == 0)
-    {
-      vtable_var_decl_array = (tree *) xmalloc (100 * sizeof (tree));
-      vtable_var_decl_array_max = 100;
-      memset (vtable_var_decl_array, 0, 100 * sizeof (tree));
-    }
-  else if (vtable_var_decl_array_max <= vtable_var_decl_array_entries)
-    {
-      int new_max = 2 * vtable_var_decl_array_max;
-      vtable_var_decl_array = (tree *) xrealloc (vtable_var_decl_array,
-                                                 new_max * sizeof(tree));
-      for (idx = vtable_var_decl_array_max; idx < new_max; ++idx)
-        vtable_var_decl_array[idx] = NULL_TREE;
-
-      vtable_var_decl_array_max = new_max;
-    }
-
-  for (idx = 0; idx < vtable_var_decl_array_entries; idx++)
-    if (vtable_var_decl_array[idx] == var_decl)
-      return;
-
-  vtable_var_decl_array[vtable_var_decl_array_entries++] = var_decl;
-}
-
 static void
 verify_bb_vtables (basic_block bb)
 {
@@ -279,6 +477,14 @@ verify_bb_vtables (basic_block bb)
   gimple_stmt_iterator gsi_vtbl_assign;
   gimple_stmt_iterator gsi_virtual_call;
 
+  /* If we are in the global 'main' function, the very first thing
+     we need to do in the very first BB is to tell the __VerifyVtablePointer
+     function to actually start verification (it does not do verification
+     before 'main', during library and constructor initialization, because
+     the necessary verification data structures may not be complete then).
+     The assumption is that no hacker will be able to attack the program before
+    'main'... */
+
   /* Search the basic block to see if it contains a virtual method
      call, i.e. a call with the tree code OBJ_TYPE_REF  */
 
@@ -317,7 +523,6 @@ verify_bb_vtables (basic_block bb)
               tree lhs = gimple_assign_lhs (stmt);
               tree vtbl_var_decl = NULL_TREE;
               tree vtbl = NULL_TREE;
-              tree vtbl_ptr = NULL_TREE;
               const char *vtable_name = NULL;
               char *vtbl_map_name = NULL;
               tree var_id;
@@ -332,11 +537,13 @@ verify_bb_vtables (basic_block bb)
               if (TREE_CODE (rhs) == COMPONENT_REF)
                 {
                   bool vtbl_found = false;
+                  struct vtbl_map_node *vtable_map_node = NULL;
+
                   while (!vtbl_found)
                     {
                       if (TREE_CODE (rhs) == COMPONENT_REF
                           && (TREE_CODE (TREE_OPERAND (rhs, 1)) == FIELD_DECL)
-                          && (strncmp (IDENTIFIER_POINTER 
+                          && (strncmp (IDENTIFIER_POINTER
 				           (DECL_NAME (TREE_OPERAND (rhs, 1))),
                                        "_vptr.", 6) == 0))
                         {
@@ -357,16 +564,28 @@ verify_bb_vtables (basic_block bb)
                         continue;
 
                       if (TREE_CODE (TREE_TYPE (vtbl)) == POINTER_TYPE)
-                        vtbl_ptr = force_gimple_operand (vtbl, &pre_p, 1,
-                                                         NULL);
+                        force_gimple_operand (vtbl, &pre_p, 1, NULL);
 
-                      vtable_name = IDENTIFIER_POINTER 
+                      vtable_name = IDENTIFIER_POINTER
 			                          (DECL_NAME (vtbl_var_decl));
-                      vtbl_map_name = (char *) xmalloc 
+                      vtbl_map_name = (char *) xmalloc
 			                           (strlen (vtable_name) + 12);
                       sprintf (vtbl_map_name, "%s.vtable_map", vtable_name);
-                      var_id = get_identifier (vtbl_map_name);
-                      vtbl_var_decl = find_vtable_map_decl (var_id);
+
+                      if (TREE_CHAIN (TREE_TYPE (rhs)))
+                        var_id = DECL_ASSEMBLER_NAME (TREE_CHAIN
+                                                      (TREE_TYPE (rhs)));
+                      else
+                        var_id = DECL_ASSEMBLER_NAME (TYPE_NAME
+                                                      (TREE_TYPE (rhs)));
+                      vtable_map_node = vtbl_map_get_node (var_id);
+                      if (vtable_map_node)
+                        {
+                          vtbl_var_decl = vtable_map_node->vtbl_map_decl;
+                          vtable_map_node->is_used = true;
+                        }
+                      else
+                        vtbl_var_decl = NULL;
                     }
 
                   /* Build  verify_vtbl_ptr_fndecl */
@@ -381,10 +600,10 @@ verify_bb_vtables (basic_block bb)
                   if (verify_vtbl_ptr_fndecl && vtbl_var_decl)
                     {
                       tree expr_tree = NULL_TREE;
-                      tree t = NULL_TREE;
                       struct gimplify_ctx gctx;
                       tree arg4 = TREE_OPERAND (rhs, 0);
                       const char *vtable_name = "<unknown>";
+
                       int len1 = 0;
                       int len2 = 0;
 
@@ -396,38 +615,38 @@ verify_bb_vtables (basic_block bb)
 
                       if ((TREE_CODE (arg4) == SSA_NAME)
                           && (DECL_NAME (SSA_NAME_VAR (arg4))))
-                        vtable_name = IDENTIFIER_POINTER 
-			                     (DECL_NAME (SSA_NAME_VAR (arg4)));
+                        vtable_name = IDENTIFIER_POINTER
+                                             (DECL_NAME (SSA_NAME_VAR (arg4)));
 
                       push_gimplify_context (&gctx);
-                      len1 = strlen (IDENTIFIER_POINTER 
+                      len1 = strlen (IDENTIFIER_POINTER
 				                  (DECL_NAME (vtbl_var_decl)));
                       len2 = strlen (vtable_name);
 
-                      expr_tree = build_call_expr 
+                      expr_tree = build_call_expr
 			             (verify_vtbl_ptr_fndecl, 6,
 				      my_build1 (ADDR_EXPR,
-						 TYPE_POINTER_TO 
+						 TYPE_POINTER_TO
 						   (TREE_TYPE (vtbl_var_decl)),
 						 vtbl_var_decl),
 				      SSA_NAME_VAR (lhs),
-				      build_string_literal 
+				      build_string_literal
 				                  (len1,
-						   IDENTIFIER_POINTER 
-						       (DECL_NAME 
+						   IDENTIFIER_POINTER
+						       (DECL_NAME
 							    (vtbl_var_decl))),
 				      build_int_cst (integer_type_node,
 						     len1),
 				      build_string_literal (len2, vtable_name),
 				      build_int_cst (integer_type_node,
 						     len2));
-		      /*  Eventually we will remove the 4 'debugging' 
+		      /*  Eventually we will remove the 4 'debugging'
 			  parameters from the call above and will use the
 			  call below instead.
-                      expr_tree = build_call_expr 
+                      expr_tree = build_call_expr
 		                     (verify_vtbl_ptr_fndecl, 2,
 				      my_build1 (ADDR_EXPR,
-				                 TYPE_POINTER_TO 
+				                 TYPE_POINTER_TO
                                                    (TREE_TYPE (vtbl_var_decl)),
                                                  vtbl_var_decl),
                                       SSA_NAME_VAR (lhs));
@@ -438,8 +657,8 @@ verify_bb_vtables (basic_block bb)
                          update_ssa.  */
 
                       mark_sym_for_renaming (SSA_NAME_VAR (lhs));
-                      t = force_gimple_operand (expr_tree, &pre_p, 1,
-                                                SSA_NAME_VAR (lhs));
+                      force_gimple_operand (expr_tree, &pre_p, 1,
+                                            SSA_NAME_VAR (lhs));
 
                       /* Insert the new call just after the original assignment
                          of the object's vtable pointer.  */
@@ -447,6 +666,7 @@ verify_bb_vtables (basic_block bb)
                       pop_gimplify_context (NULL);
                       gsi_insert_seq_after (&gsi_vtbl_assign, pre_p,
                                             GSI_NEW_STMT);
+                      any_verification_calls_generated = true;
                     }
                 }
             }
@@ -471,9 +691,11 @@ build_vtable_verify_fndecl (void)
   /* Start: Arg types to be removed when we remove debugging parameters from
      the library function. */
   arg_types = chainon (arg_types, build_tree_list (NULL_TREE, char_ptr_type));
-  arg_types = chainon (arg_types, build_tree_list (NULL_TREE, integer_type_node));
+  arg_types = chainon (arg_types, build_tree_list (NULL_TREE,
+                                                   integer_type_node));
   arg_types = chainon (arg_types, build_tree_list (NULL_TREE, char_ptr_type));
-  arg_types = chainon (arg_types, build_tree_list (NULL_TREE, integer_type_node));
+  arg_types = chainon (arg_types, build_tree_list (NULL_TREE,
+                                                   integer_type_node));
   /* End: Arg types to be removed...*/
   arg_types = chainon (arg_types, build_tree_list (NULL_TREE, void_type_node));
 
diff --git a/vtable-security/gcc/tree-vtable-verify.h b/vtable-security/gcc/tree-vtable-verify.h
new file mode 100644
index 00000000000..9996379c00b
--- /dev/null
+++ b/vtable-security/gcc/tree-vtable-verify.h
@@ -0,0 +1,81 @@
+/* Interprocedural constant propagation
+   Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
+   Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC 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.
+
+GCC 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 GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+/* Virtual Table Pointer Security.  */
+
+#ifndef TREE_VTABLE_VERIFY_H
+#define TREE_VTABLE_VERIFY_H
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "timevar.h"
+#include "cpplib.h"
+#include "tree.h"
+#include "hashtab.h"
+#include "sbitmap.h"
+
+extern unsigned num_vtable_map_nodes;
+extern bool any_verification_calls_generated;
+
+struct vtable_registration
+{
+  tree vtable_decl;
+  unsigned max_offsets;
+  unsigned cur_offset;
+  unsigned *offsets;
+};
+
+struct vtv_graph_node {
+  tree class_type;
+  unsigned class_uid;
+  unsigned max_parents;
+  unsigned max_children;
+  unsigned num_parents;
+  unsigned num_children;
+  unsigned num_processed_children;
+  struct vtv_graph_node **parents;
+  struct vtv_graph_node **children;
+  sbitmap descendants;
+};
+
+struct vtbl_map_node {
+  tree vtbl_map_decl;
+  tree class_name;
+  struct vtv_graph_node *class_info;
+  unsigned uid;
+  struct vtbl_map_node *next, *prev;
+  htab_t registered;
+  bool is_used;
+};
+
+extern struct vtbl_map_node *vtbl_map_nodes;
+extern struct vtbl_map_node **vtbl_map_nodes_array;
+
+extern struct vtbl_map_node *vtbl_map_get_node (const_tree);
+extern struct vtbl_map_node *vtbl_map_node (tree);
+extern void vtbl_map_node_class_insert (struct vtbl_map_node *, unsigned);
+extern bool vtbl_map_node_registration_find (struct vtbl_map_node *,
+                                             tree, unsigned);
+extern void vtbl_map_node_registration_insert (struct vtbl_map_node *,
+                                               tree, unsigned);
+
+#endif /* TREE_VTABLE_VERIFY_H */