Omega Test (an array data dependence analyzer), Ver 2.0 available

Version 2.0 of our implementation of the Omega test (an array data
dependence analyzer) is now available via anonymous ftp from
ftp.cs.umd.edu (128.8.128.8) in the directory pub/omega. This version is
a substantial extension to the version that was previously made available,
and includes analysis of array kills. Postscript and dvi versions of
research papers describing the Omega test are also available for ftp from
the same directory.


The README file for the distribution is enclosed below.


                Bill Pugh
                pugh@cs,umd.edu
                Univ. of Maryland


-----------------------------------------




This is the readme file for the distribution of the Omega test, which is
available via anonymous ftp from ftp.cs.umd.edu (128.8.128.8) in the
directory pub/omega.


The Omega test is an integer programming algorithm designed for
use in array data dependence analysis, as described in:


William Pugh, The Omega Test: a fast and practical integer
programming algorithm for dependence analysis, Supercomputing '91
(To appear in Comm. of the ACM).


William Pugh and Dave Wonnacott, Eliminating False Data
Dependences using the Omega Test, ACM SIGPLAN Conference on
Programming Language Design and Implementation, June 1992.




The Omega test is implemented on top of Michael Wolfe's tiny program, as
well as in a stand-alone test driver. The Omega test computes exact data
dependence information, including checks for array kills. The Omega test
data dependence analyzer is substantially more accurate than dependence
analyzers in many existing research and commercial systems.


Tiny is a tiny research implementation of an interactive program
restructuring tool. Tiny computes data dependence relations and
interactively performs many restructuring transformations, such as loop
interchanging, distribution, skewing, ... . Michael Wolfe has put his
tiny tool into the public domain, which allowed us to build on top of his
software. We are very grateful for Michael's contributions.




This implementation is a research prototype and has not been subjected
to rigorous testing. In other words:


THERE ARE BUGS IN THIS SOFTWARE


We don't know of any at the moment (other that the ones listed under KNOWN
BUGS/LIMITATIONS below), but we are sure that other, undiscovered bugs
remain in the software (although we have found the Omega test dependence
analyzer to be more reliable than a number of other research prototypes as
well as commercial software). This software has been put into the public
domain as a public service on an "as-is" basis, without warranty or
liability.




The implementation of the Omega test and extensions to tiny have
been done by a number of people at the University of Maryland:
William Pugh
Dave Wonnacott
Udayan Borkar
Wayne Kelly
Jerry Sobieski


This software is public domain. You may do whatever you want with it, and
no guarantees of any kind are made about its performance or lack of
errors. We request that any research or products that make use of this
software acknowledge that use.


Please send mail to omega@cs.umd.edu if you wish to be added to a mailing
list for people interesting in using this software. We will be notifying
people on the mail list of bug fixes and new releases.


Also send mail to omega@cs.umd.edu if you have any trouble installing
the software, bug reports or questions.


This work has been supported by NSF grants CCR-8908900 and CCR-9157384
and by a Packard Fellowship.




FILES
-----


The following tar files can be ftp-ed from ftp.cs.umd.edu (128.8.128.8)
from the directory pub/omega:




  * README This file
  * WOLFE_README The readme file that originally accompanied Michael Wolfe's
distributing of tiny
  * src.tar Source for the omega test and our enhanced version of tiny
  * sparc_bin.tar Sun Sparc executable versions of the programs that can be
made from the src files.
  * dec_bin.tar Decstations 3100 executable versions of the programs that
can be made from the src files.
  * test.tar Test data, expected results
  * doc.tar Documentation
  * ps.tar Postscript versions of two research articles on the Omega
test.
  * dvi.tar DVI versions of the same two research articles on the Omega
test (NOTE: several figures for the first paper are
available _only_ in postscript format).


Together, these tar files constitute the entire tiny system, with the
following directories:


  * include header files (from src.tar)
  * src source code (from src.tar)
  * obj makefile (from src.tar), generated files (from sparc_bin.tar)
  * doc documentation for tiny and for other drivers for the omega test
  * test test data, expected results (from test.tar)
  * misc shell scripts used for regression testing (test.tar and src.tar)


The executable programs are:


  * "t", the tiny environment, upgraded to use the omega test and
test for refinement, killing, and covering of dependences
  * "omega" a driver program that uses the omega test to solve
integer programming problems






COMPILING TINY
--------------


To compile tiny, you will need the following:


  * An C compiler that accepts ANSI-C
  * The curses library for terminal screen manipulation
  * "lex" or a compatible program (such as flex)
  * "yacc" or a compatible program (such as bison)
  * make or pmake (if you do not have pmake, use "make nopmake" first)


In addition, the program "makedepend" is useful for keeping the makefile
up-to-date. If you have it, use "pmake depend" after changing any
includes in your source files. If not, you will have to update the
makefile by hand.


There are many compile-time options for tiny - see the makefile for
details. In addition, setting the environment variable "OMEGAPRINT" to 1
will make tiny print the integer programing problems it generates (and the
results of applying the omega test to these problems) in the debug file
(which defaults to "trace.out").




INCOMPATIBILITY PROBLEMS
------------------------


We have found that header files in /usr/include vary greatly between
machines. You may need to tweak the source code to get it to compile on
your machine.


You changes that we have found it necessary to make to get the system to
compile on some machines:


  * screen.c and tiny.c both include "unistd.h" -- this header file does
not seem to exist on all machines. The only reason this file is
included is to prevent warning messages about undeclared functions.
You may safely delete these includes.


  * missing.h includes extern declarations for a number of standard routines.
This file is only included to prevent warning messages about
undeclared functions. If these functions are defined in your
/usr/include files, you may get conflicts. You may safely comment out
any or all function declarations in missing.h


  * By default, the system compiles with gcc 2.x. If you compile with
gcc 1.x, you may need to eliminate the flag -fno-builtin from
obj/makefile. If you wish to compile with cc, you will need to
change both the flag -f no-built-n and CC and obj/makefile.




VERSIONS
--------


The currently distributed version of enhanced tiny is version 2.0.


This release incorporates the techniques described in the SIGPLAN PLDI
conference paper for dealing with array kills, but does not incorporate
anything to handle assertions about the relative value of symbolic
constants or about the properties of arrays used to index other arrays.






KNOWN LIMITATIONS/BUGS
----------------------


As of version 2.0, the following limitations/bugs still exist:


Loops with negative steps are not handled


Loops with symbolic steps are not handled


No induction variable recognition or forward substitution is done to
improve the accuracy of the dependence analysis.


Currently, the dependence analyzer assumes that any variable that is not a
loop variable is a symbolic constant (THIS ASSUMPTION CAN PRODUCE SERIOUS
ERRORS IN THE DEPENDENCE ANALYSIS IF THE VARIABLE IS NOT CONSTANT).






REGRESSION TESTING
------------------


If you have modified tiny, or if you just want to see if you have
installed it correctly, you can test to see if your output is consistent
with ours. Note that some of our output has not been verified by hand, so
there's no guarantee that consistent results are correct, but at least
they show that you haven't introduced new bugs.


The shell script "r-test", in the misc directory, runs tiny on a source
file and compares the resulting data dependencies to the associated ".rdd"
file. Any discrepancies are printed as output.


The shell script "r-gen" (also in misc) can be used to generate new ".rdd"
files as you add more tests.


The shell script "regression_test" runs r-test on many of the test files
(note that some are omitted on purpose, as they test the detection of
cases that we can't handle yet). If this shell script lists the files it
is testing, with no other output, you have probably not introduced any
bugs.


NOTE that all of the above scripts depend on the environment variable
"TINYHOME", which should be set to the name of the directory in which you
install the 6 directories listed at the beginning of this document. They
also assume that you have an executable version of tiny (named t) in your
search path.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.