TC-8 Goals

Things to learn during this stage that you should remember:

Graph handling, using the Boost Graph Library

We use the Boost Graph Library to implement graphs in the Tiger Compiler. You must be able to manipulate Boost Graphs, and understand some aspects of their design.

Flow graph

A representation of all paths that might be traversed through a program during its execution. If an instruction A can be followed by another instruction B, then an edge is created between A and B.

One graph is created per function. They serve as an input for the liveness graph.

Liveness graph

A representation, of all alive variables before and after each instruction. A variable is considered live if it holds a value that may be needed in the future.

It is the exact computation of the variables that are used at the same time.

Interference graph/conflict graph

A representation, of all temporaries. They are said to interfere if they are alive at the same time, which is represented by an edge between the temporaries.

Interference is the condition that prevents two temporaries from being held in the same hard register.