doc/int/txt1

   1 .\"     Introduction
   2 .\"
   3 .\"     $Id: txt1,v 2.2 1994/06/24 10:05:31 ceriel Exp $
   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%.