Comment by ndesaulniers

This is a great high level overview of some the techniques and problems encountered with developing a register allocator!

LLVM 's FastRegAlloc also uses linear scan.