These notes are from the Week 9 of the Compilers course by Stanford.
When we generate intermediate code, we are not concerned about how many registers the target machine has. Therefore, the last phase should allocate variables in registers and also have a backup plan when more variables need to be allocated at any given time.
It is worth noting that variables that are not alive at the same time can be assigned to the same register. This problem can be represented as a graph, where nodes are variables and edges exist between two variables if they are alive at the same time. This problem can be reduced to the graph coloring problem, but as it is NP-hard, this can be solved by using heuristics. If the coloring of the graph is succeeded, they are variables are assigned to register.
If the register allocation failed, one technique called spilling can be used. Spilling consists of storing one or more values in memory and use a temporary variable only between the load and the store operation. By doing that, the interference graph is reduced and a new try of the previous register allocation algorithm can be performed. It is not uncommon that many variables should be spilled to memory.
A machine has a memory hierarchy and the cost to access it is close to:
- Registers: 1 cycle
- Cache: 3 cycles
- Main memory: 20-100 cycles
- Disk: 0.5-5M cycles
Compilers are very good to manage registers but that’s not true for managing caches. One optimization that compilers can do is to change the ordering of inner and outer loops, but it is generally left to the programmer to make good use of the cache.
Automatic Memory Management
Managing memory automatically tries to avoid introducing memory management bugs, which are very hard to find. One way to solve this through garbage collection, which tries to reclaim space occupied by unused objects. There are some known algorithms to implement a garbage collector.
Mark and Sweep is a GC algorithm that works in two phases. In the first phase, called Mark, it traces all reachable objects and tags an extra bit in those objects. In the second phase, called Sweep, it runs through all objects and collects the unmarked ones. It’s worth noting that one extra bit is necessary for this algorithm to work. This algorithm can fragment the memory because the mark phase will store the memory ranges that need to be freed.
Stop and Copy is another GC algorithm that works with two regions of memory, called both new and old space that are almost two halves from the available memory. The old space is where the objects are allocated, and from time to time the algorithm moves all reachable objects to the new space and leaves the garbage behind. It is worth noting that the new space and old space roles are swapped during the copy.
Reference Counting is the last GC we are seeing. This technique consists of storing in every object how many references point to it, and when this counter reaches zero, we know that the object can be freed from memory. It has the limitation of not being able to garbage collect circular data structures.