Time complexity of SSA form

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
--

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