Re: Post-Dominators & Lengauer/Targan Algorithm

Ian Kaplan <>
3 Apr 2000 11:26:20 -0400

          From comp.compilers

Related articles
Post-Dominators & Lengauer/Targan Algorithm (Rodrigo Augusto Barbato Ferreira) (2000-04-01)
Re: Post-Dominators & Lengauer/Targan Algorithm (Ian Kaplan) (2000-04-03)
| List of all articles for this month |

From: Ian Kaplan <>
Newsgroups: comp.compilers
Date: 3 Apr 2000 11:26:20 -0400
Organization: - Before you buy.
References: 00-04-027
Keywords: analysis

Rodrigo Augusto Barbato Ferreira <>

> How to compute the postdominance relation using the Lengauer/Tarjan
> algorithm for control flow graphs that have no exit. Since a canonical
> exit cannot be created for a no exit control flow graph, is there an
> alternative to do the reverse depth first ordering of it?

    I believe that you can simply add an exit block to the loop.
This is the same as a loop like

      while (loop_cond) {
          .. looop statements

where loop_cond is never false.

    My favorite reference on control flow graph and SSA construction
is Robert Morgan's book "Building an Optimizing Compiler". If
you have not seen this book, I recommend ordering a copy from

    Ian Kaplan

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.