home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / compiler / 1295 < prev    next >
Encoding:
Text File  |  1992-07-30  |  4.2 KB  |  110 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!think.com!spdcc!iecc!compilers-sender
  3. From: V.C. SREEDHAR <sreedhar@flo.cs.mcgill.ca>
  4. Subject: Summary (def-use chain)
  5. Reply-To: V.C. SREEDHAR <sreedhar@flo.cs.mcgill.ca>
  6. Organization: Compilers Central
  7. Date: Thu, 30 Jul 1992 23:43:34 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-07-116@comp.compilers>
  10. Keywords: optimize, bibliography
  11. References: <92-07-025@comp.compilers>
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 95
  14.  
  15.    Thanks to everyone for responding to my earlier message.  I have
  16. implemented def-use and use-def chain using bit vectors. I have at
  17. presented implemented only for scalar variables.  Basically I followed
  18. Dragon book (for structured programs) with one simple trick. Dragon book
  19. uses reaching definition to obtain ud-chain, and du-chain is handled
  20. similar to live variable analysis (backward analysis). I constructed
  21. def-use and use-def chain using only the reaching definition. I am sure
  22. many of you would do the same in actual implementation.
  23.  
  24. Thanks once again
  25.  
  26. Sreedhar
  27. End Message
  28. ---------
  29. From preston@cs.rice.edu Mon Jul 13 19:07:33 1992
  30.   Recommends SSA form (see below for reference)
  31.  
  32. ---------
  33. From tan@cis.udel.edu Mon Jul 13 00:41:56 1992
  34.  
  35. PS:
  36.  
  37. I am currently using linked-list to do it, which is not very efficient.
  38. Each item takes 32+16 bits (32 bits pointe + 16 bit unsigned short.)
  39. However, using bit vector to represent each line, for a big program, it
  40. probably takes more.
  41.  
  42.  
  43. -----
  44.  
  45. From shirish@mozart.cs.colostate.edu Mon Jul 13 01:52:31 1992
  46.  
  47.         You might find the material presented in "Compilers -
  48. Principles, Techniques and Tools" (a.k.a. "Dragon Book") by Aho, Sethi and
  49. Ullman to be useful( ISBN 0-201-10088-6). Chapter 10 deals with
  50. optimizations. In Section 10.6 an iterative reaching definition and a live
  51. varaiable algorithm are presented. (I am in the process of implementing
  52. these.) Both these algorithms can be implemented using bit vectors. From
  53. there on, deriving the ud and du chains, presumably, should not be a
  54. problem.  The bibliography might help if the book does not.  shirish
  55.  
  56. -----
  57. Reply-To: "Samuel S. Paik" <d65y@crux1.cit.cornell.edu>
  58.  
  59. As I side note, you may want to go to a more powerful representation for
  60. dataflow information, e.g. Program Dependence Graphs, Dependence Flow
  61. Graphs.  They will give your compiler better information.  Also, it turns
  62. out the DPG's also have good space requirements w.r.t. def-use chains.
  63.  
  64. J. Ferrante, K. J. Ottenstein, and J. D. Warren.  The program dependency
  65. graph and its uses in optimization.  ACM Transactions on Programming
  66. Languages and Systems, 9(3):319-349, June 1987.
  67.  
  68. Keshev Pingali, Micah Bech, Richard Johnson, Mayan Moudgill, and Paul
  69. Stodghill.  Dependence Flow Graphs: An algebraic approach to program
  70. dependencies.  In Proceedings of the 18th ACM Symposium on Principles of
  71. Programming Languages, January 1991.
  72.  
  73. A system using DFGs can be ftp-ed from ftp.cs.cornell.edu:pub/cs612
  74.  
  75. Sam Paik
  76.  
  77. From al@kepler.unh.edu Mon Jul 13 17:26:16 1992
  78.  
  79. BTW, you may want to look at the source code for gcc, available from
  80. prep.ai.mit.edu.  I'm interested in whatever else people tell you, though.
  81.  
  82. -----
  83.  
  84. From metaware.com!miker Tue Jul 14 12:43:04 1992
  85.  
  86. In the Apollo optimizer, UD chains are represented as an array of 32 bit
  87. integers, where each 32 bit integer is a bit vector chunk. The sets and
  88. equations are those from the Dragon book. Note that in most programming
  89. languages, you only need to mark definitions and uses on a per statement
  90. basis. Finer granularity wastes memory and greatly decreases efficiency
  91. due to paging. 
  92.  
  93. -----
  94. From jyelon@dante.cs.uiuc.edu Tue Jul 14 14:16:38 1992
  95.  
  96. You may be interested in checking out an article in the 1991 ACM
  97. Transactions on Programming Languages and Systems, which is called
  98. something like "Efficiently Computing the Static Single Assignment Form of
  99. a Control Flow Graph". Essentially, Static Single Assignment form (SSA) is
  100. a relatively new way of representing the same information you put into
  101. DU-UD chains. Many of the compiler people I know find it a lot easier to
  102. deal with and more efficient, to boot.
  103.  
  104. - Josh
  105.  
  106.  
  107. -- 
  108. Send compilers articles to compilers@iecc.cambridge.ma.us or
  109. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  110.