txt1 9.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215
  1. .\" Introduction
  2. .\"
  3. .\" $Id$
  4. .NH
  5. INTRODUCTION.
  6. .PP
  7. This document describes an EM interpreter which does extensive checking.
  8. The interpreter exists in two versions: the normal version with full checking
  9. and debugging facilities, and a fast stripped version that does interpretation
  10. only.
  11. This document assumes that the full version is used.
  12. .LP
  13. First the virtual EM machine embodied by the interpreter (called \fBint\fP) is
  14. described, followed by some remarks on performance.
  15. The second section gives some specific implementation decisions.
  16. Section three explains the usage of the built-in debugging tool.
  17. .LP
  18. Appendix A gives an overview of the various warnings \fBint\fP gives,
  19. with possible causes and solutions.
  20. Appendix B is a simple tutorial on the use of \fBint\fP.
  21. A separate manual page exists.
  22. .PP
  23. The document assumes a good understanding of what EM is and what
  24. the assembly code looks like [1].
  25. Notions like 'procedure descriptor', 'mini', 'shortie' etc. are not
  26. explained.
  27. In the sequel, any word in \fIthis font\fP refers to the name of a
  28. variable, constant, function or whatever, used in the source code under
  29. the same name.
  30. .LP
  31. To avoid confusion: \fBint\fP interprets EM machine language (e.out files),
  32. \fInot\fP the assembly language (.e files) and \fInot\fP the compact
  33. code (.k files).
  34. .NH 2
  35. The virtual EM machine.
  36. .PP
  37. The memory layout of the virtual EM machine represented by the interpreter
  38. differs in details from the description in [1].
  39. Virtual memory is split up into two separate spaces:
  40. one space containing the instructions,
  41. the other all the data, including stack and heap (D-space).
  42. The procedure descriptors are preprocessed and stored in a separate array,
  43. \fIproctab[]\fP.
  44. Both spaces start off at address 0.
  45. This is possible because pointers in the two different spaces are
  46. distinguishable by context (and shadow-bytes: see 2.6).
  47. .NH 3
  48. Instruction Space
  49. .PP
  50. Figure 1 shows the I-space, together with the position of some important
  51. EM registers.
  52. .Dr 12
  53. NEXT --> |________________| <-- DB \e
  54. | | |
  55. | | | T
  56. | | <-- PC |
  57. | Program | | e
  58. | | |
  59. | Text | | x
  60. | | |
  61. | | | t
  62. 0 --> |________________| <--(PB) /
  63. .Df
  64. \fI Fig 1. Virtual instruction space (I-space).\fP
  65. .De
  66. .PP
  67. The I-space is just big enough to contain all the instructions.
  68. The size needed for the program text (\fINTEXT\fP) is found from the
  69. header-bytes of the loadfile.
  70. Legal values for the program counter (\fIPC\fP) consist of all
  71. addresses in the range from 0 through \fINTEXT\fP \- 1.
  72. If the \fIPC\fP is made to point to an illegal address, a trap will occur.
  73. .NH 3
  74. The Procedure Table
  75. .PP
  76. The \fINProc\fP constant indicates how many procedure descriptors there
  77. are in the proctab array.
  78. Elements of this array contain for each procedure: the number of locals, the
  79. entry point and the entry point of the textually following procedure. This is
  80. used in testing the restriction that the program counter may not wander from
  81. procedure to procedure.
  82. .NH 3
  83. The Data Space
  84. .PP
  85. Figure 2 shows the layout of the data space, which closely conforms to the EM
  86. Manual.
  87. .Dr 36
  88. __________________
  89. maxaddr(psize) --> | | <-- ML \e
  90. | | | S
  91. | Locals | | t
  92. | & | | a
  93. | RSBs | | c
  94. | | | k
  95. |________________| <-- SP /
  96. . .
  97. . .
  98. . Unused .
  99. . .
  100. . .
  101. . .
  102. . .
  103. . .
  104. . Unused .
  105. . .
  106. . .
  107. |________________| <-- HP
  108. | | \e
  109. | Heap | |
  110. |________________| <-- HB |
  111. | | | D
  112. | Arguments | |
  113. | Environ | | a
  114. | _ _ _ _ | |
  115. | | | t
  116. | | |
  117. | | | a
  118. | Global data | |
  119. | | |
  120. | | |
  121. 0 --> |________________| <--(EB) /
  122. .Df
  123. \fI Fig 2. Virtual dataspace (D-space).\fP
  124. .De
  125. .PP
  126. D-space begins at address 0, and ends at the largest address
  127. representable by the pointer size (\fIpsize\fP) being used;
  128. for a 2-byte pointer size this maximum address is
  129. .DS
  130. ((2 ^ 16 \- 1) / word size * word size) \- 1
  131. .DE
  132. for a 4-byte pointer size it is
  133. .DS
  134. ((2 ^ 31 \- 1) / word size * word size) \- 1
  135. .DE
  136. (not 2 ^ 32, to allow illegal pointers to be implemented in the future). The
  137. funny rounding construction is required to make ML+1 expressible as the
  138. initialisation value of LB and SP.
  139. .PP
  140. D-space is split into two partitions: Data and Stack (indicated by the
  141. brackets).
  142. The Data partition holds the global data area (GDA) and the heap.
  143. Its initial size is given by the loadfile constant SZDATA.
  144. Some space is added to it, because arguments and environment are
  145. stored here also.
  146. This total size is static while interpreting.
  147. However, as the heap may grow during execution (e.g. caused by dynamic
  148. allocation) this results in a variable size for the Data partition.
  149. Initially, the size for the Data partition is the sum of the space needed
  150. by the GDA (including the space needed for arguments and environment) and
  151. the initial heapspace.
  152. The lowest legal Data address is 0; the highest \fIHP\fP \- 1.
  153. .LP
  154. The Stack partition holds the stack.
  155. It begins at the highest available D-space address, and grows
  156. towards the low addresses, so the Stack partition is of variable size too.
  157. The lowest legal Stack address is the stackpointer (\fISP\fP),
  158. the highest is the memory limit (\fIML\fP).
  159. .NH 2
  160. Physical lay-out
  161. .PP
  162. Each partition is mapped onto a piece of physical memory with the
  163. same name: \fItext\fP (fig. 1), \fIstack\fP and \fIdata\fP (fig. 2).
  164. These are the storage structures which \fBint\fP uses to physically
  165. store the contents of the virtual EM spaces.
  166. Figure 2 thus shows the mapping of D-space onto two
  167. different physical parts: \fIstack\fP and \fIdata\fP.
  168. The I-space is represented by one physical part: \fItext\fP.
  169. .LP
  170. Each time more space is needed, the actual partition is reallocated,
  171. with the new size being computed with the formula:
  172. .DS
  173. \fInew size\fP = 1.5 \(mu (\fIold size\fP + \fIextra\fP)
  174. .DE
  175. \fIextra\fP is the number of bytes exceeding the \fIold size\fP.
  176. One can prove that using this method, there is a
  177. linear relationship between allocation time and needed partition size.
  178. .PP
  179. A virtual D-space starting at address 0 is in correspondence with
  180. the definition in [1], p. 3\-6.
  181. The main reason for having D-space start at address 0, is that it induces
  182. a one-one correspondence between the heap \- and GDA
  183. addresses on the virtual machine (and hence the definition) on one hand,
  184. and the offset within the \fIdata\fP partition on the other.
  185. This implies that no extra calculation is needed to perform load and
  186. storage operations.
  187. .LP
  188. Some calculation however cannot be avoided, because the stack part of
  189. the D-space grows downwards by EM definition.
  190. The first address of the virtual stack (\fIML\fP, the maximum address for
  191. the given \fIpsize\fP) is mapped onto the
  192. beginning of the \fIstack\fP partition.
  193. When the stack grows (i.e. EM addresses get lower), the offset within the
  194. \fIstack\fP partition gets higher.
  195. By taking offset \fIML \- A\fP in the stack partition, one obtains the
  196. physical address corresponding to some virtual EM (stack) address \fIA\fP.
  197. .NH 2
  198. Speed.
  199. .PP
  200. From several test results with both versions of the interpreter, the
  201. following may be concluded.
  202. The speed of the interpreter depends strongly on the type of
  203. program being interpreted.
  204. If plain CPU arithmetic is performed, the interpreter is
  205. relatively slow (1000 \(mu the cc version).
  206. When stack manipulation is at hand, the interpreter is
  207. quite fast (100 \(mu the cc version).
  208. .LP
  209. Most programs however will not be this extreme, so an interpretation
  210. time of somewhere between 300 and 500 times direct execution
  211. for a normal program is to be expected.
  212. .LP
  213. The fast version runs in about 60% of the time of the full version, at the
  214. expense of a considerably lower functionality.
  215. Tallying costs about 10%.