Probabilistic Alias Analysis for Parallel Programming in SSA Forms
This addresses the need for more precise alias analysis in compiler optimizations for parallel programming, though it appears incremental as it builds on existing SSA-based methods.
The paper tackles the problem of imprecise static alias analysis for modern compilers by introducing a new probabilistic approach for parallel programs in SSA form, resulting in a system of inference rules that can be applied in contexts like Proof-Carrying Code.
Static alias analysis of different type of programming languages has been drawing researcher attention. However most of the results of existing techniques for alias analysis are not precise enough compared to needs of modern compilers. Probabilistic versions of these results, in which result elements are associated with occurrence probabilities, are required in optimizations techniques of modern compilers. This paper presents a new probabilistic approach for alias analysis of parallel programs. The treated parallelism model is that of SPMD where in SPMD, a program is executed using a fixed number of program threads running on distributed machines on different data. The analyzed programs are assumed to be in the static single assignment (SSA) form which is a program representation form facilitating program analysis. The proposed technique has the form of simply-strictured system of inference rules. This enables using the system in applications like Proof-Carrying Code (PPC) which is a general technique for proving the safety characteristics of modern programs.