Qualified Data Flow Problems

Abstract

It is known that not all paths are possible in the run time control flow of many programs. It is also known that data flow analysis cannot restrict attention to exactly those paths that are possible. It is, therefore, usual for analytic methods to considerallpaths. Sharper information can be obtained by considering a recursive set of paths that is large enough to include all possible paths, but small enough toexclude many of the impossible ones. This paper presents a simple uniform methodology for sharpening data flow information by considering certain recursive path sets of practical importance. Associated with each control flow arc there is a relation on a finite set Q. The paths that qualify to be considered are (essentially) those for which the composition of the relations encountered is nonempty. For example, Q might be the set of all assignments of values to each of several bit variables used by a program to remember some facts about the past and branch accordingly in the future. Given any data-flow problem together with qualifying relations on Q associated with the control flow arcs, we construct a new problem. Considering all paths in the new problem is equivalent to considering only qualifying paths in the old one. Preliminary experiments (with a small set of real programs) indicate that qualified analysis is feasible and substantialy more informative than ordinary analysis. The methodology also has a beneficial feedback effect on the delicate task of passing from programs to meaningful data flow analysis problems. Even when all paths qualify, unusually sharp information can be obtained by passing from programs to problems in ways suggested by theorems proved here. Copyright © 1981 by The Institute of Electrical and Electronics Engineers, Inc.