Synopsis Analyzing the call structure of an application.
Description Suppose a mystery box ends up on your desk. When you open it, it contains a huge software system with several questions attached to it:
- How many procedure calls occur in this system?
- How many procedures does it contains?
- What are the entry points for this system, i.e., procedures that call others but are not called themselves?
- What are the leaves of this application, i.e., procedures that are called but do not make any calls themselves?
- Which procedures call each other indirectly?
- Which procedures are called directly or indirectly from each entry point?
- Which procedures are called from all entry points?
Examples Consider the following call graph (a box represents a procedure and an arrow represents a call from one procedure to another procedure):
The reducer is initialized with all procedures (
The reducer is initialized with all procedures (
carrier(Calls)) and iterates over all entry points (p <- top(Calls)).
At each iteration the current value of the reducer (it) is intersected (&) with the procedures called directly or indirectly
from that entry point ((Calls+)[p]).
Benefits
- In small examples, the above results can be easily obtained by a visual inspection of the call graph. Such a visual inspection does not scale very well to large graphs and this makes the above form of analysis particularly suited for studying large systems.
Pitfalls
- We discuss call analysis in a, intentionally, simplistic fashion that does not take into account how the call relation is extracted from actual source code. The above principles are, however, applicable to real cases as well.