Local Register Allocation LRA Handong Ye 2008 04 17 17 04 15 08 Copyright 2008 Handong Ye Handong Ye 2008 05 01 1 Motivations of Project 2 Project Learn LRA algorithm and implementation Learn the IR of Code Generation part of open64 CGIR Learn how to read the trace of LRA Learn the register set of x8664 x 04 15 08 Copyright 2008 Handong Ye 2 agenda 04 15 08 Local Register Allocation LRA CGIR introduction Dump LRA trace x8664 register set introduction Homework Project Copyright 2008 Handong Ye 3 agenda Local Register Allocation LRA CGIR introduction Dump LRA trace x8664 register set introduction Homework Project 04 15 08 Copyright 2008 Handong Ye 4 Local Register Allocation Role of Register Allocation Make best use of the available physical registers to improve run time time performance Generate spill code when necessary Obey ABI Application Binary Interface and ISA Instruction Set Architecture regarding register usage Parameter registers Function return registers Callee saved registers Caller saved registers 04 15 08 Save restore at procedure entry exit Save restore around calls Copyright 2008 Handong Ye 5 Local Register Allocation Role of Local Register Allocation applied to local TN Temporary Name in each BB 04 15 08 using registers granted by GRA Global Register Allocation GRA Granted instruction level granularity Global TN Local TN Copyright 2008 Handong Ye 6 Local Register Allocation WHIRL Extended block optimizer CG expand Pre pass scheduling CGIR Local Req Est GRA Control flow opt LRA If conversion loop opt Post pass scheduling Epilog and prolog Software pipelining Loop unrolling Code emission s 04 15 08 Copyright 2008 Handong Ye 7 Local Register Allocation Key Points Create Live Range each maps to a register Bottom Up Allocation Backup Methods if out of registers Linear time complexity source code 04 15 08 be cg lra cxx be cg lra h Copyright 2008 Handong Ye 8 Local Register Allocation Live Range live range be cg lra cxx several properties long live range Open64 64 source code uses this one first def last use exposed use a live range is from first def to last use even if there are multiple definitions enforce one single register to a TN Fewer live ranges to handle short live range from the definition to its last use where it is still live a TN may be assigned to different registers Fewer dependencies more scheduling opportunities up down down 04 15 08 approach of creating live range Copyright 2008 Handong Ye 9 Local Register Allocation Live Range an example LR1 LR2 live range of TN1 and TN5 TN long live range vs short live range TN1 TN2 TN3 TN5 TN1 TN4 TN1 TN4 TN5 TN6 TN1 2 Long live range 04 15 08 LR1 LR2 LR3 TN1 TN2 TN3 TN5 TN1 TN4 TN1 TN4 TN5 TN6 TN1 2 short live range Copyright 2008 Handong Ye 10 Local Register Allocation Bottom Up Allocation Set of registers available in each class for the BB updated on the fly 1 A backward pass scanning from last instruction to first instruction 2 In each instruction process the result TN before the operand TNs 3 First encounter of each local TN must be last use of the TN for its live range 4 Assign register to TN by picking register round robin from available set Use as many registers as possible contrary to GRA good for scheduling 5 For local TN appearing as first definition of its live range free its register by adding register back to available set 6 Same register can be allocated to result and operand in same instruction If a register move instruction instruction can be deleted 04 15 08 Copyright 2008 Handong Ye 11 Local Register Allocation Bottom Up Allocation Example LR1 LR2 04 15 08 Bottom Up ISA has 6 registers Need to allocate for TN1 and TN5 TN1 r1 r2 TN5 TN1 r3 Allocate LR1 TN1 r3 TN5 r4 TN1 2 r5 r1 r2 TN5 r5 r3 Allocate LR2 r5 r3 TN5 r4 r5 2 Copyright 2008 Handong Ye r5 r1 r2 r6 r5 r3 r5 r3 r6 r4 r5 2 12 12 Local Register Allocation Bottom Up Allocation LR1 LR2 04 15 08 Using long live range Assuming totally 5 registers Only need to allocate for TN1 TN and TN5 TN1 r1 r2 TN5 TN1 r3 Allocate LR1 TN1 r3 TN5 r4 TN1 2 r5 r1 r2 TN5 r5 r3 Allocate LR2 r5 r3 TN5 r4 r5 2 Copyright 2008 Handong Ye r5 r1 r2 r5 r3 r5 r3 r4 r5 2 13 Local Register Allocation Bottom Up Allocation Using short live range Assuming totally 5 registers Only allocate for TN1 and TN5 r5 r1 r2 r5 r5 r3 r5 r3 r5 r4 r5 2 LR1 LR1 LR2 LR3 TN1 r1 r2 TN5 TN1 r3 TN1 r3 TN5 r4 TN1 2 04 15 08 Alloc LR3 TN1 r1 r2 r 1 r3 TN5 TN1 r5 r3 TN5 TN r4 r5 2 Alloc LR2 Copyright 2008 Handong Ye TN1 r1 r2 r5 TN1 r3 r5 r3 r5 r4 r5 2 14 Local Register Allocation Bottom Up Allocation Linear time it s cheap and can repeated if necessary Short live range seems better than long live range Why open64 doesn t split long live range into short one 1 it is rare to run out of registers in LRA not true for x86 x 2 a pre schedule schedule pass to estimate register pressure for LRA so GRA can reserve enough registers for LRA 04 15 08 Copyright 2008 Handong Ye 15 Local Register Allocation Back Up Method if out of registers 04 15 08 re do do scheduling to ease the overlapping of live ranges spill a register allocated by GRA spill a local TN over its live range Copyright 2008 Handong Ye 16 Local Register Allocation Back Up Method if out of registers re do scheduling to ease the overlapping of live ranges LR1 LR2 04 15 08 example totally 5 registers available TN1 r1 r2 TN5 TN1 r3 Allocate LR1 r3 r3 TN5 r4 TN1 2 r5 r1 r2 TN5 r5 r3 Allocate LR2 r3 r3 TN5 r4 r5 2 Copyright 2008 Handong Ye r5 r1 r2 r5 r3 r3 r3 r4 r5 2 17 Local Register Allocation Back Up Method if out of registers re do scheduling to ease the overlapping of live ranges example totally 5 registers available TN1 r1 r2 TN5 TN1 r3 r3 r3 TN5 r4 TN1 2 LR1 LR2 re sched LR1 LR2 TN1 r1 r2 r4 TN1 2 Allocate LR2 TN5 TN1 r3 r3 r3 TN5 04 15 08 TN1 r1 r r2 r4 TN1 TN 2 Allocate LR1 r5 TN1 TN r3 r3 r3 r r5 Copyright 2008 Handong Ye r5 r1 r2 r4 r5 2 r5 r5 r3 r3 r3 r5 18 Local Register Allocation Back Up Method if out of registers 5 reg totally spill a register r1 allocated by GRA LR1 LR2 r1 should not be used in LR2 LR TN1 r1 r2 TN5 TN1 r3 r3 r3 TN5 r4 TN1 2 Allocate LR1 r5 r1 r r2 TN5 r5 r3 r3 r3 r TN5 r4 r5 2 spill r1 r5 r1 r2 push …