Go to the previous, next section.

Named Linear Inequality

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);
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, 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);
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.

Project the system of inequalities using Fourier-Motzkin elimination to reduce extra inequalities.

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.

Performs general clean-up such as removing unused names and inequalities that are always true.

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.