home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / compiler / 2035 < prev    next >
Encoding:
Internet Message Format  |  1992-12-15  |  2.0 KB
  1. Path: sparky!uunet!olivea!spool.mu.edu!uwm.edu!ogicse!das-news.harvard.edu!spdcc!iecc!compilers-sender
  2. From: cliffc@rice.edu (Cliff Click)
  3. Newsgroups: comp.compilers
  4. Subject: Re: question on control dependence
  5. Keywords: optimize
  6. Message-ID: <92-12-067@comp.compilers>
  7. Date: 15 Dec 92 16:24:51 GMT
  8. References: <92-12-056@comp.compilers> <92-12-065@comp.compilers>
  9. Sender: compilers-sender@iecc.cambridge.ma.us
  10. Reply-To: cliffc@rice.edu (Cliff Click)
  11. Organization: Center for Research on Parallel Computations
  12. Lines: 38
  13. Approved: compilers@iecc.cambridge.ma.us
  14.  
  15. mcconnel@newta1.cs.uiuc.edu writes:
  16.  
  17. > I've come up with a simple algorithm for computing control dependences,
  18. > and I was wondering if it was already known; I haven't seen it in the
  19. > literature.  My algorithm uses straightforward data flow analysis, and
  20. > works like so:
  21.  
  22. I am not the world's most knowledgeable dataflow expert, so Caveat Emptor!
  23. With the disclaimer out of the way, here goes:
  24.  
  25. 1) Your MEET operator is set intersection ("&").
  26. 2) Your transfer function for node Z is: f(x) = Z | x.
  27.    (The "x" here is the MEET over the inputs.)
  28. 3) Your problem is 1-bounded; a single pass over the graph is sufficient.
  29. 4) Your problem requires O(N) bit-vectors, or
  30.    O(N^2) COMMON CASE but with a small constant.
  31.  
  32. 5) The authors in Cytron et al. claim O(N) in practice, although they admit
  33.    to O(N^2) in the worst case.  Their algorithm will surely run with a 
  34.    larger constant than yours.  I have implemented a variation of [2]
  35.    and seen it run "fast enough" for my research compiler.
  36.  
  37. 6) You don't say how to handle indirect jumps. 
  38.    Real compilers gotta deal with this case.
  39.  
  40. 7) With all that said, your algorithm is intuitive to me.
  41.  
  42.  
  43. > My question is, has this algorithm been proposed before?  
  44. > (It seems too simple not to have been.)
  45.  
  46. I've not seen it before.
  47.  
  48. Cliff
  49. cliffc@cs.rice.edu
  50. -- 
  51. Send compilers articles to compilers@iecc.cambridge.ma.us or
  52. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  53.