A safe approximate algorithm for interprocedural aliasing

TLDR

An alias is a name that refers to the same memory location, and determining aliases in pointer‑rich languages is ρ‑space‑hard. The paper proposes an algorithm for the Conditional May Alias problem to safely approximate interprocedural may aliasing with pointers. The algorithm achieves worst‑case precision and has been implemented in a prototype C‑program analysis tool. Initial experiments show promising speed and precision.

Abstract

During execution, when two or more names exist for the same location at some program point, we call them aliases. In a language which allows arbitrary pointers, the problem of determining aliases at a program point is ρ-space-hard [Lan92]. We present an algorithm for the Conditional May Alias problem, which can be used to safely approximate Interprocedural May Alias in the presence of pointers. This algorithm is as precise as possible in the worst case and has been implemented in a prototype analysis tool for C programs. Preliminary speed and precision results are presented.