Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.com!border1.nntp.dca.giganews.com!border4.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!novia!news-out.readnews.com!news-xxxfer.readnews.com!news.misty.com!news.iecc.com!nerds-end From: Andreas Zwinkau Newsgroups: comp.compilers Subject: Re: Question about the structure of a program dependence graph Date: Fri, 03 Jun 2011 11:29:30 +0200 Organization: Karlsruhe Institute of Technology Lines: 51 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <11-06-003@comp.compilers> References: <11-06-002@comp.compilers> NNTP-Posting-Host: news.iecc.com X-Trace: gal.iecc.com 1307122999 60282 64.57.183.58 (3 Jun 2011 17:43:19 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Fri, 3 Jun 2011 17:43:19 +0000 (UTC) Keywords: analysis Posted-Date: 03 Jun 2011 13:43:19 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:129 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 Adenauerring 20a 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