Go to the first, previous, next, last section, table of contents.
The standalone Linear Inequality Calculator program (LIC) takes
input from the command line or a script file and interactively performs
linear inequality and matrix operations.
LIC can be operated in two modes, a matrix and linear inequality
calculator or a rapid prototyping system for code generation.
The rapid prototyping system mode is exclusively designed for prototyping algorithms used for code generation. It uses the Library of Linear Inequalities with Symbolic Coefficients (See the SUIFMATH Reference Manual) as the underlying primitives and provides a simple interface to enter inequalities for loop bounds and array access functions, etc. See section A Rapid Prototyping System for Code Generation.
The matrix and linear inequality calculator mode allows the functions defined in the Matrix Library and Linear Inequality Library (See the SUIFMATH Reference Manual) to be used to manipulate matrices and systems of linear inequalities. See section Matrix and Linear Inequality Calculator.
This system was exclusively developed to simplify the design, debugging, and evaluation process of linear inequality based algorithms used in the SUIF compiler. Many algorithms that were developed for the SUIF shared-memory, distributed-memory and interprocedural passes are based on linear inequalities. For example, the interprocedural parallelizer uses summaries based on linear inequalities. Another example is the generation of SPMD code using "owner computes" rules in the shared memory compiler.
Before LIC, two different approaches were used in the design,
debugging, and evaluation process. The first was the paper-and-pencil
method. This became very time-consuming and error prone. For example,
doing Fourier-Motzkin elimination on even a very small system of
inequalities was quite labor intensive. The second approach was to
implement the algorithm on the compiler. Modifying a compiler is not a
task that can be taken lightly. Implementing many of these algorithms
took weeks and it took even more time to debug them. Worse yet, it was
a nightmare to separate and identify the effects of the algorithm from
the effects of the rest of the compiler. And all this programming and
debugging effort has to be made before even it was possible to evaluate
and validate the algorithms. For even a simple change to the algorithm,
it was back to square one.
LIC was created as an intermediate step between the
paper-and-pencil method and the compiler implementation method.
LIC can be viewed as a `notepad' to write down each and
every step of an algorithm. What can be written in LIC is quite
general and expressive. LIC provides a rich set of functionality
that automates the cumbersome and error-prone steps of algorithm
development. It is very simple to change the steps of the algorithm. At
the same time, large systems of inequalities can be applied to these
algorithms to evaluate and validate them.
LIC has been an invaluable tool in the design, debugging, and
evaluation process of many of the algorithms developed and used in the
SUIF compiler system. Many of the basic ideas and algorithms were
first written as LIC script files. Then, small input data sets
were applied to check the validity of the algorithms. After that, a
number of more complex input sets were applied to evaluate the
algorithms and identify subtle features (or bugs). During this process,
numerous changes to the algorithm were done by changing the script
files. Since LIC does not support a full programming language
with control flow, it may be necessary to modify the script files for
different input sets. But this was quite manageable. Finally, after
the algorithms were proven useful and were completely tested and
debugged, they were implemented in the compiler.
LIC has also been used as a teaching tool in the advanced
compiler course at Stanford. Using LIC, students can explore the
concepts behind data dependence analysis, various code generation
algorithms, etc.
Go to the first, previous, next, last section, table of contents.