:::warning
[nasal-demons](http://www.catb.org/jargon/html/N/nasal-demons.html): **"When the compiler encounters a given undefined construct, it is legal for it to make demons fly out of your nose"**
:::

## 問題

#include <stdio.h>
#include <stdint.h>

const unsigned int translate[16] = {0, 1, 2, 3, 8,  9,  10, 11,
                                    4, 5, 6, 7, 12, 13, 14, 15};
static unsigned int update(int res, unsigned int i) {
    if (i >= 16)
        return -1;

    return translate[i];
}

int main(int argc, char *argv[]) {
    if (argc < 2) {
        return -1;
    }

    unsigned int val = 0;
    sscanf(argv[1], "%d", &val);

    unsigned int ans = update(val, __builtin_ctz(val) >> 1);
    printf("get ans %d\n", ans);

    return 0;
}

考慮上述程式，開啟 -O3 選項編譯。在給定的 `argv[1]` 是合法的非負整數的前提下，最終可能印出的 `ans` 只會是 -1 ~ 15 之間的任何數值，是否正確呢?

若從 `update` 的實作來看，不管到底 `update` 接受的輸入是甚麼，輸入的 i 若 >= 16 的數字都會直接返回 -1，否則才返回 `translate[i]`，而後者的範圍在 0 ~ 15 之間。則乍看之下前述問題的答案是正確的。

但實際上，在 Linux 上使用 gcc 11.3 編譯後，執行 `./a.out 0` 我們會得到

$ gcc -O3 test.c
$ ./a.out 0
get ans 990059265

從結果來看，我們只能猜測是發生對陣列的越界存取，也就是對 `translate[i]` 輸入的 `i` 超出 15。可是理論上 `update` 已經提前用 if 來保護對 `translate` 的存取了，這又怎麼可能會發生呢?

## 分析

也許你已經發現了一些端倪。若根據 gcc 的手冊，顯然 [`__builtin_ctz(0)`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fctz) 是未定義的行為，因此我們會得到的返回值是不可預期的。然而這和 `update` 又有何關係呢? 這邊我們就得一步步解釋編譯器的優化邏輯:

1. 開啟 -O3 下，編譯不必將 `update` 視為獨立編譯單元(compilation unit)，而是可以直接 inline 到 `main` 之中
2. 因為 `__builtin_ctz(0)` 是 undefined behavior，編譯器直接假設這情況不被預期發生
3. 呈上，則因為輸入到 `__builtin_ctz` 中的數字是 32 位元的非負整數，因此編譯器可以認定 `__builtin_ctz()` 能得到的結果是 0 到 31 之間的任意數字
4. 那麼 `__builtin_ctz() >> 1` 能得到的結果就是 0 到 15 之間的任意數字
5. 根據前面的推論，既然給定 `update` 的 `i` 是來自 `__builtin_ctz() >> 1`，而該結果是 0 至 15 之間的值，編譯器判斷 `if (i > = 16)` 是不必要的，可以直接移除掉
6. 因此輸入 `./a.out 0` 使得發生 `__builtin_ctz(0)` 時，後者的結果在編譯器的優化下返回 32，加上前面 if 被移除的結果，最終得到輸出 "get ans 990059265"

## 小結

從上述問題中我們可以看到，即便我們認為自己有透過 `if` 來避免對陣列的越界存取，然而在激進的優化之下，只要程式中存在未定義行為，那麼我們仍然無法完全保證編譯器不會直接將其消除掉，進而造成前述狀況的發生。其他類似案例也可以在 [GCC undefined behaviors are getting wild](http://blog.pkh.me/p/37-gcc-undefined-behaviors-are-getting-wild.html) 一文看到。

這裡也不難看出 UB 造成的程式錯誤可能相當棘手，因為程式的執行和 C 語言中描述的邏輯已經產生歧異，嚴謹的方式上，我們可能得深入到組語才能夠探究其中端倪。不過要是對組語不是很熟悉，發生類似的情形時該怎麼除錯呢? 也許先善用 [UBSAN](https://www.kernel.org/doc/html/latest/dev-tools/ubsan.html) 排除程式中的未定義行為會是不錯的方式。