강도감소
Strength reduction컴파일러 구조에서 강도 감소는 값비싼 운영이 동등하지만 비용이 적게 드는 운영으로 대체되는 컴파일러 최적화다.[1]강도 감소의 전형적인 예는 루프 내부의 "강력한" 곱셈을 "취약한" 추가로 변환한다. 이는 어레이 어드레싱에서 자주 발생하는 것이다. (Cooper, Simpson & Vick 1995, 페이지 1)
강도 감소의 예는 다음과 같다.
- 루프 내의 곱셈을 덧셈으로 대체
- 루프 내의 지수를 곱으로 대체
코드분석
프로그램 실행 시간의 대부분은 일반적으로 코드의 작은 부분(핫 스팟이라고 함)에 소요되며, 그 코드는 종종 반복적으로 실행되는 루프 안에 있다.
컴파일러는 루프를 식별하고 루프 내에서 레지스터 값의 특성을 인식하는 방법을 사용한다.강도 감소를 위해 컴파일러는 다음 사항에 관심이 있다.
- 루프 불변제: 루프 본체 내에서 변경되지 않는 값.
- 유도 변수: 루프를 통해 매번 반복되는 값.
루프 불변성은 본질적으로 루프 내의 상수지만, 그 값은 루프 외부에서 변경될 수 있다.유도 변수는 알려진 양에 따라 변화하고 있다.그 용어들은 특정 루프에 상대적이다.루프가 내포된 경우, 외부 루프의 유도 변수는 내부 루프의 루프 불변성이 될 수 있다.
강도 감소는 루프 불변성 및 유도 변수를 포함하는 표현을 찾는다.그 표현들 중 일부는 단순화할 수 있다.예를 들어 루프 불변성의 곱하기c및 유도 변수i
c = 7; 을 위해 (i = 0; i < N; i++) { y[i] = c * i; } 연이은 약한 덧셈으로 대체할 수 있다.
c = 7; k = 0; 을 위해 (i = 0; i < N; i++) { y[i] = k; k = k + c; } 강도 감소 예
아래는 배열 인덱싱 주소 계산에서 발생한 모든 루프 승수를 강도로 감소시키는 예다.
배열을 ID 매트릭스로 설정하는 간단한 루프를 상상해 보십시오.
을 위해 (i = 0; i < n; i++) { 을 위해 (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 짐을 싣다 r2, n ; i < n 0060 cmp r1, r2 0070 큰 소리로 부르다 G0001 0080 0090 ;; for (j = 0; j < n; j++) 0100 ; { 0110 r3 = #0 ; j = 0 0120 G0002: 0130 짐을 싣다 r4, n ; j < n 0140 cmp r3, r4 0150 큰 소리로 부르다 G0003 0160 0170 ; A[i,j] = 0.0; 0180 짐을 싣다 r7, n 0190 r8 = r1 * r7 ; 첨자 i * n + j 계산 0200 r9 = r8 + r3 0210 r10 = r9 * #8 ; 바이트 주소 계산 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 짐을 싣다 r12년, n ; 첨자 i * n + i 계산 0310 r13 = r1 * r12년 0320 r14 = r13 + r1 0330 r15 = r14 * #8 ; 바이트 주소 계산 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 짐을 싣다 r2, n 0130 ; 로드 r4, n 제거됨; r2 사용 0180 ; 로드 r7, n 제거됨; r2 사용 0300 ; 로드 r12, n 제거됨, r2 사용 0220 fr3 = #0.0 0340 fr4 = #1.0 0040 G0000: 0060 cmp r1, r2 ; i < n 0070 큰 소리로 부르다 G0001 0080 0190 r8 = r1 * r2 ; 첨자 i 계산 * n 0310 ; r13 = r1 * r2 사용 안 함; r8; 첨자 i 계산 * n 0090 ;; for (j = 0; j < n; j++) 0100 { 0110 r3 = #0 ; j = 0 0120 G0002: 0140 cmp r3, r2 ; j < n 0150 큰 소리로 부르다 G0003 0160 0170 ; A[i,j] = 0.0; 0200 r9 = r8 + r3 ; 첨자 i * n + j 계산 0210 r10 = r9 * #8 ; 바이트 주소 계산 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 ; 첨자 i * n + i 계산 0330 r15 = r14 * #8 ; 바이트 주소 계산 0350 fstore fr4, A[r15] 0360 0370 ; i++ 0380 r1 = r1 + #1 0390 br G0000 0400 } 0410 G0001: 할 수 있는 최적화가 더 많다.레지스터 r3은 가장 안쪽 루프(0140-0260)의 주 변수로서, 루프를 통해 매번 1씩 증가한다.register r8(가장 안쪽 루프에서 불변함)이 r3에 추가된다.컴파일러는 r3 대신 r3을 제거하고 r9를 사용할 수 있다.루프는 r3 = 0 ~ n-1로 제어되는 대신 r9=r8+0 ~ r8+n-1로 제어할 수 있다.네 가지 지시를 추가하고 네 가지 지시를 죽이지만 루프 내부에는 한 가지 명령이 더 적다.
0110 ; r3 = #0 사망, j = 0 0115 r9 = r8 ; 새로운 과제 0117 r20 = r8 + r2 ; 새로운 한계 0120 G0002: 0140 ; cmp r3, r2 죽임; j < n 0145 cmp r9, r20 ; r8 + j < r8 + n = r20 0150 큰 소리로 부르다 G0003 0160 0170 ; A[i,j] = 0.0; 0200 ; r9 = r8 + r3 deaded; 첨자 i * n + j 계산 0210 r10 = r9 * #8 ; 바이트 주소 계산 0230 fstore fr3, A[r10] 0240 0250 ; r3 = r3 + #1 죽임; j++ 0255 r9 = r9 + #1 ; 새로운 루프 변수 0260 br G0002 이제 r9은 루프 변수지만 8의 곱셈과 상호작용한다.이제 힘을 좀 줄여야겠어.8을 곱하면 8을 연속해서 추가할 수 있다.이제 루프 안에는 승수가 없다.
0115 r9 = r8 ; 새로운 과제 0117 r20 = r8 + r2 ; 새로운 한계 0118 r10 = r8 * #8 ; r10의 초기값 0120 G0002: 0145 cmp r9, r20 ; r8 + j < r8 + n = r20 0150 큰 소리로 부르다 G0003 0160 0170 ; A[i,j] = 0.0; 0210 ; r10 = r9 * #8 죽임; 바이트 주소 계산 0230 fstore fr3, A[r10] 0240 0245 r10 = r10 + #8 ; 감소된 강도 곱하기 0255 r9 = r9 + #1 ; 루프 변수 0260 br G0002 레지스터 r9과 r10(= 8*r9)은 둘 다 필요하지 않다. r9은 루프에서 제거할 수 있다.루프는 이제 5가지 지시사항이다.
0115 ; r9 = r8 사망 0117 r20 = r8 + r2 제한하다; 제한하다 0118 r10 = r8 * #8 ; r10의 초기값 0119 r22 = r20 * #8 ; 새로운 한계 0120 G0002: 0145 ; cmp r9, r20 죽임; r8 + j < r8 + n = r20 0147 cmp r10, r22 ; r10 = 8**(r8 + j) < 8*(r8 + n) = r22 0150 큰 소리로 부르다 G0003 0160 0170 ; A[i,j] = 0.0; 0230 fstore fr3, A[r10] 0240 0245 r10 = r10 + #8 ; 감소된 강도 곱하기 0255 ; r9 = r9 + #1 죽임; 루프 변수 0260 br G0002 외부 루프
전체 그림으로 돌아가기:
0010 ;; for (i = 0, i < n; i++) 0020 { 0030 r1 = #0 ; i = 0 0050 짐을 싣다 r2, n 0220 fr3 = #0.0 0340 fr4 = #1.0 0040 G0000: 0060 cmp r1, r2 ; i < n 0070 큰 소리로 부르다 G0001 0080 0190 r8 = r1 * r2 ; 첨자 i 계산 * n 0117 r20 = r8 + r2 제한하다; 제한하다 0118 r10 = r8 * #8 ; r10의 초기값 0119 r22 = r20 * #8 ; 새로운 한계 0090 ;; for (j = 0; j < n; j++) 0100 { 0120 G0002: 0147 cmp r10, r22 ; r10 = 8**(r8 + j) < 8*(r8 + n) = r22 0150 큰 소리로 부르다 G0003 0160 0170 ; A[i,j] = 0.0; 0230 fstore fr3, A[r10] 0240 0245 r10 = r10 + #8 ; 감소된 강도 곱하기 0260 br G0002 0270 } 0280 G0003: 0290 ; A[i,i] = 1.0; 0320 r14 = r8 + r1 ; 첨자 i * n + i 계산 0330 r15 = r14 * #8 ; 바이트 주소 계산 0350 fstore fr4, A[r15] 0360 0370 ; i++ 0380 r1 = r1 + #1 0390 br G0000 0400 } 0410 G0001: 이제 r1을 증가시키는 외부 루프 내에는 4개의 승수가 있다.0190에서 register r8 = r1*r2는 루프(0055)에 들어가기 전에 설정하고 루프 하단(0385)에서 r2만큼 증가시켜 강도를 낮출 수 있다.
r8*8 (0118에서) 값은 r8을 초기화하고 (0056) r8이 증가하면 (0386) 8*r2를 더하면 강도를 줄일 수 있다.
레지스터 r20은 0117의 루프를 통해 매번 불변/정수 r2가 증가되고 있다.증분 후 8을 곱하여 0119에 r22를 만든다.그 곱셈은 루프를 통해 매번 8*r2를 추가함으로써 힘을 줄일 수 있다.
0010 ;; for (i = 0, i < n; i++) 0020 { 0030 r1 = #0 ; i = 0 0050 짐을 싣다 r2, n 0220 fr3 = #0.0 0340 fr4 = #1.0 0055 r8 = r1 * r2 ; r8의 초기값 설정 0056 r40 = r8 * #8 ; r8 * 8의 초기 값 0057 r30 = r2 * #8 ; r40의 증분 0058 r20 = r8 + r2 ; 0117에서 복사됨 0058 r22 = r20 * #8 ; r22의 초기값 0040 G0000: 0060 cmp r1, r2 ; i < n 0070 큰 소리로 부르다 G0001 0080 0190 ; r8 = r1 * r2 제거됨; 첨자 i * n 계산 0117 ; r20 = r8 + r2 사용 안 함 - 데드 코드 0118 r10 = r40 ; 강도를 r40으로 줄였다. 0119 ; r22 = r20 * #8 죽임; 강도 감소 0090 ;; for (j = 0; j < n; j++) 0100 { 0120 G0002: 0147 cmp r10, r22 ; r10 = 8**(r8 + j) < 8*(r8 + n) = r22 0150 큰 소리로 부르다 G0003 0160 0170 ; A[i,j] = 0.0; 0230 fstore fr3, A[r10] 0240 0245 r10 = r10 + #8 ; 감소된 강도 곱하기 0260 br G0002 0270 } 0280 G0003: 0290 ; A[i,i] = 1.0; 0320 r14 = r8 + r1 ; 첨자 i * n + i 계산 0330 r15 = r14 * #8 ; 바이트 주소 계산 0350 fstore fr4, A[r15] 0360 0370 ; i++ 0380 r1 = r1 + #1 0385 r8 = r8 + r2 ; 강도 감소 r8 = r1 * r2 0386 r40 = r40 + r30 ; 강도 감소 표현 r8 * 8 0388 r22 = r22 + r30 ; 강도 감소 r22 = r20 * 8 0390 br G0000 0400 } 0410 G0001: 마지막 곱하기
그러면 두 루프는 외부 루프 내에서 하나의 곱셈 연산(0330에서)만 남고 내부 루프 내에서는 곱셈이 없다.
0010 ;; for (i = 0, i < n; i++) 0020 { 0030 r1 = #0 ; i = 0 0050 짐을 싣다 r2, n 0220 fr3 = #0.0 0340 fr4 = #1.0 0055 r8 = r1 * r2 ; r8의 초기값 설정 0056 r40 = r8 * #8 ; r8 * 8의 초기 값 0057 r30 = r2 * #8 ; r40의 증분 0058 r20 = r8 + r2 ; 0117에서 복사됨 0058 r22 = r20 * #8 ; r22의 초기값 0040 G0000: 0060 cmp r1, r2 ; i < n 0070 큰 소리로 부르다 G0001 0080 0118 r10 = r40 ; 강도를 r40으로 줄였다. 0090 ;; for (j = 0; j < n; j++) 0100 { 0120 G0002: 0147 cmp r10, r22 ; r10 = 8**(r8 + j) < 8*(r8 + n) = r22 0150 큰 소리로 부르다 G0003 0160 0170 ; A[i,j] = 0.0; 0230 fstore fr3, A[r10] 0240 0245 r10 = r10 + #8 ; 감소된 강도 곱하기 0260 br G0002 0270 } 0280 G0003: 0290 ; A[i,i] = 1.0; 0320 r14 = r8 + r1 ; 첨자 i * n + i 계산 0330 r15 = r14 * #8 ; 바이트 주소 계산 0350 fstore fr4, A[r15] 0360 0370 ; i++ 0380 r1 = r1 + #1 0385 r8 = r8 + r2 ; 강도 감소 r8 = r1 * r2 0386 r40 = r40 + r30 ; 강도 감소 표현 r8 * 8 0388 r22 = r22 + r30 ; 강도 감소 r22 = r20 * 8 0390 br G0000 0400 } 0410 G0001: 라인 0320에서 r14는 r8과 r1의 합이며, r8과 r1은 루프에서 증가되고 있다.register 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 짐을 싣다 r2, n 0220 fr3 = #0.0 0340 fr4 = #1.0 0055 r8 = r1 * r2 ; r8의 초기값 설정 0056 r40 = r8 * #8 ; r8 * 8의 초기 값 0057 r30 = r2 * #8 ; r40의 증분 0058 r20 = r8 + r2 ; 0117에서 복사됨 0058 r22 = r20 * #8 ; r22의 초기값 005A r14 = r8 + r1 ; 0320에서 복사됨 005B r15 = r14 * #8 ; r15의 초기값(0330) 005C r49 = r2 + #1 005D r50 = r49 * #8 ; 강도 증가 감소 0040 G0000: 0060 cmp r1, r2 ; i < n 0070 큰 소리로 부르다 G0001 0080 0118 r10 = r40 ; 강도를 r40으로 줄였다. 0090 ;; for (j = 0; j < n; j++) 0100 { 0120 G0002: 0147 cmp r10, r22 ; r10 = 8**(r8 + j) < 8*(r8 + n) = r22 0150 큰 소리로 부르다 G0003 0160 0170 ; A[i,j] = 0.0; 0230 fstore fr3, A[r10] 0240 0245 r10 = r10 + #8 ; 감소된 강도 곱하기 0260 br G0002 0270 } 0280 G0003: 0290 ; A[i,i] = 1.0; 0320 ; r14 = r8 + r1 죽임; 데드 코드 0330 ; r15 = r14 * #8 죽임; 강도 감소 0350 fstore fr4, A[r15] 0360 0370 ; i++ 0380 r1 = r1 + #1 0385 r8 = r8 + r2 ; 강도 감소 r8 = r1 * r2 0386 r40 = r40 + r30 ; 강도 감소 표현 r8 * 8 0388 r22 = r22 + r30 ; 강도 감소 r22 = r20 * 8 0389 r15 = r15 + r50 ; 강도 감소 r15 = r14 * 8 0390 br G0000 0400 } 0410 G0001: 아직 가야 할 게 더 있다.계속 접으면 서문에서 r1=0이 인식되므로 여러 지침이 정리된다.register r8은 루프에서 사용되지 않으므로 사라질 수 있다.
더욱이 r1은 루프 제어에만 사용되고 있으므로 r1은 r40과 같은 다른 유도 변수로 대체될 수 있다.여기서 나는 0 <= i < n>, register r40은 0 <= r40 < 8 * n * n>으로 간다.
0010 ;; for (i = 0, i < n; i++) 0020 { 0030 ; r1 = #0; i = 0, 데드 코드가 됨 0050 짐을 싣다 r2, n 0220 fr3 = #0.0 0340 fr4 = #1.0 0055 ; r8 = #0 사망, r8 더 이상 사용되지 않음 0056 r40 = #0 ; r8 * 8의 초기 값 0057 r30 = r2 * #8 ; r40의 증분 0058 ; r20 = r2 제거됨, r8 = 0, 데드 코드가 됨 0058 r22 = r2 * #8 ; r20 = r2 005A ; r14 = #0 소멸, r8 = 0, 데드 코드가 됨 005B r15 = #0 ; r14 = 0 005C r49 = r2 + #1 005D r50 = r49 * #8 ; 강도 증가 감소 005D r60 = r2 * r30 ; r40의 새로운 한계 0040 G0000: 0060 ; cmp r1, r2 제거; i < n; 유도 변수 교체 0065 cmp r40, r60 ; i * 8 * n < 8 * n * n 0070 큰 소리로 부르다 G0001 0080 0118 r10 = r40 ; 강도를 r40으로 줄였다. 0090 ;; for (j = 0; j < n; j++) 0100 { 0120 G0002: 0147 cmp r10, r22 ; r10 = 8**(r8 + j) < 8*(r8 + n) = r22 0150 큰 소리로 부르다 G0003 0160 0170 ; A[i,j] = 0.0; 0230 fstore fr3, A[r10] 0240 0245 r10 = r10 + #8 ; 감소된 강도 곱하기 0260 br G0002 0270 } 0280 G0003: 0290 ; A[i,i] = 1.0; 0350 fstore fr4, A[r15] 0360 0370 ; i++ 0380 ; r1 = r1 + #1 죽임; 데드 코드(r40 컨트롤 루프) 0385 ; r8 = r8 + r2 죽임; 데드 코드 0386 r40 = r40 + r30 ; 강도 감소 표현 r8 * 8 0388 r22 = r22 + r30 ; 강도 감소 r22 = r20 * 8 0389 r15 = r15 + r50 ; 강도 감소 r15 = r14 * 8 0390 br G0000 0400 } 0410 G0001: 기타 강도 감소 작업
연산자 강도 감소는 느린 수학 연산을 더 빠른 연산으로 대체하기 위해 수학적 정체성을 사용한다.이점은 대상 CPU와 주변 코드(CPU 내의 다른 기능 단위의 가용성에 영향을 줄 수 있음)에 따라 달라진다.
- 정수 분할 또는 곱셈을 2의 검정력으로 산술 시프트 또는 논리 시프트로[2] 대체
- 이동, 추가 또는 빼기의 조합으로 정수 곱셈을 상수로 대체
- 기계 정수의 제한된 범위를 이용하여 정수 분할을 곱으로 대체한다.[3]이 방법은 divisor가 1보다 충분히 큰 비정수자인 경우에도 효과가 있다(예: √2 또는 π).[4]
| 원계산 | 대체계산 |
|---|---|
| y = x / 8 | y = x >> 3 |
| y = x * 64 | y = x << 6 |
| y = x * 2 | y = x << 1 |
| y = x * 15 | y = (x << 4) - x |
| y = x / 10(여기서 x는 uint16_t 유형) | y = (uint32_t)x * (uint32_t)0xCCCD >> 19) |
| y = x / π (여기서 x는 uint16_t 유형) | y = ((uint32_t)x *(uint32_t)0x45F3) > 16) + x) > 2) |
유도 변수(모르판)
유도 변수 또는 재귀 강도 감소는 일부 체계적으로 변화하는 변수의 함수를 함수의 이전 값을 사용한 단순한 계산으로 대체한다.절차적 프로그래밍 언어에서 이것은 루프 변수를 포함하는 표현식에 적용되며 선언적 언어에서는 재귀 함수의 인수에 적용된다.예를 들어,
f x = ... (3 ** x) ... (f (x + 1)) ... 된다
f x = f' x 1 어디에 f' x z = ... z ... (f' (x + 1) (3 * z)) ... 여기서 수정된 재귀함수 f′은 두 번째 매개변수 z = 3 ** x를 취하여 값비싼 연산(3 ** x)을 값싼 값(3 * z)으로 대체할 수 있다.
참고 항목
메모들
- ^ Steven Muchnick; Muchnick and Associates (15 August 1997). Advanced Compiler Design Implementation. Morgan Kaufmann. ISBN 978-1-55860-320-2.
Strength reduction.
- ^ C와 자바와 같은 언어에서 정수분할은 원토워즈 제로 의미론(stround-towards-zero semantic)을 가지고 있는 반면 비트시프트는 항상 반올림하여 음수에 대한 특별 처리가 필요하다.예를 들어, 자바에서는
-3 / 2로 평가하다.-1, 반면에-3 >> 1로 평가하다.-2따라서 이 경우 컴파일러는 분할을 비트 시프트로 대체하여 분할을 2로 최적화할 수 없다. - ^ Granlund, Torbjörn; Peter L. Montgomery. "Division by Invariant Integers Using Multiplication" (PDF).
- ^ Jones, Nigel. "Division of integers by constants".
참조
- Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986), Compilers: Principles, Techniques, and Tools (2nd ed.), ISBN 978-0-201-10088-4
- Allen, Francis E.; Cocke, John; Kennedy, Ken (1981), "Reduction of Operator Strength", in Munchnik, Steven S.; Jones, Neil D. (eds.), Program Flow Analysis: Theory and Applications, Prentice-Hall, ISBN 978-0-13-729681-1
- Cocke, John; Kennedy, Ken (November 1977), "An algorithm for reduction of operator strength", Communications of the ACM, 20 (11): 850–856, doi:10.1145/359863.359888, S2CID 1092505
- Cooper, Keith; Simpson, Taylor; Vick, Christopher (October 1995), Operator Strength Reduction (PDF), Rice University, retrieved April 22, 2010
