Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Polymorphic versus Monomorphic Flow-insensitive Points-to Analysis for C (Extended Version)

Jeffrey S. Foster, Manuel Fahndrich and Alexander Aiken

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-00-1097
April 2000

http://www.eecs.berkeley.edu/Pubs/TechRpts/2000/CSD-00-1097.pdf

We carry out an experimental analysis for two of the design dimensions of flow-insensitive points-to analysis for C: polymorphic versus monomorphic and equality-based versus inclusion-based. Holding other analysis parameters fixed, we measure the precision of the four design points on a suite of benchmarks of up to 90,000 abstract syntax tree nodes. Our experiments show that the benefit of polymorphism varies significantly with the underlying monomorphic analysis. For our equality-based analysis, adding polymorphism greatly increases precision, while for our inclusion-based analysis, adding polymorphism hardly makes any difference. We also gain some insight into the nature of polymorphism in points-to analysis of C. In particular, we find considerable polymorphism available in function parameters, but little or no polymorphism in function results, and we show how this observation explains our results.


BibTeX citation:

@techreport{Foster:CSD-00-1097,
    Author = {Foster, Jeffrey S. and Fahndrich, Manuel and Aiken, Alexander},
    Title = {Polymorphic versus Monomorphic Flow-insensitive Points-to Analysis for C (Extended Version)},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2000},
    Month = {Apr},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2000/5230.html},
    Number = {UCB/CSD-00-1097},
    Abstract = {We carry out an experimental analysis for two of the design dimensions of flow-insensitive points-to analysis for C: polymorphic versus monomorphic and equality-based versus inclusion-based. Holding other analysis parameters fixed, we measure the precision of the four design points on a suite of benchmarks of up to 90,000 abstract syntax tree nodes. Our experiments show that the benefit of polymorphism varies significantly with the underlying monomorphic analysis. For our equality-based analysis, adding polymorphism greatly increases precision, while for our inclusion-based analysis, adding polymorphism hardly makes any difference. We also gain some insight into the nature of polymorphism in points-to analysis of C. In particular, we find considerable polymorphism available in function parameters, but little or no polymorphism in function results, and we show how this observation explains our results.}
}

EndNote citation:

%0 Report
%A Foster, Jeffrey S.
%A Fahndrich, Manuel
%A Aiken, Alexander
%T Polymorphic versus Monomorphic Flow-insensitive Points-to Analysis for C (Extended Version)
%I EECS Department, University of California, Berkeley
%D 2000
%@ UCB/CSD-00-1097
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2000/5230.html
%F Foster:CSD-00-1097