home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / compiler / 1903 < prev    next >
Encoding:
Text File  |  1992-11-18  |  2.4 KB  |  68 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!think.com!spdcc!iecc!compilers-sender
  3. From: cheryl@gallant.apple.com (Cheryl Lins)
  4. Subject: Re: And speaking of fast compilers...
  5. Reply-To: cheryl@gallant.apple.com (Cheryl Lins)
  6. Organization: Apple Computer Inc, Cupertino, CA
  7. Date: Tue, 17 Nov 1992 17:35:48 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-11-094@comp.compilers>
  10. Summary: constant prop. and range value prop.
  11. Keywords: performance, Ada, design, bibliography
  12. References: <92-11-057@comp.compilers> <92-11-084@comp.compilers>
  13. Sender: compilers-sender@iecc.cambridge.ma.us
  14. Lines: 52
  15.  
  16. sasdrf@unx.sas.com (Dave Frederick) writes:
  17. >Most of the optimizations an Ada compiler performs are compile-time range
  18. >and bounds checking. [other comments deleted]
  19. >When performing such tests for all ranges, subranges, and array
  20. >indices, one can see how an explosion in compile time can occur.
  21.  
  22. Range and bounds checking are variations on the constant propagation
  23. problem.  If memory serves, this is doable in time linear to the number of
  24. variables.  See [1] for how global constant propagation can be done
  25. efficiently.
  26.  
  27. >One of the hot topics when I last worked on an Ada compiler was doing the
  28. >above range and bounds checking optimization across procedures in a
  29. >package. Interprocedural analysis is quite helpful for determining the
  30. >possibility of these errors on var parameters. 
  31.  
  32. So presumably, you were also doing interprocedural alias analysis. I'm
  33. curious about the algorithms used for this. Did you implement those of [2]
  34. (for alias analysis)?
  35.  
  36. The same algorithms for value propagation mentioned above. In the inter-
  37. procedural case, you may have a paritally constructed lattice with some
  38. known values or ranges for some of the variables.
  39.  
  40. References
  41. [1]
  42. @inproceedings{cooper:89a,
  43.     author        = "Keith D. Cooper and Ken Kennedy",
  44.     title        = "Fast interprocedural alias analysis",
  45.     booktitle    = popl89,
  46.     pages        = "49--59",
  47.     address        = "Austin, TX",
  48.     month        = jan,
  49.     year        = 1989}
  50.  
  51. [2]
  52. @article{wegman:91,
  53.     author        = "Mark N. Wegman and F. Kenneth Zadeck",
  54.     title        = "Constant propagation with conditional branches",
  55.     journal        = toplas,
  56.     volume        = 13,
  57.     number        = 2,
  58.     pages        = "181--210",
  59.     month        = apr,
  60.     year        = 1991}
  61.  
  62.  
  63. -- 
  64. Cheryl Lins  Oberon Paladin  lins@apple.com
  65. -- 
  66. Send compilers articles to compilers@iecc.cambridge.ma.us or
  67. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  68.