JavaScript is disabled for your browser. Some features of this site may not work without it.
Demand-Driven Alias Analysis for C

Author
Zheng, Xin; Rugina, Radu
Abstract
This paper presents a demand-driven, flow-insensitive analysis algorithm for answering may-alias queries. We formulate the computation of alias queries as a CFL-reachability problem, and use this formulation to derive a demand-driven analysis algorithm. The analysis uses a worklist algorithm that gradually explores the program structure and stops as soon as enough evidence is gathered to answer the query. Unlike existing techniques, our approach does not require building or intersecting points-to sets. Experiments show that our technique is effective at answering alias queries accurately and efficiently in a demand-driven fashion. For a set of alias queries from the SPEC2000 benchmarks, our analysis is able to accurately answer 97% of the queries in less than 1 millisecond per query. Compared to a demand-driven points-to analysis that constructs and intersects points-to sets on-the-fly, our alias analysis is more than two times faster.
Date Issued
2007-07-19Publisher
Cornell University
Subject
computer science; Programming Languages; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2007-2089
Type
technical report