\documentstyle{article}

\input{psfig}

\def\dopsfig#1#2#3{%
  \begin{figure}[htb]\centerline{\psfig{#1}}\caption{#2}\label{#3}\end{figure}}
\def\dotoppsfig#1#2#3{%
  \begin{figure}[t]\centerline{\psfig{#1}}\caption{#2}\label{#3}\end{figure}}

\title{MIT Reversible Computing Project \\ Memo \#M1\footnote{``M'' is for ``Michael.''}\\
``Time-Symmetric Control-Flow Instructions\\
for Less Garbage in Reversible Programs''\\
DRAFT}

\author{Michael Frank\\mpf@ai.mit.edu}

\date{Started 12/5/95\\
\begin{verb}$Revision: 1.21 $\end{verb}\\
\today}

\begin{document}

\maketitle

\abstract{

The most straightforward approach to implementing control-flow
instructions (such as branches) reversibly is to push the source
address for the branch onto a special stack \cite{vieri}.
Unfortunately this approach accumulates garbage whenever a branch is
taken, garbage that cannot be disposed of under program control.  

A potentially more space-efficient approach is to store the source
address in a ``branch register'' which can be cleared under program
control.  However, the branch register approach seems clumsy and
inelegant.

To solve these problems, we borrow from physics the concept of
``time-symmetry,'' which says that the same sorts of operations should
apply whether time (or in this case, program execution) is run
forwards or backwards.  Inspired by this notion, we can design
time-symmetric branching, looping, and procedure-calling instructions
that can be used to greatly reduce, and in many cases eliminate, the
garbage created by control-flow operations in structured programs, in
a way that is simple and elegant and mirrors the time-symmetry of the
underlying physics.

}

{\em [Note: After this memo was written, I noticed that many of the
same ideas were previously developed in a paper by Hall, published in
1994
\cite{hall2}.  Thus, the present memo needs to be rewritten to credit Hall's contributions
where appropriate.]}

\section{Introduction}

A central problem of reversible computing is how to deal with the
extra ``garbage'' bits of information that seem to inevitably result
from useful computations.
%
\footnote{Or, more precisely, from useful computations on
arbitrary-sized inputs.  For any function of bounded input size, there
is a custom reversible logic circuit that computes the function using
no more bits at any point than the number in the input plus the number
in the output plus one [refs to Toffoli, Bennett, others?].  However,
the construction may demand exponentially-sized circuits, and anyway,
we are interested in general-purpose reversible computers without
fixed limits on their input size.  For such machines, asymptotic space
requirements may be greater for reversible machines than for their
irreversible counterparts when solving problems of interest.
(However, this conjecture is unproven.)}
%
A traditional computer simply destroys these bits, dissipating their
energy into heat, but in sufficiently power- or cooling-limited
environments, resorting to dissipation is undesirable, and it is the
aim of our project to explore the alternatives.

Garbage bits can of course simply be stored until the end of a
computation, at which point it may be collected by running the
computation in reverse (after copying the output), so that the net
garbage consists only of the information originally input to the
computation.  However, this does not address the large amount of
garbage storage space that may be {\em temporarily} needed during the
computation.  Charles Bennett has shown \cite{ben1,ben4,levine} that
the amount of temporary storage needed for garbage can be reduced
further by reversing pieces of a computation in clever patterns.  But
so far as is known, linear-time algorithms can only do polynomial
garbage reductions.  Logarithmic garbage reduction can be achieved,
but only at the cost of a polynomial increase in running time, which
may be unacceptable for long-running programs.

Therefore, it is clearly in the interest of the designers of a
reversible computing system (consisting of the processor architecture
and one or more high-level language compilers) to minimize the amount
of garbage that is produced in the first place.

Some garbage results from the execution of what Vieri has called {\em
expanding} operations \cite{vieri}: primitive reversible operations in
which the number of interesting (non-constant) output bits exceeds the
number of interesting input bits.  No one knows for sure whether
expanding operations are absulutely necessary for universal computing.
Perhaps all programs could be rewritten in a form where only
non-expanding operations are used, but this conjecture is
unsubstantiated.  So we are currently constrained to produce some
garbage merely in the course of performing common operations such as
AND and OR.  There is not much that the architecture or compiler can
do to avoid garbage creation in the face of requests for such
operations from the programmer, except wait until enough of it has
accumulated so that undoing a chunk of the computation and storing its
input and output instead of the garbage trace becomes preferable, as
is done in Bennett's algorithms.

Another potential kind of garbage, which is the subject of this memo,
is that which results from arbitrary control-flow operations.  In the
worst case, imagine that every location in instruction memory contains
a branch to location x.  Then after executing one such instruction, we
need to store as many bits as there are in instruction memory
addresses to remember which previous instruction we just came from.

This observation leads to the simplest policy for handling
control-flow operations: allow arbitrary branch and jump operations,
but always push the address prior to the branch onto a special branch
stack.  This is the approach taken by Vieri \cite{vieri} in the
Pendulum architecture.  No further modifications of traditional
control flow operations are required.  Vieri suggests placing a
special COME-FROM instruction at the destination of every branch to
make reverse operation easier to implement, but this is not strictly
necessary; instead, the top of the branch stack can be continuously
examined to see if the current address is referred to by the branch
recorded on top of the stack, and if so, the reverse branch may be
taken (on the assumption that control flow is never allowed to wrap
circularly completely around the entire instruction address space).

Although simple, this approach has the obvious flaw, pointed out by
Vieri, that it leads to a monotonically-increasing storage requirement
for the PC garbage stack during the execution of any program with
branches (which means any real program).  Storage requirements
monotonically decrease when running backwards, and so the {\em net} PC
garbage storage for any program can be zero if programs are always
reversed after execution, but this is of no help if the storage
capacity of the system available for temporary storage of garbage data
is limited to an amount that is too small to run the desired program.

This problem can be alleviated somewhat by making the previous address
for the branch into programmer-accessible garbage, which can then be
erased in software if its value can be reconstructed.  This can be
accomplished by having the branch place its source and destination
addresses into a special ``branch register;'' other instructions can
then swap the value of the register into a memory location, after
which other code can reconstruct whether a branch was taken, and from
where, using other means.  This information can then be used to
reconstruct and zero out the memory containing the stored previous
value of the branch register.  However, this approach inelegantly
turns every branch into a somewhat clumsy jumble of garbage-cleanup
code.  Is there a way to avoid creating the branch garbage in the
first place?

We observe here that whole ``save the prior PC'' approach to making
control flow reversible is highly {\em time-{\bf a}symmetric}.  This
is because the actual branch instruction, which contains all the
information about the branch, is located at the source of the branch.
At the destination of the branch, traditional programming styles
assume that a special branch is not needed.  But observe that the
original pendulum architecture stipulates a COME-FROM statement at the
destination of the branch, and my branch-register suggestion involves
branch-register cleanup code at the destination of the branch.  Thus
we have already encountered the suggestion that there be {\em
something} at the destination of a branch in a reversible
architecture.  What if this something were, symmetrically, another
branch instruction for use when operating in the reverse direction?

At first this suggestion seems insufficient.  After all, traditional
machine architectures allow that programs may contain branches from
anywhere to anywhere based on any branch condition, so at a given
point in a program there may be no simple condition that suffices to
determine whether to branch when hitting a branch target in reverse.
Worse, if many branches target a single location, a single instruction
seems insufficient to allow branching back to any of them.  These
issues were observed and considered in more detail by Vieri
\cite{vieri}.
        
But let us set aside, for the moment, the traditional architecture's
ability to handle arbitrary branches, and instead consider the sorts
of control flow structures that appear in actual structured programs.
It is well known that three control-flow constructs suffice for
general-purpose programming: {\tt if-then-else} blocks, loops, and
procedure calls.  (Furthermore, loops and procedure calls are not both
needed for universal computation, but it is convenient to have both
available.)  Automatic translation of programs that use additional
constructs (such as C's {\tt break}, {\tt return}, {\tt switch}, and
{\tt goto}) into programs using only these three constructs is
generally straightforward and involves only modest overheads. [Need to
read up on how to do it.] [ref: Dijkstra, or Boehm et al]

It turns out that, given a reversible architecture that supports
symmetric forward and reverse branch instructions, all three basic
constructs can be implemented in a simple, elegant way.  No control
flow garbage is produced, except by some loops, which in the worst
case only produce $log_2 n$ bits of garbage, where $n$ is the number
of iterations of the loop.  The legality of programs in this
architecture is more restricted than in traditional architectures, in
that the forward and reverse branch constructs must always be used
only in a paired, symmetric way in order for energy dissipation to be
avoided, but it is a simple job for compilers to translate an
arbitrary program into symmetric machine code that satisfies this
requirement.  [Again, need to verify this.]

However, this issue makes compiler correctness even more vital than in
traditional computers, as a compiler bug in this architecture could
result in code that burns up a reversible processor implementation
that is not designed to tolerate the heat dissipation.  Automatic
detection of illegal code sequences by the processor to avoid burn-up
is an important area for future study.  Possibly it can be solved
simply by having the processor detect whenever an old PC value is
reset using a value that is not equal to it, and thereupon raise an
exception or halt.  However, this idea needs more detailed elucidation
at the register-transfer level.

\section{Symmetric Control Flow Instructions}

The fundamental feature of control flow instructions in this
architecture is that each comes in two flavors: a ``forward'' version
that is only used when the processor is running forwards, and a
``reverse'' version that is only used when the processor is running
backwards.  Each control-flow instruction is ignored (treated as a
No-Op) when encountered during execution in the inappropriate
direction.  In the discussion here, reverse instructions are
distinguished by prefixing them with a ``{\tt *}'' character.

Control flow instructions come in four basic classes which are very
traditional:

\begin{enumerate}

\item {Conditional branches, which test some condition on some
register or registers and set the program counter to point to a given
location if the condition is satisfied.}

\item {Unconditional branches and jumps, which set the program counter
to a given location unconditionally.}

\item {A jump-and-link or similar instruction for implementing procedure
calls.}

\item {A jump-register or similar instruction for returning from
procedure calls.}

\end{enumerate}

Each instruction in each of these classes comes in both forward and
reverse flavors.

\subsection{Example Instruction Specifications}

Here are some example specifications for instructions in each of these
classes.  These examples are used later to illustrate how to implement
each of the three basic structured control flow constructs (ifs,
loops, and calls).  This list is not intended to be comprehensive,
since in a real architecture, we might want to support a wider variety
of branch conditions, addressing modes, etc.  Also some instructions'
semantics might need to be changed slightly to make implementation
easier.  But the basic behavior of the instructions will be unchanged.

Each instruction implicitly exists in both forward and reverse
flavors.  Reverse flavors are distinguished by prefixing the
instruction name with ``{\tt *}''.  All control flow instructions are
defined to be No-Ops when executed in the wrong direction for their
flavor, and the instruction descriptions describe only the operation
of the instruction when encountered in the right direction.

Various instruction descriptions express conditions that must be
satisfied.  If these conditions do not hold, the processor will raise
an exception, halt, or silently dissipate energy, depending on further
design decisions.  (Whichever it is, it probably ought to be
consistent across all instructions.)

In general, the requirement is that every instruction in the entire
architecture must cause the PC to change to point to an instruction
which, if the processor's direction were to be immediately reversed,
would return the PC exactly back to the current instruction.  Later we
will describe how to implement the 3 basic control flow constructs in
a way that ensures this.

\vspace{12pt}
\hrule
%----------------------------------------------------------------------
{\tt BZ},{\tt BNZ} --- Branch if equal to zero, branch if nonzero.
\vspace{12pt}

Tests a given register to see if it is equal (for {\tt BZ}, not equal
for {\tt BNZ}) to zero, and if so, branches to the given
immediately-specified relative offset from the current location.  The
destination address (if it is not the very next instruction) {\em
must} contain a branch or jump of the opposite flavor that must be
guaranteed to jump back to the current instruction if the processor
were immediately to be reversed.

\vspace{12pt}
\hrule
%----------------------------------------------------------------------
{\tt BRA} --- Branch always.
\vspace{12pt}

As above, but unconditional.
\vspace{12pt}
\hrule
%----------------------------------------------------------------------
{\tt JAL} --- Jump and link.
\vspace{12pt}

Jumps to a given address, after placing the address of the next
instruction after (or before, for the reverse flavor) the current one
in a given register, which must have previously been ensured to
contain zero.  The destination instruction must be a {\tt JR}
instruction of opposite flavor.
\vspace{12pt}
\hrule
%----------------------------------------------------------------------
{\tt JR} --- Jump Register.
\vspace{12pt}

Swap the PC with the value stored in the given register, which must be
the address of a {\tt JAL} instruction of opposite flavor that points
to the current instruction.  Then, reset the register to 0 using the
pointer to the current instruction that is embedded in the target {\tt
JAL} instruction.

Note that, in addition to the obvious use for returning from procedure
calls, {\tt JR} can actually be used to implement run-time determined
jumps to arbitrary locations, so long as those locations contain
oppositely-flavored {\tt JAL}s pointing back to the particular {\tt
JR}.  Bizarrely, this behavior can be used to implement switch
statements in addition to the intended use for procedure calls!
[Remember to describe this in later section.]

\vspace{12pt}
\hrule
%----------------------------------------------------------------------
\vspace{12pt}

The above are actually all the control flow instructions that are
strictly necessary in a reversible architecture that supports ifs,
loops, calls, and switches.  More varieties of branch conditions are
desirable, but superfluous.

\section{Symmetric Control Flow Structures}

The following diagram (fig. \ref{fig:flows}) illustrates how various
control flow structures can be implemented in terms of the example
instructions defined above.

\dopsfig{file=flows.eps,width=\textwidth}{Examples of symmetric control flow structures.}
{fig:flows}

In the diagram, vertical arrangements of instructions are supposed to
suggest a linear sequence of instructions in memory, out of which only
the control-flow instructions are shown.  Arguments of instructions
are omitted.  Instruction streams off to one side may potentially be
located elsewhere in memory far from the main linear sequence.  Curved
arrows (and some straight arrows) indicate branches and other nonlocal
control flow.  Black arrows indicate possible control-flow paths that
may be taken when the processor is executing in the forward direction,
while grey arrows indicate paths that may be taken when the processor
is executing in the reverse direction.

Instructions prefixed by asterisks (``{\tt *}'') are reverse flavors
which are ignored when encountered during forward execution, and
vice-versa for instructions without asterisks.

\subsection{Discussion of Structures}

\subsubsection{If...then (...else)}

\begin{verbatim}
if (condition-expression) then
        body
end if
\end{verbatim}

To compile an ``if...then'' construct into code, one simply places the
result of the if's condition expression into a register that will
remain unchanged during the body of the if, and then place identical
but opposite-flavored conditional branches on that register at either
end of the if body, pointing to each other.  The value of the register
may be uncomputed by extra code after the if statement, if desired.

Let us trace through the operation of the ``if..then'' in forwards
execution.  The code before the if is executed, evaluating the if's
condition expression, and placing its result in a register, which,
say, will contain 1 if the body is to be executed, 0 otherwise.  Then
the BZ statement is encountered.  If the register is nonzero, the
branch is not taken, and control flow proceeds into the body of the
if.  The body may of course temporarily swap the register value out to
memory if the register is needed for other purposes, but if it does
so, the original value must be swapped back in before the end of the
body is reached.  At the end of the body, the *BZ instruction is
encountered, which does nothing.  (Actually, at an implementation
level, the processor may test the register again at this point to
determine that the previously executed instruction was indeed the
preceding instruction in memory, rather than the forward BZ, so that
the prior PC value may be discarded properly.  But this is not
user-visible behavior.)  Finally, after the whole ``if'', code may
uncompute the value we conditioned on, or it might placed somewhere in
memory for a future round of garbage cleanup.  If the branch is taken,
the body is skipped, and the *BZ at the destination of the branch
tells the processor what the previous value of the PC was so that that
previous value may be discarded.

Operation during reverse execution is exactly the same, except that
the program counter normally proceeds backwards through the
instruction stream, and the roles of forward and reverse instructions
are exchanged.

[There is a problem with the policy of always reversing the condition
expression after the ``if'' is finished, which is that if evaluating
the condition expression it involves a recursive call of something
involving an ``if'', then runtime can increase exponentially with the
number of levels of these if calls, compared to not reversing the
condition.  The alternative is to store at least 1 bit of garbage
information indicating which branch of the conditional was taken, and
hope to recover this bit via some larger-scale reversal.  However, if
no recursive if's are involved in turning program variables into
branch conditions, reversing the branch condition calculation is not a
problem.  Most if expressions don't involve recursive calls, so I
think we're OK.  Need to mention this issue more throughout text.]

\begin{verbatim}
if (condition-expression) then
        body1
else
        body2
end if
\end{verbatim}

The ``If...then...else'' statement is very similar to the
``if...then'', except that the conditional branches go to
opposite-flavored unconditional branch instructions.  This does not
prevent the previous PC value from being discarded properly.

\subsubsection{Loops}

Loops get a little bit tricky.  Traditional structured programming
loops (while, until, do-while) are generally associated with a
condition that is true when in the loop, and false when the loop is
about to end.  But when running in reverse, what tells us that the
loop is about to reach the beginning?  The condition associated with
the loop must change its value during {\em both} the first and the
last iterations of the loop.  (Or neither, if there is only 1
iteration.)  It must of course change during the last iteration so
that its value tells us that now it is time to leave the loop.  But
also, it must change during the first iteration so that when running
in reverse, when we reverse all the way back to the first iteration,
its change tells us that now it is time to go back out of the start of
the loop.  This leads to the following semantics for the loop
condition:

\begin{quote}
The loop condition is the condition for {\em either} exiting or
entering the loop, depending on whether we are already in the loop or
not.  In other words, when the loop boundaries are encountered, either
from inside the loop or from outside, the condition tells us whether
to cross over to the other side, or remain on the side we're already
on.
\end{quote}

\begin{verbatim}
symloop (condition-expression)
        body
end symloop
\end{verbatim}

We can imagine a new structured programming construct, ``symloop,''
for ``symmetric loop,'' similar to a traditional while loop, but with
its condition interpreted as described above.  In other words, if the
condition is false when the loop is first encountered, the loop is not
executed at all.  If it is true the loop is entered, and if it remains
true at the end of the first iteration, the loop is immediately
exited, performing only one iteration.  To execute more than one
iteration, the condition must become false during the first iteration,
and then become true again during the last iteration.

The symloop can be implemented as shown in figure \ref{fig:flows}.
The structure is essentially equivalent to an if, but branching
backwards instead of forwards, and embedded within a
forwards-branching if testing the same condition.  In the example,
each {\tt BZ}-{\tt *BZ} sequence serves as one of the boundaries of
the loop body.  Whenever a boundary is encountered, whether from
inside the loop, from outside the loop, running forwards, or running
backwards, the boundary causes the appropriate thing to occur: control
flow switches betweeen the loop's inside and outside if and only if
the loop condition (in this case that some tested register is
non-zero) is satisfied.

Programmers might be easily able to use the symloop construct directly
to implement many kinds of loops (i.e., to loop an index i between the
values min and max, the condition is simply (i=min or i=max+1)).
However, arbitrary ``while''-style loops can be supported as well via
the simple expedient of introducing an extra ``count'' variable to
keep track of the number of times through the loop.  For example, a
traditional while loop, such as the following,

\begin{verbatim}
while (continuation-condition-expression)
        body
end while
\end{verbatim}

can be automatically transformed into the following symloop:

\begin{verbatim}
count = 0
symloop ( ((count = 0) and (continuation-expression-condition))
          or
          not (continuation-expression-condition)
        )
        body
        count = count + 1
end symloop
\end{verbatim}

In forward operation, the first part of the disjunctive condition is
the condition for entering the loop, and the second part is the
condition for exiting the loop.  In reverse, however, the second part
becomes the condition for entering the loop in reverse, and the first
part becomes the condition for exiting out the start of the loop after
completing the first iteration.

Note, however, that this approach produces a count of the number of
times through the loop as a garbage value.  However, this is much
better than generating another word of garbage on every loop iteration
as would happen if loops simply used branches that pushed the prior PC
onto a stack.

\subsubsection{Procedure Calls}

Procedure calls are straightforward; the call consists of forward and
reverse {\tt JAL's} back-to-back that refer to the beginning and end
of the procedure, respectively.  At each end there is an
appropriately-flavored {\tt JR} to return control back to the caller.

One interesting thought is to have another version of JAL that
reverses the processor direction as well as changing the PC.  Then, a
single subroutine can be called in both forward and reverse modes from
a single caller running in forward mode.  This reduces code size
during garbage cleanup, since forward and reverse versions of the
procedure do not both have to be provided.

\subsubsection{Switch (Case) Statement}

This is an interesting application of {\tt JAL} and {\tt JR} in a way
other than for the procedure calls for which they were intended.
Before the switch, the address of the branch to take is computed by
evaluating some expression.  We jump to the computed address, execute
the body of the particular case, and then jump to the end of the
statement storing the address of the {\em end} of the appropriate case
in a register, which can then be uncomputed by code similar to the
code that generated the address of the start of the appropriate case.
The end code will need to be a bit different so that it uncomputes the
end address rather than the start address of the branch taken, but
this is trivial for a compiler.

\section{Conclusion}

We have shown that all the basic control-flow constructs of structured
programming can be implemented in a totally time-symmetric way that
produces no garbage except the occasional count of the number of
iterations of a loop whose number of iterations cannot be predicted
rather than by executing it.  

This advancement holds the promise of greatly simplifying the problem
of garbage accumulation in reversible computers, since it nearly
eliminates the entire class of garbage that is associated with control
flow operations, meaning that the only garbage that is produced is due
to the application of ``expanding'' data operations.

Future research will hopefully show how us to reduce data garbage as
well, although it probably cannot be eliminated entirely or even
limited to, say, a linear function of non-garbage storage.  In any
case, appropriate use of subcomputation reversals, such as in
Bennett's algorithms, should be sufficient for allowing fully
reversible architectures to perform useful computations.

\bibliographystyle{plain}
\bibliography{../bib/refs}

\end{document}
