home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / compiler / 1262 < prev    next >
Encoding:
Internet Message Format  |  1992-07-25  |  8.5 KB

  1. Path: sparky!uunet!olivea!decwrl!decwrl!world!iecc!compilers-sender
  2. From: tarvydas@tsctrl.guild.org (tarvydas)
  3. Newsgroups: comp.compilers
  4. Subject: Re: Intermediate code representations (detailed)
  5. Keywords: Eiffel, design, bibliography
  6. Message-ID: <92-07-083@comp.compilers>
  7. Date: 23 Jul 92 16:51:57 GMT
  8. Sender: compilers-sender@iecc.cambridge.ma.us
  9. Reply-To: tarvydas@tsctrl.guild.org (tarvydas)
  10. Organization: Compilers Central
  11. Lines: 246
  12. Approved: compilers@iecc.cambridge.ma.us
  13.  
  14. I've had great pleasure/success using the ideas of Ric Holt (University of
  15. Toronto) and Jim Cordy (Queen's University, Kingston, Ontario).  I've used
  16. these same ideas in the past to build most of an experimental Eiffel
  17. compiler (a relatively pure OOP language).
  18.  
  19. The nucleus for compiler data type representation can be found in "data
  20. descriptors".  Your semantic analyzer should contain at least 3 "tables"
  21. (semantic domains) - the symbol table, the type table and the scope table.
  22. The job of the semantic analyzer is to connect elements of these tables,
  23. for example a struct:
  24.  
  25.         struct s {
  26.                 int a;
  27.                 char b;
  28.         };
  29.  
  30. would be represented by:
  31.  
  32.         symbol          scope           type
  33.         ======          =====           ====
  34.         s ----------------------------> struct -+
  35.                                                 |
  36.            +------------+++++ <-----------------+
  37.           /  +----------+++++
  38.          /  /
  39.         a ----------------------------> int
  40.          /
  41.         b ----------------------------> char
  42.  
  43.  
  44. You can see that, as this method scales up to handle larger examples,
  45. specific types will be shared by many symbols.  Complex structures, eg.
  46. structs of arrays of structs, just fall into place (eg. imagine that the
  47. "int" entry above happens to be another struct, with links to another
  48. scope and its symbols).
  49.  
  50. Scope entries can be implemented as linked lists, or, as small hash
  51. tables, or, as blocks of integers/pointers which index/point-to entries in
  52. the symbol table.  The set of scopes visible at any point during the
  53. compilation (eg. the global scope, the routine scope and, say, another
  54. nested scope) can be represented by a stack of pointers to little scope
  55. hash tables, or, by a framed stack of indices/pointers-to symbols (ie.
  56. information copied directly from the scope table).
  57.  
  58. As your semantic analysis proceeds, it filters out variables and converts
  59. them to data descriptors, using the information in the tables.  Later
  60. "passes" tweak the data descriptors, eg. the allocator decides where each
  61. piece of data should be allocated and modifies the corresponding data
  62. descriptors to contain this machine specific information.  The coder
  63. "pass" then takes the filtered program and emits code.  The coder can do a
  64. good job, without great complexity, because data descriptors give a
  65. uniform representation of any compile-time object (ie. variables,
  66. parameters, constants, registers, etc).
  67.  
  68. A data descriptor is, roughly:
  69.  
  70.          k
  71.         @ b.d.[x.s]
  72.  
  73. where:
  74.  
  75.  k
  76. @ represents the number of levels of indirection (0 for constants and
  77. registers, 1 for "normal" variables in memory, 2 for variables pointed-to
  78. by pointer variables, etc).
  79.  
  80. B represents the base (null for constants and absolute addresses, a
  81. register, another data descriptor or an abstract lexic base (eg. the
  82. Global Lexic Base, the Lexic Base for the local variables for a certain
  83. routine, etc).
  84.  
  85. D represents the displacement - a numeric displacement from the base,
  86. plus, a set of labels (for representing labelled data, offsets from the
  87. ".data" beginning address (_edata), and branch labels within the program
  88. itself).
  89.  
  90. [X.S] represents and index register plus a scale (the multiplier).
  91.  
  92.  
  93. Here are some simple data descriptor examples:
  94.  
  95. 68k-like operand        data descriptor
  96. ----------------        ---------------
  97.  
  98.                          0
  99. #5  (constant)          @ .null.5    (index is null, so I dropped it)
  100.  
  101.  
  102.                          1
  103. 1234 (absolute addr)    @ .null.1234
  104.  
  105.  
  106.                          0
  107. a4                      @ .a4.0
  108.  
  109.  
  110.                          1
  111. -8(sp)                  @ .sp.-8
  112.  
  113.  
  114.                          2
  115. 0(-8(sp))               @ .sp.-8
  116.  
  117.  
  118.                          1
  119. 8(a4,d1:L)              @ .a4.8.[d1.4]
  120.  
  121.  
  122.                          1
  123. xyz (pc-rel label)      @ .pc.xyz
  124.  
  125.  
  126.                          1
  127. 5-th local within       @ .L92.5
  128. routine #92
  129.  
  130.  
  131. The translation of this notation into a C struct is straight-forward.  In
  132. reality, you need to add a size field and it's sometimes convenient to add
  133. a machine-type field (b/w/l) to help the coder make some of its decisions
  134. more efficiently.
  135.  
  136. You can develop a whole data descriptor algebra which then tells you how
  137. to emit good code.  For example, imagine a local array of words (16 bits),
  138. starting at the -8th byte from the stack pointer.  The array starts at
  139. index 1.  We wish to access element 3.  The data descriptor algebra shows
  140. that a manifest indexing operation can be done without emitting any code:
  141.  
  142.                                    1
  143.         array base (first byte) = @ .sp.-8
  144.  
  145.  
  146.                               0
  147.         index (constant 3) = @ .null.3
  148.  
  149.  
  150.         indexing operation =
  151.  
  152.                 take the address of the array, scale the index to
  153.                 origin 0, multiply the index by its scaling factor (2
  154.                 in this case), add it to the address and promote the
  155.                 result back to being a variable
  156.  
  157.                            1            0           0            0
  158.         = makevar( addrof(@ .sp.-8) + (@ .null.3 - @ .null.1) * @ null.2) )
  159.  
  160.                     -1    0
  161.         = makevar( @   * @ .sp.-8 + ...)
  162.  
  163.                     0
  164.         = makevar( @ .sp.-8 + ...)
  165.  
  166.                            0            0
  167.         = makevar( ... + (@ .null.2) * @ null.2)
  168.  
  169.                            0
  170.         = makevar( ... + (@ .null.4))
  171.  
  172.                     0          0
  173.         = makevar( @ .sp.-8 + @ .null.4 )
  174.  
  175.                     0
  176.         = makevar( @ .sp.(-8+4) )
  177.  
  178.                     0
  179.         = makevar( @ .sp.-4 )
  180.  
  181.            1    0
  182.         = @  * @ .sp.-4
  183.  
  184.            1
  185.         = @ .sp.-4
  186.  
  187.         = -4(sp).
  188.  
  189.  
  190. We've just watched an automatable compile-time calculation of an indexing
  191. operation which didn't emit any code.  The resulting operand, -4(sp), goes
  192. on to be used in further operations and will be emitted as necessary - the
  193. whole array indexing operation was subsumed, at compile time, into a
  194. single operand.  It should be obvious that variable (non-manifest) indices
  195. can't be folded exactly this way, but, for example, they could be folded
  196. into the index field of the data descriptor (the code emitted might be:
  197. "move.l var,d2" and the
  198.                                     1
  199. resulting data descriptor might be @ .sp.-8.[d2.2], which still emits the
  200. least amount of code possible for this situation (I'm just trying to make
  201. a point - if you think that a better code sequence is possible, you're
  202. welcome to twist the decision trees :-)). 
  203.  
  204. What I've just shown are, literally, some of the steps that the OCG
  205. technology takes when optimizing code - address mode arithmetic becomes a
  206. no-brainer and can be relegated to just a few OCG decision trees when data
  207. descriptors are used.
  208.  
  209.  
  210. Your intermediate code problem can be solved by looking at the operations
  211. which the Orthogonal Code Generator can accept.  The operations use data
  212. descriptors as operands - you can interpret the result if you wish, and,
  213. you can use the OCG to compile the operations into locally good code.
  214.  
  215. Rosselet's paper on PT Pascal, although old and applied to compiling a
  216. boring language, is an excellent learning tool in that it has pictures of
  217. these data structures and has the S/SL source code for the whole compiler
  218. (you have to get S/SL via anonymous ftp and you have to write the simple
  219. S/SL mechanisms yourself in C or something).  PT's coder predates OCG, but
  220. still demonstrates the evolutionary path which spawned the OCG.
  221.  
  222. Paul Tarvydas
  223. TS Controls
  224. tarvydas@tsctrl.guild.org
  225.  
  226.  
  227.  
  228. R. C. Holt
  229. Data Descriptors: A Compile-Time Model of Data and Addressing
  230. ACM Transactions on Programming Languages and Systems.
  231. Volume 9.
  232. pages 367-389.
  233. July 1987.
  234.  
  235.  
  236. Code Generation Using an Orthogonal Model
  237. Cordy, Holt
  238. Software Practice and Experience
  239. Volume 20 (3)
  240. March 1990
  241. pages 301-320
  242.  
  243.  
  244. An Orthogonal Model for Code Generation
  245. Technical Report CSRI-177.
  246. Computer Systems Research Institute.
  247. University of Toronto.
  248. January 1986.
  249.  
  250.  
  251. PT: A Pascal Subset
  252. Alan Rosselet
  253. Tech Report CSRG-119
  254. University of Toronto
  255. September 1980
  256.  
  257. -- 
  258. Send compilers articles to compilers@iecc.cambridge.ma.us or
  259. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  260.