ack/doc/em/descr.nr

.bp
.P1 "DESCRIPTORS"
.PP
Several instructions use descriptors, notably the range check instruction,
the array instructions, the goto instruction and the case jump instructions.
Descriptors reside in data space.
They may be constructed at run time, but
more often they are fixed and allocated in ROM data.
.PP
All instructions using descriptors, except GTO, have as argument
the size of the integers in the descriptor.
All implementations have to allow integers of the size of a
word in descriptors.
All integers popped from the stack and used for indexing or comparing
must have the same size as the integers in the descriptor.
.P2 "Range check descriptors"
.PP
Range check descriptors consist of two integers:
.IP 1.
lower bound	signed
.IP 2.
upper bound	signed
.LP
The range check instruction checks an integer on the stack against
these bounds and causes a trap if the value is outside the interval.
The value itself is neither changed nor removed from the stack.
.P2 "Array descriptors"
.PP
Each array descriptor describes a single dimension.
For multi-dimensional arrays, several array instructions are
needed to access a single element.
Array descriptors contain the following three integers:
.IP 1.
lower bound		signed
.IP 2.
upper bound \- lower bound	unsigned
.IP 3.
number of bytes per element	unsigned
.LP
The array instructions LAR, SAR and AAR have the pointer to the start
of the descriptor as operand on the stack.
.LP
The element A[I] is fetched as follows:
.IP 1.
Stack the address of A  (e.g., using LAE or LAL)
.IP 2.
Stack the value of I (n-byte integer)
.IP 3.
Stack the pointer to the descriptor (e.g., using LAE)
.IP 4.
LAR n (n is the size of the integers in the descriptor and I)
.LP
All array instructions first pop the address of the descriptor
and the index.
If the index is not within the bounds specified, a trap occurs.
If ok, (I~\-~lower bound) is multiplied
by the number of bytes per element (the third word).  The result is added
to the address of A and replaces A on the stack.
.QQ
At this point LAR, SAR and AAR diverge.
AAR is finished.  LAR pops the address and fetches the data
item,
the size being specified by the descriptor.
The usual restrictions for memory access must be obeyed.
SAR pops the address and stores the
data item now exposed.
.P2 "Non-local goto descriptors"
.PP
The GTO instruction provides a way of returning directly to any
active procedure invocation.
The argument of the instruction is the address of a descriptor
containing three pointers:
.IP 1.
value of PC after the jump
.IP 2.
value of SP after the jump
.IP 3.
value of LB after the jump
.LP
GTO replaces the loads PC, SP and LB from the descriptor,
thereby jumping to a procedure
and removing zero or more frames from the stack.
The LB, SP and PC in the descriptor must belong to a
dynamically enclosing procedure,
because some EM implementations will need to backtrack through
the dynamic chain and use the implementation dependent data
in frames to restore registers etc.
.P2 "Case descriptors"
.PP
The case jump instructions CSA and CSB both
provide multiway branches selected by a case index.
Both fetch two operands from the stack:
first a pointer to the low address of the case descriptor
and then the case index.
CSA uses the case index as index in the descriptor table, but CSB searches
the table for an occurrence of the case index.
Therefore, the descriptors for CSA and CSB,
as shown in figure 4, are different.
All pointers in the table must be addresses of instructions in the
procedure executing the case instruction.
.PP
CSA selects the new PC by indexing.
If the index, a signed integer, is greater than or equal to
the lower bound and less than or equal to the upper bound,
then fetch the new PC from the list of instruction pointers by indexing with
index-lower.
The table does not contain the value of the upper bound,
but the value of upper-lower as an unsigned integer.
The default instruction pointer is used when the index is out of bounds.
If the resulting PC is 0, then trap.
.PP
CSB selects the new PC by searching.
The table is searched for an entry with index value equal to the case index.
That entry or, if none is found, the default entry contains the
new PC.
When the resulting PC is 0, a trap is performed.
.PP
The choice of which case instruction to use for
each source language case statement
is up to the front end.
If the range of the index value is dense, i.e
.DS
(highest value \- lowest value) / number of cases
.DE
is less than some threshold, then CSA is the obvious choice.
If the range is sparse, CSB is better.
.Dr 30
   |--------------------|        |--------------------|  high address
   | pointer for upb    |        |    pointer n-1     |
   |--------------------|        |-  -  -  -  -  -  - |
   |         .          |        |     index  n-1     |
   |         .          |        |--------------------|
   |         .          |        |          .         |
   |         .          |        |          .         |
   |         .          |        |          .         |
   |         .          |        |--------------------|
   |         .          |        |    pointer  1      |
   |--------------------|        |-  -  -  -  -  -  - |
   | pointer for lwb+1  |        |     index   1      |
   |--------------------|        |--------------------|
   | pointer for lwb    |        |    pointer  0      |
   |--------------------|        |-  -  -  -  -  -  - |
   |   upper - lower    |        |     index   0      |
   |--------------------|        |--------------------|
   |    lower bound     |        | number of entries  |
   |--------------------|        |--------------------|
   |  default pointer   |        |  default pointer   |  low address
   |--------------------|        |--------------------|

       CSA descriptor                CSB descriptor
.Df
Figure 4. Descriptor layout for CSA and CSB
.De