May I also point out some recent work on this by Maarten Faddegon:
“SSA Back-Translation: Faster Results with Edge Splitting and Post Optimization”
Faddegon describes an early paper by Cytron about this, which Briggs points out to be of limited generality. Then later Shreedhar made performance improvements on Briggs method, but his algorithm is rather complicated.
Faddegon introduces a reasonably simple extension to Briggs by placing copy statements at a smarter place, and then uses a few simple existing optimization passes to get rid of redundancy. This leads to no performance loss in the removal of phi-nodes. The method is used commercially in ACE’s LLVM-TURBO back-end technology for LLVM (www.ace.nl).
Faddegon’s methods does not solve your problem of limited register resources. For that you would have to use a traditional register allocator.