레지스터 할당의 대상이 되는 모든 변수에 대해 변수들의 생존 범위 정보를 구하는 전역 자료 흐름 분석 단계와, 상기 생존 범위 정보를 이용하여 그래프를 구축하는 간섭 그래프 구축 단계와, 상기 레지스터 간섭 그래프의 노드를 그래프 분할 휴리스틱을 이용하여 독립 집합으로의 분할을 시도하여 실패하면 대피 코드를 삽입하고, 간섭 그래프를 재 조정하여 다시 로드하기 위한 그래프 분할 단계와, 상기 레지스터 간섭 그래프의 노드를 그래프 분할 휴리스틱을 이용하여 독립 집합으로의 분할을 시도하여 성공하면 실제 레지스터를 변수에 배정한 후 종료하는 단계로 이루어진 것을 특징으로 하는 그래프 분할에 의한 레지스터 할당 방법

그래프 분할에 의한 레지스터 할당 방법에 있어서, 간섭 그래프를 입력으로 하여 분할된 결과를 출력하고 레지스터의 선호도를 조사하는 단계와, 상기 조사 결과에 따라 할당 대상이 되는 노드들의 순서를 결정하는 단계와, 상기 결정에 따라 노드들을 할당할 순서 리스트에 저장한 후 분할에 할당할 노드들의 집합 여부를 확인하는 단계와, 상기 확인결과에 따라 분할에 할당할 노드들의 집합이 있을 경우 다시 하드 레지스터에 대한 선호도 존재 여부를 확인하는 단계와, 상기 확인결과 하드 레지스터에 대한 선호도가 존재하면 이를 파악하여 레지스터 선호도가 있는 노드를 해당 분할에 재 배치하는 단계와, 상기 확인결과 하드 레지스터에 대한 선호도가 존재하지 않으면 복사문에 의해 선호도를 가지는 노드가 리스트에 존재하는지를 확인하는 단계와, 상기 확인결과 리스트에 존재하면 복사문 선호도가 있는 노드를 분할한 후 어떤 분할에도 포함시킬 수 없음을 확인하여 해당 분할에 할당하거나 복사문 선호도를 가지는 노드를 위해 새로운 분할을 생성하여 해당 분할에 할당하는 단계와, 상기 확인결과 리스트에 존재하지 않으면 일반적인 분할을 한 후 어떤 분할에도 포함시킬 수 없음을 확인하여 해당 분할에 할당하거나 새로운 분할을 생성하여 해당 분할에 할당하는 단계와, 상기 확인결과 하드 레지스터에 대한 선호도가 존재하지 않으면 분할된 수가 실제 레지스터 수 보다 많은지를 확인하는 단계와, 상기 확인결과 분할된 수가 실제 레지스터 수 보다 많으면 선호도를 고려한 대피 코드를 처리하고, 이후 대피 코드 삽입한 후 생존 범위를 계산하여 새로운 그래프를 구성한 후 해당 분할에 할당하는 단계와, 상기 확인결과 분할된 수가 실제 레지스터 수 보다 많지 않으면 레지스터를 배정한 후 종료하는 단계로 이루어진 것을 특징으로 하는 그래프 분할에 의한 레지스터 방법

제2항에 있어서, 상기 선호도를 고려한 대피 코드 처리 방법은 대피 시킬 분할의 갯수가 특수용도 레지스터 이전에 배치된 분할의 수 보다 큰지를 확인하는 단계와, 상기 확인결과 특수 용도 레지스터 이전에 배치된 분할의 수 보다 작으면 분할의 갯수에서 사용 가능한 레지스터 수를 감한 수의 분할을 대피한 후 종료하는 단계와, 상기 확인결과 특수 용도 레지스터 이전에 배치된 분할의 수 보다 크면 선호도에 있는 하드 레지스터 이후에서 대피 될 분할 수를 계산하고, 전체 분할 중 특수 용도 레지스터 이전에 배치된 분할의 수 만큼 분할을 대피하며, 선호도 있는 하드 레지스터 이후에서 대피 될 분할 수 만큼의 분할을 대피한 후 종료하는 단계로 이루어진 것을 특징으로 하는 그패프 분할에 의한 레지스터 할당 방법

그래프 분할에 의한 레지스터 할당 방법에 있어서, 프로그램의 한 단위 영역을 부 영역으로 분할하고, 현 영역에서는 참조되고 부 영역에서는 참조되지 않는 변수에 대해 분할 한후 분할한 수가 레지스터 수 보다 큰지를 확인하는 단계와, 상기 확인 결과 분할한 수가 레지스터 수보다 작으면 바로 대피리스트에 노드가 존재 하는지를 확인하고, 분할한 수가 레지스터 수 보다 크면 많은 수 만큼 분할을 이동시키고, 옮기지 못한 노드를 대피 리스트에 유지한 후 대피 리스트에 노드가 존재 하는지를 확인하는 단계와, 상기 대피 리스트에 노드가 존재하면 부 영역에서 참조되지 않음을 확인하고, 존재하지 않으면 분할의 수가 실제 사용 가능한 레지스터 수보다 큰지를 확인하는 단계와, 상기 부 영역에서 참조되지 않았으면 해당 변수를 해당 부 영역에서 대피하고, 분할 조정을 한 후 다시 상기 대피 리스트에 노드가 존재 하는지를 확인하는 단계와, 상기 부 영역에서 참조 되었으면 상기 분할의 수가 실제 사용 가능한 레지스터 수보다 큰지를 확인하는 단계와, 상기 확인 결과 분할한 수가 실제 사용 가능한 레지스터 수보다 작으면 바로 종료하고, 크면 수행 빈도가 높은 하위 영역에서 참조된 변수를 대피한 후 종료하는 단계로 이루어진 것을 특징으로 하는 그래프 분할에 의한 레지스터 할당 방법