Register Allocation15-745 Optimizing CompilersSpring 2006Peter LeeAnnouncementsRead Ch.16 (register allocation)Task 2 due todayTask 3 available next weekread: efficient path profilingCompiler structuresourceprogramtargetprogramfrontendbackendIRBack-end structureIRTempMapinstructionselectorregisterallocatorAssemAsseminstructionschedulerSample instruction selector run.text.align 4.globl l1mainl1main:pushl %ebpmovl %esp, %ebppushl %edipushl %ebxpushl %esimovl $2, t7movl t7, t11imull t7, t11movl t11, t10imull $37, t10movl t10, t8movl t7, t17addl $1, t17movl $33, %eaxcltdidivl t17movl %eax, t15movl t7, t14addl t15, t14movl t8, t13imull t14, t13movl t13, t8movl $78, t20negl t20movl t8, t19subl t20, t19movl t19, %eaxpopl %esipopl %ebxpopl %edimovl %ebp, %esppopl %ebpretstandardpreludestandardpostluderesult valuein %eaxAssem representation… movl $2, t7 movl t7, t11 imull t7, t11 movl t11, t10 imull $37, t10 movl t10, t8 movl t7, t17 addl $1, t17 movl $33, t1 cltd idivl t17……OPER(“movl\t$2, `d0”, [], [t7])MOVE(“movl\t`s0, `d0”, [t7], [t11])OPER(“imull\t`s0, `d0”, [t7], [t11])MOVE(“movl\t`s0, `d0”, [t11], [t10])OPER(“imull\t$37, `d0”, [], [t10])MOVE(“movl\t`s0, `d0”, [t10], [t8])MOVE(“movl\t`s0, `d0”, [t7], [t17])OPER(“addl\t$1, `d0”, [], [t17])OPER(“movl\t$33, `d0”, [], [%eax])OPER(“cltd”, [%eax], [%edx])OPER(“idivl `s0”, [t17], [%eax,%edx])…represented asAssume tempMap: temp -> stringHow do we emit assemblycode?Assem in MLdatatype instr = OPER of {assem : string, dst : temp list, src : temp list} | MOVE of {assem : string, dst : temp list, src : temp list} | DIRECTIVE of {assem : string} | COMMENT of stringAssem in Javaabstract public class Instruction { … }public class OperInstruction extends Instruction { public OperInstruction(String a, List d, List s) { … } …}public class MoveInstruction extends Instruction { public MoveInstruction(List d, List s) { … } …}…Register allocator’s view…OPER(“movl\t$2, `d0”, [], [t7])MOVE(“movl\t`s0, `d0”, [t7], [t11])OPER(“imull\t`s0, `d0”, [t7], [t11])MOVE(“movl\t`s0, `d0”, [t11], [t10])OPER(“imull\t$37, `d0”, [], [t10])MOVE(“movl\t`s0, `d0”, [t10], [t8])MOVE(“movl\t`s0, `d0”, [t7], [t17])OPER(“addl\t$1, `d0”, [], [t17])OPER(“movl\t$33, `d0”, [], [%eax])OPER(“cltd”, [%eax],[%edx])OPER(“idivl `s0”, [t17], [%eax,%edx])……t7 <- !()t11 := t7t11 <- !(t7)t10 := t11t10 <- !()t8 := t10t17 := t7t17 <- !()%eax <- !()%edx <- !(%eax)%eax,%edx <- !(t17)…Register allocator’s viewRegister allocator’s jobAssign each temp to a machine registerIf that fails (due to a shortage of registers), rewrite the code so that it can succeed, and then try again…t7 <- !()t11 := t7t11 <- !(t7)t10 := t11t10 <- !()t8 := t10t17 := t7t17 <- !()%eax <- !()%edx <- !(%eax)%eax,%edx <- !(t17)……t7 : %ebxt8 : %ecxt10 : %eaxt11 : %eaxt17 : %esi…TheTempMapA graph-coloring problemt1 <- !()t2 <- !()t3 <- !(t1,t2)t4 <- !(t1,t3)t5 <- !(t1,t2)t6 <- !(t4,t5)Assume 3 machine registers, {r1,r2,r3}.Assume t4 may not be in r1.Then we have the interference grapht3 t1t2 t4t5r3r1r2t6A small example:A graph-coloring problemt1 <- !()t2 <- !()t3 <- !(t1,t2)t4 <- !(t1,t3)t5 <- !(t1,t2)t6 <- !(t4,t5)Assume 3 machine registers, {r1,r2,r3}.Assume t4 may not be in r1.Then we have the interference grapht3t1t2 t4t5r3r1r2t6r1 <- !()r2 <- !()r3 <- !(r1,r2)r3 <- !(r1,r3)r1 <- !(r1,r2)r2 <- !(r3,r1)Steps in register allocationDetermine what temps are candidates for register allocationConstruct the interference graphAllocate registers by coloring the graph with K colors (where K is the number of assignable registers), so that no adjacent nodes have the same colorAssign each temp to the register corresponding to its colorHistoryFor early architectures, register allocation was a theoretical curiosity with negligible practical importanceCocke in 1971 proposed register allocation as a graph-coloring problemChaitin was the first to implement this idea, for the IBM 370 PL/1 compiler, in 1981In 1982, Chaitin’s allocator was used for the landmark PL.8 compiler for the IBM 801 RISC systemHistory, cont’dThe RISC revolution inspired many people to think about register allocationMotivated by the MIPS architecture, Chow and Hennessy developed priority-based coloring in 1984Today, one of the most popular algorithms is due to Briggs, in 1992“…since I was a mathematician, the register allocation keptgetting simpler and faster as I understood better what wasrequired. I preferred to base algorithms on a simple, clean ideathat was intellectually understandable rather than writecomplicated ad hoc computer code…So I regard the success of this approach, which has been the basisfor much future work, as a triumph of the power of a simplemathematical idea over ad hoc hacking. Yes, the real world ismessy and complicated, but one should try to base algorithms onclean, comprehensible mathematical ideas and only complicatethem when absolutely necessary. In fact, certain instructionswere omitted from the 801 architecture because they would haveunduly complicated register allocation…”- G. Chaitin, 2004Today, register allocation is arguably the single most important optimizationmemory accesses are expensiveeven with caches and on CISC machineswhen it doesn’t work well, the performance impact is noticeableLive rangeA live range for a temp t is a node containing a def of t plus all other nodes for which that def is livet1 <- !()t2 <- !()t3 <- !(t1,t2)t4 <- !(t1,t3)t5 <- !(t1,t2)t6 <- !(t4,t5)t1 t2 t3 t4 t5 t6overlapping liveranges indicateinterfering valuesLive-in sets and the IG{}{}{t1}{t1,t2}{t1,t2,t3}{t1,t2,t4}{t4,t5}{t6}t3t1t2 t4t5r3r1r2t6t1 <- !()t2 <- !()t3 <- !(t1,t2)t4 <- !(t1,t3)t5 <- !(t1,t2)t6 <- !(t4,t5)t1 t2 t3 t4 t5 t6overlapping liveranges indicateinterfering valuesMaking the IGLiveness analysis provides the basic information needed to build the interference graphThe graph nodes represent the temps plus all of the machine registerseach machine register interferes with all other machine registersSubtlety #1: MOVE instructionsDuring graph construction, MOVE instructions should be treated speciallyt := s …x <- !(…s…) …y <- !(…t…)Note that s and t don’treally
View Full Document
Unlocking...