Go to the previous, next section.

The named linear inequality (class `named_lin_ineq`

) is a
composition of two parts,
a name table (section Name Table) and a system of linear inequalities
(section Linear Inequality Library).

The following are functions and operations available for
`named_lin_ineq`

. In this list of functions,
symbols `nli`

, `nli1`

, `nli2`

are named linear inequalities,
the symbol `ptr_nli`

is a pointer to a named linear inequality,
symbols `nt`

and `nt1`

are name tables,
symbol `nte`

is a name table entry,
`i`

and `j`

are integers,
symbol `leq`

is a `lin_ineq`

and
`im`

is an `immed`

.

`named_lin_ineq nli();`

- Creates an empty named linear inequality.
`named_lin_ineq nli(nli1);`

`nli.init(nli1);`

- Duplicates the named linear inequality
`nli1`

. `named_lin_ineq nli(nt, leq);`

- The names are taken from nt and the system of inequalities are
taken from leq. Note that the number of columns in leq
should match the number of elements in nt.
`nt = nli.names();`

`leq = nli.ineqs();`

- Get the name part or the linear inequality system part of the named
linear inequality.
`i = nli.m();`

`i = nli.n();`

`m()`

is the number of inequalities and`n()`

is the number of variables plus one (for the constant term) in the system.`nli.swap_col(i, j);`

- Swap the columns i and j. Both the name table and the
system of inequalities are changed.
`nli.add_col(nte, i);`

- Add the given name at the ith column. A blank column is added to the
system of inequalities.
`nli.del_col(i);`

`nli.del_col(i, j);`

- Delete the column(s). Both the names and the entries in the system of
inequalities are deleted.
`i = nli.find(im);`

- Find the column of the variable with the name im. If the variable
is not in the system return -1.
`nli = nli2;`

`nli = leq;`

- Copy the named linear inequalities. When the linear inequality leq is
given for the RHS, only the system of inequalities in nli is
updated. The columns in leq should match the elements in
nli.
`nli1 || nli2;`

`named_lin_ineq::align_named_lin_ineqs(nli1, nli2);`

`nli.align(nt);`

- Align two named linear inequalities.
`boolean isa = named_lin_ineq::is_aligned(nli1, nli2);`

- Check if two inqualities are already aligned.
`nli = nli1 & nli2;`

`nli &= nli1;`

- Intersect the two systems of inequalities by combining the two systems
of inequalities together. Before performing the intersection, the two
inequalities are aligned.
`boolean del1, del2;`

`ptr_nli = named_lin_ineq::and(ptr_nli1, ptr_nli2, del1, del2);`

- A simplified function to intersect systems of inequalities when one or
more systems may not exist (NULL pointers). The flags are used to do
memory management. For example if del1 is TRUE and ptr_nli1
is not NULL, then that named linear inequality will be deleated.
`nli &= leq;`

- Perform intersection assuming that leq is already aligned with nli.
`nli.project();`

- Project the system of inequalities using Fourier-Motzkin elimination to
reduce extra inequalities.
`nli.project_away(nt);`

`nli.project_away(im);`

- Project away a given variable from the system of inequalities using
Fourier-Motzkin elemination.
`boolean isempty = ~nli;`

- Performs Fourier-Motzkin elimination with Branch-and-Bound to find if an
integer solution exists for the system. Returns TRUE if no integer
solution.
`boolean iseq = (nli1 == nli2);`

- Returns TRUE if both systems represent identical convex polyhedrons.
`boolean isin = (nli1 << nli2);`

`boolean isin = (nli2 >> nli1);`

- Returns TRUE if the contex polyhedron of nli1 is contained in the
contex polyhedron of nli2.
`array_info ai;`

`access_vector av;`

`boolean lb;`

`immed ind;`

`ptr_nli = named_lin_ineq::mk_named_lin_ineq(ai, ind, lb);`

`ptr_nli = named_lin_ineq::mk_named_lin_ineq(av, ind, lb);`

- Convert the linear expressions of array bounds and access functions
to a named linear inequality. If the access function is a linear
expression f() and lb is TRUE,
`mk_named_lin_ineq()`

will create a named linear inequality representing`f() <= ind`

, and if lb is FALSE,`lind <= f()`

. `instruction * in;`

`in = nli.mk_bounds();`

- Convert the system of inequalities directly to a SUIF
expression, i.e. construct a SUIF expression tree which will return
TRUE when executed with a set of values of the variables that satisfy
the system of inequalities. This can be incorporated as the test of a
SUIF IF conditional.
`instruction * in;`

`boolean is_ub;`

`base_symtab * sym_tab;`

`in = nli.create_expression(v, is_ub)`

`in = nli.create_expression(v, is_ub, symb_tab)`

- Find the set of constraints of the system which are upper (or lower)
bounds of the variable v and create a SUIF expression that
will calculate the bound value. This is extensively used to produce
bounds when generating loop nests to iterate over a convex polyhedron
defined by a system of inequalities.
`immed_list iml;`

`named_lin_ineq nli(iml);`

`iml = nli.cvt_immed_list()`

- Convert to (from) a named linear inequality from (to) an
`immed_list`

. This is used to store a named linear inequality as an annotation so that the information can be transferred between passes. `nli.cleanup();`

- Performs general clean-up such as removing unused names and inequalities
that are always true.
`nli.print_exp();`

`nli.print();`

- Print the named linear inequality in the matrix format or as
expressions.
`tree_for * tf;`

`ptr_nli = include_for(tf);`

`ptr_nli = include_for(tf, ptr_nli);`

- Generate a named linear inequality to represent the iterations of the
loop. If the optional pointer is valid, that named linear inequality is
added to the result. The dependence library command
`fill_in_access()`

needs to be run on the`tree_proc`

before using`include_for`

.

Go to the previous, next section.