Importance

Loading Importance Indicators...

Abstract

A call-graph profile is created by constructing a finite state machine during execution of a program to be analyzed. Each state in the state machine corresponds to an execution context, ie. the set of subroutines that are active in the program at a particular time, together with information about the subroutines that precede and follow their most recent activation on the program's stack. Each transition between states represents a change in execution context taking place on a subroutine call. Each state is represented by a dynamically-allocated record containing a counter that stores the number of times the state has been entered, a counter storing the number of self-transitions made from the state to itself, a timer that stores the total time spent in the state, and data that records the set of subroutines that are active in the execution context. Transitions between states are stored in a hash table whose key is a pair of addresses: the address of the record representing the current state and entry address of the subroutine being called. The profiler also maintains a shadow stack which shadows the subroutine stack of the running program. Each item in the shadow stack is a state of the finite state machine represented by a pointer to the current state record. On entry to a subroutine a new item is added to the stack, and on a return, the stack is popped. After execution the data for each state is written to a file and is then analyzed to produce a report for each subroutine giving the time spent in each routine and in its descendents.

Loading the Abstract Image...

First Claim