[libmudflap] switching to splay trees

["Frank Ch. Eigler" <fche at redhat dot com>]

Hi -


As kindly suggested by Doug Graham a few weeks ago, libmudflap's
data structure for tracking live objects has been, er, rather
elementary.  This punished instrumented programs with frequent
allocation / deallocation, or with frequent misses in the
object lookup cache.  I just checked in code that improves this
to some extent, by adopting libiberty's splay-tree code to store
the object database.  

This first stab appears to make a nice (2x relative speedup)
improvement to pointer-intensive programs such as Doug's, and
more is within reach.  For example, I'm considering a splay-tree
patch that would let that code avoid the comparison function-pointer
indirection for the common (integer/pointer) keying case.

The patches are too involved to post here, since they involved
a rewrite of big chunks of the main libmudflap/mf-runtime.c file,
plus minor mechanical changes elsewhere.

By the way, someone naughtily broke mudflap support for C++ in the last
few days (mudflap_finish gets a NULL dereference during its building its
synthetic constructor function).


- FChE