Re: dynamic library cost (was RE: libtool, java woes)

[Jonathan P. Olson <olson at mmsi dot com>]

Right, adding write barriers was incredibly easy.   The  following code
in `expr.c' store_expr() invokes the write barrier:

#if defined (HAVE_write_barrier)
       /*
        * Generate write barrier code if we're setting memory with
        * something that's not a constant, not a vtable, and with
        * something that is a pointer.
        */
       else if (flag_write_barriers
                && GET_CODE (target) == MEM
                && GET_MODE (target) == Pmode
#ifdef TARGET_NEEDS_WRITE_BARRIER
                && TARGET_NEEDS_WRITE_BARRIER (target)
#endif
                && !(TREE_CODE(exp) == ADDR_EXPR
                     && DECL_VIRTUAL_P (TREE_OPERAND (exp, 0)))
                && !really_constant_p (exp)
                && contains_pointers_p (TREE_TYPE (exp))) {
           temp = force_reg (Pmode, temp);
           emit_insn (gen_write_barrier (target, temp));
       }
#endif

And here's the example RTL write-barrier pattern that I added for
StrongARM:

;; Garbage collector write barrier
(define_insn "write_barrier"
   [(parallel [
         (set (match_operand:SI 0 "memory_operand"   "=m")
              (match_operand:SI 1 "register_operand" "r"))
         (unspec_volatile [(match_dup 1)] 16)
         (clobber (reg:SI 12))
         (clobber (reg:SI 14))])]
   ""
   "str%?\\t%1,%0\;bl%?\\t___write_barrier_%1"
[(set_attr "conds" "clob")
  (set_attr "length" "8")])

On StrongARM, I have a separate statically linked function for each
hardware register.  For example, bl __write_barrier_r0 tells the
garbage collector the object contained in register `r0' is live.

Note that this GC is my own conservative GC especially designed
for real-time embedded work.  The StrongARM write barrier code for 
register r0
looks like this:

         .global __write_barrier_r0
__write_barrier_r0:
         ldr     ip,SysBlocktbl
         cmp     r0,ip
         movls   pc,lr
         mov     ip,REG
         swi     #V_write_barrier
         mov     pc,lr

SysBlocktbl is a global memory location which, during GC, points to the
base of the collected heap.  When GC isn't running, SysBlocktbl contains 
ffffffff.
Thus, the write_barrier code itself requires three instructions when GC 
is not
running.  When GC is running, each write to a pointer requires a SWI.  
Obviously
it would be possible to inline these 5 instructions, but on memory 
constrained
embedded devices, I chose to save the memory.  On a system where you 
didn't
mind the extra code size, you could inline this entire sequence to:

	str	%1,%0
	ldr	ip,SysBlocktbl
	cmp	%1,ip
	movhi pc,lr
	movhi ip,%1
	swihi #V_write_barrier

This would execute an extra instruction, but avoid a couple of pipeline 
stalls
so overall would save a few cycles.  I doubt if it would be very 
noticable in most
applications, however, since the write barrier code only gets generated 
when
you write to a pointer.

On embedded devices I use a SWI since the write barrier code which grays 
a particular
object needs to be non -preemptible.  On Linux or other multiuser 
systems you may want
to replace this SWI with a call which locks an appropriate pthread 
mutex.  However
on a single user, multi-threaded embedded device the SWI is alot more 
efficient.

FYI, another processor which we use (now obsolete) is the AMD a29k.  One 
thing
it's really good for is write barriers because it has an ASSERT 
instruction.  The
RTL write barrier pattern for this processor is just a single 
instruction:

;; Garbage collector write barrier
(define_insn "write_barrier"
   [(parallel [
         (set (match_operand:SI 0 "memory_operand"   "=m")
              (match_operand:SI 1 "register_operand" "r"))
         (unspec_volatile [(match_dup 1)] 16)])]
   ""
   "store 0,0,%1,%0\;asleu V_write_barrier,%1,gr95")

The `asleu' instruction traps to the write barrier code whenever the
value of the pointer being written is higher than the heap base.  Because
the A29K has a zillion global registers, I can easily afford to use one 
to
hold the GC's SysBlocktbl pointer.

When GC is not running, `asleu' is a NOP.  Other processors which have
assert instructions could use similar code to implement ultra cheap
write barriers.

BTW, one thing about GC on pthreads implementations which I've found 
truly
evil is the whole business of suspending threads.  SInce pthreads 
doesn't provide
any way to suspend a thread, Boehm GC and I assume everybody else that
does multi-threaded GC sends Unix signals to all the threads.  Worse 
yet, pthreads
doesn't provide any way to find all the threads, so GCs must perform 
their own
bookkeeping to try to keep track of all the running threads.  If a 
thread dies with
GC not knowing about it, GC hangs forever waiting for the thread to 
catch the
signal ;^(

My guess is that putting write barriers in the compiler will be alot 
cheaper than
all the Unix signalling nonsense to suspend threads which is necessary 
when
write barriers aren't part of the compiler.

On Thursday, April 12, 2001, at 10:27  PM, Tom Tromey wrote:

>>>>>> "Hans" == Boehm, Hans <hans_boehm@hp.com> writes:
>
> Hans> (As far as I know, the only way to currently get a write barrier
> Hans> is with virtual memory techniques.  That means generational or
> Hans> incremental collection requires virtual memory, and you only get
> Hans> update information at coarse granularity.  And you're presumably
> Hans> limited to a conservative stack scan.)
>
> That is definitely the current state of affairs.
>
> Adding write barrier support doesn't appear to be hugely difficult.
> Jon Olson implemented it (I haven't seen the code).  Is it worth doing
> this with your collector?
>
> Adding non-conservative stack scanning is much harder.  It has been
> added to gcc before (in gcc 1.something -- ancient history).  It is
> definitely possible, but it touches a lot of the compiler.  There's a
> paper on this by Rick Hudson.  When I say "much harder", my guess (and
> this is really a wild guess) is that it is on the order of a man year.
>
> Tom