Key points are not available for this paper at this time.
The Omega test is an integer programming algorithm that can determine whether a dependence exists between two array references, and if so, under what conditions. Conventional wisdom holds that integer programming techniques are far too expensive to be used for dependence analysis, except as a method of last resort for situations that cannot be decided by simpler methods. We present evidence that suggests this wisdom is wrong, and that the Omega test is competitive with approximate algorithms used in practice and suitable for use in production compilers. Experiments suggest that, for almost all programs, the average time required by the Omega test to determine the direction vectors for an array pair is less than 500 ¯secs on a 12 MIPS workstation. The Omega test is based on an extension of Fourier-Motzkin variable elimination (a linear programming method) to integer programming, and has worst-case exponential time complexity. However, we show that for many situations in which other (po...
William Pugh (Tue,) studied this question.