mapping.nr 8.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232
  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. Type A Type B
  139. .Df
  140. Figure 3. Two possible memory implementations.
  141. Numbers within the boxes are EM addresses.
  142. The other numbers are physical addresses.
  143. .De
  144. .LP
  145. So, we have two different EM memory implementations:
  146. .IP "A~\-"
  147. stack downwards
  148. .IP "B~\-"
  149. stack upwards
  150. .PP
  151. For each of these two possibilities we give the translation of
  152. the EM instructions to push the third byte of a global data
  153. block starting at EM address 40 onto the stack and to load the
  154. word at address 40.
  155. All translations assume a word and pointer size of two bytes.
  156. The target machine used is a PDP-11 augmented with push and pop instructions.
  157. Registers 'r0' and 'r1' are used and suffer from sign extension for byte
  158. transfers.
  159. Push $40 means push the constant 40, not word 40.
  160. .PP
  161. The translation of the EM instructions depends on the pointer representation
  162. used.
  163. For each of the two solutions explained above the translation is given.
  164. .PP
  165. First, the translation for the two implementations using EM addresses as
  166. pointer representation:
  167. .KS
  168. .TS
  169. tab(:), center;
  170. l s l s l s
  171. l 2 l 6 l 2 l 6 l 2 l.
  172. EM:type A:type B
  173. _
  174. LAE:40:push:$40:push:$40
  175. ADP:3:pop:r0:pop:r0
  176. ::add:$3,r0:add:$3,r0
  177. ::push:r0:push:r0
  178. LOI:1:pop:r0:pop:r0
  179. ::\-::neg:r0
  180. ::clr:r1:clr:r1
  181. ::bisb:eb(r0),r1:bisb:eb(r0),r1
  182. ::push:r1:push:r1
  183. LOE:40:push:eb+40:push:eb-41
  184. .TE
  185. .KE
  186. .PP
  187. The translation for the two implementations, if the target machine address is
  188. used as pointer representation, is:
  189. .KS
  190. .TS
  191. tab(:), center;
  192. l s l s l s
  193. l 2 l 6 l 2 l 6 l 2 l.
  194. EM:type A:type B
  195. _
  196. LAE:40:push:$eb+40:push:$eb-40
  197. ADP:3:pop:r0:pop:r0
  198. ::add:$3,r0:sub:$3,r0
  199. ::push:r0:push:r0
  200. LOI:1:pop:r0:pop:r0
  201. ::clr:r1:clr:r1
  202. ::bisb:(r0),r1:bisb:(r0),r1
  203. ::push:r1:push:r1
  204. LOE:40:push:eb+40:push:eb-41
  205. .TE
  206. .KE
  207. .PP
  208. The translation presented above is not intended to be optimal.
  209. Most machines can handle these simple cases in one or two instructions.
  210. It demonstrates, however, the flexibility of the EM design.
  211. .PP
  212. There are several possibilities to implement EM on machines with
  213. address spaces larger than 64k bytes.
  214. For EM with two byte pointers one could allocate instruction and
  215. data space each in a separate 64k piece of memory.
  216. EM pointers still have to fit in two bytes,
  217. but the base registers PB and EB may be loaded in hardware registers
  218. wider than 16 bits, if available.
  219. EM implementations can also make efficient use of a machine
  220. with separate instruction and data space.
  221. .PP
  222. EM with 32 bit pointers allows one to make use of machines
  223. with large address spaces.
  224. In a virtual, segmented memory system one could use a separate
  225. segment for each fragment.