Analyses of pointers, induction variables, and container objects for dependence testing

Many compiler optimizations rely on dependence tests to check the validity of the proposed transformations. Classical dependence tests focus primarily on array accesses with affine subscript expressions. These tests, however, often fall short when dealing with program features such as pointers, irregular subscripts, and object-oriented designs, which are common in today's high performance applications. In this thesis, we present three analyses that enable dependence tests for three types of objects: pointers, induction variables, and container objects.; The first analysis is a pointer analysis that is precise enough for iteration-based dependence tests. The analysis is presented in the context of Java. An iteration-based dependence test needs to disambiguate pointers from different iterations. Therefore, our method summarizes memory locations referenced by a pointer at every instance of a static program point. Such pointer information can also be used to eliminate redundant exception checks on Java references.; We then present an induction variable analysis that exploits IV information without closed form computation. Array subscripts involving induction variables are non-affine. In classical dependence analyses, such subscripts are handled by replacing occurrences of induction variables by their closed form expressions. Instead of computing closed form expressions, however, our method computes the value change of a variable along different control-flow paths. It then uses this information to discover that array references are dependence-free.; The last analysis targets container objects that are provided by standard libraries. Object-oriented design plays an increasing role in performance-critical codes. When dealing with general-purpose programs, arrays share their preeminence with more general container components, such as lists, sets, and hash-tables. We provide a pointer analysis that accurately models containers, iterators, and container-element connections. The analysis is an extension of Sagiv, Reps and Wilhelm's shape analysis for destructive updating. The output of the analysis can be interpreted as alias relations, shape properties, or connectivity.