A binary translator examines binary code for a source machine, optionally
builds an intermediate representation, and generates code for a target
machine. Understanding what to do with delayed branches in binary code can
involve tricky case analyses, e.g., if there is a branch instruction in a
delay slot. Correctness of a translation is of utmost importance. This
paper presents a disciplined method for deriving such case analyses. The
method identifies problematic cases, shows the translations for the
non-problematic cases, and gives confidence that all cases are
considered.The method supports such common architectures as SPARC®, MIPS,
We begin by writing a very simple interpreter for the source machine's
code. We then transform the interpreter into an interpreter for a target
machine without delayed branches. To maintain the semantics of the program
being interpreted, we simultaneously transform the sequence of
source-machine instructions into a sequence of target-machine instructions.
The transformation of the instructions becomes our algorithm for binary
translation. We show the translation is correct by reasoning about
corresponding states on source and target machines.
Instantiation of this algorithm to the SPARC V8 and PA-RISC V1.1
architectures is shown. Of interest, these two machines share seven of 11
classes of delayed branching semantics; the PA-RISC has three classes which
are not available in the SPARC architecture, and the SPARC architecture has
one class which is not available in the PA-RISC architecture.
Although the delayed branch is an architectural idea whose time has come
and gone, the method is significant to anyone who must write tools that
deal with legacy binaries. For example, translators using this method could
run PA-RISC on the new IA-64 architecture, or they may enable architects to
eliminate delayed branches from a future version of the SPARC architecture.
*This report is a very extended version of TR 440, Department of Computer
Science and Electrical Engineering, The University of Queensland, Dec 1998,
and describes applications of the technique to translations of SPARC® and
PA-RISC codes. This report fully documents the translation algorithms for