Sun, 5 Jun 2011 11:22:51 -0300

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

From: | Douglas do Couto Teixeira <douglasdocouto@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Sun, 5 Jun 2011 11:22:51 -0300 |

Organization: | Compilers Central |

References: | 11-06-002 11-06-003 |

Keywords: | analysis |

Posted-Date: | 06 Jun 2011 12:45:36 EDT |

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*

*>*

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.