Fri, 03 Jun 2011 18:56:11 -0400

Related articles |
---|

Question about the structure of a program dependence graph douglasdocouto@gmail.com (Douglas do Couto Teixeira) (2011-05-31) |

Re: Question about the structure of a program dependence graph zwinkau@kit.edu (Andreas Zwinkau) (2011-06-03) |

Re: Question about the structure of a program dependence graph gneuner2@comcast.net (George Neuner) (2011-06-03) |

Re: Question about the structure of a program dependence graph douglasdocouto@gmail.com (Douglas do Couto Teixeira) (2011-06-05) |

Re: Question about the structure of a program dependence graph zwinkau@kit.edu (Andreas Zwinkau) (2011-06-06) |

From: | George Neuner <gneuner2@comcast.net> |

Newsgroups: | comp.compilers |

Date: | Fri, 03 Jun 2011 18:56:11 -0400 |

Organization: | A noiseless patient Spider |

References: | 11-06-002 |

Keywords: | analysis |

Posted-Date: | 05 Jun 2011 09:45:26 EDT |

On Tue, 31 May 2011 13:09:58 -0700 (PDT), Douglas do Couto Teixeira

<douglasdocouto@gmail.com> wrote:

*> Given a program P in SSA form, let its dependence graph G = (V, E)*

*>be a graph with a vertex nv for each variable v in P, and an edge*

*>(na->nb) if b is defined by an instruction that uses a.*

*>*

*> If P is a general program with GOTOs, then it is possible to have a*

*>graph G that is dense, i.e., has O(N^2) edges, where N is the number*

*>of variables in P.*

Not exactly. Recall that a GOTO has a single target label. There is

no more edge fan-out with GOTO than with a conditional or loop

construct.

*> However, if P contains only IF and WHILE, then it seems that the*

*>number of edges in P will be O(N). Could you tell me if that is the*

*>case? Otherwise, could you provide me a counter example?*

It will be between O(N) and O(N^2). Remember that multiple loops may

have the same entry or exit, multiple conditionals may converge, and

as Andreas already has mentioned, case/switch constructs have at least

as many edges as they have cases (remember the default case may not be

explicit and may not change the value).

Additionally, if the language includes pointers to non-local data,

then there will be edges associated with manipulations of both the

pointer and the value.

*> If I add a break with a label, or exceptions, like in Java, then I*

*>am tempted to believe that the number of edges in the dependence graph*

*>is still O(N). Could you tell me if this assumption is wrong?*

Break is the same as GOTO. For exceptions the answer depends on the

particular implementation.

George

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.