|Control Dependencies for Loops email@example.com (1993-04-20)|
|Re: Control Dependencies for Loops firstname.lastname@example.org (1993-04-22)|
|Re: Control Dependencies for Loops email@example.com (1993-04-22)|
|From:||firstname.lastname@example.org (Paul Havlak)|
|Date:||Thu, 22 Apr 1993 12:15:47 GMT|
email@example.com (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.
> | |
> v |
> +-<?> |
> | | |
> | v |
> | [S] |
> | | |
> | +---+
>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
> ... 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
Hope this helps,
Paul Havlak Dept. of Computer Science
Graduate Student Rice University, Houston TX 77251-1892
PFC/ParaScope projects (713) 527-8101 x2738 firstname.lastname@example.org
Return to the
Search the comp.compilers archives again.