### 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`

.