Efficient context-sensitive pointer analysis for C programs

Abstract

This paper proposes an efficient technique for context- sensitive pointer analysis that is applicable to real C pro- grams. For efficiency, we summarize the effects of pro- cedures using partial transfer functions. A partial transfer function (PTF) describes the behavior of a procedure assum- ing that certain alias relationships hold when it is called. We can reuse a PTF in many calling contexts as long as the aliases among the inputs to the procedure are the same. Our empir- ical results demonstrate that this technique is successful —a single PTF per procedure is usually sufficient to obtain com- pletely context-sensitive results. Because many C programs use features such as type casts and pointer arithmetic to cir - cumvent the high-level type system, our algorithm is based on a low-level representation of memory locations that safely handles all the features of C. We have implemented our algo- rithm in the SUIF compiler system and we show that it runs efficiently for a set of C benchmarks.