왜 GCC는 정수 나눗셈을 실장할 때 홀수 곱셈을 사용하는가?

왜 GCC는 정수 나눗셈을 실장할 때 홀수 곱셈을 사용하는가?

에 대해 읽은 적이 있습니다.div그리고.mul조립 작업, 그리고 C:에 간단한 프로그램을 작성함으로써 조립 작업의 실제 모습을 확인하기로 했습니다.

파일 분할.c

#include <stdlib.h>
#include <stdio.h>

int main()
{
    size_t i = 9;
    size_t j = i / 5;
    printf("%zu\n",j);
    return 0;
}

다음으로 어셈블리 언어 코드 생성:

gcc -S division.c -O0 -masm=intel

하지만 생성된 것을 보면division.s파일에는 div 연산이 포함되어 있지 않습니다!대신 비트 시프트와 매직 넘버로 블랙 마법을 부립니다.여기 코드 조각이 있습니다.i/5:

mov     rax, QWORD PTR [rbp-16]   ; Move i (=9) to RAX
movabs  rdx, -3689348814741910323 ; Move some magic number to RDX (?)
mul     rdx                       ; Multiply 9 by magic number
mov     rax, rdx                  ; Take only the upper 64 bits of the result
shr     rax, 2                    ; Shift these bits 2 places to the right (?)
mov     QWORD PTR [rbp-8], rax    ; Magically, RAX contains 9/5=1 now, 
                                  ; so we can assign it to j

이게 무슨 일이야?왜 GCC는 div를 전혀 사용하지 않는 거죠?이 매직 넘버는 어떻게 생성되며 왜 모든 것이 작동합니까?

5로 나누는 것은 1/5를 곱하는 것과 같으며, 이는 4/5를 곱하고 2비트를 오른쪽으로 옮기는 것과 같습니다.관련된 가치는CCCCCCCCCCCCCCCD16진수점 뒤에 4/5를 대입하는 경우 4/5의 이진수 표현이다(즉, 4/5에 대한 이진수는0.110011001100recurring - 이유는 아래를 참조하십시오).여기서부턴 네가 맡을 수 있을 것 같아!고정점 산술은 체크 아웃할 수 있습니다(마지막에는 정수로 반올림됩니다).

그 이유는 나눗셈보다 곱셈이 빠르고, 제수가 고정되면 이것이 더 빠른 경로입니다.

고정 소수점 단위로 설명하는 방법에 대한 자세한 내용은 상호 곱셈 튜토리얼을 참조하십시오.역수를 찾는 알고리즘이 어떻게 작동하는지, 그리고 부호화된 나눗셈과 모듈로를 처리하는 방법을 보여줍니다.

그 이유를 잠시 생각해 봅시다.0.CCCCCCCC...(표준) 또는0.110011001100...바이너리는 4/5 입니다.2진수 표현을 4(오른쪽 2자리)로 나누면 다음과 같이 됩니다.0.001100110011...간단한 검사를 통해 원본을 추가하여 얻을 수 있습니다.0.111111111111...이것은 분명히 1과 같은 방법입니다.0.9999999...10진수는 1과 같다.따라서 우리는 그것을 알고 있다.x + x/4 = 1,그렇게5x/4 = 1,x=4/5이것은 다음과 같이 표현됩니다.CCCCCCCCCCCCD반올림을 위한 16진수(마지막 1자리 이후의 2진수 자리수로서)1).

정수 나눗셈은 최신 프로세서에서 실행할 수 있는 가장 느린 산술 연산 중 하나이며, 최대 수십 사이클의 레이텐시와 불량 스루풋이 있습니다(x86에 대해서는 Agner Fog의 명령표와 마이크로아치 가이드를 참조하십시오).

미리 제수를 알고 있는 경우에는 동일한 효과가 있는 다른 연산 집합(승법, 덧셈 및 교대조)으로 바꾸면 나눗셈을 피할 수 있습니다.몇 가지 연산이 필요하더라도 정수 나눗셈 자체보다 훨씬 더 빠른 경우가 많습니다.

C의 실장/를 포함한 다중 명령 시퀀스를 사용하는 대신 이 방법으로 연산한다.divGCC가 상수로 나누는 기본 방법일 뿐입니다.운영 전반에 걸쳐 최적화할 필요가 없으며 디버깅 시에도 아무것도 변경되지 않습니다. (사용 시)-Os코드 사이즈가 작을 경우 GCC가 사용할 수 있습니다.div단,).나눗셈 대신 곱셈 역수를 사용하는 것은 다음을 사용하는 것과 같다.lea대신mul그리고.add

그 결과, 당신은 단지 볼 수 있을 뿐이다.div또는idiv컴파일 시 제수가 불분명한 경우 출력에 표시됩니다.

컴파일러가 이러한 시퀀스를 생성하는 방법 및 사용자가 직접 생성할 수 있는 코드(뇌사 컴파일러를 사용하지 않는 한 거의 불필요함)에 대해서는 libdivide를 참조하십시오.

일반적으로 곱셈은 나눗셈보다 훨씬 빠르다.그래서 만약 우리가 역수를 곱하는 것에서 벗어날 수 있다면 우리는 나눗셈을 상수로 크게 가속할 수 있다.

주름은 정확하게 역수를 나타낼 수 없다는 것입니다(나눗셈이 2의 거듭제곱에 의한 것이 아니라면 보통 나눗셈을 비트 시프트로 변환할 수 있습니다).따라서 정답을 확인하기 위해 우리는 상호의 오류로 인해 최종 결과에 오류가 발생하지 않도록 주의해야 합니다.

-3689348814741910323은 0xCCCCCCCCD로, 0.64 고정점에서는 4/5를 조금 넘는 값입니다.

64비트 정수에 0.64 고정 소수점 수를 곱하면 64.64 결과가 됩니다.값을 64비트 정수로 잘라내고(효과적으로 0을 향해 반올림) 다음 4로 나눈 다음 다시 잘라내는 추가 시프트를 수행합니다.비트 레벨을 보면 두 절단을 모두 단일 절단으로 취급할 수 있습니다.

이것은 적어도 5로 나누기 근사치를 제공하지만, 0을 향해 정확하게 반올림한 정확한 답을 제공합니까?

정확한 답을 얻으려면 오차가 반올림 경계 밖으로 정답을 밀어내지 않을 정도로 작아야 합니다.

5로 나눗셈에 대한 정확한 답은 항상 0, 1/5, 2/5, 3/5, 또는 4/5의 소수 부분을 가집니다. 따라서 곱셈 및 시프트 결과에서 1/5 미만의 양의 오차는 결과를 반올림 경계 밖으로 밀어넣지 않습니다.

상수의 오차는 (1/5) * 2입니다^-64. i의 값이 2보다⁶⁴ 작기 때문에 곱한 후의 오차는 1/5보다 작습니다.4로 나누면 오차는 (1/5) * 2보다⁻² 작아집니다.

(1/5) * 2⁻² < 1/5이므로 정답은 항상 정확한 나눗셈과 0을 향해 반올림하는 것과 같습니다.

---

불행하게도 이것은 모든 제수에게 효과가 있는 것은 아니다.

4/7을 0에서 반올림한 0.64 고정 소수점 수로 나타내려고 하면 (6/7) * 2의^-64 오차가 발생합니다.i 값에 2를⁶⁴ 곱하면 6/7을 조금 밑돌고 4로 나누면 1.5/7보다 큰 오차가 발생합니다.

따라서 7을 올바르게 구현하려면 0.65 고정 소수점을 곱해야 합니다.고정점 번호의 하위 64비트에 곱한 다음 원래 숫자(이것은 캐리 비트로 오버플로될 수 있음)를 추가한 다음 회전 통과를 수행하면 구현할 수 있습니다.

Visual Studio에서 볼 수 있는 값 및 코드를 생성하는 알고리즘 문서에 대한 링크입니다(대부분의 경우). GCC에서 변수 정수를 상수 정수로 분할하는 데 여전히 사용되는 것으로 가정합니다.

http://gmplib.org/~tege/divcnst-pldi94.pdf

이 글에서 uword는 N비트를 가지며, udword는 2N비트를 가지며, n = 분자 = 배당, d = 분모 = 제수, θ는 처음에 seil(log2(d)로 설정되며, shpre는 프리시프트(곱셈 전에 사용) = d의 후행 제로비트 수, shpost는 프리시프트(곱셈 정밀도 n 후에 사용)로 설정된다.목표는 사전 이동, 곱셈 및 사후 이동을 사용하여 n/d 계산을 최적화하는 것입니다.

그림 6.2까지 스크롤 다운합니다.이 그림에서는 udword multiplier(최대 사이즈는 N+1비트)가 생성되는 방법을 정의하고 있습니다만, 프로세스에 대해서는 명확하게 설명하지 않습니다.이하에 설명하겠습니다.

그림 4.2와 그림 6.2는 대부분의 제수에서 승수를 N비트 이하로 줄이는 방법을 보여줍니다.식 4.5는 그림 4.1과 4.2의 N+1 비트 승수를 처리하는 데 사용되는 공식을 어떻게 도출했는지 설명합니다.

최신 X86 및 기타 프로세서의 경우 곱셈 시간은 고정되어 있기 때문에 이러한 프로세서에서는 프리시프트가 도움이 되지 않지만 곱셈기를 N+1비트에서N비트로 줄일 수 있습니다.GCC나 Visual Studio가 X86 타겟의 프리시프트를 없앴는지 모르겠습니다.

그림 6.2로 되돌아가다mlow 및 mhigh의 분자(소수)는 분모(divisor) > 2^(N-1)(θ == N > mlow = 2^(2N)인 경우에만 udword보다 클 수 있으며, 이 경우 n/d에 대한 최적화된 치환은 비교입니다(n > d, q = 1, q = 0).mlow 및 mhigh의 초기값은 N+1비트이며, 2개의 udword/uword 분할을 사용하여 각 N+1비트 값(mlow 또는 mhigh)을 생성할 수 있습니다.64비트 모드의 X86을 예로 들어 보겠습니다.

; upper 8 bytes of dividend = 2^(ℓ) = (upper part of 2^(N+ℓ))
; lower 8 bytes of dividend for mlow  = 0
; lower 8 bytes of dividend for mhigh = 2^(N+ℓ-prec) = 2^(ℓ+shpre) = 2^(ℓ+e)
dividend  dq    2 dup(?)        ;16 byte dividend
divisor   dq    1 dup(?)        ; 8 byte divisor

; ...
        mov     rcx,divisor
        mov     rdx,0
        mov     rax,dividend+8     ;upper 8 bytes of dividend
        div     rcx                ;after div, rax == 1
        mov     rax,dividend       ;lower 8 bytes of dividend
        div     rcx
        mov     rdx,1              ;rdx:rax = N+1 bit value = 65 bit value

이것은 GCC를 사용하여 테스트할 수 있습니다.j = i/5가 어떻게 처리되는지 이미 확인했습니다.j = i/7의 처리 방식을 살펴봅니다(N+1 비트 승수의 경우).

대부분의 현재 프로세서에서는 곱셈에는 타이밍이 정해져 있기 때문에 프리시프트는 필요 없습니다.X86의 경우, 최종 결과는 대부분의 제수에 대해 2개의 명령 시퀀스와 7과 같은 제수에 대해 5개의 명령 시퀀스가 됩니다(식 4.5 및 pdf 파일의 그림 4.2와 같이 N+1 비트 승수를 에뮬레이트하기 위해).X86-64 코드의 예:

;       rbx = dividend, rax = 64 bit (or less) multiplier, rcx = post shift count
;       two instruction sequence for most divisors:

        mul     rbx                     ;rdx = upper 64 bits of product
        shr     rdx,cl                  ;rdx = quotient
;
;       five instruction sequence for divisors like 7
;       to emulate 65 bit multiplier (rbx = lower 64 bits of multiplier)

        mul     rbx                     ;rdx = upper 64 bits of product
        sub     rbx,rdx                 ;rbx -= rdx
        shr     rbx,1                   ;rbx >>= 1
        add     rdx,rbx                 ;rdx = upper 64 bits of corrected product
        shr     rdx,cl                  ;rdx = quotient
;       ...

---

5개의 명령 시퀀스를 설명하자면, 단순한 3개의 명령 시퀀스가 오버플로할 수 있습니다.u64()는 상위 64비트(지분에 필요한 모든 것)를 의미합니다.

        mul     rbx                     ;rdx = u64(dvnd*mplr)
        add     rdx,rbx                 ;rdx = u64(dvnd*(2^64 + mplr)), could overflow
        shr     rdx,cl

이 경우 cl = post_shift-1. rax = 승수 - 2^64, rbx = 배당. u64()는 상위 64비트입니다.rax = rax<1 - rax라는 점에 유의하십시오.비율:

        u64( (  rbx * (2^64 + rax) )>>(cl+1) )
        u64( (  rbx * (2^64 + rax<<1 - rax) )>>(cl+1) )
        u64( (  (rbx * 2^64) + (rbx * rax)<<1 - (rbx * rax) )>>(cl+1) )
        u64( (  (rbx * 2^64) - (rbx * rax) + (rbx * rax)<<1 )>>(cl+1) )
        u64( ( ((rbx * 2^64) - (rbx * rax))>>1) + (rbx*rax) )>>(cl  ) )

        mul     rbx                     ;   (rbx*rax)
        sub     rbx,rdx                 ;   (rbx*2^64)-(rbx*rax)
        shr     rbx,1                   ;(  (rbx*2^64)-(rbx*rax))>>1
        add     rdx,rbx                 ;( ((rbx*2^64)-(rbx*rax))>>1)+(rbx*rax)
        shr     rdx,cl                  ;((((rbx*2^64)-(rbx*rax))>>1)+(rbx*rax))>>cl

조금 다른 각도로 대답하겠습니다.왜냐하면 그것은 그것을 할 수 있기 때문이다.

C와 C++는 추상 머신에 대해 정의됩니다.컴파일러는 추상 머신이라는 관점에서 이 프로그램을 as-if 규칙에 따라 구체적인 머신으로 변환합니다.

• 컴파일러는 추상 머신에 의해 지정된 대로 관찰 가능한 동작을 변경하지 않는 한 모든 변경을 할 수 있습니다.컴파일러가 가능한 한 가장 간단한 방법으로 코드를 변환한다는 합리적인 기대는 없습니다(많은 C 프로그래머가 그렇게 가정하고 있는 경우에도 마찬가지입니다.보통 컴파일러가 (다른 답변에서 자세히 설명하듯이) 간단한 접근법에 비해 성능을 최적화하고 싶어하기 때문입니다.
• 어떤 상황에서도 컴파일러가 다른 관찰 가능한 동작을 가진 무언가에 대해 올바른 프로그램을 "최적화"하는 경우, 그것은 컴파일러 버그입니다.
• 코드 내에서 정의되지 않은 동작(서명된 정수 오버플로는 고전적인 예)은 모두 무효입니다.

언급URL : https://stackoverflow.com/questions/41183935/why-does-gcc-use-multiplication-by-a-strange-number-in-implementing-integer-divi