Knowledge-Augmented Genetic Algorithms for Effective Instruction Template Selection in Compilers

Compilers form one of the most basic components in computing today. The high-level programs used to form applications are translated to assembly code by the compiler, and subsequently to machine code by the assembler. Assembly code generation is preceded by the optimization phase, which reorganizes and modifies the program to give the best possible performance. But the instruction selection is as important as the optimization itself, since the underlying processing units only use the machine code, rather than the program logic. The complexity associated with the selection of instruction is that there might be multiple ways to perform an operation, and each method might be beneficial for a particular scenario. We may not be able to determine a universally beneficial method for all operations. Genetic Algorithms can be employed in this scenario since it is a randomized enumerative search strategy. It can eventually reach the optimal solution. We can encode the algorithm chromosomes using different indices for the different instruction templates, and perform the genetic operations on those chromosomes to yield good generations of results. Even if genetic algorithms don´t guarantee a globally optimal solution, it always improves on the current solution and after some runs, we are guaranteed to get a fairly acceptable result. Analysis shows that with some acceptable compromise on the compilation time, the knowledge - augmented genetic algorithm approach works in more than 80% of the cases.