The old branch instructions were unidirectional: they were no-ops when executed in one direction, and only provided the possibility of branching when executed in the other, appropriate direction. Branches always came in pairs, with a forward branch pointing to a matching reverse branch, and vice-versa. The motivation here is that we do not want a pair of branches to branch back and forth to each other forever, so when we hit a branch instruction we need to have some way of knowing whether it is a branch we are supposed to actually take given our execution direction. This was the reason for the two opposite types of branches.
Moreover, the behavior of a branch is undefined if the instruction being branched to is not a branch back to the first instruction, or if it is a conditional branch that doesn't actually succeed.
There are two problems with this scheme. First, there is the obvious one that arbitrary code is not guaranteed to have paired branches and thus not guaranteed reversible. If the only entity that can submit new code into the processor for execution is a guaranteed-correct compiler that always provides matching pairs of branches, this is not a problem; but if we want to allow possibly-imperfect native user programs to generate code as well, it is a problem.
However, even aside from the issue of providing a branch at the destination, there is the deeper problem: What if the code in between a pair of branches changes the success/failure of the branch condition? There is no way to tell at compile time whether the user body in the body if an IF statement, for example, will leave the condition's truth value alone, unless side effects in the body code are forbidden, which reduces us to pure functional programming. This implies a sacrifice in asymptotic speed which I would rather not be forced to make.
Again, a run-time check either in software or hardware could allow us to halt instead of dissipating in cases where the branch condition is changed in between branches, but this seems non-ideal.
Our proposal is a new method for doing branches in which which each branch instruction is always atomically reversible in and of itself, regardless of the presence or absence or success or failure of a corresponding branch at the destination. In cases where the branches do not match properly, the behavior will be bizarre, but reversible and well-defined.
The mechanism involves a new entity called the branch register, or BR. It controls how the PC is updated between instructions. If it is 0, the PC is incremented by +1 or -1 depending on the current processor direction. If it is nonzero, the PC is incremented by BR. When the processor direction is reversed between instructions by an external signal, BR is two's-complement negated at the same time that the direction bit is flipped. We will arrange things so that the sign of BR is invisible to the programmer; this means that a program has no way of following a different path when running in reverse than the path that is the reverse of the path that it follows when running forwards.
A branch instruction (executed in either direction) works by adding the offset (if the test succeeds) to the destination into the branch register. The matching branch at the destination is just the same, but with a negative offset. Thus when the second branch is executed, the offset in the branch register is canceled out to zero and normal sequential execution resumes. When running in reverse, the lexically-later branch runs first, setting BR to the negated offset to the lexically-earlier branch, and then that earlier branch cancels this out with its offset.
Note that if the first of a pair of branches succeeds but there is no second branch at the destination or it fails, the effect will be that the PC will keep hopping through the code in increments of the offset. This does not seem like useful behavior, but it is well-defined and reversible.
Similarly, if the body of an IF changes the IF-condition to be false, then the branch at the end of the IF will succeed instead of failing, and control will loop back to the start of the body, and looping will continue until the condition becomes false. So a single branch pair really serves as both a loop and a conditional, the exact behavior determined by when and whether the tests succeed or fail.
This scheme has the advantage of being simple to implement, and reversible all the time. Moreover, since the same instructions are used for branching when running in both forwards and reverse directions, we eliminate all the reverse branch instructions BEQ_r, BGEZ_r, BGTZ_r, BLEZ_r, BLTZ_r, and BNE_r.