Tuesday, June 10, 2008

Worst case Number of Phi Nodes in a SSA graph

Q. What is the worst case number of phi functions in a SSA graph ?

It could be O(N^2). Consider this program:

while (...)
{
while (...)
{
while (...)
{
i = ...
}
i = ...
}
i = ...
}
... = i

A minimal phi insertion (confirm this !) has 5 phi nodes. This is around (N/2). For V variables, number of phi functions would be (N/2)*V or around O(N^2) phi functions.

i0 = ...
while (...)
{
i1 = phi(i0, i7)
while (...)
{
i2 = phi(i1, i5)
while (...)
{
i3 = i2;
}
i4 = phi(i3,i2)
i5 = i4
}
i6 = phi(i4, i1)
i7 = i6
}
i8 = phi(i7, i0)

There is some interesting discussion on this in comp.compilers here

Labels: ,

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home