루프 불변 코드 이동

컴퓨터 프로그래밍에서 루프 불변 코드는 프로그램의 의미론에 영향을 주지 않고 루프 본문 밖으로 이동할 수 있는 명령문 또는 표현식( 명령형 프로그래밍 프로그래밍 언어에서)으로 구성된다. 루프 불변 코드 이동(Loop-invariant code motion, 호이스팅 또는 스칼라 승격이라고도 함)은 이 이동을 자동으로 수행하는 컴파일러 최적화이다.

예시
다음 코드 샘플에는 두 가지 최적화가 적용될 수 있다.

int i = 0;
while (i < n) {
    x = y + z;
    a[i] = 6 * i + x * x;
    ++i;
}

x = y + z와 x * x 계산은 루프 불변이지만, 코드를 루프 밖으로 이동하기 전에 주의를 기울여야 한다. 루프 조건이 false일 가능성(예: n이 음수 값을 가질 경우)이 있으며, 이 경우 루프 본문은 전혀 실행되지 않아야 한다. 올바른 동작을 보장하는 한 가지 방법은 루프 외부에 조건부 분기를 사용하는 것이다. 루프 조건을 평가하는 것은 부작용을 가질 수 있으므로, if 구성에 의한 추가 평가는 while 루프를 do {} while로 대체하여 보상해야 한다. 코드가 처음부터 do {} while을 사용했다면, 루프 본문이 최소 한 번 실행될 것이 보장되므로 전체 보호 프로세스가 필요 없다.

int i = 0;
if (i < n) {
    x = y + z;
    int const t1 = x * x;
    do {
        a[i] = 6 * i + t1;
        ++i;
    } while (i < n);
}

이 코드는 더욱 최적화될 수 있다. 예를 들어, 강도 감소는 루프 내의 두 곱셈(6*i 및 a[i])을 제거할 수 있고, 유도 변수 제거는 i를 완전히 생략할 수 있다. 6 * i는 i 자체와 동기화되어야 하므로 둘 다 가질 필요는 없다.

불변 코드 감지
일반적으로, 도달 정의 분석은 명령문이나 표현식이 루프 불변인지 감지하는 데 사용된다.

예를 들어, 어떤 단순 표현식의 피연산자에 대한 모든 도달 정의가 루프 밖에 있다면, 그 표현식은 루프 밖으로 이동될 수 있다.

모이앙, 루비아노, 세이예의 최근 연구는 데이터 흐름 의존성 분석을 사용하여 불변 명령어뿐만 아니라 내부 루프와 같은 더 큰 코드 조각도 감지한다. 이 분석은 또한 임의의 차수의 준불변, 즉 루프 본문의 고정된 반복 횟수 후에 불변이 되는 명령어 또는 코드 조각을 감지한다. 이 기술은 후에 오베르, 루비아노, 루쉬, 세이예에 의해 루프를 자동으로 병렬화하는 데 사용되었다.

장점
루프 밖으로 이동된 루프 불변 코드는 더 적게 실행되어 속도를 향상시킨다. 이 변환의 또 다른 효과는 상수를 레지스터에 저장하고 각 반복마다 주소를 계산하고 메모리(또는 캐시 라인)에 접근할 필요가 없다는 것이다.

그러나 너무 많은 변수가 생성되면, 특히 32비트 X86과 같이 레지스터가 적은 프로세서에서는 레지스터 압박이 높아진다. 컴파일러가 레지스터를 다 소진하면 일부 변수는 레지스터 스필링된다. 이를 상쇄하기 위해 역최적화인 재자료화가 수행될 수 있다.

 같이 보기 
 코드 이동
 루프 불변성

더 읽어보기
 Aho, Alfred V.; Sethi, Ravi; & Ullman, Jeffrey D. (1986). Compilers: Principles, Techniques, and Tools. Addison Wesley. .

 각주 

 외부 링크 
 컴파일러 최적화 — 호이스팅

분류:컴파일러 최적화