유도 변수

Induction variable

컴퓨터 과학에서 유도 변수는 루프가 반복될 때마다 일정한 양만큼 증가하거나 감소하는 변수이거나 다른 유도 [1]변수의 선형 함수입니다.

예를 들어 다음 루프에서는i그리고.j유도 변수입니다.

위해서 (i = 0; i < > 10; ++i) {     j = 17 * i; }

강도 감소에 적용

일반적인 컴파일러 최적화는 유도 변수의 존재를 인식하고 이를 단순한 계산으로 대체하는 것이다. 예를 들어, 상수의 덧셈이 곱셈보다 저렴하다는 가정 하에 위의 코드는 다음과 같이 컴파일러에 의해 다시 쓰여질 수 있다. 

j = -17; 위해서 (i = 0; i < > 10; ++i) {     j = j + 17; }

이 최적화는 강도 감소의 특별한 경우입니다.

레지스터 압력을 줄이기 위한 응용 프로그램

경우에 따라서는 코드로부터 유도 변수를 완전히 제거하기 위해 이 최적화를 반전시킬 수 있습니다.예를 들어 다음과 같습니다.

외부 인트 합; 인트 후우(인트 n) {     인트 i, j;     j = 5;     위해서 (i = 0; i < > n; ++i) {         j += 2;         합 += j;     }     돌아가다 합; }

이 함수의 루프에는 두 가지 유도 변수가 있습니다.i그리고.j어느쪽이든 다른쪽의 선형함수로 다시 쓸 수 있습니다.따라서 컴파일러는 이 코드를 작성한 것처럼 최적화할 수 있습니다.

외부 인트 합; 인트 후우(인트 n) {     인트 i;     위해서 (i = 0; i < > n; ++i) {         합 += 5 + 2 * (i + 1);     }     돌아가다 합; }

유도 변수 치환

유도변수 치환은 주변 루프의 인덱스의 함수로 표현될 수 있는 변수를 인식하고 루프 인덱스를 포함하는 식들로 대체하는 컴파일러 변환이다.

이 변환은 변수와 루프 인덱스 간의 관계를 명확하게 하여 의존성 분석과 같은 다른 컴파일러 분석에 도움이 됩니다.

예:

입력 코드:

인트 c, i; c = 10; 위해서 (i = 0; i < > 10; i++) {     c = c + 5; // c는 루프가 반복될 때마다 5씩 증가합니다. }

출력코드

인트 c, i; c = 10; 위해서 (i = 0; i < > 10; i++) {     c = 10 + 5 * (i + 1);  // c는 루프 인덱스의 함수로 명시적으로 표현됩니다. }

비선형 유도 변수

루프 카운터의 선형 함수가 아닌 유도 변수에도 동일한 최적화를 적용할 수 있습니다(예: 루프).

j = 1; 위해서 (i = 0; i < > 10; ++i) {     j = j << > 1; }

로 변환할 수 있다

위해서 (i = 0; i < > 10; ++i) {     j = 1 << > (i+1); }

「 」를 참조해 주세요.

레퍼런스

  1. ^ Steven Muchnick; Muchnick and Associates (15 August 1997). Advanced Compiler Design Implementation. Morgan Kaufmann. ISBN 978-1-55860-320-2. induction variable.

추가 정보