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-xfer.nntp.sonic.net!rahul.net!wasp.rahul.net!rahul.net!news.misty.com!news.iecc.com!nerds-end
From: Douglas do Couto Teixeira <douglasdocouto@gmail.com>
Newsgroups: comp.compilers
Subject: Re: Question about the structure of a program dependence graph
Date: Sun, 5 Jun 2011 11:22:51 -0300
Organization: Compilers Central
Lines: 66
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <11-06-006@comp.compilers>
References: <11-06-002@comp.compilers> <11-06-003@comp.compilers>
NNTP-Posting-Host: news.iecc.com
X-Trace: gal.iecc.com 1307378736 82263 64.57.183.58 (6 Jun 2011 16:45:36 GMT)
X-Complaints-To: abuse@iecc.com
NNTP-Posting-Date: Mon, 6 Jun 2011 16:45:36 +0000 (UTC)
Keywords: analysis
Posted-Date: 06 Jun 2011 12:45:36 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: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
>