Re: Loop-carried dependence analysis for scalar variables

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
--

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