Browse Prior Art Database

Method for register EXCHANGE instruction elimination in binary translation

IP.com Disclosure Number: IPCOM000007121D
Publication Date: 2002-Feb-26
Document File: 4 page(s) / 55K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for register EXCHANGE instruction elimination in binary translation. Benefits include improved performance.

This text was extracted from a Microsoft Word document.
This is the abbreviated version, containing approximately 47% of the total text.

Method for register EXCHANGE instruction elimination in binary translation

Disclosed is a method for register EXCHANGE instruction elimination in binary translation. Benefits include improved performance.

Background

              A binary translator takes the source binary code as input, translates it and runs the translated code in a different target machine. In some source architecture, the EXCHANGE instruction transfers the values of registers simultaneously, for example, the FXCH instructions. However, these instructions seldom exist in the target architectures. They provide a register-moving instruction, MOV.

              An intuitive way to translate EXCHANGE to MOV instructions includes the following steps:

1.           MOV the first operand to a temporary register

2.           MOV the second operand to the first operand

2.           MOV the content of temporary register to the second operand

              This method is very expensive especially for floating pointer registers. These three instructions are flow dependent, and the floating-point register MOV instruction is usually expensive.

Description

              The disclosed method eliminates the EXCHANGE instruction using a renaming mechanism. Typically, the number of floating point registers in the source architectures is many fewer than in the target architectures. The renaming mechanism can effectively use a large target register file to greatly improve the quality of the translated code. In general, the situation can be stated as follows.

              In the source architecture, there are n registers r1, r2, ¼, rn (which are renamed objects). In the target architecture, there are m registers R1, R2, ¼, Rm (which are renaming objects). Here, m is much larger than n.

              Using the disclosed method, the renaming registers are divided into two parts, (R1, R2, ¼, Rn) and (Rn+1, Rn+2, ¼, Rm), which are called canonical registers and temporary registers, respectively. To be convenient, the canonical registers R1, R2, ¼, Rn are annotated as C1, C2, ¼, Cn, and the temporary registers Rn+1, Rn+2, ¼, Rm are annotated as T1, T2, ¼, Tm-n.

              From a global point of view, the disclosed method always maps the source registers
r1, r2, ¼, rn onto the canonical registers C1, C2, ¼, Cn that is ri is always mapped to Ci. This greatly simplifies the state recovery problem because the value of ri can be computed from Ci.

              In the scope of the basic block, the original registers r1, r2, ¼, rn can be mapped to
R1, R2, ¼, Rm by renaming. During the renaming process, copy propagation and constant propagation are also performed.

              A rollback and recovery method is used to map the source registers r1, r2, ¼, rn onto the canonical registers C1, C2, ¼, Cn.

              Because the disclosed method only handles the basic blocks, and all the writes to registers in the blocks are definite, the last definition to a given register ri in the given block can be easily identified. Therefore, the last definition of ri is easily tracked during the renaming process. This information is used to generate efficient and correct code at the...