Intererence analysis tools for parallelizing programs with recursive data structures
Laurie Jane Hendren, Alexandru Eugen Nicolau · 1989
Interference estimation is a useful tool in developing parallel programs and is a key aspect of automatically parallelizing sequential programs. Interference analysis and disambiguation mechanisms for programs with simple data types and arrays have become a standard part of parallelizing and vectorizing compilers. However, efficient and implementable techniques for interference analysis in the presence of dynamic data-structures have yet to be developed. In this paper we study the problem of estimating interference in an imperative language with dynamic data-structures. We focus on developing efficient and implementable methods for regular recursive data-structures. We illustrate the approach by presenting a method for analysing trees and DAGs. In particular, we develop a structural flow-analysis technique that allows us to estimate whether two statements affect disjoint sub-trees of a forest of dynamically-allocated trees and DAGs. The method is based on a regular-expression-like representation of the relationships between accessible nodes in the forest. We have implemented our analysis and have obtained some very promising preliminary results.