Re: Control To Data Dependence

lka@lems17lems.brown.edu (Lalit K. Agarwal) writes:
>Has anyone played with converting CONTROL-DEPENDENCE to DATA-DEPENDENCE in
>High-Level-Synthesis or come across any algorithm for doing it in the
>literature.? All suggestions are highly welcome.


        You can convert control dependence to data dependence, but it's better
to build control dependences directly. They can be treated similarly to
data dependences, and explicitly converted to data dependences only when
necessary.
        Control dependence can be replaced with explicit data dependence by
the process of "IF-conversion." Each conditional branch is replaced with
an assignment to a guard variable, and the controlled statements are then
prefixed with a test of the guard. Successive guards are AND'd together,
and guards applying along merging paths are OR'd together.
        This was the approach in the PFC vectorization system [1,2]. There
were some disadvantages:


* Guards constructed in this way can grow quite large, and
simplification is an exponential process.


* If your IF-converted code is your primary representation of
the program, large-scale control structure is
difficult to recover. This can make coarse-grain
parallelization difficult.


        Use of directly-computed control dependences avoids these problems.
Building control dependences with the help of a post- dominator tree [3,4]
avoids the need for simplification. Consider the control conditions
(guards) for S3 in the following:


if (T) then
S1
else
S2
endif
S3


With IF-conversion, the guard for S3 is (T | !T) which simplifies to
(true). Control dependence algorithms never build guards for S3; S3 is a
postdominator of the test and thus always executes.
        One of the cases where control dependences need to be converted to
data dependences is in loop distribution. A test may end up in a
different loop than its controlled statements. Methods for doing the
conversion only when necessary are given in [5] and [6].


        Even if one wanted to do blanket IF-conversion, the way to do it now
would be to build the control dependence graph first, then convert control
dependences to explicit guards. This avoids the need for a simplification
step.


--Paul


[1] @InProceedings{AKPW:83,
                Author = {J. R. Allen and K. Kennedy and
                                C. Porterfield and J. Warren},
                Title = {Conversion of Control Dependence to Data Dependence},
                BookTitle = POPL83,
                Address = Austin,
                Month = Jan,
                Year = 1983}


[2] @Article{AlKe:Automatic,
                Author = {J. R. Allen and K. Kennedy},
                Title = {Automatic Translation of {Fortran} Programs to Vector Form},
                Journal = TOPLAS,
                Volume = 9,
                Number = 4,
                Pages = {491--542},
                Month = Oct,
                Year = 1987}


[3] @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}}


[4] @inproceedings{CFS:Compact,
Author={R. Cytron and J. Ferrante and V. Sarkar},
Title={Compact representations for control dependence},
BookTitle=SIGPLAN90,
Address={White Plains, New York},
Pages={337--351},
Month=Jun,
Year={1990}}


[5] @InProceedings{KeMc:LoopControl,
                Author = {K. Kennedy and K. S. M\raisebox{.2em}{c}Kinley},
                Title = {Loop Distribution with Arbitrary Control Flow},
                BookTitle = {Proceedings of Supercomputing '90},
                Address = NY,
                Month = Nov,
                Year = 1990}


[6] @InProceedings{HHCy:LoopExits,
                Author = {Bor-Ming Hsieh and Michael Hind and Ron Cytron},
                Title = {Loop Distribution with Multiple Exits},
                BookTitle = {Proceedings of Supercomputing '92},
                Address = {Minneapolis, Minnesota},
                Month = Nov,
                Year = 1992}
--
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.