
3.2 Code Generation and Back-End Compilation 161
those variables have nonoverlapping lifetimes. An edge, therefore, identifies a
pair of variables that can be allocated to the same register. The pairwise infor-
mation is easy to generate from the schedule. However, to choose registers for
the variables, we need to consider all the conflicts.
clique A register is represented in this formulation by a clique of nodes, a clique
being a set in which every pair of vertices is connected by an edge. To avoid
defining a clique that is a subset of a larger clique, a clique must be the largest
possible set of fully connected nodes. A graph and a set of cliqu