October 01, 1991
URL:http://www.drdobbs.com/a-call-tree-generator-for-c-programs/184402421

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

• main calling functions one, two, and three
• function one calling three and four
• two calling itself, four and six and so on.

C_CALLS

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 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

A Directed Graph

C_CALLS.H

BLD_GRA.C

LISTS.C

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

Compiling C_CALLS

Turbo C: tcc -mh -N *.c
Microsoft C: cl /AH /F 8000
/Fec_calls.exe *.c

Using C_CALLS

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

Caveats

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.

Figure 1: Call Tree (Graphical Representation)

Listing 1

/* line read from .asm file */
#define MAX_LINE_LEN  1024
typedef char LINE[MAX_LINE_LEN + 1];

/* set of tokens extracted from list in .asm file */
#define MAX_TOKENS       10
#define MAX_TOKEN_LEN    80
typedef char TOKENS[MAX_TOKENS][MAX_TOKEN_LEN + 1];

/* fcn name */
#define MAX_NAME_LEN     80
typedef char NAME[MAX_NAME_LEN + 1];

/* fcn call list */
typedef struct CELL *LIST;

typedef struct CELL
{
NAME      name;
LIST      calls, called_from, next;
} CELL;

/* Function prototypes. */

void build_graph(LIST *fcn_list, const char *filename);
void insert_cell(LIST *list, const char *name);
void delete_cell(LIST *list, const char *name);
LIST find_cell(LIST list, const char *name);
void print_calls(LIST list, const char *name, int depth, LIST *fcns);
void print_all_calls(LIST list);
void error(const char *message);
int namecmp(const char *name1, const char *name2);
/* End of File */

Listing 2

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "c_calls.h"

void build_graph(LIST *fcn_list, const char *filename)

/*
Build a graph which shows the calling relationships of all fcns in
a C program by parsing the program's assembly language file.
*/

{
FILE      *input_file;
LINE      line;
TOKENS    toks;
char      *tp;
NAME      caller_name, called_name;
int       i;
LIST      caller_ptr = NULL, called_ptr;

if ((input_file = fopen(filename, "r")) == NULL)
    error("cannot open input file");

while (!feof(input_file))
    {
    fgets(line, sizeof(line), input_file);
    line[strlen(line) - 1] = '\0';  /* Remove \n from end of line. */
    
    memset(toks, 0, sizeof(toks));
    
    /* Extract the fields from the current line. */
    tp = strtok(line, "\t ");  /* Token separator is a tab or space. */
    
    for (i = 0; (i < MAX_TOKENS) && (tp != NULL); i++)
        {
        strcpy(toks[i], tp);
        tp = strtok(NULL, "\t ");  /* Get next token. */
        }
    
    i-; /* i now points to last token on current line.  */
    
    /* If current line is the start of a fcn... */
    if (stricmp(toks[1], "proc") == O)
        {
        strcpy(caller_name, &toks[O] [1]);
        
        /* Insert fcn into fcn list.  */
        insert_cell (fcn_list, caller_name);
        
        /* Make the new fcn the calling fcn.  */
        caller_ptr = find_cell(*fcn_list, caller_name);
        
        }
    
    /* If current line is a user-defined fcn call...  */
    if ((stricmp(toks[0], "call") == 0) &&
       (toks[i][strlen(toks[i]) - 1] != '@') && (toks[i][1] != '_'))
        {
        strcpy (called_name, &toks  [1] );
        
        /* Insert called fcn into the fcn list.  */
        insert_cell (fcn_list, called_name);
        
        /* Record that the calling fcn is calling this fcn.  */
        insert_cell(&caller_ptr->calls, called_name);
        
        /* Record that this fcn is called by the calling fcn.  */
        called_ptr = find_cell (*fcn_list, called_name);
        insert_cell (&called_ptr->called_from, caller_name);
        }
    }

if (fclose(input_file) != 0)
    error("cannot close input file");
}
/* End of File */

Listing 3

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "c_calls.h"

void insert_cell(LIST *list, const char *name)

/*
Insert a new cell in the list with the specified name and return a
pointer to the head of the list. The new cell is inserted in
alphabetical order.
*/

{
LIST new_cell;

if ((*list == NULL) || (namecmp(name, (*list)->name) < 0))
    {
    if ((new_cell = malloc(sizeof(CELL))) == NULL)
        error("out of memory");
    
    new_cell->calls = new_cell->called_from = NULL;
    strcpy(new_cell->name, name);
    
    if (*list == NULL)
        new_cell->next = NULL;
    else
        new_cell->next = *list;
    
    *list = new_cell;
    }
else
    if (stricmp(name, (*list)->name) != O)
        insert_cell((&(*list)->next), name);
}
void delete_cell (LIST *list, const char *name)

/* Delete the cell with the specified name from the list. */

{
LIST ptr;

/* If cell to be deleted is at head of list... */
if ((*list != NULL) && (stricmp{name, (*list)->name) == 0))
    {
    /* Delete the cell. */
    ptr = *list;
    *list = (*list)->next;
    free(ptr);
    }

else
    /* Try to delete the cell from the rest of the list. */
    if (*list != NULL)
        delete_cell(&(*list)->next, name);
}

LIST find_cell(LIST list, const char *name)

/*
Return a pointer to the cell containing the specified name
if it is found in the list. Otherwise return NULL.
*/

{
for (; list != NULL; list = list->next)
    if (stricmp(name, list->name) == 0)
        return list;

return NULL;
}
/* End of File */

Listing 4

#include <stdio.h>
#include "c_calls.h"

void print_calls(LIST list, const char *name, int depth, LIST *fcns)

/*
Print out the name of the current fcn, and recursively print the names
of all fcns called by the current fcn (i.e. "expand" the current fcn).
*/

{
LIST tmp;
int i;

for (i = 1; i <= depth; i++)
    printf("%1d   ", (i - 1) % 10);  /* Print name of current fcn. */

if (find_cell{*fcns, name) != NULL)   /* Don't continue recursive call. */
    printf("%s...\n", name);
else
    {
    printf("%s\n", name);
    
    /* Save the name of the current fcn to avoid infinite expansion. */
    insert_cell(fcns, name);
    
    /* Print out names of all fcns called by the current fcn. */
    tmp = find_cell(list, name);
    
    for (tmp = tmp->calls; tmp != NULL; tmp = tmp->next)
        print_calls(list, tmp->name, depth + 1, fcns);

    /* Delete name of current fcn after completely expanding it. */
    delete_cell(fcns, name);
    }
}

void print_all_calls(LIST list)

/* Print the fcn call tree. */

{
LIST tmp1, tmp2, fcns = NULL;

for (tmp1 = list; tmp1 != NULL; tmp1 = tmp1->next)
    {
    print_calls(list, tmp1->name, 0, &fcns);
    printf("\n%s is called by:\n", tmp1->name);
    
    for (tmp2 = tmp1->called_from; tmp2 != NULL; tmp2 = tmp2->next)
        printf(" %s\n", tmp2->name);
    printf("\n\n");
    }
}
/* End of File */

Listing 5

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "c_calls.h"

/* Allocate enough stack space to support recursion. */
#ifdef __TURBOC__
extern unsigned_stklen = 32000;
#endif

void main(int argc, char *argv[])
{
LIST fcn_list = NULL;

if (argc ! = 2)
    error("c_calls: usage: c_calls <.asm filename>");

build_graph(&fcn_list, argv[1]); /* Determine calling relationships. */

if (fcn_list != NULL)
    print_all_calls(fcn_list); /* Print the fcn call tree. */
}

void error(const char *message)

/* Exit after giving an error message. */

{
printf("Error: %s\n", message);
exit(-1);
}

int namecmp(const char *name1, const char *name2)

/*
Identical to stricmp, except that "main" is considered
less than any other string.
*/

{
if (stricmp(name1, "main") == 0)
    return -1;
else
    if (stricmp(name2, "main') == 0)
        return 1;
    else return stricmp(name1, name2);
}
/* End of File */

Listing 6

tcc -S -c *.c

del asm.tmp

for %%f in (*.asm) do type %%f >> asm.tmp

c_calls asm.tmp

/* End of File */

Listing 7

cl /0d /c /Fa *.c

del asm.tmp

for %%f in (*.asm) do type %%f >> asm.tmp

c_calls asm.tmp

/* End of File */

Table 1 Call Tree (Textual Representation)

 1:  main
 2:  0     one
 3:  0     1      four
 4:  0     1      three     one...
 5:  0     1      2         seven
 6:  0     1      2         three...
 7:  0     1      2
 8:  0     three
 9:  0     1      one
10:  0     1      2         four
11:  0     1      2         three...
12:  0     1      seven
13:  0     1      three...
14:  0     two
15:  0     1      four
16:  0     1      six
17:  0     1      two...

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.