臺灣博碩士論文加值系統

Loop unrolling是一個相當知名的編譯器最佳化技巧，然而，由於Android Dalvik虛擬機採用Just-in-time的方式所以大部份的Loop unrolling機制並不適
用於此，詳細原因將在本論文的第二章節提到。
為了解決這個問題，我們使用一種名為Duff’s device的Loop unrolling技巧，在這種實作之下我們可以加入更多有關Loop unrolling的最佳化技巧，整體而言，
我們提升了Android知名benchmark約莫13%~14%的效能。

Loop unrolling is a well-known technique of the compiler optimization and has been widely used in many programming languages. However, most loop unrolling techniques are not suitable for Android Dalvik virtual machine because the Dalvik virtual machine applies Just-in-time compilation techniques. In Just-in-time compilation, codes are compiled to the binary at runtime, which means it’s more complicated to unroll the loop. The reason and the detail will be explained in chapter 2. To satisfy the requirements of applying loop unrolling in the Just-in-time compiler in Android Dalvik virtual machine, a mechanism called Duff’s device is conducted. In conclusion of our experiment, the
speedup on famous Android benchmarks is about 13~14%.

口試委員會審定書 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
誌謝 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
CONTENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
1. Introduction 1
1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Dalvik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3. Method-based and Trace-based JIT . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4. ART . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5. Dalvik and ART nowadays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2. Loop Unrolling 6
2.1. Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2. Why unrolling on dalvik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3. Mechanism of unrolling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4. Duff’s device . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3. Implementation 12
3.1. Loop structure of dalvik’s trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2. Unroll the loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3. Duff’s device . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.4. Preload and hoist load instruction . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.5. Optimization for basic induction variable . . . . . . . . . . . . . . . . . . . . . . 19
4. Experiment 23
4.1. Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2. Experiment result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5. Conclusion 26
5.1. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.2. Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Reference 28

1.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, San Francisco, California, USA, 1999, pp. 119-128.
2.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 systems Journal, vol. 39, no. 1, pp. 175-193, 2000.
3.T. Suganuma, T. Yasue, M. Kawahito, H. Komatsu, and T. Nakatani, "A dynamic
optimization framework for a Java just-in-time compiler." pp. 180-195.
4.H. Inoue, H. Hayashizaki, P. Wu, and T. Nakatani, "A trace-based Java JIT
compiler retrofitted from a method-based compiler." pp. 246-256.
5.H. Inoue, H. Hayashizaki, P. Wu, and T. Nakatani, “Adaptive multi-level compilation in a trace-based Java JIT compiler,” ACM SIGPLAN Notices, vol. 47,
no. 10, pp. 179-194, 2012.
6.D. Bornstein. Dalvik VM internals, 2008. https://sites.google.com/site/io/dalvik-vm-internals/
7.G. A. Perez, C.-M. Kao, Y.-C. Chung, and W.-C. Hsu, "A hybrid just-in-time compiler for android: comparing JIT types and the result of cooperation." pp. 41-50.
8.A. Gal, C. W. Probst, and M. Franz, "HotpathVM: an effective JIT compiler for
resource-constrained devices." pp. 144-153.

9.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.
10.IDC:Smartphone OS Market Share, Q1 2014.
http://www.idc.com/prodserv/smartphone-os-market-share.jsp
11.Fog, Agner (2012-02-29). "Optimizing subroutines in assembly language". Copenhagen University College of Engineering. p. 100. Retrieved 2012-09-22.
"12.11 Loop unrolling"
12.Duff, Tom. "Duff’s device." Usenet posting: http://www. lysator. liu.se/c/
duffsdevice.html (Nov 1983) (2008).