Register allocation is a NP-hard problem. See “Register Allocation:What does the NP-completeness Proof of Chaitin et al. Really Prove?” via this thread on RTX2010 – Radiation-hardened stack machine microprocessor
What every programmer should know about memory, Part 1 [LWN.net] by Ulrich Drepper; September 2007. 9 part series.