Multisource data flow problems involve information which may enter nodes independently through different classes of edges. In some cases, dissimilar meet operations appear to be used for different types of nodes. These problems include bidirectional and flow-sensitive problems as well as many static analyses of concurrent programs with synchronization. K-tuple frameworks , a type of standard data flow framework, provide a natural encoding for multisource problems using a single meet operator. Previously, the solution of these problems has been described as the fixed point of a set of data flow equations. Using our k -tuple representation, we can access the general results of standard data flow frameworks concerning convergence time and solution precision for these problems. We demonstrate this for the bidirectional component of partial redundancy suppression and two problems on the program summary graph. An interesting subclass of k -tuple frameworks, the join-of-meets frameworks, is useful for reachability problems, especially those stemming from analyses of explicitly parallel programs. We give results on function space properties for join-of-meets frameworks that indicate precise solutions for most of them will be difficult to obtain.

Non-concurrency analysis is a set of techniques for statically identifying pairs (or sets) of statements in a concurrent program which can never happen together. This information aids programmers in debugging and manually optimizing programs, improves the precision of data flow analysis, enables optimized translation of rendezvous, facilitates dead code elimination and other automatic optimizations, and allows anomaly detection in explicitly parallel programs. We present a framework for non-concurrency analysis, capable of incorporating previous analysis algorithms [CS88, DS92] and improving upon them. We show general theoretical results which are useful in estimating non-concurrency, and examples of non-concurrency analysis frameworks for two synchronization primitives: the Ada rendezvous and binary semaphores. Both of these frameworks have a low-order polynomial bound on worst-case solution time. We provide experimental evidence that static non-concurrency analysis of Ada programs can be accomplished in a reasonable time, and is generally quite accurate. Our framework, and the set of refinement components we develop, also exhibits dramatic accuracy improvements over [DS91], when the latter is used as a stand-alone algorithm, as demonstrated by our experiments.