In this paper we describe efficient symbolic evaluation techniques to compute the values of variables and symbolic expressions, and to determine the condition under which control flow reaches a program statement at compile time. Computations are represented as algebraic expressions over the input data which maintains the crucial relationship between input data and the resulting analysis information. Our symbolic evaluation techniques comprise accurate modeling of assignment and conditional statements, loops, recurrences, arrays (including indirect accesses) and procedures. Efficiency and accuracy is highly improved by aggressive usage of simplification techniques. Examples including program verification, dependence analysis, array privatization, communication vectorization, and elimination of redundant communication are used to illustrate how our symbolic evaluation techniques support program optimization in the context of a distributed memory parallelizing compiler.

Top