SSA Versus DU-chains: Is the worst case size really different?

Hello everyone,


A few months ago I had posted a query regarding maximum number of Phi
functions in an SSA program. Many helpful replies were posted, and I
am really thankful to all. My query about number of phi functions
concerns my doubt regarding the worst case sizes of SSA graphs and
DU-chains.


All articles which I referred to (Including Wegman and Zadeck's conditional
constant propagation using SSA and many other technical papers) state that
SSA is better than DU-chains since its worst case as well as practical
size is less than number of DU-chains.


But I am unable understand why - especially the worst case. My confusion
is mostly due to use of different program measures viz. number of basic
blocks, number of statements, number of edges for computing worst case
bound. I feel that both SSA and DU graph would have the same upper bound
on size.


Can someone please give some clues to clarify my confusion? Is there
any reference material that particularly addresses this issue? I would
greatly appreciate any help in this regard.


Thanks and regards,


Ms Bageshri Sathe
Research Scholar,
Dept of Computer Science and Engg.
Indian Institute of Technology, Bombay.

Return to the comp.compilers page.
Search the comp.compilers archives again.