One popular approach to improving the performance of fine-grain concurrent languages is to partition programs into threads. This requires static analysis to determine dependencies between tasks, to avoid placing a cycle within a thread. In the context of concurrent logic programming (CLP) languages, dependency analysis requires mode analysis. Simple argument modes are insufficient because dependencies can be hidden within complex terms.

This paper describes and compares four compile-time analysis algorithms, based on seminal work by Ueda and Morita, for deriving the path modes of concurrent logic programs. A path describes a subterm of a procedure argument. The analyses are based on constraint propagation over graphs, path partitioning, and model generation theorem proving. All four analyses were implemented in KLl to allow critical comparisons. We discuss the issues of completeness and complexity, and present empirical performance measurements for a benchmark suite, to determine utility. We show that the time and space requirements of the analysis is comparable to compilation, and that completeness is not problem for the programs studied.