blob: de4f6ee2da6696cb5934ba1d52f69789c08f940e (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
+++
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.
|
