Re: Omega Calculator examples

Robert Bernecky wrote:


> The types of problems I'm trying to solve with this are basically of
> two forms:
>
> b. Intersection of two symbolically expressed arithmetic progression
> vectors,
> of the form [Start,Stride, Count] or equivalent, where Count may be
> unknown:
> Start, Start+ Stride, start + 2* Stride...
> but I may have knowledge of the arithmetic relationship between the
> two counts.


There is a lot of work done at the University of Illinois at U-C by
Jay Hoeflinger & others about symbolic intersection of linear memory
access descriptors (Start, Stride, Span). Most of it is implemented
in Polaris (http://polaris.cs.uiuc.edu) and uses symbolic range
information. Its main advantage is that it is already in the compiler
(Fortran 77 only). You can also check how the Omega library is used
in Polaris for data dependence testing. There is also a symbolic
expression simplifier.


A different representation (close to the linear systems found in
Omega), but with similar goals exists in SUIF (Stanford). I do not
know too much about it but there is a lot of documentation available
on http://suif.stanford.edu (Saman Amarasinghe's Ph.D. thesis could be
a good referrence).


I think Omega is, at least theoretically, the most powerful of the
three. However, it is limited by the symbolic power of your analyzer.
That "knowledge of the arithmetic relationship" must be expressed so
that it can be exploited. Also, there are a few classes of nonlinear
cases handled by Polaris or SUIF that may not fit the specifications
of the input for the Omega calculator.


There is also much work on linear access descriptors in many other
places that may suit your purpose better. They are usually divided in
two categories. (1) Linear inequation systems, such as the Polytope,
Omega, SUIF. (2) Triplet-based, such as the LMAD (Polaris) or the
GAR.


Good luck,
Silvius




Silvius Rus
Texas A&M University

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