Counting calls for call graph data

[Will C. <wc...@re...>]

A very desirable thing would be to have sampling that provides call
graphs that are comparable to the data that gprof collects: flat
time-based samples and arcs for function calls. The released versions
of OProfile already provide flat time-based profiles. The work by Phil
Elie provides stack trace back informatin, but the key is to get the
stack trace back sampled based on function calls.  The Pentium II/III
processors do not have performance monitor that count function
calls. However, the Pentium 4 processors provides a
RETIRED_BRANCH_TYPE. Some experiments show that this event measures
calls and could be used to trigger the stack trace back.

The RETIRED_BRANCH_TYPE on the Pentium 4 has a unit mask to specify
which kinds of branches are counted.  According to The newest versions
of the ia32 manual vol 3 list:

Bit
0: UNCONDITIONAL
1: CONDITIONAL
2: CALL
3: RETURN
4: INDIRECT


I did some testing and verified the performance monitoring hardware
counted only indirect and direct calls with mask bit 2 on. The count
did not include the unconditional or conditional jumps in the loop
constructs, or indirect branches from switch case statements.  The 
profiling was started with the following command using a 2.6 kernel:

sudo /usr/local/bin/opcontrol --setup 
--event=RETIRED_BRANCH_TYPE:100000:4:1:1 --vmlinux=/boot/vmlinux-`uname 
-r` --separate=library


The Pentium M documentation lists a similar event to count calls,
BR_CALL_EXEC, so it should be possible to do the sample on the Pentium
M. However, I haven't had a chance to test it out.

-Will