Qualified Data Flow Problems

It is known that not aU 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 consider aU paths. Sharper information can be obtaine...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on software engineering 1981-01, Vol.SE-7 (1), p.60-78
Main Authors: Holley, L.H., Rosen, B.K.
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Analysis
Applied mathematics
Assembly
Availability
Computer languages
Computer programming
Computer science
Constraint optimization
Data
Data analysis
Data flow analysis
Engineering
Feedback
Flowcharts
global variable
interprocedural analysis
label variable
Mathematics
Methods
Operating systems
Path
Programming languages
Sets
Software
symbolic execution
Testing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:It is known that not aU 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 consider aU paths. Sharper information can be obtained by considering a recursive set of paths that is large enough to include aUl possible paths, but smaU enough to exclude 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 smaUl set of real programs) indicate that qualified analysis is feasible and substantialy more informative than ordinary analysis.
ISSN:0098-5589
1939-3520
DOI:10.1109/TSE.1981.234509