Efficient gmon call-arc counting

[Greg McGary]

I need to implement efficient profiling for an embedded MIPS target,
and had the following inspiration.  I'm pleased with the design and
don't think there are any problems with it, but thought I'd throw it
out for comment in case anyone has better ideas.  I expect that when
it's finished it will make a nice addition to GCC.

Traditional gmon implementations generate a call to _mcount in the
prologue of every function.  _mcount rummages back through the stack
to find its caller and its caller's caller, then hashes those two
addresses to locate a bucket which has a counter for that arc.  Let's
denote the caller as B(), and its caller as A().  If A calls B from
multiple places, _mcount will see different values for the caller's
caller address and will therefore use different buckets for
accumulating call-arc counts.  Later, gprof will coalesce these into a
single A->B call-arc count.

While this might be OK for a workstation environment, it sucks for
embedded systems with tight memory and/or CPU resources.  The CPU and
memory overhead of the hash table is high enough to be a concern.

Fortunately, there's a very efficient and easy-to-implement
alternative.  In the foregoing, I'll assume a RISC CPU with a
temporary/scratch register available (call-clobbered non-fixed and not
used for passing args), and an object format, such as ELF, that
accommodates named sections:

While compiling A, when we see a call to B, we construct a variable
name from A & B, say "__callarc_A_B" and emit assembler to define it
in the ".callarc" section.  We just eliminated the need for a call-arc
hash table!  We can either emit code to increment the count in (a) A
before calling B, or (b) A can load the address of __callarc_A_B into
a temporary/scratch register and pass it to B, where B's prologue will
do increment.  (a) is simpler and saves one insn at runtime, while (b)
saves a bit of space.  Either choice seems acceptable.

The only wrinkle is for calls through function pointers.  If A calls
(*f)(), we don't know at compile time what value `f' will have.  In
that case, we need to arrange for a runtime lookup.  I make the
assumption that the number of values `f' can have will be small, and
create a linked list of call-arc counts for each value of `f'
encountered at runtime.  We emit assembler to define a variable in
the section ".callarclist" which is a three-word struct like so:

struct call_arc_cons
{
  struct call_arc_cons *next;
  void *func_addr;
  unsigned int count;
};

One list could serve for all of A's indirect calls, or if we want to
get fancy, we could have a list for every distinct function type among
A's indirect calls, making the assumption that distinct lists will
represent disjoint sets, and therefore the lists will be shorter.

Rather than open-code the list search, we'd emit code to call a small
library function that searches the list and increments the counter,
inserting a new element if the function isn't found.

Comments?

Greg