Pathlistings applied to data flow analysis

Summary In this paper the pathlisting mechanism is developed as a new tool useful in performing efficient data flow analysis of programs for a wide variety of problems. An algorithm using this tool for forward flow, code improvement problems is presented. It is shown that for all practical purposes this algorithm is linear in the size of the input which is, generally speaking, a reducible flow graph modeling the given program. Pathlistings generalize the nodelisting approach, introduced by Kennedy, for solving data flow problems. The efficiency of the pathlisting algorithm is due to the reuse of intermediate values and due to the fact that the cycles of a reducible flow graph can be ordered. Other advantages of the approach are also discussed.Work supported by National Science Foundation grant DCR73-00365-AO