A Transformational Approach to Binary Translation of Delayed Branches

Authors:Ramsey, Norman, Department of Computer ScienceUniversity of Virginia Cifuentes, Cristina, Department of Computer ScienceUniversity of Virginia

The fundamental steps in binary translation are distinguishing code from data, mapping data from source to target, and translating instructions. Translating instructions presents few problems, except when the source instruction set has features not present in typical compiler intermediate codes. The most common such feature is the delayed branch. <p> Standard code-generation technology can handle delayed branches in the target language, but not in the source. Translating delayed branches can involve tricky case analyses to figure out what happens 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 also applies to other tools that analyze machine instructions. <p> <!-- The method is based on program transformation. --> We begin by writing a very simple interpreter for the source machine. It specifies, at the register-transfer level, how the source machine executes instructions, including delayed branches. 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. <p> We show the translation is correct by using a correspondence between source and target states, and showing if the source and target machines begin execution in corresponding states, they reach new corresponding states in a few instructions.

All rights reserved (no additional license for public reuse)
Source Citation:

Ramsey, Norman, and Cristina Cifuentes. "A Transformational Approach to Binary Translation of Delayed Branches." University of Virginia Dept. of Computer Science Tech Report (1999).

University of Virginia, Department of Computer Science
Published Date: