Tại sao GCC lại sử dụng phép nhân với một số lạ trong việc thực hiện phép chia số nguyên?

Tôi đã đọc về divvà mulcác phép toán lắp ráp, và tôi quyết định xem chúng hoạt động bằng cách viết một chương trình đơn giản trong C:

Tệp phân chia.c

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

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

Và sau đó tạo mã hợp ngữ với:

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

Nhưng nhìn vào division.stệp được tạo , nó không chứa bất kỳ phép toán div nào! Thay vào đó, nó thực hiện một số loại ma thuật đen với dịch chuyển bit và số ma thuật. Đây là một đoạn mã tính toán 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

Những gì đang xảy ra ở đây? Tại sao GCC không sử dụng div? Làm thế nào nó tạo ra con số kỳ diệu này và tại sao mọi thứ hoạt động?

Phép chia số nguyên là một trong những phép toán số học chậm nhất mà bạn có thể thực hiện trên bộ xử lý hiện đại, với độ trễ lên đến hàng chục chu kỳ và thông lượng kém. (Đối với x86, hãy xem bảng hướng dẫn của Agner Fog và hướng dẫn về vi tinh bột ).

Nếu bạn biết trước số chia, bạn có thể tránh phép chia bằng cách thay thế nó bằng một tập hợp các phép toán khác (nhân, cộng và dịch) có hiệu quả tương đương. Ngay cả khi cần một số phép toán, nó thường vẫn nhanh hơn rất nhiều so với phép chia số nguyên.

Thực hiện /toán tử C theo cách này thay vì với một chuỗi nhiều lệnh liên quan đến divchỉ là cách mặc định của GCC để thực hiện phép chia cho các hằng số. Nó không yêu cầu tối ưu hóa giữa các hoạt động và không thay đổi bất kỳ điều gì ngay cả khi gỡ lỗi. (Tuy nhiên, việc sử dụng -Oscho kích thước mã nhỏ sẽ khiến GCC sử dụng div.) Sử dụng phép nghịch đảo nhân thay vì phép chia giống như sử dụng leathay vì mulvàadd

Kết quả là, bạn chỉ có xu hướng nhìn thấy divhoặc idivtrong đầu ra nếu số chia không được biết tại thời điểm biên dịch.

Để biết thông tin về cách trình biên dịch tạo ra các trình tự này, cũng như mã để cho phép bạn tạo chúng cho chính mình (hầu như chắc chắn là không cần thiết trừ khi bạn đang làm việc với trình biên dịch braindead), hãy xem libdivide .

Chia cho 5 giống như nhân 1/5, một lần nữa giống như nhân với 4/5 và dịch sang phải 2 bit. Giá trị liên quan CCCCCCCCCCCCCCCDở dạng hex, là biểu diễn nhị phân của 4/5 nếu được đặt sau dấu thập lục phân (tức là hệ nhị phân cho bốn phần năm được 0.110011001100lặp lại - xem bên dưới để biết lý do). Tôi nghĩ bạn có thể lấy nó từ đây! Bạn có thể muốn kiểm tra số học điểm cố định (mặc dù lưu ý rằng nó được làm tròn thành số nguyên ở cuối.

Vì sao, phép nhân nhanh hơn phép chia, và khi số chia được cố định, đây là một con đường nhanh hơn.

Xem Phép nhân đối ứng, một hướng dẫn để biết chi tiết về cách hoạt động của nó, giải thích về điểm cố định. Nó chỉ ra cách thức hoạt động của thuật toán tìm đối ứng và cách xử lý phép chia và mô đun có dấu.

Hãy xem xét trong một phút tại sao 0.CCCCCCCC...(hex) hoặc 0.110011001100...nhị phân là 4/5. Chia biểu diễn nhị phân cho 4 (dịch chuyển sang phải 2 vị trí) và chúng ta sẽ nhận được 0.001100110011...bằng cách kiểm tra nhỏ có thể được thêm vào bản gốc để lấy 0.111111111111..., rõ ràng là bằng 1, theo cùng một cách 0.9999999...trong thập phân bằng một. Do đó, chúng ta biết rằng x + x/4 = 1, vì vậy 5x/4 = 1, x=4/5. Sau đó, giá trị này được biểu diễn dưới dạng CCCCCCCCCCCCDhex để làm tròn (vì chữ số nhị phân nằm ngoài chữ số cuối cùng hiện tại sẽ là a 1).

Nói chung, phép nhân nhanh hơn nhiều so với phép chia. Vì vậy, nếu chúng ta có thể loại bỏ việc nhân với nghịch đảo thay vào đó chúng ta có thể tăng tốc đáng kể phép chia cho một hằng số

Một điểm khó khăn là chúng ta không thể biểu diễn nghịch đảo chính xác (trừ khi phép chia là lũy thừa của hai nhưng trong trường hợp đó, chúng ta thường có thể chuyển phép chia thành một bit shift). Vì vậy, để đảm bảo câu trả lời chính xác, chúng tôi phải cẩn thận để lỗi trong đối ứng của chúng tôi không gây ra sai sót trong kết quả cuối cùng của chúng tôi.

-3689348814741910323 là 0xCCCCCCCCCCCCCCCD, là giá trị chỉ hơn 4/5 được biểu thị bằng 0,64 điểm cố định.

Khi chúng ta nhân một số nguyên 64 bit với một số điểm cố định 0,64, chúng ta nhận được kết quả 64,64. Chúng tôi cắt bớt giá trị thành số nguyên 64 bit (làm tròn giá trị về 0 một cách hiệu quả) và sau đó thực hiện một phép dịch chuyển nữa chia cho bốn và một lần nữa cắt bớt.

Điều này rõ ràng cung cấp cho chúng ta ít nhất một phép chia gần đúng cho 5 nhưng nó có cung cấp cho chúng ta một câu trả lời chính xác được làm tròn chính xác đến 0 không?

Để có được câu trả lời chính xác, lỗi cần phải đủ nhỏ để không đẩy câu trả lời qua một ranh giới làm tròn.

Câu trả lời chính xác cho phép chia cho 5 sẽ luôn có phần phân số là 0, 1/5, 2/5, 3/5 hoặc 4/5. Do đó, sai số dương nhỏ hơn 1/5 trong kết quả được nhân và dịch chuyển sẽ không bao giờ đẩy kết quả vượt qua ranh giới làm tròn.

Sai số trong hằng số của chúng tôi là (1/5) * 2 ^-64 . Giá trị của i nhỏ hơn 2 ⁶⁴ nên sai số sau khi nhân nhỏ hơn 1/5. Sau khi chia cho 4, sai số nhỏ hơn (1/5) * 2 ⁻² .

(1/5) * 2 ⁻² <1/5 nên câu trả lời sẽ luôn bằng khi thực hiện một phép chia chính xác và làm tròn về 0.

Thật không may, điều này không hoạt động cho tất cả các ước số.

Nếu chúng ta cố gắng biểu diễn 4/7 dưới dạng một số điểm cố định 0,64 với việc làm tròn đi từ 0, chúng ta sẽ có sai số là (6/7) * 2 ^-64 . Sau khi nhân với giá trị i của chỉ dưới 2 ^64, chúng ta kết thúc với sai số chỉ dưới 6/7 và sau khi chia cho bốn, chúng ta kết thúc với sai số chỉ dưới 1.5 / 7 lớn hơn 1/7.

Vì vậy, để thực hiện đúng số chia cho 7, chúng ta cần nhân với một số điểm cố định 0,65. Chúng tôi có thể thực hiện điều đó bằng cách nhân với 64 bit thấp hơn của số điểm cố định của chúng tôi, sau đó thêm số gốc (điều này có thể tràn vào bit mang) sau đó thực hiện xoay vòng qua mang.

Đây là liên kết đến tài liệu của một thuật toán tạo ra các giá trị và mã mà tôi thấy với Visual Studio (trong hầu hết các trường hợp) và tôi giả sử vẫn được sử dụng trong GCC để chia một số nguyên biến cho một số nguyên không đổi.

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

Trong bài viết, một uword có N bit, một udword có 2N bit, n = tử số = cổ tức, d = mẫu số = số chia, ℓ ban đầu được đặt thành ceil (log2 (d)), shpre là chuyển dịch trước (được sử dụng trước khi nhân ) = e = số bit không theo sau trong d, shpost là dịch chuyển sau (được sử dụng sau khi nhân), prep là độ chính xác = N - e = N - shpre. Mục đích là để tối ưu hóa việc tính toán n / d bằng cách sử dụng dịch chuyển trước, nhân và sau.

Cuộn xuống hình 6.2, xác định cách tạo ra một hệ số udword (kích thước tối đa là N + 1 bit), nhưng không giải thích rõ ràng quá trình này. Tôi sẽ giải thích điều này dưới đây.

Hình 4.2 và hình 6.2 cho thấy cách hệ số nhân có thể được giảm xuống một N bit hoặc hệ số nhân nhỏ hơn đối với hầu hết các ước số. Phương trình 4.5 giải thích cách công thức được sử dụng để xử lý số nhân N + 1 bit trong hình 4.1 và 4.2.

Trong trường hợp của X86 hiện đại và các bộ xử lý khác, thời gian nhân là cố định, vì vậy dịch chuyển trước không giúp ích gì cho các bộ xử lý này, nhưng nó vẫn giúp giảm hệ số nhân từ N + 1 bit xuống N bit. Tôi không biết liệu GCC hoặc Visual Studio có loại bỏ tính năng chuyển trước cho các mục tiêu X86 hay không.

Quay lại Hình 6.2. Tử số (số bị chia) cho mlow và mhigh chỉ có thể lớn hơn một ô chữ khi mẫu số (số chia)> 2 ^ (N-1) (khi ℓ == N => mlow = 2 ^ (2N)), trong trường hợp này thay thế tối ưu cho n / d là một phép so sánh (nếu n> = d, q = 1, khác q = 0), do đó không có hệ số nhân nào được tạo ra. Các giá trị ban đầu của mlow và mhigh sẽ là N + 1 bit và hai phép chia udword / uword có thể được sử dụng để tạo ra mỗi giá trị N + 1 bit (mlow hoặc mhigh). Sử dụng X86 ở chế độ 64 bit làm ví dụ:

; 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

Bạn có thể kiểm tra điều này với GCC. Bạn đã thấy cách j = i / 5 được xử lý. Hãy xem cách xử lý j = i / 7 (phải là trường hợp nhân N + 1 bit).

Trên hầu hết các bộ vi xử lý hiện tại, nhân có thời gian cố định, do đó không cần chuyển trước. Đối với X86, kết quả cuối cùng là một chuỗi hai lệnh cho hầu hết các ước số và một chuỗi năm lệnh cho các ước số như 7 (để mô phỏng hệ số nhân N + 1 bit như thể hiện trong phương trình 4.5 và hình 4.2 của tệp pdf). Ví dụ mã 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
;       ...

Tôi sẽ trả lời ở một góc độ hơi khác: Vì nó được phép làm điều đó.

C và C ++ được định nghĩa dựa trên một máy trừu tượng. Trình biên dịch chuyển đổi chương trình này dưới dạng máy trừu tượng thành máy cụ thể theo quy tắc as-if .

• Trình biên dịch được phép thực hiện BẤT KỲ thay đổi nào miễn là nó không thay đổi hành vi có thể quan sát được như được chỉ định bởi máy trừu tượng. Không có kỳ vọng hợp lý nào rằng trình biên dịch sẽ chuyển đổi mã của bạn theo cách đơn giản nhất có thể (ngay cả khi nhiều lập trình viên C giả định như vậy). Thông thường, nó thực hiện điều này vì trình biên dịch muốn tối ưu hóa hiệu suất so với cách tiếp cận đơn giản (như đã thảo luận trong các câu trả lời khác ở độ dài).
• Nếu trong bất kỳ trường hợp nào mà trình biên dịch "tối ưu hóa" một chương trình đúng thành một chương trình nào đó có hành vi quan sát khác, thì đó là lỗi trình biên dịch.
• Bất kỳ hành vi không xác định nào trong mã của chúng tôi (tràn số nguyên đã ký là một ví dụ cổ điển) và hợp đồng này vô hiệu.