Also, see "Global Register Allocation at Link Time" by David W. Wall. An amazing paper, but you can't help to notice that it would have been a much, much easier if he didn't insist on producing valid object files that could be linked together into a working program by a "standard" linker; but he does and so has to resort to linker relaxation too.