doc/em/mapping.nr

   1 .bp
   2 .P1 "MAPPING OF EM DATA MEMORY ONTO TARGET MACHINE MEMORY"
   3 .PP
   4 The EM architecture is designed to be implemented
   5 on many existing and future machines.
   6 EM memory is highly fragmented to make
   7 adaptation to various memory architectures possible.
   8 Format and encoding of pointers is explicitly undefined.
   9 .PP
  10 This chapter gives solutions to some of the
  11 anticipated problems.
  12 First, we describe a possible memory layout for machines
  13 with 64K bytes of address space.
  14 Here we use a member of the EM family with 2-byte word and pointer
  15 size.
  16 The most straightforward layout is shown in figure 2.
  17 .Dr 40
  18        65534 \-> |-------------------------------|
  19                 |///////////////////////////////|
  20                 |//// unimplemented memory /////|
  21                 |///////////////////////////////|
  22           ML \-> |-------------------------------|
  23                 |                               |
  24                 |                               | <\- LB
  25                 |     stack and local area      |
  26                 |                               |
  27                 |-------------------------------| <\- SP
  28                 |///////////////////////////////|
  29                 |//////// inaccessible /////////|
  30                 |///////////////////////////////|
  31                 |-------------------------------| <\- HP
  32                 |                               |
  33                 |           heap area           |
  34                 |                               |
  35                 |                               |
  36           HB \-> |-------------------------------|
  37                 |                               |
  38                 |       global data area        |
  39                 |                               |
  40           EB \-> |-------------------------------|
  41                 |                               |
  42                 |         program text          | <\- PC
  43                 |                               |
  44                 |        ( and tables )         |
  45                 |                               |
  46                 |                               |
  47           PB \-> |-------------------------------|
  48                 |///////////////////////////////|
  49                 |////////// undefined //////////|
  50                 |///////////////////////////////|
  51            0 \-> |-------------------------------|
  52 .Df
  53 Figure 2.  Memory layout showing typical register
  54 positions during execution of an EM program.
  55 .De
  56 .sp 1
  57 The base registers for the various memory pieces can be stored
  58 in target machine registers or memory.
  59 .TS
  60 tab(;);
  61 l 1 l l l.
  62 PB;:;program base;points to the base of the instruction address space.
  63 EB;:;external base;points to the base of the data address space.
  64 HB;:;heap base;points to the base of the heap area.
  65 ML;:;memory limit;marks the high end of the addressable data space.
  66 .TE
  67 .LP
  68 The stack grows from high
  69 EM addresses to low EM addresses, and the heap the
  70 other way.
  71 The memory between SP and HP is not accessible,
  72 but may be allocated later to the stack or the heap if needed.
  73 The local data area is allocated starting at the high end of
  74 memory.
  75 .PP
  76 Because EM address 0 is not mapped onto target
  77 address 0, a problem arises when pointers are used.
  78 If a program pushed a constant, say 6, onto the stack,
  79 and then tried to indirect through it,
  80 the wrong word would be fetched,
  81 because EM address 6 is mapped onto target address EB+6
  82 and not target address 6 itself.
  83 This particular problem is solved by explicitly declaring
  84 the format of a pointer to be undefined,
  85 so that using a constant as a pointer is completely illegal.
  86 However, the general problem of mapping pointers still exists.
  87 .PP
  88 There are two possible solutions.
  89 In the first solution, EM pointers are represented
  90 in the target machine as true EM addresses,
  91 for example, a pointer to EM address 6 really is
  92 stored as a 6 in the target machine.
  93 This solution implies that every time a pointer is fetched
  94 EB must be added before referencing
  95 the target machine's memory.
  96 If the target machine has powerful indexing
  97 facilities, EB can be kept in a target machine register,
  98 and the relocation can indeed be done on
  99 every reference to the data address space
 100 at a modest cost in speed.
 101 .PP
 102 The other solution consists of having EM pointers
 103 refer to the true target machine address.
 104 Thus the instruction LAE 6 (Load Address of External 6)
 105 would push the value of EB+6 onto the stack.
 106 When this approach is chosen, back ends must know
 107 how to offset from EB, to translate all
 108 instructions that manipulate EM addresses.
 109 However, the problem is not completely solved,
 110 because a front end may have to initialize a pointer
 111 in CON or ROM data to point to a global address.
 112 This pointer must also be relocated by the back end or the interpreter.
 113 .PP
 114 Although the EM stack grows from high to low EM addresses,
 115 some machines have hardware PUSH and POP
 116 instructions that require the stack to grow upwards.
 117 If reasons of efficiency demand the use of these
 118 instructions, then EM
 119 can be implemented with the memory layout
 120 upside down, as shown in figure 3.
 121 This is possible because the pointer format is explicitly undefined.
 122 The first element of a word array will have a
 123 lower physical address than the second element.
 124 .Dr 18
 125           |                 |                    |                 |
 126           |      EB=60      |                    |        ^        |
 127           |                 |                    |        |        |
 128           |-----------------|                    |-----------------|
 129       105 |   45   |   44   | 104            214 |   41   |   40   | 215
 130           |-----------------|                    |-----------------|
 131       103 |   43   |   42   | 102            212 |   43   |   42   | 213
 132           |-----------------|                    |-----------------|
 133       101 |   41   |   40   | 100            210 |   45   |   44   | 211
 134           |-----------------|                    |-----------------|
 135           |        |        |                    |                 |
 136           |        v        |                    |      EB=255     |
 137           |                 |                    |                 |
 138
 139                 Type A                                 Type B
 140 .Df
 141 Figure 3. Two possible memory implementations.
 142 Numbers within the boxes are EM addresses.
 143 The other numbers are physical addresses.
 144 .De
 145 .LP
 146 So, we have two different EM memory implementations:
 147 .IP "A~\-"
 148 stack downwards
 149 .IP "B~\-"
 150 stack upwards
 151 .PP
 152 For each of these two possibilities we give the translation of
 153 the EM instructions to push the third byte of a global data
 154 block starting at EM address 40 onto the stack and to load the
 155 word at address 40.
 156 All translations assume a word and pointer size of two bytes.
 157 The target machine used is a PDP-11 augmented with push and pop instructions.
 158 Registers 'r0' and 'r1' are used and suffer from sign extension for byte
 159 transfers.
 160 Push $40 means push the constant 40, not word 40.
 161 .PP
 162 The translation of the EM instructions depends on the pointer representation
 163 used.
 164 For each of the two solutions explained above the translation is given.
 165 .PP
 166 First, the translation for the two implementations using EM addresses as
 167 pointer representation:
 168 .KS
 169 .TS
 170 tab(:), center;
 171 l s l s l s
 172 l 2 l 6 l 2 l 6 l 2 l.
 173 EM:type A:type B
 174 _
 175 LAE:40:push:$40:push:$40
 176
 177 ADP:3:pop:r0:pop:r0
 178 ::add:$3,r0:add:$3,r0
 179 ::push:r0:push:r0
 180
 181 LOI:1:pop:r0:pop:r0
 182 ::\-::neg:r0
 183 ::clr:r1:clr:r1
 184 ::bisb:eb(r0),r1:bisb:eb(r0),r1
 185 ::push:r1:push:r1
 186
 187 LOE:40:push:eb+40:push:eb-41
 188 .TE
 189 .KE
 190 .PP
 191 The translation for the two implementations, if the target machine address is
 192 used as pointer representation, is:
 193 .KS
 194 .TS
 195 tab(:), center;
 196 l s l s l s
 197 l 2 l 6 l 2 l 6 l 2 l.
 198 EM:type A:type B
 199 _
 200 LAE:40:push:$eb+40:push:$eb-40
 201
 202 ADP:3:pop:r0:pop:r0
 203 ::add:$3,r0:sub:$3,r0
 204 ::push:r0:push:r0
 205
 206 LOI:1:pop:r0:pop:r0
 207 ::clr:r1:clr:r1
 208 ::bisb:(r0),r1:bisb:(r0),r1
 209 ::push:r1:push:r1
 210
 211 LOE:40:push:eb+40:push:eb-41
 212 .TE
 213 .KE
 214 .PP
 215 The translation presented above is not intended to be optimal.
 216 Most machines can handle these simple cases in one or two instructions.
 217 It demonstrates, however, the flexibility of the EM design.
 218 .PP
 219 There are several possibilities to implement EM on machines with
 220 address spaces larger than 64k bytes.
 221 For EM with two byte pointers one could allocate instruction and
 222 data space each in a separate 64k piece of memory.
 223 EM pointers still have to fit in two bytes,
 224 but the base registers PB and EB may be loaded in hardware registers
 225 wider than 16 bits, if available.
 226 EM implementations can also make efficient use of a machine
 227 with separate instruction and data space.
 228 .PP
 229 EM with 32 bit pointers allows one to make use of machines
 230 with large address spaces.
 231 In a virtual, segmented memory system one could use a separate
 232 segment for each fragment.