%======================================================================
% pisa.tex - The Pendulum Instruction Set Architecture
%======================================================================

%----------------------------------------------------------------------
% Macro definitions.

% 1st arg: instruction name
% 2nd arg: textual description
% 3rd arg: usage
% 4th arg: arguments
% After macro, give a textual description.
\newcommand{\instruction}[4]{
{
\setlength{\parskip}{5pt}
\setlength{\parindent}{0in}
\vskip 10pt
\hrule
\vskip 5pt
{\bf\LARGE\tt #1}\hfill\begin{minipage}{4in}\begin{flushright}#2\end{flushright}\end{minipage}
\begin{description}
\item[Usage: ] 
\begin{minipage}[t]{5in}
{\tt
\begin{tabbing}
#3
\end{tabbing}
}
\end{minipage}
\item[Arguments:]\ 
\begin{description}
#4
\end{description}
\item[Description:]
\end{description}
}}

%----------------------------------------------------------------------
% Body

\chapter{The Pendulum instruction set architecture (PISA)}
\markboth{APPENDIX \thechapter. THE PISA ARCHITECTURE}
         {APPENDIX \thechapter. THE PISA ARCHITECTURE}
\label{ch:pisa}

\def\draftid{$\ $Id: pisa.tex,v 1.3.2.3.2.1 1999/05/11 19:54:57 mpf Exp $\ $}

This appendix gives a detailed description of the assembly language
instruction set for the Pendulum reversible microprocessor currently being
fabricated by Carlin Vieri {\cite{Vieri-99}.  Some reversible instruction
set issues encountered during the development of this instruction set
(which I assisted Vieri with) were discussed in~\S{\ref{ch:program}}.  The
version of the instruction set described here was the target for the
compiler described in~\S\ref{sec:rcomp} and appendix~{\ref{ch:rcomp}}.

Vieri's thesis describes these instructions at a more detailed level, that
gives the precise instruction word layout for purposes of machine code
assembly and instruction decoding in his real hardware implementation.  For
our purposes of testing compiler techniques, such details were unimportant.
Thus, in this reference we only describe the instructions from an assembly
language programmer's point of view.

\section{Overall organization}

The PISA instruction set can be divided into three categories: reversible
artihmetic/logical operations, ordinary branch instructions, and special
instructions.  

\begin{figure}
{\footnotesize
\begin{verbatim}
Key:
rsd,rt = 5-bit register identifier. 
  No-Op if rsd is same reg as rt.
imm,amt = 16 bit signed immediate
  [imm] = imm sign-extended to 32 bits

"Non-expanding" arith./logical operations:

Mnem.   Args.      Forwards behavior
-----   ---------  ---------------------
NEG     rsd        rsd = -rsd
ADD     rsd,rt     rsd += rt (mod 2^32)
ADDI    rsd,imm    rsd += [imm] (mod 2^32)
SUB     rsd,rt     rsd -= rt (mod 2^32)
XOR     rsd,rt     rsd ^= rt
XORI    rsd,imm    rsd ^= [imm]
RL      rsd,amt    rsd = rsd rol amt
RLV     rsd,rt     rsd = rsd rol rt
RR      rsd,amt    rsd = rsd ror amt
RRV     rsd,rt     rsd = rsd ror rt
\end{verbatim}}
\caption[``Non-expanding'' arithmetic/logical operations]{``Non-expanding''
arithmetic/logical operations in the 32-bit simulator/compiler version of
the PISA instruction set.}
\label{f:nonex}
\vspace{.1in}
\hrule
\end{figure}

The set of arithmetic/logical operations is designed to be logically
complete, yet purely reversible.  To achieve this, the results of
operations are generally XOR'ed into separate destination registers, an
operation which can be inverted by simply repeating it.  Certain
``non-expanding'' operations can be performed reversibly without a separate
destination register.

\begin{figure}
{\footnotesize
\begin{verbatim}
Key:
rd,rs,rt = 5-bit register identifier. 
  No-Op if rd is same reg as rs or rt.
imm,amt = 16 bit signed immediate
  [imm] = imm sign-extended to 32 bits

"Expanding" arith./logical operations:

Mnem.   Args.      Forwards behavior
-----   ---------  ---------------------
ANDX    rd,rs,rt   rd ^= rs&rt
ANDIX   rd,rs,imm  rd ^= rs&[imm]
NORX    rd,rs,rt   rd ^= ~(rs|rt)
ORX     rd,rs,rt   rd ^= rs|rt
ORIX    rd,rs,imm  rd ^= rs|[imm]
SLLX    rd,rs,amt  rd ^= rs<<amt
SLLVX   rd,rs,rt   rd ^= rs<<rt
SLTX    rd,rs,rt   rd ^= (rs<rt)?1:0
SLTIX   rd,rs,imm  rd ^= (rs<imm)?1:0
SRAX    rd,rs,amt  rd ^= rs>>amt
SRAVX   rd,rs,rt   rd ^= rs>>rt
SRLX    rd,rs,amt  rd ^= (unsigned)rs>>amt
SRLVX   rd,rs,rt   rd ^= (unsigned)rs>>rt
\end{verbatim}}
\caption[``Expanding'' arithmetic/logical operations]{``Expanding''
arithmetic/logical operations in the PISA instruction set.}
\label{f:expinst}
\vspace{.1in}
\hrule
\end{figure}

As for the branch instructions, these are designed to be used in pairs,
where each branch instruction points to a corresponding branch that points
back to the original instruction, as per the discussion
in~\S\ref{sec:branchpair}.  Given this, one way to implement branches
reversibly is to have the branch instruction add its offset into a special
``branch register'' which is normally zero.  Between instructions, if the
branch register is non-zero, the program counter increments by the branch
register value, instead of by the normal 1 instruction.  Then the branch at
the destination executes, canceling out the value stored in the branch
register and resuming normal execution.

\begin{figure}
{\footnotesize
\begin{verbatim}
Key:
rd,ra,rb = 5-bit register identifier. 
off = 16 bit signed offset
loff = 26 bit signed offset
dir = +1/-1 bit where +1=forward, -1=reverse
BR = internal "branch register"

Branch instructions:

BEQ     ra,rb,off  if ra=rb, BR+=off*dir
BGEZ    rb,off     if rb>=0, BR+=off*dir
BGTZ    rb,off     if rb>0, BR+=off*dir
BLEZ    rb,off     if rb<=0, BR+=off*dir
BLTZ    rb,off     if rb<0, BR+=off*dir
BNE     ra,rb,off  if ra!=rb, BR+=off*dir
BRA     loff       BR+=loff*dir
RBRA    loff       dir=-dir, BR+=loff*dir
SWAPBR  r          r<->BR

PC update between instructions:
  if (BR=0) pc+=dir else pc+=BR*dir

Memory & I/O instructions:

EXCH    rd,ra      rd <-> mem[ra]
READ    ra         ra ^= next word from input str.
SHOW    ra         Copies ra to output stream.
EMIT    ra         Emit ra to garbage stream.
\end{verbatim}}
\caption[Branch and I/O operations]{Branching, memory access, and
input/output operations in the PISA instruction set.}
\label{f:miscinst}
\vspace{.1in}
\hrule
\end{figure}

In this scheme, even if the programmer forgets to put in the branch at the
destination, the resulting behavior will still be reversible.  But it will
not be useful behavior: the program counter will jump forward through the
program in repeated leaps, of size equal to the original offset.

To implement subroutine calls, the branch destination can be the special
SWAPBR instruction, which exchanges the branch register with an empty
register.  The body of the subroutine negates the register, so when the
subroutine hits the next SWAPBR it branches back to the location it came
from; the branch at that location cancels out the branch register and the
processor continues sequentially.  SWAPBR can also be used in a
complementary way to perform switch statements.

All memory access happens through the EXCH instruction which exchanges a
register with a variable memory location.  There is an interesting case
here, in which an EXCH instruction tries to exchange {\emph{itself}} with a
memory location.  The machine can be designed to do nothing in such a case.
Or, if the instruction fetch/unfetch mechanism works via an exchange, the
register will actually be exchanged with the single constantly-moving value
that sits in the instruction register between instructions, and in the
current PC location in memory during instructions.

The processor direction can be reversed in software using the special RBRA
(reversing branch) instruction, which toggles the processor direction bit
while it is performing BRA functionality.  This allows subroutines to be
called either forwards or in reverse, thus reducing the need for repeated
code.

Special instructions to perform reversible output are also available---the
SHOW instruction which just exports a copy of a register, and the EMIT
instruction which actually reversibly sends the information in the register
out of the processor to whatever system it is embedded in.  Input
instructions could also be defined, and there could be two types: a SEE
instruction which just XOR's an input word into a register, but does not
consume it (the external system would be responsible for disposing of the
original) and a TAKE instruction which would reversibly consume the outside
information and bring it into a register, would have to be initially clear.
Another option would just be a single IOEX instruction which simply
exchanges a register with the value currently present in the external I/O
system, which could then move the old value to its output, and move a new
value into place from its input.

Finally, there are START/FINISH instructions for marking the
start/endpoints of programs when running in the simulation environment.
Presumably, a real processor would always be running its operating system,
and would never need to halt.

Let us now give all the instructions, in a reference format.

\section{List of Instructions}

Figures~\ref{f:nonex}, \ref{f:expinst}, and \ref{f:miscinst} list the name,
arguments, and forwards behavior of all the instructions in the 32-bit
version of the PISA instruction set that was used in the Pendulum simulator
and the R language compiler.

\clearpage
\section{Arithmetic/logical ops}

%----------------------------------------------------------------------
\instruction{ADD}{Add one register into another.}{
ADD $reg_d$ $reg_s$
}{
\item[$reg_d$ ---] The destination register.
\item[$reg_s$ ---] The source register.
}

Adds the value of register $reg_s$ into register $reg_d$, that is, modifies
$reg_d$ be equal to the previous value of $(reg_d + reg_s) \bmod 2^{32}$.
Note that this operation is inherently reversible, no matter the previous
values of $reg_d$ and $reg_s$.  It is inverted by SUB with the same
arguments.

%----------------------------------------------------------------------
\instruction{ADDI}{Add an immediate value into a register.}{
ADDI $reg_d$ $imm$
}{
\item[$reg_d$ ---] The destination register.
\item[$imm$ ---] The immediate value to be added into $reg_d$.
}

Sign-extends the immediate 16-bit value $imm$ to 32 bits and adds it into
$reg_d$.  That is, $reg_d \leftarrow (reg_d + imm) \bmod 2^{32}$.  Note
that this operation is inherently reversible, no matter the previous value
of $reg_d$.  It is inverted by another ADDI with the immediate value
negated, or by doing NEG of $reg_d$ followed by the identical ADDI,
followed by another NEG of $reg_d$.

%----------------------------------------------------------------------
\instruction{ANDX}{Exclusive-OR the result of an AND into a register.}{
ANDX $reg_d$ $reg_{s1}$ $reg_{s2}$
}{
\item[$reg_d$ ---] The destination register.
\item[$reg_{s1}$ ---] The first source operand.
\item[$reg_{s2}$ ---] The second source operand.
}

Computes the bitwise logical AND of the contents of $reg_{s1}$ and $reg_{s2}$,
and exclusive-OR's the result into register $reg_d$.  That is, $reg_d
\leftarrow reg_d \oplus (reg_{s1} \wedge reg_{s2})$.  Note that due to the
XOR, this operation is inherently reversible, no matter the previous values
of the registers.  It is inverted by repeating the exact same instruction
again.  Note also that plain AND may be emulated by letting $reg_d$ be a
register that was previously 0.  ANDX corresponds to 32 Toffoli gates
operating in parallel on the corresponding bits of the 3 operands.

%----------------------------------------------------------------------
\instruction{ANDIX}{XOR an AND with an immediate value into a register.}{
ANDIX $reg_d$ $reg_s$ $imm$
}{
\item[$reg_d$ ---] The destination register.
\item[$reg_s$ ---] The source register.
\item[$imm$ ---] The immediate value to AND with.
}

Like ANDX, except the source register is AND'ed with the immediate value
$imm$ instead of with a second source register.

%----------------------------------------------------------------------
\instruction{NORX}{Exclusive-OR the result of a NOR into a register.}{
NORX $reg_d$ $reg_{{s1}}$ $reg_{s2}$
}{
\item[$reg_d$ ---] The destination register.
\item[$reg_{s1}$ ---] The first source operand.
\item[$reg_{s2}$ ---] The second source operand.
}

Computes the bitwise logical NOR of the contents of $reg_{s1}$ and $reg_{s2}$,
and exclusive-OR's the result into register $reg_d$.  That is, $reg_d
\leftarrow reg_d \oplus \overline{(reg_{s1} \vee reg_{s2})}$.  Note that due to the
XOR, this operation is inherently reversible, no matter the previous values
of the registers.  It is inverted by repeating the exact same instruction
again.

For no particular reason, there are no corresponding NORIX, NANDX, or
NAND\-IX instructions.  I believe this was just to keep the instruction set
smaller.  But NORX itself is not strictly necessary either, since one can
emulate it by using ORX and then XORI'ing $-1$ into the result.

%----------------------------------------------------------------------
\instruction{NEG}{Two's-complement negate the given register.}{
NEG $reg_{sd}$
}{
\item[$reg_{sd}$ ---] The source/destination register.
}

Replace the contents of $reg_{sd}$ with its (two's complement) negative.
That is, $reg_{sd} \leftarrow (2^{32} - reg_{sd}) \bmod 2^{32}$.  Note that
this operation is inherently reversible.  It is its own inverse.

%----------------------------------------------------------------------
\instruction{ORX}{Exclusive-OR the result of an OR into a register.}{
ORX $reg_d$ $reg_{{s1}}$ $reg_{s2}$
}{
\item[$reg_d$ ---] The destination register.
\item[$reg_{s1}$ ---] The first source operand.
\item[$reg_{{s2}}$ ---] The second source operand.
}

Computes the bitwise logical OR of the contents of $reg_{s1}$ and
$reg_{s2}$, and exclusive-OR's the result into register $reg_d$.  That is,
$reg_d \leftarrow reg_d \oplus (reg_{s1} \vee reg_{s2})$.  Note that due to
the XOR, this operation is inherently reversible, no matter the previous
values of the registers.  It is inverted by repeating the exact same
instruction again.  Note also that plain AND may be emulated by letting
$reg_d$ be a register that was previously 0.

%----------------------------------------------------------------------
\instruction{ORIX}{XOR an OR with an immediate value into a register.}{
ORIX $reg_d$ $reg_s$ $imm$
}{
\item[$reg_d$ ---] The destination register.
\item[$reg_s$ ---] The source register.
\item[$imm$ ---] The immediate value to AND with.
}

Like ORX, except the source register is AND'ed with the immediate value
$imm$ instead of with a second source register.

%----------------------------------------------------------------------
\instruction{RL}{Rotate a register left by a fixed number of bits.}{
RL $reg_{sd}$ $amt$
}{
\item[$reg_{sd}$ ---] The source/destination register.
\item[$amt$ ---] The immediate number of bits to rotate by.
}

Rotate the bits in register $reg_{sd}$ left (that is, in the direction from
least-significant positions to most-significant positions) by the given
number of places (0-31).  Bits rotated off the left end of the word rotate
back onto the right end.  RL is inherently reversible; it is inverted by RR
$amt$, or by RL'ing by the amount $(32-amt)\bmod 32$.

%----------------------------------------------------------------------
\instruction{RLV}{Rotate a register left by a variable number of bits.}{
RLV $reg_{sd}$ $reg_{t}$
}{
\item[$reg_{sd}$ ---] The source/destination register.
\item[$reg_{t}$ ---] The register giving the number of bits to rotate by.
}

Rotate the bits in register $reg_{sd}$ left (that is, in the direction from
least-significant positions to most-significant positions) by the number of
places given by $reg_t \bmod 32$.  Bits rotated off the left end of the
word rotate back onto the right end.  RLV is inherently reversible; it is
inverted by RRV.

%----------------------------------------------------------------------
\instruction{RR}{Rotate a register right by a fixed number of bits.}{
RR $reg_{sd}$ $amt$
}{
\item[$reg_{sd}$ ---] The source/destination register.
\item[$amt$ ---] The immediate number of bits to rotate by.
}

Rotate the bits in register $reg_{sd}$ right (that is, in the direction
from most-significant positions to least-significant positions) by the
given number of places (0-31).  Bits rotated off the right end of the word
rotate back onto the left end.  RR is inherently reversible; it is inverted
by RL $amt$, or by RR'ing by the amount $(32-amt)\bmod 32$.

%----------------------------------------------------------------------
\instruction{RRV}{Rotate a register right by a variable number of bits.}{
RRV $reg_{sd}$ $reg_{t}$
}{
\item[$reg_{sd}$ ---] The source/destination register.
\item[$reg_{t}$ ---] The register giving the number of bits to rotate by.
}

Rotate the bits in register $reg_{sd}$ right (that is, in the direction
from most-significant positions to least-significant positions) by the
number of places given by $reg_t \bmod 32$.  Bits rotated off the right end
of the word rotate back onto the left end.  RRV is inherently reversible;
it is inverted by RLV.

%----------------------------------------------------------------------
\instruction{SLLX}{XOR with result of shifting a register left logically by
a fixed number of bits.}{
SLLX $reg_d$ $reg_s$ $amt$
}{
\item[$reg_d$ ---] The destination register.
\item[$reg_s$ ---] The source register.
\item[$amt$ ---] The immediate number of bits to shift by.
}

Logically shifts the given register left by $amt$, filling in 0's on the
right, and XOR's the result into the destination register $reg_d$.  Note
that since the shift operation is information-losing, we cannot put the
result back into the same register.  Instead, we XOR the result into a
register as with NANDX and other operations.

%----------------------------------------------------------------------
\instruction{SLLVX}{XOR with result of shifting a register left logically by
a variable number of bits.}{
SLLVX $reg_d$ $reg_s$ $reg_t$
}{
\item[$reg_d$ ---] The destination register.
\item[$reg_s$ ---] The source register.
\item[$reg_t$ ---] Register specifying amount to shift by.
}

Like SLLX but with a variable number of bits.  See RLV.

%----------------------------------------------------------------------
\instruction{SRAX}{XOR with result of shifting a register right
arithmetically by a fixed number of bits.}{
SRAX $reg_d$ $reg_s$ $amt$
}{
\item[$reg_d$ ---] The destination register.
\item[$reg_s$ ---] The source register.
\item[$amt$ ---] The immediate number of bits to shift by.
}

Arithmetically shifts the given register right by $amt$, filling in with
copies of the leftmost bit, and XOR's the result into the destination
register $reg_d$.  Note that since the shift operation is
information-losing, we cannot put the result back into the same register.
Instead, we XOR the result into a register as with NANDX and other
operations.

%----------------------------------------------------------------------
\instruction{SRAVX}{XOR with result of shifting a register right 
arithmetically by a variable number of bits.}{
SLLVX $reg_d$ $reg_s$ $reg_t$
}{
\item[$reg_d$ ---] The destination register.
\item[$reg_s$ ---] The source register.
\item[$reg_t$ ---] Register specifying amount to shift by.
}

Like SRAX but with a variable number of bits.  See RLV.

%----------------------------------------------------------------------
\instruction{SRLX}{XOR with result of shifting a register right logically by
a fixed number of bits.}{
SRLX $reg_d$ $reg_s$ $amt$
}{
\item[$reg_d$ ---] The destination register.
\item[$reg_s$ ---] The source register.
\item[$amt$ ---] The immediate number of bits to shift by.
}

Logically shifts the given register right by $amt$, filling in 0's on the
left, and XOR's the result into the destination register $reg_d$.  Note
that since the shift operation is information-losing, we cannot put the
result back into the same register.  Instead, we XOR the result into a
register as with NANDX and other operations.

%----------------------------------------------------------------------
\instruction{SRLVX}{XOR with result of shifting a register right logically by
a variable number of bits.}{
SRLVX $reg_d$ $reg_s$ $reg_t$
}{
\item[$reg_d$ ---] The destination register.
\item[$reg_s$ ---] The source register.
\item[$reg_t$ ---] Register specifying amount to shift by.
}

Like SRLX but with a variable number of bits.  See RLV.

%----------------------------------------------------------------------
\instruction{SUB}{Subtract one register from another.}{
SUB $reg_d$ $reg_s$
}{
\item[$reg_d$ ---] The destination register.
\item[$reg_s$ ---] The source register.
}

Subtracts the value of register $reg_s$ from register $reg_d$, that is,
modifies $reg_d$ be equal to the previous value of $(reg_d - reg_s +
2^{32}) \bmod 2^{32}$.  Note that this operation is inherently reversible,
no matter the previous values of $reg_d$ and $reg_s$.  It is inverted by
ADD with the same arguments.

%----------------------------------------------------------------------
\instruction{XOR}{Exclusive-OR one register into another.}{
XOR $reg_d$ $reg_s$
}{
\item[$reg_d$ ---] The destination register.
\item[$reg_s$ ---] The source register.
}

Exclusive-OR $reg_s$ into $reg_d$, that is, sets $reg_d$ equal to $reg_d
\oplus reg_s$.  This is a self-reversible operation.

%----------------------------------------------------------------------
\instruction{XORI}{Exclusive-OR an immediate value into a register.}{
XORI $reg_d$ $imm$
}{
\item[$reg_d$ ---] The destination register.
\item[$imm$ ---] The immediate value to XOR with.
}

Exclusive-OR the 16-bit immediate value $imm$ into $reg_d$, that is, sets
$reg_d$ equal to $reg_d \oplus imm$.  Self-reversible.

\section{Ordinary branches}

%----------------------------------------------------------------------
\instruction{BEQ}{Branch if equal.}{
BEQ $reg_a$ $reg_b$ $off$
}{
\item[$reg_a$, $reg_b$ ---] Registers to compare.
\item[$off$ ---] Immediate offset.
}

If the contents of registers $reg_a$ and $reg_b$ are equal, arrange to
branch to an instruction $off$ steps ahead of the current instruction.
That is, add the signed 16-bit value $off$ into the branch register.  The
destination must be a branch pointing back to the current location, or a
SWAPBR.

%----------------------------------------------------------------------
\instruction{BGEZ}{Branch if greater than or equal to zero.}{
BGEZ $reg_a$ $off$
}{
\item[$reg_a$ ---] Register to compare.
\item[$off$ ---] Immediate offset.
}

If the value in register $reg_a$, interpreted in two's complement form, is
greater than or equal to zero (that is, if its high bit is 0), then branch
to an instruction $off$ steps ahead of the current instruction.
That is, add the signed 16-bit value $off$ into the branch register.
The destination must be a branch pointing back to the current location, or a
SWAPBR.

%----------------------------------------------------------------------
\instruction{BGTZ}{Branch if greater than zero.}{
BGTZ $reg_a$ $off$
}{
\item[$reg_a$ ---] Register to compare.
\item[$off$ ---] Immediate offset.
}

If the value in register $reg_a$, interpreted in two's complement form, is
greater than zero (that is, if it is not zero but its high bit is 0), then
branch to an instruction $off$ steps ahead of the current instruction.
That is, add the signed 16-bit value $off$ into the branch register.
The destination must be a branch pointing back to the current location, or a
SWAPBR.

%----------------------------------------------------------------------
\instruction{BLEZ}{Branch if less than or equal to zero.}{
BLEZ $reg_a$ $off$
}{
\item[$reg_a$ ---] Register to compare.
\item[$off$ ---] Immediate offset.
}

If the value in register $reg_a$, interpreted in two's complement form, is
less than or equal to zero (that is, if it is zero or its high bit is 1),
then branch to an instruction $off$ steps ahead of the current instruction.
That is, add the signed 16-bit value $off$ into the branch register.
The destination must be a branch pointing back to the current location, or a
SWAPBR.

%----------------------------------------------------------------------
\instruction{BLTZ}{Branch if less than zero.}{
BLTZ $reg_a$ $off$
}{
\item[$reg_a$ ---] Register to compare.
\item[$off$ ---] Immediate offset.
}

If the value in register $reg_a$, interpreted in two's complement form, is
less than zero (that is, if its high bit is 1), then branch to an
instruction $off$ steps ahead of the current instruction.
That is, add the signed 16-bit value $off$ into the branch register.
The destination must be a branch pointing back to the current location, or a
SWAPBR.

%----------------------------------------------------------------------
\instruction{BNE}{Branch if not equal to zero.}{
BNE $reg_a$ $reg_b$ $off$
}{
\item[$reg_a$, $reg_b$ ---] Registers to compare.
\item[$off$ ---] Immediate offset.
}

If the contents of registers $reg_a$ and $reg_b$ are equal, then branch to
an instruction $off$ steps ahead of the current instruction.
That is, add the signed 16-bit value $off$ into the branch register.
The destination must be a branch pointing back to the current location, or a
SWAPBR.

%----------------------------------------------------------------------
\instruction{BRA}{Unconditional branch.}{
BRA $loff$
}{
\item[$loff$ ---] Long immediate offset.
}

Unconditionally branch to a location $loff$ steps ahead of the current
instruction.  That is, add the signed value $loff$ into the branch
register.  The value $loff$ is a signed long immediate value, with more
bits than the short offsets in the various conditional branches above.  The
exact number of bits depends on the instruction encoding and the number of
bits reserved for opcodes.  The destination must be a branch pointing back
to the current location, or a SWAPBR.

\section{Special instructions}

%----------------------------------------------------------------------
\instruction{EXCH}{Exchange a register with a memory cell.}{
EXCH $reg_d$ $reg_a$ }{
\item[$reg_d$ ---] The data register.
\item[$reg_a$ ---] The address register.
}

Exchanges the contents of the given data register $reg_d$ with the contents
of the RAM memory cell at the 32-bit address given in register $reg_a$.  If
the address given happens to be the address of the EXCH instruction being
executed, the hardware may treat this as a special case, and for example,
ignore the instruction.  Whatever it does, it must be reversible, however.

%----------------------------------------------------------------------
\instruction{SWAPBR}{Exchange register with branch register.}{
SWAPBR $reg$
}{
\item[$reg$ ---] Register to swap with the branch register.
}

Swap the contents of register $reg$ with the contents of the branch
register.  This instruction is useful at the entry/exit points of
subroutines and switch statements.  

%----------------------------------------------------------------------
\instruction{RBRA}{Direction-reversing unconditional branch.}{
RBRA $loff$
}{
\item[$loff$ ---] Long immediate offset.
}

Like BRA, but also toggles the processor direction bit.  After the branch
is taken, the processor will proceed in the opposite direction from the one
it was traversing originally.  Useful for making reverse subroutine calls.

%----------------------------------------------------------------------
\instruction{READ}{Copy information from input device.}{
READ $reg$
}{
\item[$reg$ ---] Register to read data into.
}

This instruction XORs the next word of data from the processor's canonical
input device into register $reg$.  In a multiprocessing architecture, this
might be a means to receive information from the interprocessor
communication network.

%----------------------------------------------------------------------
\instruction{SHOW}{Copy information to output device.}{
SHOW $reg$
}{
\item[$reg$ ---] Register whose contents to show.
}

This instruction copies the information in register $reg$ and sends the
copy to the processor's canonical output device.  In the Pendulum
simulator, this is used to echo data to the standard output stream, for
viewing program output.  In a multiprocessing architecture, this might be a
means to send information into the interprocessor communication network.

%----------------------------------------------------------------------
\instruction{EMIT}{Emit information from the processor.}{
EMIT $reg$
}{
\item[$reg$ ---] Register whose contents to emit.
}

Like SHOW, but moves the data out of $reg$, instead of making a copy.  This
is presumed to represent the explicit, reversible removal of unwanted data
from the processor to an entropy-removal mechanism.  This mechanism might
be a sub-processor that first compresses the garbage stream, then erases it
using as little energy as possible.  Or, it might be a mechanism for
reversible, digitally transmitting the information to the edge of a
multiprocessor mesh, and then dissipating it there.  Or, it might be
another mechanism for moving information out to an interprocessor
communication network.

%----------------------------------------------------------------------
\instruction{START/FINISH}{End-points for computation.}{
START \\
FINISH
}{
\item
}

These instructions merely mark the start and end of a program, for ease of
simulation.  They could be used in a real processor: FINISH could halt the
processor, and START could halt if running in reverse.  Note, however, that
actually halting the processor is an irreversible event, since one has lost
the information about how long ago the processor halted.  One should be
careful not to build a very large, dense reversible mesh processor that
will explode when all the processors simultaneously reach the FINISH
instruction, as a result of each processing node dissipating the $\kT \ln
2$ energy to clear the bit of information that tells it that it is still
running.

One could fix this problem by having FINISH merely switch to a mode where
the processor starts counting the number of time-steps since it halted.
When the counter runs out of space, however, the processor must either
erase information, or start running again.



% End chapter.
\cleardoublepage
