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: Mon, 06 Jun 2011 10:37:43 +0200 Organization: Karlsruhe Institute of Technology Lines: 88 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <11-06-008@comp.compilers> References: <11-06-002@comp.compilers> <11-06-003@comp.compilers> <11-06-006@comp.compilers> NNTP-Posting-Host: news.iecc.com X-Trace: gal.iecc.com 1307378844 83222 64.57.183.58 (6 Jun 2011 16:47:24 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Mon, 6 Jun 2011 16:47:24 +0000 (UTC) Keywords: analysis Posted-Date: 06 Jun 2011 12:47:24 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:134 Am 05.06.2011 16:22, schrieb Douglas do Couto Teixeira: > Thanks for your answer. I built a small program in C to reproduce your > suggestion. And after converted to SSA form it seems produce a > quadratic number of edges. > #include > > int main(int argc, char** argv) { > int x0 = 0, x1 = 0, x2 = 0, x3 = 0; > > switch(argc) { > case 0: x0 = 2; break; > case 1: x1 = 44; break; > case 2: x2 = 42; break; > case 3: x3 = 67; break; > default: > x0 = x1 = x2 = x3 = -1; break; > } > > printf("%d %d %d %d\n", x0, x1, x2, x3); > > return 0; > } Depends on the compiler, i guess. Google suggests (Non-iterative Range Analysis Algorithm?) that you use clang/LLVM. Our cparser/libFirm constructs a quadratic number of edges, but only a linear number of Phis. You can always convert Phis with N arguments into N-1 Phis with two arguments. The core of your question is, whether one basic block can have N control flow predecessors. You can "desugar" your program like this (considering only x3): x3 = 0 if (case1) then x0 = 2 else if (case2) then x1 = 44 else if (case3) then x2 = 42 else x3' = 67 x3'' = phi(x3,x3') x3''' = phi(x3,x3'') x3'''' = phi(x3,x3''') print(x3'''') Here the program contains some empty basic blocks, where "empty" means containing only Phi and Jmp instructions. Alternatively, the program might look like this: x3 = 0 if (case1) then x0 = 2 else if (case2) then x1 = 44 else if (case3) then x2 = 42 else x3' = 67 x3'' = phi(x3,x3,x3,x3') print(x3'') Instead of empty basic blocks, this variant jumps into the print block immediately. Thus, this basic block has N predecessors. For theory advertisement (i.e. paper writing) you probably should restrict your Phis to two arguments, because then you have a linear number of edges and your algorithm probably has a lower bound in Big-O notation. However, your method to count Phis as instructions is wierd. Unfortunatelly, SSA construction is inherently quadratic, since there are programs that require a quadratic number of Phi instructions. Instead you could show that there cannot be a quadratic number of Phis with a quadratic number of edges, i.e. O(N^4). Effectively, the results reads "quadratic due to SSA", which sounds worse than "linear". -- Andreas Zwinkau Karlsruhe Institute of Technology (KIT) Institut f|r 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  University of the State of Baden-Wuerttemberg and National Research Center of the Helmholtz Association