Interprocedural def-use associations for C systems with single level pointers

Abstract

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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>