30 Jun 2000 00:52:58 -0400

Related articles |
---|

Algorithm for finding SCC bokhanko@my-deja.com (Andrey Bohanko) (2000-06-30) |

From: | Andrey Bohanko <bokhanko@my-deja.com> |

Newsgroups: | comp.compilers |

Date: | 30 Jun 2000 00:52:58 -0400 |

Organization: | Deja.com - Before you buy. |

Keywords: | theory, question |

Hello!

Everybody knows about classical Tarjan's algorithm for finding SCC's

(strongly connected components) of an arbitrary (both reducible and

irreducible) graph, and its application on many tasks of compiler

development (for example, loop tree construction). It has a very good

complexity (linear; i think nobody can beat it in this regard), but in

practice it's not so good (we need to maintain two stacks with

unpredictable dynamic behavior, and this may be very costly). I know

about Havlak's solution of this problem (Havlak, P., "Nesting of

reducible and irreducible loops", ACM TPLS, 16, 6), but his approach

has it's own deficiencies (we need to determine ancestor/descendant

relation of tree nodes, which in not always affordable). I think there

must be more [practically] feasible solution of this problem. What do

you think about this issue? Do you know other approaches to this

problem?

Thanks for your help!

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.