next up previous
Next: Eliminate BAL and Up: MIT REVERSIBLE COMPUTING PROJECT Previous: Illegal Instructions =

Expanding instructions do XOR

For all the expanding arithmetic/logical operations AND, ANDI, NOR, OR, ORI, SLL, SLLV, SLT, SLTI, SRA, SRAV, SRL, SRLV, the current spec specifies that the destination register must be zero before the operation.

Unfortunately, it is impossible (undecidable) to determine at compile-time whether a given register is actually clear. The user may have arranged through a complicated series of manipulations for the value in a variable to always end up zero, yet there is know way for the compiler to know this.

The compiler could have the policy of always assuming the register is not clear, and pushing its old value onto a garbage stack, or alternatively, the compiler could insert a run-time check of whether the value is clear, and halt the machine if not. But either of these approaches incurs unnecessary inefficiencies in both amount of code used and run time. The garbage stack approach will, even worse, in general asymptotically increase the space requirements of a program beyond what could be achieved otherwise.

The action of halting the machine if the register is not clear could be handled at the hardware level; this could be a reasonable alternative to performing the AND dissipatively, depending on the context. (For debugging, the halt would be better because it would tell you that a precondition had been violated.)

However, we propose a different solution: have all the expanding instructions XOR their result into the destination register, regardless of the destination register's previous value. This is 100% reversible regardless of the data present in any registers.

Moreover, this provision entirely eliminates the need for all the ``Undo'' instructions UAND, UANDI, UNOR, UOR, UORI, USLL, USLLV, USLT, USLTI, USRA, USRAV, USRL, USRLV, since the XOR version of the instructions will undo themselves if repeated.

We propose that the expanding instruction names be changed by appending ``X'' to make their new XOR semantics explicit: ANDX, ANDIX, NORX, ORX, ORIX, SLLX, SLLVX, SLTX, SLTIX, SRAX, SRAVX, SRLX, SRLVX.



next up previous
Next: Eliminate BAL and Up: MIT REVERSIBLE COMPUTING PROJECT Previous: Illegal Instructions =



Michael Frank
Wed Jul 23 13:48:27 EDT 1997