강도 감소

컴파일러 구성에서 강도 감소 또는 스트렝스 리덕션(strength reduction)은 비용이 많이 드는 연산을 동등하지만 비용이 적게 드는 연산으로 대체하는 컴파일러 최적화이다. 강도 감소의 고전적인 예는 루프 내의 강한 곱셈을 약한 덧셈으로 변환하는 것으로, 이는 배열 주소 지정에서 자주 발생한다.

강도 감소의 예로는 루프 내의 곱셈을 덧셈으로 대체하고 루프 내의 거듭제곱을 곱셈으로 대체하는 것이 있다.

 코드 분석 
프로그램 실행 시간의 대부분은 일반적으로 코드의 작은 부분(핫 스팟이라고 불림)에서 소비되며, 이 코드는 종종 반복적으로 실행되는 루프 내에 있다.

컴파일러는 루프를 식별하고 해당 루프 내의 레지스터 값 특성을 인식하는 방법을 사용한다. 강도 감소를 위해 컴파일러가 관심을 갖는 것은 다음과 같다.
루프 불변: 루프 본문 내에서 변경되지 않는 값.
유도 변수: 루프를 통해 매번 반복되는 값.

루프 불변은 본질적으로 루프 내에서 상수이지만, 그 값은 루프 외부에서 변경될 수 있다. 유도 변수는 알려진 양만큼 변경된다. 이 용어는 특정 루프에 상대적이다. 루프가 중첩될 때, 바깥쪽 루프의 유도 변수는 안쪽 루프의 루프 불변이 될 수 있다.

강도 감소는 루프 불변과 유도 변수를 포함하는 표현식을 찾는다. 이러한 표현식 중 일부는 단순화될 수 있다. 예를 들어, 루프 불변 c와 유도 변수 i의 곱셈은
c = 7;
for (i = 0; i < N; i++)
{
    y[i] = c * i;
}

연속적인 약한 덧셈으로 대체될 수 있다.
c = 7;
k = 0;
for (i = 0; i < N; i++)
{
    y[i] = k;
    k = k + c;
}

 강도 감소 예제 

다음은 배열 인덱싱 주소 계산에서 발생한 모든 루프 곱셈을 강도 감소시키는 예제이다.

배열을 단위 행렬로 설정하는 간단한 루프를 상상해 보자.

for (i = 0; i < n; i++)
{
    for (j = 0; j < n; j++)
    {
        A[i,j] = 0.0;
    }
    A[i,i] = 1.0;
}

중간 코드

컴파일러는 이 코드를 다음과 같이 볼 것이다.

0010  ; for (i = 0, i < n; i++)
0020  ; {
0030      r1 = #0                        ; i = 0
0040  G0000:
0050      load r2, n                     ; i < n
0060      cmp r1, r2
0070      bge G0001
0080
0090      ; for (j = 0; j < n; j++)
0100      ; {
0110           r3   = #0                 ; j = 0
0120  G0002:
0130           load r4, n                ; j < n
0140           cmp r3, r4
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0180           load r7, n
0190           r8  = r1 * r7             ; calculate subscript i * n + j
0200           r9  = r8 + r3
0210           r10 = r9 * #8             ; calculate byte address
0220           fr3 = #0.0
0230           fstore fr3, A[r10]
0240
0250           r3 = r3 + #1              ; j++
0260           br G0002
0270      ; }
0280  G0003:
0290      ; A[i,i] = 1.0;
0300      load r12, n                    ; calculate subscript i * n + i
0310      r13 = r1 * r12
0320      r14 = r13 + r1
0330      r15 = r14 * #8                 ; calculate byte address
0340      fr4 = #1.0
0350      fstore fr4, A[r15]
0360
0370      ; i++
0380      r1 = r1 + #1
0390      br G0000
0400  ; }
0410  G0001:

이것은 2차원 배열 A를 n*n 크기의 1차원 배열로 표현하므로, 고수준 코드가 A[x, y]를 표현할 때마다 유효한 모든 인덱스 x와 y에 대해 내부적으로 A[(x*n)+y]가 된다.

 많은 최적화 

컴파일러는 강도 감소뿐만 아니라 많은 최적화를 시작한다. 루프 내에서 상수(불변)인 표현식은 루프 밖으로 끌어올려진다. 부동 소수점 레지스터 fr3 및 fr4와 같은 상수는 두 루프 외부에서 로드될 수 있다. 일부 변수가 변경되지 않는다는 인식은 레지스터를 병합할 수 있게 한다. n은 상수이므로 r2, r4, r7, r12는 끌어올려지고 병합될 수 있다. 공통 값 i*n은 (끌어올려진) r8과 r13에서 계산되므로, 이들은 합쳐진다. 가장 안쪽 루프(0120-0260)는 11개에서 7개의 중간 명령어로 감소되었다. 가장 안쪽 루프에 남아있는 유일한 곱셈은 0210번 줄의 8 곱셈이다.

0010  ; for (i = 0, i < n; i++)
0020    {
0030      r1 = #0                        ; i = 0
0050      load r2, n
0130 ;   load r4, n     killed; use r2
0180 ;   load r7, n     killed; use r2
0300 ;   load r12, n    killed; use r2
0220      fr3 = #0.0
0340      fr4 = #1.0
0040  G0000:
0060      cmp r1, r2                     ; i < n
0070      bge G0001
0080
0190      r8  = r1 * r2                  ; calculate subscript i * n
0310 ;   r13 = r1 * r2  killed; use r8   ; calculate subscript i * n
0090      ; for (j = 0; j < n; j++)
0100        {
0110           r3   = #0                 ; j = 0
0120  G0002:
0140           cmp r3, r2                ; j < n
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0200           r9  = r8 + r3             ; calculate subscript i * n + j
0210           r10 = r9 * #8             ; calculate byte address
0230           fstore fr3, A[r10]
0240
0250           r3 = r3 + #1              ; j++
0260           br G0002
0270        }
0280  G0003:
0290      ; A[i,i] = 1.0;
0320      r14 = r8  + r1                 ; calculate subscript i * n + i
0330      r15 = r14 * #8                 ; calculate byte address
0350      fstore fr4, A[r15]
0360
0370      ;i++
0380      r1 = r1 + #1
0390      br G0000
0400    }
0410  G0001:

더 많은 최적화가 필요하다. 레지스터 r3은 가장 안쪽 루프(0140-0260)의 주요 변수이다. 루프를 통과할 때마다 1씩 증가한다. 레지스터 r8(가장 안쪽 루프에서 불변)이 r3에 더해진다. 컴파일러는 r3 대신 r3을 제거하고 r9를 사용할 수 있다. 루프는 r3 = 0에서 n-1까지 제어되는 대신 r9=r8+0에서 r8+n-1까지 제어될 수 있다. 이는 4개의 명령어를 추가하고 4개의 명령어를 제거하지만, 루프 내부에는 하나의 명령어가 더 적다.

0110  ;       r3   = #0     killed       ; j = 0
0115           r9   = r8                 ; new assignment
0117           r20  = r8 + r2            ; new limit
0120  G0002:
0140  ;       cmp r3, r2    killed       ; j < n
0145           cmp r9, r20               ; r8 + j < r8 + n = r20
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0200  ;       r9  = r8 + r3 killed       ; calculate subscript i * n + j
0210           r10 = r9 * #8             ; calculate byte address
0230           fstore fr3, A[r10]
0240
0250  ;       r3 = r3 + #1  killed       ; j++
0255           r9 = r9 + #1              ; new loop variable
0260           br G0002

이제 r9가 루프 변수이지만, 8을 곱하는 연산과 상호작용한다. 여기에서 우리는 강도 감소를 할 수 있다. 8을 곱하는 연산은 8을 연속적으로 더하는 것으로 줄일 수 있다. 이제 루프 안에 곱셈 연산이 없다.

0115           r9   = r8                 ; new assignment
0117           r20  = r8 + r2            ; new limit
0118           r10  = r8 * #8            ; initial value of r10
0120  G0002:
0145           cmp r9, r20               ; r8 + j < r8 + n = r20
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0210  ;       r10 = r9 * #8    killed    ; calculate byte address
0230           fstore fr3, A[r10]
0240
0245           r10 = r10 + #8            ; strength reduced multiply
0255           r9 = r9 + #1              ; loop variable
0260           br G0002

레지스터 r9와 r10(= 8*r9) 모두 필요하지 않다. 루프에서 r9를 제거할 수 있다. 이제 루프는 5개의 명령어로 구성된다.

0115  ;       r9   = r8         killed
0117           r20  = r8 + r2            ; limit
0118           r10  = r8 * #8            ; initial value of r10
0119           r22  = r20 * #8           ; new limit
0120  G0002:
0145  ;       cmp r9, r20       killed   ; r8 + j < r8 + n = r20
0147           cmp r10, r22              ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0230           fstore fr3, A[r10]
0240
0245           r10 = r10 + #8            ; strength reduced multiply
0255  ;       r9 = r9 + #1      killed   ; loop variable
0260           br G0002

 바깥쪽 루프 

전체 그림으로 돌아가서:

0010  ; for (i = 0, i < n; i++)
0020    {
0030      r1 = #0                        ; i = 0
0050      load r2, n
0220      fr3 = #0.0
0340      fr4 = #1.0
0040  G0000:
0060      cmp r1, r2                     ; i < n
0070      bge G0001
0080
0190      r8   = r1 * r2                 ; calculate subscript i * n
0117      r20  = r8 + r2                 ; limit
0118      r10  = r8 * #8                 ; initial value of r10
0119      r22  = r20 * #8                ; new limit
0090      ; for (j = 0; j < n; j++)
0100        {
0120  G0002:
0147           cmp r10, r22              ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0230           fstore fr3, A[r10]
0240
0245           r10 = r10 + #8            ; strength reduced multiply
0260           br G0002
0270        }
0280  G0003:
0290      ; A[i,i] = 1.0;
0320      r14 = r8  + r1                 ; calculate subscript i * n + i
0330      r15 = r14 * #8                 ; calculate byte address
0350      fstore fr4, A[r15]
0360
0370      ;i++
0380      r1 = r1 + #1
0390      br G0000
0400    }
0410  G0001:

이제 r1을 증가시키는 외부 루프 내에 4개의 곱셈이 있다. 0190번 줄의 r8 = r1*r2는 루프 진입 전(0055번 줄)에 설정하고 루프 하단(0385번 줄)에서 r2만큼 증가시켜 강도 감소할 수 있다.

값 r8*8(0118번 줄)은 초기화(0056번 줄)하고 r8이 증가할 때 8*r2를 더하여(0386번 줄) 강도 감소할 수 있다.

레지스터 r20은 루프를 통과할 때마다 0117번 줄에서 불변/상수 r2에 의해 증가하고 있다. 증가된 후 8을 곱하여 0119번 줄에서 r22를 생성한다. 이 곱셈은 루프를 통과할 때마다 8*r2를 더함으로써 강도 감소할 수 있다.

0010  ; for (i = 0, i < n; i++)
0020    {
0030      r1 = #0                        ; i = 0
0050      load r2, n
0220      fr3 = #0.0
0340      fr4 = #1.0
0055      r8  = r1 * r2                  ; set initial value for r8
0056      r40 = r8 * #8                  ; initial value for r8 * 8
0057      r30 = r2 * #8                  ; increment for r40
0058      r20 = r8 + r2                  ; copied from 0117
0058      r22 = r20 * #8                 ; initial value of r22
0040  G0000:
0060      cmp r1, r2                     ; i < n
0070      bge G0001
0080
0190  ;  r8   = r1 * r2    killed        ; calculate subscript i * n
0117  ;  r20  = r8 + r2    killed - dead code
0118      r10  = r40                     ; strength reduced expression to r40
0119  ;  r22  = r20 * #8   killed        ; strength reduced
0090      ; for (j = 0; j < n; j++)
0100        {
0120  G0002:
0147           cmp r10, r22              ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0230           fstore fr3, A[r10]
0240
0245           r10 = r10 + #8            ; strength reduced multiply
0260           br G0002
0270        }
0280  G0003:
0290      ; A[i,i] = 1.0;
0320      r14 = r8  + r1                 ; calculate subscript i * n + i
0330      r15 = r14 * #8                 ; calculate byte address
0350      fstore fr4, A[r15]
0360
0370      ;i++
0380      r1  = r1 + #1
0385      r8  = r8 + r2                  ; strength reduce r8 = r1 * r2
0386      r40 = r40 + r30                ; strength reduce expression r8 * 8
0388      r22 = r22 + r30                ; strength reduce r22 = r20 * 8
0390      br G0000
0400    }
0410  G0001:

 마지막 곱셈 
이제 두 루프는 외부 루프 내에 하나의 곱셈 연산(0330번 줄)만 남고 내부 루프에는 곱셈 연산이 없다.

0010  ; for (i = 0, i < n; i++)
0020    {
0030      r1 = #0                        ; i = 0
0050      load r2, n
0220      fr3 = #0.0
0340      fr4 = #1.0
0055      r8  = r1 * r2                  ; set initial value for r8
0056      r40 = r8 * #8                  ; initial value for r8 * 8
0057      r30 = r2 * #8                  ; increment for r40
0058      r20 = r8 + r2                  ; copied from 0117
0058      r22 = r20 * #8                 ; initial value of r22
0040  G0000:
0060      cmp r1, r2                     ; i < n
0070      bge G0001
0080
0118      r10  = r40                     ; strength reduced expression to r40
0090      ; for (j = 0; j < n; j++)
0100        {
0120  G0002:
0147           cmp r10, r22              ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0230           fstore fr3, A[r10]
0240
0245           r10 = r10 + #8            ; strength reduced multiply
0260           br G0002
0270        }
0280  G0003:
0290      ; A[i,i] = 1.0;
0320      r14 = r8  + r1                 ; calculate subscript i * n + i
0330      r15 = r14 * #8                 ; calculate byte address
0350      fstore fr4, A[r15]
0360
0370      ;i++
0380      r1  = r1 + #1
0385      r8  = r8 + r2                  ; strength reduce r8 = r1 * r2
0386      r40 = r40 + r30                ; strength reduce expression r8 * 8
0388      r22 = r22 + r30                ; strength reduce r22 = r20 * 8
0390      br G0000
0400    }
0410  G0001:

0320번 줄에서 r14는 r8과 r1의 합이며, r8과 r1은 루프 내에서 증가하고 있다. 레지스터 r8은 r2(=n)만큼 증가하고 r1은 1만큼 증가한다. 결과적으로 r14는 루프를 통과할 때마다 n+1만큼 증가한다. 0330번 줄의 마지막 루프 곱셈은 루프를 통과할 때마다 (r2+1)*8을 더함으로써 강도 감소될 수 있다.

0010  ; for (i = 0, i < n; i++)
0020    {
0030      r1 = #0                        ; i = 0
0050      load r2, n
0220      fr3 = #0.0
0340      fr4 = #1.0
0055      r8  = r1 * r2                  ; set initial value for r8
0056      r40 = r8 * #8                  ; initial value for r8 * 8
0057      r30 = r2 * #8                  ; increment for r40
0058      r20 = r8 + r2                  ; copied from 0117
0058      r22 = r20 * #8                 ; initial value of r22
005A      r14 = r8 + r1                  ; copied from 0320
005B      r15 = r14 * #8                 ; initial value of r15 (0330)
005C      r49 = r2 + #1
005D      r50 = r49 * #8                 ; strength reduced increment
0040  G0000:
0060      cmp r1, r2                     ; i < n
0070      bge G0001
0080
0118      r10  = r40                     ; strength reduced expression to r40
0090      ; for (j = 0; j < n; j++)
0100        {
0120  G0002:
0147           cmp r10, r22              ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0230           fstore fr3, A[r10]
0240
0245           r10 = r10 + #8            ; strength reduced multiply
0260           br G0002
0270        }
0280  G0003:
0290      ; A[i,i] = 1.0;
0320  ;  r14 = r8  + r1     killed      ; dead code
0330  ;  r15 = r14 * #8     killed      ; strength reduced
0350      fstore fr4, A[r15]
0360
0370      ;i++
0380      r1  = r1 + #1
0385      r8  = r8 + r2                  ; strength reduce r8 = r1 * r2
0386      r40 = r40 + r30                ; strength reduce expression r8 * 8
0388      r22 = r22 + r30                ; strength reduce r22 = r20 * 8
0389      r15 = r15 + r50                ; strength reduce r15 = r14 * 8
0390      br G0000
0400    }
0410  G0001:

아직 더 남았다. 상수 폴딩은 프롤로그에서 r1=0임을 인식하여 여러 명령어를 정리할 것이다. r8은 루프에서 사용되지 않으므로 사라질 수 있다.

게다가, r1은 루프를 제어하기 위해서만 사용되므로, r1은 r40과 같은 다른 유도 변수로 대체될 수 있다. i가 0 <= i < n으로 갔던 곳에서, 레지스터 r40은 0 <= r40 < 8 * n * n으로 간다.

0010  ; for (i = 0, i < n; i++)
0020    {
0030  ;  r1 = #0                        ; i = 0, becomes dead code
0050      load r2, n
0220      fr3 = #0.0
0340      fr4 = #1.0
0055  ;  r8  = #0         killed         ; r8 no longer used
0056      r40 = #0                       ; initial value for r8 * 8
0057      r30 = r2 * #8                  ; increment for r40
0058  ;  r20 = r2         killed         ; r8 = 0, becomes dead code
0058      r22 = r2  * #8                 ; r20 = r2
005A  ;  r14 =       #0   killed         ; r8 = 0, becomes dead code
005B      r15 =       #0                 ; r14 = 0
005C      r49 = r2 + #1
005D      r50 = r49 * #8                 ; strength reduced increment
005D      r60 = r2 * r30                 ; new limit for r40
0040  G0000:
0060  ;  cmp r1, r2       killed         ; i < n; induction variable replaced
0065      cmp r40, r60                   ; i * 8 * n < 8 * n * n
0070      bge G0001
0080
0118      r10  = r40                     ; strength reduced expression to r40
0090      ; for (j = 0; j < n; j++)
0100        {
0120  G0002:
0147           cmp r10, r22              ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0230           fstore fr3, A[r10]
0240
0245           r10 = r10 + #8            ; strength reduced multiply
0260           br G0002
0270        }
0280  G0003:
0290      ; A[i,i] = 1.0;
0350      fstore fr4, A[r15]
0360
0370      ;i++
0380  ;  r1  = r1 + #1      killed       ; dead code (r40 controls loop)
0385  ;  r8  = r8 + r2      killed       ; dead code
0386      r40 = r40 + r30                ; strength reduce expression r8 * 8
0388      r22 = r22 + r30                ; strength reduce r22 = r20 * 8
0389      r15 = r15 + r50                ; strength reduce r15 = r14 * 8
0390      br G0000
0400    }
0410  G0001:

 다른 강도 감소 연산 

연산자 강도 감소는 수학적 항등식을 사용하여 느린 수학 연산을 더 빠른 연산으로 대체한다. 이점은 대상 CPU와 때로는 주변 코드(CPU 내의 다른 기능 단위의 가용성에 영향을 미칠 수 있음)에 따라 달라진다.

 2의 거듭제곱으로 하는 정수 나눗셈 또는 곱셈을 산술 시프트 또는 논리 시프트로 대체C 및 자바와 같은 언어에서 정수 나눗셈은 0으로 반올림하는 의미론을 가지는 반면, 비트 시프트는 항상 내림하므로 음수에 대한 특별한 처리가 필요하다. 예를 들어, 자바에서 -3 / 2는 -1로 평가되지만, -3 >> 1은 -2로 평가된다. 따라서 이 경우 컴파일러는 2로 나누는 것을 비트 시프트로 대체하여 최적화할 수 없다.
 상수로 하는 정수 곱셈을 시프트, 덧셈 또는 뺄셈의 조합으로 대체
 상수와 하는 정수 나눗셈을 곱셈으로 대체하여 기계 정수의 제한된 범위를 활용한다. 이 방법은 나눗셈이 1보다 충분히 큰 비정수, 예를 들어 √2 또는 π인 경우에도 작동한다.

 원래 계산 대체 계산 y+= 1 y++ y%2 != 0 y & 1 y = x * 2 y = x << 1 y = x / 2 y = x >> 1 y = x % 2 y = x & 1 y = x * 15 y = (x << 4) - x y = (uint16_t)x / 10 y = ((uint32_t)x * (uint32_t)0xCCCD) >> 19) y = (uint16_t)x / π y = (((uint32_t)x * (uint32_t)0x45F3) >> 16) + x) >> 2)

 유도 변수 (고아) 

유도 변수 또는 재귀적 강도 감소는 체계적으로 변하는 변수의 함수를 함수의 이전 값을 사용하여 더 간단한 계산으로 대체한다. 절차형 프로그래밍 언어에서는 루프 변수를 포함하는 표현식에 적용되며, 선언형 프로그래밍 언어에서는 재귀 함수의 인수에 적용된다. 예를 들어,
 f x = ... (3 ** x) ... (f (x + 1)) ...
는 다음과 같이 된다.
 f x = f' x 1
 where
   f' x z = ... z ... (f' (x + 1) (3 * z)) ...
여기서 수정된 재귀 함수 는 두 번째 매개변수 z = 3 ** x를 사용하여 비용이 많이 드는 계산 (3 ** x)을 더 저렴한 (3 * z)로 대체할 수 있게 한다.

 같이 보기 
 고속 역 제곱근
 해커의 즐거움
 부분 평가

 내용주 

 각주 

분류:컴파일러 최적화