[c] 정수 나누기를 구현할 때 GCC가 왜 이상한 수의 곱셈을 사용합니까?

다음은 Visual Studio에서 볼 수있는 값과 코드를 생성하는 알고리즘 문서에 대한 링크입니다 (대부분의 경우). 변수 정수를 상수 정수로 나누기 위해 GCC에서 여전히 사용된다고 가정합니다.

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

이 기사에서 uword에는 N 비트가 있고 udword에는 2N 비트가 있으며 n = 분자 = 피제수, d = 분모 = 제수, ℓ는 처음에 ceil (log2 (d))로 설정되고 shpre는 사전 이동 (곱하기 전에 사용됨) ) = e = d의 후행 0 비트 수, shpost는 이동 후 (곱셈 후 사용), prec는 정밀도 = N-e = N-shpre입니다. 목표는 프리 시프트, 곱셈 및 포스트 시프트를 사용하여 n / d 계산을 최적화하는 것입니다.

udword multiplier (최대 크기는 N + 1 비트)가 생성되는 방법을 정의하는 그림 6.2까지 아래로 스크롤하지만 프로세스를 명확하게 설명하지는 않습니다. 이것을 아래에서 설명하겠습니다.

그림 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에 대한 분자 (배당)는 분모 (제수)> 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 개의 명령어 시퀀스입니다 (pdf 파일의 식 4.5 및 그림 4.2에 표시된대로 N + 1 비트 승수를 에뮬레이션하기 위해). 예제 X86-64 코드 :

;       rax = dividend, rbx = 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
;       ...

답변