descr.nr 5.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153
  1. .bp
  2. .P1 "DESCRIPTORS"
  3. .PP
  4. Several instructions use descriptors, notably the range check instruction,
  5. the array instructions, the goto instruction and the case jump instructions.
  6. Descriptors reside in data space.
  7. They may be constructed at run time, but
  8. more often they are fixed and allocated in ROM data.
  9. .PP
  10. All instructions using descriptors, except GTO, have as argument
  11. the size of the integers in the descriptor.
  12. All implementations have to allow integers of the size of a
  13. word in descriptors.
  14. All integers popped from the stack and used for indexing or comparing
  15. must have the same size as the integers in the descriptor.
  16. .P2 "Range check descriptors"
  17. .PP
  18. Range check descriptors consist of two integers:
  19. .IP 1.
  20. lower bound signed
  21. .IP 2.
  22. upper bound signed
  23. .LP
  24. The range check instruction checks an integer on the stack against
  25. these bounds and causes a trap if the value is outside the interval.
  26. The value itself is neither changed nor removed from the stack.
  27. .P2 "Array descriptors"
  28. .PP
  29. Each array descriptor describes a single dimension.
  30. For multi-dimensional arrays, several array instructions are
  31. needed to access a single element.
  32. Array descriptors contain the following three integers:
  33. .IP 1.
  34. lower bound signed
  35. .IP 2.
  36. upper bound \- lower bound unsigned
  37. .IP 3.
  38. number of bytes per element unsigned
  39. .LP
  40. The array instructions LAR, SAR and AAR have the pointer to the start
  41. of the descriptor as operand on the stack.
  42. .LP
  43. The element A[I] is fetched as follows:
  44. .IP 1.
  45. Stack the address of A (e.g., using LAE or LAL)
  46. .IP 2.
  47. Stack the value of I (n-byte integer)
  48. .IP 3.
  49. Stack the pointer to the descriptor (e.g., using LAE)
  50. .IP 4.
  51. LAR n (n is the size of the integers in the descriptor and I)
  52. .LP
  53. All array instructions first pop the address of the descriptor
  54. and the index.
  55. If the index is not within the bounds specified, a trap occurs.
  56. If ok, (I~\-~lower bound) is multiplied
  57. by the number of bytes per element (the third word). The result is added
  58. to the address of A and replaces A on the stack.
  59. .QQ
  60. At this point LAR, SAR and AAR diverge.
  61. AAR is finished. LAR pops the address and fetches the data
  62. item,
  63. the size being specified by the descriptor.
  64. The usual restrictions for memory access must be obeyed.
  65. SAR pops the address and stores the
  66. data item now exposed.
  67. .P2 "Non-local goto descriptors"
  68. .PP
  69. The GTO instruction provides a way of returning directly to any
  70. active procedure invocation.
  71. The argument of the instruction is the address of a descriptor
  72. containing three pointers:
  73. .IP 1.
  74. value of PC after the jump
  75. .IP 2.
  76. value of SP after the jump
  77. .IP 3.
  78. value of LB after the jump
  79. .LP
  80. GTO replaces the loads PC, SP and LB from the descriptor,
  81. thereby jumping to a procedure
  82. and removing zero or more frames from the stack.
  83. The LB, SP and PC in the descriptor must belong to a
  84. dynamically enclosing procedure,
  85. because some EM implementations will need to backtrack through
  86. the dynamic chain and use the implementation dependent data
  87. in frames to restore registers etc.
  88. .P2 "Case descriptors"
  89. .PP
  90. The case jump instructions CSA and CSB both
  91. provide multiway branches selected by a case index.
  92. Both fetch two operands from the stack:
  93. first a pointer to the low address of the case descriptor
  94. and then the case index.
  95. CSA uses the case index as index in the descriptor table, but CSB searches
  96. the table for an occurrence of the case index.
  97. Therefore, the descriptors for CSA and CSB,
  98. as shown in figure 4, are different.
  99. All pointers in the table must be addresses of instructions in the
  100. procedure executing the case instruction.
  101. .PP
  102. CSA selects the new PC by indexing.
  103. If the index, a signed integer, is greater than or equal to
  104. the lower bound and less than or equal to the upper bound,
  105. then fetch the new PC from the list of instruction pointers by indexing with
  106. index-lower.
  107. The table does not contain the value of the upper bound,
  108. but the value of upper-lower as an unsigned integer.
  109. The default instruction pointer is used when the index is out of bounds.
  110. If the resulting PC is 0, then trap.
  111. .PP
  112. CSB selects the new PC by searching.
  113. The table is searched for an entry with index value equal to the case index.
  114. That entry or, if none is found, the default entry contains the
  115. new PC.
  116. When the resulting PC is 0, a trap is performed.
  117. .PP
  118. The choice of which case instruction to use for
  119. each source language case statement
  120. is up to the front end.
  121. If the range of the index value is dense, i.e
  122. .DS
  123. (highest value \- lowest value) / number of cases
  124. .DE
  125. is less than some threshold, then CSA is the obvious choice.
  126. If the range is sparse, CSB is better.
  127. .Dr 30
  128. |--------------------| |--------------------| high address
  129. | pointer for upb | | pointer n-1 |
  130. |--------------------| |- - - - - - - |
  131. | . | | index n-1 |
  132. | . | |--------------------|
  133. | . | | . |
  134. | . | | . |
  135. | . | | . |
  136. | . | |--------------------|
  137. | . | | pointer 1 |
  138. |--------------------| |- - - - - - - |
  139. | pointer for lwb+1 | | index 1 |
  140. |--------------------| |--------------------|
  141. | pointer for lwb | | pointer 0 |
  142. |--------------------| |- - - - - - - |
  143. | upper - lower | | index 0 |
  144. |--------------------| |--------------------|
  145. | lower bound | | number of entries |
  146. |--------------------| |--------------------|
  147. | default pointer | | default pointer | low address
  148. |--------------------| |--------------------|
  149. CSA descriptor CSB descriptor
  150. .Df
  151. Figure 4. Descriptor layout for CSA and CSB
  152. .De