This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Java: indirect virtual dispatch for binary compatibility


One current problem with GCJ is that it is constrained by C++ ABI for 
field access and method calls. The C++ ABI does not support java's rules 
for binary compatibility, so it is impossible to create a 
dynamically-linked application binary with GCJ and expect it to continue 
working without recompilation if any underlying classes (such as those 
in libgcj itself) are modified such that the virtual methods table and 
field layouts are different.

As an example, consider the following classes:

class A
{
  void a() { System.out.println ("a"); }
}

public class B
{
  public static void main(String[] args)
  {
    new A().a();
  }
}

We could compile these separately but link them together into the same 
executable:

$ gcj -c A.java
$ gcj -c B.java
$ gcj A.o B.o --main=B
$ ./a.out
a

Now imagine that we insert a new method, b, into class A, and recompile 
A.java but not B.java. We get the wrong result:

class A
{
  void b() { System.out.println ("b"); }
  void a() { System.out.println ("a"); }
}

$ ./a.out
b

This is because the layout of the virtual table for A has changed, but B 
was compiled with a reference to a fixed offset within A and is not 
aware of the change. B will call the wrong method and crash or 
misbehave. Naturally, this makes it very difficult to evolve shared 
class libraries while retaining compatibility with existing compiled 
applications.

A similar problem exists for fields, which are loaded using fixed 
offsets from an object pointer. If the location of these fields changes, 
any code referencing them will break.

The Java language specification defines a set of "binary compatibility 
rules" which determine what changes to classes should and should not 
cause incompatibility between their binary representations: 
http://java.sun.com/docs/books/jls/second_edition/html/binaryComp.doc.html
Previously, GCJ has simply ignored these rules, but it is desirable, and 
not entirely unreasonable, to implement them.

So...

This patch introduces an "--indirect-dispatch" option which does two things:

1. defers vtable layout until runtime
2. changes the way virtual and interface calls are compiled so that 
vtable offsets are resolved symbolically at runtime

It does this by introducing "offset tables" which are filled out by the 
runtime during class preparation/linking to contain the actual vtable 
offsets for any virtual methods called by code in the compilation unit. 
Rather than compiling calls to reference a fixed offset within the 
vtable, they reference a fixed offset within the offsets table, and load 
from that location the offset within the vtable to find the code pointer 
for the called method.

Basically, "call obj->vtable[X]" becomes "call obj->vtable[otable[Y]]".

Where X and Y are compile-time constants. To give some idea of the extra 
overhead involved, the Java code "System.out.println("Hello")", which 
without indirect dispatch compiles on x86 with -O2 to:

    movl    _ZN4java4lang6System3outE, %eax
    movl    (%eax), %edx
    movl    %eax, (%esp)
    movl    _CD_Hello+4, %eax
    movl    %eax, 4(%esp)
    call    *116(%edx)

With --indirect-dispatch, it becomes:

    movl    _ZN4java4lang6System3outE, %eax
    movl    (%eax), %edx
    movl    %eax, (%esp)
    movl    _CD_Hello+4, %eax
    movl    %eax, 4(%esp)
    movl    otable+4, %eax
    call    *(%eax,%edx)

When the same call occurs in succession or in a loop, the compiler moves 
the otable load out of the loop, so the overhead is reduced.

What does this cost? Running the attached "factorial" benchmark, which 
calls an inner recursive factorial function either defined as a static, 
virtual, or interface call, gives these results on a 650Mhz mobile P3:

with -O2:
static factorial: 10.933s
virtual factorial: 6.565s
interface factorial: 13.774s

with -O2 --indirect-dispatch:
static factorial: 10.928s
virtual factorial: 6.368s
interface factorial: 13.023s

So, strangely, this benchmark actually speeds up on x86 using indirect 
dispatch! On PowerPC (7410), there was a small slowdown for the virtual 
and interface calls, but in both cases they still ran substantially 
faster than non-virtuals, even without -fPIC. (Q: Why are non-virtual 
calls so slow?)

For real applications (ie not just micro-benchmarks), my suspicion is 
that there would be some slowdown, but the difference is certainly not 
large.

As for space, binarys typically turn out to be *smaller* with indirect 
dispatch than without it since getting rid of the vtables saves more 
space than is added by the symbols for the offset table. Two new pointer 
fields were added to java.lang.Class (otable and otable_syms), and 3 
utf8 constants are emitted for each of the methods in the offset table. 
A new "index" field was added to the _Jv_Method structure, however its 
size was not increased (apart from extra debugging symbols) since it 
just makes use of space that was previously lost to alignment. This new 
field will also be useful in simplifying/speeding up some existing 
interpreter and reflection code.

This technique retains complete compatibility with the existing ABI. 
That is, a single libgcj.so compiled without indirect dispatch can 
support binaries compiled either with or without indirect dispatch, and 
those compiled with it get all the binary compatibility benefits. And an 
object compiled without indirect dispatch can still call into 
indirect-dispatch compiled object without problems. I would like to make 
binary compatibility the default behaviour eventually, but 
--no-indirect-dispatch etc can be used for maximum performance when 
compatibility is not an issue.

The patch currently only implements indirect virtual and interface 
dispatch. Things that still need to be worked on include:

1. Fields. Should be able to be implemented using a similar offset table 
technique, with the offset being the offset from object pointer rather 
than vtable offsets. For field access within classes in the compilation 
unit, we can make a potential optimization: Since we know that field 
order cannot change without recompiling the unit, we just need to know 
the position within the object that the fields of the class in question 
begin at, which can be stored in the metaclass object or some other 
convenient location. Then, we add it to the statically-known offset from 
that position to access a field. This has the advantage of being able to 
re-use the same value for multiple field accesses, and not having to 
load values from a potentially large table, however it does require 
three adds (this + class->offset + field_offset) rather than two (this + 
otable[X]), so some testing would be required to determine if it is 
definatly a win.

2. Interface calls. The patch already implements a partial solution for 
interface calls, however it is not completely compliant with the binary 
compatibility rules. While methods can be added/deleted/reordered within 
an interface without problems, a method moved to a superinterface will 
not be found by the dispatch mechanism. This is because an interface 
call in GCJ requires the object reference, method offset, and a 
reference to the target interface to complete. A layout like:

interface A { void a(); }
interface B extends A {void b(); }

generates an itable like {A.class, *a, B.class, *b}. If b() were moved 
into A, the itable would now look like {A.class, *a, *b, B.class}. The 
call site has B.class statically compiled into it, and there is no fixed 
offset from B.class to get to b() due to multiple inheritance, so the 
call cannot be completed. One solution would be to generate itables 
which contain all inherited methods for each interface, ie {A.class, *a, 
B.class, *a, *b}. This would add no additional overhead, but I can 
imagine the itables growing unreasonably large with some inheritance 
heirarchies, and this is probibly not what JITs etc are expecting. The 
second solution is to have the otable, for interface calls, contain an 
offset and target interface pair so that both of these are set 
dynamically. This should be a net size win over the first option, and, 
hey, people expect interface calls to be slower anyway ;-)

3. Throwing exceptions at the right time. In order to support 
NoSuchMethodError as per the spec, we can add a special entry in each 
vtable pointing to a throw function. When a method required for an 
otable is found not to exist, the offset to this entry is put in the 
table. The patch doesn't do this yet, a call to a missing method has 
undefined behaviour. For fields, luckily we only have to throw an error 
at link-time so there is no issue there.

4. CNI. The C++ compiler will need to understand the new mechanisms when 
dealing with extern "Java" classes (in order to get the benefits of 
binary compatibility). One issue is how the C++ compiler will register 
any offset tables it needs to be filled out with the runtime, since it 
can't use fields in class objects as the Java compiler does. One 
solution would be to use global constructors much like the class 
registration mechanism already used by java, though we may lose the 
"lazy linking" benefit that Java gets, since otables only need to be 
resolved when a class using them is initialized.

5. Static methods and fields. These are already resolved symbolically, 
but by the dynamic linker not the gcj runtime. Thus they are not really 
binary compatible per the spec since link time errors will occur if they 
are missing rather than Java exceptions. So do we want to implement our 
own static method tables etc? Again, C++ will have to play too.

My thanks to Dachuan Yu who provided much of the initial inspiration for 
this patch as well as an early test implementation. I know that Dachuan 
was looking at running the SpecJVM benchmarks against GCJ, so perhaps he 
could provide some more comprehensive performance figures.

regards

Bryce.


Attachment: appeal-bench.tar.gz
Description: GNU Zip compressed data

2001-12-10  Bryce McKinlay  <bryce@waitaki.otago.ac.nz>

	* java-tree.h (otable_methods, otable_decl, otable_syms_decl,
	otable_type, otable_ptr_type, method_symbol_type, 
	method_symbols_array_type, method_symbols_array_ptr_type): New
	field/global tree definitions.
	(flag_indirect_dispatch): New flag.
	* decl.c (java_init_decl_processing): Initialize new otable and 
	otable_syms type nodes and decls. Add new field "index" to
	method_type_node.
	* class.c (build_method_symbols_entry): New function.
	(make_method_value): Set "index" to to method's vtable index for
	virtual methods when indirect-dispatch is not used.
	(make_class_data): For indirect-dispatch, dont emit the dtable_decl,
	and set vtable_method_count to -1. Set otable and otable_syms field
	if indirect-dispatch is used and there was something to put in them.
	(build_method_symbols_entry): New function.
	(emit_offset_symbol_table): New function.
	* expr.c (get_offset_table_index): New function.
	(build_invokevirtual): Build array reference to otable at the index 
	returned by get_offset_table_index, and use the result as the vtable
	offset.
	(build_invokeinterface): Similar.
	* jcf-parse.c (yyparse): If indirect-dispatch, call 
	emit_offset_symbol_table at the end of compilation, after all classes 
	have been generated.
	* jvspec.c: Don't pass findirect-dispatch to jvgenmain.
	* lang.c (flag_indirect_dispatch): Define.
	(lang_f_options): Add indirect-dispatch flag.

2001-12-10  Bryce McKinlay  <bryce@waitaki.otago.ac.nz>

	* include/jvm.h (_Jv_VTable::idx_to_offset): New method.
	* java/lang/natClassLoader.cc (_Jv_PrepareCompiledClass): Call
	_Jv_MakeVTable and _Jv_LinkOffsetTable if needed.
	* java/lang/Class.h (_Jv_Method): Add "index" field.
	(_Jv_MethodSymbol): New struct type.
	(_Jv_LinkOffsetTable, _Jv_LayoutVTableMethods, _Jv_SetVTableEntries,
	_Jv_MakeVTable): Friends.
	(otable, otable_syms): New Class fields.
	* java/lang/natClass.cc (_Jv_LinkOffsetTable): New function.
	(isVirtualMethod): New static function.
	(_Jv_LayoutVTableMethods): New function.
	(_Jv_SetVTableEntries): New function.
	(_Jv_MakeVTable): New function.


Index: gcc/java/decl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/decl.c,v
retrieving revision 1.112
diff -u -r1.112 decl.c
--- decl.c	2001/12/06 23:12:55	1.112
+++ decl.c	2001/12/10 09:38:38
@@ -613,6 +613,35 @@
   dtable_type = make_node (RECORD_TYPE);
   dtable_ptr_type = build_pointer_type (dtable_type);
 
+  otable_type = make_node (RECORD_TYPE);
+  otable_ptr_type = build_pointer_type (otable_type);
+
+  method_symbol_type = make_node (RECORD_TYPE);
+  PUSH_FIELD (method_symbol_type, field, "clname", utf8const_ptr_type);
+  PUSH_FIELD (method_symbol_type, field, "name", utf8const_ptr_type);
+  PUSH_FIELD (method_symbol_type, field, "signature", utf8const_ptr_type);
+  FINISH_RECORD (method_symbol_type);
+
+  one_elt_array_domain_type = build_index_type (integer_one_node);
+  method_symbols_array_type = build_array_type (method_symbol_type, 
+						one_elt_array_domain_type);
+  method_symbols_array_ptr_type = build_pointer_type 
+				  (method_symbols_array_type);
+
+  otable_decl = build_decl (VAR_DECL, get_identifier ("otable"), 
+			    build_array_type (integer_type_node, 
+			    one_elt_array_domain_type));
+  DECL_EXTERNAL (otable_decl) = 1;
+  TREE_STATIC (otable_decl) = 1;
+  TREE_READONLY (otable_decl) = 1;
+  pushdecl (otable_decl);
+  
+  otable_syms_decl = build_decl (VAR_DECL, get_identifier ("otable_syms"), 
+    method_symbols_array_type);
+  TREE_STATIC (otable_syms_decl) = 1;
+  TREE_CONSTANT (otable_syms_decl) = 1;
+  pushdecl (otable_syms_decl);
+  
   PUSH_FIELD (object_type_node, field, "vtable", dtable_ptr_type);
   /* This isn't exactly true, but it is what we have in the source.
      There is an unresolved issue here, which is whether the vtable
@@ -646,6 +675,9 @@
   PUSH_FIELD (class_type_node, field, "field_count", short_type_node);
   PUSH_FIELD (class_type_node, field, "static_field_count", short_type_node);
   PUSH_FIELD (class_type_node, field, "vtable", dtable_ptr_type);
+  PUSH_FIELD (class_type_node, field, "otable", otable_ptr_type);
+  PUSH_FIELD (class_type_node, field, "otable_syms", 
+  	      method_symbols_array_ptr_type);
   PUSH_FIELD (class_type_node, field, "interfaces",
 	      build_pointer_type (class_ptr_type));
   PUSH_FIELD (class_type_node, field, "loader", ptr_type_node);
@@ -660,6 +692,11 @@
   for (t = TYPE_FIELDS (class_type_node);  t != NULL_TREE;  t = TREE_CHAIN (t))
     FIELD_PRIVATE (t) = 1;
   push_super_field (class_type_node, object_type_node);
+
+  /* Hash synchronization requires double-word alignment for all monitors. */
+  if (flag_hash_synchronization && POINTER_SIZE < 64)
+    TYPE_ALIGN (class_type_node) = POINTER_SIZE * 2;
+
   FINISH_RECORD (class_type_node);
   build_decl (TYPE_DECL, get_identifier ("Class"), class_type_node);
 
@@ -679,7 +716,6 @@
   FINISH_RECORD (field_type_node);
   build_decl (TYPE_DECL, get_identifier ("Field"), field_type_node);
 
-  one_elt_array_domain_type = build_index_type (integer_one_node);
   nativecode_ptr_array_type_node
     = build_array_type (nativecode_ptr_type_node, one_elt_array_domain_type);
 
@@ -716,6 +752,7 @@
   PUSH_FIELD (method_type_node, field, "name", utf8const_ptr_type);
   PUSH_FIELD (method_type_node, field, "signature", utf8const_ptr_type);
   PUSH_FIELD (method_type_node, field, "accflags", access_flags_type_node);
+  PUSH_FIELD (method_type_node, field, "index", unsigned_short_type_node);
   PUSH_FIELD (method_type_node, field, "ncode", nativecode_ptr_type_node);
   PUSH_FIELD (method_type_node, field, "throws", ptr_type_node);
   FINISH_RECORD (method_type_node);
Index: gcc/java/class.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/class.c,v
retrieving revision 1.117
diff -u -r1.117 class.c
--- class.c	2001/12/06 23:12:55	1.117
+++ class.c	2001/12/10 09:38:39
@@ -58,6 +58,8 @@
 static struct hash_entry *init_test_hash_newfunc PARAMS ((struct hash_entry *,
 							  struct hash_table *,
 							  hash_table_key));
+static tree build_method_symbols_entry PARAMS ((tree));
+
 static rtx registerClass_libfunc;
 static rtx registerResource_libfunc;
 
@@ -1269,9 +1271,16 @@
 {
   static int method_name_count = 0;
   tree minit;
+  tree index;
   tree code;
 #define ACC_TRANSLATED          0x4000
   int accflags = get_access_flags_from_decl (mdecl) | ACC_TRANSLATED;
+
+  if (!flag_indirect_dispatch && DECL_VINDEX (mdecl) != NULL_TREE)
+    index = DECL_VINDEX (mdecl);
+  else
+    index = integer_minus_one_node;
+
   code = null_pointer_node;
   if (DECL_RTL_SET_P (mdecl))
     code = build1 (ADDR_EXPR, nativecode_ptr_type_node, mdecl);
@@ -1289,6 +1298,7 @@
 			 IDENTIFIER_LENGTH(signature)))));
   }
   PUSH_FIELD_VALUE (minit, "accflags", build_int_2 (accflags, 0));
+  PUSH_FIELD_VALUE (minit, "index", index);
   PUSH_FIELD_VALUE (minit, "ncode", code);
 
   {
@@ -1531,7 +1541,7 @@
   rest_of_decl_compilation (methods_decl, (char*) 0, 1, 0);
 
   if (assume_compiled (IDENTIFIER_POINTER (DECL_NAME (type_decl)))
-      && ! CLASS_INTERFACE (type_decl))
+      && ! CLASS_INTERFACE (type_decl) && !flag_indirect_dispatch)
     {
       tree dtable = get_dispatch_table (type, this_class_addr);
       dtable_decl = build_dtable_decl (type);
@@ -1625,7 +1635,12 @@
   PUSH_FIELD_VALUE (cons, "methods",
 		    build1 (ADDR_EXPR, method_ptr_type_node, methods_decl));
   PUSH_FIELD_VALUE (cons, "method_count",  build_int_2 (method_count, 0));
-  PUSH_FIELD_VALUE (cons, "vtable_method_count", TYPE_NVIRTUALS (type));
+
+  if (flag_indirect_dispatch)
+    PUSH_FIELD_VALUE (cons, "vtable_method_count", integer_minus_one_node)
+  else
+    PUSH_FIELD_VALUE (cons, "vtable_method_count", TYPE_NVIRTUALS (type));
+    
   PUSH_FIELD_VALUE (cons, "fields",
 		    fields_decl == NULL_TREE ? null_pointer_node
 		    : build1 (ADDR_EXPR, field_ptr_type_node, fields_decl));
@@ -1633,9 +1648,27 @@
   PUSH_FIELD_VALUE (cons, "field_count", build_int_2 (field_count, 0));
   PUSH_FIELD_VALUE (cons, "static_field_count",
 		    build_int_2 (static_field_count, 0));
-  PUSH_FIELD_VALUE (cons, "vtable",
-		    dtable_decl == NULL_TREE ? null_pointer_node
-		    : build1 (ADDR_EXPR, dtable_ptr_type, dtable_decl));
+
+  if (flag_indirect_dispatch)
+    PUSH_FIELD_VALUE (cons, "vtable", null_pointer_node)
+  else
+    PUSH_FIELD_VALUE (cons, "vtable",
+		      dtable_decl == NULL_TREE ? null_pointer_node
+		      : build1 (ADDR_EXPR, dtable_ptr_type, dtable_decl));
+  
+  if (otable_methods == NULL_TREE)
+    {
+      PUSH_FIELD_VALUE (cons, "otable", null_pointer_node);
+      PUSH_FIELD_VALUE (cons, "otable_syms", null_pointer_node);
+    }
+  else
+    {
+      PUSH_FIELD_VALUE (cons, "otable",
+			build1 (ADDR_EXPR, otable_ptr_type, otable_decl));
+      PUSH_FIELD_VALUE (cons, "otable_syms",
+			build1 (ADDR_EXPR, method_symbols_array_ptr_type,
+				otable_syms_decl));
+    }
   PUSH_FIELD_VALUE (cons, "interfaces", interfaces);
   PUSH_FIELD_VALUE (cons, "loader", null_pointer_node);
   PUSH_FIELD_VALUE (cons, "interface_count", build_int_2 (interface_len, 0));
@@ -2148,6 +2181,87 @@
 	(* targetm.asm_out.constructor) (XEXP (DECL_RTL (init_decl), 0),
 					 DEFAULT_INIT_PRIORITY);
     }
+}
+
+/* Make a method_symbol_type (_Jv_MethodSymbol) node for METHOD. */
+
+tree
+build_method_symbols_entry (tree method)
+{
+  tree clname, name, signature, method_symbol;
+  
+  clname = build_utf8_ref (DECL_NAME (TYPE_NAME (DECL_CONTEXT (method))));
+  name = build_utf8_ref (DECL_NAME (method));
+  signature = build_java_signature (TREE_TYPE (method));
+  signature = build_utf8_ref (unmangle_classname 
+			      (IDENTIFIER_POINTER (signature),
+			       IDENTIFIER_LENGTH (signature)));
+
+  START_RECORD_CONSTRUCTOR (method_symbol, method_symbol_type);
+  PUSH_FIELD_VALUE (method_symbol, "clname", clname);
+  PUSH_FIELD_VALUE (method_symbol, "name", name);
+  PUSH_FIELD_VALUE (method_symbol, "signature", signature);
+  FINISH_RECORD_CONSTRUCTOR (method_symbol);
+  TREE_CONSTANT (method_symbol) = 1;
+
+  return method_symbol;
+} 
+
+/* Emit the offset symbols table for indirect virtual dispatch. */
+
+void
+emit_offset_symbol_table ()
+{
+  tree method_list, method, table, list, null_symbol;
+  tree otable_bound, otable_array_type;
+  int index;
+  
+  /* Only emit an offset table if this translation unit actually made virtual 
+     calls. */
+  if (otable_methods == NULL_TREE)
+    return;
+
+  /* Build a list of _Jv_MethodSymbols for each entry in otable_methods. */
+  index = 0;
+  method_list = otable_methods;
+  list = NULL_TREE;  
+  while (method_list != NULL_TREE)
+    {
+      method = TREE_VALUE (method_list);
+      list = tree_cons (NULL_TREE, build_method_symbols_entry (method), list);
+      method_list = TREE_CHAIN (method_list);
+      index++;
+    }
+
+  /* Terminate the list with a "null" entry. */
+  START_RECORD_CONSTRUCTOR (null_symbol, method_symbol_type);
+  PUSH_FIELD_VALUE (null_symbol, "clname", null_pointer_node);
+  PUSH_FIELD_VALUE (null_symbol, "name", null_pointer_node);
+  PUSH_FIELD_VALUE (null_symbol, "signature", null_pointer_node);
+  FINISH_RECORD_CONSTRUCTOR (null_symbol);
+  TREE_CONSTANT (null_symbol) = 1;  
+  list = tree_cons (NULL_TREE, null_symbol, list);
+
+  /* Put the list in the right order and make it a constructor. */
+  list = nreverse (list);
+  table = build (CONSTRUCTOR, method_symbols_array_type, NULL_TREE, list);  
+
+  /* Make it the initial value for otable_syms and emit the decl. */
+  DECL_INITIAL (otable_syms_decl) = table;
+  DECL_ARTIFICIAL (otable_syms_decl) = 1;
+  DECL_IGNORED_P (otable_syms_decl) = 1;
+  rest_of_decl_compilation (otable_syms_decl, NULL, 1, 0);
+  
+  /* Now that its size is known, redefine otable as an uninitialized static 
+     array of INDEX + 1 integers. The extra entry is used by the runtime 
+     to track whether the otable has been initialized. */
+  otable_bound = build_index_type (build_int_2 (index, 0));
+  otable_array_type = build_array_type (integer_type_node, otable_bound);
+  otable_decl = build_decl (VAR_DECL, get_identifier ("otable"), 
+			    otable_array_type);
+  TREE_STATIC (otable_decl) = 1;
+  TREE_READONLY (otable_decl) = 1;  
+  rest_of_decl_compilation (otable_decl, NULL, 1, 0);
 }
 
 void
Index: gcc/java/expr.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/expr.c,v
retrieving revision 1.123
diff -u -r1.123 expr.c
--- expr.c	2001/12/06 23:12:55	1.123
+++ expr.c	2001/12/10 09:38:42
@@ -84,6 +84,7 @@
 static unsigned char peek_opcode_at_pc PARAMS ((struct JCF *, int, int));
 static bool emit_init_test_initialization PARAMS ((struct hash_entry *,
 						   PTR ptr));
+static int get_offset_table_index PARAMS ((tree));
 
 static tree operand_type[59];
 extern struct obstack permanent_obstack;
@@ -1840,6 +1841,40 @@
   return dtable;
 }
 
+/* Determine the index in the virtual offset table (otable) for a call to
+   METHOD. If this method has not been seen before, it will be added to the 
+   otable_methods. If it has, the existing otable slot will be reused. */
+
+int
+get_offset_table_index (method)
+     tree method;
+{
+  int i = 1;
+  tree method_list;
+  
+  if (otable_methods == NULL_TREE)
+    {
+      otable_methods = build_tree_list (method, method);
+      return 1;
+    }
+  
+  method_list = otable_methods;
+  
+  while (1)
+    {
+      if (TREE_VALUE (method_list) == method)
+        return i;
+      i++;
+      if (TREE_CHAIN (method_list) == NULL_TREE)
+        break;
+      else
+        method_list = TREE_CHAIN (method_list);
+    }
+
+  TREE_CHAIN (method_list) = build_tree_list (method, method);
+  return i;
+}
+
 tree 
 build_invokevirtual (dtable, method)
      tree dtable, method;
@@ -1847,17 +1882,29 @@
   tree func;
   tree nativecode_ptr_ptr_type_node
     = build_pointer_type (nativecode_ptr_type_node);
-  tree method_index = convert (sizetype, DECL_VINDEX (method));
+  tree method_index;
+  tree otable_index;
 
-  /* Add one to skip "class" field of dtable, and one to skip unused
-     vtable entry (for C++ compatibility). */
-  method_index = size_binop (PLUS_EXPR, method_index, size_int (2));
-  method_index = size_binop (MULT_EXPR, method_index,
-			     TYPE_SIZE_UNIT (nativecode_ptr_ptr_type_node));
+  if (flag_indirect_dispatch)
+    {
+      otable_index = build_int_2 (get_offset_table_index (method), 0);
+      method_index = build (ARRAY_REF, integer_type_node, otable_decl, 
+			    otable_index);
+    }
+  else
+    {
+      method_index = convert (sizetype, DECL_VINDEX (method));
 
-  if (TARGET_VTABLE_USES_DESCRIPTORS)
-    method_index = size_binop (MULT_EXPR, method_index,
-			       size_int (TARGET_VTABLE_USES_DESCRIPTORS));
+      /* Add one to skip "class" field of dtable, and one to skip unused
+	 vtable entry (for C++ compatibility). */
+      method_index = size_binop (PLUS_EXPR, method_index, size_int (2));
+      method_index = size_binop (MULT_EXPR, method_index,
+				 TYPE_SIZE_UNIT (nativecode_ptr_ptr_type_node));
+
+      if (TARGET_VTABLE_USES_DESCRIPTORS)
+	method_index = size_binop (MULT_EXPR, method_index,
+				   size_int (TARGET_VTABLE_USES_DESCRIPTORS));
+    }
 
   func = fold (build (PLUS_EXPR, nativecode_ptr_ptr_type_node, dtable,
 		      convert (nativecode_ptr_ptr_type_node, method_index)));
@@ -1879,6 +1926,7 @@
   tree interface;
   tree idx;
   tree meth;
+  tree otable_index;
   int i;
 
   /* We expand invokeinterface here.  _Jv_LookupInterfaceMethod() will
@@ -1898,16 +1946,24 @@
   interface = DECL_CONTEXT (method);
   layout_class_methods (interface);
   
-  i = 1;
-  for (meth = TYPE_METHODS (interface); ; meth = TREE_CHAIN (meth), i++)
+  if (flag_indirect_dispatch)
     {
-      if (meth == method)
-        {
-	  idx = build_int_2 (i, 0);
-	  break;
+      otable_index = build_int_2 (get_offset_table_index (method), 0);
+      idx = build (ARRAY_REF, integer_type_node, otable_decl, otable_index);
+    }
+  else
+    {
+      i = 1;
+      for (meth = TYPE_METHODS (interface); ; meth = TREE_CHAIN (meth), i++)
+	{
+	  if (meth == method)
+            {
+	      idx = build_int_2 (i, 0);
+	      break;
+	    }
+	  if (meth == NULL_TREE)
+	    abort ();
 	}
-      if (meth == NULL_TREE)
-	abort ();
     }
 
   lookup_arg = tree_cons (NULL_TREE, dtable,
Index: gcc/java/java-tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/java-tree.h,v
retrieving revision 1.127
diff -u -r1.127 java-tree.h
--- java-tree.h	2001/12/06 23:12:55	1.127
+++ java-tree.h	2001/12/10 09:38:44
@@ -140,6 +140,18 @@
 /* List of all class filenames seen so far.  */
 #define all_class_filename java_global_trees [JTI_ALL_CLASS_FILENAME]
 
+/* List of virtual method decls called in this translation unit, used to 
+   generate virtual method offset symbol table. */
+#define otable_methods java_global_trees [JTI_OTABLE_METHODS]
+
+/* The virtual method offset table. This is emitted as uninitialized data of 
+   the required length, and filled out at run time during class linking. */
+#define otable_decl java_global_trees [JTI_OTABLE_DECL]
+
+/* The virtual method offset symbol table. Used by the runtime to fill out the
+   otable. */
+#define otable_syms_decl java_global_trees [JTI_OTABLE_SYMS_DECL]
+
 extern int flag_emit_class_files;
 
 extern int flag_filelist_file;
@@ -195,6 +207,10 @@
    initialization optimization should be performed.  */
 extern int flag_optimize_sci;
 
+/* When non zero, use offset tables for virtual method calls
+   in order to improve binary compatibility. */
+extern int flag_indirect_dispatch;
+
 /* Encoding used for source files.  */
 extern const char *current_encoding;
 
@@ -329,6 +345,11 @@
   JTI_LINENUMBERS_TYPE,
   JTI_METHOD_TYPE_NODE,
   JTI_METHOD_PTR_TYPE_NODE,
+  JTI_OTABLE_TYPE,
+  JTI_OTABLE_PTR_TYPE,
+  JTI_METHOD_SYMBOL_TYPE,
+  JTI_METHOD_SYMBOLS_ARRAY_TYPE,
+  JTI_METHOD_SYMBOLS_ARRAY_PTR_TYPE,
 
   JTI_END_PARAMS_NODE,
 
@@ -367,6 +388,10 @@
   JTI_ALL_CLASS_LIST,
   JTI_ALL_CLASS_FILENAME,
 
+  JTI_OTABLE_METHODS,
+  JTI_OTABLE_DECL,
+  JTI_OTABLE_SYMS_DECL,
+
   JTI_MAX
 };
 
@@ -560,6 +585,16 @@
   java_global_trees[JTI_METHOD_TYPE_NODE]
 #define method_ptr_type_node \
   java_global_trees[JTI_METHOD_PTR_TYPE_NODE]
+#define otable_type \
+  java_global_trees[JTI_OTABLE_TYPE]
+#define otable_ptr_type \
+  java_global_trees[JTI_OTABLE_PTR_TYPE]
+#define method_symbol_type \
+  java_global_trees[JTI_METHOD_SYMBOL_TYPE]
+#define method_symbols_array_type \
+  java_global_trees[JTI_METHOD_SYMBOLS_ARRAY_TYPE]
+#define method_symbols_array_ptr_type \
+  java_global_trees[JTI_METHOD_SYMBOLS_ARRAY_PTR_TYPE]
 
 #define end_params_node \
   java_global_trees[JTI_END_PARAMS_NODE]
@@ -1091,6 +1126,7 @@
 extern void register_class PARAMS ((void));
 extern int alloc_name_constant PARAMS ((int, tree));
 extern void emit_register_classes PARAMS ((void));
+extern void emit_offset_symbol_table PARAMS ((void));
 extern void lang_init_source PARAMS ((int));
 extern void write_classfile PARAMS ((tree));
 extern char *print_int_node PARAMS ((tree));
Index: gcc/java/jcf-parse.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/jcf-parse.c,v
retrieving revision 1.97
diff -u -r1.97 jcf-parse.c
--- jcf-parse.c	2001/12/03 19:13:40	1.97
+++ jcf-parse.c	2001/12/10 09:38:45
@@ -1188,7 +1188,11 @@
 
   java_expand_classes ();
   if (!java_report_errors () && !flag_syntax_only)
-    emit_register_classes ();
+    {
+      emit_register_classes ();
+      if (flag_indirect_dispatch)
+	emit_offset_symbol_table ();
+    }
   return 0;
 }
 
Index: gcc/java/jvspec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/jvspec.c,v
retrieving revision 1.49
diff -u -r1.49 jvspec.c
--- jvspec.c	2001/12/03 19:13:40	1.49
+++ jvspec.c	2001/12/10 09:38:45
@@ -64,6 +64,7 @@
                    %{<fcompile-resource*}\
 		   %{<femit-class-file} %{<femit-class-files} %{<fencoding*}\
 		   %{<fuse-boehm-gc} %{<fhash-synchronization} %{<fjni}\
+		   %{<findirect-dispatch} \
 		   %{<fclasspath*} %{<fCLASSPATH*} %{<foutput-class-dir}\
 		   %{<fuse-divide-subroutine} %{<fno-use-divide-subroutine}\
 		   %{<fcheck-references} %{<fno-check-references}\
Index: gcc/java/lang.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/lang.c,v
retrieving revision 1.81
diff -u -r1.81 lang.c
--- lang.c	2001/12/07 19:01:19	1.81
+++ lang.c	2001/12/10 09:38:45
@@ -153,6 +153,10 @@
    be tested alone, use STATIC_CLASS_INITIALIZATION_OPTIMIZATION_P instead.  */
 int flag_optimize_sci = 1;
 
+/* When non zero, use offset tables for virtual method calls
+   in order to improve binary compatibility. */
+int flag_indirect_dispatch = 0;
+
 /* When non zero, print extra version information.  */
 static int version_flag = 0;
 
@@ -174,7 +178,8 @@
   {"jni", &flag_jni, 1},
   {"check-references", &flag_check_references, 1},
   {"force-classes-archive-check", &flag_force_classes_archive_check, 1},
-  {"optimize-static-class-initialization", &flag_optimize_sci, 1 }
+  {"optimize-static-class-initialization", &flag_optimize_sci, 1 },
+  {"indirect-dispatch", &flag_indirect_dispatch, 1}
 };
 
 static struct string_option
Index: libjava/include/jvm.h
===================================================================
RCS file: /cvs/gcc/egcs/libjava/include/jvm.h,v
retrieving revision 1.46
diff -u -r1.46 jvm.h
--- jvm.h	2001/11/26 06:40:05	1.46
+++ jvm.h	2001/12/10 09:38:46
@@ -55,6 +55,12 @@
 
   void *get_finalizer() { return get_method(0); }
   static size_t vtable_elt_size() { return sizeof(vtable_elt); }
+
+  // Given a method index, return byte offset from the vtable pointer.
+  static jint idx_to_offset (int index)
+  {
+    return (index + 2) * vtable_elt_size ();
+  }
   static _Jv_VTable *new_vtable (int count);
 };
 
Index: libjava/java/lang/natClassLoader.cc
===================================================================
RCS file: /cvs/gcc/egcs/libjava/java/lang/natClassLoader.cc,v
retrieving revision 1.43
diff -u -r1.43 natClassLoader.cc
--- natClassLoader.cc	2001/11/26 06:40:06	1.43
+++ natClassLoader.cc	2001/12/10 09:38:46
@@ -235,7 +235,6 @@
   return _Jv_FindClassInCache (_Jv_makeUtf8Const (name), this);
 }
 
-
 /** This function does class-preparation for compiled classes.  
     NOTE: It contains replicated functionality from
     _Jv_ResolvePoolEntry, and this is intentional, since that function
@@ -309,6 +308,12 @@
 #ifdef INTERPRETER
     }
 #endif /* INTERPRETER */
+
+  if (klass->vtable == NULL)
+    _Jv_MakeVTable(klass);
+
+  if (klass->otable != NULL && klass->otable->state == 0)
+    _Jv_LinkOffsetTable(klass);
 
   klass->notifyAll ();
 }
Index: libjava/java/lang/Class.h
===================================================================
RCS file: /cvs/gcc/egcs/libjava/java/lang/Class.h,v
retrieving revision 1.40
diff -u -r1.40 Class.h
--- Class.h	2001/11/05 23:39:54	1.40
+++ Class.h	2001/12/10 09:38:46
@@ -70,6 +70,8 @@
   _Jv_Utf8Const *signature;
   // Access flags.
   _Jv_ushort accflags;
+  // Method's index in the vtable.
+  _Jv_ushort index;
   // Pointer to underlying function.
   void *ncode;
   // NULL-terminated list of exception class names; can be NULL if
@@ -114,6 +116,19 @@
   jclass self;
 };
 
+struct _Jv_MethodSymbol
+{
+  _Jv_Utf8Const *class_name;
+  _Jv_Utf8Const *name;
+  _Jv_Utf8Const *signature;
+};
+
+struct _Jv_OffsetTable
+{
+  jint state;
+  jint offsets[];
+};
+
 #define JV_PRIMITIVE_VTABLE ((_Jv_VTable *) -1)
 
 #define JV_CLASS(Obj) ((jclass) (*(_Jv_VTable **) Obj)->clas)
@@ -303,6 +318,10 @@
   friend jstring _Jv_GetMethodString(jclass, _Jv_Utf8Const *);
   friend jshort _Jv_AppendPartialITable (jclass, jclass, void **, jshort);
   friend jshort _Jv_FindIIndex (jclass *, jshort *, jshort);
+  friend void _Jv_LinkOffsetTable (jclass);
+  friend void _Jv_LayoutVTableMethods (jclass klass);
+  friend void _Jv_SetVTableEntries (jclass, _Jv_VTable *);
+  friend void _Jv_MakeVTable (jclass);
 
   // Return array class corresponding to element type KLASS, creating it if
   // necessary.
@@ -367,6 +386,10 @@
   jshort static_field_count;
   // The vtbl for all objects of this class.
   _Jv_VTable *vtable;
+  // Virtual method offset table.
+  _Jv_OffsetTable *otable;
+  // Offset table symbols.
+  _Jv_MethodSymbol *otable_syms;
   // Interfaces implemented by this class.
   jclass *interfaces;
   // The class loader for this class.
Index: libjava/java/lang/natClass.cc
===================================================================
RCS file: /cvs/gcc/egcs/libjava/java/lang/natClass.cc,v
retrieving revision 1.48
diff -u -r1.48 natClass.cc
--- natClass.cc	2001/12/09 00:17:07	1.48
+++ natClass.cc	2001/12/10 09:38:48
@@ -692,7 +692,7 @@
 	  _Jv_PrepareCompiledClass (this);
 	}
     }
-  
+
   if (state <= JV_STATE_LINKED)
     _Jv_PrepareConstantTimeTables (this);
 
@@ -1421,4 +1421,195 @@
 java::lang::Class::getProtectionDomain0 ()
 {
   return protectionDomain;
+}
+
+// Functions for indirect dispatch (symbolic virtual method binding) support.
+
+// Resolve entries in the virtual method offset symbol table 
+// (klass->otable_syms). The vtable offset (in bytes) for each resolved method 
+// is placed at the corresponding position in the virtual method offset table 
+// (klass->otable). A single otable and otable_syms pair may be shared by many 
+// classes.
+void
+_Jv_LinkOffsetTable(jclass klass)
+{
+  //// FIXME: Need to lock the otable ////
+  
+  if (klass->otable == NULL
+      || klass->otable->state != 0)
+    return;
+  
+  klass->otable->state = 1;
+
+  int index = 0;
+  _Jv_MethodSymbol sym = klass->otable_syms[0];
+
+  while (sym.name != NULL)
+    {
+      jclass target_class = _Jv_FindClass (sym.class_name, NULL);
+      _Jv_Method *meth = NULL;            
+      
+      if (target_class != NULL)
+	if (target_class->isInterface())
+	  {
+	    // FIXME: This does not yet fully conform to binary compatibility
+	    // rules. It will break if a declaration is moved into a 
+	    // superinterface.
+	    for (int i=0; i < target_class->method_count; i++)
+	      {
+		meth = &target_class->methods[i];
+		if (_Jv_equalUtf8Consts (sym.name, meth->name)
+		    && _Jv_equalUtf8Consts (sym.signature, meth->signature))
+		  {
+		    klass->otable->offsets[index] = i + 1;
+		    break;
+		  }
+	      }
+	  }
+	else
+	  {
+	    // If the target class does not have a vtable_method_count yet, 
+	    // then we can't tell the offsets for its methods, so we must lay 
+	    // it out now.
+	    if (target_class->vtable_method_count == -1)
+	      {
+		JvSynchronize sync (target_class);
+		_Jv_LayoutVTableMethods (target_class);
+	      }
+
+            meth = _Jv_LookupDeclaredMethod(target_class, sym.name, 
+					    sym.signature);
+
+	    if (meth != NULL)
+	      {
+		klass->otable->offsets[index] = 
+		  _Jv_VTable::idx_to_offset (meth->index);
+	      }
+	  }
+
+      if (meth == NULL)
+	// FIXME: This should be special index for ThrowNoSuchMethod().
+	klass->otable->offsets[index] = -1;
+
+      sym = klass->otable_syms[++index];
+    }
+}
+
+// Returns true if METH should get an entry in a VTable.
+static bool
+isVirtualMethod (_Jv_Method *meth)
+{
+  using namespace java::lang::reflect;
+  return (((meth->accflags & (Modifier::STATIC | Modifier::PRIVATE)) == 0)
+          && meth->name->data[0] != '<');
+}
+
+// Prepare virtual method declarations in KLASS, and any superclasses as 
+// required, by determining their vtable index, setting method->index, and
+// finally setting the class's vtable_method_count. Must be called with the
+// lock for KLASS held.
+void
+_Jv_LayoutVTableMethods (jclass klass)
+{
+  if (klass->vtable != NULL || klass->isInterface() 
+      || klass->vtable_method_count != -1)
+    return;
+    
+  jclass superclass = klass->superclass;
+
+  if (superclass != NULL && superclass->vtable_method_count == -1)
+    {
+      JvSynchronize sync (superclass);
+      _Jv_LayoutVTableMethods (superclass);
+    }
+    
+  int index = (superclass == NULL ? 0 : superclass->vtable_method_count);
+
+  for (int i = 0; i < klass->method_count; ++i)
+    {
+      _Jv_Method *meth = &klass->methods[i];
+      _Jv_Method *super_meth = NULL;
+    
+      if (!isVirtualMethod(meth))
+        continue;
+	      
+      if (superclass != NULL)
+        super_meth = _Jv_LookupDeclaredMethod (superclass, meth->name, 
+					       meth->signature);
+      
+      if (super_meth)
+        meth->index = super_meth->index;
+      else
+        meth->index = index++;
+    }
+  
+  klass->vtable_method_count = index;
+}
+
+// Set entries in VTABLE for virtual methods declared in KLASS. If KLASS has
+// an immediate abstract parent, recursivly do its methods first.
+void
+_Jv_SetVTableEntries (jclass klass, _Jv_VTable *vtable)
+{
+  using namespace java::lang::reflect;
+
+  jclass superclass = klass->getSuperclass();
+
+  if (superclass != NULL && (superclass->getModifiers() & Modifier::ABSTRACT))
+    _Jv_SetVTableEntries (superclass, vtable);
+    
+  for (int i = klass->method_count - 1; i >= 0; i--)
+    {
+      _Jv_Method *meth = &klass->methods[i];
+      if (!isVirtualMethod(meth))
+	continue;
+      vtable->set_method(meth->index, meth->ncode);
+    }
+}
+
+// Allocate and lay out the virtual method table for KLASS. This will also
+// cause vtables to be generated for any non-abstract superclasses, and
+// virtual method layout to occur for any abstract superclasses. Must be
+// called with monitor lock for KLASS held.
+void
+_Jv_MakeVTable (jclass klass)
+{
+  using namespace java::lang::reflect;  
+
+  if (klass->vtable != NULL || klass->isInterface() 
+      || (klass->accflags & Modifier::ABSTRACT))
+    return;
+  
+  //  out before we can create a vtable. 
+  if (klass->vtable_method_count == -1)
+    _Jv_LayoutVTableMethods (klass);
+
+  // Allocate the new vtable.
+  _Jv_VTable *vtable = _Jv_VTable::new_vtable (klass->vtable_method_count);
+  klass->vtable = vtable;
+  
+  // Copy the vtable of the closest non-abstract superclass.
+  jclass superclass = klass->superclass;
+  if (superclass != NULL)
+    {
+      while ((superclass->accflags & Modifier::ABSTRACT) != 0)
+	superclass = superclass->superclass;
+
+      if (superclass->vtable == NULL)
+	{
+	  JvSynchronize sync (superclass);
+	  _Jv_MakeVTable (superclass);
+	}
+
+      for (int i = 0; i < superclass->vtable_method_count; ++i)
+	vtable->set_method (i, superclass->vtable->get_method (i));
+    }
+
+  // Set the class pointer and GC descriptor.
+  vtable->clas = klass;
+  vtable->gc_descr = _Jv_BuildGCDescr (klass);
+
+  // For each virtual declared in klass and any immediate abstract 
+  // superclasses, set new vtable entry or override an old one.
+  _Jv_SetVTableEntries (klass, vtable);
 }

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]