The Virtual Register Allocator

This portion will go over the virtual register allocator in SquirrelFish. Many intermediate languages use a virtual register instead of a physical hardware register since executing a register based instruction set is faster than a stack based machine. Much of this improvement comes from not having to execute stack manipulation instructions, thus reducing bytecode dispatch. If you want an in-depth analysis, checkout Virtual Machine Showdown: Stack versus Registers.

SquirrelFish parses actual JavaScript source, and creates a register based bytecode representation. SquirrelFish parse tree nodes ask for a new register for any value that needs one during the emitNode() method. Registers are freed when a new temporary register is generated. If a register is no longer referenced by anything else, it is freed. I'm pretty surprised at how little code the register allocator is with only two methods:

ByteCodeGenerator.cpp
RegisterID* BytecodeGenerator::newRegister()
{
m_calleeRegisters.append(m_calleeRegisters.size());
m_codeBlock->m_numCalleeRegisters = max<int>(m_codeBlock->m_numCalleeRegisters, m_calleeRegisters.size());
return &m_calleeRegisters.last();
}

RegisterID* BytecodeGenerator::newTemporary()
{
// Reclaim free register IDs.
while (m_calleeRegisters.size() && !m_calleeRegisters.last().refCount())
m_calleeRegisters.removeLast();

RegisterID* result = newRegister();
result->setTemporary();
return result;
}

Another thing I found out. If we go back to the hello world example from the previous post, 14 callee registers were allocated. However, the debug output only showed 5 registers were used. The difference is that upon making a function call, 8 registers are allocated for call frame variables. One additional register is used for the function call's argument, bringing the grand total up to 14 registers.