Question about the structure of a program dependence graph

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

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