ある関数の中で、同時に生きている値の数が最も多いところで5個だった。干渉グラフがこの5個以外の制約を生まない単純な場合、すべての値をスピルなしでレジスタに置くには、レジスタが少なくとも何個必要か。

正解：A. 5個

同時に生きている5個の値は、互いにすべて干渉するので、干渉グラフの中で5個の節がすべて辺でつながった形(完全グラフ)になり、塗り分けには少なくとも5色が必要です。直線的なコードのように生存区間が区間として表せる単純な場合は、同時に生きている値の最大数の色で塗り分けられるので、5個のレジスタで足ります。4個では、どこかで1つの値をメモリに退避するスピルが必要になります。10個は必要以上に多い数です。

• A. 正しい。同時に生きている最大数の5個が必要で、この場合は十分です。
• B. 4個ではどこかでスピルが必要になります。
• C. 10個は必要以上に多い数です。