BitEA: BitVertex Evolutionary Algorithm to Enhance Performance for Register Allocation

Abstract

Register allocation is important in compiler design to enhance the execution time of programs, as CPU registers operate significantly faster than memory locations. The challenge of optimally assigning program variables to a limited number of CPU registers requires innovative solutions within constrained timeframes, particularly when traditional methods are not applicable due to computational infeasibility on current CPU architectures. This study introduces BitVertex Evolutionary Algorithm (BitEA), a novel approach grounded in bitwise operations and bit-based solutions, designed to accelerate computational performance in register allocation. Our experimental results show that BitEA outperforms the existing methods by a factor of up to 60 across all tested scenarios in the DIMACS benchmarks. Furthermore, in terms of solution quality, BitEA achieves lower chromatic numbers on 9 DIMACS benchmarks compared to its closest contemporaries. This research underscores that BitEA has potential to set a new standard for register allocation through its superior speed and solution quality.

Keywords

• Evolutionary optimization
• parallel processing
• register allocation
• graph coloring problem
• vertex-weighted graphs
• crossover operator