Re: Question about the structure of a program dependence graph

Andreas Zwinkau <zwinkau@kit.edu>Fri, 03 Jun 2011 11:29:30 +0200

From comp.compilers

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)
| List of all articles for this month |

 From: Andreas Zwinkau Newsgroups: comp.compilers Date: Fri, 03 Jun 2011 11:29:30 +0200 Organization: Karlsruhe Institute of Technology References: 11-06-002 Keywords: analysis Posted-Date: 03 Jun 2011 13:43:19 EDT

Yes, a quadratic number of edges is possible, if you consider "switch".
You just have to desugar it into "if" for your simple language.

// initialize N variables x0..xN with zero
x0_0 = 0;
x1_0 = 0;
x2_0 = 0;
...
xN_0 = 0;
// switch over n cases, each set xn = 1
switch(rand) {
case 0: x0_1 = 1; break;
case 1: x1_1 = 1; break;
case 2: x2_1 = 1; break;
...
case N: xN_1 = 1; break;
}
// print all x
x0_2 = phi(x0_1, x0_0, x0_0, ..., x0_0);
x1_2 = phi(x1_0, x1_1, x1_0, ..., x1_0);
x2_2 = phi(x2_0, x2_0, x2_1, ..., x2_0);
...
xN_2 = phi(xN_0, xN_0, xN_0, ..., xN_1);
print(x0_2);
print(x1_2);
print(x2_2);
...
print(xN_2);

This program has N*3 variables (+1 for "rand") and each phi instruction
introduces N dependencies, because there is one for each control flow
predecessor. For example, the dependees of xi_2 are all xi_0, except one
xi_1. This means N edges for each of the N variables. QED

--
Andreas Zwinkau

Karlsruhe Institute of Technology (KIT)
Institut fuer Programmstrukturen und Datenorganisation (IPD)
Lehrstuhl Prof. Snelting
76131 Karlsruhe

Phone: +49 721 608 48351
Fax: +49 721 608 48457
Email: zwinkau@kit.edu
Web: http://pp.info.uni-karlsruhe.de/person.php?id=107

KIT b University of the State of Baden-Wuerttemberg and
National Research Center of the Helmholtz Association

Post a followup to this message