例題描述

例題描述：通過(guò)C語(yǔ)言識(shí)別一個(gè)int型數(shù)據(jù)在十進(jìn)制下是否為回文數(shù)字。不能有額外的字符串空間開(kāi)銷(xiāo)。
如：2156512是回文數(shù)，而21565不是回文數(shù)。

問(wèn)題分析：
1. 當(dāng)這個(gè)數(shù)字是負(fù)數(shù)的時(shí)候，肯定不是回文數(shù)
2. 可以將這個(gè)數(shù)翻轉(zhuǎn)，判斷翻轉(zhuǎn)后是否相同

C語(yǔ)言代碼演示：

/*************************************************************************> File Name: isPalindrome.cpp> Author: ChenXiansen > Mail: 1494089474@qq.com > Created Time: Wed 11 Nov 2020 09:49:43 AM CST************************************************************************/#include <stdio.h>bool isPalindrome(int x, int n) {if (__builtin_expect(!!(x < 0), 0)) return false;int y = 0, z = x;while (x) {y = y * n + x % n;x /= n;}return z == y; }int main() {int n, Cov = 10;scanf("%d", &n);if (isPalindrome(n, Cov)) {printf("Num: %d in Cov: %d is a reverse num!\n", n, Cov);} else {printf("NO! It's not a reverse num!\n");}return 0; }

---

代碼分析

在 isPalindrome函數(shù)中，使用了if (__builtin_expect(!!(x < 0), 0)) return false; 這條語(yǔ)句。
下面是對(duì)__builtin_expect宏的表述：

GCC提供了__builtin_expect宏，作為編譯分支時(shí)候的暗示。用法是__builtin_expect(var, expected_value)，也就是說(shuō)，告訴編譯器var這個(gè)變量的值比較可能是什么。在kernel中這個(gè)宏被用在likely和unlikely這兩個(gè)宏定義中：

#define likely(x) __builtin_expect(!!(x), 1) //x很可能成立 #define unlikely(x) __builtin_expect(!!(x), 0) //x很可能不成立

從現(xiàn)代的處理器架構(gòu)說(shuō)起。相信大家都知道流水線(xiàn)技術(shù)，就是CPU可以在統(tǒng)一個(gè)時(shí)鐘周期內(nèi)同時(shí)執(zhí)行多條指令，當(dāng)前指令尚未執(zhí)行完畢，實(shí)際上就已經(jīng)開(kāi)始處理后面的指令了。然而當(dāng)處理器遇到分支的時(shí)候，就無(wú)法判斷即將執(zhí)行的是哪個(gè)分支，流水線(xiàn)優(yōu)化就受到了限制。

后來(lái)，隨著處理器技術(shù)的發(fā)展，處理器開(kāi)始直接預(yù)取分支后面的指令，如果發(fā)現(xiàn)分支預(yù)判錯(cuò)誤，則拋棄之前的執(zhí)行結(jié)果，重新轉(zhuǎn)入正確的分支繼續(xù)執(zhí)行。 更加現(xiàn)代的處理器甚至能夠預(yù)取更多后面的指令，對(duì)于不依賴(lài)之前執(zhí)行結(jié)果的指令都可以按照一定的規(guī)則預(yù)先執(zhí)行得到結(jié)果。

---

匯編代碼

1. 初始代碼匯編

接下來(lái)在終端運(yùn)行g(shù)cc -S isPalindrome.cpp，查看匯編代碼中的isPalindrome()函數(shù)：

.LFB0:.cfi_startprocendbr64pushq %rbp.cfi_def_cfa_offset 16.cfi_offset 6, -16movq %rsp, %rbp.cfi_def_cfa_register 6movl %edi, -20(%rbp)movl %esi, -24(%rbp)movl -20(%rbp), %eaxshrl $31, %eaxmovzbl %al, %eaxtestq %rax, %raxje .L2movl $0, %eaxjmp .L3 .L2:movl $0, -8(%rbp)movl -20(%rbp), %eaxmovl %eax, -4(%rbp) .L5:cmpl $0, -20(%rbp)je .L4movl -8(%rbp), %eaximull -24(%rbp), %eaxmovl %eax, %ecxmovl -20(%rbp), %eaxcltdidivl -24(%rbp)movl %edx, %eaxaddl %ecx, %eaxmovl %eax, -8(%rbp)movl -20(%rbp), %eaxcltdidivl -24(%rbp)movl %eax, -20(%rbp)jmp .L5 .L4:movl -4(%rbp), %eaxcmpl -8(%rbp), %eaxsete %al .L3:popq %rbp.cfi_def_cfa 7, 8ret.cfi_endproc .LFE0:.size _Z12isPalindromeii, .-_Z12isPalindromeii.section .rodata

對(duì).LFB0段的釋義：

main()函數(shù)中的變量n的值存入了edi寄存器，作為bool isPalindrome(int x, int n)的形參x。

main()函數(shù)中的變量Cov的值存入esi寄存器，作為bool isPalindrome(int x, int n)的形參n。

movl %edi, -20(%rbp)
movl %esi, -24(%rbp)
將這兩個(gè)參數(shù)壓入函數(shù)棧。

movl -20(%rbp), %eax :將存在于-20(%rbp)中x的值，存入eax寄存器。

執(zhí)行以下匯編指令，這段匯編指令由if (__builtin_expect(!!(x < 0), 0)) return false;轉(zhuǎn)換得到： shrl $31, %eaxmovzbl %al, %eaxtestq %rax, %raxje .L2movl $0, %eaxjmp .L3 可以看到：在執(zhí)行前三行語(yǔ)句后(這三行代碼現(xiàn)在沒(méi)有弄清楚具體含義，待后續(xù)查閱相關(guān)資料)，下一步是判斷分支：匯編代碼是je .L2，

如果滿(mǎn)足testq %rax, %rax條件，下一步是執(zhí)行C程序中的：int y = 0, z = x; 對(duì)應(yīng)在匯編.L2函數(shù)中的： .L2:movl $0, -8(%rbp)movl -20(%rbp), %eaxmovl %eax, -4(%rbp)

如果不滿(mǎn)足條件，將返回值0放入寄存器eax中，執(zhí)行.L3 匯編函數(shù)部分的return操作。

修改程序后匯編：

現(xiàn)在將

if (__builtin_expect(!!(x < 0), 0)) return false;

這部分C代碼轉(zhuǎn)換成

if (x < 0) return false;

觀察執(zhí)行預(yù)處理-編譯-匯編過(guò)程后，查看匯編代碼中的isPalindrome()函數(shù)。(由于.L2之后的部分完全相同，因此沒(méi)有在博客中顯示)

.LFB0:.cfi_startprocendbr64pushq %rbp.cfi_def_cfa_offset 16.cfi_offset 6, -16movq %rsp, %rbp.cfi_def_cfa_register 6movl %edi, -20(%rbp)movl %esi, -24(%rbp)cmpl $0, -20(%rbp)jns .L2movl $0, %eaxjmp .L3

可以看到：將函數(shù)參數(shù)全部壓棧后，進(jìn)行的分支判斷：

movl %edi, -20(%rbp)movl %esi, -24(%rbp)cmpl $0, -20(%rbp)jns .L2movl $0, %eaxjmp .L3

cmpl $0, -20(%rbp)：如果 bool isPalindrome(int x, int n)函數(shù)中 參數(shù)x的值不滿(mǎn)足 x < 0，則執(zhí)行.L2之后的匯編函數(shù)，反之直接return 0.

---

參考資料：
https://zhuanlan.zhihu.com/p/27339191
http://deltamaster.is-programmer.com/posts/37285.html

附錄：完整匯編程序代碼：

.file "isPalindrome.cpp".text.globl _Z12isPalindromeii.type _Z12isPalindromeii, @function _Z12isPalindromeii: .LFB0:.cfi_startprocendbr64pushq %rbp.cfi_def_cfa_offset 16.cfi_offset 6, -16movq %rsp, %rbp.cfi_def_cfa_register 6movl %edi, -20(%rbp)movl %esi, -24(%rbp)movl -20(%rbp), %eaxshrl $31, %eaxmovzbl %al, %eaxtestq %rax, %raxje .L2movl $0, %eaxjmp .L3 .L2:movl $0, -8(%rbp)movl -20(%rbp), %eaxmovl %eax, -4(%rbp) .L5:cmpl $0, -20(%rbp)je .L4movl -8(%rbp), %eaximull -24(%rbp), %eaxmovl %eax, %ecxmovl -20(%rbp), %eaxcltdidivl -24(%rbp)movl %edx, %eaxaddl %ecx, %eaxmovl %eax, -8(%rbp)movl -20(%rbp), %eaxcltdidivl -24(%rbp)movl %eax, -20(%rbp)jmp .L5 .L4:movl -4(%rbp), %eaxcmpl -8(%rbp), %eaxsete %al .L3:popq %rbp.cfi_def_cfa 7, 8ret.cfi_endproc .LFE0:.size _Z12isPalindromeii, .-_Z12isPalindromeii.section .rodata .LC0:.string "%d".align 8 .LC1:.string "Num: %d in Cov: %d is a reverse num!\n" .LC2:.string "NO! It's not a reverse num!".text.globl main.type main, @function main: .LFB1:.cfi_startprocendbr64pushq %rbp.cfi_def_cfa_offset 16.cfi_offset 6, -16movq %rsp, %rbp.cfi_def_cfa_register 6subq $16, %rspmovq %fs:40, %raxmovq %rax, -8(%rbp)xorl %eax, %eaxmovl $10, -12(%rbp)leaq -16(%rbp), %raxmovq %rax, %rsileaq .LC0(%rip), %rdimovl $0, %eaxcall __isoc99_scanf@PLTmovl -16(%rbp), %eaxmovl -12(%rbp), %edxmovl %edx, %esimovl %eax, %edicall _Z12isPalindromeiitestb %al, %alje .L7movl -16(%rbp), %eaxmovl -12(%rbp), %edxmovl %eax, %esileaq .LC1(%rip), %rdimovl $0, %eaxcall printf@PLTjmp .L8 .L7:leaq .LC2(%rip), %rdicall puts@PLT .L8:movl $0, %eaxmovq -8(%rbp), %rcxxorq %fs:40, %rcxje .L10call __stack_chk_fail@PLT .L10:leave.cfi_def_cfa 7, 8ret.cfi_endproc .LFE1:.size main, .-main.ident "GCC: (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0".section .note.GNU-stack,"",@progbits.section .note.gnu.property,"a".align 8.long 1f - 0f.long 4f - 1f.long 5 0:.string "GNU" 1:.align 8.long 0xc0000002.long 3f - 2f 2:.long 0x3 3:.align 8 4:

總結(jié)

以上是生活随笔為你收集整理的GCC __builtin_expect与kernel指令序列优化的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。