Mon, 06 Jun 2011 10:37:43 +0200

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: | Andreas Zwinkau <zwinkau@kit.edu> |

Newsgroups: | comp.compilers |

Date: | Mon, 06 Jun 2011 10:37:43 +0200 |

Organization: | Karlsruhe Institute of Technology |

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

Keywords: | analysis |

Posted-Date: | 06 Jun 2011 12:47:24 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.