Previous: Subroutines, Up: Call Graph

#### 5.2.4 How Mutually Recursive Functions Are Described

The graph may be complicated by the presence of cycles of recursion in the call graph. A cycle exists if a function calls another function that (directly or indirectly) calls (or appears to call) the original function. For example: if `a` calls `b`, and `b` calls `a`, then `a` and `b` form a cycle.

Whenever there are call paths both ways between a pair of functions, they belong to the same cycle. If `a` and `b` call each other and `b` and `c` call each other, all three make one cycle. Note that even if `b` only calls `a` if it was not called from `a`, `gprof` cannot determine this, so `a` and `b` are still considered a cycle.

The cycles are numbered with consecutive integers. When a function belongs to a cycle, each time the function name appears in the call graph it is followed by <cycle number>.

The reason cycles matter is that they make the time values in the call graph paradoxical. The “time spent in children” of `a` should include the time spent in its subroutine `b` and in `b`'s subroutines—but one of `b`'s subroutines is `a`! How much of `a`'s time should be included in the children of `a`, when `a` is indirectly recursive?

The way `gprof` resolves this paradox is by creating a single entry for the cycle as a whole. The primary line of this entry describes the total time spent directly in the functions of the cycle. The “subroutines” of the cycle are the individual functions of the cycle, and all other functions that were called directly by them. The “callers” of the cycle are the functions, outside the cycle, that called functions in the cycle.

Here is an example portion of a call graph which shows a cycle containing functions `a` and `b`. The cycle was entered by a call to `a` from `main`; both `a` and `b` called `c`.

```     index  % time    self  children called     name
----------------------------------------
1.77        0    1/1        main [2]
[3]     91.71    1.77        0    1+5    <cycle 1 as a whole> [3]
1.02        0    3          b <cycle 1> [4]
0.75        0    2          a <cycle 1> [5]
----------------------------------------
3          a <cycle 1> [5]
[4]     52.85    1.02        0    0      b <cycle 1> [4]
2          a <cycle 1> [5]
0        0    3/6        c [6]
----------------------------------------
1.77        0    1/1        main [2]
2          b <cycle 1> [4]
[5]     38.86    0.75        0    1      a <cycle 1> [5]
3          b <cycle 1> [4]
0        0    3/6        c [6]
----------------------------------------
```

(The entire call graph for this program contains in addition an entry for `main`, which calls `a`, and an entry for `c`, with callers `a` and `b`.)

```     index  % time    self  children called     name
<spontaneous>
[1]    100.00       0     1.93    0      start [1]
0.16     1.77    1/1        main [2]
----------------------------------------
0.16     1.77    1/1        start [1]
[2]    100.00    0.16     1.77    1      main [2]
1.77        0    1/1        a <cycle 1> [5]
----------------------------------------
1.77        0    1/1        main [2]
[3]     91.71    1.77        0    1+5    <cycle 1 as a whole> [3]
1.02        0    3          b <cycle 1> [4]
0.75        0    2          a <cycle 1> [5]
0        0    6/6        c [6]
----------------------------------------
3          a <cycle 1> [5]
[4]     52.85    1.02        0    0      b <cycle 1> [4]
2          a <cycle 1> [5]
0        0    3/6        c [6]
----------------------------------------
1.77        0    1/1        main [2]
2          b <cycle 1> [4]
[5]     38.86    0.75        0    1      a <cycle 1> [5]
3          b <cycle 1> [4]
0        0    3/6        c [6]
----------------------------------------
0        0    3/6        b <cycle 1> [4]
0        0    3/6        a <cycle 1> [5]
[6]      0.00       0        0    6      c [6]
----------------------------------------
```

The `self` field of the cycle's primary line is the total time spent in all the functions of the cycle. It equals the sum of the `self` fields for the individual functions in the cycle, found in the entry in the subroutine lines for these functions.

The `children` fields of the cycle's primary line and subroutine lines count only subroutines outside the cycle. Even though `a` calls `b`, the time spent in those calls to `b` is not counted in `a`'s `children` time. Thus, we do not encounter the problem of what to do when the time in those calls to `b` includes indirect recursive calls back to `a`.

The `children` field of a caller-line in the cycle's entry estimates the amount of time spent in the whole cycle, and its other subroutines, on the times when that caller called a function in the cycle.

The `called` field in the primary line for the cycle has two numbers: first, the number of times functions in the cycle were called by functions outside the cycle; second, the number of times they were called by functions in the cycle (including times when a function in the cycle calls itself). This is a generalization of the usual split into non-recursive and recursive calls.

The `called` field of a subroutine-line for a cycle member in the cycle's entry says how many time that function was called from functions in the cycle. The total of all these is the second number in the primary line's `called` field.

In the individual entry for a function in a cycle, the other functions in the same cycle can appear as subroutines and as callers. These lines show how many times each function in the cycle called or was called from each other function in the cycle. The `self` and `children` fields in these lines are blank because of the difficulty of defining meanings for them when recursion is going on.