The MMIX Supplement: Supplement to The Art of Computer Programming Volumes 1, 2, 3 by Donald E. Knuth

PROGRAMMING TECHNIQUES

1. INDEX VARIABLES

Many algorithms traverse information structures that are sequentially allocated in memory. Let us assume that a sequence of n data items a₀, a₁, . . . , a_n−1 is stored sequentially. Further assume that each data item occupies 8 bytes, and the first element a₀ is stored at address A; the address of a_i is then A + 8i. To load a_i with 0 ≤ i < n from memory into register ai, we need a suitable base address and so we assume that we have A = LOC(a₀) in register a. Then we can write ‘8ADDU t,i,a; LDO ai,t,0’ or alternatively ‘SL t,i,3; LDO ai,a,t’. If this operation is necessary for all i, it is more efficient to maintain a register i containing 8i as follows:

SET	i,0	i ← 0.
LDO	ai,a,i	Load ai.
ADD	i,i,8 ...