Patch: GC marker bitmaps for gcj

[Tom Tromey <tromey at cygnus dot com>]

This patch adds a new `-fuse-boehm-gc' flag to gcj.  If this flag is
given, gcj emits a special bitmap for each class; this bitmap can be
used by the Boehm GC to trace Java objects more efficiently (the
current method of using a mark function turns out to be quite slow).

The generated bitmap is not yet used by libgcj.  It needs a special
version of the GC in order to work.  However, having this code in gcj
doesn't hurt -- it is disabled by default.  I want to check it in so
that other people (namely, Hans Boehm) can continue work where I've
been forced (by schedule pressure) to leave off.

Is this ok to go in?

2000-02-17  Tom Tromey  <tromey@cygnus.com>

	* Makefile.in (JAVA_OBJS): Added boehm.o.
	(boehm.o): New target.
	* Make-lang.in (JAVA_SRCS): Added boehm.c.
	* java-tree.h (flag_use_boehm_gc): Declare.
	* lang.c (lang_f_options): Added `use-boehm-gc'.
	(flag_use_boehm_gc): New global.
	* lang-options.h: Added -fuse-boehm-gc.
	* boehm.c: New file.
	* class.c (get_dispatch_table): If class uses a Boehm type
	descriptor, put it in the vtable.

Tom

Index: Make-lang.in
===================================================================
RCS file: /cvs/gcc/egcs/gcc/java/Make-lang.in,v
retrieving revision 1.27
diff -u -r1.27 Make-lang.in
--- Make-lang.in	2000/02/03 18:39:48	1.27
+++ Make-lang.in	2000/02/17 19:27:44
@@ -74,7 +74,7 @@
   $(srcdir)/java/verify.c $(srcdir)/java/zextract.c $(srcdir)/java/jcf-io.c \
   $(srcdir)/java/jcf-parse.c $(srcdir)/java/mangle.c \
   $(srcdir)/java/jcf-write.c $(srcdir)/java/buffer.c \
-  $(srcdir)/java/check-init.c \
+  $(srcdir)/java/check-init.c $(srcdir)/java/boehm.c \
   $(srcdir)/java/jcf-depend.c  $(srcdir)/java/jcf-path.c
 
 jc1$(exeext): $(P) $(JAVA_SRCS) $(LIBDEPS) stamp-objlist ggc-callbacks.o
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/egcs/gcc/java/Makefile.in,v
retrieving revision 1.47
diff -u -r1.47 Makefile.in
--- Makefile.in	2000/02/15 16:36:34	1.47
+++ Makefile.in	2000/02/17 19:27:51
@@ -165,7 +165,7 @@
 #
 JAVA_OBJS = parse.o class.o decl.o expr.o constants.o lang.o typeck.o \
   except.o verify.o zextract.o jcf-io.o jcf-parse.o mangle.o jcf-write.o \
-  buffer.o check-init.o jcf-depend.o jcf-path.o xref.o
+  buffer.o check-init.o jcf-depend.o jcf-path.o xref.o boehm.o
 
 JAVA_OBJS_LITE = parse-scan.o jv-scan.o
 
@@ -267,6 +267,8 @@
   jcf-reader.c jcf.h javaop.h javaop.def $(srcdir)/../version.h
 gjavah.o : $(CONFIG_H) $(srcdir)/../system.h $(JAVA_TREE_H) gjavah.c \
   jcf-reader.c jcf.h javaop.h $(srcdir)/../version.h
+boehm.o: boehm.c $(CONFIG_H) $(srcdir)/../system.h $(TREE_H) $(JAVA_TREE_H) \
+  $(PARSE_H)
 buffer.o : buffer.c $(CONFIG_H) buffer.h $(srcdir)/../gansidecl.h \
   $(srcdir)/../system.h $(srcdir)/../toplev.h
 check-init.o : check-init.c $(CONFIG_H) $(srcdir)/../gansidecl.h \
Index: boehm.c
===================================================================
RCS file: boehm.c
diff -N boehm.c
--- /dev/null	Tue May  5 13:32:27 1998
+++ boehm.c	Thu Feb 17 11:28:42 2000
@@ -0,0 +1,149 @@
+/* Functions related to the Boehm garbage collector.
+   Copyright (C) 1999 Free Software Foundation, Inc.
+
+This file is part of GNU CC.
+
+GNU CC 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.
+
+GNU CC 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 GNU CC; see the file COPYING.  If not, write to
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA.
+
+Java and all Java-based marks are trademarks or registered trademarks
+of Sun Microsystems, Inc. in the United States and other countries.
+The Free Software Foundation is independent of Sun Microsystems, Inc.  */
+
+/* Written by Tom Tromey <tromey@cygnus.com>.  */
+
+#include <config.h>
+
+#include "system.h"
+#include "tree.h"
+#include "java-tree.h"
+#include "parse.h"
+
+/* Compute a procedure-based object descriptor.  We know that our
+   `kind' is 0, and `env' is likewise 0, so we have a simple
+   computation.  From the GC sources:
+	    (((((env) << LOG_MAX_MARK_PROCS) | (proc_index)) << DS_TAG_BITS) \
+	    | DS_PROC)
+   Here DS_PROC == 2.  */
+#define PROCEDURE_OBJECT_DESCRIPTOR build_int_2 (2, 0)
+
+/* Treat two HOST_WIDE_INT's as a contiguous bitmap, with bit 0 being
+   the least significant.  This function sets bit N in the bitmap.  */
+static void
+set_bit (unsigned HOST_WIDE_INT *low, unsigned HOST_WIDE_INT *high,
+	 unsigned int n)
+{
+  HOST_WIDE_INT *which;
+
+  if (n >= CHAR_BIT * sizeof (HOST_WIDE_INT))
+    {
+      n -= CHAR_BIT * sizeof (HOST_WIDE_INT);
+      which = high;
+    }
+  else
+    which = low;
+
+  *which |= 1 << n;
+}
+
+/* Return the marking bitmap for the class TYPE.  For now this is a
+   single word describing the type.  class_uses_boehm_type_descriptor
+   must return 1 for TYPE for this function to be meaningful.  */
+tree
+get_boehm_type_descriptor (tree type)
+{
+  unsigned int count, bit, log2_size;
+  int all_bits_set = 1;
+  int last_set_index = 0;
+  int pointer_after_end = 0;
+  unsigned HOST_WIDE_INT low = 0, high = 0;
+  tree field, value;
+
+  /* If the GC wasn't requested, just use a null pointer.  */
+  if (! flag_use_boehm_gc)
+    return null_pointer_node;
+
+  /* If we have a type of unknown size, use a proc.  */
+  if (int_size_in_bytes (type) == -1)
+    return PROCEDURE_OBJECT_DESCRIPTOR;
+
+  bit = int_size_in_bytes (ptr_type_node);
+  /* The size of this node has to be known.  And, we only support 32
+     and 64 bit targets, so we need to know that the log2 is one of
+     our values.  */
+  log2_size = exact_log2 (bit);
+  if (bit == -1 || (log2_size != 2 && log2_size != 3))
+    {
+      /* This means the GC isn't supported.  We should probably
+	 abort or give an error.  Instead, for now, we just silently
+	 revert.  FIXME.  */
+      return null_pointer_node;
+    }
+  bit *= BITS_PER_UNIT;
+
+  field = TYPE_FIELDS (type);
+  if (DECL_NAME (field) == NULL_TREE)
+    field = TREE_CHAIN (field);  /* Skip dummy field for inherited data. */
+  for (count = 0; field != NULL_TREE; field = TREE_CHAIN (field))
+    {
+      if (FIELD_STATIC (field))
+	continue;
+
+      if (JREFERENCE_TYPE_P (TREE_TYPE (field)))
+	{
+	  last_set_index = count;
+	  /* First word in object corresponds to most significant byte
+	     of bitmap.  */
+	  set_bit (&low, &high, bit - count);
+	  if (count > bit - 2)
+	    pointer_after_end = 1;
+	}
+      else
+	all_bits_set = 0;
+
+      ++count;
+    }
+
+  /* If the object is all pointers, or if the part with pointers fits
+     in our bitmap, then we are ok.  Otherwise we have to allocate it
+     a different way.  */
+  if (all_bits_set)
+    {
+      /* In the GC the computation looks something like this:
+	 value = DS_LENGTH | WORDS_TO_BYTES (last_set_index + 1);
+	 DS_LENGTH is 0.
+	 WORDS_TO_BYTES shifts by log2(bytes-per-pointer).  */
+      count = 0;
+      ++last_set_index;
+      while (last_set_index)
+	{
+	  if ((last_set_index & 1))
+	    set_bit (&low, &high, log2_size + count);
+	  last_set_index >>= 1;
+	  ++count;
+	}
+      value = build_int_2 (low, high);
+    }
+  else if (! pointer_after_end)
+    {
+      /* Bottom two bits for bitmap mark type are 01.  */
+      set_bit (&low, &high, 0);
+      value = build_int_2 (low, high);
+    }
+  else
+    value = PROCEDURE_OBJECT_DESCRIPTOR;
+
+  return value;
+}
Index: class.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/java/class.c,v
retrieving revision 1.53
diff -u -r1.53 class.c
--- class.c	2000/01/21 20:57:00	1.53
+++ class.c	2000/02/17 19:28:54
@@ -1132,8 +1132,11 @@
 			build1 (ADDR_EXPR, nativecode_ptr_type_node, method),
 			list);
     }
-  /* Dummy entry for compatibility with G++ -fvtable-thunks. */
-  list = tree_cons (integer_zero_node, null_pointer_node, list);
+  /* Dummy entry for compatibility with G++ -fvtable-thunks.  When
+     using the Boehm GC we sometimes stash a GC type descriptor
+     there.  */
+  list = tree_cons (integer_zero_node, get_boehm_type_descriptor (type),
+		    list);
   list = tree_cons (integer_zero_node, this_class_addr, list);
   return build (CONSTRUCTOR, build_prim_array_type (nativecode_ptr_type_node,
 						    nvirtuals + 2),
Index: java-tree.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/java/java-tree.h,v
retrieving revision 1.52
diff -u -r1.52 java-tree.h
--- java-tree.h	2000/02/09 14:08:44	1.52
+++ java-tree.h	2000/02/17 19:29:08
@@ -139,6 +139,9 @@
 /* When non zero, call a library routine to do integer divisions. */
 extern int flag_use_divide_subroutine;
 
+/* When non zero, generate code for the Boehm GC.  */
+extern int flag_use_boehm_gc;
+
 /* The Java .class file that provides main_class;  the main input file. */
 extern struct JCF *current_jcf;
 
Index: lang-options.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/java/lang-options.h,v
retrieving revision 1.11
diff -u -r1.11 lang-options.h
--- lang-options.h	1999/07/21 14:51:24	1.11
+++ lang-options.h	2000/02/17 19:29:08
@@ -1,5 +1,5 @@
 /* Switch definitions for the GNU compiler for the Java(TM) language.
-   Copyright (C) 1998 Free Software Foundation, Inc.
+   Copyright (C) 1998, 1999 Free Software Foundation, Inc.
 
 This file is part of GNU CC.
 
@@ -33,6 +33,7 @@
   { "-fno-assume-compiled", "" },
   { "-femit-class-file", "" },
   { "-femit-class-files", "Dump class files to <name>.class" },
+  { "-fuse-boehm-gc", "Generate code for Boehm GC" },
 #if ! USE_CPPLIB
   { "-MD", "Print dependencies to FILE.d" },
   { "-MMD", "Print dependencies to FILE.d" },
Index: lang.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/java/lang.c,v
retrieving revision 1.35
diff -u -r1.35 lang.c
--- lang.c	2000/01/21 20:57:00	1.35
+++ lang.c	2000/02/17 19:29:13
@@ -110,6 +110,9 @@
 /* When non zero, call a library routine to do integer divisions. */
 int flag_use_divide_subroutine = 1;
 
+/* When non zero, generate code for the Boehm GC.  */
+int flag_use_boehm_gc = 0;
+
 /* From gcc/flags.h, and indicates if exceptions are turned on or not.  */
 
 extern int flag_new_exceptions;
@@ -127,6 +130,7 @@
   {"emit-class-file", &flag_emit_class_files, 1},
   {"emit-class-files", &flag_emit_class_files, 1},
   {"use-divide-subroutine", &flag_use_divide_subroutine, 1},
+  {"use-boehm-gc", &flag_use_boehm_gc, 1},
 };
 
 JCF *current_jcf;