Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #128 > unrolled thread

Question about the structure of a program dependence graph

Back to article view | Back to comp.compilers

Contents

  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

#128 — Question about the structure of a program dependence graph

Dear all,

   Given a program P in SSA form, let its dependence graph G = (V, E)
be a graph with a vertex nv for each variable v in P, and an edge
(na->nb) if b is defined by an instruction that uses a.

   If P is a general program with GOTOs, then it is possible to have a
graph G that is dense, i.e., has O(N^2) edges, where N is the number
of variables in P.

   However, if P contains only IF and WHILE, then it seems that the
number of edges in P will be O(N). Could you tell me if that is the
case? Otherwise, could you provide me a counter example?

   If I add a break with a label, or exceptions, like in Java, then I
am tempted to believe that the number of edges in the dependence graph
is still O(N). Could you tell me if this assumption is wrong?

Example:

Let L be a language with the following instructions:
x = ?; // Variable assignment
x = phi(x0, ..., xn) // phi function
if (?) {...} else {...}
print (x)

Let P be a program in L:

x0 = ?;
if (?) {
 x1 = ?;
}
x2 =phi (x0, x1)
print (x2);

Then P's dependence graph is:
x0 -> x2
x1 -> x2


Thank you very much,

Douglas

[toc] | [next] | [standalone]

#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

[toc] | [prev] | [next] | [standalone]

#132

Dear Andreas,

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. The program is:

#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;
}


Thanks again,

Douglas


On Fri, Jun 3, 2011 at 6:29 AM, Andreas Zwinkau <zwinkau@kit.edu> wrote:
> 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
>

[toc] | [prev] | [next] | [standalone]

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

[toc] | [prev] | [next] | [standalone]

#130

On Tue, 31 May 2011 13:09:58 -0700 (PDT), Douglas do Couto Teixeira
<douglasdocouto@gmail.com> wrote:

>   Given a program P in SSA form, let its dependence graph G = (V, E)
>be a graph with a vertex nv for each variable v in P, and an edge
>(na->nb) if b is defined by an instruction that uses a.
>
>   If P is a general program with GOTOs, then it is possible to have a
>graph G that is dense, i.e., has O(N^2) edges, where N is the number
>of variables in P.

Not exactly.  Recall that a GOTO has a single target label.  There is
no more edge fan-out with GOTO than with a conditional or loop
construct.

>   However, if P contains only IF and WHILE, then it seems that the
>number of edges in P will be O(N). Could you tell me if that is the
>case? Otherwise, could you provide me a counter example?

It will be between O(N) and O(N^2).  Remember that multiple loops may
have the same entry or exit, multiple conditionals may converge, and
as Andreas already has mentioned, case/switch constructs have at least
as many edges as they have cases (remember the default case may not be
explicit and may not change the value).

Additionally, if the language includes pointers to non-local data,
then there will be edges associated with manipulations of both the
pointer and the value.

>   If I add a break with a label, or exceptions, like in Java, then I
>am tempted to believe that the number of edges in the dependence graph
>is still O(N). Could you tell me if this assumption is wrong?

Break is the same as GOTO.   For exceptions the answer depends on the
particular implementation.

George

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web