Mon, 14 Dec 1992 23:42:03 GMT

Related articles |
---|

Extension Languages marks@iris.mincom.oz.au (1992-12-14) |

question on control dependence mcconnel@newta1.cs.uiuc.edu (1992-12-14) |

Re: question on control dependence cliffc@rice.edu (1992-12-15) |

Re: question on control dependence preston@dawn.cs.rice.edu (1992-12-15) |

Re: question on control dependence preston@dawn.cs.rice.edu (1992-12-15) |

Re: question on control dependence paco@cs.rice.edu (Paul Havlak) (1992-12-15) |

Re: question on control dependence bwilson@shasta.stanford.edu (1992-12-15) |

Re: question on control dependence paco@cs.rice.edu (1992-12-16) |

[2 later articles] |

Newsgroups: | comp.compilers |

From: | mcconnel@newta1.cs.uiuc.edu |

Organization: | Compilers Central |

Date: | Mon, 14 Dec 1992 23:42:03 GMT |

References: | 92-12-056 |

Keywords: | design |

I've come up with a simple algorithm for computing control dependences,

and I was wondering if it was already known; I haven't seen it in the

literature. My algorithm uses straightforward data flow analysis, and

works like so:

=== Begin Algorithm ===

1. For a given flow node X, let P(X) denote the nodes that post-dominate

X, along with X itself. Compute P(X) by using any of the standard

techniques to solve the following backward data flow equations:

P(X) = X | (P(Y1) & ... & P(Yn)),

P(Stop) = {}

where Y1 ... Yn are the successors of X, "|" denotes set union, "&"

denotes set intersection, and Stop is a unique exit node for the flow

graph. (This part is pretty much straight out of the red dragon book.)

2. Assume that each node in the flow graph has no more than 2 successors,

and that if a node does have 2 successors, one is the "true" successor and

the other the "false" successor. For a given flow node X, let CD(X)

denote the nodes that are control dependent on X. If X has fewer than 2

successors, CD(X) is empty. Otherwise, we can find CD(X) as follows:

CD(X) = P(X-true) ^ P(X-false)

where X-true and X-false are respectively the true and false successors,

and "^" denotes symmetric difference (i.e., A ^ B = (A | B) - (A & B)).

Furthermore, the edges that should be labelled "true" in the control

dependence graph are the ones from X to the nodes in CD(X) & P(X-true);

and "false", the ones to the nodes in CD(X) & P(X-false).

=== End Algorithm ===

To me this algorithm seems much more intuitive and easier to program

than the control dependence algorithms in [1] and [2], since those

algorithms are based on the post-dominator tree, which is more

complicated to compute than P(X), and less suitable for computing

control dependences. This algorithm is asymptotically as efficient as

they are; for typical programs, it's probably more efficient than the

algorithm in [1]. My question is, has this algorithm been proposed

before? (It seems too simple not to have been.)

Carl McConnell

Grad Student

Department of Computer Science

University of Illinois at Urbana-Champaign

1304 W. Springfield Ave.

Urbana, IL 61801-2987

-------------------

References:

[1]

@article{ferrante87,

author="Jeanne Ferrante and Karl J. Ottenstein and Joe D. Warren",

title="The Program Dependence Graph and Its Use in Optimization",

journal=toplas,

volume=9,

number=3,

month=jul,

year=1987,

pages="319-349"

*}*

[2]

@article{cytron91,

author = "Ron Cytron and Jeanne Ferrante and Barry Rosen

and Mark Wegman and Kenneth Zadeck",

title="Efficiently Computing Static Single Assignment Form and the

Control Dependence Graph",

journal=toplas,

volume=13,

number=4,

month=oct,

year=1991,

pages="451-490"

*}*

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.