臺灣博碩士論文加值系統

本論文將會探討 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.

Contents

口試委員會審定書 i
誌謝 ii
Acknowledgements iii
摘要 iv
Abstract v

1 Introduction 1
1.1 Context 1
1.2 Goal 3
1.3 Structure of the Thesis 4

2 Background 5
2.1 Java Programming Language 5
2.2 Java Virtual Machine 6
2.2.1 Instruction Set 6
2.2.2 Method JIT 6
2.2.3 Tracing JIT 7
2.3 Dalvik Virtual Machine 8
2.3.1 Instruction Set 8
2.3.2 Dex File and Zygote 8
2.3.3 Tracing JIT 9

3 Redundant Check Elimination 10
3.1 Motivation 10
3.2 SSA Renaming 12
3.3 Speculative Null Pointer Check Motion 15
3.4 Complete Algorithm 17

4 Hardware Trap 20
4.1 Motivation 20
4.2 Hardware Trap 20
4.3 Complete Algorithm 22

5 Evaluation 24
5.1 Environment 24
5.2 Microbenchmark 25
5.2.1 Integer Array Microbenchmark 25
5.2.2 Object Array Microbenchmark 26
5.2.3 Linear Trace Microbenchmark 27
5.3 Java Benchmark 30

6 Related Works 31
6.1 Null Pointer Checks Elimination 31
6.2 Array Bound Checks Elimination 33

7 Conclusion 35
7.1 Conclusion 35
7.2 Future Works 36

Bibliography 37

Bibliography
[1] A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools (2nd Edition). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2006.
[2] B. Alpern, C. R. Attanasio, J. Barton, M. G. Burke, P. Cheng, J.-D. Choi, A. Cocchi, S. Fink, D. Grove, M. Hind, S. F. Hummel, D. Lieber, V. Litvinov, M. F. Mergen, T. Ngo, J. R. Russell, V. Sarkar, M. J. Serrano, J. Shepherd, S. E. Smith, V. Sreedhar, H. Srinivasan, and J. Whaley. The Jalapeno virtual machine. IBM Systems Journal, 39(1):211–238, 2000.
[3] C. S. Ananian and M. Rinard. Static single information form. Technical report, Master’s thesis, Massachussets Institute of Technology, 1999.
[4] V. Bala, E. Duesterwald, and S. Banerjia. Dynamo: a transparent dynamic optimization system. In Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, PLDI ’00, pages 1–12, New York, NY, USA,
2000. ACM.
[5] R. Bodik. Gupta, and V. Sarkar. ABCD: Eliminating array bounds checks on demand. In Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, PLDI ’00, pages 321–333, New York, NY, USA, 2000. ACM.
[6] D. Bornstein. Dalvik VM internals, 2008. https://sites.google.com/site/io/dalvik-vm-internals/.
[7] B. Cheng and B. Buzbee. A JIT compiler for Android’s Dalvik VM, 2010. http://www.google.com/events/io/2010/sessions/jit-compiler-androids-dalvik-vm.html.
[8] D. D. I. F. Committee et al. DWARF debugging information format version 4, 2010.
[9] comScore/the Kelsey group. April 2013 u.s. smartphone subscriber market share. Press Release, June 2013. http://www.comscore.com/Insights/Press_Releases/2013/6/comScore_Reports_April_2013_U.S._Smartphone_Subscriber_Market_Share.
[10] R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Trans. Program. Lang. Syst., 13(4):451–490, Oct. 1991.
[11] A. Gal, C. W. Probst, and M. Franz. HotpathVM: an effective JIT compiler for resource-constrained devices. In Proceedings of the 2nd international conference on Virtual execution environments, VEE ’06, pages 144–153, New York, NY, USA, 2006. ACM.
[12] J. Gosling, B. Joy, G. Steele, and G. Bracha. Java Language Specification, Second Edition: The Java Series. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2nd edition, 2000.
[13] C. Haubl and H. Mossenbock. Trace-based compilation for the Java HotSpot virtual machine. In Proceedings of the 9th International Conference on Principles and Practice of Programming in Java, PPPJ ’11, pages 129–138, New York, NY, USA, 2011. ACM.
[14] J. L. Hennessy and D. A. Patterson. Computer Architecture, Fourth Edition: A Quantitative Approach. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2006.
[15] H. Inoue, H. Hayashizaki, P. Wu, and T. Nakatani. A trace-based java JIT compiler retrofitted from a method-based compiler. In Proceedings of the 9th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO’11, pages 246–256, Washington, DC, USA, 2011. IEEE Computer Society.
[16] K. Ishizaki, M. Kawahito, T. Yasue, M. Takeuchi, T. Ogasawara, T. Suganuma, T. Onodera, H. Komatsu, and T. Nakatani. Design, implementation, and evaluation of optimizations in a just-in-time compiler. In Proceedings of the ACM 1999 conference on Java Grande, JAVA ’99, pages 119–128, New York, NY, USA, 1999. ACM.
[17] M. Kawahito, H. Komatsu, and T. Nakatani. Effective null pointer check elimination utilizing hardware trap. SIGPLAN Not., 35(11):139–149, Nov. 2000.
[18] T. Kotzmann, C. Wimmer, H. Mossenbock, T. Rodriguez, K. Russell, and D. Cox. Design of the Java HotSpotTM client compiler for Java 6. ACM Trans. Archit. Code Optim., 5(1):7:1–7:32, May 2008.
[19] T. Lindholm and F. Yellin. Java Virtual Machine Specification. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2nd edition, 1999.
[20] H.-S. Oh, B.-J. Kim, H.-K. Choi, and S.-M. Moon. Evaluation of Android Dalvik virtual machine. In Proceedings of the 10th International Workshop on Java Technologies for Real-time and Embedded Systems, JTRES ’12, pages 115–124, New York, NY, USA, 2012. ACM.
[21] I. Rogers, J. Zhao, and I. Watson. Boot image layout for Jikes RVM. 2008.
[22] Y. Shi, K. Casey, M. A. Ertl, and D. Gregg. Virtual machine showdown: Stack versus registers. ACM Trans. Archit. Code Optim., 4(4):2:1–2:36, Jan. 2008.
[23] R. Sol, C. Guillon, F. M. Q. a. Pereira, and M. A. S. Bigonha. Dynamic elimination of overflow tests in a trace compiler. In Proceedings of the 20th international conference on Compiler construction: part of the joint European conferences on theory
and practice of software, CC’11/ETAPS’11, pages 2–21, Berlin, Heidelberg, 2011. Springer-Verlag.
[24] D. Spinellis and G. Gousios. Beautiful Architecture: Leading Thinkers Reveal the Hidden Beauty in Software Design. O’Reilly Media, Inc., 1st edition, 2009.
[25] T. Suganuma, T. Ogasawara, M. Takeuchi, T. Yasue, M. Kawahito, K. Ishizaki, H. Komatsu, and T. Nakatani. Overview of the IBM Java just-in-time compiler. IBM Syst. J., 39(1):175–193, Jan. 2000.
[26] T. Wurthinger, C. Wimmer, and H. Mossenbock. Array bounds check elimination for the Java HotSpotTM client compiler. In Proceedings of the 5th international symposium on Principles and practice of programming in Java, PPPJ ’07, pages 125–133, New York, NY, USA, 2007. ACM.