Profile-Guided optimization for Function Reordering: A Reinforcement Learning Approach
Weibin Chen, Yeh‐Ching Chung · 2022 IEEE International Conference on Systems, Man, and Cybernetics (SMC) · 2022
Profile-guided optimization (PGO) remains one of the most popular optimization strategies in code generation optimization. Function reordering is an essential step for profile-guided optimization. The state-of-the-art function reordering method performs on a unidirectional function call graph where nodes and edges define functions and caller-callee pairs. Each edge is labeled by its call frequency. However, we demonstrate that a bidirectional function call graph can represent the memory call better. We use a reinforcement learning algorithm SARSA to choose the appropriate order of functions by maximizing the total numbers of the function call through a bidirectional function call graph. In this paper, we use a self-developed tool to reordering functions. We first illustrate how our RL-based algorithm generates a new function order. Then we evaluate three algorithms on various applications, including Redis, Protobuf, and SPEC CPU benchmark. Our experiment results indicate that the new algorithm outperforms the other two algorithms in various applications, improving the resulting performance of practical applications. Especially on Redis, the performance is improved by 4.2% on SARSA, which is better than C3(3.4%) and ph (2.8%).