Re: question on control dependence

preston@dawn.cs.rice.edu (Preston Briggs) writes:
>McConnel's algorithm will require at least O(N^2) time (consider the bit
>vectors to be initialized). On the other hand, I believe it only requires
>O(N^2) time worst-case. Therefore, worst case, the algorithms are the
>same. Best case (and probably expected case , Cytron et al. are faster,
>though perhaps only for very large N.


        It depends on how you define "worst case". In terms of the time
and space required per control dependence, the newer Cytron et al.
algorithm (and I think the older one as well) can beat McConnel's
method by a linear factor.


* When the number of control dependences is O(N), McConnel's
algorithm is quadratic in its output -- O(|CD|^2). It
is linear in its output only when |CD| is O(N^2).


* The newer Cytron et al. algorithm is always linear in its
output -- O(|CD|). This is particularly important
because |CD| is much more often O(N) than O(N^2).


        I believe the newer Cytron et al. algorithm to be as fast as
theoretically possible. Once you've built the predominator tree, it
requires very few (less than a dozen?) instructions to find each control
dependence relation.


Note: The newer Cytron et al. algorithm, which amounts to reading control
dependences off the postdominator tree, appeared in Cytron, Ferrante and
Sarkar's SIGPLAN '90 paper. However, the method was also described
briefly in Ferrante, Ottenstein and Warren's July 1987 TOPLAS paper
(although without handling of labels).
--
Paul Havlak Dept. of Computer Science
Graduate Student Rice University, Houston TX 77251-1892
PFC/ParaScope projects (713) 527-8101 x2738 paco@cs.rice.edu
--

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