16 Sep 2001 00:27:30 -0400

Related articles |
---|

Omega Calculator examples bernecky@acm.org (Robert Bernecky) (2001-09-11) |

Re: Omega Calculator examples rus@tamu.edu (Silvius Rus) (2001-09-16) |

From: | Silvius Rus <rus@tamu.edu> |

Newsgroups: | comp.compilers |

Date: | 16 Sep 2001 00:27:30 -0400 |

Organization: | Texas A&M University |

References: | 01-09-052 |

Keywords: | optimize, storage |

Posted-Date: | 16 Sep 2001 00:27:30 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.