language: en

Practical Comparison of call string and functional Approach in Data Flow Analysis *

Martin Alt Florian Martin
Universit�t des Saarlandes,
P.O. Box 151150, 66041 Saarbr�cken,
{alt�floriang}@cs.uni-sb.de June 10, 1997

Abstract The techniques which are used to implement interprocedural data flow analyzers can be generally divided into two parts: the call string and the functional approach [18]. Both differ in their time and space complexity as well as in the preciseness due to properties of the abstract domains and transfer functions. We have developed a data flow analyzer generator PAG [2] which is able to produce interprocedural analyzers for both techniques. We specified two variants of constant propagation working in an ANSI-C compiler; a copy constant propagation that uses distributive transfer function and can be solved precisely, even interprocedurally [13], and a full constant propagator which includes an interpreter for expressions of the language. We present the practical relevant results applying both analyzers to a rather fair set of real-world programs and compare the space/time consumption of the analyzers versus their preciseness.

1 Introduction