리머티리얼라이제이션
컴퓨터 과학에서 리머티리얼라이제이션(rematerialization) 또는 리맷(remat)은 값을 메모리에서 로드하는 대신 재계산하여 시간을 절약하는 컴파일러 최적화 기법이다. 이는 일반적으로 레지스터 할당과 밀접하게 통합되어 있으며, 레지스터를 메모리로 스필링하는 대안으로 사용된다. 이 개념은 그레고리 차이틴, 마크 아우스랜더, 아쇼크 찬드라, 존 코크, 마틴 홉킨스 및 피터 마크스타인에 의해 고안되었으며 1970년대 후반 801 미니컴퓨터용 Pl.8 컴파일러에 구현되었다. 이후 1992년 프레스턴 브릭스, 키스 D. 쿠퍼, 린다 토르크존에 의해 개선되었다.
공통 부분식 제거 및 루프 불변 코드 이동과 같은 전통적인 최적화는 종종 중복 계산을 제거하는 데 중점을 둔다. 계산은 CPU 사이클을 필요로 하므로 이는 일반적으로 좋은 일이지만, 변수의 라이브 범위를 늘리고 많은 새로운 변수를 생성하여 레지스터 할당 중 스필링을 초래할 수 있는 잠재적으로 파괴적인 부작용이 있다. 리머티리얼라이제이션은 거의 정반대이다. 즉, CPU 계산량을 늘려 레지스터 압력을 줄인다. 불필요한 계산 시간을 추가하는 것을 피하기 위해 리머티리얼라이제이션은 컴파일러가 이점이 있다고 확신할 때만 수행된다. 즉, 메모리로 레지스터 스필링이 발생할 경우에만 수행된다.
리머티리얼라이제이션은 사용 가능 표현식의 개념을 사용하여 각 변수를 계산하는 데 사용되는 표현식을 추적함으로써 작동한다. 때때로 값을 계산하는 데 사용되는 변수가 수정되어 더 이상 해당 값을 리머티리얼라이즈하는 데 사용될 수 없는 경우가 있다. 그러면 해당 표현식은 더 이상 사용 가능하지 않다고 말한다. 다른 기준도 충족되어야 한다. 예를 들어 값을 리머티리얼라이즈하는 데 사용되는 표현식의 최대 복잡성 등이 있다. 로드보다 더 많은 시간이 걸리는 복잡한 계산을 사용하여 값을 리머티리얼라이즈하는 것은 도움이 되지 않을 것이다. 일반적으로 표현식은 부작용이 없어야 한다.
외부 링크
[편집]- Chaitin, Gregory, Marc Auslander, Ashok Chandra, John Cocke, Martin Hopkins, and Peter Markstein. "Register Allocation Via Coloring, Computer Languages, Vol. 6, No. 1, 1981, pp. 47-57"
- P. Briggs, K. D. Cooper, and L. Torczon. Rematerialization. Proceedings of the SIGPLAN 92 Conference on Programming Language Design and Implementation, SIGPLAN Notices 27(7), p.311-321. July 1992.
- Mukta Punjabi. Register Rematerialization in GCC. Discusses gcc's implementation of rematerialization.