Elimination of parallel copies using code motion on data dependence graphs |
| |
Affiliation: | 1. Technical University of Denmark, Richard Petersens Plads, Building 322, 2800 Lyngby, Denmark;2. INRIA—ENS de Lyon, 46 Allee d''Italie, F-69364 Lyon Cedex 07, France;1. State Key Laboratory of Powder Metallurgy, Central South University, Changsha 410083, China;2. Sino-German Cooperation Group “Microstructure in Al alloys”, Central South University, Changsha 410083, China;1. National Engineering Laboratory for Hydrometallurgical Cleaner Production Technology, Institute of Process Engineering, Chinese Academy of Sciences, Beijing 100190, China;2. Key Laboratory of Green Process and Engineering, Institute of Process Engineering, Chinese Academy of Sciences, Beijing 100190, China |
| |
Abstract: | Register allocation regained much interest in recent years due to the development of decoupled strategies that split the problem into separate phases: spilling, register assignment, and copy elimination.Traditional approaches to copy elimination during register allocation are based on interference graphs and register coalescing. Variables are represented as nodes in a graph, which are coalesced, if they can be assigned the same register. However, decoupled approaches strive to avoid interference graphs and thus often resort to local recoloring.A common assumption of existing coalescing and recoloring approaches is that the original ordering of the instructions in the program is not changed. This work presents an extension of a local recoloring technique called Parallel Copy Motion. We perform code motion on data dependence graphs in order to eliminate useless copies and reorder instructions, while at the same time a valid register assignment is preserved. Our results show that even after traditional register allocation with coalescing our technique is able to eliminate an additional 3% (up to 9%) of the remaining copies and reduce the weighted costs of register copies by up to 25% for the SPECINT 2000 benchmarks. In comparison to Parallel Copy Motion, our technique removes 11% (up to 20%) more copies and up to 39% more of the copy costs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|