scale.score.dependence.omega
Class OmegaTest

java.lang.Object
  scale.score.dependence.DataDependence
      scale.score.dependence.omega.OmegaTest

public class OmegaTest
extends DataDependence

A class which implements the Omega test.

$Id: OmegaTest.java,v 1.51 2007-01-04 17:08:09 burrill Exp $

Copyright 2008 by the Scale Compiler Group,

Department of Computer Science

University of Massachusetts,

Amherst MA. 01003, USA

All Rights Reserved.

A class which implements the Omega test. The Omega test is a practical algorithm for exact array dependence analysis developed by William Pugh at Maryland. The Omega test is an integer programming technique that combines new methods for eliminating equality constraints with an extension of Fourier-Motzkin variable elimination.

The code in this class is directly based upon the code in Petit, a tool that comes with the Omega code that illustates dependence analysis (especially files, ddomega.[ch] and Zima.[ch]). The Zima file implements a dependence interface which facilitates creating relations for program analysis. The Zima interface is based on the notation suggested by Hans Zima in Supercompilers for Parallel and Vector Computers.

Our code significantly differs from the Petit in several ways. Petit computes all the dependences and stores them into the graph during a single pass over the array references. Our code differs since we compute forward and backward dependences in separate calls. Also, we compute loop-carried and loop-independent dependences during separate calls (although this probably doesn't waist much time). If time is a critical factor then, we should rewrite the routines to compute the forward and backward dependences at the same time.

The Omega test uses the Omega library (scale.omega) to create dependence equations and compute direction vectors and distance values.

Improvement:

I think we can improve the efficiency of this code by generating all the dependences during the call to ddTest (during a single pass over the dependence relations) and then the getForwardDependence and getBackwardDependence would just return the appropriate information (this current requires two passes over the dependence relations).

See Also:

Relation, BanerjeeTest

Field Summary

static boolean

classTrace True if traces are to be performed.

Fields inherited from class scale.score.dependence.DataDependence

bnest, cEqDependent, cFailed, cIndependent, cLCDependent, cloop, cUnkDependent, ddinfo, iloop, inode, loopInfo, oloop, onode, precedes, result, scribble

Constructor Summary

OmegaTest(Scribble scribble)
Create a data dependence object using the Omega test.

Method Summary

int	ddTest(SubscriptExpr onode, SubscriptExpr inode, LoopHeaderChord oloop, LoopHeaderChord iloop, int precedes) Set up the relation for the Omega test.
Vector<long[]>	getBackwardDependence() Return backwards dependence information.
Vector<long[]>	getDependenceInfo(boolean forward) Compute data dependences in one direction.
Vector<long[]>	getForwardDependence() Return forward dependence information.
void	printDepRelation() Print dependence relation to stdout.
void	spatialTest(SubscriptExpr onode, SubscriptExpr inode, LoopHeaderChord oloop, LoopHeaderChord iloop, int precedes) Create a data dependence relation for the two array accesses using the omega library.

Methods inherited from class scale.score.dependence.DataDependence

getBackwardDependences, getDDInfo, getForwardDependences, initialize

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

classTrace

public static boolean classTrace

True if traces are to be performed.

Constructor Detail

OmegaTest

public OmegaTest(Scribble scribble)

Create a data dependence object using the Omega test. The Omega test is an exact dependence test created by William Pugh.

Method Detail

ddTest

public int ddTest(SubscriptExpr onode,
                  SubscriptExpr inode,
                  LoopHeaderChord oloop,
                  LoopHeaderChord iloop,
                  int precedes)

Set up the relation for the Omega test. This method does not actually compute dependences, it just sets up the Omega relation between two array accesses using the Omega library. The relation is a mathematical representation of the dependence between the references.

We create an Omega Relation object and we add constraints to the relation to set up the dependence test. We create AccessIteration objects to represent the array accesses. Then, we add constraints which indicate the conditions which cause a data dependence between the two accesses.

The inode must precede the onode in execution order.

Specified by:

ddTest in class DataDependence

Parameters:

onode - is a node access

inode - is a node access

oloop - is the loop coressponding to the onode access

iloop - is the loop coressponding to the inode access

precedes - specifies the execution order. It is 1 if inode is execute before onode, -1 if onode is executed befoe inode, and 0 if they are "executed in parallel".

Returns:

the data dependence test result

See Also:

DDInfo, getForwardDependence(), getBackwardDependence(), Relation

printDepRelation

public void printDepRelation()

Print dependence relation to stdout. The relation is a mathematical representation of the dependence between the references.

See Also:

Relation

spatialTest

public void spatialTest(SubscriptExpr onode,
                        SubscriptExpr inode,
                        LoopHeaderChord oloop,
                        LoopHeaderChord iloop,
                        int precedes)
                 throws java.lang.Exception

Create a data dependence relation for the two array accesses using the omega library.

The inode must precede the onode in execution order.

Specified by:

spatialTest in class DataDependence

Parameters:

onode - is a node access

inode - is a node access

oloop - is the loop coressponding to the onode access

iloop - is the loop coressponding to the inode access

precedes - specifies the execution order. It is 1 if inode is execute before onode, -1 if onode is executed befoe inode, and 0 if they are "executed in parallel".

Throws:

java.lang.Exception

getForwardDependence

public Vector<long[]> getForwardDependence()

Return forward dependence information. That is, the information from onode to inode. Recall that the dependence tester computes dependences in both directions. This routine just checks if there is a forward dependence.

Our code is much different than the code it is based upon (Petit). Petit determines all dependences and stores them in the graph during the same pass. We make separate passes to compute forward and backward dependences.

We need to make a clone of the dependence relation information and operate on the cloned version. We do this because the depRelation relation is altered by this method, but we need the unaltered relation for getBackwardDependence.

Returns:

the data dependence information for foward dependences.

getBackwardDependence

public Vector<long[]> getBackwardDependence()

Return backwards dependence information. That is, the information from inode to onode. Recall that the dependence tester computes dependences in both directions. This routine just checks if there is a backward dependence.

Our code is much different than the code it is based upon (Petit). Petit determines all dependences and stores them in the graph during the same pass. We make separate passes to compute forward and backward dependences.

We need to make a clone of the dependence relation information and operate on the cloned version. We do this because the depRelation relation is altered by this method, but we would like to maintain the unaltered relation (for example, if the method getForwardDependence is called after this method.

Returns:

the data dependence info for backward dependences.

getDependenceInfo

public Vector<long[]> getDependenceInfo(boolean forward)

Compute data dependences in one direction. The code for determining forward and backward dependences is pretty much the same except for a few details. The algorithm works by computing loop-carried and loop-independent dependences separately. We then merge the dependences into a single structure. Note - we only compute self dependences if forward is true. Also, we work on a copy of the dependence relation since we change the relation when we test for dependences. However, we need to retain the original relation because we will call this routine twice.

The code in Petit works the same way - we just separate the computation of loop-carried and loop-independence into different methods.

Specified by:

getDependenceInfo in class DataDependence

Parameters:

forward - is true if we want forward dependence information.

Returns:

the dependence information (in one direction).