2016/08/15 by Josef Eisl, Matthias Grimmer, Doug Simon +2 · 2 citations
Computer Science · #Parallel Computing and Optimization Techniques #Logic, programming, and type systems #Software Testing and Debugging Techniques #Register allocation #Computer science #Allocator #Compiler #TRACE (psycholinguistics) #Just-in-time compilation #Parallel computing #Processor register #Dynamic compilation #Call graph #Profiling (computer programming) #Theoretical computer science #Programming language #Operating system
paper · doi:10.1145/2972206.2972211
openalex publication_date 2016/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
State-of-the-art dynamic compilers often use global approaches, like Linear Scan or Graph Coloring, for register allocation. These algorithms consider the complete compilation unit for allocation, which increases the complexity of the implementation (e.g., support for lifetime holes in Linear Scan) and potentially also affects compilation time. We propose a novel non-global algorithm, which splits a compilation unit into traces based on profiling feedback and subsequently performs register allocation within each trace individually. Traces reduce the problem size to a single linear code segment, which simplifies the problem a register allocator needs to solve. Additionally, we can apply different register allocation algorithms to each trace. We show that this non-global approach can achieve results competitive to global register allocation.