어떤 함수 안에서 동시에 살아 있는 값의 수가 가장 많은 곳에서 5개였다. 간섭 그래프가 이 5개 이외의 제약을 만들지 않는 단순한 경우, 모든 값을 스필 없이 레지스터에 두려면 레지스터가 최소 몇 개 필요한가?

정답: A. 5개

동시에 살아 있는 5개의 값은 서로 모두 간섭하므로, 간섭 그래프 안에서 5개의 노드가 모두 간선으로 연결된 형태(완전 그래프)가 되어 칠하는 데 최소 5색이 필요합니다. 직선적인 코드처럼 생존 구간을 구간으로 나타낼 수 있는 단순한 경우에는 동시에 살아 있는 값의 최대 개수만큼의 색으로 칠할 수 있으므로 5개의 레지스터로 충분합니다. 4개로는 어딘가에서 하나의 값을 메모리로 내보내는 스필이 필요해집니다. 10개는 필요 이상으로 많은 수입니다.

• A. 올바릅니다. 동시에 살아 있는 최대 개수인 5개가 필요하며 이 경우에는 충분합니다.
• B. 4개로는 어딘가에서 스필이 필요해집니다.
• C. 10개는 필요 이상으로 많은 수입니다.