doc/em/descr.nr

   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
 150        CSA descriptor                CSB descriptor
 151 .Df
 152 Figure 4. Descriptor layout for CSA and CSB
 153 .De