コンパイラのレジスタ割り当てで、干渉グラフを塗り分ける(彩色する)方法を使うとき、グラフの節と辺が表すものの組み合わせとして正しいものはどれか。

正解：C. 節は値、辺は同時に生きている関係

干渉グラフでは、変数や途中の値を節にし、ある時点で両方ともまだ使われる(生きている)2つの値を辺で結びます。辺でつながった値は同時に必要なので、同じレジスタには入れられません。レジスタの数をk個として、隣どうしが同じ色にならないようにk色で塗り分けられれば、色をそのままレジスタに対応させて割り当てられます。塗り分けられない場合は、一部の値をメモリに退避(スピル)します。命令の順番やレジスタの配線を表すグラフではありません。

• A. 命令の順番を表すグラフではありません。
• B. レジスタの配線を表すグラフではありません。
• C. 正しい。同時に生きている値どうしを辺で結びます。