# Re: Question about the structure of a program dependence graph

## Andreas Zwinkau <zwinkau@kit.edu>Mon, 06 Jun 2011 10:37:43 +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: Mon, 06 Jun 2011 10:37:43 +0200 Organization: Karlsruhe Institute of Technology References: 11-06-002 11-06-003 11-06-006 Keywords: analysis Posted-Date: 06 Jun 2011 12:47:24 EDT

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

> #include<stdio.h>
>
> 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.

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

--
Andreas Zwinkau

Karlsruhe Institute of Technology (KIT)
Institut f|r 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  University of the State of Baden-Wuerttemberg and
National Research Center of the Helmholtz Association

Post a followup to this message