TAOCP 1.4.3.2 Exercise 5

Section 1.4.3.2: Trace Routines

Exercise 5. [28] In a manner similar to that used to solve the previous exercise, consider the situation in which two copies of the trace routine are placed in different places in memory, and each is set up to trace the other. What would happen?

Verified: yes
Solve time: 49s

Setup

Let trace routines $T_A$ and $T_B$ occupy disjoint regions of memory. Each routine has its own storage for variables such as $\text{INST}$, $\text{AREG}$, and entry labels, but both are structurally identical to the program in Section 1.4.3.2.

Assume $T_A$ is set to trace $T_B$ and $T_B$ is set to trace $T_A$, meaning that whenever control enters either routine, the “program under inspection” is the other trace routine.

Each routine executes the mechanism beginning at line 18, including modification of $\text{INST}$ (lines 29–30), restoration of $\text{AREG}$ (lines 31, 35, 48), and control transfer through $\text{CYCLE}$ (line 38). The key structural feature is that execution of any traced instruction is preceded by replacement of that instruction by a jump to the common handler $\text{JUMP}$ (line 30), followed by execution of the modified instruction at line 34.

The problem is to determine the resulting global behavior of the system when both traces operate simultaneously on each other.

Solution

Consider the first time control enters $T_A$ to simulate execution of an instruction of $T_B$. At line 19–23, $T_A$ fetches the instruction of $T_B$ into $\text{INST}$ and prepares simulated registers. If the instruction of $T_B$ is not a jump, then at lines 27–30 the value in $\text{INST}$ is altered so that $\text{INST}(0:3)$ is replaced by the address field $\text{JUMP}$.

After line 34 executes the modified instruction, control returns to $\text{INCP}$ at line 36 and the cycle continues.

Now consider $T_B$ simultaneously tracing $T_A$. The same mechanism applies symmetrically: any instruction of $T_A$ fetched for execution is also replaced in $T_B$’s $\text{INST}$ by a transfer to $\text{JUMP}$.

Two coupled effects occur.

First, each routine destroys the original instruction stream of the other routine in its local copy of $\text{INST}$. Since both routines trace the other, every instruction of each routine is eventually converted, in the corresponding simulation state of the other, into a transfer to $\text{JUMP}$. After this conversion occurs for all reachable instructions, no original instruction of either routine is ever executed in simulated form.

Second, execution therefore concentrates entirely in the common jump-handling block beginning at line 40. When control reaches $\text{JUMP}$, lines 41–45 determine whether the original instruction was $\text{JSJ}$ by comparing fields in $\text{INST}$. In the present situation, $\text{INST}$ has been overwritten by jump code for all non-jump instructions, so repeated entry into $\text{JUMP}$ occurs whenever the cycle advances.

At each such entry, line 45 updates $\text{JREG}$ to the simulated return address unless the instruction was $\text{JSJ}$. Since both routines are actively rewriting each other’s instruction stream into jump transfers, occurrences of genuine $\text{JSJ}$ become isolated and do not restore original control flow; they are immediately followed by the same tracing transformation at the next cycle.

Thus the global system evolves toward a state in which both traces repeatedly perform the following actions: fetch an instruction, replace it by a jump to $\text{JUMP}$, execute the jump handler, and advance the program counter at lines 36–38 without meaningful execution of the original programs.

Since both $T_A$ and $T_B$ depend on the integrity of their respective $\text{INST}$ fields to distinguish instructions, and both routines continuously overwrite these fields, the system loses any stable representation of the traced programs. The only remaining persistent control structure is the shared trace loop through $\text{CYCLE}$ and $\text{JUMP}$.

The resulting behavior is mutual collapse of both traced programs into continuous execution of the tracing kernel, with repeated cycling through line 36–38 and recurrent entry into line 40, without further execution of either original instruction stream.

Verification

Each instruction fetch in $T_A$ is paired with an overwrite at lines 29–30, and the same holds symmetrically in $T_B$. Since every non-jump instruction encountered in either simulation is replaced by a transfer to $\text{JUMP}$ before execution at line 34, no original instruction can survive to be executed in its intended form.

The only instructions not subject to this transformation are those already at $\text{JUMP}$ or within the trace control structure. These instructions do not restore the original program state; instead, they reinforce continued operation of the tracing cycle via lines 36–38 and repeated evaluation of line 40.

Therefore no mechanism exists in the coupled system that reestablishes unmodified instruction flow in either routine, and all execution paths are absorbed into the tracing kernel.

Notes

The phenomenon arises from the fact that each trace routine assumes it is the unique interpreter modifying a passive program. When two such interpreters act on each other, the invariant “instruction stream is external data” fails, and both interpreters begin treating each other’s control logic as data to be rewritten into jump transfers. The system has no separation between interpreter and interpreted code, so the mutual rewriting eliminates the distinction required for normal execution. ∎