The call-return tree and its application to program performance analysis

The notion of a call-return tree is defined to describe the dynamic calling relationship of the procedure and functions in a program execution. It is shown how the call-return tree can be used to compute the live times and the execution times of the various calls made during the execution. The call-return tree can also be used to compute other behavioral metrics such as the depth and height of a call and the number of direct and indirect calls generated from any point. The technique applies uniformly for both nonrecursive and recursive calls. The algorithms take linear time in the length of the source code and the number of calls made during an execution.