Virtual Registers

Introduction

Compilers often use named slots to represent locations where a value will be stored. These named slots are virtual in the sense that they may be mapped in the end to a CPU register or a function's stack frame. In our compiler we use the term Register to denote such a virtual slot.

Instructions can define a Register, or use one or more Registers.

Design Considerations

There are several requirements we need to meet when deciding how to represent these virtual registers.

Each Source Variable Declaration Gets New Register

The first requirement is that every variable declared in a function must get a unique slot. In the source language a variable name may be reused in multiple scopes, but from a compiler's perspective, each variable declaration is unique, because each has a unique lifetime and type.

Consider this example:

func foo(x: Int)
{
  if (x == 0)
  {
    var i = 0
  }
  if (x == 1)
  {
    var i = 1
  }
}

The variable i has two defined instances, each has a different lifetime. From a compiler's standpoint, each instance of i must be mapped to a distinct virtual register.

Each Virtual Register Eventually Gets Assigned To A Potentially Shared Physical Slot

The second requirement is that although each virtual register is unique - they may get mapped to the same physical slot eventually. If we are targeting a CPU then this final location may be a CPU register or a memory location in the function's stack frame. In optvm module, we target an abstract virtual machine, a VM that is. This abstract machine supports unlimited number of virtual registers per function. Each such register is a 64-bit slot in the function's stack frame. We call this a frameSlot in the implementation.

So in the above example, after compiling the two virtual registers that represent i may end up pointing to the same frameSlot.

source variable	virtual register ID	frame slot
i	1	0
i	2	0

In SSA Form a Register may be Versioned

Consider this example:

func foo(x: Int)->Int
{
  var y = 0
  if (x == 1)
  {
    y = 5
  }
  return y
}

Since this function has a single declaration of the variable y initially this variable gets a unique virtual Register slot.

But after SSA form this function looks something like this:

func foo(x: Int)->Int
{
  var y = 0
  var y1: Int
  if (x == 1)
  {
    y1 = 5
  }
  var y2 = phi(y,y1)
  return y2
}

We now have the original virtual Register y but also two new versions of this: y1 and y2.

The requirement is that we need to be able to tell that these are all versions of y.

To support this there is specialized type of virtual Register - this is called SSARegister. Here is how this might look for above example:

name	register type	virtual register ID	frame slot	original ID	SSA version
y	Virtual	1	1	NA	NA
y1	SSA	2	-1	1	1
y2	SSA	3	-1	1	2

Observe following:

• The name of the SSA register is a concatenation of the original name with SSA version.
• The SSA register's original ID refers back to the register ID for y.
• Note that frame slot is set to -1 on SSA registers - SSA registers are converted to regular registers when the compiler exits SSA. See below on life cycle of the frame slot.

Life Cycle of the Frame Slot

Stage	Frame Slot
Pre-SSA	Same as Register ID
SSA	-1
Post Reg Allocation	Slot assigned by Register Allocator