Eric Bergman-Terrell is an author of astronomy software and articles about astronomy and computer science. You may contact him at Personal MicroCosms, 8547 E. Arapahoe Rd., Suite J-147, Greenwood Village, CO 80112.
Introduction
A call tree shows the hierarchy of function calls in a program. For example, the call tree in Figure 1 shows:
- main calling functions one, two, and three
- function one calling three and four
- two calling itself, four and six and so on.
C_CALLS
Since call trees can clarify the function interaction of complex programs, a utility to generate call trees belongs in every programmer's toolbox. This article describes a program named C_CALLS that generates text call trees for Turbo C or Microsoft C programs. C_CALLS can be compiled by either the Turbo C or the Microsoft C compiler.
C_CALLS uses the assembly output from the compiler, so if you don't use the Turbo C or the Microsoft C compiler you may need to modify C_CALLS to work with your compiler's output. The section on customizing C_CALLS provides further details.
Recursive Function Calls
When a function calls itself either directly or indirectly, that call is said to be "recursive." In C_CALLS output, recursive calls are marked by an ellipsis ("..."). In Table 1, function three (line 8) calls itself directly on line 13, and indirectly (through function one) on line 11.
When a program runs, recursive calls bottom out with some base case (arguments that don't require a recursive call), but the static call tree contains a loop back to a previous node, creating an infinite branch in the tree (since the call tree doesn't have access to any arguments). So, when a function makes a recursive call (such as in line 13 of Table 1) , that branch of the function call tree is abandoned and an ellipsis is printed.
How C_CALLS Works
The following sections present the C_CALLS source code and discuss its implementation and use.
A Directed Graph
When you compile a program using Turbo C or Microsoft C, you can specify an option that saves the assembly language translation of the program to a disk file. Using the assembly language file as input, C_CALLS builds a directed graph representing the function calls in the program.
C_CALLS.H
The data structures used for the directed graph (CELL and LIST) are defined in the C_CALLS.H header file shown in Listing 1. Note that "function" is abbreviated as "fcn" in the code.
BLD_GRA.C
Function build_graph creates the directed graph by parsing the assembly language file. build_graph is defined in file BLD_GRA.C shown in Listing 2.
LISTS.C
The directed graph structure uses several linked lists. These lists are manipulated by functions insert_cell, delete_cell, and find_cell, which are defined in file LISTS.C shown in Listing 3.
PRINT.C
Once the directed graph has been built, the call tree is printed by calling print_all_calls, defined in PRINT.C.
C_CALLS "expands" a function, say main, by printing the function name "main" followed by the names of all functions called by that function (one, three, two).
To avoid infinite loops while expanding recursive functions, a list named fcns is used. fcns contains the names of the functions currently being expanded. If print_calls is called for a function already in fcns, that function name is printed followed by an ellipsis ("...") and that function is not expanded further. See Listing 4.
C_CALLS.C
The main program, C_CALLS (defined in C_CALLS.C), takes one command-line argument, the name of an assembly language file. C_CALLS parses the file, builds the directed graph, and prints out the call tree. See Listing 5.
Compiling C_CALLS
The following commands show the appropriate options for compiling the C_CALLS modules (when they are the only.c files in the current directory).
Turbo C: tcc -mh -N *.c Microsoft C: cl /AH /F 8000 /Fec_calls.exe *.c
Using C_CALLS
To generate a call tree with C_CALLS first compile the target program using an option to create an assembly language file, then run C_CALLS with the assembly language filename as an argument.
The MS-DOS batch files shown in Listing 6 and Listing 7 generate the assembly language file and run C_CALLS. Turbo C users can use TC_CALLS.BAT, and Microsoft C users can use MS_CALLS.BAT. The batch files expect only the target files in the current directory. For further details on generating assembly language files, see your compiler's user guide.
Customizing C_CALLS
Users may want to customize C_CALLS. Possible extensions include excluding standard library functions from call trees or supporting additional compilers. To support another compiler, the first step requires studying the format of assembly language files generated by the compiler. The remaining step is to modify the function build_graph, adjusting its parsing process to the new format.
Caveats
Since optimizing compilers can change the function calling hierarchy of a program by removing or changing function calls, you should disable optimization when generating assembly language files for C_CALLS. For details on optimization and possible interaction with call trees, see your compiler's user guide.
If your compiler's assembly-language file format changes in subsequent releases, function build_graph may need to be modified.
C_CALLS has been tested with Turbo C v1.5 and Microsoft C v5.1.
