This dissertation studies two related problems in data flow and control flow analysis of logic programs and provides efficient solutions.

The first part of the dissertation proposes a static analysis based on abstract interpretation to compute the data dependencies in a program; specifically, it derives precise information about sharing, freeness, and groundness of variables. This information is used in parallel execution and optimization of logic programs. The analysis has polynomial time complexity in the number of clauses and clause literals, and exponential worst-case complexity in the number of clause variables. In practice, the number of iterations required for computing the fixed-point appears to be independent of the height of the abstract domain and is usually less than five. A widening operation is used to accelerate convergence when computing the minimal function graph semantics of programs.

The second part of the dissertation provides a practical solution to the problem of simultaneous data flow and control flow analysis of logic programs. All analyses of logic programs to date have assumed that either control flow or data flow is known. We develop a framework for simultaneous data flow and control flow analysis. It is shown that a sub-problem in deriving control flow, namely, finding the set of all minimal permissible modes, is computationally intractable. We define a practical approximation algorithm and study its usefulness and complexity. The approximation algorithm derives minimal permissible modes for many non-trivial programs in polynomial time. A control flow for each clause and each entry substitution is then derived using the proposed framework and the approximation algorithm.

The simultaneous derivation of data flow and control flow in logic programs has many advantages. It results in a flexible control flow, uncovers more parallelism at compile­ time than previous proposals, and enables other program analysis such as compile-time memory reuse strategies. Above all, it moves logic programming a step closer towards the ideal of separating the logic and control aspects of a program.