1 School of Computer Science Register Allocation 15-745 Optimizing Compilers Spring 2008 School of Computer Science School of Computer Science Back end structure IR TempMap instruction selector register allocator Assem Assem instruction scheduler School of Computer Science After Instruction Selection entry: 0x803ce0, LLVM BB @0x801a90, ID#0:!! %reg1024 = MOV32ri 33!! %reg1025 = ADD32rm %reg1024, <fi#-2>, 1, %NOREG, 0!! %reg1026 = MOV32rm <fi#-1>, 1, %NOREG, 0!! %reg1027 = IMUL32rr %reg1026, %reg1026!! %reg1028 = IMUL32rri8 %reg1027, 37!! %EAX = MOV32rr %reg1028!! %EAX = CDQ %EDX<imp-def>, %EAX<imp-use>!! IDIV32r %reg1025, %EAX<imp-def>, %EDX<imp-def>, %EAX<imp-use>, %EDX<imp-use>!! %reg1029 = MOV32rr %EAX!! %reg1030 = NOT32r %reg1026!! %reg1031 = ADD32rr %reg1029, %reg1030!! %EAX = MOV32rr %reg1031!! RET!define i32 @erk(i32 %a, i32 %b) {!entry:!! %tmp3 = mul i32 %a, 37!! ; <i32> [#uses=1]!! %tmp4 = mul i32 %tmp3, %a!! ; <i32> [#uses=1]!! %tmp6 = add i32 %b, 33!! ; <i32> [#uses=1]!! %tmp7 = sdiv i32 %tmp4, %tmp6!! ; <i32> [#uses=1]!! %tmp9.neg = xor i32 %a, -1!! ; <i32> [#uses=1]!! %tmp10 = add i32 %tmp7, %tmp9.neg!! ; <i32> [#uses=1]!! ret i32 %tmp10!}!2 School of Computer Science Abstract View … 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, %eax cltd idivl 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 purposes Read Written School of Computer Science Register allocator’s job The register allocator’s job is to assign each temp to a machine register. If that fails, the register allocator must rewrite the code so that it can succeed. … t7 : %ebx t8 : %ecx t10 : %eax t11 : %eax t17 : %esi … The TempMap …!t7 <- 2!t11 <- t7!t11 <- (t7, t11)!t10 <- t11!t10 <- t10!t8 <- t10!t17 <- t7!t17 <- t17!%eax <- !%edx <- (%eax,%edx)!%eax,%edx <- t17!…!School of Computer Science Some terminology Two temps interfere if at some point in the program they cannot both occupy the same register. v <- 1 w <- v + 3 x <- w + v u <- v t <- u + x <- w <- t <- u Which temps interfere? School of Computer Science A graph-coloring problem v x w u t v <- 1 w <- v + 3 x <- w + v u <- v t <- u + x <- w <- t <- u Interference graph: an undirected graph where •!nodes = temps •!there is an edge between two nodes if their corresponding temps interfere3 School of Computer Science A graph-coloring problem v x w u t v <- 1 w <- v + 3 x <- w + v u <- v t <- u + x <- w <- t <- u A graph is k-colorable if every node in the graph can be colored with one of k colors such that two adjacent nodes do not have the same color Assigning k registers = Coloring with k colors eax edx ecx School of Computer Science History For early architectures, register allocation was not very important Early work by Cocke (in 1971) proposed the idea that register allocation can be viewed as a graph coloring problem Chaitin was the first to implement this idea for the IBM 370 PL/1 compiler, in 1981 In 1982, at IBM, Chaitin’s allocator was used for the PL.8 compiler for the IBM 801 RISC system Today, register allocation is the most essential of code optimizations School of Computer Science History, cont’d Motivated by the first MIPS architecture, Chow and Hennessy developed priority-based graph coloring in 1984 Another popular algorithm for register allocation based on graph coloring is due to Briggs in 1992 “top down” coloring “bottom up” coloring School of Computer Science Steps in register allocation Build Color Spill4 School of Computer Science Building the interference graph Given liveness information, we can build the interference graph (IG) v <- 1 w <- v + 3 x <- w + v u <- v t <- 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} v x w u t How? School of Computer Science Edges of Interference Graph Intuitively: 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 point An optimized definition & algorithm for edges: "" For each defining inst i Let x be definition at inst i For each variable y live at end of inst i insert an edge between x and y Faster? Better quality? A = 2 (A2) {D} {A,D} Edge between A and D School of Computer Science Building the interference graph for 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 y!v x w u t v <- 1 w <- v + 3 x <- w + v u <- v t <- 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} School of Computer Science A Better Interference Graph x = 0;!for(i = 0; i < 10; i++)!{! x += i;!}!y = global;!y *= x;!for(i = 0; i < 10; i++)!{! y += i;!}!What does the interference graph look like? What’s the minimum number of registers needed?5 School of Computer Science Live Ranges & Merged Live Ranges A live range consists of a definition and all the points in a program (e.g. end of an instruction) in which that definition is live. –!How to compute a live range? Two overlapping live ranges for the same variable must be merged a = … a = … … = a School of Computer Science Example A = ... (A1) IF A goto L1 L1: C = ... (C1) = A D = ... (D1) B = ... (B1) = A D = B (D2) A = 2 (A2) = A ret D {} {} {A} {A1} {A} {A1} {A} {A1} {A,B} {A1,B1} {B} {A1,B1} {D} {A1,B1,D2} Live Variables Reaching 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} Merge A live range consists of a definition and all the points in a program in which that definition is live. School of Computer Science Merging Live Ranges Merging 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 one equivalence class Merged live ranges are also known as “webs” School of Computer Science Example: Merged Live Ranges A = ...
View Full Document
Unlocking...