Time complexity of SSA form

"V.C. SREEDHAR" <sreedhar@bluebeard.cs.mcgill.ca>
Wed, 23 Nov 1994 18:11:08 GMT

          From comp.compilers

Related articles
Time complexity of SSA form sreedhar@bluebeard.cs.mcgill.ca (V.C. SREEDHAR) (1994-11-23)
| List of all articles for this month |

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


I find the following statements in Cytron and Ferrante's paper
regarding complexity analysis that I am not convinced 100%.

Reference is:

  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


Post a followup to this message

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