My problem today was to determine and visualize the set of functions (callers) that call another set of functions (callees). For this purpose, I knew the callees function names all started with the same word, say "Callee", and that none of the caller's names start with Callee. For C programs,
namespaces are often formed by a coding convention that specifies the format of function names and groups related functions by a common "first name".
I found a simple tool,
egypt, that relies on gcc and GraphViz to generate a visualization of a program's static call graph. A call graph is a natural way to visualize what I need, but my requirements are slightly different than the usual. Normally a call graph will include all of the directed edges from callers to callees in an entire program or subset of its functions. What I need is just the nodes of immediate callers of the Callee functions, that is, the subgraph
induced by the caller and callee vertices in the call graph.
For my needs, the tool lacks the ability to specify a set of vertices and generate the subgraph they induce. The induced subgraph could be found if I could:
- specify terminal nodes (callees)
- filter nodes that do not have an edge to terminal nodes
Rather than implement this ability, I realized I could wrap egypt with a bit of shell code to produce the graph(s) I want.
egypt processes
RTL dumps produced by gcc. It outputs a call graph for the RTL dump files passed in. The first thing to do then is to compile the project to visualize using gcc with the
-fdump-rtl-expand flag. This produces the *.expand files required by egypt. My first attempt was using gcc 4.4.7, which dumps all of the .expand files in the root directory of the build. For projects with multiple source files having the same name, the .expand files overwrite each other. I switched to gcc 4.7.1 because it dumps the .expand files in the same directory as the .o files are generated. Then, I revisited some
old tricks to gather the .expand files into a separate directory for analysis while keeping the project's directory structure.
Now, if I just wanted the callgraph of the Callees, I could easily grep for the .expand files containing functions that start with Callee and pass them to egypt. However, to get the subgraph of caller->Callee is trickier. What I did was to use egypt on each of the .expand files individually and filter the output for edges to a Callee. This gives exactly the set of nodes and edges I need. Then I just need to wrap the output similarly to how egypt does to produce a graph file for GraphViz. The resulting script looks something like,
#!/bin/bash
echo "digraph callgraph {"
files=`find . -name "*.expand"`
for f in $files
do
egypt --include-external $f | grep Callee_ \
| grep -v Callee_.*-\> | grep -v Callee_.*\"\;
done
echo "}"
The --include-external is necessary to force egypt to produce caller nodes for which it does not find a definition. The second line of greps are to exclude any calls originating from Callee, and to discard any uncalled Callee. Redirect the output of the script to a file, say callgraph.dot, and then it can be processed with one of the layout engines in the dot tools, like
$> dot -Teps -o callgraph-neato.eps callgraph.dot
As an example, I processed the RTEMS
Supercore Scheduler package. For this package, the Callee is _Scheduler. I processed the output with the circo drawing filter.
 |
| Supercore Scheduler Callers, with Scheduling Functions filled in Grey |
Some further improvements could be made. It might also be interesting to visualize the paths (open walks) that end at the Callees. Also, the egypt tool works only on the static call graph, so indirect function calls e.g. through function pointers are not captured. Making use of dynamic profiling tools that generate a call graph, such as gprof or callgrind, could improve the accuracy of the visualization.
