View Full Document


Unformatted text preview:

Register Alloca on Deconstructed David Ryan Koes Seth Copen Goldstein 12th Interna onal Workshop on So3ware and Compilers for Embedded Systems April 24 2009 Register Alloca9on Problem v 1 w v 3 x w v u v t u x print x print w print t print u eax ebx ecx edx esi edi esp ebp 2 Register Alloca9on Graph coloring Linear scan Op9mal frameworks Move elimina9on allocators Spill Code Op9miza9on spill to memory to meet register availability Move Inser9on insert moves to make assignment easy or leave in SSA form 3 Assignment assign variables to registers aLempt to maximize move coalescing Ques9ons What is the penalty of decomposing register alloca9on into individual components What is the individual impact of each component on code quality How far from op9mal are exis9ng heuris9cs Our goal is to answer these ques ons An op9mal register alloca9on framework is used to empirically evaluate the importance of the components of register alloca9on the impact of component integra9on and the e ec9veness of exis9ng heuris9cs 4 Outline Mo9va9on Register Alloca9on Components Move Inser9on Coalescing Spilling Assignment Methodology Results Conclusion 5 Move Inser9on Addi9onal move instruc9ons can simplify assignment problem Can eliminate need to spill Only indirect impact on code quality L1 write read write read write read branch b a c b a c L1 a a b Live c a b RA c a 6 move r0 r1 Move Inser9on Evalua9on full move instruc9ons may be inserted at any program point limited move instruc9ons may be inserted only at the entry and exit of basic blocks none no register to register move instruc9ons are generated by the allocator 7 Coalescing Eliminate move instruc9ons by assigning each operand to the same loca9on Can be performed as separate pass lose ability to coalesce with physical registers lose ability to coalesce uncoalescables Pre alloc Coalescing t1 t1 t2 t1 t2 Physical Reg t3 t3 t3 t3 t3 t3 r0 8 Uncoalescable t1 t2 t1 t1 t2 t1 Coalescing Evalua9on integrated op mal move coalescing is

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...

Join to view Register Allocation Deconstructed and access 3M+ class-specific study document.

We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Register Allocation Deconstructed and access 3M+ class-specific study document.


By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?