1School of Computer ScienceRegister Allocation15-745 Optimizing CompilersSpring 2007School of Computer SciencePeas tell me allPeas tell me allabout registerabout registerallocation!allocation!School of Computer ScienceBack end structureIRTempMapinstructionselectorregisterallocatorAssemAsseminstructionschedulerSchool of Computer Science.text.align 4.globl _main_main:enterpushl %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 %edileaveretstandardpreludestandardpostluderesult valuein %eaxAfter Instruction Selection2School of Computer Science.text.align 4.globl _main_main:pushl %ebpmovl %esp, %ebpmovl %edi, t2movl %ebx, t3movl %esi, t4movl $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, %eaxmovl t4, %esimovl t3, %ebxmovl t2, %edimovl %ebp, %esppopl %ebpretbetterpreludebetterpostluderesult valuein %eaxAfter Instruction SelectionSchool of Computer ScienceAbstract View…movl $2, t7movl t7, t11imull t7, t11movl t11, t10imull $37, t10movl t10, t8movl t7, t17addl $1, t17movl $33, %eaxcltdidivl t17……t7 <- ()t11 <- (t7)t11 <- (t7, t11)t10 <- (t11)t10 <- (t10)t8 <- (t10)t17 <- (t7)t17 <- (t17)%eax <- ()%edx,%eax <- (%eax)%eax,%edx <- (t17,%eax,%edx)…Abstract view, for register allocation purposesReadWritt enSchool of Computer ScienceRegister allocator’s jobThe register allocator’sjob is to assign eachtemp to a machineregister.If that fails, the registerallocator must rewritethe code so that it cansucceed.…t7 : %ebxt8 : %ecxt10 : %eaxt11 : %eaxt17 : %esi…TheTempMap…t7 <- 2t11 <- t7t11 <- (t7, t11)t10 <- t11t10 <- t10t8 <- t10t17 <- t7t17 <- t17%eax <- %edx <- (%eax,%edx)%eax,%edx <- t17…School of Computer ScienceSome terminologyTwo temps interfere if at some point in theprogram they cannot both occupy the sameregister.v <- 1w <- v + 3x <- w + vu <- vt <- u + x <- w <- t <- uWhich temps interfere?3School of Computer ScienceA graph-coloring problemvx wutv <- 1w <- v + 3x <- w + vu <- vt <- u + x <- w <- t <- uInterference graph: an undirected graph where• nodes = temps• there is an edge between two nodes if theircorresponding temps interfereSchool of Computer ScienceA graph-coloring problemvx wutv <- 1w <- v + 3x <- w + vu <- vt <- u + x <- w <- t <- uA graph is k-colorable if every node in the graph canbe colored with one of k colors such that two adjacentnodes do not have the same colorAssigning k registers = Coloring with k colorseaxedxecxSchool of Computer ScienceHistoryFor early architectures, register allocation was not veryimportantEarly work by Cocke (in 1971) proposed the idea thatregister allocation can be viewed as a graph coloringproblemChaitin was the first to implement this idea for the IBM370 PL/1 compiler, in 1981In 1982, at IBM, Chaitin’s allocator was used for thePL.8 compiler for the IBM 801 RISC systemToday, register allocation is the most essential of codeoptimizationsSchool of Computer ScienceHistory, cont’dMotivated by the first MIPS architecture,Chow and Hennessy developed priority-basedgraph coloring in 1984Another popular algorithm for registerallocation based on graph coloring is due toBriggs in 1992“top down” coloring“bottom up” coloring4School of Computer ScienceSteps in register allocationBuildColorSpillSchool of Computer ScienceBuilding the interference graphGiven liveness information, we can build theinterference graph (IG)v <- 1w <- v + 3x <- w + vu <- vt <- u + x <- x <- w <- t <- u{}{v}{w,v}{w,x,v}{w,u,x}{x,w,u,t}{w,u,t}{u,t}{u}vx wutHow?School of Computer ScienceEdges of Interference GraphIntuitively:Two variables interfere if they overlap at some point in the program.Algorithm:At each point in program,enter an edge for every pair of variables at that pointAn optimized definition & algorithm for edges:For each defining inst iLet x be definition at inst iFor each variable y live at end of inst iinsert an edge between x and yFaster?Better quality?A = 2 (A2){D} {A,D}Edge between A and DSchool of Computer ScienceBuilding the interference graphfor each defining inst i let x be temp defined at inst i for all y in LIVE-IN of succ(i) insert an edge between x and yvx wutv <- 1w <- v + 3x <- w + vu <- vt <- u + x <- x <- w <- t <- u{}{v}{w,v}{w,x,v}{w,u,x}{x,w,u,t}{w,u,t}{u,t}{u}5School of Computer ScienceA Better Interference Graphx = 0;for(i = 0; i < 10; i++){ x += i;}y = global;y *= x;for(i = 0; i < 10; i++){ y += i;}What does the interferencegraph look like?What’s the minimumnumber of registersneeded?School of Computer ScienceLive Ranges & Merged Live RangesA live range consists of a definition and allthe points in a program (e.g. end of aninstruction) in which that definition is live.– How to compute a live range?Two overlapping live ranges for the samevariable must be mergeda = … a = …… = aSchool of Computer ScienceExampleA = ... (A1)IF A goto L1L1:C = ... (C1) = AD = ... (D1) B = ... (B1) = AD = B (D2) A = 2 (A2) = Aret D{} {}{A} {A1}{A} {A1}{A} {A1}{A,B} {A1,B1}{B} {A1,B1}{D} {A1,B1,D2}Live VariablesReaching Definitions{A} {A1}{A,C} {A1,C1}{C} {A1,C1}{D} {A1,C1,D1}{D} {A1,B1,C1,D1,D2}{A,D} {A2,B1,C1,D1,D2}{A,D} {A2,B1,C1,D1,D2}{D} {A2,B1,C1,D1,D2}MergeA live range consists of a definition and all thepoints in a program in which that definition is live.School of Computer ScienceMerging Live RangesMerging definitions into equivalence classes:– Start by putting each definition in a different equivalence class– For each point in a program• if variable is live,and there are multiple reaching definitions for the variable• merge the equivalence classes of all such definitions into a oneequivalence classMerged live ranges are also known as “webs”6School of Computer ScienceExample: Merged Live RangesA = ... (A1)IF A goto L1L1:C = ... (C1) = AD = ... (D1) B = ... (B1) = AD = B (D2) A = 2 (A2) = Aret D{}{A1}{A1}{A1}{A1,B1}{B1}{D1,2}{A1}{A1,C1}{C1}{D1,2}{D1,2}{A2,D1,2}{A2,D1,2}{D1,2}A has two “webs”makes register allocation easierSchool
View Full Document
Unlocking...