[分享] Header Time Optimization (HTO)

[Lipraxde (靜夜)]

Cross-Translation Unit Optimization via Annotated Headers

以前在 LLVM youtube 頻道上看到的：
https://www.youtube.com/watch?v=elmio6AoyK0

LLVM 在優化程式碼的時候，會對 IR 順便添加一些 attribute。

例如：

define i32 @square(i32) {   
    %2 = mul nsw i32 %0, %0 
    ret i32 %2              
}                           

會發現經過 opt 優化後，square 這個 function 被加上了：norecurse、nounwind、
readnone 這三個 attribute。https://godbolt.org/z/6n47h6

而所謂的 HTO 呢，就是把這些 attribute 放到 header file 裡，利用這種方式提供跨
Translation Unit (TU) 的優化能力。

讓我們來看看影片裡的例子：

double norm(double *A, int n);                   
                                                 
void normalize(double *out, double *in, int n) { 
    for (int i = 0; i < n; ++i) {                
        out[i] = in[i] / norm(in, n);            
    }                                            
}                                                

如何才能使 for loop 裡的計算被 vectorized？

一般來說，因為 norm 的 definition 在不同的 TU 裡，compiler 是沒辦法主動做
vectorization 的，所以不想改程式的話就只好開啟 LTO 了。

然而，若是在無法取得 source code 情況下是無法開 LTO 的 QQ。

這時候就是 HTO 派上用場的時間啦～

HTO 可以把由 LLVM 優化所添加的 attribute 放到 header file 裡：

__attribute__((fn_attr("readonly"), fn_attr("argmemonly"))) 
double norm(double* A, int n);                              

* fn_attr 是 HTO 提供的特殊 attribute

這樣一來，compiler 就能知道 norm 這個 function：

  1. 不會透過 pointer 寫入
  2. 只使用它的 argument

這樣 compiler 在優化 normalize 的時候呢，就可以把對 norm 的呼叫移到 for loop
外，對剩下的運算進行 vectorization。


心得：

原則上，任何優化要是在「不改變程式行為的前提下」才能做。

Aggressive 的優化當然也不能無法無天。

事實上所謂 aggressive 的優化，是對程式碼的假設變得 aggressive，譬如說假設不會
發生越界存取之類的（-faggressive-loop-optimizations）。

那...為什麼開了優化後程式出問題了？

絕大多數的情況是因為寫了 Undefined Behavior，或是說破壞了某些 compiler 做的假
設。

Compiler 是真的不會變魔術，有時候由於提供的資訊不夠， 並不能做出想像中的優化。

因此，使用一門程式語言，除了學會語法外，對其 compiler 的熟悉度也是很重要的。

就譬如文中所述的例子，其實寫的時候把 norm 移到 for loop 外即可。

了解「什麼情況下 compiler 可以優化這段程式碼」才能更加善用程式語言，寫出更有效
率的程式。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.177.1.12 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/CompilerDev/M.1600535873.A.C8D.html
※ 編輯: Lipraxde (180.177.1.12 臺灣), 09/20/2020 01:27:03
推 mshockwave: 推推 這種方法感覺就像把 ThinLTO 的 summary搬到原始
推 mshockwave: 碼階層 畢竟ThinLTO summary也只記載函式介面的屬性
→ Lipraxde: 不過 HTO 沒辦法拿來 inline function，而且最後也沒被
→ Lipraxde: 合併到 LLVM 裡QQ
推 unimaybe: 實用，推推！！