home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / compiler / 2045 < prev    next >
Encoding:
Text File  |  1992-12-17  |  2.3 KB  |  52 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!world!iecc!compilers-sender
  3. From: paco@cs.rice.edu (Paul Havlak)
  4. Subject: Re: question on control dependence
  5. Reply-To: paco@cs.rice.edu (Paul Havlak)
  6. Organization: Center for Research on Parallel Computation
  7. Date: Wed, 16 Dec 1992 17:08:33 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-12-077@comp.compilers>
  10. Keywords: optimize, analysis
  11. References: <92-12-056@comp.compilers> <92-12-070@comp.compilers>
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 37
  14.  
  15. preston@dawn.cs.rice.edu (Preston Briggs) writes:
  16. >McConnel's algorithm will require at least O(N^2) time (consider the bit
  17. >vectors to be initialized).  On the other hand, I believe it only requires
  18. >O(N^2) time worst-case.  Therefore, worst case, the algorithms are the
  19. >same.  Best case (and probably expected case , Cytron et al. are faster,
  20. >though perhaps only for very large N.
  21.  
  22.     It depends on how you define "worst case".  In terms of the time
  23. and space required per control dependence, the newer Cytron et al.
  24. algorithm (and I think the older one as well) can beat McConnel's
  25. method by a linear factor.
  26.  
  27.     * When the number of control dependences is O(N), McConnel's
  28.         algorithm is quadratic in its output -- O(|CD|^2).  It
  29.         is linear in its output only when |CD| is O(N^2).
  30.  
  31.     * The newer Cytron et al. algorithm is always linear in its
  32.         output -- O(|CD|).  This is particularly important
  33.         because |CD| is much more often O(N) than O(N^2).
  34.  
  35.     I believe the newer Cytron et al. algorithm to be as fast as
  36. theoretically possible.  Once you've built the predominator tree, it
  37. requires very few (less than a dozen?) instructions to find each control
  38. dependence relation.
  39.  
  40. Note: The newer Cytron et al. algorithm, which amounts to reading control
  41. dependences off the postdominator tree, appeared in Cytron, Ferrante and
  42. Sarkar's SIGPLAN '90 paper.  However, the method was also described
  43. briefly in Ferrante, Ottenstein and Warren's July 1987 TOPLAS paper
  44. (although without handling of labels).
  45. --
  46. Paul Havlak            Dept. of Computer Science
  47. Graduate Student        Rice University, Houston TX 77251-1892
  48. PFC/ParaScope projects        (713) 527-8101 x2738     paco@cs.rice.edu
  49. -- 
  50. Send compilers articles to compilers@iecc.cambridge.ma.us or
  51. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  52.