1CS553 Lecture Register Allocation II 2Register Allocation II Announcements– Grades posted on WebCT– unix groups for project 2 have been set up Last time– Register allocation– Global allocation via graph coloring Today– Subversion– More register allocation– Allocation across procedure callsCS553 Lecture Register Allocation II 3Interference Graph AllocatorsChaitinBriggsCS553 Lecture Register Allocation II 4Register Allocation and Procedure Calls Problem– Register values may change across procedure calls– The allocator must be sensitive to this Two approaches– Work within a well-defined calling convention– Use interprocedural allocation (not covering this)CS553 Lecture Register Allocation II 5Calling Conventions Goals– Fast calls (pass arguments in registers, minimal register saving/restoring)– Language-independent– Support debugging, profiling, etc. Complicating Issues– Varargs– Passing/returning aggregates– Exceptions, non-local returns– setjmp()/longjmp()2CS553 Lecture Register Allocation II 6Architecture Review: Caller- and Callee-Saved Registers Partition registers into two categories– Caller-saved– Callee-saved Caller-saved registers– Caller must save/restore these registers when live across call– Callee is free to use them Examplefoo(){rcaller = 4save rcallergoo()restore rcallerrcaller?}goo(){rcaller = 99}goo() is free tomodify rcallercallercalleeCS553 Lecture Register Allocation II 7Architecture Review: Caller- and Callee-Saved Registers Callee-saved registers– Callee must save/restore these registers when it uses them– Caller expects callee to not change them Examplefoo(){rcallee = 4 goo() rcallee?}goo(){save rcalleercallee = 99restore rcallee}goo() promisesnot to modifyrcalleecallercalleeCS553 Lecture Register Allocation II 8Architectures with Callee and Caller Registers SPARC– hardware-saved %i0-%i7, %o0-%o8 Alpha– 7 callee-saved out of 32 registers MIPS– caller-saved: $t0-$t9, $a0-$a3, $v0-$v1– callee-saved: $s0-$s7, $ra PPC– 18 callee-saved– 14 caller-saved StarCore EABI– 4 callee-saved– 28 caller-savedCS553 Lecture Register Allocation II 9Register Allocation and Calling Conventions Insensitive register allocation– Save all live caller-saved registers before call; restore after– Save all used callee-saved registers at procedure entry; restore at return– Suboptimal Sensitive register allocation– Encode calling convention constraints in the IR and interference graph– How?A variable that is not live across calls should go incaller-saved registersA variable that is live across multiple calls shouldgo in callee-saved registersfoo(){ t = … … = t s = … f() g() … = s} Use precolored nodes3CS553 Lecture Register Allocation II 10r1r2s1f3s2s4s3floating pointintegerPrecolored Nodes Add architectural registers to interference graph– Precolored (mutually interfering)– Not simplifiable– Not spillable Express allocation constraints– Integers usually can’t be stored in floating point registers– Some instructions can only store result in certain registers– Caller-saved and callee-saved registers. . .floating pointintegerCS553 Lecture Register Allocation II 11Precolored Nodes and Calling Conventions Callee-saved registers– Treat entry as def of all callee-saved registers– Treat exit as use of them all– Allocator must “spill” callee-saved registers to use them Caller-saved registers– Variables live across call interfere with all caller-saved registersfoo(){ def(r3) use(r3)}Live range of callee-saved registersCS553 Lecture Register Allocation II 12Examplefoo():def(r3)t1 := r3a := ...b := ...... a ...call goo... b ...r3 := t1use(r3)returnr1r3t1 r1, r2 caller-saved r3 callee-savedb ar2CS553 Lecture Register Allocation II 13MiniJava compiler, Tiger pg. 198, Ch 11, Ch 12 Callee-saved registers– MipsFrame.java, calleeSaves = { RA, S0, S1, S2, S3, S4, S5, S6, S7, S8 },– In MipsFrame.java procEntryExit1– at entry, copy calleeSaves into temporaries– at end, copy from temporaries back into calleeSaves– In MipsFrame.java procEntryExit2– at entry, could put a source statement with defs, but is not necessary– at end, already inserting a sink statement that uses all calleeSavesCaller-saved registers– MipsFrame.java, callerSaves = {T0, T1, T2, T3, T4, T5, T6, T7, T8, T9, V0, V1};– Put them all in destlist for the function call, see line 172 in Codegen.javaSpecial registers– Cannot use for register allocation, might want to make FP (which is S8) special– In MipsFrame.java procEntryExit2 put uses of the special registers in sink stmtArgument registers can also be used as caller-saved registers– Codegen.java pushes all arguments onto the stack right now4CS553 Lecture Register Allocation II 14Tradeoffs Callee-saved registers+ Decreases code size: one procedure body may have multiple calls+ Small procedures tend to need fewer registers than large ones; callee-savemakes sense because procedure sizes are shrinking− May increase execution time: For long-lived variables, may save andrestore registers multiple times, once for each procedure, instead of asingle end-to-end save/restore The larger “problem”– We’re making local decisions for policies that require global informationCS553 Lecture Register Allocation II 15Concepts Register allocation and procedure calls Calling conventions– Caller- vs. callee-saved registers– PrecoloringCS553 Lecture Register Allocation II 16Next TimeReading– Make sure to read Ch. 11 in the Tiger book and the Briggs paperProject– Should be able to generate the interference graph by MondayLecture– Register Allocation