Tue, 15 Dec 1992 19:13:56 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) |

Re: question on control dependence dkchen@sp91.csrd.uiuc.edu (1992-12-16) |

Newsgroups: | comp.compilers |

From: | Paul Havlak <paco@cs.rice.edu> |

Organization: | Center for Research on Parallel Computation |

Date: | Tue, 15 Dec 1992 19:13:56 GMT |

Keywords: | optimize, design, bibliography |

References: | 92-12-056 92-12-065 |

mcconnel@newta1.cs.uiuc.edu writes:

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

Looks to me like the algorithm should work. I dislike it anyway

for two reasons:

* It's not very general; many languages allow more than two

branches out of a node.

* It uses bit vectors. Sure, you only require O(N) bit-vector

steps for N nodes, but the bit vectors are O(N) long,

so you're always paying O(N^2) time and space.

My favorite algorithm for control dependence calculation is in [3].

It requires no data structures besides the control-flow graph and the

postdominator tree, as input, and the control dependence graph, as output.

The algorithm takes time linear in the number of control dependences,

which is usually linear in the number of nodes.

First, build the postdominator tree using the method of [4]

(almost-linear) or [5] (linear). Then to enumerate the set CD(X, L) [the

control dependence successors of a node X with label L], do the following:

* CD(X, L) = {}

* Assign Y = the sink of X's control-flow outedge with label L

* While (Y != immediate postdominator of X)

CD(X, L) += Y

Assign Y = immediate postdominator of Y

(where += denotes addition of member to set)

Note that this method can also be used in the construction of SSA form;

see [3] for details.

References:

[3]

@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}}

[4]

@Article{LeTa:Dom,

Author = {T. Lengauer and R. E. Tarjan},

Title = {A fast algorithm for Finding Dominators in a flowgraph},

Journal = TOPLAS,

Volume = 1,

Pages = {121--141},

Year = 1979}

Actually, [3] cites another method for building the postdominator

tree which, I just realize, I've never looked up:

[5]

@inproceedings{Harel:Dom,

Author = {Dov Harel},

Title = {A linear-time algorithm for finding dominators in

flow graphs and related problems},

BookTitle = {Symposium on Theory of Computing},

Month = May,

Year = {1985}}

--

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.