The small set of measurement points provides the location for inserting measurement code that records the order of events. While the actual measurement code depends on the intended analysis of the program, the amount of the measurement code may be further reduced by distinguishing between different call sites of a function. For an event-ordered analysis, the first invocation of a function may trigger certain initialization events. The analysis of subsequent calls to the same function are simplified by the assumption that these initialization events have already occurred. Such an example will be illustrated later in the context of instruction cache analysis.
A program may be composed of a number of functions. The possible sequence of calls between these functions is depicted in a call graph []. Functions can be further distinguished by function instances. An instance depends on the call sequence, i.e. on the immediate call site of its caller, the caller's call site, etc. The function instances of a call graph are defined below. The definition excludes recursive calls that require special handling and are discussed later. Indirect calls are not handled since the callee cannot be statically determined.
The call graph of a program without recursion (i.e., a directed
acyclic graph) can be transformed into a tree of function instances by
a depth-first search traversal of the call graph. Function instances
can then be uniquely identified by their index, where 
denotes
the ith occurrence of function f within the depth-first search.
Backedges in the call graph corresponding to recursive calls can be
detected by marking vertices as visited during the depth-first
traversal. If an already visited edge is encountered again, the last
edge in the current traversal is due to recursion. The depth-first
search will then backtrack and retain this backedge as a special edge
in the function-instance graph (see algorithm in []).
