To statically determine a program's or task's cache behavior as
accurately as possible, the program/task is decomposed into smaller
components. A program/task may be composed of a number of
functions
. The
possible sequence of calls between these functions is depicted in a
call graph. Each function can be represented by a control-flow graph
where nodes are basic blocks and
edges denote legal transitions of the control flow between basic
blocks.
Functions are further distinguished by function instances. An instance depends on the call sequence, that is, it depends on the immediate call site within its caller as well as the caller's call site, etc. The instance i of a function corresponds to the ith occurrence of the function within a depth-first traversal of the call graph. Thus, a directed acyclic call graph (without recursion) is transformed into a tree of function instances.