Abstract

As parallel systems become dominant in computer architectures, parallel programs that take the advantage of multiple threads of control are taking the place of conventional sequential programs. Yet, parallel programs have introduced new challenges to compiler static analyses and optimizations. On one hand, classical compiler analyses and optimizations need to be enhanced to handle the inter-thread interference and synchronization enforced dependence relation in a parallel program. On the other hand, new analyses and optimizations need to be designed for new programming language features.

In this dissertation we propose the following compiler static analyses and optimizations for parallel programs with synchronization: (1) An interprocedural multi-valued expressions analysis for both distributed and shared memory programs, based on program slicing. An expression is multi-valued if it evaluates differently in different threads. For Single Program Multiple Data style programs, multi-valued expressions analysis is a key component to determine the concurrent paths which are executed by different threads concurrently. (2) An interprocedural barrier matching technique for both distributed and shared memory programs to detect synchronization errors caused by the misplacement of barriers, or if the program is validated, to determine the set of barrier statements that synchronize together. (3) The first interprocedural concurrency analysis algorithm that can handle shared memory programs with textually unaligned barriers. (4) A new framework of flow-sensitive and synchronization-sensitive data flow analyses for shared memory programs. Pointer analysis is used as an example to demonstrate the effectiveness of this framework. The most significant advantage of this framework is that inter-thread interference and synchronization enforced dependence are modeled as concurrency relation, thus it is easily extensible to new language features and compatible with different memory models. (5) A lock assignment algorithm to optimize shared memory programs with atomic sections - a high-productivity synchronization construct that enforces atomicity and mutual exclusion. Taking a program annotated with atomic sections, the compiler automatically infers an assignment of the minimum number of locks to atomic sections so as to exploit the parallelism among atomic sections, without violating their semantics. Two additional lock optimization problems that are closely related to the lock assignment problem are presented.