Efficient context-sensitive pointer analysis for C programs

TLDR

Partial transfer functions model procedure behavior under specific alias assumptions, and this work addresses applying them to real C programs that use type casts and pointer arithmetic by employing a low‑level memory representation. The paper proposes an efficient, context‑sensitive pointer‑analysis technique applicable to real C programs. The technique summarizes procedure effects with partial transfer functions that can be reused across contexts sharing the same input aliasing, implemented on a low‑level memory representation in SUIF, and runs efficiently on C benchmarks. Empirical results show that a single PTF per procedure typically suffices to achieve fully context‑sensitive analysis.

Abstract

This paper proposes an efficient technique for context-sensitive pointer analysis that is applicable to real C programs. For efficiency, we summarize the effects of procedures using partial transfer functions . A partial transfer function (PTF) describes the behavior of a procedure assuming 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 empirical results demonstrate that this technique is successful—a single PTF per procedure is usually sufficient to obtain completely context-sensitive results. Because many C programs use features such as type casts and pointer arithmetic to circumvent 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 algorithm in the SUIF compiler system and we show that it runs efficiently for a set of C benchmarks.