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
Loading...
Date
2019
DOI
Open Access Location
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Massey University
Rights
The Author
Abstract
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.
Description
Keywords
Compilers (Computer programs), Algorithms