Wed, 23 Nov 1994 18:11:08 GMT

Related articles |
---|

Time complexity of SSA form sreedhar@bluebeard.cs.mcgill.ca (V.C. SREEDHAR) (1994-11-23) |

Newsgroups: | comp.compilers |

From: | "V.C. SREEDHAR" <sreedhar@bluebeard.cs.mcgill.ca> |

Keywords: | analysis, optimize, question |

Organization: | Compilers Central |

Date: | Wed, 23 Nov 1994 18:11:08 GMT |

Hello

I find the following statements in Cytron and Ferrante's paper

regarding complexity analysis that I am not convinced 100%.

Reference is:

@InProceedings{CytronFer93,

Author = "Ron Cytron and Jeanne Ferrante",

Title = "Efficiently Computing $\phi$-nodes on-the-fly",

BookTitle = "Languages and Compilers for Parallel Computing",

year = "1993"

*}*

(In the following "usual algorithm" is one where phi-nodes are computed

by first precomputing the dominance frontiers.)

The authors write:

1. Constructing a single SEG by the usual algorithm takes O(E+N^2) time;

VC> I agree on this

2. Where a data flow problem can be partitioned into V disjoint

frameworks, constructing the associated V SEGs takes O(EV+N^2).

VC>> I am not convinced here. I beleive it should take

VC>> O(E\times V + V \times N^2)

3. If we bound the number of variable references per node by some constant,

then construction of SSA form takes O(EV + N^2) time.

VC>> Again I am not convinced. It should be O(E\times V + V \times N^2)

Thanks a lot

Sreedhar

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.