TAOCP 1.4.3.1 Exercise 1

The subroutine `FCHECK` is called whenever an instruction uses a field specification.

taocpmathematicsalgorithmsvolume-1simple

Section 1.4.3.1: A MIX Simulator

Exercise 1. [14] Study all the uses of the FCHECK subroutine in the simulator program. Can you suggest a better way to organize the code? (See step 3 in the discussion at the end of Section 1.4.1.)

Verified: yes
Solve time: 1m20s

Solution

The subroutine FCHECK is called whenever an instruction uses a field specification. The sequence

JMP FCHECK

appears inside GETV, and the resulting values of L and R are then used to isolate the desired field. The special entrance GETAV bypasses FCHECK, because comparison operators already have the fielded quantity in a register instead of memory.

The organization is inefficient because FCHECK performs two logically distinct tasks:

  1. validation of the field specification;
  2. decoding the field into the quantities L and R.

Every use of FCHECK requires both tasks together, even when only validation is logically needed. Furthermore, the subroutine stores L and R into memory locations and reloads L into rI1, although the quantities are already present in registers immediately after the division in line 138.

Step 3 of the discussion at the end of Section 1.4.1 advocates combining operations that naturally belong together, thereby reducing unnecessary transfers and subroutine overhead. Applying that principle here, the better organization is to eliminate FCHECK entirely and absorb its function into GETV.

After line 149, the code may be rewritten as follows:

149 GETV    STJ  9F
150         ENTA 0
151         ENTX 0,3
152         DIV  =8=
153         CMPX =5=
154         JG   FERROR
155         STA  L
156         STX  R
157         LD1  L
158         CMPA R
159         JG   FERROR
160         JMP  MEMORY
161 1H      J1Z  2F
162         ENTX 1
163         SLA  -1,1
164         SRA  -1,1
165 2H      LD2N R
166         SRA  5,2
167 9H      JMP  *

This organization has two advantages.

First, one subroutine linkage disappears. In the original program, the call sequence

JMP GETV
JMP FCHECK
...
JMP MEMORY

requires two subroutine entries and two exits before the actual extraction of the field begins. In the revised organization, the field decoding occurs directly inside GETV, so only the MEMORY subroutine remains.

Second, the control structure becomes more coherent. The routine GETV computes the quantity $V$, and the interpretation of the field specification is an essential part of that computation. Separating the decoding into an independent subroutine obscures the logical unity of the operation.

The resulting code is also slightly shorter. The original organization requires:

  • line 150, JMP FCHECK;
  • line 145, JLE *;
  • line 146, JMP FERROR.

The revised organization replaces these by direct conditional branches within GETV, removing one complete subroutine return.

This completes the proof.

∎