Important considerations when designing a new virtual ISA

The shape of the ISA significantly shapes the implementation of the LLVM backend. Changes to the properties of the VM, such as how it interacts with the host, may require reengineering large parts of the backend. Getting the cornerstones of the architecture right is foundational to the implementation. All the points I will highlight in this post come back to the same question: what purpose does the VM fulfill, and how much pain can you endure or want to inflict?

For this post, I am making a few assumptions to keep the scope manageable: the VM is single-threaded, memory access is atomic, and exceptions are not yet supported. These topics will be covered in a follow-up post once I have built a prototype.

When building an LLVM backend for a virtual ISA, you have a unique opportunity: unlike hardware ISAs, you are not constrained by silicon limitations, fabrication costs, or power consumption. You can design an ISA that is perfectly tailored to your use case. However, this freedom comes with a cost — every decision you make will influence the complexity of your backend implementation.

VM Boundary

The boundary between the VM and the host is the most foundational decision, as it dictates large parts of the VM design and has significant implications for the LLVM backend.

Memory Access: Transparent vs. Isolated

Transparent memory access means the VM and host share the same virtual memory space. The VM has direct access to the host, and vice versa. Memory pointers can be passed across the boundary freely.

• Advantages: Simple, no address translation needed. The VM can directly access host memory and vice versa. If the call boundary is transparent as well, even complex types with vtables or function pointers could be passed across the VM boundary.
• Disadvantages: Memory model, calling convention and other ISA properties need to fully agree, or subtle differences will result in impossible-to-debug issues. This binds the virtual ISA to exactly one physical ISA.
• Backend impact: Simplifies handling data between host and VM. No serialization is needed on either side, reducing the footprint of VM and emulator.

Isolated memory access means the VM and host have separate memory spaces. An address translation component handles pointer translation, and memory must be explicitly mapped into the VM.

• Advantages: Stronger isolation; the memory model of host and VM can be decoupled (e.g., VM uses big-endian while the host uses little-endian). The same virtual ISA can be used on virtually any physical ISA.
• Disadvantages: Requires address translation layer, explicit memory mapping, and a complex emulator.
• Backend impact: Code for the virtual ISA and physical ISA must be generated as if it were a distributed system.

Call Boundary: Transparent vs. Isolated

Transparent call boundary allows the VM to directly call functions in the host address space (such as malloc).

• Requirements: Memory access must also be transparent for this to work.
• Characteristics: Execution of the VM and external calls happen on the same stack. The VM can trivially pass function pointers to the host for callbacks.
• Backend impact: Simplifies call instruction codegen; direct call instructions can be used.

Isolated call boundary means the VM is running in isolation.

• Characteristics: VM execution may happen in a separate thread and waits for IPC or a timer to start execution. Interaction between host and VM is asynchronous and does not share the same stack. Callbacks into the VM require additional synchronization.
• Backend impact: The code in the VM must be self-contained. Libraries that are needed within the VM and on the host as well need to be compiled for either architecture, and both copies must be placed in memory.

Context Location

Where is the VM context stored?

• Global: Single VM instance, globally accessible. Access must be coordinated in multi-threaded systems.
• Thread-local: Each thread has its own VM context. Setup must either be done upfront after launching each thread, or each call must check if setup is needed. Allocated structures must be manually cleaned up before the thread exits, or there will be memory leaks.
• Local: A new VM is instantiated in each method that calls into the VM. Depending on memory access transparency, this can be very costly in terms of memory and runtime.

Memory Model

The memory model defines how the VM interacts with memory and its properties, which has significant implications for the generated code.

Endianness

There are generally three endianness types: little-endian, big-endian, and middle-endian. But more important is the question of whether the VM and the host share the same endianness. While differing endianness can improve robustness against reverse engineering, matching endianness simplifies the emulator and is necessary for transparent memory access. Choosing the archaic middle-endianness has the disadvantage that extending stores and truncating loads become more complex, for example when only reading or writing the lowest 16 bits from a 64-bit value.

Alignment Requirements

Are there special alignment requirements within the VM? If all instructions are multiples of 16 bits wide, for example, jumps would not need to encode the lowest bit and the jump distance doubles. The same applies to memory access instructions.

Against intuition, this is not dictated by the host architecture as this can be worked around in the ISA. However, if you decide on differing alignment requirements, you need to scrutinize each structure that may cross the VM boundary, even those invisible to the developer like vtables.

Alignment requirements influence the offset of fields within structures as padding is introduced or omitted. You can try this if you know what you are doing, but be prepared to spend a significant amount of time bridging the gap between VM and host memory.

Access Widths

The memory access granularity has multiple subtle implications for all parts of the VM. If the access width is larger than the smallest register width, you will either need to:

• Load, update, store (which breaks atomicity assumptions)
• Raise alignment requirements (which has the caveats explained earlier)

Generally, the simplest approach is to support the same access width as the host ISA. However, the access width also needs to be encoded in the instruction, either increasing instruction size or reducing the available offset bits.

Stack Direction and Type

How does the stack grow, and what is its initial state? For transparent calling, the stack direction and type must match the host ISA. While conventionally there are two directions and two types (so, four combinations in total), feel free to come up with a new one — it is a virtual ISA and does not need to be practical.

• Direction: Descending (grows toward lower addresses) or ascending (grows toward higher addresses).
• Type: If the stack pointer points to the last memory cell holding a value, it is Full. If it points to the first empty cell beyond the stack, it is Empty.
• Backend impact: Affects prologue, epilogue, and function call code generation, as well as stack pointer management.

Register Architecture

The register set is another fundamental aspect that significantly affects code generation.

Register Width

For transparent memory access and calls, registers should be of equal width to the host registers. This allows seamless integration between VM and host code.

• 16-bit: For nostalgia and to make the code unwieldy.
• 32-bit: A middle ground that can be useful for loading immediates.
• Host matching: The simplest option for transparent memory access and calling. Otherwise, register pairs may be used to simulate wider registers.
• Odd bit widths: To inflict pain. It may be difficult to pull off in practice due to the prevalence of 8/16/32/64-bit architectures and missing support.

Number of Registers

Key considerations:

• Match the host?
• Registers need to be encoded in the instruction, possibly multiple times.
• Can all registers be used with every instruction?

Subregisters

Do you need subregister access (e.g., accessing the lower 32 bits of a 64-bit register)?

• Yes: Useful for operating on different data widths without moving to memory. Subregisters will also need to be encoded in the instruction. Can they be used with every instruction?
• No: Simpler backend but may require more memory operations for type conversions.

Special Purpose Registers

Beyond general-purpose registers, consider:

• Link register: For return addresses. Eliminates the need to push/pop return addresses on the stack but uses a dedicated register.
• Frame pointer: For stack frame management. Useful for debugging but adds overhead.
• Flags/condition registers: For conditional execution. Traditional approach but adds dependencies between instructions.
• Vector registers: For SIMD operations. Useful if your VM targets vectorizable workloads.

Instruction Set Design

The instruction set defines the operations your VM can perform. Since this is a virtual ISA, you have more freedom than with hardware ISAs.

RISC vs. CISC

This is a classic trade-off between simplicity and expressiveness.

RISC (Reduced Instruction Set Computer)

• Fewer, simpler instructions
• Fixed instruction width
• Memory access is restricted to load/store instructions
• Advantages: Simpler backend, easier instruction selection, simpler decoding/emulation.
• Disadvantages: More instructions may be needed for complex operations

CISC (Complex Instruction Set Computer)

• Richer instruction set with more complex operations
• Variable instruction width
• Memory-to-memory operations
• Advantages: More expressive, potentially fewer instructions for complex operations
• Disadvantages: More complex backend, more instruction patterns to handle, expensive decoding, and needs compiler optimizations to leverage

For an LLVM backend, RISC-style ISAs are often easier to work with due to their regularity and simpler instruction patterns.

Instruction Width

• Fixed width: Simplifies instruction decoding and selection. Allows for omitting the lower bits in offsets. However, getting everything into a small instruction set can be challenging. Loading immediates into wide registers may take many instructions. Some instructions may thus be a multiple of the width.
• Variable width: More compact code but adds complexity to instruction encoding and decoding.

Immediate Encoding

How are immediate values encoded in instructions? This also depends on the instruction. Extended immediates mostly make sense for dedicated load instructions; simple immediates may be used for arithmetic; shifted immediates for offsets into memory.

• Simple immediates: Direct encoding with limited range.
• Shifted immediates: Immediate value can be shifted (e.g., imm + shift). More flexible but adds complexity.
• Extended immediates: Special instructions for loading large immediates.

Special Operations

Consider what special operations your ISA needs to support efficiently:

• Division and modulo: Often slow on hardware; consider if your VM needs efficient division.
• Extended multiplication: 64-bit × 64-bit → 128-bit results. Useful for arbitrary-precision arithmetic.
• Count leading/trailing zeros: Useful for certain algorithms.
• Bit manipulation: Rotation, population count, etc.

But keep in mind that you will need to find the bits necessary to encode all these instructions and the fortitude to implement them all — bug-free (or at least strongly bug-reduced).

Conditional Execution

How are conditional branches and operations handled?

Key questions to consider:

• Is there a flags register?
• Are there comparison instructions that store a boolean in a register, with conditional instructions only checking true/false?
• Is only a single instruction skipped?
• Are jump tables supported?
• Does the platform offer a select instruction?

Calling Convention

The calling convention defines how functions receive arguments, return values, and manage the stack.

Caller vs. Callee Saved Registers

• Caller-saved: Registers that the caller must preserve across a function call. More registers available for use but requires more saving/restoring.
• Callee-saved: Registers that the callee must preserve. Fewer registers available for use but less saving/restoring in common cases.

Cleanup Responsibility

Who is responsible for cleaning up the stack after a function call? While the caller cleanup is more common and simpler to implement, the callee cleanup could help enable tail call optimizations and throw curve balls at the reverse engineer.

• Caller cleanup: Caller removes arguments from the stack. More flexible for variable argument counts.
• Callee cleanup: Callee removes its own stack frame. Slightly more efficient for fixed argument counts.

Return Address

• Link register: Dedicated register for return addresses. Faster function calls but uses a register.
• On stack: Return address pushed onto the stack. More flexible but adds stack operations.

Frame Pointer

• Use frame pointer: Maintains a pointer to the current stack frame. Useful for debugging and exception handling.
• Omit frame pointer: More registers available but harder to debug.

Guidelines for Virtual ISAs

When designing a virtual ISA, remember:

1. Virtual ISAs are not bound by the constraints of real hardware. You can make design choices that would be impractical for silicon.
2. Threading could be built into the ISA (e.g., lockstepping, fork + join), but for now we are assuming a single-threaded VM.
3. It does not need to be efficient or efficiently emulatable. Focus on simplicity and correctness first.
4. May not be deterministic, especially if the VM interacts with external state.
5. Could allow for external signals for preemption in the future, but for this initial design we are assuming no exceptions.

Conclusion

Designing a virtual ISA for an LLVM backend requires careful consideration of many interrelated factors. The key is to always tie each decision back to your VM’s purpose and accept the trade-offs that come with each choice.

As a bonus for reading this far, here are two ideas you may (or may not) want to try out:

• The semi-full whirlwind stack: You allocate alternately from the top and the bottom of the stack while the stack pointer always points at the boundary. If you allocated from the top, it points to the empty space above. If you allocated from the bottom, it points to the occupied cell. As LLVM requires the local memory for a function to be contiguous, a stack frame would need to be considered an allocation. The pointer to the other side of the stack could be stored within the stack frame, or as the difference in offset to the stack base. Let your imagination run wild.
• When using the callee cleanup with a vararg function, you could deliberately omit popping part of the argument setup, shifting the stack and tormenting not only an analyst but probably mostly yourself.

I take no responsibility for any harm to you, loved ones, reverse engineers, or any other party as direct or indirect result from adhering to or deviating from any of these recommendations, even implied ones.

In this post, I have outlined the foundational decisions for a single-threaded VM with atomic memory access and no exception support. In a follow-up post, I will explore how to add threading, non-atomic memory access, and exception handling to the design.