Saat menulis ftolfungsi yang dioptimalkan saya menemukan beberapa perilaku yang sangat aneh di GCC 4.6.1. Biarkan saya tunjukkan kode terlebih dahulu (untuk kejelasan saya menandai perbedaannya):

fast_trunc_one, C:

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = mantissa << -exponent;                       /* diff */
    } else {
        r = mantissa >> exponent;                        /* diff */
    }

    return (r ^ -sign) + sign;                           /* diff */
}

fast_trunc_two, C:

int fast_trunc_two(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = (mantissa << -exponent) ^ -sign;             /* diff */
    } else {
        r = (mantissa >> exponent) ^ -sign;              /* diff */
    }

    return r + sign;                                     /* diff */
}

Tampak sama kan? GCC tidak setuju. Setelah dikompilasi dengan gcc -O3 -S -Wall -o test.s test.cini adalah output perakitan:

fast_trunc_one, dihasilkan:

_fast_trunc_one:
LFB0:
    .cfi_startproc
    movl    4(%esp), %eax
    movl    $150, %ecx
    movl    %eax, %edx
    andl    $8388607, %edx
    sarl    $23, %eax
    orl $8388608, %edx
    andl    $255, %eax
    subl    %eax, %ecx
    movl    %edx, %eax
    sarl    %cl, %eax
    testl   %ecx, %ecx
    js  L5
    rep
    ret
    .p2align 4,,7
L5:
    negl    %ecx
    movl    %edx, %eax
    sall    %cl, %eax
    ret
    .cfi_endproc

fast_trunc_two, dihasilkan:

_fast_trunc_two:
LFB1:
    .cfi_startproc
    pushl   %ebx
    .cfi_def_cfa_offset 8
    .cfi_offset 3, -8
    movl    8(%esp), %eax
    movl    $150, %ecx
    movl    %eax, %ebx
    movl    %eax, %edx
    sarl    $23, %ebx
    andl    $8388607, %edx
    andl    $255, %ebx
    orl $8388608, %edx
    andl    $-2147483648, %eax
    subl    %ebx, %ecx
    js  L9
    sarl    %cl, %edx
    movl    %eax, %ecx
    negl    %ecx
    xorl    %ecx, %edx
    addl    %edx, %eax
    popl    %ebx
    .cfi_remember_state
    .cfi_def_cfa_offset 4
    .cfi_restore 3
    ret
    .p2align 4,,7
L9:
    .cfi_restore_state
    negl    %ecx
    sall    %cl, %edx
    movl    %eax, %ecx
    negl    %ecx
    xorl    %ecx, %edx
    addl    %edx, %eax
    popl    %ebx
    .cfi_restore 3
    .cfi_def_cfa_offset 4
    ret
    .cfi_endproc

Itu perbedaan ekstrem . Ini sebenarnya muncul di profil juga, fast_trunc_onesekitar 30% lebih cepat daripada fast_trunc_two. Sekarang pertanyaan saya: apa yang menyebabkan ini?

Diperbarui untuk menyinkronkan dengan edit OP

Dengan mengutak-atik kode, saya telah berhasil melihat bagaimana GCC mengoptimalkan kasus pertama.

Sebelum kita dapat memahami mengapa mereka sangat berbeda, pertama-tama kita harus memahami bagaimana GCC mengoptimalkan fast_trunc_one().

Percaya atau tidak, fast_trunc_one()sedang dioptimalkan untuk ini:

int fast_trunc_one(int i) {
    int mantissa, exponent;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);

    if (exponent < 0) {
        return (mantissa << -exponent);             /* diff */
    } else {
        return (mantissa >> exponent);              /* diff */
    }
}

Ini menghasilkan rakitan yang sama persis seperti fast_trunc_one()nama register asli dan semuanya.

Perhatikan bahwa tidak ada xors untuk perakitan fast_trunc_one(). Itulah yang memberikannya untuk saya.

Bagaimana?

Langkah 1: sign = -sign

Pertama, mari kita lihat signvariabelnya. Karena sign = i & 0x80000000;, hanya ada dua nilai yang mungkin signdapat diambil:

• sign = 0
• sign = 0x80000000

Sekarang ketahuilah bahwa dalam kedua kasus sign == -sign,. Karena itu, ketika saya mengubah kode asli ke ini:

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = mantissa << -exponent;
    } else {
        r = mantissa >> exponent;
    }

    return (r ^ sign) + sign;
}

Ini menghasilkan perakitan yang sama persis seperti aslinya fast_trunc_one(). Saya akan menghindarkan Anda dari majelis, tetapi identik - daftarkan nama dan semuanya.

Langkah 2: Pengurangan matematika:x + (y ^ x) = y

signhanya dapat mengambil satu dari dua nilai, 0atau 0x80000000.

• Kapan x = 0, x + (y ^ x) = ylalu hal sepele berlaku.
• Menambahkan dan menambahkan berdasarkan 0x80000000sama. Itu membalik bit tanda. Karena itu x + (y ^ x) = yjuga berlaku kapan x = 0x80000000.

Karena itu, x + (y ^ x)kurangi menjadi y. Dan kode menyederhanakan ini:

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = (mantissa << -exponent);
    } else {
        r = (mantissa >> exponent);
    }

    return r;
}

Sekali lagi, ini mengkompilasi ke majelis yang sama - mendaftarkan nama dan semua.

Versi di atas ini akhirnya mengurangi ini:

int fast_trunc_one(int i) {
    int mantissa, exponent;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);

    if (exponent < 0) {
        return (mantissa << -exponent);             /* diff */
    } else {
        return (mantissa >> exponent);              /* diff */
    }
}

yang cukup banyak persis apa yang dihasilkan GCC di majelis.

Jadi mengapa kompiler tidak mengoptimalkan fast_trunc_two()hal yang sama?

Bagian kunci dalam fast_trunc_one()adalah x + (y ^ x) = yoptimasi. Di fast_trunc_two()dalam x + (y ^ x)ekspresi sedang dibagi di cabang.

Saya menduga itu mungkin cukup untuk membingungkan GCC untuk tidak melakukan optimasi ini. (Perlu mengangkat ^ -signkeluar cabang dan menggabungkannya ke r + signbagian akhir.)

Misalnya, ini menghasilkan rakitan yang sama dengan fast_trunc_one():

int fast_trunc_two(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = ((mantissa << -exponent) ^ -sign) + sign;             /* diff */
    } else {
        r = ((mantissa >> exponent) ^ -sign) + sign;              /* diff */
    }

    return r;                                     /* diff */
}

Ini adalah sifat kompiler. Dengan asumsi mereka akan mengambil jalur tercepat atau terbaik, itu sangat salah. Siapa pun yang menyiratkan bahwa Anda tidak perlu melakukan apa pun untuk kode Anda untuk mengoptimalkan karena "kompiler modern" mengisi kosong, lakukan pekerjaan terbaik, buat kode tercepat, dll. Sebenarnya saya melihat gcc semakin buruk dari 3.x ke 4.x paling tidak pada lengan. 4.x mungkin telah mencapai 3.x pada titik ini, tetapi sejak awal menghasilkan kode lebih lambat. Dengan latihan Anda dapat belajar bagaimana menulis kode Anda sehingga kompiler tidak harus bekerja sekeras dan sebagai hasilnya menghasilkan hasil yang lebih konsisten dan diharapkan.

Bug di sini adalah harapan Anda tentang apa yang akan diproduksi, bukan apa yang sebenarnya diproduksi. Jika Anda ingin kompiler menghasilkan output yang sama, berikan input yang sama. Secara matematis tidak sama, tidak agak sama, tetapi sebenarnya sama, tidak ada jalur yang berbeda, tidak ada operasi berbagi atau mendistribusikan dari satu versi ke versi lainnya. Ini adalah latihan yang baik dalam memahami bagaimana menulis kode Anda dan melihat apa yang dilakukan oleh kompiler. Jangan membuat kesalahan dengan mengasumsikan bahwa karena satu versi gcc untuk satu target prosesor suatu hari menghasilkan hasil tertentu yang merupakan aturan untuk semua kompiler dan semua kode. Anda harus menggunakan banyak kompiler dan banyak target untuk merasakan apa yang sedang terjadi.

gcc cukup jahat, saya mengundang Anda untuk melihat ke belakang tirai, melihat nyali gcc, mencoba untuk menambah target atau memodifikasi sesuatu sendiri. Ini hampir tidak disatukan oleh lakban dan kawat bailing. Baris kode tambahan ditambahkan atau dihapus di tempat-tempat penting dan itu runtuh. Fakta bahwa ia telah menghasilkan kode yang dapat digunakan sama sekali adalah sesuatu yang bisa disenangi, alih-alih mengkhawatirkan mengapa ia tidak memenuhi harapan lain.

apakah Anda melihat versi gcc yang berbeda? 3.x dan 4.x khususnya 4.5 vs 4.6 vs 4.7, dll? dan untuk prosesor target yang berbeda, x86, arm, mips, dll atau rasa yang berbeda dari x86 jika itu adalah kompiler asli yang Anda gunakan, 32 bit vs 64 bit, dll? Dan kemudian llvm (dentang) untuk target yang berbeda?

Mystical telah melakukan pekerjaan yang sangat baik dalam proses pemikiran yang diperlukan untuk bekerja melalui masalah menganalisis / mengoptimalkan kode, mengharapkan kompiler untuk datang dengan semua itu, yah, tidak diharapkan dari "kompiler modern" apa pun.

Tanpa masuk ke properti matematika, kode formulir ini

if (exponent < 0) {
  r = mantissa << -exponent;                       /* diff */
} else {
  r = mantissa >> exponent;                        /* diff */
}
return (r ^ -sign) + sign;                           /* diff */

akan memimpin compiler ke A: mengimplementasikannya dalam bentuk itu, melakukan if-then-else lalu konvergen pada kode umum untuk menyelesaikan dan kembali. atau B: simpan cabang karena ini adalah ujung fungsi. Juga tidak repot menggunakan atau menyimpan r.

if (exponent < 0) {
  return((mantissa << -exponent)^-sign)+sign;
} else {
  return((mantissa << -exponent)^-sign)+sign;
}

Kemudian Anda bisa masuk sebagai Mystical menunjukkan variabel tanda menghilang bersama-sama untuk kode yang ditulis. Saya tidak akan mengharapkan kompiler untuk melihat variabel tanda pergi sehingga Anda harus melakukannya sendiri dan tidak memaksa kompiler untuk mencoba mengetahuinya.

Ini adalah kesempatan sempurna untuk menggali kode sumber gcc. Tampaknya Anda telah menemukan sebuah kasus di mana pengoptimal melihat satu hal dalam satu kasus kemudian hal lain dalam kasus lain. Kemudian ambil langkah selanjutnya dan lihat apakah Anda tidak bisa mendapatkan gcc untuk melihat kasing itu. Setiap optimasi ada karena beberapa individu atau kelompok mengenali optimasi dan sengaja meletakkannya di sana. Agar pengoptimalan ini ada di sana dan berfungsi setiap kali seseorang harus meletakkannya di sana (lalu mengujinya, dan kemudian mempertahankannya di masa mendatang).

Jelas jangan berasumsi bahwa lebih sedikit kode lebih cepat dan lebih banyak kode lebih lambat, sangat mudah untuk membuat dan menemukan contoh yang tidak benar. Ini mungkin lebih sering terjadi daripada kurang kode menjadi lebih cepat daripada lebih banyak kode. Seperti yang saya tunjukkan dari awal meskipun Anda dapat membuat lebih banyak kode untuk menyimpan percabangan dalam kasus atau perulangan, dll dan memiliki hasil bersih menjadi kode lebih cepat.

Intinya adalah Anda memberi kompiler sumber yang berbeda dan mengharapkan hasil yang sama. Masalahnya bukan output kompiler tetapi harapan pengguna. Cukup mudah untuk diperlihatkan untuk kompiler dan prosesor tertentu, penambahan satu baris kode yang membuat keseluruhan fungsi lebih lambat secara dramatis. Misalnya mengapa mengubah a = b + 2; ke a = b + c + 2; menyebabkan _fill_in_the_blank_compiler_name_ menghasilkan kode yang sangat berbeda dan lebih lambat? Jawabannya tentu saja sebagai kompiler diberi kode yang berbeda pada input sehingga sangat valid untuk kompiler untuk menghasilkan output yang berbeda. (bahkan lebih baik adalah ketika Anda menukar dua baris kode yang tidak terkait dan menyebabkan output berubah secara dramatis) Tidak ada hubungan yang diharapkan antara kompleksitas dan ukuran input dengan kompleksitas dan ukuran output.

for(ra=0;ra<20;ra++) dummy(ra);

Ini menghasilkan suatu tempat antara 60-100 garis assembler. Itu membuka gulungannya. Saya tidak menghitung garis, jika Anda memikirkannya, ia harus menambahkan, menyalin hasilnya ke input ke panggilan fungsi, membuat panggilan fungsi, tiga operasi minimum. jadi tergantung pada target yang mungkin 60 instruksi setidaknya, 80 jika empat per loop, 100 jika lima per loop, dll.

Mysticial telah memberikan penjelasan yang bagus, tetapi saya pikir saya akan menambahkan, FWIW, bahwa benar-benar tidak ada yang mendasar tentang mengapa kompiler membuat optimasi untuk yang satu dan bukan yang lain.

clangKompiler LLVM , misalnya, memberikan kode yang sama untuk kedua fungsi (kecuali untuk nama fungsi), memberikan:

_fast_trunc_two:                        ## @fast_trunc_one
        movl    %edi, %edx
        andl    $-2147483648, %edx      ## imm = 0xFFFFFFFF80000000
        movl    %edi, %esi
        andl    $8388607, %esi          ## imm = 0x7FFFFF
        orl     $8388608, %esi          ## imm = 0x800000
        shrl    $23, %edi
        movzbl  %dil, %eax
        movl    $150, %ecx
        subl    %eax, %ecx
        js      LBB0_1
        shrl    %cl, %esi
        jmp     LBB0_3
LBB0_1:                                 ## %if.then
        negl    %ecx
        shll    %cl, %esi
LBB0_3:                                 ## %if.end
        movl    %edx, %eax
        negl    %eax
        xorl    %esi, %eax
        addl    %edx, %eax
        ret

Kode ini tidak sesingkat versi gcc pertama dari OP, tetapi tidak selama yang kedua.

Kode dari kompiler lain (yang tidak akan saya sebutkan), kompilasi untuk x86_64, menghasilkan ini untuk kedua fungsi:

fast_trunc_one:
        movl      %edi, %ecx        
        shrl      $23, %ecx         
        movl      %edi, %eax        
        movzbl    %cl, %edx         
        andl      $8388607, %eax    
        negl      %edx              
        orl       $8388608, %eax    
        addl      $150, %edx        
        movl      %eax, %esi        
        movl      %edx, %ecx        
        andl      $-2147483648, %edi
        negl      %ecx              
        movl      %edi, %r8d        
        shll      %cl, %esi         
        negl      %r8d              
        movl      %edx, %ecx        
        shrl      %cl, %eax         
        testl     %edx, %edx        
        cmovl     %esi, %eax        
        xorl      %r8d, %eax        
        addl      %edi, %eax        
        ret                         

yang menarik karena menghitung kedua sisi if dan kemudian menggunakan gerakan bersyarat pada akhirnya untuk memilih yang benar.

Kompiler Open64 menghasilkan yang berikut:

fast_trunc_one: 
    movl %edi,%r9d                  
    sarl $23,%r9d                   
    movzbl %r9b,%r9d                
    addl $-150,%r9d                 
    movl %edi,%eax                  
    movl %r9d,%r8d                  
    andl $8388607,%eax              
    negl %r8d                       
    orl $8388608,%eax               
    testl %r8d,%r8d                 
    jl .LBB2_fast_trunc_one         
    movl %r8d,%ecx                  
    movl %eax,%edx                  
    sarl %cl,%edx                   
.Lt_0_1538:
    andl $-2147483648,%edi          
    movl %edi,%eax                  
    negl %eax                       
    xorl %edx,%eax                  
    addl %edi,%eax                  
    ret                             
    .p2align 5,,31
.LBB2_fast_trunc_one:
    movl %r9d,%ecx                  
    movl %eax,%edx                  
    shll %cl,%edx                   
    jmp .Lt_0_1538                  

dan kode yang serupa, tetapi tidak identik, untuk fast_trunc_two.

Lagi pula, ketika datang ke optimasi, itu lotre - itu adalah apa itu ... Tidak selalu mudah untuk mengetahui mengapa kode Anda dikompilasi dengan cara tertentu.