預執行優化技巧是編譯器利用程式實際執行的行為來做優化，但前提 是先前收集到的程式特徵要和真實線上情況相近，否則預執行優化技 巧會傷害程式效能。這個研究討論在 LLVM 上的抽樣預執行優化的流 程，舉出了一些預執行優化降低程式效能的例子，並且嘗試以線性合 併靜態分支預測與收集到的程式特徵來做保守的預執行優化。實驗結 果顯示此方法在一些程式之中降低預執行優化的負面影響。

Profile Guided Optimizations (PGO) exploit runtime profile information from sample runs to predict the execution behavior of a program. However, the premise of PGO is that the profile of a sample run could likely represent the behavior of the program execution in general. In some conditions, this premise is not true, and when that happens, profile-guided optimizations may not help. Worse yet, they could significantly degrade the performance of the program. This work discusses the sampling profile guided optimizations adopted in LLVM and shows performance degradation of multiple pro- grams after PGO applied. We propose a conservative approach of using a linear combination of static branch prediction and the gathered branch profile from sample runs to guide optimizations. Such a combination has shown to be effective on reducing the negative impact of the original PGO in LLVM on multiple programs.

口試委員會審定書 iii
摘要 v
Abstract vii
1 Introduction 1
2 Background 5
2.1 Profile guided optimization 5
2.1.1 Instrumentation based 5
2.1.2 Sampling based 6
2.2 AutoFDO 7
2.3 SamplePGO in LLVM 7
2.4 LLVM Sample PGO Related Optimization 8
2.4.1 Function inline 8
2.4.2 Change select instruction to branch 8
2.4.3 Basic block frequency related optimization 8
3 Sampling PGO flow and Problem description 9
3.1 Flow of sampling PGO with perf, AutoFDO and LLVM 9
3.2 An example of performance impact of PGO 11
3.2.1 Original version from tutorial website 12
3.2.2 Modified version 12
3.3 Performance impact of 456.hmmer in SPEC2006 13
3.4 Problem Description 13
4 Experimental Evaluate 15
4.1 Implementation of linear combination of branch probability in LLVM 15
4.2 Experiment configure and benchmark description 16
4.3 Experiment results 16
4.4 Discussion 19
4.4.1 Bubble sort 19
5 Related Work 21
5.1 Sampling PGO and performance monitor unit 21
5.2 Evaluation of PGO 22
5.3 Multiple input handling in PGO 22
5.4 Sampling errors and rectifying 22
6 Conclusion 23
Bibliography 25

[1] Ivan Baev. 2012. Profile-based Indirect Call Promotion. LLVM Developers’ Meeting. (2012). Qualcomm Innovation Center.
[2] Paul Berube and José Nelson Amaral. 2007. Benchmark Design for Robust Profile-Directed Optimization. 2007 SPEC Benchmark Workshop. (2007).
[3] Paul Berube and José Nelson Amaral. 2012. Combined pro ling: A methodology to capture varied program behavior across multiple inputs. In 2012 IEEE International Symposium on Performance Analysis of Systems & Software, New Brunswick, NJ, USA, April 1-3, 2012. 210–220. https://doi.org/10.1109/ISPASS.2012.6189227
[4] Paul Berube, José Nelson Amaral, Rayson Ho, and Raúl Silvera. 2009. Workload Reduction for Multi-input Feedback-Directed Optimization. In Proceedings of the CGO 2009, The Seventh International Symposium on Code Generation and Optimization, Seattle, Washington, USA, March 22-25, 2009. 59–69. https://doi.org/10.1109/ CGO.2009.23
[5] Dehao Chen, David Xinliang Li, and Tipp Moseley. 2016. AutoFDO: automatic feedback-directed optimization for warehouse-scale applications. In Proceedings of the 2016 International Symposium on Code Generation and Optimization, CGO 2016, Barcelona, Spain, March 12-18, 2016. 12–23. https://doi.org/10.1145/2854038.2854044
[6] DehaoChen,Neil Vachharajani,Robert Hundt,Shih-wei Liao,Vinodha Ramasamy, Paul Yuan, Wenguang Chen, and Weimin Zheng. 2010. Taming hardware event samples for FDO compilation. In Proceedings of the CGO 2010, The 8th International Symposium on Code Generation and Optimization, Toronto, Ontario, Canada, April 24-28, 2010. 42–52. https://doi.org/10.1145/1772954.1772963
[7] Wei-Chung Hsu, Howard Chen, Pen-Chung Yew, and Dong-yuan Chen. 2002. On the Predictability of Program Behavior Using Different Input Data Sets. In 6th Annual Workshop on Interaction between Compilers and Computer Architecture (INTERACT-6 2002), 3 February 2002, Boston, MA, USA. 45–53. https://doi.org/10. 1109/INTERA.2002.995842
[8] Andi Kleen. 2013. pmu-tools. (2013). https://github.com/andikleen/pmu-tools
[9] Roy Levin, Ilan Newman, and Gadi Haber. 2008. Complementing Missing and Inaccurate Pro ling Using a Minimum Cost Circulation Algorithm. In High Performance Embedded Architectures and Compilers, Third International Conference, HiPEAC 2008, Göteborg, Sweden, January 27-29, 2008, Proceedings. 291–304. https: //doi.org/10.1007/978-3-540-77560-7_20
[10] David Levinthal and Dehao Chen. 2014. Gooda. (2014). https://github.com/David- Levinthal/gooda
[11] Diego Novillo. 2014. SamplePGO: the power of profile guided optimizations with- out the usability burden. In Proceedings of the 2014 LLVM Compiler Infrastructure in HPC, LLVM 2014, New Orleans, LA, USA, November 17, 2014. 22–28. https: //doi.org/10.1109/LLVM-HPC.2014.8
[12] Vinodha Ramasamy, Paul Yuan, Dehao Chen, and Robert Hundt. 2008. Feedback- Directed Optimizations in GCC with Estimated Edge Profiles from Hardware Event Sampling. In Proceedings of GCC Summit 2008. 87–102. http://www.capsl.udel.edu /conferences/open64/2008/Papers/113.pdf
[13] Baptiste Wicht, Roberto A. Vitillo, Dehao Chen, and David Levinthal. 2014. Hard- ware Counted Profile-Guided Optimization. CoRR abs/1411.6361 (2014). http: //arxiv.org/abs/1411.6361
[14] Bo Wu, Mingzhou Zhou,Xipeng Shen,Yaoqing Gao,Raúl Silvera, and Graham Yiu. 2013. Simple Profile Rectfications Go a Long Way - Statistically Exploring and Alleviating the Effects of Sampling Errors for Program Optimizations. In ECOOP 2013 - Object-Oriented Programming - 27th European Conference, Montpellier, France, July 1-5, 2013. Proceedings. 654–678. https://doi.org/10.1007/978-3-642-39038-8_27
[15] Ahmad Yasin. 2014. A Top-Down method for performance analysis and couters architecture. In 2014 IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS 2014, Monterey, CA, USA, March 23-25, 2014. 35–44. https://doi.org/10.1109/ISPASS.2014.6844459
[16] Mingzhou Zhou, Bo Wu, Xipeng Shen, Yaoqing Gao, and Graham Yiu. 2016. Examining and Reducing the Influence of Sampling Errors on Feedback-Driven Optimizations. TACO 13, 1 (2016), 6:1–6:24. https://doi.org/10.1145/2851502