A compiler optimization framework for Concordia parallel C

In this thesis, we present the design and implementation of a compiler optimization framework for the Concordia Parallel C (CPC). CPC is the working language for the Concordia Parallel Systems Simulator (CPSS), whose purpose is to study interactions between parallel runtime systems and languages and their impacts on performance. The major challenge of designing a compiler optimization framework is to choose an appropriate Intermediate Representation (IR) that is able to support the solving of dataflow equations efficiently and applying corresponding transformations easily. The demanding issue in implementing such a framework is to make it general enough to meet the requirements of various dataflow analyses and transformations. We choose Control Flow Graph (CFG) as our intermediate representation because it is a general and mature compiler IR. We developed a two-pass algorithm that can build CFG from the CPC Abstract Syntax Tree (CPC-AST). Based on CFG representation, we implemented an optimization framework that can solve dataflow equations in either forward and backward manner. As a demonstration example, we showed how to solve the Common Subexpression Elimination (CSE) problem using the optimization framework. To make our optimization framework general yet efficient, we pay special attention on data structures used in our implementation. Sets are the common data structure used in describing dataflow equations and their solution algorithms. We use linked lists to represent sets and implement various set operations such as intersection, union and member on linked lists. Our optimization framework is general yet efficient to solve various compiler optimization problems including CSE, live variable analysis, and reaching definition. The experimental results show that the implemented CSE optimization does improve program performance