Optimization and garbage collection in Ada programs on shared memory computers

Candidate: Operowsky,Howard Lawrence

Abstract

Compiler development for Ada is still in its infancy. Despite its goal of supporting embedded systems in an efficient manner, Ada programs still tend to be large and slow. In this thesis, we investigate three issues related to the efficient implementation of Ada programs: run-time representation of types and objects, reduction of run-time constraint checking, and parallel garbage collection on a shared memory multiprocessor. We present a collection of type templates for scalar and composite types which are storage-efficient and allow for efficient object code to be produced by the code generator. We present an algorithm for constructing these templates at run-time when constraint information is unavailable at compile-time. We show that a global optimizer is not required to reduce the overhead of constraint checking in Ada programs. We present a series of data-flow equations for available expressions and use them as the basis for a simple algorithm to eliminate redundant constraint checks. The algorithm is syntax-directed and is executed in a single pass over the source program's abstract syntax tree. No control flow analysis is required. Our algorithm also includes constant propagation using an extended framework and induction variable analysis. Because the algorithm operates on the abstract syntax tree, induction variable analysis is simplified. Although programs with goto statements are not considered, the exit statement is handled fully. We also examine the effects of shared variables and exception handling. No commercial compiler for Ada currently performs garbage collection. We examine the difficulties in garbage collection presented by Ada and present practical algorithms for Ada on shared memory multiprocessors. We extend Kung and Song's on-the-fly garbage collection algorithm to support multiple tasks on the NYU Ultracomputer/IBM RP3 computers. We prove that no additional synchronization is required because of Ada's rules on the use of shared variables.