Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!news.linkpendium.com!news.linkpendium.com!news.snarked.org!newsfeed.news.ucla.edu!usenet.stanford.edu!news.kjsl.com!rahul.net!wasp.rahul.net!rahul.net!news.misty.com!news.iecc.com!nerds-end
From: Douglas do Couto Teixeira <douglasdocouto@gmail.com>
Newsgroups: comp.compilers
Subject: Question about the structure of a program dependence graph
Date: Tue, 31 May 2011 13:09:58 -0700 (PDT)
Organization: Compilers Central
Lines: 44
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <11-06-002@comp.compilers>
NNTP-Posting-Host: news.iecc.com
X-Trace: gal.iecc.com 1307057309 67450 64.57.183.58 (2 Jun 2011 23:28:29 GMT)
X-Complaints-To: abuse@iecc.com
NNTP-Posting-Date: Thu, 2 Jun 2011 23:28:29 +0000 (UTC)
Keywords: analysis, question
Posted-Date: 02 Jun 2011 19:28:29 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Xref: x330-a1.tempe.blueboxinc.net comp.compilers:128

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