Interprocedural Symbolic Analysis

Abstract

Compiling for efficient execution on advanced computer architectures requires extensive program analysis and transformation. Most compilers limit their analysis to simple phenomena within single procedures, limiting effective optimization of modular codes and making the programmer’s job harder. We present methods for analyzing array side effects and for comparing nonconstant values computed in the same and different procedures. Regular sections, described by rectangular bounds and stride, prove as effective in describing array side effects in LINPACK as more complicated summary techniques. On a set of six programs, regular section analysis of array side effects gives 0 to 39 percent reductions in array dependences at call sites, with 10 to 25 percent increases in analysis time. Symbolic analysis is essential to data dependence testing, array section analysis, and other high-level program manipulations. We give methods for building symbolic expressions from gated single-assignment form and simplifying them arithmetically. On a suite of 33 scientific Fortran programs, symbolic dependence testing yields reductions of 0 to 32 percent in the number of array dependences, as compared with constant propagation alone.The additional time and space requirements appear proportional to the size of the codes analyzed. Interprocedural symbolic methods are essential in enabling array section analysis and other advanced techniques to operate on multiple procedures. Our implementation provides this support while allowing for recompilation analysis to approximate the incrementalism of separate compilation. However, direct improvement of data dependence graphs from interprocedural symbolic facts is rare in the programs studied. Overall, the use of our symbolic techniques in a production compiler is justified by their efficiency, their direct enhancement of dependence testing within procedures, and their indirect improvement of interprocedural dependence testing through array side effect analysis.