ggc-page.c: Avoid division in ggc_set_mark.

	* ggc-page.c: Avoid division in ggc_set_mark.
	(DIV_MULT, DIV_SHIFT, OFFSET_TO_BIT, inverse_table,
	compute_inverse): New.
	(ggc_set_mark, ggc_marked_p): Use OFFSET_TO_BIT.
	(init_ggc): Initialize inverse_table.

From-SVN: r56512

2 files changed, 76 insertions, 17 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 05ebd77..b27072a 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,11 @@
+2002-08-22  Zack Weinberg  <zack@codesourcery.com>
+
+	* ggc-page.c: Avoid division in ggc_set_mark.
+	(DIV_MULT, DIV_SHIFT, OFFSET_TO_BIT, inverse_table,
+	compute_inverse): New.
+	(ggc_set_mark, ggc_marked_p): Use OFFSET_TO_BIT.
+	(init_ggc): Initialize inverse_table.
+
 2002-08-22  Tom Tromey  <tromey@redhat.com>
 
 	* doc/install.texi (Configuration): Document --datadir.
@@ -46,7 +54,7 @@
 	* config/rs6000/rs6000.c: Ditto.
 	* config/stormy16/stormy16.h: Ditto.
 	* doc/md.texi: Ditto.
-	
+
 2002-08-21  John David Anglin  <dave@hiauly1.hia.nrc.ca>
 
 	* cppinit.c (remove_dup_nonsys_dirs): Fix warning and return value.
@@ -59,11 +67,11 @@
 	errors.
 
 2002-08-21  Andrew Pinski <pinskia@physics.uc.edu>
-            Kaveh R. Ghazi  <ghazi@caip.rutgers.edu>
+	    Kaveh R. Ghazi  <ghazi@caip.rutgers.edu>
 
 	* doc/tm.texi (TARGET_ASM_GLOBALIZE_LABEL): Move '@end deftypefn'
 	to the actual end.  Add '@end table' and '@table @code'.
-	
+
 2002-08-20  Geoffrey Keating  <geoffk@redhat.com>
 
 	* doc/tm.texi (Label Output): Add missing '@end deftypefn'.
@@ -157,7 +165,7 @@
 
 2002-08-20  Devang Patel  <dpatel@apple.com>
 	* tree.c (get_qualified_type): Add TYPE_CONTEXT check.
-	
+
 2002-08-20  Kaveh R. Ghazi  <ghazi@caip.rutgers.edu>
 
 	* arc.c (output_shift): Use stdio instead of asm_fprintf.
@@ -205,7 +213,7 @@
 	(mips_use_dfa_pipeline_interface): Use.
 
 2002-08-15  Eric Christopher  <echristo@redhat.com>
-            Richard Sandiford <rsandifo@redhat.com>
+	    Richard Sandiford <rsandifo@redhat.com>
 	    Aldy Hernandez  <aldyh@redhat.com>
 	    Graham Stott    <grahams@redhat.com>
 	    Michael Meissner  <meissner@redhat.com>
@@ -249,8 +257,8 @@
 	quote and bracket include chains when they duplicate equivalent system
 	directories.
 	* doc/cpp.texi (-I): Update.
-        * doc/cppopts.texi (-I): Update.
-        * doc/install.texi (--with-local-prefix): Further document usage of
+	* doc/cppopts.texi (-I): Update.
+	* doc/install.texi (--with-local-prefix): Further document usage of
 	this option.
 	* doc/invoke.texi (-I): Update.
 
@@ -558,7 +566,7 @@
 
 2002-08-14  Dale Johannesen  <dalej@apple.com>
 
-        * explow.c (emit_stack_restore):  Emit memory clobbers
+	* explow.c (emit_stack_restore):  Emit memory clobbers
 	preceding the stack pop, to prevent the scheduler from
 	moving refs to variable arrays below this pop.
 	* reload1.c (reload):  Preserve these clobbers for sched2.
@@ -794,7 +802,7 @@ Tue Aug 13 17:40:25 2002  J"orn Rennecke <joern.rennecke@superh.com>
 2002-08-13  Denis Chertykov  <denisc@overta.ru>
 
 	* config/avr/avr.md: Call CC_STATUS_INIT in all peepnoles
-        which can change CC0.
+	which can change CC0.
 
 Tue Aug 13 14:49:20 2002  J"orn Rennecke <joern.rennecke@superh.com>
 
@@ -1357,10 +1365,10 @@ Sat Aug 10 19:59:43 CEST 2002  Jan Hubicka  <jh@suse.cz>
 
 2002-08-06  Aldy Hernandez  <aldyh@redhat.com>
 
-        * c-decl.c (duplicate_decls): Error out for incompatible TLS
-        declarations.
+	* c-decl.c (duplicate_decls): Error out for incompatible TLS
+	declarations.
 
-        * testsuite/gcc.dg/tls/diag-3.c: New.
+	* testsuite/gcc.dg/tls/diag-3.c: New.
 
 2002-08-06  Jason Merrill  <jason@redhat.com>
 
@@ -1369,7 +1377,7 @@ Sat Aug 10 19:59:43 CEST 2002  Jan Hubicka  <jh@suse.cz>
 
 2002-08-06  Dale Johannesen  <dalej@apple.com>
 	* c-common.c (fname_decl): Use line number 0 for
-        __func__, to avoid confusing debuggers.
+	__func__, to avoid confusing debuggers.
 
 2002-08-06  Nathan Sidwell  <nathan@codesourcery.com>
 
diff --git a/gcc/ggc-page.c b/gcc/ggc-page.c
index 9a5644a..af3af1a 100644
--- a/gcc/ggc-page.c
+++ b/gcc/ggc-page.c
@@ -158,6 +158,15 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 /* The size of an object on a page of the indicated ORDER.  */
 #define OBJECT_SIZE(ORDER) object_size_table[ORDER]
 
+/* For speed, we avoid doing a general integer divide to locate the
+   offset in the allocation bitmap, by precalculating numbers M, S
+   such that (O * M) >> S == O / Z (modulo 2^32), for any offset O
+   within the page which is evenly divisible by the object size Z.  */
+#define DIV_MULT(ORDER) inverse_table[ORDER].mult
+#define DIV_SHIFT(ORDER) inverse_table[ORDER].shift
+#define OFFSET_TO_BIT(OFFSET, ORDER) \
+  (((OFFSET) * DIV_MULT (ORDER)) >> DIV_SHIFT (ORDER))
+
 /* The number of extra orders, not corresponding to power-of-two sized
    objects.  */
 
@@ -209,6 +218,17 @@ static unsigned objects_per_page_table[NUM_ORDERS];
 
 static size_t object_size_table[NUM_ORDERS];
 
+/* The Ith entry is a pair of numbers (mult, shift) such that
+   ((k * mult) >> shift) mod 2^32 == (k / OBJECT_SIZE(I)) mod 2^32,
+   for all k evenly divisible by OBJECT_SIZE(I).  */
+
+static struct
+{
+  unsigned int mult;
+  unsigned int shift;
+}
+inverse_table[NUM_ORDERS];
+
 /* A page_entry records the status of an allocation page.  This
    structure is dynamically sized to fit the bitmap in_use_p.  */
 typedef struct page_entry
@@ -377,6 +397,7 @@ static void release_pages PARAMS ((void));
 static void clear_marks PARAMS ((void));
 static void sweep_pages PARAMS ((void));
 static void ggc_recalculate_in_use_p PARAMS ((page_entry *));
+static void compute_inverse PARAMS ((unsigned));
 
 #ifdef GGC_POISON
 static void poison_pages PARAMS ((void));
@@ -988,7 +1009,7 @@ ggc_set_mark (p)
 
   /* Calculate the index of the object on the page; this is its bit
      position in the in_use_p bitmap.  */
-  bit = (((const char *) p) - entry->page) / OBJECT_SIZE (entry->order);
+  bit = OFFSET_TO_BIT (((const char *) p) - entry->page, entry->order);
   word = bit / HOST_BITS_PER_LONG;
   mask = (unsigned long) 1 << (bit % HOST_BITS_PER_LONG);
 
@@ -1028,7 +1049,7 @@ ggc_marked_p (p)
 
   /* Calculate the index of the object on the page; this is its bit
      position in the in_use_p bitmap.  */
-  bit = (((const char *) p) - entry->page) / OBJECT_SIZE (entry->order);
+  bit = OFFSET_TO_BIT (((const char *) p) - entry->page, entry->order);
   word = bit / HOST_BITS_PER_LONG;
   mask = (unsigned long) 1 << (bit % HOST_BITS_PER_LONG);
 
@@ -1045,8 +1066,37 @@ ggc_get_size (p)
   return OBJECT_SIZE (pe->order);
 }
 
-/* Initialize the ggc-mmap allocator.  */
+/* Subroutine of init_ggc which computes the pair of numbers used to
+   perform division by OBJECT_SIZE (order) and fills in inverse_table[].
+
+   This algorithm is taken from Granlund and Montgomery's paper
+   "Division by Invariant Integers using Multiplication"
+   (Proc. SIGPLAN PLDI, 1994), section 9 (Exact division by
+   constants).  */
+
+static void
+compute_inverse (order)
+     unsigned order;
+{
+  unsigned size, inv, e;
+
+  size = OBJECT_SIZE (order);
+  e = 0;
+  while (size % 2 == 0)
+    {
+      e++;
+      size >>= 1;
+    }
 
+  inv = size;
+  while (inv * size != 1)
+    inv = inv * (2 - inv*size);
+
+  DIV_MULT (order) = inv;
+  DIV_SHIFT (order) = e;
+}
+
+/* Initialize the ggc-mmap allocator.  */
 void
 init_ggc ()
 {
@@ -1109,12 +1159,13 @@ init_ggc ()
       object_size_table[order] = s;
     }
 
-  /* Initialize the objects-per-page table.  */
+  /* Initialize the objects-per-page and inverse tables.  */
   for (order = 0; order < NUM_ORDERS; ++order)
     {
       objects_per_page_table[order] = G.pagesize / OBJECT_SIZE (order);
       if (objects_per_page_table[order] == 0)
 	objects_per_page_table[order] = 1;
+      compute_inverse (order);
     }
 
   /* Reset the size_lookup array to put appropriately sized objects in