Channels ▼
RSS

A Call-Tree Generator For C Programs


, October 01, 1991


October 1991/A Call-Tree Generator For C Programs

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.
While graphic dispays of call trees, such as Figure 1, are clearest, call trees can also be displayed using text and indentation, as in Table 1. Note that Figure 1 and Table 1 give the same information.

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.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video