The MAXLIVE Problem (solved in 2005/2006)

• Register Allocation was the killer problem:

• 1-bit operations increase DAG complexity

• Trinary ops increase DAG complexity

• Basic blocks often needed 1000s of registers

• Needed to dramatically reduce MAXLIVE

• Developed two new techniques: GA & SUN-GA