Def-use analysis links possible value-setting statements for a variable (i.e. definitions) to potential value-fetches (i.e. uses) of that value. This paper describes the first algorithm that calculates accurate interprocedural def-use associations in C software systems. Our algorithm accounts for program-point-specific pointer-induced aliases, though it is currently limited to programs using a single level of indirection. We prove the NP-hardness of the interprocedural reaching definitions problem and describe the approximations made by our polynomial-time algorithm. Initial empirical results are also presented.>

Incremental data flow analysis algorithms have been designed to deal efficiently with change in evolving software systems. These algorithms document the current state of a software system by incorporating change effects into previously derived information describing the definition and use of data in the system. Unfortunately, the performance of these algorithms cannot, in general, be characterized by analytic predictions of their expected behavior. It is possible, however, to observe their performance empirically and predict their average behavior. The authors report on experiments on the empirical profiling of a general-purpose, incremental data flow analysis algorithm. The algorithm, dominator based and coded in C, was applied to statistically significant numbers of feasible, random software systems of moderate size. The experimental results, with quantifiable confidence limits, substantiate the claim that incremental analyses are viable and grow more valuable as a software system grows in size.>