Re: Question about the structure of a program dependence graph

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

Return to the comp.compilers page.
Search the comp.compilers archives again.