Re: Recognize valid paths

Jeff Kenton <>
Mon, 01 Sep 2008 09:43:48 -0400

          From comp.compilers

Related articles
Recognize valid paths (Tim Frink) (2008-08-20)
Re: Recognize valid paths (2008-08-23)
Re: Recognize valid paths (Hans-Peter Diettrich) (2008-08-24)
Re: Recognize valid paths (Tim Frink) (2008-08-26)
Re: Recognize valid paths (Tim Frink) (2008-08-26)
Re: Recognize valid paths (Michiel Helvensteijn) (2008-08-27)
Re: Recognize valid paths (Jeff Kenton) (2008-09-01)
| List of all articles for this month |

From: Jeff Kenton <>
Newsgroups: comp.compilers
Date: Mon, 01 Sep 2008 09:43:48 -0400
Organization: Compilers Central
References: 08-08-042
Keywords: analysis, optimize
Posted-Date: 01 Sep 2008 17:29:01 EDT

In an otherwise wretched compiler, I saw the use of edge dominators to
solve this type of problem. In the sample code below, after you have
handled the first assignment statement ("x = 1;"), you know that the
edge that got you there had "x < 1" true. Therefore, "x > 10" is false
and you can branch around that path.

Note that you can calculate edge dominators in the same way you do block
dominators, and you can do both calculations at the same time. Note
that, in general, edge dominators form a forest and not a tree as the
block dominators do.


Tim Frink wrote:
> Hi,
> for some static program analyses it is crucial to recognize valid
> paths of the control flow graph taken while executing the code.
> if (x < 1)
> x = 1;
> if (x > 10)
> x = 10;
> For this example code, it's obvious that a path through both
> then-parts of the conditions is not feasible.


= Jeff Kenton =

Post a followup to this message

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