SPARC Subroutine Register Allocation

In a typical machine, if a subroutine is called the program needs to save the state of the machine at the time of the subroutine call. In particular, a number of registers need to be saved. These include the stack pointer, frame pointer, program counter and a number of general use registers.

On the MIPS machine, the processor depends upon the program to save the registers that are in use by the subroutine. Therefore, when a subroutine is called, the program must adjusts the stack pointer to make space for the registers that must be saved and then it pushes the registers to save onto the stack.

Typically, the MIPS program will push the global pointer ($gp), the return address ($ra), and the saved registers ($s0-$s7) onto the stack when entering a subroutine. Then when the subroutine is complete, the registers that were saved should be restored ("popped" from the stack) and the subroutine will jump to the return address.

The MIPS machine assumes that the subroutine arguments will be in the argument registers ($a0-$a3) and the return values will be in the return value registers ($v0-$v1). Therefore, the program must ensure that the arguments are in the correct registers when the subroutine is called and that the return values are in the correct registers when the subroutine is complete.

Since the MIPS machine must relie on the program to handle the register saving and restoring, the MIPS machine spends a number of clock cycles saving the machine state before the subroutine is called and a number of machine cycles to restore the state once the subroutine is complete.

Since the saving and restoring of registers can take a significant amount of clock cycles, SUN created a large number registers for their SPARC machine of which a particular subroutine can only see thrity-two registers. These registers consist of the normal in (%i0-%i7), out (%o0-%07), local (%l0-%l7), and global (%g0-%g7) registers. By creating the "register file", the SPARC machine can save the machine state without requiring the program to push the register states to the stack. The SPARC machince does this by creating a "window" over the registers in such a way that the previous subroutine registers and the new allocated registers overlap slightly.

In essence, when a subroutine is called, the SPARC processor renames the out registers (%o0-%o7) before the subroutine as the input registers (%i0-%i7) inside the subroutine and it creates new local (%l0-%l7) and output registers (%o0-%o7) for the subroutine. These new output registers could then become input registers in for a subroutine call inside this subroutine.

Graphically, the process looks like:

In this manner, the SPARC machine can guarantee a quick subroutine call if the subroutine has less than 8 arguments (%i0-%i7), and the register file is not "full". If the subroutine has too many arguments, the SPARC machine must rely on the program to save the machine state on the stack like the MIPS machine. If the machine cannot allocate anymore registers from the register file, the SPARC machine will save the earliest subroutine call to the stack which will free the needed thirty-two registers. Then the SPARC machine will allocate the free registers to the new subroutine.

The SPARC machine can tell when the register file is full by using two additional machine registers, the "Current Window Pointer" and the "Window Invalid Bit", designated CWP and WIM. The CWP points to the current register set and the WIM points to the last available register set. Once the CWP points to the same WIM and an additional subroutine is called, a hardware trap occurs causing the SPARC machine to save the oldest window set to the stack and allocating the free registers to the new subroutine call. Once the registers are saved to the stack, the WIM is updated to point to the new free registers.

Graphically, the register file overflow looks like:

Paul Austin Charles Gates