Dalvik Tracing JIT 最佳化 -- 去除冗餘例外檢查與低成本例外檢查實作

Abstract

本論文將會探討 Dalvik Tracing JIT 的特性，解釋為何現有的最佳化無法消除一些冗餘的 Null Pointer 檢查。 為解決此問題，本文提出一個以 SSA Renaming 為基礎的程式分析，用以消去這些冗餘檢查。對於「部分冗餘檢查 (Partial Redundant Check)」，本文亦善用 Tracing JIT 的特性，將迴圈內的檢查投機地移到迴圈外，以減少程式的執行時間。 除此之外，對於非冗餘的 Null Pointer 檢查，本文亦引入硬體中斷機制，利用「記憶體分頁存取保護」降低 Null Pointer 檢查在正常情況的執行成本。 根據實驗結果，本文提出之最佳化分別可以讓 LinPack 加快 20.08% 與 SciMark 2.0 加快 2.74%。至於最佳化的額外負擔，對於不常操作 Java 物件或陣列的 Benchmarks 沒有顯著的影響。

This thesis discusses several properties of Dalvik Tracing JIT and explains the reason why does the existing optimization or algorithm can't eliminate some redundant null pointer check. To solve this problem, this thesis proposed a new algorithm based on SSA renaming to eliminate these redundant checks. For the partial redundant checks, we can even take advantage of the Tracing JIT, and speculatively move the checks to the loop header so that we can reduce the number of instructions per iteration. For the non-redundant checks, this thesis utilize the hardware trap and page protection mechanism to reduce the run-time cost of the normal execution of the program. Our experimental results shows that our approach can speed up LinPack by 20.08% and SciMark 2.0 by 2.74%. For the benchmarks that seldom access Java objects or arrays, the overhead of our approach are negligible.