From: Paul Havlak <paco@cs.rice.edu>
Subject: Re: Control To Data Dependence
Reply-To: Paul Havlak <paco@cs.rice.edu>
Organization: Center for Research on Parallel Computation
Date: Sat, 23 Jan 1993 22:22:45 GMT
Keywords: optimize, bibliography

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
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers