Style Guide for The MMIX Supplement: Supplement to The Art of Computer Programming Volumes 1, 2, 3 by Donald E. Knuth
This chapter is from the book
This chapter is from the book
This chapter is from the book
1. Names
Choosing good names is one of the most important and most difficult tasks when writing programs, especially if the programs are intended for publication. Good names need to be consistent and so this section starts with some simple rules that guided how names in this book were chosen.
Small named constants, for instance, have all uppercase names such as FACEUP. Special cases of this rule are the offsets of fields inside records such as NEXT or TAG (see 2.1–(1) and 2.1–(5)). Addresses are associated with names that always start with an uppercase letter and continue with uppercase or lowercase letters. Examples are ‘TOP OCTA 1F’ and ‘Main SET i,0’. In contrast, names for registers use only lowercase letters, as in x, t, or new.
As a short example illustrating these rules, consider the solution to exercise 2.1–9 on page 123. The address where the printing subroutine starts has the name :PrintPile (an explanation for the colon follows below), and the location where the string is stored is named String. The constant #0a, the ASCII newline character, is named NL; every node has a CARD field at offset 8, and when the value of this field is loaded into a register, this register has the name card.
Often the statement of algorithms has a more mathematical nature. In mathematical language most variables have single-letter names that are set in italic font, such as x, y, Q, or even Q′, f0, or α. In the actual program these variables might look like x, y, Q, Qp, f0, or alpha. The single-letter style of mathematics leads to rather terse programs. This style is appropriate if the exposition is mostly mathematical and the implementation has to convince the reader that it embodies the right mathematics. If the program describes the manipulation of “real-world objects,” a more verbose style using descriptive names such as card or title will improve readability.
In this book, the ultimate aim of choosing a specific name for an address, register, or constant is to make the transition from the algorithms and MIX programs, as given in The Art of Computer Programming, to their implementations as MMIX programs as painless as possible.
One difficulty arises from the fact that the MIX assembly language did not provide named registers but only named memory locations; further, names consisted of uppercase letters only. So when an algorithm mentions the variable X, there is the silent assumption that if the corresponding MIX Program uses X, it names a memory location where the value of the variable X is stored. In MMIX programs, names for memory locations are quite rare, because all load and store instructions require registers to compute the target address. Therefore, it is most likely that you will not find X in the corresponding MMIX program; instead you will find a register, named x, that contains the address of the memory location where the variable X resides. Taking this one step further, often there is no need to store the value of variable X in memory at all; instead, it is completely sufficient to keep the value of X in register x for the entire Program or subroutine. As an example, consider again the solution to exercise 2.1–9. The line that read
LD2 0,2(NEXT) Set X ← NEXT(X).
in the MIX Program on page [535] now reads as follows in the MMIX program:
LDOU x,x,NEXT Set X ← NEXT(X).
2. Temporaries
There is one special variable, named t, which is used as a temporary variable (hence t). It is used to carry intermediate values from one instruction to the next and there is no benefit in giving it an individual name. In a few cases, where the name t is used already in the exposition of the algorithm, x is used to name the temporary variable.
The specific register number used for one of the named registers is typically not relevant; in connection with the PUSHJ instruction, however, all named local registers will have register numbers smaller than t such that the subroutine call ‘PUSHJ t,. . . ’ will not clobber any of them — except t, which might hold the return value.
3. Index Variables
The variables used to index arrays fall into a special class. If the exposition of an algorithm refers to xi for 1 ≤ i ≤ n, we might expect a register xi (the value of xi), a register x (the address of the array), and a register i (the index) to show up somewhere in the implementation. Often, however, the implementation will find it more convenient to maintain in register i the value of 8×i (the offset of xi relative to LOC(x0)), or 8 × (i − 1) (the offset of xi relative to LOC(x1)), or even 8 × (i − n) (the offset of xi relative to LOC(xn)). In the latter case (see below), it is also more convenient to change the value of x to x + 8n. In all these cases, the use of x (not X) and i (not i) will remind the reader that the registers x and i are not exactly the variables X and i. For a short example see the solution to exercise 4.3.1–25 on page 157.
4. Register Numbers
Typically, it is best to avoid the use of register numbers, but instead use register names. There are, though, a few exceptions.
When using TRIP and TRAP instructions, register $255 has a special purpose: It serves as parameter register. For the reader of a program, there is some useful information in the fact that a value is stored in $255: It will serve as a parameter to the next TRAP or TRIP. This information should not be hidden by using an alias for $255. Similarly, using the return value from a TRAP or TRIP can be made explicit by using $255. For an example see Program 1.3.3A on page 1.
Further, the return value of a function must be in register $0 just before the final POP. Identifying the register by its number makes the assignment of a return value visible. For an example see again the solution to exercise 4.3.1–25.
The Program in Section 2.2.5 is special, however: Due to the restrictions imposed by its very simple implementation of coroutines, this Program can use local registers only for temporary variables. Consequently, there is no need to give them names.
5. Local Name Spaces
If programs have multiple subroutines, name conflicts will be inevitable — unless the pseudo-instruction PREFIX is used. In this book, every subroutine is given its own name space by starting it with ‘PREFIX :name:’, where name repeats the name of the subroutine itself. (See, for example, the solution to exercise 5–7 on page 162.)
The use of two colons, one before and one after ‘name’, begs for an explanation. Without the first colon, ‘name:’ would just be added to the current prefix, leading to longer and longer prefixes unless the prefix is reset regularly by ‘PREFIX :’. Adding a colon before ‘name’ is the safer and more convenient alternative. To explain the second colon, imagine using the label ‘Put’ — without defining it — after ‘PREFIX :Out’; then MMIXAL will complain about an undefined symbol ‘OutPut’. In a long program, this error might be hard to diagnose. Could it be a misspelling of ‘Output’? It becomes really hard to track down such an error if your Program contains an unrelated global symbol ‘OutPut’; MMIXAL will use it without notice. The colon after ‘name’ will prevent MMIXAL from confusing global and local names and will make error messages, like a complaint about ‘Out:Put’, more readable.
In order to avoid a clumsy :name:name in the calling code, the entry point into the subroutine is marked by :name, making it global. A short example is the ShiftLeft subroutine shown in the solution to exercise 4.3.1–25. The entry point is usually the only global name defined by a subroutine. However, the subroutine might use quite a few global names, defined elsewhere, to reference other subroutines, global registers, or special registers such as :rJ. In these cases, the extra colon in front of the name is a useful hint that the name belongs to a global entity; as an added benefit, it allows us to say ‘rJ IS $0’ and use rJ to keep a local copy of :rJ.
Not typical, but occasionally useful, is a joint name space for multiple subroutines. For example, in the simulation Program of Section 2.2.5, the routines Insert and Delete (lines 059–072 on page 30) share the same name space.
To leave the local name space and return to the global name space, a simple ‘PREFIX :’ is sufficient.
Because name spaces are merely a technicality, in most of the Program listings in this book, the PREFIX instructions are not shown.
6. Instruction Counts
For the analysis of algorithms, a column of instruction counts is added to the Program display. Instruction counts* are shown rather than cycle counts because the former are easier to read and because there is no simple way to determine the latter. For a superscalar pipeline processor such as MMIX, the number of cycles per instruction depends on many, many factors. To further complicate the issue, MMIX can be configured to mimic a wide variety of processors. Therefore, the running time is approximated by counting υ and µ, where 1υ is approximately one cycle and 1µ is one access to main memory. Most MMIX instructions require 1υ; the most important exceptions are load and store instructions (1υ+1µ), multiplication (10υ), division (60υ), most floating point instructions (4υ), POP (3υ), TRIP (5υ), and TRAP (5υ).
For branch instructions, the number of bad guesses is given in square brackets. So m[n] will label a branch that is executed m times with n bad guesses (and m − n good guesses). It will contribute (m + 2n)υ to the total running time.
Often the code is presented as a subroutine. In this case, the “call overhead” — the assignment of parameters, the PUSHJ, and the final POP — is not included in the computation of the total running time. In situations where the call overhead would be a significant percentage of the running time, the subroutine code can be expanded inline (see, for example, the FindTag subroutine in the solution to exercise 2.5–27 on page 143).
If, however, the subroutine under examination is itself the caller of a subroutine, the called subroutine, including its call overhead, will be included in the total count. A special case arises for recursive routines. There, the PUSHJ and POP instructions cannot be eliminated and must be counted. Further, it would be confusing not to include the final POP in the total count since this would violate Kirchhoff’s law. The initial PUSHJ is, however, not shown — and not counted.