Performing the Code Generation Phase of a Software Compiler Through Linear Genetic Programming

Mathew Carr, MSc. Dissertation, 2010, University of Liverpool

This dissertation considers the process of code generation in a compiler as a computer program induction and optimisation problem. The evolutionary computation method Linear Genetic Programming (LGP) is adapted for this task by use of a novel fitness function based upon methods a human programmer may consider to be good practice.

Download CD Image with Software, Source Code, Data, Progress Reports and Analyses

Download PDF

Abstract

This dissertation considers the process of code generation in a compiler: the task of transforming a program stored in some form of high level representation into a series of instructions in a low level language suitable for execution by a machine such as a computer. The problem is interpreted as one of computer program induction and optimisation.

The evolutionary computation method Linear Genetic Programming (LGP) is adapted for this task by use of a novel fitness function based upon methods a human programmer may consider to be good practice.

Two methods are considered, that of direct application of LGP and a second method which attempts to accelerate the process by subdividing the input program into smaller sections. The methods are compared and contrasted by considering the required computational effort to produce a solution to a series of sample programs, and the distribution of program lengths that result.

The dissertation concludes that LGP alone is not currently a suitable method for the task of code generation, but may act as a useful optimisation tool within some larger system.