[PATCH]: Pool allocation of a few structures

[Daniel Berlin <dberlin at dberlin dot org>]

This patch includes a pool based allocator for fixed size objects, and
uses it for et-forest things and basic blocks, to improve locality.
This does better than the patch i submitted yesterday, it knocks 12
seconds (out of 26) off branch prediction rather than 10, and improves
cache locality of basic block traversals.

The et-forest changes no longer depend on ggc-page behavior.

The basic blocks used to be obstack allocated, with a freelist. This is
close to what the pool does, except the pool doesn't have anything but
basic blocks to allocate.

I've not included a changelog (the changes to existing files are trivial
enough to look at and answer the question below), though this patch was
bootstrapped on i686-pc-linux-gnu and reg-tested.

I only wanted to know whether it *would* be acceptable to include a pool
allocator for fixed size objects and use it in gcc, and whether the
current one included is acceptable. If so, i'll split up the patch below
into a submission of the new files, and one patch each for the changes to
allocate et-forest.c and cfg.c.

Thus, the lack of a changelog since i just want people to look at the new
files and an example of how it's used.
--Dan


Index: alloc-pool.c
===================================================================
RCS file: alloc-pool.c
diff -N alloc-pool.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ alloc-pool.c	17 Dec 2002 20:26:42 -0000
@@ -0,0 +1,167 @@
+/* Functions to support a pool of allocatable objects.
+   Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
+   Contributed by Daniel Berlin <dan@cgsoftware.com>
+
+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 2, 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 COPYING.  If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+#include "libiberty.h"
+#include "config.h"
+#include "system.h"
+#include "toplev.h"
+#include "alloc-pool.h"
+
+#define align_four(x) (((x+3) >> 2) << 2)
+#define align_eight(x) (((x+7) >> 3) << 3)
+
+/* Create a pool of things of size SIZE, with NUM in each block we
+   allocate.  */
+
+alloc_pool
+create_alloc_pool (name, size, num)
+     const char *name;
+     size_t size;
+     size_t num;
+{
+  alloc_pool pool;
+  size_t pool_size, header_size;
+
+  if (!name)
+    abort ();
+
+  /* Make size large enough to store the list header.  */
+  if (size < sizeof (alloc_pool_list))
+    size = sizeof (alloc_pool_list);
+
+  /* Now align the size to a multiple of 4.  */
+  size = align_four (size);
+
+  /* Um, we can't really allocate 0 elements per block.  */
+  if (num == 0)
+    abort ();
+
+  /* Find the size of the pool structure, and the name.  */
+  pool_size = sizeof (struct alloc_pool_def);
+
+  /* and allocate that much memory.  */
+  pool = (alloc_pool) xmalloc (pool_size);
+
+  /* Now init the various pieces of our pool structure.  */
+  pool->name = xstrdup (name);
+  pool->elt_size = size;
+  pool->elts_per_block = num;
+
+  /* List header size should be a multiple of 8 */
+  header_size = align_eight (sizeof (struct alloc_pool_list_def));
+
+  pool->block_size = (size * num) + header_size;
+  pool->free_list = NULL;
+  pool->elts_allocated = 0;
+  pool->elts_free = 0;
+  pool->blocks_allocated = 0;
+  pool->block_list = NULL;
+
+  return (pool);
+}
+
+/* Free all memory allocated for the given memory pool.  */
+void
+free_alloc_pool (pool)
+     alloc_pool pool;
+{
+  alloc_pool_list block, next_block;
+
+  if (!pool)
+    abort ();
+
+  /* Free each block allocated to the pool.  */
+  for (block = pool->block_list; block != NULL; block = next_block)
+    {
+      next_block = block->next;
+      free (block);
+    }
+  /* Lastly, free the pool and the name.  */
+  free (pool->name);
+  free (pool);
+}
+
+/* Allocates one element from the pool specified.  */
+void *
+pool_alloc (pool)
+     alloc_pool pool;
+{
+  alloc_pool_list header;
+  char *block;
+
+  if (!pool)
+    abort ();
+
+  /* If there are no more free elements, make some more!.  */
+  if (!pool->free_list)
+    {
+      size_t i;
+      alloc_pool_list block_header;
+
+      /* Make the block */
+      block = (char *) xmalloc (pool->block_size);
+      block_header = (alloc_pool_list) block;
+      block += align_eight (sizeof (struct alloc_pool_list_def));
+
+      /* Throw it on the block list */
+      block_header->next = pool->block_list;
+      pool->block_list = block_header;
+
+      /* Now put the actual block pieces onto the free list.  */
+      for (i = 0; i < pool->elts_per_block; i++, block += pool->elt_size)
+      {
+        header = (alloc_pool_list) block;
+        header->next = pool->free_list;
+        pool->free_list = header;
+      }
+      /* Also update the number of elements we have free/allocated, and
+         increment the allocated block count.  */
+      pool->elts_allocated += pool->elts_per_block;
+      pool->elts_free += pool->elts_per_block;
+      pool->blocks_allocated += 1;
+    }
+
+  /* Pull the first free element from the free list, and return it.  */
+  header = pool->free_list;
+  pool->free_list = header->next;
+  pool->elts_free--;
+  return ((void *) header);
+}
+
+/* Puts PTR back on POOL's free list.  */
+void
+pool_free (pool, ptr)
+     alloc_pool pool;
+     void *ptr;
+{
+  alloc_pool_list header;
+
+  if (!ptr)
+    abort ();
+
+  /* Check if we free more than we allocated, which is Bad (TM).  */
+  if (pool->elts_free + 1 > pool->elts_allocated)
+    abort ();
+  header = (alloc_pool_list) ptr;
+  header->next = pool->free_list;
+  pool->free_list = header;
+  pool->elts_free++;
+}
Index: alloc-pool.h
===================================================================
RCS file: alloc-pool.h
diff -N alloc-pool.h
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ alloc-pool.h	17 Dec 2002 20:26:42 -0000
@@ -0,0 +1,48 @@
+
+/* Functions to support a pool of allocatable objects
+   Copyright (C) 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
+   Contributed by Daniel Berlin <dan@cgsoftware.com>
+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 2, 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 COPYING.  If not, write to
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA.  */
+#ifndef ALLOC_POOL_H
+#define ALLOC_POOL_H
+
+typedef struct alloc_pool_list_def
+{
+  struct alloc_pool_list_def *next;
+}
+ *alloc_pool_list;
+
+typedef struct alloc_pool_def
+{
+  char *name;
+  size_t elts_per_block;
+  alloc_pool_list free_list;
+  size_t elts_allocated;
+  size_t elts_free;
+  size_t blocks_allocated;
+  alloc_pool_list block_list;
+  size_t block_size;
+  size_t elt_size;
+}
+ *alloc_pool;
+
+extern alloc_pool create_alloc_pool PARAMS ((const char *, size_t, size_t));
+extern void free_alloc_pool PARAMS ((alloc_pool));
+extern void *pool_alloc PARAMS ((alloc_pool));
+extern void pool_free PARAMS ((alloc_pool, void *));
+#endif
Index: et-forest.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/et-forest.c,v
retrieving revision 1.1.6.2
diff -u -3 -p -r1.1.6.2 et-forest.c
--- et-forest.c	25 Sep 2002 19:16:05 -0000	1.1.6.2
+++ et-forest.c	17 Dec 2002 20:26:43 -0000
@@ -26,6 +26,7 @@ Boston, MA 02111-1307, USA.
 #include "config.h"
 #include "system.h"
 #include "et-forest.h"
+#include "alloc-pool.h"

 struct et_forest_occurrence;
 typedef struct et_forest_occurrence* et_forest_occurrence_t;
@@ -35,6 +36,8 @@ struct et_forest
 {
   /* Linked list of nodes is used to destroy the structure.  */
   int nnodes;
+  alloc_pool node_pool;
+  alloc_pool occur_pool;
 };

 /* Single occurrence of node in ET-forest.
@@ -71,7 +74,7 @@ struct et_forest_node


 static et_forest_occurrence_t splay PARAMS ((et_forest_occurrence_t));
-static void remove_all_occurrences PARAMS ((et_forest_node_t));
+static void remove_all_occurrences PARAMS ((et_forest_t, et_forest_node_t));
 static inline et_forest_occurrence_t find_leftmost_node
                                PARAMS ((et_forest_occurrence_t));
 static inline et_forest_occurrence_t find_rightmost_node
@@ -334,7 +337,8 @@ splay (node)

 /* Remove all occurences of the given node before destroying the node.  */
 static void
-remove_all_occurrences (forest_node)
+remove_all_occurrences (forest, forest_node)
+     et_forest_t forest;
      et_forest_node_t forest_node;
 {
   et_forest_occurrence_t first = forest_node->first;
@@ -379,7 +383,7 @@ remove_all_occurrences (forest_node)
       if (prev_node->node->last == next_node)
 	prev_node->node->last = prev_node;

-      free (next_node);
+      pool_free (forest->occur_pool, next_node);
     }

   if (first != last)
@@ -398,14 +402,14 @@ remove_all_occurrences (forest_node)
 	    node->right->parent = 0;

 	  next_node = node->next;
-	  free (node);
+	  pool_free (forest->occur_pool, node);
 	  node = next_node;
 	}
     }

-  free (first);
+  pool_free (forest->occur_pool, first);
   if (first != last)
-    free (last);
+    pool_free (forest->occur_pool, last);
 }

 /* Calculate ET value of the given node.  */
@@ -437,6 +441,8 @@ et_forest_create ()
   et_forest_t forest = xmalloc (sizeof (struct et_forest));

   forest->nnodes = 0;
+  forest->occur_pool = create_alloc_pool ("et_forest_occurrence pool", sizeof (struct et_forest_occurrence), 300);
+  forest->node_pool = create_alloc_pool ("et_forest_node pool", sizeof (struct et_forest_node), 300);
   return forest;
 }

@@ -449,7 +455,8 @@ et_forest_delete (forest)
 {
   if (forest->nnodes)
     abort ();
-
+  free_alloc_pool (forest->occur_pool);
+  free_alloc_pool (forest->node_pool);
   free (forest);
 }

@@ -464,8 +471,8 @@ et_forest_add_node (forest, value)
   et_forest_node_t node;
   et_forest_occurrence_t occ;

-  node = xmalloc (sizeof (struct et_forest_node));
-  occ = xmalloc (sizeof (struct et_forest_occurrence));
+  node = pool_alloc (forest->node_pool);
+  occ = pool_alloc (forest->occur_pool);

   node->first = node->last = occ;
   node->value = value;
@@ -503,7 +510,7 @@ et_forest_add_edge (forest, parent_node,
   if (child_occ->left)
     abort ();  /* child must be root of its containing tree.  */

-  new_occ = xmalloc (sizeof (struct et_forest_occurrence));
+  new_occ = pool_alloc (forest->occur_pool);

   new_occ->node = parent_node;
   new_occ->left = child_occ;
@@ -530,10 +537,10 @@ et_forest_remove_node (forest, node)
      et_forest_t forest;
      et_forest_node_t node;
 {
-  remove_all_occurrences (node);
+  remove_all_occurrences (forest, node);
   forest->nnodes--;

-  free (node);
+  pool_free (forest->node_pool, node);
 }

 /* Remove edge from the tree, return 1 if sucesfull,
@@ -573,7 +580,7 @@ et_forest_remove_edge (forest, parent_no
   if (parent_post_occ == parent_node->last)
     parent_node->last = parent_pre_occ;

-  free (parent_post_occ);
+  pool_free (forest->occur_pool, parent_post_occ);
   return 1;
 }

Index: cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfg.c,v
retrieving revision 1.18.6.5
diff -u -3 -p -r1.18.6.5 cfg.c
--- cfg.c	3 Sep 2002 23:04:51 -0000	1.18.6.5
+++ cfg.c	17 Dec 2002 20:26:43 -0000
@@ -55,12 +55,14 @@ Software Foundation, 59 Temple Place - S
 #include "toplev.h"
 #include "tm_p.h"
 #include "obstack.h"
+#include "alloc-pool.h"

 /* The obstack on which the flow graph components are allocated.  */

 struct obstack flow_obstack;
 static char *flow_firstobj;

+static alloc_pool bb_pool;
 /* Number of basic blocks in the current function.  */

 int n_basic_blocks;
@@ -76,7 +78,6 @@ int n_edges;
 /* First edge in the deleted edges chain.  */

 edge first_deleted_edge;
-static basic_block first_deleted_block;

 /* The basic block array.  */

@@ -139,7 +140,6 @@ init_flow ()
   static int initialized;

   first_deleted_edge = 0;
-  first_deleted_block = 0;
   n_edges = 0;

   if (!initialized)
@@ -150,9 +150,11 @@ init_flow ()
     }
   else
     {
+      free_alloc_pool (bb_pool);
       obstack_free (&flow_obstack, flow_firstobj);
       flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
     }
+  bb_pool = create_alloc_pool ("Basic block pool", sizeof (struct basic_block_def), 100);
 }

 /* Helper function for remove_edge and clear_edges.  Frees edge structure
@@ -214,18 +216,8 @@ basic_block
 alloc_block ()
 {
   basic_block bb;
-
-  if (first_deleted_block)
-    {
-      bb = first_deleted_block;
-      first_deleted_block = (basic_block) bb->succ;
-      bb->succ = NULL;
-    }
-  else
-    {
-      bb = (basic_block) obstack_alloc (&flow_obstack, sizeof *bb);
-      memset (bb, 0, sizeof *bb);
-    }
+  bb = pool_alloc (bb_pool);
+  memset (bb, 0, sizeof (*bb));
   return bb;
 }

@@ -270,7 +262,6 @@ compact_blocks ()
   last_basic_block = n_basic_blocks;
 }

-
 /* Remove block B from the basic block array.  */

 void
@@ -280,12 +271,7 @@ expunge_block (b)
   unlink_block (b);
   BASIC_BLOCK (b->index) = NULL;
   n_basic_blocks--;
-
-  /* Invalidate data to make bughunting easier.  */
-  memset (b, 0, sizeof *b);
-  b->index = -3;
-  b->succ = (edge) first_deleted_block;
-  first_deleted_block = (basic_block) b;
+  pool_free (bb_pool, b);
 }

 /* Create an edge connecting SRC and DST with FLAGS optionally using