HyperLink   Compaction algorithm for precise modular context-sensitive pointer analysis.
   
Publication Year:
  2003
Authors
  Hong-Seok Kim, Erik M. Nystrom, Ronald D. Barnes, Wen-mei Hwu
   
Published:
  IMPACT Technical Report, IMPACT-03-03, University of Illinois, Urbana, IL, 2003
   
Abstract:

Points-to analysis is a critical component of optimization and software engineering tools. A higher degree of precision in this analysis can significantly benefit such tools if it can be provided with a reasonably bounded analysis cost. The focus of this work is to enable a fully context-sensitive modular points-to analysis under the flow-insensitive and inclusionbased intraprocedural setting. Such a modular approach reduces the interprocedural problem to a series of intraprocedural ones. The main source of difficulty with such an approach is that the size of the module grows very quickly as they are built up as the bottom-up phase of the analysis proceeds. 

The main contribution of this work is compaction, an algorithm that produces a concise-yet-equivalent summary of a procedures module. It allows the modular points-to analysis to enjoy the full power of context sensitivity in a scalable fashion. Through empirical results, both the necessity and the effectiveness of the proposed techniques are demonstrated.