Re: Loop-carried dependence analysis for scalar variables

Paul Havlak <>
Mon, 25 Jan 1993 17:50:44 GMT

          From comp.compilers

Related articles
Loop-carried dependence analysis for scalar variables (1993-01-23)
Re: Loop-carried dependence analysis for scalar variables (Paul Havlak) (1993-01-25)
Re: Loop-carried dependence analysis for scalar variables (1993-01-26)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Paul Havlak <>
Organization: Center for Research on Parallel Computation
Date: Mon, 25 Jan 1993 17:50:44 GMT
References: 93-01-169
Keywords: optimize, analysis, parallel, bibliography (Grant Edward Haab) writes:
>I am seeking information about implementations/research in the area of
>loop-carried dependence analysis of scalar variables. ...

In the PFC batch vectorizer/parallelizer, we built scalar dependences just
like array dependences, ignoring many dataflow issues (we built a separate
def-use graph for scalar optimizations). This proved a mistake; the
scalar dependence edges required more space than the array dependence

In the ParaScope programming environment, we're now starting to use static
single-assignment (SSA) form [1] (I'm not sure what we used before). The
advantages of SSA form for scalar dependence analysis are:

* Building SSA form requires only linear time and space in
extensive experiments. It can be used to compute
def-use (true dependence) and def-def (output
dependence) edges.

* A true or output dependence edge will be loop-carried with
level L if and only if its sink is a pseudo-assignment
(phi node) at a level-L loop header and its source is
a definition in that loop.

The disadvantages of SSA form are:

* Standard SSA form can have extraneous (dead, unuseful) phi
nodes. To prevent spurious (loop-carried or other)
edges, you must delete these or never build them [2].

* Use-def edges (anti-dependences) aren't part of SSA form.
You can build them using the similar techniques of
[2], or else use some conservative approximation,
given that the anti-dependence successors of a use are
a subset of the output-dependence successors of the
use's true-dependence predecessor.


      Author={Ron Cytron and Jeanne Ferrante and
                                Barry K. Rosen and Mark N. Wegman and F. Kenneth Zadeck},
      Title={Efficiently computing static single assignment form
                                and the control dependence graph},

[2] @inproceedings{CCF:Sparse,
        Author={Jong-Deok Choi and Ron Cytron and Jeanne Ferrante},
        Title={Automatic construction of sparse data flow evaluation graphs},
Paul Havlak Dept. of Computer Science
Graduate Student Rice University, Houston TX 77251-1892
PFC/ParaScope projects (713) 527-8101 x2738

Post a followup to this message

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