# A Transformational Approach to Binary Translation of Delayed Branches

## Abstract

A binary translator examines binary code for a source machine, 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.
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, and
PA-RISC, and it
should apply to any tool that analyzes machine instructions.
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.

## Full paper

The paper is available as
US Letter PostScript (427K),
US Letter PDF (158K), and
US Letter TeX DVI (127K).
There is too much mathematics to render in HTML.