Optimizing Compiler Code Generation

In an optimizing compiler, the tasks of back end is to translate the IR(Intermediate Representation) to efficient assembly representation. This thesis attacks two important issues in back end of an optimizing compiler: instruction selection and register allocation.Instruction selection is such a process that map the operations represented by IR to the operations represented by assembly language. Three widely used methods in instruction selection are representative instruction selection, pattern matching instruction selection and table driven instruction selection. In the basis of analyzing and comparing these three methods, an implementation of pattern matching instruction selection is provided. It is composed of three parts: machine description, machine description processor and pattern matching algorithm. This implementation not only ensure that the generated assembly codes are perfect, but also make the code generator itself highly retargetable.Register allocation is one of the most important optimization techniques in optimizing compiler. The dominant paradigm in modern global register allocation is graph coloring. Several styles of graph coloring register allocation is analyzed. A graph coloring register allocator is implemented and several new techniques are developed. First, a new definition for interference relation between variables is derived. Second, renaming, a technique orginates from supercompiler, is used in graph coloring register allocation. Third, a new extension on rematerialization in dealing with the spilled variables is approached. Besides global register allocation, local register allocation on basic block is also implemented. It cooperate with global register allocation in our methodology.