Re: Loop-carried dependence analysis for scalar variables

Paul Havlak <paco@cs.rice.edu>Mon, 25 Jan 1993 17:50:44 GMT

From comp.compilers

Related articles
Loop-carried dependence analysis for scalar variables haab@crhc.uiuc.edu (1993-01-23)
Re: Loop-carried dependence analysis for scalar variables paco@cs.rice.edu (Paul Havlak) (1993-01-25)
Re: Loop-carried dependence analysis for scalar variables paco@cs.rice.edu (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

haab@crhc.uiuc.edu (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
edges.

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.

--Paul

[1]@article{CFRWZ:Efficient,
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},
Journal=TOPLAS,
Volume=13,
Number=4,
Pages={451-490},
Month=Oct,
Year={1991}}

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

Post a followup to this message