Re: Dependency relation types

K.P.Williams@reading.ac.uk (K. P. Williams)12 Dec 1997 14:53:26 -0500

From comp.compilers

Related articles
Dependency relation types fadata!velco@mail-relay.eu.net (Momchil \Velco\Velikov) (1997-12-10)
Re: Dependency relation types K.P.Williams@reading.ac.uk (1997-12-12)
| List of all articles for this month |

 From: K.P.Williams@reading.ac.uk (K. P. Williams) Newsgroups: comp.compilers Date: 12 Dec 1997 14:53:26 -0500 Organization: Compilers Central References: 97-12-067 Keywords: analysis

Momchil "Velco" Velikov wrote:
> Could anyone explain me the different kinds of dependency relations,
> i.e., flow-, output-, anti-, etc., or if the explanation would took a
> lot of space, could anyone give me any references.

Hi,

Calculation of Flow, Anti, Input and Output dependencies is
derived from caluclation of DEF and USE sets. Simply, given a
statement S, the DEF set of S is the set of variables
written to (i.e. DEFINED) in the execution of S. The USE set of S
is the set of variables USE'd in the execution of S. Examples:

a = b DEF = {a} USE = {b}

a = 0 DEF = {a} USE = Empty

a = a * 2 + b DEF = {a} USE = {a, b}

for (i = 0; i < N; i++) DEF = {i} USE = {i, N}

if (a < Total) DEF = Empty USE = {a, Total}

So first - compute the DEF / USE sets for all statements in your program
then you can compute the Flow, Anti, Output, and Input dependencies
as you require.

Approximate definitions of Flow, Anti, Output and Input dependencies can
be made in terms of DEF/USE sets, namely:

If a variable (V) exists in the DEF of one statement (S1) and the USE of
another later statement (S2), with no intervening re-definition of V, then
there exists a Flow dependency from statement S1 to S2.

If a variable (V) exists in the USE of one statement (S1) and the DEF of
another later statement (S2), with no intervening re-definition of V, then
there exists a Anti dependency from statement S1 to S2.

If a variable (V) exists in the DEF of one statement (S1) and the DEF of
another later statement (S2), with no intervening re-definition of V, then
there exists a Output dependency from statement S1 to S2.

If a variable (V) exists in the USE of one statement (S1) and the USE of
another later statement (S2), with no intervening re-definition of V, then
there exists a Input dependency from statement S1 to S2.

Example:

Given the following piece of code;

1) a := b - 1
2) c := a * 2
3) x := y
4) a := i
5) a := y

The following dependencies exist:

Flow (sometimes called True dependencies) :

1 to 2 {a}

Anti :

2 to 4 {a}

Output :

4 to 5 {a}

Input:

3 to 5 {y}

Anti / Output and Input dependencies are all sometimes called False
dependencies
since they may all be removed by a restructuring/parallelizing compiler. True
dependencies cannot always be removed ...

This all gets quite complicated when analyzing arrays references (especially in
loops), analyzing pointer dependencies, and in the presence of procedure /
function calls.

Good references are:

\bibitem[6]{Bacon94} Bacon, D.F, Graham, S.L., and Sharp, O.J.,
{\it Compiler Transformations for High-Performance Computing},
ACM Computing Surveys, Vol 26, No. 4, pgs 345-420, Dec (1994).

\bibitem[120]{Wolfe96} Wolfe, M.J.,
{\it High Performance Compilers for Parallel Computing},

Hope this helps,

Ken

=========================================================================