Re: Control Dependencies for Loops

hagerman@ece.cmu.edu (John Hagerman) writes:
>This definition of control dependence is fairly typical, right?
>
> DEP(x,y) iff !POST-DOM(y,x)
> and there exists a path P=<x,...,y> such that
> for all z in P (except x,y), POST-DOM(y,z)


        Yes, this is pretty standard, although for this version to be precise,
POST-DOM must be strict; i.e., POST-DOM(x,x) is false for all x.


> [START]
> |
> v
> [E]<-+
> | |
> v |
> +-<?> |
> | | |
> | v |
> | [S] |
> | | |
> | +---+
> v
> [END]
>
>The above definition specifies that DEP(<?>,[E]) and DEP(<?>,[S]). But it
>seems like I should only be concerned with the dependencies within a
>single iteration, so why have DEP(<?>,[E]) at all? Is it only an artifact
>of the definition? ...


        It's not an artifact, it's the whole point. Control dependences,
defined as above, are a powerful abstraction because they can be handled
very similarly to data dependences. Like data dependences, control
dependences are either loop-independent or carried by a particular loop.
In your example, DEP(<?>,[E]) is loop-carried and DEP(<?>,[S]) is
loop-independent.


> ... If I change the definition so that backedges are not
>permitted in P, do I shoot myself?


        Loop-carried control dependences, together with other control and data
dependences, can create dependence cycles (recurrences). So they are
essential for many purposes. Recurrences must be broken by
transformations before a loop can be run in parallel.
        However, if you never perform a transformation that could violate a
loop-carried control dependence, you may "ignore" them because they are
implicitly respected.


Hope this helps,
Paul
--
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.