First a pass is made over the block to count the number of references made to each virtual register. These are then sorted by the number of references in descending order. A count of the total number of virtual registers is kept, and if it is greater than the number of registers available on the target machine two registers are set aside as the feasible set for loading and storing values. Two registers suffice to load the two possible input registers for an operation (each can hold the address and then the value), and two registers are also sufficient for the single output of each instruction (one to hold the address and one to hold the temporary result). If spilling will not be necessary (the number of virtual registers is no greater than the number of physical registers available) there is no need to reserve the feasible set.
With the virtual registers sorted in order of decreasing reference frequency, the first r-f virtual registers (physical registers - the feasible set) are assigned to physical registers based on their rank, the most common is assigned register 0, the next most common register 1, etc. Remaining registers will have to be spilled in and out of the reserved temporary registers as they are used.
A second pass is then made to actually emit the rewritten code, examining one instruction at a time. The frequency of a register read by the instruction is looked up, and if it is common enough to warrant a physical register the physical one is written into the instruction. Otherwise, spill code is emitted to load the value from memory (memory addresses for spilled registers are assigned by the virtual register number, register 0 is stored at address 0, register 1 is stored at address 4, etc.) into a temporary physical register. The instruction is then rewritten to use the temporary physical register. After the read registers are all checked and rewritten, the registers written by the instruction are examined (in this instruction set there is only ever one output written, but this implementation is generalized to support multiple outputs, though this will require increasing the size of the feasible set). If a written register is mapped to a physical register (again, decided strictly by the ordering of the virtual registers by frequency) the physical register replaces the virtual register address. Otherwise, a temporary register is used for the output. Another temporary register is reserved to hold the address to which the output will be written, but there need be only one of these regardless of the number of outputs. After all written registers have been considered the rewritten instruction is emitted. It is followed by spill code to store to memory any output values which have been stored in temporary registers.