home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / compiler / 2038 < prev    next >
Encoding:
Text File  |  1992-12-15  |  2.4 KB  |  59 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!world!iecc!compilers-sender
  3. From: preston@dawn.cs.rice.edu (Preston Briggs)
  4. Subject: Re: question on control dependence
  5. Reply-To: preston@dawn.cs.rice.edu (Preston Briggs)
  6. Organization: Rice University, Houston
  7. Date: Tue, 15 Dec 1992 18:58:20 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-12-070@comp.compilers>
  10. References: <92-12-056@comp.compilers> <92-12-065@comp.compilers>
  11. Keywords: design
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 44
  14.  
  15. mcconnel@newta1.cs.uiuc.edu writes:
  16. >I've come up with a simple algorithm for computing control dependences,
  17.  
  18. >2.  Assume that each node in the flow graph has no more than 2 successors,
  19. >and that if a node does have 2 successors, one is the "true" successor and
  20. >the other the "false" successor.  For a given flow node X, let CD(X)
  21. >denote the nodes that are control dependent on X.  If X has fewer than 2
  22. >successors, CD(X) is empty.  Otherwise, we can find CD(X) as follows:
  23. >    CD(X) = P(X-true) ^ P(X-false)
  24. >where X-true and X-false are respectively the true and false successors,
  25. >and "^" denotes symmetric difference (i.e., A ^ B = (A | B) - (A & B)).
  26.  
  27. The general case of more than 2 succesoors is handled like this...
  28.  
  29.     CD(X) = union(P(S)) - intersection(P(S)), for S in successors(X)
  30.  
  31. (This is a much simpler version of another answer I posted earlier)
  32.  
  33. cliffc@rice.edu (Cliff Click) writes:
  34. >3) Your problem is 1-bounded; a single pass over the graph is
  35. >sufficient.
  36.  
  37. Only for part 2.  For part 1 (computing post dominance), more than 1
  38. pass may be required.
  39.  
  40. >4) Your problem requires O(N) bit-vectors, or
  41. >   O(N^2) COMMON CASE but with a small constant.
  42.  
  43. That is, O(N^2) space, where N is the number of basic blocks.
  44.  
  45. >5) The authors in Cytron et al. claim O(N) in practice, although they admit
  46. >   to O(N^2) in the worst case.  Their algorithm will surely run with a 
  47. >   larger constant than yours.
  48.  
  49. McConnel's algorithm will require at least O(N^2) time (consider the bit
  50. vectors to be initialized).  On the other hand, I believe it only requires
  51. O(N^2) time worst-case.  Therefore, worst case, the algorithms are the
  52. same.  Best case (and probably expected case , Cytron et al. are faster,
  53. though perhaps only for very large N.
  54.  
  55. Preston Briggs
  56. -- 
  57. Send compilers articles to compilers@iecc.cambridge.ma.us or
  58. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  59.