Printer Friendly

Binary translation.

When Digital started to design the Alpha AXP architecture in the fall of 1988, the Alpha AXP team was concerned with running existing VAX[TM] code and MIPS[TM] code on the new Alpha AXP computers [5, 6]. To get full performance on a new computer architecture, an application must be ported by rebuilding, using native compilers. For a single program written in a standard programming language, this is a matter of recompile and run. A complex software application can be built, however, from hundreds of source pieces using dozens of tools. A native port of such an application is only possible when all parts of the build path are running on the new architecture.

Therefore, having a way to run an existing (old architecture) binary version of a complex application on a new architecture is an important interim measure. It allows a user to get applications up and running immediately, with minimal porting effort. Once a user's everyday environment is established, applications can be rebuilt over time, using native code or partially native and partially old code.

Several techniques are used in the industry to run the binary code of an old architecture on a new architecture. Figure 1 shows four common techniques, from slowest to fastest:

* Software interpreter (e.g., Insignia Solutions' SoftPC)

* Microcoded emulator (e.g., PDP-11 compatibility mode in early VAX computers)

* Binary translator (e.g., Hunter System's XDOS)

* Native compiler

A software interpreter is a program that reads instructions of the old architecture one at a time, performing each operation in turn on a software-maintained version of the old architecture's state. Interpreters are not very fast, but run on a wide variety of machines and can faithfully reproduce the behavior of self-modifying programs, programs that branch to data, programs that branch to a checksum of themselves, and so forth. Caching interpreters gain speed by retaining predecoded forms of previously interpreted instructions.

A microcoded emulator operates similarly to a software interpreter but usually with some key hardware assists to decode the old instructions quickly and to hold hardware state information in registers of the micromachine. An emulator is typically faster than an interpreter but can run only on a specific microcoded new machine. This technique cannot be used to run existing code on a reduced instruction set computer (RISC) machine, since RISC architectures do not have a microcoded hardware layer underlying the visible machine architecture.

A translated binary program is a sequence of new-architecture instructions that reproduces the behavior of an old-architecture program. Typically, much of the state information of the old machine is kept in registers in the new machine. Translated code reproduces faithfully the calling standard, implicit state, instruction side effects, branching flow, and other artifacts of the old machine. Translated programs can be much faster than interpreters or emulators but slower than native-compiled programs.

Translators can be classified as either (1) bounded translation systems, in which all the instructions of the old program must exist at translation time and must be found and translated to new instructions [2, 3, 7], or (2) open-ended translation systems, in which code also may be discovered, created, or modified at execution time. Bounded systems usually require manual intervention to find 100% of the code; open-ended systems can be fully automatic.

To run existing VAX and MIPS programs, an open-ended system is absolutely necessary. For example, some customer programs write license-check code (VAX instructions) to memory and branch to that code. A bounded system fails on such programs.

A native-compiled program is a sequence of new-architecture instructions produced by recompiling the program. Usually, native-compiled programs use newer, faster calling conventions than old programs. With a well-tuned optimizing compiler, native-compiled programs can be substantially faster than any of the other choices.

Most large programs are not self-contained; they call library routines, windowing services, databases, and toolkits, for example. Also, these programs (directly or indirectly) invoke operating-system services. In simple environments with a single dominant library, it can be sufficient to rewrite that library in native code and to interpret user programs, particularly user programs that actually spend most of their time in the library. This strategy is commonly used to run Windows[TM] and Macintosh[TM] programs under the Unix[TM] operating system.

In more robust environments, it is not practical to rewrite all the shared libraries by hand; collections of dozens or even hundreds of images (such as typical VAX ALL-IN-1[TM] systems) must be run in the old environment, with an occasional excursion into the native operating system. Over time, it is desirable (1) to rebuild some images using a native compiler while retaining other images as translated code and (2) to achieve interoperability between these old and new images. The interface between an old environment and a new one typically consists of "jacket" routines that receive a call using old conventions and data stuctures, reformat the parameters, perform a native call using new conventions and data structures, reformat the result, and return.

The Alpha AXP Migration Tools team considered running old VAX binary programs on Alpha AXP computers using a simple software interpreter, but rejected this method because the performance would be too slow to be useful. The idea of using some form of microcoded emulator was rejected also. This technique would compromise the performance of a native Alpha AXP implementation, and VAX compatibility would be nearly impossible to achieve without microcode, which is inconsistent with a high-speed RISC design.

Therefore, we turned to open-ended binary translation. We were aware of the earlier Hewlett-Packard binary translator, but its single-image HP[TM] 3000 input code looked much simpler to translate than large collections of hand-coded VAX assembly language programs [1]. One team member wrote a VAX-to-VAX binary translator as a proof of concept, which looked feasible, so we set the following goals:

1. Open-ended (completely automatic) translation of almost all user-mode applications from the OpenVMS VAX system to the OpenVMS AXP system.

2. Open-ended translation of almost all user-mode applications from the ULTRIX system to the DEC OSF/1 system.

3. Run-time performance of translated code on Alpha AXP computers that meets or exceeds the performance of the original code on the original architecture.

4. Optional reproduction of subtle old-architecture details, at the cost of run-time performance, e.g., complex instruction set computer (CISC) instruction atomicity for multithreaded applications and exact arithmetic traps for sophisticated error handlers.

5. If translation is not possible, generation of explicit messages that give reasons and specify what source changes are necessary.

While creating the VAX translator, we discovered the process of building flow graphs and tracking data dependencies yielded information about source code bugs, performance bottlenecks, and dependencies on features not available in all Alpha AXP operating systems. This analysis information could be valuable to a source code maintainer. Thus, we added one more product goal:

6. Optional source analysis information.

To achieve these goals, the team created two binary translators: VEST, which translates OpenVMS VAX binary images to OpenVMS AXP images, and mx, which translates ULTRIX MIPS images to DEC OSF/1 AXP images. However, binary translation is only half the migration process. As shown in Figure 2, the other half is to build a run-time environment in which to execute the translated code. This second half must bridge any differences between old and new operating systems, for example, calling standards, and exception handling. For open-ended translation, this part of the process must also include a way to run old code not discovered (or nonexistent) at translation time. The translated-image environment (TIE) and mxr run-time environment support the VEST and mx translators, respectively, by reproducing the old operating environment. Each environment supports open-ended translation by including a fallback interpreter of old code and extensive run-time feedback to avoid using the interpreter except for dynamically created code. Our design philosophy is to do everything feasible to stay out of the interpreter, rather than to increase the speed of the interpreter. This approach gives better performance over a wider range of programs than using pure interpreters or bounded translation systems.

The remainder of this article discusses the two binary translator/run-time environment pairs available for Alpha AXP computers: VEST/TIE and mx/mxr. To establish a basis for the discussion, the reader must understand the following terms: datum, alignment, instruction atomicity, granularity, interlocked update, and word tearing. (See box.)

VEST: Translating a VAX Image

Translating a VAX image involves two main steps: analyzing VAX code and generating Alpha AXP code. The translated images produced are OpenVMS AXP images and may be run just like native images [4]. Translated images run with the assistance of the translated image environment, discussed later. The VEST binary translator is written in C++ and runs on VAX, MIPS, and Alpha AXP machines. The TIE is written in the OpenVMS system programming languages, Bliss, and Alpha AXP assembler.

To locate VAX code, VEST starts disassembling code at known entry points and traces the program's flow of control recursively. Entry points come from main and global routines, debug symbol table entries, and optional information files (including run-time feedback from the TIE).

As VEST traces the program, it builds a flow graph that consists of basic blocks (i.e., straight-line code sequences) annotated with information derived from parsing instructions. Then, VEST performs several analyses on the flow graph to propagate context information to each basic block and eliminate unnecessary operations. Context information includes condition code usage, register contents, stack depth, and other information that allows VEST to generate optimized code.

Analysis is important for achieving good performance. For example, no condition codes exist in the Alpha AXP architecture. Without analysis it would be necessary to compute condition codes for each VAX instruction even if the codes were not used. Furthermore, several forms of analysis were invented to allow correct translation. For example, VEST determines automatically if a subroutine does a normal return.

Code analysis can detect many problems, including some that indicate latent bugs in the source image. For example, VEST can detect uninitialized variables, improperly formed VAX CASE instructions, stack depth mismatches along two different paths to the same code (the program expects data to be at a certain stack depth), improperly formed returns from subroutines, and modifications to a VAX call frame. A latent bug in the source image should be fixed, since the translated image may demonstrate incorrect behavior due to that bug.

Also, analysis detects the use of unsupported OpenVMS features including unsupported system services. The source image must be modified to eliminate the use of these features.

Some problems reported by VEST result from code that is hackish in nature. For example, we found code that expects a call mask at an entry point to be executed as a no-op instruction so that the code preceding the subroutine can simply execute the call mask, rather than go through the overhead of a VAX jump (JMP) instruction. VEST reproduces the behavior of the VAX program, even if this behavior is a result of luck.

A VEST-generated flow graph is displayed in Figure 3. Dashed lines represent code paths followed if a conditional branch is taken. Solid lines indicate fall-through paths. A problem is highlighted by a wide, dashed pointer whose bottom end indicates the basic block in which the problem was uncovered. Full blocks show the path that reveals the error; empty blocks show basic blocks that are not in the error path. In Figure 3, a path exists by which register 3 (R3) may be used without being set if the VAX BNEQ (branch if the register does not equal zero) instruction in the second basic block is true the first time through the code sequence.

Code Generation

The VEST translator generates code by converting each VAX instruction into zero or more Alpha AXP instructions. The architecture mapping is straightforward because there are more Alpha AXP registers than VAX registers. The VAX architecture has only 15 registers, which are used for both floating-point and integer operations. The Alpha AXP architecture has separate integer and floating-point registers. VAX registers R0 through R14 are mapped to Alpha AXP R0 through R14 for all operations except floating point. Registers R12, R13, and R14 retain their VAX designations as argument pointer, frame pointer, and stack pointer, and R15 is used to resolve PC-relative references. Floating-point operations are mapped to F0 through F14.

The VAX architecture has condition codes that may be referenced explicity. In translated images, condition codes are mapped into R22 and R23. Similar to the HP 3000 translator, R23 is used as a fast condition code register for positive/negative/zero results [1]. R22 contains all four condition code bits, which are calculated only when necessary. All remaining Alpha AXP registers are used as scratch registers or for OpenVMS AXP standard calls.

VEST connects simple branches directly to their translated targets. VEST performs backward symbolic execution of VAX instructions to resolve as many computed branch targets as feasible. If more than one possible computed target exists, a run-time lookup is done on the VAX target address. If the lookup fails to find a translated target, a fallback VAX interpreter is used, as described later. Unlike bounded translation systems, which must achieve 100% resolution of computed targets, the VEST and mx binary translators require no manual intervention.

Translated Images, Files Used

A translated image has the same format as an OpenVMS AXP image and contains the original OpenVMS VAX image as well as the Alpha AXP instructions that were generated for the VAX code. The run-time VAX interpreter in the TIE needs the original VAX instructions as a fallback. (Also, some error handlers look up the call stack for pointers to specific VAX instructions.) The addresses of statically allocated data in the translated image are identical to their VAX addresses. The image contains a VAX-to-Alpha AXP address-mapping table for use during lookups and may contain an instruction atomicity table, described later.

Translated images use the OpenVMS VAX calling standard. Native images use different conventions, but translated images inter-operate with native or translated shareable images. Automatic jacketing services are provided in the TIE to convert calls using one set of conventions into the other. In many cases, jacketing services permit substitution of a native shareable image for a translated shareable image without modification. However, a jacket routine is sometimes required. For example, on OpenVMS AXP systems, the translated Fortran run-time library, FORRTL_TV, invokes the native Alpha AXP library DEC$FORRTL for I/O-related subroutine calls. DEC$FORRTL has a different interface than FORRTL has on an OpenVMS VAX system. For these calls, FORRTL_TV contains hand-written jacket routines.

Translating an image requires only one file--a VAX-executable image. Several optional files make translation more effective:

1. Image information files (IIFs). VEST creates IIFs automatically to provide information about shareable image interfaces. The information includes the addresses of entry points, names of routines, and resource utilization.

2. Symbol information files (SIFs). VEST generates SIFs automatically to control the global symbol table in a translated shared library, facilitating interoperation between translated and native images.

3. Hand-edited information files (HIFs). The TIE generates HIFs automatically, which may be hand-edited to supply information that VEST cannot deduce. HIFs contain directives to tell VEST about undetected entry points, to force it to change specific assumptions about an image during translation, and to provide known interface properties to be propagated into an IIF.

VEST Performance Considerations

In evaluating translated-code performance, we recognized that there was a significant trade-off between the performance and accuracy of emulating the VAX architecture. VEST permits users to select several architectural assumptions and optimizations, including:

* D-float precision. The Alpha AXP architecture provides hardware support for D-float with only 53-bit mantissas, whereas the VAX architecture provides 56-bit mantissas. The user may select translation with either 53-bit software support (slower).

* Alignment. Alpha AXP instructions support only naturally aligned longword (32-bit) and quadword (64-bit) memory operations. Unaligned memory operations cause alignment faults, which are handled transparently by software at significant run-time expense. The user may direct VEST to assume that data references are unaligned whenever alignment information is unavailable.

* Instruction atomicity and memory granularity. Multitasking and multi-processing programs may depend on instruction atomicity and memory operation characteristics similar to those of the VAX architecture. VEST uses special code sequences to produce exact VAX memory characteristics. VEST and the TIE cooperate to ensure VAX instruction atomicity when instructed to do so.

Untranslatable Images

Some characteristics make OpenVMS VAX images untranslatable, including:

* Exception handler issues. Images that depend on examining the VAX processor status longword (PSL) during exception handling must be modified, because the VAX PSL is not available within exception handlers.

* Direct reference to undocumented system services. Some software contains references to unsupported and undocumented system services, such as an internal-to-VMS service, which parses image symbol tables. VEST highlights these references.

* Exact VAX memory management requirements. Images that depend on exact VAX memory management behavior do not function properly and must be modified. These images include those that depend on VAX page size or that expect certain objects to be mapped to particular addresses.

* Image format. Programs that use images as data are not able to read OpenVMS AXP images without modifications, because the image formats are different.

TIE Design Overview

The run-time translated-image environment, TIE, assists in executing translated OpenVMS VAX images under the OpenVMS AXP operating system. Figure 4 and Table 1 show the contents of TIE.

Complications may occur when translated OpenVMS VAX images are run under the OpenVMS AXP operating system: failure to find all code during translation, VAX instruction guarantees, instruction atomicity, memory update, and preserving VAX exceptions.

Failure to Find All Code During Translation

When the VEST binary translator encounters a branch or subroutine call to an unknown destination, VEST generates code to call one of the TIE lookup routines. The lookup routines map a VAX instruction address to a translated Alpha AXP code address. If an address mapping exists, then a transfer to the translated code is performed. Otherwise, the VAX interpreter executes the destination code. When the VAX interpreter encounters a flow-of-control change, it checks for returns to translated code. If the target of the flow change is translated code, the interpreter exists to this code. Otherwise, the interpreter continues to interpret the target.

Lookup operations that transfer control to the interpreter record the starting VAX code address in an HIF file entry. The VAX image can be retranslated then with the HIF information, resulting in an image that runs faster.

Lookup routines are used also to call native Alpha AXP (nontranslated) routines. The TIE supplies the required special autojacketing processing that allows interoperation between translated and native routines, with no manual intervention. At load time, each translated image identifies itself to the TIE and supplies a mapping table used by the lookup routines. The TIE maintains a cache of translations to speed up the actual lookup processing.

Every translated image contains both the original VAX code and the corresponding Alpha AXP code. When a translated image identifies itself, the TIE marks its original VAX addresses with the page protection called fault on execute (FOE). An Alpha AXP processor that attempts to execute an instruction on one of these pages generates an access violation fault, which is processed by a TIE condition handler to convert the FOE fault into an appropriate destination address lookup operation. For example, the FOE might occur when a translated routine returns to its caller. If the caller was interpreted, then its return address is a VAX code address instead of a translated VAX (Alpha AXP code) address. The Alpha AXP processor attempts to execute the VAX code and generates a FOE condition. The TIE condition handler converts this into a JMP lookup operation.

VAX Instruction Guarantees

Instruction guarantees are characteristics of a computer architecture that are inherent to instructions executed on that architecture. For example, on a VAX computer, if instruction 1 writes data to memory and instruction 2 writes data to memory, a second processor must not see the write from instruction 2 before the write from instruction 1. This property is called strict read-write ordering.

The VEST/TIE pair can provide the illusion that a single CISC instruction is executed in its entirety, even though the underlying translation is a series of RISC instructions. VEST/TIE can also provide the illusion of two processors updating adjacent memory bytes without interference, even though the underlying RISC instructions manipulate four or eight bytes at a time. Finally, VEST/TIE can provide exact memory read-write ordering and arithmetic exceptions, e.g., overflow. All these provisions are optional and require extra execution time. Tables 2 and 3 show the visibility differences between various guarantees on VAX and Alpha AXP systems as well as for translated VAX programs. [TABULAR DATA OMITTED]

Special Considerations for Instruction Atomicity

The VAX architecture requires that interrupted instructions complete or appear never to have started. Since translation is a process of converting one VAX instruction to potentially many Alpha AXP instructions, run-time processing must achieve this guarantee of instruction atomicity. Hence, a VAX instruction atomicity controller (IAC) was created to manipulate Alpha AXP state to an equivalent VAX state. When a translated asynchronous event-processing routine is called, the IAC is invoked. The IAC examines the Alpha AXP instruction stream and either (1) backs up the interrupted program counter to restart at the equivalent VAX instruction boundary or (2) executes the remaining instructions to the next boundary. Many VAX programs do not require this guarantee to operate correctly, so VEST emits code that is VAX instruction atomic only if the qualifier

/PRESSURE=INSTRUCTION_ ATOMICITY

is specified when translating an image.

VEST-generated code consists of four sections that are detected by the IAC. These sections have the following functions:

* Get operands to temporary registers

* Operate on these temporary registers

* Atomically update VAX results that could generate side effects (i.e., an exception or interlocked access)

* Perform any updates that cannot generate side effects (e.g., register updates)

The VAX interpreter achieves VAX instruction atomicity by using the atomic-move, register to memory (AMOVRM) instruction, which is implemented in privileged-architecture library (PAL) subroutines and which updates a contiguous region of memory containing VAX state without being interrupted. At the beginning of each interpreted VAX instruction, a read-and-set-flag (RS) instruction sets a flag that is cleared when an interrupt occurs on the processor. AMOVRM tests the flag, and if set, performs the update and returns a success indication. If the flag is clear, the AMOVRM instruction indicates failure, and the interpreter reprocesses the interrupted instruction.

Issues with Changing Memory

VAX instruction atomicity ensures that an arithmetic instruction does not have any partially updated memory locations, as viewed from the processor on which that instruction is executed. In a multiprocessing environment, inspection from another processor could result in a perception of partial results.

Since an Alpha AXP processor accesses memory only in aligned longwords or quadwords, it is therefore not byte granular. To achieve byte granularity, VEST generates a load-locked/store-conditional code sequence, which ensures that a memory location is updated as if it were byte granular. This sequence is used also to ensure interlocked access to shared memory. Longword-size updates to aligned locations are performed using normal load/store instructions to ensure longword granularity.

Many multiprocessing VAX programs depend on byte granularity for memory update. VEST generates byte-granular code if the qualifier

/PRESERVE=MEMORY_ ATOMICITY is specified when translating an image. In addition, VEST generates strict read-write ordering code if the qualifier

/PRESERVE=READ_WRITE_ ORDERING is specified when translating an image.

Preserving VAX Exceptions

Alpha AXP instructions do not have the same exception characteristics as VAX instructions; for instance, an arithmetic fault is imprecise, i.e., not synchronous with the instruction that caused it. The Alpha AXP hardware generates an arithmetic fault that is mapped into an OpenVMS AXP high-performance arithmetic exception (HPARITH) exception. To retain compatibility with VAX condition handlers, the TIE maps HPARITH into a corresponding VAX exception when calling a translated condition handler. Most VAX languages do not require precise exceptions. For those that do, such as BASIC, VEST generates the necessary trap barrier (TRAPB) instructions if

/PRESERVE=FLOATING_ EXCEPTIONS is specified when translating an image.

OpenVMS AXP and OpenVMS VAX Differences

Functional Differences Most OpenVMS AXP system services are identical to their OpenVMS VAX counterparts. Services that depend on a VAX-specific mechanism are changed for the Alpha AXP architecture. The TIE intervenes in such system services to ensure the translated code sees the old interface.

For example, the declare change mode handler ($DCLCMH) system service establishes a handler for VAX change mode to user (CHMU) instructions. The handler is invoked as if it were an interrupt service routine, required to use the VAX return from interrupt or exception (REI) instruction to return to the invoker's context. On OpenVMS AXP systems, the handler is called as a normal procedure. To ensure compatibility, the TIE inserts its own handler when calling OpenVMS AXP $DCLCMH. When a CHMU is involked on Alpha AXP computers, the TIE handler calls the handler of the translated image, using the same VAX-specific mechanisms that the handler expects.

Exception Handling

OpenVMS AXP exception processing is almost identical to that performed in the OpenVMS VAX system. The major difference is that the VAX mechanism array needs only to hold the value of two temporary registers, R0 and R1, whereas the Alpha AXP mechanism array needs to hold the value of 15 temporary registers, R0, R1, and R16 through R28.

Complex Instructions

Translating some VAX instructions would require many Alpha AXP instructions. Instead, VEST generates code that calls a TIE subroutine. Subroutines are implemented in two ways: (1) hand-written native emulation routines, e.g., MOVC5, and (2) VEST-translated VAX emulation routines, e.g., POLYH.

Together, VEST and TIE can translate and run most existing user-mode VAX binary images. As shown in Table 4, performance of translated VAX programs slightly exceeds the original goal. Performance depends heavily on the frequency of use of VAX features that are not present in Alpha AXP machines.

ULTRIX MIPS Translation

The translator that converts ULTRIX MIPS programs to DEC OSF/1 AXP programs is called mx. The mx project started after VEST was functional, and we took advantage of the VEST common code base for much of the analysis and Alpha AXP code assembly phases of the translator. In fact, about half of the code in mx is compiled from the same source files as those used for VEST, with some architectural specifics supplied by different include files. The C++ language has proven quite valuable in this regard.

mxr is the run-time support system for translated programs. It provides services similar to TIE, emulating the ULTRIX MIPS environment on a DEC OSF/1 AXP system. mxr is written in C++, C, and Alpha AXP assembler.

Challenges

Creating a translator for the MIPS R2000/R3000 architecture presented a host of new opportunities, along with some significant challenges. The basic structure of the mx translator is considerably simpler than that of VEST. Both the source and the target architectures are RISC machines; therefore, the two instruction sets have a considerable similarity. Many instructions translate one for one. The MIPS architecture has very few instruction side effects or subtle architectural details, although those that are present are particularly tricky. Futhermore, the format of an excutable program under the ULTRIX system collects all code in a single contiguous segment and makes it easy for mx to reliably find almost 100% of the code in the MIPS application. The system interfaces to the ULTRIX and DEC OSF/1 systems are similar enough that most ULTRIX system call have functionally identical counterparts under the DEC OSF/1 system.

The challenges in mx stem from the fact that the source architecture is a RISC machine. For example, DEC OSF/1 AXP is a 64-bit computing environment, i.e., all pointers used to communicate with the operating system are 64 bits wide. This environment does not present a problem when the pointer is passed in a register. However, when a pointer (or a long data item, such as a file size) is passed in memory, it must be converted between the 32-bit representation, used by the ULTRIX system, and the 64-bit AXP representation, even when the semantics of the operating system call are the same on both systems.

A significant challenge is the fact that our users' expectations for performance of translated programs are much higher than for VEST. Reasoning that the source and target machines are similar, users expect mx to achieve a translated program performance better than that of the source program, since Alpha AXP processors are faster. Thus, the performance goal was producing a translated program that runs at about the same speed as the original program would run on an MIPS R4000 machine with a 100MHz internal clock rate. [TABULAR DATA OMITTED]

Mapping the Architectures

It appears, at first glance, that we could simply assign each MIPS register to a corresponding Alpha AXP register, because each machine has 32 general-purpose registers. The translated code would then have two scratch registers, since the MIPS architecture does not allow user-level programs to use registers K0 and K1, which are reserved for the operating system kernel.

Unfortunately, translation requires more than two scratch registers. The Alpha AXP architecture does not have byte or halfword (16-bit) loads or stores, and the code sequences for performing these operations require four or five scratch registers. Furthermore, mx requires a base register to locate mxr without having to load a 64-bit address constant at each call. Finally, the MIPS architecture has more than 32 registers, including the HI and LO registers used by the multiply-and-divide instructions, and a floating-point condition register, whose layout and contents do not correspond to the Alpha AXP floating-point condition register.

In mx, we assign registers using standard compiler techniques. To assign registers to 33 MIPS resources (the 32 general registers plus one 64-bit register to hold both HI and LO), certain registers are permanently mapped, and other MIPS registers are kept in either AXP registers or memory. The MIPS argument-passing registers A0 through A3 are permanently assigned to Alpha AXP registers R16 through R19, which are the argument registers in the DEC OSF/1 AXP calling standard. This correspondence simplifies the work needed when mxr must take arguments for an ULTRIX system call and pass them to a DEC OSF/1 system call. Similarly, the argument return registers V0 and V1 are mapped to the Alpha AXP argument return registers R0 and R1. The return address registers and stack pointer registers of the two machines are also mapped. MIPS R0 is mapped to Alpha AXP R31, where both registers contain the same hardwired zero value. We reserve Alpha AXP registers and use them also when interfacing to mxr. We reserve Alpha AXP R14 as a pointer to an mxr communication area. Finally, we reserve three more registers as scratch registers for use by the code generator.

The remaining 16 Alpha AXP registers are available to be assigned to the remaining 23 MIPS resources. After the code is analyzed and we have register usage information, the 16 most frequently used MIPS registers are mapped to the 16 remaining Alpha AXP registers, and the remaining registers are assigned to memory slots in the mxr communication area. When a MIPS basic block uses one of the slotted registers, mx assigns it to one of the scratch registers. If the first reference reads the old contents of the register, mx generates a load instruction from the communications area. If the value of the MIPS resource changes in the basic block, the scratch register is stored in the communication area before the end of the block. As in most compilers, if we run out of registers, a spill algorithm chooses a value to save in the communication area and frees up a register.

Alpha AXP integer registers are 64 bits wide, whereas MIPS registers are only 32 bits wide. We chose to keep all 32 bits values in Alpha AXP integer registers as sign-extended values, with the high 32 bits equal to bit 31. This approach occasionally requires mx to generate additional code to create canonical 32-bit integer results, but the 64-bit compare operations do not need to change the values that they are comparing.

The floating-point architecture is more complex. Each of the 32 MIPS floating-point registers is 32 bits wide. Only the even registers are used for single precision, and a double-precision number is kept in an even-odd register pair. We map each pair of MIPS floating-point registers onto a single 64-bit Alpha AXP floating-point register. Also, one Alpha AXP floating-point register represents the condition code bit of the MIPS floating-point control register. Thus, the mx code generator can use 14 scratch registers. mx goes to considerable effort to find paired loads and stores in the MIPS code stream and merge them into one Alpha AXP floating-point operation.

MIPS single-precision operations cause problems with floating-point correspondence. Since the single-precision number on MIPS machines is kept in only the even register of the register pair, the even and odd registers in a pair are independent when single-precision (or integer) operations are done in the floating-point unit. On Alpha AXP machines, computation must be done on a value extended to double format in the whole 64-bit register. We defined two forms for values in Alpha AXP floating-point registers: computational form, in which computation is done, and canonical form, which mimics the MIPS even and odd registers. If a MIPS program loads an even register and uses this register as a single-precision value, mx loads the value from memory to be used computationally. If a MIPS program loads an even register only but does not use this register in the basic block, mx puts the 32-bit value into half of the Alpha AXP floating-point register. This permits correct behavior in the pathological case where half of a floating-point number is loaded in one place, and the other half is loaded in some other basic block. If a register is used as a single-precision number in basic block without first being loaded, the code generator inserts code to convert it from canonical to computational floating-point form. If a single-precision value has been computed in a block and is live at the end of the block, it is converted to canonical form.

mx inserts a register-mapping table into the translated program that indicates (1) which MIPS resources are statically mapped to which Alpha AXP registers and (2) which MIPS resources are normally kept in memory. This table allows mxr to find the MIPS resources at run time.

Finding Code

As with the VEST translator, mx finds code by starting at entry points and recursively tracing down the flow of control. mx finds entry points using the executable-file header, the symbol table (if present), and feedback from mxr (if present). Finally, mx performs a linear scan of the entire text section for unexamined longwords. mx analyzes any data that looks like plausible code but does not connect this data into the main flow graph. Plausible code consists of a series of valid MIPS instructions terminated by an unconditional transfer of control.

While finding code and connecting the basic blocks into a flow graph, mx looks for the code sequence that indicates a switch statement, i.e., a multi-way branch, usually through an element of a table. mx finds the branch table and connects each of the possible targets as successors of the branch.

Code Analysis

Static analysis of hundreds of MIPS programs indicates that only 10 instructions account for about 85% of all code. These instructions are LW, ADDIU, SW, NOP, ADDU, BEQ, JAL, BNE, LUI, and SLL. The corresponding sequences of Alpha AXP code range from zero operation codes (opcodes) for NOP, since the Alpha AXP architecture does not require NOPs anywhere in the code stream) to two opcodes (for SLL).

Code analysis for source programs is much more important in mx than in VEST, because the coding idioms for many common operations differ between the Alpha AXP and MIPS processors. The simple technique of mapping each MIPS instruction to a sequence of one or more Alpha AXP instructions loses much of the context information in the original program.

For example, the idiom used to load a 32-bit constant into a register on MIPS machines is to generate a load upper immediate (LUI) opcode, placing a 16-bit constant in the high-order 16-bits of a register. This operation is followed by an OR immediate (ORI) opcode, logically ORing a 16-bit zero-extended value into the register. The LUI corresponds exactly to the Alpha AXP load address high (LDAH) opcode. However, the Alpha AXP architecture has no way to directly ORing a 16-bit value into a register and cannot load even a zero-extended 16-bit constant into a register. When the high-order bit of the 16-bit constant is 1, the shortest translation for the ORI is three instructions. The mx translator scans the code looking for such idioms and generates the optimal two-instruction sequence of Alpha AXP code that performs the 32-bit load. No opcode exists that corresponds to the ORI, but the results in the registers are correct.

We thought we would never see a number of code possibilities. In retrospect, this proved to be a misguided assumption. For example, we have seen programs that branch into the delay slot of other instructions, requiring us to indicate that the delay slot instruction is a member of two different basic blocks--the block it ends and the one it starts. We have observed programs that put software breakpoint (BREAK) instructions in the branch delay slot, and thus BREAK ends a basic block without being the last instruction. Some compilers schedule code so that half of a floating-point register is stored and then reused before the other half is stored. The general principle that we intuit from these observations is "if a code sequence is not expressly prohibited by the architecture, some program somewhere will use it."

Code Generation

After the program is parsed and analyzed and the flow graph is built, the code generator is called. It builds the register-mapping table, then in turn, processes each basic block, generating Alpha AXP code that performs the same functions as the MIPS code.

At each subroutine entry, mx scans the code stream with a pattern-matching algorithm to see if the code corresponds to any of a number of standard MIPS library routines, such as strcpy. (Note that the ULTRIX operating system has no shared libraries, so library routines are bound into each binary image.) If a correspondence exists, the entire subroutine is recursively deleted from the flow graph and replaced with a canned routine to perform the subroutine's work on Alpha AXP processors. This technique contributes significantly to the performance of translated programs.

For each remaining basic block, the instructions are converted to a linked list of intermediate opcodes. At first, each opcode corresponds exactly to a MIPS opcode. The list is then scanned by an optimization phase, which looks for MIPS coding idioms and replaces them with abstract machine instructions that better reflect the idiom. For example, mx changes (1) loads of immediate values to a non-MIPS hardware load immediate (LI) instruction, (2) shift and add sequences to abstract operations that reflect the Alpha AXP scaled add and subtract sequences, and (3) sequences that change the floating-point rounding mode (used to truncate a floating-point number to an integer) to a single opcode that represents the Alpha AXP convert operation with the chopped mode (/C) modifier.

MIPS code contains a number of common code sequences that cross basic block boundaries, but which can be compressed into a single basic block in Alpha AXP code. Examples of these are the min and max functions, which map neatly onto a single conditional move (CMOV xx) instruction in Alpha AXP code. The code generator looks for these sequences, merges the basic blocks, and creates an extended basic block, which includes pseudo-opcodes that indicate the MIPS code idiom.

After the optimizer completes the list of instructions, it translates each abstract opcode to zero or more Alpha AXP opcodes, again building a linked list of instructions. This process may permit further improvements, so the optimizer makes a second pass over the Alpha AXP code.

When processing a basic block, the code generator assumes that it has an unlimited number of temporary resources. Since this is not actually true, the code generator then calls a register assigner to allocate the real Alpha AXP temporary resources to the intermediate temporary registers. The register assigner will load and spill MIPS resources and generate temporary registers as needed.

Finally, the list of Alpha AXP instructions is assembled into a binary stream, and the instruction scheduler rearranges them to remove resource latencies and use the chip's multiple-issue capability.

Image Formats

The file format for input is the standard ULTRIX extended common object file format (COFF). In most ULTRIX MIPS programs, the text section starts at 00400000 (hexadecimal) and the data at 10000000 (hexadecimal). In virtually all programs, a large gap exists between the virtual address for the end of text and the start of the data section. When mx creates the output image, it places the generated Alpha AXP code after the MIPS code and before the MIPS data. This allows the program to have one large text section. The Alpha AXP code begins at an Alpha AXP page boundary, so that we can set the memory protection on the MIPS code separately from the Alpha AXP code.

The translated image is not in DEC OSF/1 AXP executable format. Instead, it looks like a MIPS COFF file, but with the first few bytes changed to the string "#!/usr/bin/mxr".

Executing a Translated Program

When a translated image is run on DEC OSF/1 AXP, its modified header invokes mxr first, mxr uses the memory map (mmap) system call to load the translated program at the same virtual address that it would have had under the ULTRIX operating system. mxr resets the protection of the MIPS code to read/no-write/no-execute, the Alpha AXP code to read/no-write/execute, and the data to read/write/no-execute. Table 5. Translated MIPS Relative Performance
                         MIPS Time on        Translated Time
                         DECstation          on DEC 3000 AXP
  Program                5000/240            Model 500
  SPECint92              (40 MHz)            (150 MHz)
  espresso               2.4                 1.1 (1.0)(1)
  li                     1.6                 1.2 (1.0)
  eqntott                1.6                 2.1 (1.0)
  compress               2.7                 1.0 (1.0)
  sc                     __(2)               __
  gcc                    2.1                 1.2 (1.0)
  Geometric Mean         2.0                 1.3 (1.0)


(without sc)

SPECfp92
  spice2g6               --                  --
  doduc                  1.7                 1.0
  mdljdp2                2.7                 1.0
  wave5                  1.1                 1.0
  tomcatv                3.0                 1.0
  ora                    1.5                 1.0
  alvinn                 1.6                 1.0
  ear                    1.7                 1.0
  mdljsp2                1.4                 1.0
  swm256                 2.3                 1.0
  su2cor                 2.7                 1.0
  hydro2d                2.9                 1.0
  nasa7                  2.6                 1.0
  fpppp                  2.2                 1.0
  Geometric Mean         2.0                 1.0


(without spice2g6)

(1) The values in parentheses are from running once, then retranslating with the run-time feedback from the first run; this gave a significant performance difference only for the programs shown. (2) Timing information for this run is not available. NOTE: The larger the number, the slower the performance. These performance numbers were measured on derated field test hardware and software at various times during 1992; production results will vary somewhat. The SPEC benchmarks are written in FORTRAN and C; no conclusions should be drawn about other classes of programs written in other languages.

NOTE: The larger the number, the slower the performance. These performance numbers were measured on derated field test hardware and software at various times during 1992; production results will vary somewhat. The SPEC benchmarks are written in FORTRAN and C; no conclusions should be drawn about other classes of programs written in other languages.

Then mxr allocates a communication area and initializes Alpha AXP R14 to point to this area. The communication area contains save areas for MIPS resources, initialized pointers to mxr services routines, and other scratch space. mxr then constructs new command argument (argv) and environment vectors as 32-bit wide pointers (as the MIPS program expects), arranges to intercept certain signals from the DEC OSF/1 AXP system, and transfers control to the translated start address of the program.

When a system signal is delivered to the program, control goes to the signal intercept code in mxr. This code transforms the signal context structure from the DEC OSF/1 AXP system and constructs a ULTRIX MIPS style context, which it passes then to the translated signal handler.

Certain signals are processed specially. For instance, a program that attempts to transfer control to a location containing MIPS code rather than translated code gets a segmentation violation, since the MIPS code is not executable. This situation can occur if a routine modifies its return address to be a MIPS address constant. mxr will examine the target address and, if it corresponds to the start of a pretranslated MIPS basic block, divert the flow of control to the translated code for that block. If not, mxr enters the MIPS interpreter. The interpreter proceeds to emulate the MIPS code until a translated point is reached. mxr then resynchronizes its machine state and reenters the translated code.

Translation Goals and Classes of Programs Not Supported

Our goal was to translate most user mode MIPS programs compiled for a MIPS R2000 or R3000 machine running ULTRIX Release 4.0 (or later) to run identically on the DEC OSF/1 AXP system with acceptable performance. As shown in Table 5, performance of translated MIPS programs meets or exceeds the original goal.

Due to extreme technical obstacles, some classes of programs will never be supported by mx. We decided not to translate programs that use privileged opcodes or system calls or that need to run with superuser privileges. In cases where the file system hierarchy differs between the ULTRIX and DEC OSF/1 AXP systems, programs that expect files to be in particular places or in a particular format may fail. Similarly, programs that read /dev/kmem and expect to see an ULTRIX MIPS memory layout fail.

Certain other classes of programs are not currently supported, but are technically feasible. These include big-endian MIPS programs from non-Digital MIPS environments, programs that use R4000 or R6000 instructions that are not present on the R3000 model, programs that need to be multiprocessor safe, and programs that require certain categories of precise exception behavior.

Summary

Building successful, turnkey binary translators requires hard work but not magic. We built two different translators, VEST and mx. In both cases, the old and new environments are, by design, quite similar in fundamental data types, memory addressing, register and stack usage, and operating system services. Translators between dissimilar architectures or operating systems are a different matter. Translating the code might be a reasonably straightforward task. However, emulating a run-time environment in which to execute the code might present insurmountable technical and business obstacles. Without capturing the environment, an instruction translator would be of no use.

References

[1.] Bergh, A., Keilman, K., Magenheimer, D. and Miller, J. HP 3000 emulation on HP Precision Architecture computers. Hewlett-Packard J. (Dec. 1987).

[2.] Echo Logic, Inc. News Release (May 4, 1992).

[3.] Hunter, C. and Banning, J. DOS at RISC. Byte Mag. (Nov. 1989), 361-368.

[4.] Kronenberg, N. et al. Porting OpenVMS from VAX to Alpha. Commun. ACM 36, 2 (1993).

[5.] Sites, R., Ed. Alpha Architecture Reference Manual. Digital Press, Burlington, Mass., 1992.

[6.] Sites, R. Alpha AXP architecture. Commun. ACM 36, 2 (1993).

[7.] Wirbel, L. DOS-to-UNIX compiler. Electr. Eng. Times (Mar. 14, 1988), 83.

Related article: Terminology

Alignment is the property of a datum of size [2.sup.n] bytes. This datum is alligned if its byte address has n nlow-order zeros. A size or address not meeting thisnconstraint implies that the datum is unaligned.

Granularity is the property of memory writes on multiprocessor systems such that independent writes to adjacent aligned data produce consistent results. The terms byte, word, longword, quadword, and octaword granularity refer to writing 1-, 2-, 4-, 8-, and 16-byte size adjacent data.

Instruction atomicity is the property of instruction execution on single-processor systems such that an interrupted instruction has been completed or has never started, i.e., partial execution of an instruction is never observed.

Interlocked update is the property of memory updates (read-modify-write sequences) on multiprocessor systems such that simultaneous independent updates to the same aligned datum will be consistent. This property causes serialization of the independent read-modify-write sequences and is not guaranteed for an unaligned datum.

Word tearing is the property of aligned memory writes on multiprocessor systems such that a reader independent of the writer can see partial results of the write.

Related article: Design of EV-4

EV-4 is the internal code name for the DECchip 21064 microprocessor which represents the first implementation of the Alpha AXP architecture. The overriding functional goals of high performance and longevity presented the EV-4 design team with significant challenges that directly influenced the design style and the implementation particulars of the chip. The design had to deliver exceptional performance through speeds surpassing existing technologies and through complex functions such as multiple issue.

EV-4 is a 1.4 by 1.7-cm CMOS chip incorporating 1.68 million transistors. It is a super-scalar super-pipelined processor design, using dual instruction issue, that has sampled up to 200MHz cycle time. The CMOS process is a .75 micron, three-layer metal technology with a .5 micron channel length.

The accompanying figure depicts the major functional blocks of the EV-4, which include 8KB 1-cache, 8KB D-cache and two associated translation buffers, a four-entry 32B/entry write buffer, a pipelined 64B integer execution unit with 32-entry register file (IRF + EBOX), and a pipelined floating-point unit with an additional 32 registers (FRF + FBOX). The Bus interface Unit (BIU) handles all communication between the chip and external components.

The development of EV-4 resulted from a combination of the Alpha AXP architecture, Digital's CMOS process technology, and an innovative design and implementation approach. The basis of this handcrafted design approach allowed the EV-4 designers to achieve optimum microprocessors performance. Custom CAD tools, complementing the design style, empowered the designers in their efforts and gave them the means to verify and model design implementations such as a single-wire clock and on-chip decoupling capacitance.

Chips will continue to grow, features will continue to shrink, and switching speeds will continue to increase. Current microprocessor chips contain nearly two million transistors. In the next two years, 10 million transistor computer systems on a chip will emerge. More layers of wires, denser memory structures and high-performance mixed analog and digital capabilities will be developed. To manage total chip power and realize more efficient speed-power product characteristics, the power supply will continue to decrease; first to 2.5V and eventually to 1.8V. The target for the year 2000, as stated by Intel's Andrew Grove, is 100 million transistor systems on a chip. Digital's CMOS technology development and microprocessor design teams are aimed at that target.
COPYRIGHT 1993 Association for Computing Machinery, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 1993 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:contains related articles on terminology used in the main article, the design of the DECchip 21064 microprocessor and the technology used in the 21064 microprocessor; one of four articles on DEC's Alpha architecture; running the binary code of DEC's VAX and MIPS architectures on the company's new Alpha AXP computers
Author:Sites, Richard L.; Chernoff, Anton; Kirk, Matthew B.; Marks, Maurice P.; Robinson, Scott G.
Publication:Communications of the ACM
Article Type:Cover Story
Date:Feb 1, 1993
Words:8532
Previous Article:The Alpha Demonstration Unit: a high-performance multiprocessor.
Next Article:Calendar of events.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters