+++
title = "Graph-Colouring Allocation"
author = "Yann Herklotz"
tags = []
categories = []
backlinks = ["1c5b"]
forwardlinks = ["1c5d"]
zettelid = "1c5c"
+++

The following are the main phases of graph-colouring:

1.  **Renumber**: discover the live range information in the source
    program.
2.  **Build**: build the inference graph.
3.  **Coalesce**: merge the live ranges of non-interfering variables
    related by copy instructions.
4.  **Spill cost**: compute the spill cost of each variable. This
    assesses the impact of mapping a variable to memory on the speed of
    the final program.
5.  **Simplify**: construct an ordering of the nodes in the inferences
    graph.
6.  **Spill code**: insert spill instructions, i.e. loads and stores to
    commute values between registers and memory.
7.  **Select**: assign a register to each variable.