Abstract
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 [MR79; DRZ92] and flow sensitive [Cal88; SL93] problems as well as many static analyses of concurrent programs with synchronization[CS88; DS91; MR93]. K-tuple frameworks, a subset of standard data flow frameworks [MR90; Hec77], provide a natural encoding for multisource problems using a single meet operator. Previously, the solution of these problems has been described as the xed 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, are 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.