UML Architecture
This article describes the Universal Machine Language runtime architecture.
Machine Architecture
At its heart, the Universal Machine Language describes an abstract, primarily 32-bit computer architecture. It has been designed with several goals in mind:
- dynamic recompilers should be able to express common operations simply
- 64-bit integer operations should be supported, even if they are not preferred
- creating x86 and PowerPC back-ends (both 32-bit and 64-bit) should be relatively straightforward
- a back-end written in a high-level language such as C should have reasonable performance
In addition to a collection of opcodes, described below, the Universal Machine Language also describes an abstract runtime architecture with several basic requirements:
- 10 64-bit integer registers (i0-i9)
- 10 64-bit floating point registers (f0-f9)
- 10 32-bit "map variables" (m0-m9) which map values onto sections of code
- 5 flag bits that can be optionally set on most instructions
- 1 internal exception parameter register
- a 16-entry call stack for subroutine and exception handling
Because each back-end targets a different final CPU architecture, these abstract requirements may not map perfectly; however, it is the job of the back-end code generator to provide an implementation that fully supports all of these requirements. For example, there may not be enough free actual system registers to hold 10 64-bit values, so some of those registers may be implicitly converted by the backend into memory references. More details on how to provide these abstractions will be available in the Back-End Author's Guide.
Code Cache
One of the primary features of a dynamic recompiler is its ability to cache and quickly recall already-translated code. Because of this, the concept of a code cache is central to the UML. The code cache not only contains all the generated code, along with the necessary hash tables to find it, but it also serves as a general heap for any data referenced by the generated code. Memory can be allocated from the cache and thus kept in the vicinity of the code that is likely to reference it. On many architectures, memory that is close to the code can be more efficiently accessed, so it is important to make good use of the memory management provided by the cache.
The cache is created by the dynamic recompiler at initialization time. The size of the cache is fixed once it is created, so it is important to create a cache that is large enough to hold a typical translated working set. If the cache is too small, then code will be flushed from it relatively quickly, and your CPU usage will increase because you are spending extra time to re-translate code that could have been executed from the cache.
The cache is divided into three sections. The topmost section is known as the near cache and is a fixed size (64k). The near cache is where frequently-accessed data should be stored. Generally this includes the current architectural state of the CPU that is being emulated, along with tables or other data that is frequently accessed by the UML code. It is also important to realize that many UML opcodes support using memory locations as parameters, but only if those memory locations are within the near cache.
The bottommost section of the cache is where permanent memory allocations are taken from. Data structures that are used and re-used throughout the lifetime of the dynamic recompiler are allocated here. When memory is allocated from this section, the cache end is moved downward, reducing the amount of free space in the cache. Although memory that has been allocated from this section can be freed, it does not affect the position of the cache end. Rather, that data is kept in a free list and re-used for the next memory allocation of a similar size.
The middle section of the cache is where the most action is. This is where all temporary memory allocations and code generation takes place. It starts at the cache base, which is simply fixed at the end of the near cache, and can expand as far as the cache end, which is where the permanent memory allocations lie. The cache top represents the position within this region where the next code will be generated or the next block of memory allocated. As code is generated and added to the cache, the cache top moves forward until it reaches the cache end. When that happens, the cache is flushed. A flush simply resets the cache top back to the cache base, effectively throwing away everything that has accumulated in this middle section and starting over.
Although it could be argued that there might be value in keeping some frequently-used cached code around when running out of space, in practice it is not worth the extra bookeeping necessary to make that determination. The dynamic recompiler and back-end should operate relatively quickly, making the performance hit of regenerating the code minimal.
Code Generation
UML code is generated in blocks. A block of UML code is defined to be self-contained. That is, all local jumps within the code are resolved, and all calls or jumps to code outside of the block are performed via either code handles or code hashes, which are described below. In general, a code block is either a subroutine or a translated sequence of code. The dynamic recompiler generates the block one instruction at a time using helper functions and macros provided by the UML system, which in response encodes the instruction opcodes and parameters into a sequence of structures. Once a block is complete, the dynamic recompiler notifies the UML system, who takes the list of structures and hands it off to the back-end to perform final translation.
One potential problem is that during code generation, the back-end may run out of space in the cache. When this happens, the cache needs to be flushed, and whatever was being generated needs to be regenerated from scratch. To accomplish this, the UML makes use of setjmp/longjmp. Before a block is started, the dynamic recompiler performs a setjmp and passes the jump buffer to the UML. If at any time the cache runs out of space, the UML performs a longjmp back to the starting point, which is responsible for flushing the cache and starting the codegen over again.
Code Flow
Becase the details of back-end code generation are abstracted, code flow becomes a little tricky, since the addresses of the code you wish to jump to are not known until the back-end translates to the final code. To remedy this, the UML introduces three concepts: code handles, code hashes, and code labels.
A code handle is a globally accessible reference to a block of code. In practice, a code handle is allocated from the near cache by the dynamic recompiler and contains a pointer to the generated code provided by the back-end. When first allocated, a code handle is empty, since the back-end hasn't had a chance to generate the final code yet. Similarly, when the cache is flushed, all code handles are automatically reset to their empty state, since any code they referenced has been jettisoned. During back-end code generation, when a HANDLE opcode is encountered, the back-end will fill in the code handle's code pointer with the current cache top, which is where subsequent code will be generated.
To execute code referenced by a handle, the dynamic recompiler calls the UML from C code, passing in the handle where it should begin execution. A pointer to the generated code for this handle is extracted from the handle and then the back-end is called to begin execution. UML code can also make subroutine calls to handle-based code via the CALLH opcode, or it can invoke handle-based code to handle an exception via the EXH opcode.
A code hash is a more indirect way to create a global reference to a block of code, more typically used for hopping between blocks of translated code. As its name implies, a code hash is filed away in a hash table or some other structure that is maintained by the back-end code. A code hash is represented by two values: a PC, which is typically the linear address of a block of code, and a mode, which allows further differentiation between code which may live at the same PC but execute in different contexts. During back-end code generation, when a HASH opcode is encountered, the back-end will take the PC and mode specified in the opcode and create an entry in its hash table pointing to the current cache top.
The only way to execute code referenced in the hash table is via the UML opcode HASHJMP, which accepts a mode and PC, performs the lookup, and either continues execution at the target code entry, or generates an exception if no code exists for that hash entry.
A code label is a mechanism to handle branches within a block. Code labels can be seen as analagous to labels in a typical assembly language. The primary difference is that the label itself is the UML opcode LABEL with a 32-bit integer identifier that must be unique within the block. Because the label itself is an opcode, it is easy for the back-end to determine whether a given instruction can be blended with neighboring instructions, since branches can only occur to the label opcodes. Labels are not resolved until back-end code generation, so if you make a mistake and reference an invalid label or forget to define a label, it won't be caught until the block is ended.
Code labels can be branched to via the JMP instruction, either unconditionally or via one of 16 conditions.
Opcodes
Below is an exhaustive list of opcodes and their defined behaviors. Before diving into the details, however, there are some general principles and conventions which must be understood:
Integer Registers. There are 10 integer registers, each 64-bits wide. The same registers are used for both 32-bit and 64-bit opcodes; however, unlike many real computer architectures, the upper 32 bits are fully undefined when a 32-bit operation is performed. This means you cannot load a 64-bit value, perform a 32-bit operation, and expect the upper 32 bits to be anything in particular when you are finished.
Most back-ends are expected to assign as many integer registers to native integer registers as possible; however, some architectures do not support mapping all 10 registers in this way. Because of this, dynamic recompilers should try to use the first few registers aggressively, only resorting to the later registers where necessary.
The contents of the integer registers are lost whenever an EXIT opcode is encountered.
Floating Point Registers. As with the integer registers, there are 10 floating point registers, each 64-bits wide. The same registers are again used for both 32-bit and 64-bit opcodes, and the upper 32 bits are fully undefined when a 32-bit operation is performed.
Back-end support for floating point registers is often even more limited than support for integer registers, so dynamic recompilers should focus on using the first few registers as much as possible.
The contents of the floating point registers are lost whenever an EXIT opcode is encountered.
Immediates. Immediate values can be up to 64-bits wide. Of course, it only makes sense to use immediate values that fit in the size of the opcode.
Memory Parameters. Memory parameters can be used in most of the places where register parameters are permitted. The memory parameter size is implicitly determined by the opcode. Most importantly, for the majority of instructions, any memory parameters must reside in the near cache. This is to ensure that they can be efficiently accessed on all architectures. The lone exceptions to this rule are the LOAD and STORE opcodes, which can be used to access memory anywhere.
Map Variables. Map variables are constant values that are encoded into the instruction stream. They are used to recover values when a subroutine or exception occurs, based on the caller's address. Map variables are only 32-bits wide and when used in code always translate into immediate values.
Flags. There are 5 flags defined by the architecture:
- C (bit 0) is the carry flag, and indicates an unsigned carry in arithmetic operations or the shift-out value in rotate/shift operations
- V (bit 1) is the overflow flag, and indicates a signed overflow in arithmetic operations
- Z (bit 2) is the zero flag, and indicates a zero result
- S (bit 3) is the sign flag, and indicates a negative result
- U (bit 4) is the unordered flag, and indicates that a floating point compare had at least one NaN parameter
Opcodes which can affect the flags must specify which flags they care about. Flags that are not explicitly requested are undefined.
Conditions. Control flow instructions and simple data move instructions support an optional condition, which allows behavior to occur based on the state of the flags. Each flag can be checked for on/off independently. In addition, the usual collection of G/GE/L/LE/A/AE/B/BE conditions are available.
Control Flow Opcodes
CALLC
Usage:
CALLC function,parameter[,condition]
Parameters:
- function — a memory pointer to a C function of the form
void cfunction(void *parameter) - parameter — a memory pointer that is passed as the argument to the C function
- condition — an optional condition which is used to determine whether or not to execute the call
Flags:
- C — undefined
- V — undefined
- Z — undefined
- S — undefined
- U — undefined
Description: The CALLC opcode is used to execute a C function from within the generated code. A single parameter may be passed to the function. More data can be effectively passed by using the parameter to point to a communication block. Upon return from the C function, all registers retain their original values; however, all flags are left in an undefined state.
Like most control flow opcodes, CALLC can be used either unconditionally or flagged with a condition that controls whether or not the target function is called.
CALLH
Usage:
CALLH handle[,condition]
Parameters:
- handle — a memory pointer to a previously-allocated code handle
- condition — an optional condition which is used to determine whether or not to execute the call
Flags:
- C — undefined
- V — undefined
- Z — undefined
- S — undefined
- U — undefined
Description: The CALLH function makes a subroutine call to the code referenced by the given handle. Note that although the handle must have already been allocated, it is permitted to pass a handle which has not yet been populated by code. The back-end code generator must support both cases, though it will generally output less efficient code if the handle is not yet populated (since it must fetch the address at runtime from the handle).
Like most control flow opcodes, CALLH can be used either unconditionally or flagged with a condition that controls whether or not the target function is called.
COMMENT
Usage:
COMMENT string
Parameters:
- string — a memory pointer to character string
Flags:
- C — maintained
- V — maintained
- Z — maintained
- S — maintained
- U — maintained
Description: The COMMENT opcode exists to provide a means of documenting the UML code. Comments are generally ignored completely by the back-end and typically generate no code. However, they do show up in the disassembly of UML code, and may optionally propogate to disassembly of generated code as well.
DEBUG
Usage:
DEBUG pc
Parameters:
- pc — a 32-bit integer register, memory location, map variable, or immediate
Flags:
- C — undefined
- V — undefined
- Z — undefined
- S — undefined
- U — undefined
Description: The DEBUG opcode indicates that, if the debugger is present, it should be updated with the provided pc as the current instruction. To properly support the built-in debugger, this opcode should be present before the execution of each instruction. Before issuing a DEBUG opcode, be sure to flush any cached state (including the PC) to its target memory location so that the debugger can properly examine it or modify it. Upon completion of this opcode, all registers retain their original values; however, all flags are left in an undefined state.
EXH
Usage:
EXH handle,parameter[,cond]
Parameters:
- handle — a memory pointer to a previously-allocated code handle
- parameter — a 32-bit integer register, memory location, map variable, or immediate
- condition — an optional condition which is used to determine whether or not to generate the exception
Flags:
- C — undefined
- V — undefined
- Z — undefined
- S — undefined
- U — undefined
Description: The EXH function generates an exception, which is effectively a subroutine call with a special parameter. The code to call is referenced by the given handle. As with the CALLH opcode, the handle must have already been allocated, though again it is permitted to pass a handle which has not yet been populated by code. The back-end code generator must support both cases, though it will generally output less efficient code if the handle is not yet populated (since it must fetch the address at runtime from the handle). The parameter is stored in a special internal register called EXP and can be retrieved via the GETEXP opcode.
Like most control flow opcodes, EXH can be used either unconditionally or flagged with a condition that controls whether or not the exception is generated.
EXIT
Usage:
EXIT parameter[,condition]
Parameters:
- parameter — a 32-bit integer register, memory location, map variable, or immediate
- condition — an optional condition which is used to determine whether or not to exit
Flags:
- C — undefined
- V — undefined
- Z — undefined
- S — undefined
- U — undefined
Description: The EXIT opcode immediately exits from the generated code and returns control back to the back-end, which ultimately returns control to the dynamic recompiler. The exit can be performed even from within a subroutine or exception handler. The parameter is surfaced as the return value of the execute function.
Like most control flow opcodes, EXIT can be used either unconditionally or flagged with a condition that controls whether or not the exit occurs.
HANDLE
Usage:
HANDLE handle
Parameters:
- handle — a memory pointer to previously-allocated handle
Flags:
- C — maintained
- V — maintained
- Z — maintained
- S — maintained
- U — maintained
Description: The HANDLE opcode connects the current code position to the specified handle. The handle must have been previously explicitly allocated. By definition only one piece of code can connect itself to a handle; attempts to attach a new piece of code to an existing handle are considered errors and will assert in debug builds.
HASH
Usage:
HASH mode, pc
Parameters:
- mode — a 32-bit immediate value
- pc — a 32-bit immediate value
Flags:
- C — maintained
- V — maintained
- Z — maintained
- S — maintained
- U — maintained
Description: The HASH opcode connects the current code position to the back-end's hash table. The back-end is free to implement whatever code lookup mechanism it desires, though a standard one is provided by the back-end utilities module. The available number of modes is specified at dynamic recompiler initialization time; it is an error to specify mode value beyond the number of modes requested at that time.
Note that unlike a handle, a hash for a given mode/pc combination can be replaced at any time.
HASHJMP
Usage:
HASHJMP mode,pc,handle
Parameters:
- mode — a 32-bit integer register, memory location, map variable, or immediate
- pc — a 32-bit integer register, memory location, map variable, or immediate
- handle — memory pointer to allocated handle
Flags:
- C — undefined
- V — undefined
- Z — undefined
- S — undefined
- U — undefined
Description: The HASHJMP opcode transfers control to a block of code that has previously been connected to the provided mode/pc pair. If no code has been registered, an exception is generated by setting the exception parameter EXP to pc and calling the given handle. The expected response to this is to return to the dynamic recompiler and request that it generate new code for the provided mode/pc pair.
JMP
Usage:
JMP label[,cond]
Parameters:
- label — - a 32-bit immediate value
- condition — an optional condition which is used to determine whether or not to jump
Flags:
- C — maintained
- V — maintained
- Z — maintained
- S — maintained
- U — maintained
Description: The JMP opcode transfers control to another location within the current block. The label parameter specifies a 32-bit integer label that serves as the jump target. Within the block, a LABEL opcode must be present to signify what code the label refers to. In debug builds, attempts to jump to a non-existent label will assert at back-end code generation time (when all the labels are resolved).
Like most control flow opcodes, JMP can be used either unconditionally or flagged with a condition that controls whether or not the jump occurs.
LABEL
Usage:
LABEL label
Parameters:
- label — 32-bit immediate value
Flags:
- C — maintained
- V — maintained
- Z — maintained
- S — maintained
- U — maintained
Description: The LABEL opcode connects the current code position to a block-local label with the value of label. Only one label per block of UML can claim the same label value, so the dynamic recompiler must set up some conventions to ensure that each label has a unique 32-bit identifier.
MAPVAR
Usage:
MAPVAR mapvar,value
Parameters:
- mapvar — a map variable
- value — a 32-bit immediate value
Flags:
- C — maintained
- V — maintained
- Z — maintained
- S — maintained
- U — maintained
Description: The MAPVAR opcode sets the specified map variable mapvar to a new value value starting at the current position within the code. Map variables are encoded into the instruction stream and can be retrieved from within a subroutine or exception handler via the RECOVER opcode. At the start of a block, all map variables default to 0, and hold that value until a MAPVAR opcode overrides it, at which point all subsequent code will take on the new value.
Note that because the RECOVER opcode always operates on the outermost return address, it does not make sense to use MAPVAR within a subroutine.
RECOVER
Usage:
RECOVER dest,mapvar
Parameters:
- dest — a 32-bit integer register or memory location
- mapvar — a map variable
Flags:
- C — undefined
- V — undefined
- Z — undefined
- S — undefined
- U — undefined
Description: The RECOVER opcode retrieves the value of the given mapvar and stores it in dest. It does this by fetching the outermost return address from the stack and using that value to find the value specified by the most recent MAPVAR opcode that preceded the point where the subroutine call or exception generation happened. Because of this behavior, it only makes sense to use RECOVER from within a subroutine or exception handler; using it outside of this context will produce undefined results.
RET
Usage:
RET [cond]
Parameters:
- condition — an optional condition which is used to determine whether or not to return
Flags:
- C — undefined
- V — undefined
- Z — undefined
- S — undefined
- U — undefined
Description: Returns control from a subroutine call or exception handler to the instruction following the CALLH or EXH opcode.
Like most control flow opcodes, RET can be used either unconditionally or flagged with a condition that controls whether or not the return occurs.
Internal Register Opcodes
SETFMOD
Usage:
SETFMOD mode
Parameters:
- mode —
Flags:
- C — undefined
- V — undefined
- Z — undefined
- S — undefined
- U — undefined
Description:
GETFMOD
Usage:
GETFMOD dest
Parameters:
- dest —
Flags:
- C — undefined
- V — undefined
- Z — undefined
- S — undefined
- U — undefined
Description:
GETEXP
Usage:
GETEXP dest
Parameters:
- dest —
Flags:
- C — undefined
- V — undefined
- Z — undefined
- S — undefined
- U — undefined
Description:
SAVE
Usage:
SAVE dest
Parameters:
- dest —
Flags:
- C — undefined
- V — undefined
- Z — undefined
- S — undefined
- U — undefined
Description:
RESTORE
Usage:
RESTORE source
Parameters:
- source —
Flags:
- C — set to the value provided in source
- V — set to the value provided in source
- Z — set to the value provided in source
- S — set to the value provided in source
- U — set to the value provided in source
Description:
Integer Operations
LOAD
Usage (32-bit):
LOAD1U dest,base,index LOAD1S dest,base,index LOAD2U dest,base,index LOAD2S dest,base,index LOAD4 dest,base,index
Usage (64-bit):
DLOAD1U dest,base,index DLOAD1S dest,base,index DLOAD2U dest,base,index DLOAD2S dest,base,index DLOAD4U dest,base,index DLOAD4S dest,base,index DLOAD8 dest,base,index
Parameters:
- dest —
- base —
- index —
Flags:
- C — undefined
- V — undefined
- Z — undefined
- S — undefined
- U — undefined
Description:
STORE
Usage (32-bit):
STORE1 base,index,source STORE2 base,index,source STORE4 base,index,source
Usage (64-bit):
DSTORE1 base,index,source DSTORE2 base,index,source DSTORE4 base,index,source DSTORE8 base,index,source
Parameters:
- base —
- index —
- source —
Flags:
- C — undefined
- V — undefined
- Z — undefined
- S — undefined
- U — undefined
Description:
READ
Usage (32-bit):
READ1U dest,space,address READ1S dest,space,address READ2U dest,space,address READ2S dest,space,address READ2M dest,space,address,mask READ4 dest,space,address READ4M dest,space,address,mask
Usage (32-bit):
DREAD1U dest,space,address DREAD1S dest,space,address DREAD2U dest,space,address DREAD2S dest,space,address DREAD2M dest,space,address,mask DREAD4U dest,space,address DREAD4S dest,space,address DREAD4M dest,space,address,mask DREAD8 dest,space,address DREAD8M dest,space,address,mask
Parameters:
- dest —
- space —
- address —
- mask —
Flags:
- C — undefined
- V — undefined
- Z — undefined
- S — undefined
- U — undefined
Description:
WRITE
Usage (32-bit):
WRITE1 space,address,source WRITE2 space,address,source WRIT2M space,address,mask,source WRITE4 space,address,source WRIT4M space,address,mask,source
Usage (64-bit):
DWRITE1 space,address,source DWRITE2 space,address,source DWRIT2M space,address,mask,source DWRITE4 space,address,source DWRIT4M space,address,mask,source DWRITE8 space,address,source DWRIT8M space,address,mask,source
Parameters:
- param0 —
- param1 —
Flags:
- C — undefined
- V — undefined
- Z — undefined
- S — undefined
- U — undefined
Description:
Template
Usage:
OPCODE param0[,param1]
Parameters:
- param0 —
- param1 —
Flags:
- C — undefined
- V — undefined
- Z — undefined
- S — undefined
- U — undefined
Description:
