Recursive Data Structures and Parallelism Detection

Interference estimation is a key aspect of automatic parallelization of programs. In this paper we study the problem of estimating interference in a language with dynamic data-structures. We focus on the case of binary trees to illustrate the approach. We develop a structural flow-analysis technique that allows us to estimate whether two statements influence disjoint sub-trees of a forest of dynamically-allocated binary trees. The method uses a regular-expression-like representation of the relationships between the nodes of the trees and is based on the algebraic properties of such expressions. We have implemented our analysis in Standard ML and have obtained some promising experimental results