JavaScript is disabled for your browser. Some features of this site may not work without it.
Analysis and application of Fourier-Motzkin variable elimination to program optimization : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Computer Science at Massey University, Albany, New Zealand
This thesis examines four of the most influential dependence analysis techniques in use by optimizing compilers:
Fourier-Motzkin Variable Elimination, the Banerjee Bounds Test, the Omega Test, and the I-Test.
Although the performance and effectiveness of these tests have previously been documented empirically,
no in-depth analysis of how these techniques are related from a purely analytical perspective has been done.
The analysis given here clarifies important aspects of the empirical results that were noted but never fully
explained. A tighter bound on the performance of one of the Omega Test algorithms than was known previously
is proved and a link is shown between the integer refinement technique used in the Omega Test
and the well-known Frobenius Coin Problem. The application of a Fourier-Motzkin based algorithm to the
elimination of redundant bound checks in Java bytecode is described. A system which incorporated this
technique improved performance on the Java Grande Forum Benchmark Suite by up to 10 percent.