TAOCP 1.4.3.2 Exercise 2

The trace routine in Section 1.

taocpmathematicsalgorithmsvolume-1hard

Section 1.4.3.2: Trace Routines

Exercise 2. [26] Modify the trace routine of the text so that before executing each program step it writes the following information on tape unit 0.

Word 1, (0:2) field: location.
Word 1, (4:5) field: register J (before execution).
Word 1, (3:3) field: 2 if comparison is greater, 1 if equal, 0 if less; plus 8 if overflow is not on before execution.
Word 2: instruction.
Word 3: register A (before execution).
Words 4-9: registers I1-I6 (before execution).
Word 10: register X (before execution).

Words 11-100 of each 100-word tape block should contain nine more ten-word groups, in the same format.

Verified: no
Solve time: -

Setup

The trace routine in Section 1.4.3.2 must be modified so that, immediately before each instruction of the traced program is executed, a ten-word record is written onto tape unit $0$. Each record is to contain:

$$ \begin{array}{ll} \text{Word 1 }(0{:}2) & \text{location;}\ \text{Word 1 }(3{:}3) & 2,1,0\text{ according as comparison is }>,=,<,\ & \text{plus }8\text{ if overflow is not on;}\ \text{Word 1 }(4{:}5) & \text{register }J\text{ before execution;}\ \text{Word 2} & \text{instruction;}\ \text{Word 3} & \text{register }A\text{ before execution;}\ \text{Words 4, 9} & \text{registers }I_1,\ldots,I_6\text{ before execution;}\ \text{Word 10} & \text{register }X\text{ before execution.} \end{array} $$

Furthermore, words $11$--$100$ of each tape block are to contain nine additional records in the same format. Thus each block contains exactly ten records.

The original trace routine already preserves all registers except $J$ and executes the traced instruction at label INST. The problem is to insert a recording mechanism without disturbing the state of the traced program.

Solution

The modifications are made in three parts.

First, a $100$-word buffer is reserved, together with a pointer that advances by ten words after each instruction. When the pointer reaches the end of the block, the complete $100$ words are written on tape unit $0$, and the pointer is reset to the beginning of the buffer.

Second, immediately before line 34 of the trace routine, the required information is copied into the current ten-word record. Since the trace routine already guarantees that all registers except $J$ contain the values belonging to the traced program, the data can be copied directly. The simulated contents of register $A$ are already stored in AREG; register $J$ is represented by JREG.

Third, the comparison indicator and overflow toggle must be encoded into word $1(3{:}3)$. The comparison indicator may be tested by the three-way jumps JL, JE, JG; the overflow toggle may be tested by JOV. The specified code is:

$$ 0 \text{ for }<,\qquad 1 \text{ for }=,\qquad 2 \text{ for }> $$

and

$$ +8 $$

when overflow is not on.

The following additions suffice.

PTR     CON  BUFFER              Current position in tape buffer
COUNT   CON  0                   Number of entries in current block
BUFFER  BSS  100                 Ten records of ten words each

TRACE   LDX  PTR                 X1 <- beginning of current record

        LDA  PREG(0:2)           Word 1(0:2): location
        STA  0,1(0:2)

        LDA  JREG(0:2)           Word 1(4:5): register J
        STA  0,1(4:5)

        ENTA 0                   Prepare comparison code
        JL   LESS
        JE   EQUAL
        ENTA 2
        JMP  CMPDONE
EQUAL   ENTA 1
        JMP  CMPDONE
LESS    ENTA 0
CMPDONE JOV  OVRON
        INCA 8                   Overflow not on
OVRON   STA  0,1(3:3)

        LDA  INST                Word 2: instruction
        STA  1,1

        LDA  AREG                Word 3: register A
        STA  2,1

        ST1  3,1                 Words 4-9: I1-I6
        ST2  4,1
        ST3  5,1
        ST4  6,1
        ST5  7,1
        ST6  8,1

        STX  9,1                 Word 10: register X

        LDA  PTR                 Advance pointer by 10 words
        INCA 10
        STA  PTR

        LDA  COUNT               Count records in block
        INCA 1
        STA  COUNT
        CMPA =10=
        JNE  CONT

        OUT  BUFFER(0:99),0      Write completed block
        ENTA BUFFER
        STA  PTR
        ENTA 0
        STA  COUNT

CONT    NOP                      Resume original trace routine

The call to TRACE is inserted immediately before line 34:

        JSJ  TRACE
INST    NOP  *

The location of the call is forced by the requirements of the exercise. At this point:

  1. PREG contains the location of the instruction to be executed.
  2. INST contains the actual instruction.
  3. AREG contains the simulated value of register $A$ before execution.
  4. Registers $I_1,\ldots,I_6,X$ contain their actual values before execution.
  5. JREG contains the simulated value of register $J$.
  6. The comparison indicator and overflow toggle still reflect the external program, by property (3) of the section.

Hence the recorded information is precisely the state immediately before execution.

The buffer length is determined as follows. Each record occupies exactly ten words. A tape block contains exactly one hundred words. Therefore

$$ 100 \div 10 = 10 $$

records fit in one block. After the tenth entry, the routine performs one OUT instruction and resets the pointer to the first word of BUFFER.

Verification

The format of each ten-word record is checked directly.

Word $1(0{:}2)$ is filled from PREG(0:2), hence it equals the instruction location. Word $1(4{:}5)$ is filled from `JREG(0:2)$, hence it equals the simulated contents of register $J$ before execution.

Word $1(3{:}3)$ is determined by case analysis. If the comparison indicator is less, equal, or greater, the routine stores respectively $0$, $1$, or $2$. If overflow is not on, $8$ is added before storage. Therefore the resulting digit is exactly the required encoding.

Word $2$ receives INST, which is the instruction about to execute. Word $3$ receives AREG, which contains register $A$ before execution. Words $4$ through $9$ are obtained directly from ST1 through ST6, hence contain $I_1,\ldots,I_6$. Word $10$ receives register $X$.

The block structure is also correct. The pointer advances by ten words after each instruction. After exactly ten records, since

$$ 10 \times 10 = 100, $$

the buffer is full, and the routine writes words $0$ through $99$ to tape unit $0$. The counter and pointer are then reset, so the next record begins a new block.

The added code does not alter the program state seen by the traced computation. The trace routine continues to use only internal storage and does not modify the external comparison indicator or overflow toggle. Register values are copied, not changed. Therefore the traced program executes exactly as before, except for the intended delay caused by tracing.

Notes

A shorter implementation is possible if space is valued more highly than time, as recommended in the text. For example, the comparison-indicator encoding may be compressed by suitable arithmetic on branch destinations, and the buffer counter may be eliminated by comparing PTR directly against the address BUFFER+100.