Inter-Procedural Dependency Analysis

To generate the prefetch thread for an application program that contains multiple procedures, inter-procedural dependency analysis is required. It propagates the information on whether a variable is I/O related through procedure call arguments, return values, and global variables. This propagation proceeds as follows:

1. For each procedure $P$, let $Q(x_1, x_2,..., x_n)$ be one of the procedures that $P$ calls with actual parameters $(y_1, y_2,.., y_n)$. If any actual parameter $y_i$ is I/O related in $P$, and it is a pointer (i.e., the value it points to can be changed inside $Q$), then mark the object $x_i$ points to in $Q$ as I/O related. If $P$ stores the return value from $Q$ in variable $a$, and $a$ is I/O related in $P$, then the variable in $Q$ corresponding to the return value is considered I/O related.

2. For each procedure $P(y_1, y_2,.., y_n)$, let $R$ be a procedure that calls $P$ with actual parameters $P(z_1, z_2,..., z_n)$. If a formal parameter $y_i$ is I/O related in $P$, its corresponding actual parameter $z_i$ is considered I/O related in $R$.

3. All global variables that are I/O related are I/O related within all procedures.

The above algorithm only needs to be applied to the function call graph once if there are no recursive function calls. It recursion occurs, the algorithm may need to be applied more than once until the extracted code converges.