# Re: Recognize valid paths

## Jeff Kenton <jeffrey.kenton@comcast.net>Mon, 01 Sep 2008 09:43:48 -0400

From comp.compilers

Related articles
Recognize valid paths plfriko@yahoo.de (Tim Frink) (2008-08-20)
Re: Recognize valid paths m.helvensteijn@gmail.com (2008-08-23)
Re: Recognize valid paths DrDiettrich1@aol.com (Hans-Peter Diettrich) (2008-08-24)
Re: Recognize valid paths plfriko@yahoo.de (Tim Frink) (2008-08-26)
Re: Recognize valid paths plfriko@yahoo.de (Tim Frink) (2008-08-26)
Re: Recognize valid paths m.helvensteijn@gmail.com (Michiel Helvensteijn) (2008-08-27)
Re: Recognize valid paths jeffrey.kenton@comcast.net (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.

jeff

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 http://home.comcast.net/~jeffrey.kenton =
---------------------------------------------------------------------

Post a followup to this message