strict aliasing - Eternity

今天剛好又遇到有人在問這個。
可能網路上能查到的資料太零散看規格書又查不到，很多人不清楚這東西是幹什麼的，
甚至還有一堆網頁列出了 x86 還是其它硬體架構的組語講了半天都講不到重點，所以還是在這簡單的做個說明好了。

每個 programmer 應該都知道 C/C++ 最大的問題就是 aliasing。
Java 這類只有 reference 的語言也非常愛攻擊這一點，實際上 Java 的 optimizer 也常在這方面吃 C/C++ 的豆腐吃得很高興。
以下面的 code 為例：

void foo(int *v1, int *v2, int *result, int count)
{
    while(count--) {
        *result += *v1 + *v2;
    }
}

void foo(int *v1, int *v2, int *result, int count)

{

while(count--) {

*result += *v1 + *v2;

}

大部分的人都以為 compiler 為了做最佳化，會去把 *v1 + *v2 的算式往迴圈外面提，
然後將 *v1 + *v2 的結果存到一個暫時變數上，再把迴圈裡的算式直接用那個暫時變數代換以節省重複運算的時間。
像是這樣：

void foo(int *v1, int *v2, int *result, int count)
{
    int temp = *v1 + *v2;

    while(count--) {
        *result += temp;
    }
}

void foo(int *v1, int *v2, int *result, int count)

{

int temp = *v1 + *v2;

while(count--) {

*result += temp;

}

如果大學是讀資工系或資科系而且有畢業的話，應該會知道這是不可能的。
因為 compiler 不知道會不會有人寫 foo(&var, &var, &var, 1000) 來呼叫 foo，所以會假設所有的 pointer 之間都有 aliasing。
簡單說就是假設 *result 被改變了，那麼 *v1 和 *v2 的值也會跟著改變。
所以不能像上面那樣把 *v1 + *v2 的結果視為 loop invariant，必須每一次重新計算才行。
更精確的來說，就是每個 iteration 都要把 *v1 和 *v2 的值從 memory 裡重新 load 出來 (有點類似 volatile 變數的行為)，所以 performance 就會爛掉。

當然 strict aliasing 的標準化並不能解決上述的效能問題。
上述問題的解法是使用 C99 的 restrict 去修飾 pointer 的 type，由 programmer 來保證它們之間絕對不會有 aliasing，讓 compiler 放心的去做最佳化。
當然如果 programmer 對 compiler 說謊的話，那程式跑出來有時候對有時候錯就是 programmer 活該了。

strict aliasing 被設計出來的目的是解決類似下述這種的問題：

void bar(int32_t *input1, int32_t *input2, int64_t *result, int count)
{
    while(count--) {
        *result += *input1 * *input2;
    }
}

void bar(int32_t *input1, int32_t *input2, int64_t *result, int count)

{

while(count--) {

*result += *input1 * *input2;

}

乍看之下好像會覺得既然 result 跟 input1/input2 的 type 根本就不一樣。
那麼 *result 的值被修改總該跟 input1 和 input2 沒有關聯了吧？
因此 compiler 一定可以把 *input1 * *input2 的運算結果提出來...
很遺憾，如果你的 compiler 不知道什麼叫 strict aliasing，那麼答案還是不會。
原因跟前面差不多所以就不細述了。
反正大家都知道程式要怎樣亂寫來讓它們真的產生 aliasing，有 pointer 的語言就是這麼神奇又無敵。

連這種用人眼觀察都覺得不應該會有 aliasing 的程式碼 compiler 居然還是無法最佳化，理所當然的一定會使得某些人十分的不爽。
畢竟最佳化只要碰到 pointer 就死掉，那即使是 Java 這類半直譯式的語言都可能在效能上隨便把 C/C++ 程式打趴在地上。
因此某些人自然就會想要讓 compiler 的最佳化機制能符合他們的經驗判斷。
也就是說根據他們的經驗，絕大多數的 programmer 只要寫出上面那樣的程式碼，就是打從一開始根本沒打算讓 result 跟 input1/input2 之間有 aliasing。
會有 aliasing 肯定是 programmer 亂寫或設計不良所造成的，compiler 根本就沒有必要為了遷就這些不會寫程式的人來壓抑其最佳化的能力，於是乎就產生了 strict aliasing 這個想法。
也就是對以往總是無限上綱的 aliasing rule 設下一些限制，如此一來就能把問題簡單化一點以增加最佳化的空間。

既然決定要制訂涵蓋範圍比較小的 aliasing rule 了，那麼要以什麼為基準來設定限制條件呢？
當然是以人類直覺不應該有 aliasing 這個觀點出發，回頭看看前面的程式碼。
人類之所以能夠一眼就覺得沒有 aliasing 的理由，當然是因為 input1/input2 跟 result 有不同的 type。
所以就搞了一套 type-based aliasing rule 出來了，這樣做就可以符合了上面所說的人類直覺。
因為那兩個 pointer 的 type 根本就不相容 (incompatible)，所以只要不是亂寫就不應該會有 aliasing 發生，因此 compiler 可以非常大膽的放手去做最佳化。
這也就是說，「*input1 * *input2」的結果可以預先算好，並存放在 register 裡面。
就算 *result 的值被改變了真的會動到 *input1 或 *input2 的值，那也是不管。誰叫寫程式的人亂寫。

講了這麼多，看起來好像事情是很單純。
確實從語言機制演進的角度來看是這樣沒錯。
但是這個演化而來的機制也確實的對一些老舊的程式碼產生了巨大的衝擊，典型的狀況就是：

int64_t transform(int64_t value)
{
    int32_t *ptr = (int32_t *)&value;
    int32_t x = *ptr;
    int32_t y = *(ptr + 1);

    *ptr = y;
    *(ptr + 1) = x;

    return value;
}

int64_t transform(int64_t value)

{

int32_t *ptr = (int32_t *)&value;

int32_t x = *ptr;

int32_t y = *(ptr + 1);

*ptr = y;

*(ptr + 1) = x;

return value;

}

這樣在編譯器並未明確關閉 strict aliasing 功能的狀態下，程式跑到 return 那行時 value 的內容將無法預測。
儘管 ptr = (int32_t *)&value 試圖在 *ptr 和 value 之間建立 aliasing 關係，但根據 strict aliasing 的規則，
ptr 的 type 是 (int32_t *)，&value 的 type 是 (int64_t *)。
不管你是不是有把 &value 的結果 cast 成 (int32_t *)，反正只要變成了跟 (int64_t *) 不相容的型別，aliasing 關係就不會建立也不允許被建立，而這個動作就會被視為所謂的亂寫。
也就是說，到了最後一行的 return 敘述，value 的值可能就是直接拿 cache 在 register 裡的內容而不會重新從 memory 裡讀值。
用程式碼來說的話就是變成：

int64_t transform(int64_t value)
{
    int64_t reg = value;
    int32_t *ptr = (int32_t *)&value;
    int32_t x = *ptr;
    int32_t y = *(ptr + 1);

    *ptr = y;
    *(ptr + 1) = x;

    return reg;
}

int64_t transform(int64_t value)

{

int64_t reg = value;

int32_t *ptr = (int32_t *)&value;

int32_t x = *ptr;

int32_t y = *(ptr + 1);

*ptr = y;

*(ptr + 1) = x;

return reg;

}

4 - 9 行可以說是完全白寫。
極端的狀況下 compiler 甚至能把 x = transform(y) 的算式直接化簡成 x = y，結果打了一大堆程式碼根本就是在浪費時間。
我知道就算到了 2010 年的今天，還是會有學校的老師出類似的考題但心裡所想的答案卻不是「行為未定義」，幹這種事只會暴露自己在這 10 幾年間一直疏於進修罷了。

看到這邊似乎會發現好像又違反了人類直覺？
其實再往前看一步，就會發現這個 transform() 的寫法正是所謂的禍根。
回頭想想要如何呼叫前面寫的 bar()，才能讓 input1/input2 和 result 所指向的記憶體空間產生重疊關係？
答案是 bar((int32_t *)&var, ((int32_t *)&var) + 1, &var, 100);。
這種 pointer casting 的動作正是禍害的來源，講白話一點就是開始亂寫程式的位置。
所以這樣設定規則並不算過份，只要說明原因之後還是可以讓人覺得很合理，儘管它跟所謂的人類直覺有一段小小的距離。
不過就我個人的觀點來說，這種連小學生看上去都覺得亂七八糟的程式碼當然就是亂寫的，會造成故障可說是一點都不意外。

當然 strict aliasing 的 rule 也有一些特例狀況，像是把任何 type 的 pointer cast 成 (char *) 還是可以建立 aliasing 關係 (反之不成立) 等等。
這裡只是簡單介紹一下為什麼會有這種東西，以及它對 legacy code 有什麼影響。
總之一個最基本的原則就是不相容的 pointer 間互相做 casting 的動作，管它是包在 struct 還是 union 裡面，只要掌握這個原則就能輕易的確認出那些程式碼是不是亂寫出來的。
當然直接用 compiler 的 warning option 也是可以，不過要當心可能會出現誤判。

現今我們在使用 make + gcc 編譯一些 open source 的程式時，還是時常會發現不少程式的 Makefile 都偷偷的加上了 -fno-strict-aliasing 這個編譯選項。
根據該程式碼的出產年份，我們可以據此研判該程式的作者是否不會寫程式。
請至少對這些作者的名字留下一點印象，將來評估要使用哪套 library 來實作自己的程式時，可以藉此做為選擇的依據之一，避免寫出來的程式三不五時就莫名其妙的故障。
如果原作者是 80 年代或 90 年代初開發完這樣的程式就丟給別人 maintain 了，那麼我們倒是不能直接判定那位作者不會寫程式，也不能這樣就判定現在的 maintainer 不會寫程式。
因為如果程式規模稍微大一點的話，maintainer 可能會由於各種因素而沒空或懶得去整個做大翻修，不見得就是不會或不懂。
但如果從以前到現在都是原作者自己在 maintain，或是原作者一路 maintain 到 90 年末或 2000 年初，那麼可以有相當大的機率是這位原作者不會寫程式。
因為根據我個人的經驗，不管程式規模大得再誇張，只要整個程式都是自己寫的，翻修起來幾乎都不會花自己多少時間。

一	二	三	四	五	六	日
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31