Program optimizations analyze and transform the programs such that better performance results can be achieved. Classical optimizations mainly use the static properties of the programs to analyze program code and make sure that the optimizations work for every possible combination of the program and the input data. This approach is conservative in those cases when the programs show the same runtime behaviors for most of their execution time. On the other hand, profile-guided optimizations use runtime profiling information to discover the aforementioned common behaviors of the programs and explore more optimization opportunities, which are missed in the classical, non-profile-guided optimizations. Redundancy elimination is one of the most powerful optimizations in compilers. In this thesis, a new partial redundancy elimination (PRE) algorithm and a partial dead code elimination algorithm (PDE) are proposed for a profile-guided redundancy elimination framework. During the design and implementation of the algorithms, we address three critical issues: optimality, feasibility and profitability. First, we prove that both our speculative PRE algorithm and our region-based PDE algorithm are optimal for given edge profiling information. The total number of dynamic occurrences of redundant expressions or dead codes cannot be further eliminated by any other code motion. Moreover, our speculative PRE algorithm is lifetime optimal, which means that the lifetimes of new introduced temporary variables are minimized. Second, we show that both algorithms are practical and can be efficiently implemented in production compilers. For SPEC CPU2000 benchmarks, the average compilation overhead for our PRE algorithm is 3%, and the average overhead for our PDE algorithm is less than 2%. Moreover, edge profiling rather than expensive path profiling is sufficient to guarantee the optimality of the algorithms. Finally, we demonstrate that the proposed profile-guided redundancy elimination techniques can provide speedups on real machines by conducting a thorough performance evaluation. To the best of our knowledge, this is the first performance evaluation of the profile-guided redundancy elimination techniques on real machines.
| Identifer | oai:union.ndltd.org:ADTP/242334 |
| Date | January 2006 |
| Creators | Cai, Qiong, Computer Science & Engineering, Faculty of Engineering, UNSW |
| Publisher | Awarded by:University of New South Wales. School of Computer Science and Engineering |
| Source Sets | Australiasian Digital Theses Program |
| Language | English |
| Detected Language | English |
| Rights | Copyright Qiong Cai, http://unsworks.unsw.edu.au/copyright |
Page generated in 0.0215 seconds