Tue, 31 May 2011 13:09:58 -0700 (PDT)

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: | Douglas do Couto Teixeira <douglasdocouto@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Tue, 31 May 2011 13:09:58 -0700 (PDT) |

Organization: | Compilers Central |

Keywords: | analysis, question |

Posted-Date: | 02 Jun 2011 19:28:29 EDT |

Dear all,

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.

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?

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?

Example:

Let L be a language with the following instructions:

x = ?; // Variable assignment

x = phi(x0, ..., xn) // phi function

if (?) {...} else {...}

print (x)

Let P be a program in L:

x0 = ?;

if (?) {

x1 = ?;

*}*

x2 =phi (x0, x1)

print (x2);

Then P's dependence graph is:

x0 -> x2

x1 -> x2

Thank you very much,

Douglas

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.