Pre-colored registers

I am currently having problems with pre-colored registers. Those are virtual registers that must be assigned a fixed color. Well, one can think on them as physical registers that exist before register allocation. The problem is that, without the pre-colored registers, a simple linear scan of the SSA-code would generate optimal coloring. But, because of them, this does not happen. In order to avoid them, I am building a little interference graph. It only includes interferences between physical and virtual registers. This helps not assigning a register p to a virtual v when p and v interfere (p is pre-colored). The spilling algorithm is looking something like:

allocate(Virt op) {
  if(reg_mappping->there_is_free_reg(class(op))) {
    Phys color = reg_mappping->get_free_reg(class(op));
    reg_mappping->allocate_reg(op, color);
  } else {
    if(reg_mappping->there_is_unused_reg(class(op))) {
      Phys pre_col = reg_mappping->unused_reg(class(op));
      reg_mappping->allocate_reg(op, pre_col);
      spill(op);
    } else {
      Virt spill_c =
      reg_mappping->choose_reg_to_spill(class(op));
      Phys color = reg_mappping->get_color(color);
      spill(spill_c);
      reg_mappping->allocate_reg(op, color);
      if(reg_mappping->interfere(op, color)) {
        spill(op);
      }
    }
  }
}

The first if is used if there are free registers to be allocated to op. In this case, nothing very fancy has to be done: the free color is simply assigned to the operand. The else handles the case when spills must happen. In the first test, there are, indeed, free registers, but they will interfere with the operand later, because they are alive as pre-colored registers. So, the operand is spilled. In the other case, there are no free register at all, and a virtual register must be spilled. After a good candidate is found, it is spilled, and its color is now used to allocate the operand. If the operand and the new color interfere, the operand will have to be spilled too.