Interprocedural Reaching Definitions in the Presence of Single Level Pointers

This paper describes the rst algorithm that calculates Interprocedural Def-Use Associations in C software systems. Our algorithm accounts for program-point-specic pointer-induced aliases, although it is currently limited to programs using a single level of indirection. We prove the NP-hardness of the Interprocedural Reaching Denitions Problem and point out the approximation made by our polynomial-time algorithm. Initial empirical results are also presented.Technical report LCSR-TR-19