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.