Intermediate code uses “unlimited” temporaries. We have more temporaries than there are registers. Key: assign multiple temporaries to each register example Consider: a := c + d e := a + b f := e - 1 notice how a and e are both dead after use, we can then allocate: r1 := r2 + r3 r1 := r1 + r4 r1 := r1 - r1 key: *you can share a register between t_{1} and t_{2} if at any point at most one of t_1 and t_2 are alive. algorithm liveness check go through liveness analysis to see what’s live or not at any particular moment. register inference graph construct an undirected graph where: a node for each temporary an edge between t_1, t_2 if they are live at the same time two temporaries can’t be at the same register if there’s an edge between them. Think of this as a clique problem for every group of live variables from the step above. coloring Notice that the graph above is k colorable iff all variables can fit in k registers as no two adjacent nodes will share the same color as they occur simultaneously. This is naively an NP hard problem. And a coloring also may not exist. observation pick a node t with fewer than k neighbors in the RIG eliminate t and its edges from RIG if the result is k colorable, then so is the original graph since t has fewer than k neighbors, and then coloring it will just allow us to use the remaining color for t algorithm to k_color: remove a node with less than k neighbors; stick it on a stack repeat step 1 until graph is empty while stack is not empty pop assign a color; since at every state here the thing we popped has less than k, we can find a distinct color under k we have a failure case when we are unable to peel the graph until empty in step 2. if so, peel as much as you can, and then… pick a node (following some heuristics, see below) remove it and stick it somewhere else keep going to previous algorithm’s step 2 when we put the node you evicted back in, there’s a chance that you can still color it. if a variable is not colorable, we stick it into the stack. We now make a control flow graph where we load the variable and write to the variable. This allows us to recompute liveness since the liveness is reduced to right before load and uses. also each “live” of f is independent, and so we will have more nodes on the graph, etc. who do we spill? if we have a case where everybody’s edges is above k-1, who do we spill? general goals: “reduce number of loads” spill with the most conflicts spill with few definition and uses avoid spilling in inner loops