Hybrid evolutionary algorithm for graph coloring register allocation

Memory or registers are used to store the results of computation of a program. As compared to memory, accessing a register is much faster, but they are scarce resources and have to be utilized very efficiently. If the register set is not sufficient to hold all program variables, certain values have to be stored in memory and so-called spill code has to be inserted. The optimization goal is to hold as many live variables as possible in registers in order to avoid expensive memory accesses. We present a new hybrid evolutionary algorithm (HEA) for graph coloring register allocation problem for embedded systems. We have used MachineSUIF compiler research framework for implementing our algorithm.