|Time complexity of SSA form email@example.com (V.C. SREEDHAR) (1994-11-23)|
|From:||"V.C. SREEDHAR" <firstname.lastname@example.org>|
|Keywords:||analysis, optimize, question|
|Date:||Wed, 23 Nov 1994 18:11:08 GMT|
I find the following statements in Cytron and Ferrante's paper
regarding complexity analysis that I am not convinced 100%.
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
Return to the
Search the comp.compilers archives again.