ThinLTO: Scalable and Incremental LTO 論文閱讀筆記

A little bit of history.

SYZYGY – A Framework for Scalable Cross-Module IPO

• ielf，persistent intermediate representation (IR)，基于 ELF 格式，存儲自定義格式的 IR（以及 summary）。論文中表示 ielf 文件大小平均是原始 elf 文件的五倍，極端情況下有700倍。在 SYZYGY 中的地位類似于 LLVM ThinLTO 中的 bitcode IR。
  • 注：從上圖中我們可以看到，FE會直接生成 ielf 文件，同時會收集summary信息，并基于這些信息進行后面的 interprocedural analysis。
• FE，編譯源碼，進行簡單的優化，生成 IR 并收集summary信息，生成 ielf 文件。
• u2comp，真正的 IPO 過程。主要是基于 summary 信息，進行 interprocedural analysis，然后將 analysis result 寫回到 ielf 文件中，也就是會更新這些 summary 信息。
• BE會 consume u2comp 分析得到的 analysis result，然后進行最后的優化和代碼生成

可以看到這里的核心是 ielf 以及 summary 的設計，但是論文中沒有給出詳細的介紹。

GCC LTO

GCC LTO 的發展歷程可以去看 Jan Hubi?ka 的博客，Honza Hubi?ka’s Blog 。講述了 GCC LTO 的發展過程，從

statement-at-a-time

basic common subexpression elimination or peephole optimization

mixture of statement-at-a-time and function-at-a-time

frontend 是statement-at-a-time，RTL 是 function-at-a-time，此時是GCC 2.9

function-at-a-time

隨著 C++ 的崛起，gcc 為了能夠更好的編譯 c++，擁有了更強大的前端，實現了 function-at-a-time parsing。由于 C++ 抽象程度更好，存在很多的“小函數”，所謂的 abstraction penalty，所以此時 inlining 變得至關重要，所以對 inlining 進行了持續的迭代，此時是GCC3.0

unit-at-a-time

設計了新的 callgraph module，unit 級別的 interprocedural analysis 得以更好的完善，此時是GCC3.4

–combine

由于Open64開源并且具有更好的 interprocedural analysis 以及部分 LTO feature ，gcc 已經完全落后，所以Geoffrey Keating擴充了 gcc，使其能夠同時編譯多個源文件，然后將結果作為一個整體喂給gcc后端，但僅限于C語言。

GIMPLE*

GIMPLE Proceedings of the 2003 GCC Developers Summit，原來 GCC 結構：

添加 GIMPLE 后的GCC結構：

LLVM

2003年 chris lattner 曾經推過LLVM，想使其成為 GCC 的后端以此用來取代 GIMPLE ，見Architecture for a Next-Generation GCC，這篇論文在 GIMPLE 后面，主要是 chris lattner 為了推銷自己的LLVM，指出 GCC 在 statement-at-atime，function-at-a-time，unit-at-a-time 之后，變得越來越復雜，可以將 LLVM 納入到GCC，作為其optimizer，整體結構圖如下。這樣做的好處是雙贏，LLVM 不需要為 frontend 以及配套的binutils 而發愁，GCC 不用為其 LTO 而發愁，但是最后卻沒有實現。

From what I understand, LLVM has never been used outside of a research
environment and it can only generate code for a very limited set of
targets. These two are very serious limitations.

直到2005年，雙方還在討論 LLVM project 納入 GCC 的問題，https://marc.info/?l=gcc&m=113269846722569&w=2 ，這里面有很多有趣的爭論，例如 LLVM 的性能很差，LLVM 是 C++ 寫的，但是GCC是C寫的，LLVM 是不是真的要替換 GIMPLE 等等問題。

At the time Tree-SSA merge was being prepared, Chris Lattner presented at 2003 GCC Summit an proposal of itegration of LLVM into GCC as a new middle-end that would take place of the (not yet finished) Tree-SSA project. This never happened and as a result we now have two major open source compilers.
One of major trading point at that time was implementation of LTO. People made guesses if it will be harder to modify GCC architecture for LTO or if it would be harder to complete LLVM to features and richness of backends GCC had. It is definitely interesting to observe that from today point of view.

Hubika 還不忘內涵一把。現在 LLVM 成長為現在這個樣子，不知道他現在是什么想法。現在 GCC 終于有了完善的 LTO，LLVM 的后端也足夠強大。

LTO

2005年發表了Link-Time Optimization in GCC: Requirements and High-Level Design，沒有細讀這篇paper。

WHOPR

2007年又提出了新的 proposal ，WHOPR - Fast and Scalable Whole Program Optimizations in GCC，這篇 paper 的思想和 SYZYGY 很相似，WHOPR 的結構如下所示：

整個過程分為如下幾個步驟：

Local generation (LGEN). This stage executes in parallel. Every file in the program is compiled into intermediate language (IL) together with the local call-graph and summary information.

Whole Program Analysis (WPA). This stage is performed sequentially. The global call-graph is assembled, and a global analysis process makes transformation decisions. The global call-graph may be partitioned to facilitate optimization during phase 3.

Local transformations (LTRANS). This stage executes in parallel. All the decisions made during phase 2 are implemented locally in each target file, and final object code is generated. Optimizations which cannot be decided efficiently during phase 2 may be performed on local call-graph partitions.

目前這個 IL 就是 GIMPLE ，然后附帶上 summary 信息，主要是 call graph（還有 symbol table 以及 type table），這個和 SYZYGY 類似。WPA 作用在這個 call graph 以及 summary 信息上。這也是為了解決編譯耗時和內存占用問題。

另外為了支持增量分析，可以為 summary 信息計算 checksum 來進行復用。

另外為了支持第三方庫，可以手工指定一些簡單的summary信息，例如 mod/ref以及 type 信息。

對于優化大致分為兩類，

Global decisions with local transformations

只需要基于 global summary 信息計算得到的分析結果，就可以在為module單獨codegen時做優化。這應該是最理想化的方式。有以下幾種優化：

• Devirtualization
• Inline caching
• PIC optimizations
• Common block padding and splitting, array padding
• Global variable analysis (assigned ones, global->static)
• Class hierarchy analysis, static cast removal
• Indirect call promotion
• Dead variable elimination
• Dead function elimination
• Field reordering, structure splitting/peeling
• Data reuse analysis
• Inter-procedural prefetch

Global decisions with global transformations

需要將各個 module 的相關信息都 hold 在 memory 中（也就是都可見），才能做的優化，都是 inline 相關的優化。

• Cross-module inlining
• Virtual function inlining
• Cloning
• Inter-procedural points-to
• Inter-procedural constant propagation

WHOPR 合入 GCC，并經過一些迭代后，成為了 GCC LTO 的默認實現，此時是GCC4.6。

LIPO

LIPO 對應的論文是Lightweight Feedback-Directed Cross-Module Optimization。前面提到 LTO 或者 CMO 需要面臨的問題是，如何在編譯耗時以及 memory 開銷可控前提下看到更多的 scope，做更 aggressive 的優化。這篇文章把 LTO 相關的邏輯描述的很清楚：

In the parallelizable front-end phase, the compiler performs a reasonable amount of optimizations for code cleanup and canonicalization. It may also compute summary information for consumption by IPO. This phase writes the compiler intermediate representation (IR) to disk as fake ELF object files, which allows seamless integration into existing build systems.

The IPO phase is typically executed at link time. IPO reads in the fake object files, or parts of them, e.g., sections containing summary data. It may perform type unification and build an interprocedural symbol table, perform analysis, either on summaries, IR, or combined IR, make transformation decisions or perform actual transformations, and readies output for consumption by the back-end phase.

The parallelizable backend phase accepts the compiler IR from IPO, either directly out of memory or via intermediate fake object files, and performs a stronger set of scalar, loop, and other optimizations, as well as code generation and object file production. These final object files are then fed back to the linker to produce the final binary.

LIPO 另辟蹊徑，在 runtime 的時候基于 FDO 得到的 profile 信息，做 cross-module 分析。這篇文章先列舉了inter-procrdural optimization，然后指出了其中最重要的是 inlining 和 indirect call promotion。

• inlining and cloning
• indirect function call promotion
• constant propagation
• alias
• mod/ref
• points-to analysis
• register allocation
• register pressure estimation
• global variable optimizations
• code and data layout techniques
• profile propagation techniques
• C++ class hierarchy analysis and devirtualization
• dead variable and function elimination, and many more.

可以說是論文作者”有意“著重描述了LIPO提升最大的兩個優化，inling 和 indirect call promotion。

然后作者列列舉了 LTO 的幾個缺點

• 需要將中間表示IR，需要在disk和memory之間序列化，開銷比較大
• 某個文件小小的修改，都有可能重新觸發LTO
• debug和LTO一起用起來可能比較麻煩

LIPO 分為如下幾個要點：

• We seamlessly integrate IPO and FDO.
• We move the IPA analysis phase into the binary and execute it at the end of the FDO training run.
• We add aggregated IPA analysis results to the FDO profiles.
• During the FDO optimization build, we use these results to read in additional source modules and form larger pseudo modules to extend scope and to enable more intra-module inter-procedural optimizations.

核心是基于”運行時信息，構建一個dynamic call graph，將親和度（affinity）比較高的modules(稱之為auxiliary module)組合成一個更大的module(稱之為module groupings)，然后進行cross-module optimization“，親和度通過call graph的hot edges來判定，稱之為 source module affinity analysis。

如何判斷 module 之間是否要放在一起，論文有相關算法的介紹，這里不贅述。

通過一個示例來介紹LIPO的過程，

// a.c int foo(char *d, unsigned int i){return d[i] + d[i + 1]; }// b.c char tokens [] = {1 ,3 ,5 ,7 ,11 ,13}; int extern foo(char *d, unsigned int i); int bar(void) {return foo(tokens , 3); }// main.c #include <stdio.h> #include <string.h> extern int sum(char *d, unsigned int i); extern int bar(void); int main(int argc, char **argv) {unsigned int i, s = 0;if(argc != 2) return;for (i = 0; i < strlen(argv[1]) - 1; i++) s += foo(argv[1], i);printf ("sum: %d\n", s);printf ("tokens: %d\n", bar()); }

假設 main.c 中的 for 循環調用 foo 是 hot call，將其放在一起，{main.c, a.c(aux)}，{a.c}，{b.c}。

有一個小插曲由于 LIPO(google的項目) 太成功了，導致 WHOPR (同樣是 google 提的proposal)沒有開發人員開發，直到2009年，WHOPR 才合入 GCC。

LLVM full LTO

LLVM full LTO 是比較樸素的 LTO 實現，frontend 編譯生成的是 bitcode IR，然后在鏈接時進行 materialize，合并成為一個超大的 IR 文件，然后再進行優化。

ThinLTO: Scalable and Incremental LTO

ThinLTO 可以說和 WHOPR 以及 SYZYGY 很像，都是 summary-based Whole-Program Analysis (WPA)，只是工程實現以及一些實現上大同小異，ThinLTO 列舉了以前 LTO/CMO 實現的一些缺點（雖然我感覺不夠實錘）。

實現缺點

LLVM full LTO & HP-UX compiler	將所有的 compilation unit 合并成為一個，開銷較大；IPA/IPO 無法并行化
SYZYGY	summary-based analysis, inlining 無法并行完成，中間需要頻繁修改 ielf ；IPA/IPO 無法并行化；不能處理增量編譯
Open64	summary-based analysis, 中間需要頻繁修改 IR；IPA/IPO 無法并行化；不能處理增量編譯
WHOPR	summary-based analysis, 在IPA的過程中需要頻繁 I/O?(沒有看實現，存疑)；IPA/IPO 無法并行化；不能處理增量編譯
LIPO	需要插樁并收集 profile；雖然通過 module grouping 減少了 scope 以降低開銷，但是 module group 較大時還是會存在 memory issue；同時需要修改 frontend

ThinLTO 雖然也有 serial 過程，但作用在 compact summary(C:沒有對比過其它 LTO summary formats，ThinLTO 的 summary 確實比較 compact)上進行 global analysis，開銷比較可控。ThinLTO 提出了新穎的技術，function importing transformation，用來 enable inlining。不同于 LIPO 或者 WHOPR，ThinLTO 通過 function importing技 術，只 import 需要的 function，使得開銷進一步降低。

ThinLTO Design

ThinLTO 大致分為如下幾個步驟：

Compile: Generate IR as with LTO mode, but extended with module summaries.

Thin link: Thin linker plugin layer to combine summaries and perform global analyses.

ThinLTO backend: Parallel backends with summary- based importing and optimizations.ThinLTO: Scalable and Incremental LTO

上面幾個步驟沒有什么好說的，比較重要的是下面的這張圖，清晰展示了 ThinLTO Thin 在哪里，重點在于 summary 以及基于 summary whole program analysis。

• 每一個全局變量和函數都有一個 entry
• entry中包含一些metadata，用來驅動后面的global analysis
• function entry包含，linkage type，指令數量，可選的PGO信息，以及一些flag
• 另外所有的ref和函數調用關系都被記錄下來了。函數調用可以附帶有PGO hotness信息。

Thin Link主要是將不同 module 中的 summary 信息（又稱之為 summary index）聚合起來，合并成為一個summary index，然后基于這個 summary 做后續的分析。

Function Importing

Function Importing 是整個過程中比較重要的一步，對于一個 module 來說，只有其需要的函數才會被 import 到 module 中，這樣做可以減少開銷。所以這里的核心點是如何判斷一個函數是否需要 importing？目前論文中的判斷標準，就是這個函數足夠 hot 并且足夠小，從而能夠使得 inlining 從中受益。整個過程通過一個 threshold 來控制，未來如果需要對其進行擴展，只需要根據”其余判斷標準“調整 threshold 即可。

在 backend 進行真正的優化時，module 將其需要的 function import 進來（也就是拷貝進來）。這個過程在backend 的較早期進行，以便使得其它IPO收益。

如果需要 import 的函數引用了一個 local symbol（例如 static 修飾的變量），那么需要將這個 local symbol 的 scope 提升到全局 scope。需要 renamed。我們可以看到 ThinLTO 比 LIPO 更進一步，LIPO 是將 module 進行 grouping，但是 ThinLTO 只將需要 function 給 imoprt。另外需要注意的是，ThinLTO 也保留了接口基于 PGO profile data 來協助 function importing。

ThinLTO Cross-Module Optimizations

在 full LTO 中有一個比較重要的概念叫做 internalization，這個是針對 global symbol 來說的，如果說在把“所有”的 IR 都合并成為一個超大 IR 的時候，發現一些 symbol 不需要對外可見了，那么就將其進行internalize。與之類似的還有 visibility 問題。internalization有兩個好處，一是可以做dead symbol elimination ，二是可以做更精確與激進的分析，例如別名分析。通過 global reference graph ，ThinLTO 也可以做 internalization。

另外一個需要注意的點是 weak symbol resolution，這里引入了兩個概念 prevailing 和 preempted。如果 linker 選擇了 weak symbol 中的某一個 copy，將其它的丟棄，那么這個 symbol 就是 prevailing symbol，其它 symbol 就被 preempted 了（C：未來再介紹 linkage 相關的內容）

對于 indirect call promotioin 來說，PGO profile data 應該算是比較重要的了，用來告訴 optimizer，這個 call target 比較熱，值得你對代碼進行transform來做ICP。ThinLTO 的 summary 也保留了這部分的接口。

Integration with Profile Guided Optimization (PGO)

前面我們提到 ThinLTO 可以和 PGO 進行結合，profile data 放在 summary 中的 call 信息中，用來表征 hot or cold 。然后可以沿著 global call graph 進行 propagtion，用來協助做 function importing。

這篇文章只是論文閱讀到的內容，真正 ThinLTO 中實現的細節，未來再進行討論。

相關材料

• Optimizing large applications
• https://slideplayer.com/slide/7645018/
• https://gcc.gnu.org/wiki/LightweightIpo
• WHOPR - A scalable whole program optimizer for GCC
• https://gcc.gnu.org/wiki/LinkTimeOptimization
• https://llvm.org/devmtg/2016-11/Slides/Amini-Johnson-ThinLTO.pdf

總結

以上是生活随笔為你收集整理的论文阅读：ThinLTO: Scalable and Incremental LTO的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。