15.9 Omega a solver for linear programming problems

The data dependence analysis contains several solvers triggered sequentially from the less complex ones to the more sophisticated. For ensuring the consistency of the results of these solvers, a data dependence check pass has been implemented based on two different solvers. The second method that has been integrated to GCC is based on the Omega dependence solver, written in the 1990's by William Pugh and David Wonnacott. Data dependence tests can be formulated using a subset of the Presburger arithmetics that can be translated to linear constraint systems. These linear constraint systems can then be solved using the Omega solver.

The Omega solver is using Fourier-Motzkin's algorithm for variable elimination: a linear constraint system containing n variables is reduced to a linear constraint system with n-1 variables. The Omega solver can also be used for solving other problems that can be expressed under the form of a system of linear equalities and inequalities. The Omega solver is known to have an exponential worst case, also known under the name of “omega nightmare” in the literature, but in practice, the omega test is known to be efficient for the common data dependence tests.

The interface used by the Omega solver for describing the linear programming problems is described in omega.h, and the solver is omega_solve_problem.