Groups | Search | Server Info | Login | Register

Groups > comp.compilers > #134

Re: Question about the structure of a program dependence graph

Show key headers only | View raw

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<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.

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

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Question about the structure of a program dependence graph Douglas do Couto Teixeira <douglasdocouto@gmail.com> - 2011-05-31 13:09 -0700
  Re: Question about the structure of a program dependence graph Andreas Zwinkau <zwinkau@kit.edu> - 2011-06-03 11:29 +0200
    Re: Question about the structure of a program dependence graph Douglas do Couto Teixeira <douglasdocouto@gmail.com> - 2011-06-05 11:22 -0300
      Re: Question about the structure of a program dependence graph Andreas Zwinkau <zwinkau@kit.edu> - 2011-06-06 10:37 +0200
  Re: Question about the structure of a program dependence graph George Neuner <gneuner2@comcast.net> - 2011-06-03 18:56 -0400

csiph-web