Register Allocation Optimization with GRASP, Tabu Search, and Simulated Annealing: A Comparative Study

This paper explores the use of metaheuristics for register allocation in compilers, modeled as a graph coloring problem. Due to its NP-complete nature, exact methods are often impractical, while metaheuristics appear as alternatives. In this paper, we implement and compare three metaheuristics — Greedy Randomized Adaptive Search Procedure (GRASP), Tabu Search (TS), and Simulated Annealing (SA) — aiming to minimize conflicts under different color constraints. Experiments were conducted on DIMACS benchmark graphs to simulate limited-register scenarios. TS performed better on dense graphs, SA was more effective on regular and sparse ones, and GRASP showed competitive results in specific cases. The findings suggest that metaheuristics are promising tools for improving register allocation and reducing memory usage, especially under tight hardware constraints.