Completed Plan for --gc-sections on gcj [IGNORE my previous posts]

[Adam Megacz <gcj at lists dot megacz dot com>]

Okay, I think I have a completely working theory... Bryce (and
others), could you please sanity-check this?  I think this is
something I can implement completely on my own, and distribute as a
patch against gcj (you definately wouldn't want this to be the
default).  Please let me know if you can see any problems with this
approach...

Here's what I propose to do:

1. Break up otable_syms[] into a seperate symbol-and-section for each
   entry.  Each otable_sym will be a pointer to the corresponding
   _Jv_Method rather than a trio of utf8consts.  All the otable_sym's
   for a given class all have the same section name, so they get
   merged during linking.  _Jv_InitClass() writes the appropriate
   offsets *over* the _Jv_Method*'s in the otable.

2. Every _Jv_Method gets its own symbol and section.  All the section
   names for the methods of a given class are the same, so the section
   is merged during linkage.  Class->methods is a pointer to the symbol
   MD_<classname>_BEGIN (see diagram below).

3. Every _Jv_Method gets one additional entry, "overrides", which is a
   pointer into an empty section,
   ".overrides_<classname>_<methodname>".  Every class which overrides
   the method includes a section with the same name which includes a
   single relocation pointing at the *overriding* _Jv_Method.

4. We modify the linker in one small way: all section names beginning
   with ".overrides" are merged BEFORE section_gc.  All other sections
   are merged after section_gc, as usual.

Here's a diagram that shows the relocations for the following code:

    [note: contrary to the legend, the arrow next to "CALL
           Super.foo()" isn't a reloc, it's an array lookup]

    http://www.megacz.com/gcsections.png

    class Main {
        public static void main(String[] s) {
            new Sub().foo();
        }
    }

    class Super {
        public void foo() { /* ... */ }
    }

    class Sub extends Super {
        public void foo() { /* ... */ }
    }

Overhead, post-link:

  Size:

    - Two pointer-sizes per class for .otable_<classname>_{BEGIN,END}
    - Two pointer-sizes per class for .jmd_<classname>_{BEGIN,END}
    - At most three pointer-sizes per method for .overrides_<classname>_{BEGIN,END}

  Performance:

    - Substantially more time to dynamically link against libgcj.so at
      runtime, but you would probably only want to use this feature if
      you're statically linking.

Drawbacks:

  If you invoke a given method, every method that overrides it is
  included in the link, as well as everything that those methods refer
  to.

  This could possibly be fixed in (4) by making more changes to the
  linker -- only pre-merge .overrides sections if at least one
  constructor of the class is reachable.  This would be pretty
  challenging, however.