Bob Reversible ISA - About Reversibility

Reversibility in computing is the notion that all operations can be undone. Another way to look at it is this, say some program is a function taking some arguments and returns a result. Now we would like to put in arguments and obtain a result. But we would also like to put in the result, undo the function and obtain the arguments.

The naive approach

Given some set of instructions that makes up for a program the naive approach is to keep track of every instruction calculated by adding a trace. This is called a Landuaer embedding.

Local reversibilty

Instead of a total trace we ensure that every instruction has an inverse. This amounts to show that every instructions is injective - we allow undefined behavior of instructions in some situations. By ensuring that some program is made up of local reversible parts, we actually have a reversible program in total.

Locally reversible model

Normally one would have a special purpose register called a program counter (pc for shorts) to keep track of which instruction currently is executing. When doing a jump, the pc is set to the address of the target label. However more than one jump can target the same label. In this case a jump clearly is not injective. This is accounted for by adding yet two registers, a branch register and a direction register, in which the relative jump value and the direction of execution is set, respectively. Now when execution continues after a jump, we have the information needed to know from where we jumped.

Locally reversible instructions

First and foremost we need to do without the mov instruction known from other ISA's. Say we execute

In the post code $reg1 = $reg2, that is we have no way of knowing the pre code value of $reg1 in the post code. This can to some extend be seen as the function f(x) = constant - this is clearly not injective.

Instead of moving integers into registers, we use XORI - that is we exclusive or some integer into the target register. Exclusive or is self-inverse. That is it has itself as inverse instruction.

Instead of moving values from registers into memory, we exchange them. Exchanging is self inverse.

For arithmetic operators we have a way of dealing with non-injective ones. For example if we take multiplication. Say we multiply as thus

And say that $reg2 = 0. Now we have $reg1 = $reg2 = 0 in the post code and no way of telling what the value of $reg1 was in the pre code. This can be overcome by adding an extra register in which the result is XOR'ed into. XOR has itself as inverse, and by doing this trick the core instruction of multiplication is exclusive or.

For instructions in general we need to avoid having the same register as target and destination. For example given

In the post code $reg1 = 0, and we have no way of telling what the value of this register was in the pre code.

The need for zero-clearing

Since we do not have access to a MOV instruction, we need to zero-clear all registers and memory slots that we have used. If not, during next execution of the next program we might exclusive or some value into a register that isn't zero-cleared, and we end up storing some unknown value in that register. This results in undefined behavior. Even locally, if we do not zero-clear registers during a loop, we can end up with undefined behavior.