The MMIX Supplement to The Art of Computer Programming: Programming Techniques

Feb 25, 2015

⎙ Print

Page 1 of 1

In this excerpt from The MMIX Supplement: Supplement to The Art of Computer Programming Volumes 1, 2, 3 by Donald E. Knuth, Martin Ruckert discusses various programming techniques, including index variables, fields, relative addresses, bit stuffing, loop unrolling, subroutines, and reporting errors.

This chapter is from the book 

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

Learn More Buy

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₋₁ 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 a_i.
ADD	i,i,8	Advance to next element: i ← i + 1.
· · ·

Note how i advances by 8 when i advances by 1.

The branch instructions of MMIX, like most computer architectures, directly support a test against zero; therefore a loop becomes more efficient if the index variable runs toward 0 instead of toward n. The loop may then take the form:

	SL	i,n,3	i ← n.
0H	SUB	i,i,8	Advance to next element: i ← i − 1.
	LDO	ai,a,i	Load a_i.
	· · ·
	PBP	i,0B	Continue while i > 0.

In the above form, the items are traversed in decreasing order. If the algorithm requires traversal in ascending order, it is more efficient to keep A + 8n, the address of a_n, as new base address in a register an, and to run the index register i from −8n toward −8 as in the following code:

	8ADDU	an,n,a	an ← A + 8n.
	SUBU	i,a,an	i ← 0 (or i ← −8n).
0H	LDO	ai,an,i	ai ← a_i.
	· · ·
	ADD	i,i,8	Advance to next element: i ← i + 1.
	PBP	i,0B	Continue while i < n.

If a is used only to compute A+8n, it is possible to write ‘8ADDU a,n,a’ and reuse register a to hold A + 8n. Loading a_i then resumes the nice form ‘LDO ai,a,i’, without any need for an. For an example, see Program 4.3.1S on page 63.

When computer scientists enumerate n elements, they say “a₀, a₁, a₂, . . . ”, starting with index zero. When mathematicians (and most other people) enumerate n elements, they say “a₁, a₂, a₃, . . . ” and start with index 1. Nevertheless when such a sequence of elements is passed as a parameter to a subroutine, it is customary to pass the address of its first element LOC(a₁). If this address is in register a, the address of a_i is now a + 8(i − 1). To load a_i efficiently into register ai, we have two choices: Either we adjust register a, saying ‘SUBU a,a,8’ for a ← LOC(a₀), or we maintain in register i the value of 8(i − 1), saying for example ‘SET i,0’ for i ← 1. In both cases, we can write ‘LDO ai,a,i’ to load ai ← a_i.

Many variations of these techniques are possible; a nice and important example is Program 5.2.1S on page 76.

2. Fields

Let us assume that the data elements a_i, just considered, are further structured by having three fields, two WYDEs and one TETRA, like this:

Click to view larger image

It is then convenient to define offsets for the fields reusing the field names as follows:

LEFT	IS	0	Offset for field LEFT
RIGHT	IS	2	Offset for field RIGHT
KEY	IS	4	Offset for field KEY

There is very little information in these lines, so these definitions are usually suppressed in a program’s display.

Computing the address of, say, the KEY field of a_i requires two additions, A + 8i + KEY, of which only one must be done inside a loop over i. The quantity A + KEY can be precomputed and kept in a register named key. This simplifies loading of KEY(a_i) as follows:

ADDU	key,a,KEY	key ← A + KEY.
· · ·		Loop on i with i = 8_i.
LDT	k,key,i	k ← KEY(a_i).

3. Relative Addresses

In a more general setting, this technique can be applied to relative addresses. Assume that one of the data items a_i is given by its relative address P = LOC(a_i) − BASE relative to some base address BASE.

Then again KEY(a_i) can be loaded by a single instruction ‘LDT k,key,p’, if P is in register p, and BASE + KEY is in register key.

While an absolute address always requires eight bytes in MMIX’s memory, relative addresses can be stored using only four bytes, two bytes, or one byte, which allows tighter packing of information structures and reduces the memory footprint of applications that handle large numbers of links. Using this technique, the use of relative addresses can be as efficient as the use of absolute addresses.

4. Using the Low Order Bits of Pointers (“Bit Stuffing”)

Modern computers impose alignment restrictions on the possible addresses of primitive data types. In the case of MMIX, an OCTA may start only at an address that is a multiple of 8, a TETRA requires a multiple of 4, and a WYDE needs an even address. As a result, data structures are typically octabyte-aligned, because they contain one or more OCTA-fields—for example, to hold an absolute address in a link field. Those link fields, in turn, are multiples of eight as well. Put differently, their three low-order bits are all zero. Such precious bits can be put to use as tag bits, marking the pointer to indicate that either the pointer itself or the data item it points to has some special property. MMIX further simplifies the use of these bits as tags by ignoring the low-order bits of an address in load and store instructions. That convention is not the case for all CPU architectures. Still, these bits are usable as tags; they just need to be masked to zero on such computers before using link fields as addresses.

Three different uses need to be distinguished. First, a tag bit in a link may contain some additional information about the data item it links to. Second, it may tell about the data item that contains the link. Third, it may disclose information about the link itself.

An example of the first type of use is the implementation of two-dimensional sparse arrays in Section 2.2.6. There, the nonzero elements of each row (or column) form a circular linked list anchored in a special list head node. It would have been possible to mark each head node using one of the bits in one of its link fields, but it is more convenient to put this information into the links pointing to a head node. Once the link to the next node in the row is known, a single instruction is sufficient to test for a head node, as for example in the implementation of Program 2.2.6S on page 132:

S3	LDOU	q0,q0,UP	S3. Find new row.	Q0 ← UP(Q0).
	BOD	q0,9F	Exit if Q0 is odd.

If a head node would be marked by using a tag bit in its own UP link, the code would require an extra load instruction:

S3	LDOU	q0,q0,UP	S3. Find new row.	Q0 ← UP(Q0).
	LDOU	t,q0,UP	t ← UP(Q0).
	BOD	t,9F	Exit if TAG(Q0) = 1.

The great disadvantage of this method, so it seems, is the need to maintain all the tag bits in all of the links that point to a head node during the running time of the program. A closer look at the operations a Program like Algorithm 2.2.6S performs will reveal, however, that it inserts and deletes matrix elements but never deletes or creates head nodes. Inserting or deleting matrix elements will just copy existing link values; hence no special coding is required to maintain the tag bits in the links to head nodes.

The second, more common, type of use of a tag field is illustrated by the solution to exercise 2.3.5–4 on page 139. The least significant bit of the ALINK field is used to mark accessible nodes, and the least significant bit of the BLINK field is used to distinguish between atomic and non-atomic nodes. The following snippet taken from this code is typical for testing and setting of these tag bits:

E2	LDOU	x,p,ALINK	E2. Mark P.
	OR	x,x,1
	STOU	x,p,ALINK	MARK(P) ← 1.
E3	LDOU	x,p,BLINK	E3. Atom?
	PBEV	x,E4	Jump if ATOM(P) = 0.

An interesting variation of this use of a tag bit can be seen in exercise 2.2.3–26 on page 23. There, the data structure asks for a variable-length list of links allocated sequentially in memory. Instead of encoding the length of the list somewhere as part of the data structure, the last link of the structure is marked by setting a tag bit. This arrangement leads to very simple code for the traversal of the list.

As a final example, consider the use of tag bits in the implementation of threaded binary trees in Section 2.3.1. There, the RIGHT and LEFT fields of a node might contain “down” links to a left or right subtree, or they might contain “thread” or “up” links to a parent node (see, for example, 2.3.1–(10), page 324 ). Within a tree, there are typically both “up” and “down” links for the same node. Hence, the tag is clearly a property of the link, not the node. Searching down the left branch of a threaded binary tree, as required by step S2 of Algorithm 2.3.1S, which reads “If LTAG(Q) = 0, set Q ← LLINK(Q) and repeat this step,” may take the following simple form:

0H	SET	q,p	Set Q ← LLINK(Q) and repeat step S2.
S2	LDOU	p,q,LLINK	S2. Search to left. p ← LLINK(Q).
	PBEV	p,0B	Jump if LTAG(Q) = 0.

5. Loop Unrolling

The loop shown at the end of the last section has a SET operation that has no computational value; it just reorganizes the data when the code advances from one iteration to the next. A small loop may benefit significantly from eliminating such code by unrolling it or, in the simplest case, doubling it. Doubling the loop adds a second copy of the loop where the registers p and q exchange roles. This leads to

S2	LDOU	p,q,LLINK	S2. Search to left. P ← LLINK(Q).
	BOD	p,1F	If LTAG(Q) ≠ 0, exit the loop.
	LDOU	q,p,LLINK	S2. Search to left. Q ← LLINK(P).
	PBEV	q,S2	If LTAG(P) = 0, repeat step S2.
	SET	q,p	At this point p and q have exchanged roles.
1H	IS	@

The new loop requires 2υ per iteration instead of 3υ. For another example, see the solution to exercise 5.2.1–33 on page 167. Further, Program 6.1Q′ on page 98 illustrates how loop unrolling can benefit loops maintaining a counter variable, and the solution to exercise 6.2.1–10 on page 184 shows how to completely unroll a loop with a small, fixed number of iterations.

6. Subroutines

The code of a subroutine usually starts with the definition of its stack frame, the storage area containing parameters and local variables. Using the MMIX register stack, it is sufficient for most subroutines to list and name the appropriate local registers. Once the stack frame is defined, the instructions that make up the body of the subroutine follow. The first instruction is labeled with the name of the subroutine—typically preceded by a colon to make it global; the last instruction is a POP. For a simple example see the solution to exercise 2.2.3–2 on page 124 or the solution to exercise 5–7 on page 162.

Subroutine Invocation. Calling a subroutine requires three steps: passing of parameters, transfer of control, and handling of return values. In the simplest case, with no parameters and no return values, the transfer of control is accomplished with a single ‘PUSHJ $X,YZ’ instruction and a matching POP instruction. The problem remains choosing a register $X such that the subroutine call will preserve the values of registers belonging to the caller’s stack frame. For this purpose, the subroutines in this book will define a local register, named t, such that all other named local registers have register numbers smaller than t. Aside from its role in calling subroutines, t is used as temporary variable. The typical form of a subroutine call is then ‘PUSHJ t,YZ’.

If the subroutine has n > 0 parameters, the registers for the parameter values can be referenced as t+1, t+2, . . . , t+ n. A simple example is Program 2.3.1T, where the two functions Inorder and Visit are called like this:

T3	LDOU	t+1,p,LLINK	T3. Stack ⇐ P.
	SET	t+2,visit
	PUSHJ	t,:Inorder	Call Inorder(LLINK(P),Visit).
T5	SET	t+1,p	T5. Visit P.
	PUSHGO	t,visit,0	Call Visit(P).

After the subroutine has transferred control back to the caller, it may use the return values. If the subroutine has no return values, register t (and all registers with higher register numbers) will be marginal and a reference to it will yield zero; otherwise, t will hold the principal return value and further return values will be in registers t+1, t+2, . . . . The function FindTag in the solution to exercise 2.5–27 on page 143 is an example of a function with three return values.

Nested Calls. If the return value of one function serves as a parameter for the next function, the schema just described needs some modification. It is better to place the return value of the first function not in register t but directly in the parameter register for the second function; therefore we have to adjust the first function call. For example, the Mul function in Section 2.3.2, page 42, needs to compute Q1 ← Mult(Q1,Copy(P2)), and that is done like this:

SET	t+1,q1	t+1 ← Q1.
SET	t+3,p2
PUSHJ	t+2,:Copy	t+2 ← Copy(P2).
PUSHJ	t,:Mult
SET	q1,t	Q1 ← Mult(Q1,Copy(P2)).

The Div function of exercise 2.3.2–15, which computes the slightly more complex formula

Q ← Tree2(Mult(Copy(P1),Q),Tree2(Copy(P2),Allocate(),“↑”),“/”),

contains more examples of nested function calls (see also the Pwr function of exercise 2.3.2–16).

Nested Subroutines. If one subroutine calls another subroutine, we have a situation known as nested subroutines. The most common error when programming MMIX is failing to save and restore the rJ register. At the start of a subroutine, the special register rJ contains the return address for the POP instruction. It will be rewritten by the next PUSHJ instruction and therefore must be saved if the next PUSHJ occurs before the POP.

There are two preferred places to save and restore rJ: Either start the subroutine with a GET instruction, saving rJ in a local register, and end the subroutine with a PUT instruction, restoring rJ, immediately before the terminating POP instruction; or, if the subroutine contains only a single PUSHJ instruction, save rJ immediately before the PUSHJ and restore it immediately after the PUSHJ. An example of the first method is the Mult function in Section 2.3.2; the second method is illustrated by the Tree2 function in the same section. If subroutines use the PREFIX instruction to create local namespaces, the local copy of ‘:rJ’ can simply be called ‘rJ’; that is the naming convention used in this book.

Tail Call Optimization. The Mult function of Section 2.3.2 is an interesting example for another reason: It uses an optimization called “tail call optimization.” If a subroutine ends with a subroutine call in such a way that the return values of the inner subroutine are already the return values of the outer subroutine, the stack frame of the outer subroutine can be reused for the inner subroutine because it is no longer needed after the call to the inner routine. Technically, this is achieved by moving the parameters into the right place inside the existing stack frame and then using a jump or branch instruction to transfer control to the inner subroutine. The POP instruction of the inner subroutine will then return directly to the caller of the outer subroutine. So, when the function Mult(u,v) wants to return Tree2(u,v,“×”), u and v are already in place and ‘GETA v+1,:Mul’ initializes the third parameter; then ‘BNZ t,:Tree2’ transfers control to the Tree2 function, which will return its result directly to the caller of Mult.

A special case of this optimization is the “tail recursion optimization.” Here, the last call of the subroutine is a recursive call to the subroutine itself. Applying the optimization will remove the overhead associated with recursion, turning a recursive call into a simple loop. For an example, see Program 5.2.2Q on page 82, which uses PUSHJ as well as JMP to call the recursive part Q2.

7. Reporting Errors

There is no good Program without good error handling. The standard situation is the discovery of an error while executing a subroutine. If the error is serious enough, it might be best to issue an error message and terminate the Program immediately. In most cases, however, the error should be reported to the calling Program for further processing.

The most common form of error reporting is the specification of special return values. Most UNIX system calls, for example, return negative values on error and nonnegative values on success. This schema has the advantage that the test for a negative value can be accomplished with a single instruction, not only by MMIX but by most CPUs. Another popular error return value, which can be tested equally well, is zero. For example, functions that return addresses often use zero as an error return, because addresses are usually considered unsigned and the valid addresses span the entire range of possible return values. In most circumstances, it is, furthermore, simple to arrange things in a way that excludes zero from the range of valid addresses.

MMIX offers two ways to return zero from a subroutine: The two instructions ‘SET $0,0; POP 1,0’ will do the job, but just ‘POP 0,0’ is sufficient as well. The second form will turn the register that is expected to contain the return value into a marginal register, and reading a marginal register yields zero (see the solution to exercise 2.2.3–4 on page 125 for an example).

The POP instruction of MMIX makes another form of error reporting very attractive: the use of separate subroutine exits for regular return and for error return (see exercise 2.2.3–3 and its solution on page 125 for an example). The subroutine will end with ‘POP 0,0’ in case of error and with ‘POP 1,1’ in case of success, returning control to the instruction immediately following the PUSHJ in case of error and to the second instruction after the PUSHJ otherwise. The calling sequence must then insert a jump to the error handler just after the PUSHJ while the normal control flow continues with the instruction after the jump instruction. The advantages of this method are twofold. First, the execution of the normal control path is faster because it no longer contains a branch instruction to test the return value. Second, this programming style forces the calling Program to provide explicit error handling; simply skipping the test for an error return will no longer work.

Page 1 of 1

🔖 Save To Your Account

InformIT Promotional Mailings & Special Offers

I would like to receive exclusive offers and hear about products from InformIT and its family of brands. I can unsubscribe at any time.

Privacy Notice

Overview

Pearson Education, Inc., 221 River Street, Hoboken, New Jersey 07030, (Pearson) presents this site to provide information about products and services that can be purchased through this site.

This privacy notice provides an overview of our commitment to privacy and describes how we collect, protect, use and share personal information collected through this site. Please note that other Pearson websites and online products and services have their own separate privacy policies.

Collection and Use of Information

To conduct business and deliver products and services, Pearson collects and uses personal information in several ways in connection with this site, including:

Questions and Inquiries

For inquiries and questions, we collect the inquiry or question, together with name, contact details (email address, phone number and mailing address) and any other additional information voluntarily submitted to us through a Contact Us form or an email. We use this information to address the inquiry and respond to the question.

Online Store

For orders and purchases placed through our online store on this site, we collect order details, name, institution name and address (if applicable), email address, phone number, shipping and billing addresses, credit/debit card information, shipping options and any instructions. We use this information to complete transactions, fulfill orders, communicate with individuals placing orders or visiting the online store, and for related purposes.

Surveys

Pearson may offer opportunities to provide feedback or participate in surveys, including surveys evaluating Pearson products, services or sites. Participation is voluntary. Pearson collects information requested in the survey questions and uses the information to evaluate, support, maintain and improve products, services or sites, develop new products and services, conduct educational research and for other purposes specified in the survey.

Contests and Drawings

Occasionally, we may sponsor a contest or drawing. Participation is optional. Pearson collects name, contact information and other information specified on the entry form for the contest or drawing to conduct the contest or drawing. Pearson may collect additional personal information from the winners of a contest or drawing in order to award the prize and for tax reporting purposes, as required by law.

Newsletters

If you have elected to receive email newsletters or promotional mailings and special offers but want to unsubscribe, simply email information@informit.com.

Service Announcements

On rare occasions it is necessary to send out a strictly service related announcement. For instance, if our service is temporarily suspended for maintenance we might send users an email. Generally, users may not opt-out of these communications, though they can deactivate their account information. However, these communications are not promotional in nature.

Customer Service

We communicate with users on a regular basis to provide requested services and in regard to issues relating to their account we reply via email or phone in accordance with the users' wishes when a user submits their information through our Contact Us form.

Other Collection and Use of Information

Application and System Logs

Pearson automatically collects log data to help ensure the delivery, availability and security of this site. Log data may include technical information about how a user or visitor connected to this site, such as browser type, type of computer/device, operating system, internet service provider and IP address. We use this information for support purposes and to monitor the health of the site, identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents and appropriately scale computing resources.

Web Analytics

Pearson may use third party web trend analytical services, including Google Analytics, to collect visitor information, such as IP addresses, browser types, referring pages, pages visited and time spent on a particular site. While these analytical services collect and report information on an anonymous basis, they may use cookies to gather web trend information. The information gathered may enable Pearson (but not the third party web trend services) to link information with application and system log data. Pearson uses this information for system administration and to identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents, appropriately scale computing resources and otherwise support and deliver this site and its services.

Cookies and Related Technologies

This site uses cookies and similar technologies to personalize content, measure traffic patterns, control security, track use and access of information on this site, and provide interest-based messages and advertising. Users can manage and block the use of cookies through their browser. Disabling or blocking certain cookies may limit the functionality of this site.

Do Not Track

This site currently does not respond to Do Not Track signals.

Security

Pearson uses appropriate physical, administrative and technical security measures to protect personal information from unauthorized access, use and disclosure.

Children

This site is not directed to children under the age of 13.

Marketing

Pearson may send or direct marketing communications to users, provided that

Pearson will not use personal information collected or processed as a K-12 school service provider for the purpose of directed or targeted advertising.
Such marketing is consistent with applicable law and Pearson's legal obligations.
Pearson will not knowingly direct or send marketing communications to an individual who has expressed a preference not to receive marketing.
Where required by applicable law, express or implied consent to marketing exists and has not been withdrawn.

Pearson may provide personal information to a third party service provider on a restricted basis to provide marketing solely on behalf of Pearson or an affiliate or customer for whom Pearson is a service provider. Marketing preferences may be changed at any time.

Correcting/Updating Personal Information

If a user's personally identifiable information changes (such as your postal address or email address), we provide a way to correct or update that user's personal data provided to us. This can be done on the Account page. If a user no longer desires our service and desires to delete his or her account, please contact us at customer-service@informit.com and we will process the deletion of a user's account.

Choice/Opt-out

Users can always make an informed choice as to whether they should proceed with certain services offered by InformIT. If you choose to remove yourself from our mailing list(s) simply visit the following page and uncheck any communication you no longer want to receive: www.informit.com/u.aspx.

Sale of Personal Information

Pearson does not rent or sell personal information in exchange for any payment of money.

While Pearson does not sell personal information, as defined in Nevada law, Nevada residents may email a request for no sale of their personal information to NevadaDesignatedRequest@pearson.com.

Supplemental Privacy Statement for California Residents

California residents should read our Supplemental privacy statement for California residents in conjunction with this Privacy Notice. The Supplemental privacy statement for California residents explains Pearson's commitment to comply with California law and applies to personal information of California residents collected in connection with this site and the Services.

Sharing and Disclosure

Pearson may disclose personal information, as follows:

As required by law.
With the consent of the individual (or their parent, if the individual is a minor)
In response to a subpoena, court order or legal process, to the extent permitted or required by law
To protect the security and safety of individuals, data, assets and systems, consistent with applicable law
In connection the sale, joint venture or other transfer of some or all of its company or assets, subject to the provisions of this Privacy Notice
To investigate or address actual or suspected fraud or other illegal activities
To exercise its legal rights, including enforcement of the Terms of Use for this site or another contract
To affiliated Pearson companies and other companies and organizations who perform work for Pearson and are obligated to protect the privacy of personal information consistent with this Privacy Notice
To a school, organization, company or government agency, where Pearson collects or processes the personal information in a school setting or on behalf of such organization, company or government agency.

Links

This web site contains links to other sites. Please be aware that we are not responsible for the privacy practices of such other sites. We encourage our users to be aware when they leave our site and to read the privacy statements of each and every web site that collects Personal Information. This privacy statement applies solely to information collected by this web site.

Requests and Contact

Please contact us about this Privacy Notice or if you have any requests or questions relating to the privacy of your personal information.

Changes to this Privacy Notice

We may revise this Privacy Notice through an updated posting. We will identify the effective date of the revision in the posting. Often, updates are made to provide greater clarity or to comply with changes in regulatory requirements. If the updates involve material changes to the collection, protection, use or disclosure of Personal Information, Pearson will provide notice of the change through a conspicuous notice on this site or other appropriate way. Continued use of the site after the effective date of a posted revision evidences acceptance. Please contact us if you have questions or concerns about the Privacy Notice or any objection to any revisions.

Last Update: November 17, 2020

Email Address