Advanced Indirect Addressing Modes

A memory indirect addressing mode is one in which the effective address provided by the instruction is used to access memory to locate the effective address of the operand. That is, memory is accessed twice: first to get the pointer and second to get the actual operand. Most microprocessors don't provide indirect addressing. Moreover, the trend since the mid 90s has been to abandon memory indirect addressing modes in favor of simpler addressing modes. You can always synthesize a complex addressing mode by using a sequence of instructions with simple addressing modes.

We are interested in complex indirect addressing modes because they provide a powerful means of accessing data structures and allow you (or the compiler) to generate very efficient and compact code. Although this "CISC" style addressing is not currently in vogue, the pendulum may well swing away from "RISC" style simplicity in the future.

Review of Conventional Address Register Indirect Addressing

Figure 1 demonstrates an address register indirect address which is expressed as (A0) in 68000 assembly language. Address register A0 contains the value 1000 which points to the location of the actual operand in memory. This addressing mode is used to access linear data structures such as lists and tables.

Figure 1 Address register indirect addressing

Figure 2 demonstrates a simple extension of address register indirect addressing. In this case a constant offset is added to the contents of the address regster to create the effective address. Note that the contents of the address register is not modified. In this example address register A0 contains 1234, the offset is 8, and the effective address is 1234+8=123C.

This addressing mode is used to access an item in a table whose location is expressed with respect to the start of the table.. For example, if A0 points to the start of a 7-byte data structure representing the days of the week, the operation MOVE.B MONDAY(A0),D0 loads the entry corresponding to "Monday" into D0. Note that the sysntax of this addressing mode was changed between the 68000 and the 68020 (and later) microprocesors. You can write either MOVE.B MONDAY(A0),D0 or MOVE.B (MONDAY,A0),D0.

Figure 2 Address register indirect addressing with offset

The 68020's New Addressing Modes

The 68020 provides two memory indirect addressing modes: memory indirect postindexed and memory indirect preindexed. The syntax of the 68020's new indirect addressing modes is:

Here bd is a 16- or 32-bit constant called the bse displacement, Xn is an address or data register, and od is a second 16- or 32-bit literal constant called the outer displacement. These addressing modes can be used in simpler forms by suppressing the displacements bd and/or od, and by omitting registers An or Xn. The following instructions are legal examples of memory indirect postindexed addressing:

MOVE D0,([A0])
MOVE D0,([4,A0])
MOVE D0,([A0],6)
MOVE D0,([A0],D3)
MOVE D0,([A0],D4,12)
MOVE D0,([$12345678,A0],D4,$FF000000)

Note that the index register Xn can be scaled (i.e., multiplied) by 2, 4, or 8 by writing Xn*sc. If you write the effective address MOVE D0,([24,A0,4*D0])then the contents of the square brackets is evaluated as [A0] + 4 x [D0] + 24. In what follows, we examine only the two memory indirect addressing modes. The two program counter memory indirect addressing modes are not dealt with here (they are used to generate position-independent code).

Let's examine how these addressing modes work. Each effective address contains a pair of square brackets [...] within a pair or round brackets ([...],..). The contents of the square brackets are first evaluated to create a 4-byte (32-bit) pointer. For example, if the postindexed form is [20,A2] the effective address is given by 20 + [A2]. Similarly, if the preindexed form is [12,A4,D5] the effective address is given by 12 + [A4] + [D5].

The pointer generated by the contents of the square bracket is used to access memory to obtain a new pointer (hence the term memory indirect addressing). The contents of the outer round brackets are added to this new pointer to generate the actual address of the operand.

Let's look at how the effective address ([12,A2],D3,9) is evaluated. Figures 3 to 6 demonstrate, step by step, how an operand is accessed by this effective address. First, the the longword at the location given by 12 plus the contents of A2 is accessed in memory.

Figure 3 Evaluating the effective address ([12,A2],D3,9)

Figure 4 demonstrates how the contents of the inner square brackets are evaluated to generate the address of a pointer in memory. This pointer points to a new location.

Figure 4 The value of [12,A2] is evaluated and the pointer at that location accessed

So far, we've generated the address of a pointer in memory, and read the pointer. In the final stge we access the operand which is specified with respect to this pointer. In figure 5 the the contents of data register D3 are added to the address pointed at by the pointer in memory. In figure 6 the so called outer offset whose value is 9 is added to give the address of the operand.

Figure 5 The contents of D3 are added to the location pointed at

Figure 6 The offset 9 is added to the pointer to give the address of the actual operand

As you can see from figures 3 to 6, this memory indirect postindexed addressing mode used two pointers. The first pointer is obtained by evaluation the contents of the square brackets. The second pointer is obtained by adding the register and constant outsde the square brackets to the contents of the memory location pointed at by the first pointer. In RTL terms, the effective address of the operand is given by

ea = [M([M([A2] + 12)] + [D3] + 9)]

The 68020 implements postindexed and preindexed memory indirect addresing forms. Because of the way in whch the 68020's instructions are encoded, only one index register Xn can be specified. You can use this index register to generate the address of the pointer (e.g., ([bd,An,Xn],...)) or you can use it to index into the data structure itself (e.g., ([...],Xn,od)). The form of addressing you use depends on the application.

Using Address Register Indirect Addressing

We will now provide an example of the application of this addressing mode. A typical high-level language construct is the switch or case statement that executes one of n statements according to the value of a variable i. You can implement this construct by creating table of pointers to the statements (or subroutines) to be executed. Statement i is executed by loading the program counter with the ith pointer.

Figure 7 demonstrates a table of longword addresses, each of which corresponds to a subroutine entry point. Address register A0 points to the first location in this table. Suppose that the number in D0 indicates which subroutine is to be called. We can call the appropriate subroutine (in 68000 code without memory indirect addressing) by the following actions.

The contents of D0 are first multiplied by 4 because subroutine addresses occupy one longword (4 bytes), whereas the subroutine identifier in D0 is a one-byte value. That is, successive pointers are stored at [A0], [A0]+4, [A0]+8,... etc. Note that the operation JSR (A1) means "jump to the suroutine whose address is in address register A0".

We can now use the 68020's indirect addressing mode to implement this computed jump in one single instruction.

In RTL this opertion is defined as [PC] <-- [M([A0] + 4 x [D0])]

The contents of A0 are added to the contents of D0 multiplied by 4. The resulting effective address is used to access the table. The longword at this address is read and loaded into the program counter to call the subroutine. The 68020's memory indirect addressing mode replaces three 68000 instructions with a single 68020 instruction. Moreover, the scaling does not modify the contents of the register being scaled; that is, the value of D0 is not modified by this operation.

Figure 7 Accessing a jump table

Constants used in Memory Indirect Addressing

The constants or literals employed by the 68020's new memory indirect addressing modes and are written bd, od and sc. The base displacement, bd, is added to an address register to give the location in memory containing the pointer to the actual operand. The outer displacement, od, is added to the value read from memory to give the actual address of the operand. The scale factor, sc, is 1, 2, 4 or 8 and is used to scale the contents of an index register.

The need for a scale factor is related to the 68020's ability to support byte, word, longword, and quadword operands. Clearly, successive bytes differ by one location, successive words differ by two locations, successive longwords differ by four locations, and successive quadwords differ by eight locations because the 68000 family's memory is byte addressed, irrespective of the type of data being accessed. Suppose that A0 points to an array of elements and D0 contains an index i. The address of the ith element is given by [A0] + [D0]*sc, where sc is 1, 2, 4 or 8 for byte, word, longword or quadword (i.e., 64-bit) data elements. For example, in 68000 code we would write:

The 68020 provides explicit scaling in conjunction with memory indirect addressing. The index register, Xn, may be an address or data register and is written Xn*sc in assembler form. Typical effective addresses might be written:

Figure 8 demonstrates how the scale factor relates to the size of data objects. Of course, the built-in scale factors of the 68020 cannot be used with data objects of arbitrary size.

Figure 8 The scale factor (only factors of 1, 2, and 4 illustrated)

Example of Memory Indirect Addressing

We now demonstrate how the 68020's memory indirect addressing mode is used to access a complex data structure. Consider the arrangement of figure 9 where we have constructed three data structures 1, 2, and 3. Each of these is only 4 elements long, although a real system could implement much more complex structures. Somewhere in memory we have a table of pointers whose elements point to the data structures; for example, pointer 1 points to data structure 1.

Figure 9 Example of a data structure

Why do we need the structure of figure 9? We could just put the data structures one after the other and forget about the table of pointers. If we wish to access structure i, its address is Base + (i - 1) * n, where Base is the address of the first structure and n is the size of each structure. There's nothing wrong with this arrangement, but it is limited. First, we can't easily use structures of different sizes. Second, if there are m structures of n bytes, the memory requirement is n.m bytes. If we use a table of pointers as described by figure 9, the individual records don't have to have the same size. Moreover, we don't have to implement all m records. You only have to implement the records actually required.

Consider a list of student records, each of which consists of six elements. An element corresponds to the student's results in that subject (see figure 10). There are many ways of organizing the data structure of figure 10. One is to create list of pointers, one per student, where each pointer points to the appropriate student's results.

Figure 10 Example of memory indirect addressing with preindexing

Register A0 points to the base of a region of memory devoted to the pointers to the students' records. This region may include other items of related data. The base displacement, bd, points to the start of the list of pointers to students with respect to the start of the region of data; i.e., the first student's pointer is at address [A0] + bd.

The index of the student selected is in data register D0. Since each entry in the table of pointers is a longword, we have to scale the contents of D0 by 4. The effective address of the pointer to the selected student's record is therefore [A0] + bd + 4*[D0]. In figure 10 the base displacement is PTR. The 68020 reads this pointer which points to the start of the student's record.

Suppose we want to know how the student performed in computer science which is the fourth out of the six results. We need to access the fourth item in the table (i.e., item 3 because the first item is numbered zero). The outer displacement provides us with a facility to do this. When the processor reads the pointer from memory, it adds the outer displacement to it to calculate the actual effective address of the desired operand.

If this example were to be coded for the 68000, the assembly language form might look like:

The same calculation can be carried out by the 68020 using memory indirect addressing with preindexing:

Before looking at another example of the 68020's two memory indirect addressing modes, it is worthwhile looking at how they differ. Figure 11 illustrates the effect of preindexing and figure 12 the effect of postindexing.

Figure 11 The 68020's preindexing memory indirect addressing

Figure 12 The 68020's postindexing memory indirect addressing

Using Memory Indirect Addressing to with a TRAPcc Instruction

A TRAPcc instruction calls the operating system if condition cc is true; e.g., TRAPCS calls the O/S if the carry bit is set. A TRAPcc instruction has three formats, one with no extension, one with an extension word (TRAPcc.W) and one with two extension words (TRAPcc.L). These extensions are literal values that can be read by the operating system.

When a TRAPcc instruction is encountered and the specified condition cc is true, a call to the operating system is made and certain information saved on the stack pointed at by A7. Figure 13 illustrates the state of the system immediately after a TRAPCS.W #d16 instruction has been executed and the trap taken. You don’t have to understand the details of exception handlers—all that you need know is that the stack frame pointed at by A7 contains the address of the instruction that caused the exception (i.e., the address of the TRAPCS.W #d16) at location [A7] + 8. Suppose the TRAPcc handler needs to examine the literal following the TRAPcc. This literal is stored at address N + 2 in figure 13. We can use memory indirect addressing to access this literal via the stack pointer, A7. That is:

Eight is added to the contents of the stack pointer to get the address of the "address of the TRAPcc exception". The contents of this location (i.e., [A7] + 8) are read to give the address of the TRAPcc. The outer displacement, 2, is added to this value to give the address of the literal following the TRAPCS.W. This literal is then loaded into D0. As we have seen, this entire sequence is carried out by a single 68020 instruction. By the way, we assumed that the trap had been called by a TRAPcc instruction with a word extension. If we did not know this, the exception handler would have to have examined the bit pattern of the TRAPcc instruction in order to determine the length of the operand following it.

Figure 13 Effect of executing a TRAPCS.W #data instruction