<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 1988-2015 Free Software Foundation, Inc.

Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3 or
any later version published by the Free Software Foundation; with the
Invariant Sections being "Funding Free Software", the Front-Cover
Texts being (a) (see below), and with the Back-Cover Texts being (b)
(see below).  A copy of the license is included in the section entitled
"GNU Free Documentation License".

(a) The FSF's Front-Cover Text is:

A GNU Manual

(b) The FSF's Back-Cover Text is:

You have freedom to copy and modify this GNU Manual, like GNU
     software.  Copies published by the Free Software Foundation raise
     funds for GNU development. -->
<!-- Created by GNU Texinfo 5.2, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Compiler Collection (GCC) Internals: Omega</title>

<meta name="description" content="GNU Compiler Collection (GCC) Internals: Omega">
<meta name="keywords" content="GNU Compiler Collection (GCC) Internals: Omega">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="index.html#Top" rel="start" title="Top">
<link href="Option-Index.html#Option-Index" rel="index" title="Option Index">
<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
<link href="Loop-Analysis-and-Representation.html#Loop-Analysis-and-Representation" rel="up" title="Loop Analysis and Representation">
<link href="Machine-Desc.html#Machine-Desc" rel="next" title="Machine Desc">
<link href="Dependency-analysis.html#Dependency-analysis" rel="prev" title="Dependency analysis">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
-->
</style>


</head>

<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="Omega"></a>
<div class="header">
<p>
Previous: <a href="Dependency-analysis.html#Dependency-analysis" accesskey="p" rel="prev">Dependency analysis</a>, Up: <a href="Loop-Analysis-and-Representation.html#Loop-Analysis-and-Representation" accesskey="u" rel="up">Loop Analysis and Representation</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Option-Index.html#Option-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Omega-a-solver-for-linear-programming-problems"></a>
<h3 class="section">15.9 Omega a solver for linear programming problems</h3>
<a name="index-Omega-a-solver-for-linear-programming-problems"></a>

<p>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&rsquo;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.
</p>
<p>The Omega solver is using Fourier-Motzkin&rsquo;s algorithm for variable
elimination: a linear constraint system containing <code>n</code> variables
is reduced to a linear constraint system with <code>n-1</code> 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 &ldquo;omega nightmare&rdquo; in the
literature, but in practice, the omega test is known to be efficient
for the common data dependence tests.
</p>
<p>The interface used by the Omega solver for describing the linear
programming problems is described in <samp>omega.h</samp>, and the solver is
<code>omega_solve_problem</code>.
</p>


</body>
</html>