- Spilling is done when coloring is not possible. It is the case when number of temporaries are more than registers.
- So variable with k or more neighbor is spilled in memory. The whole thing is done like this:
First of all apply graph coloring algorithm’s part when vertices are being stored in stack. Make it as far as it can, if the condition arises that every vertex has k or more neighbors then put one of these in stack and apply graph coloring on the rest. Assign color to each vertex in the rest of the graph. Now pop the vertex and place it in graph in hope that the rest of the graph has used less than k colors, if this is not the case then store the vertex in memory. Now at each use of that variable, it is to be loaded from memory or stored.
For every load and store, different versions of the variables are used. Hence each version gets the very low range for its liveness. In this way spilling reduces this range and also the number of neighbors by dividing one node in many. Now the graph coloring can be applied as before.
- Any choice of spilling variable is correct but some produces better code, some heuristics used to select are:
- select variable having most conflicts most of the edges would be removed;
- used very less, decreases the usage of memory;
- avoid variables of inner loop.
- Example is explained in the video.
- Register Allocation is important as IC can use many registers. In CISC it is very complicated. The Register Allocation discussed here is good for RISC machines.