Making context‐sensitive inclusion‐based pointer analysis practical for compilers using parameterised summarisation. (22nd July 2013)

• Record Type: Journal Article
• Authors: Sui, Yulei; Ye, Sen; Xue, Jingling; Zhang, Jie
• Is Part Of: Software, practice & experience. Volume 44:Number 12(2014)
• Page Start: 1485
• Page End: 1510
• Publication Date: 2013-07-22
• Subjects: Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2214
• Languages: English
• ISSNs: 0038-0644

Abstract

<abstract abstract-type="main" id="spe2214-abs-0001"> <title>SUMMARY</title> <p id="spe2214-para-0001">Because of its high precision as a flow‐insensitive pointer analysis, Andersen's analysis has been deployed in some modern optimising compilers. To obtain improved precision, we describe how to add context sensitivity on top of Andersen's analysis. The resulting analysis, called <sc>ICON</sc>, is efficient to analyse large programs while being sufficiently precise to drive compiler optimisations. Its novelty lies in summarising the side effects of a procedure by using one transfer function on virtual variables that represent fully parameterised locations accessed via its formal parameters. As a result, a good balance between efficiency and precision is made, resulting in <sc>ICON</sc> that is more powerful than a 1‐callsite‐sensitive analysis and less so than a call‐path‐sensitive analysis (when the recursion cycles in a program are collapsed in all cases). We have compared <sc>ICON</sc> with <sc>FULCRA</sc>, a state of the art Andersen's analysis that is context sensitive by acyclic call paths, in Open64 (with recursion cycles collapsed in both cases) using the 16 C/C++ benchmarks in SPEC2000 (totalling 600 KLOC) and 5 C applications (totalling 2.1 MLOC). Our results demonstrate scalability of <sc>ICON</sc> and lack of scalability of <sc>FULCRA</sc>. <sc>FULCRA</sc> spends over 2 h in analysing SPEC2000 and fails to run to completion within 5 h for two of the five applications tested. In contrast, <sc>ICON</sc> spends just under 7 min on the 16 benchmarks in SPEC2000 and just under 26 min on the same two applications. For the 19 benchmarks analysable by <sc>FULCRA</sc>, <sc>ICON</sc> is nearly as accurate as <sc>FULCRA</sc> in terms of the quality of the built Static Single Assignment (SSA) form and the precision of the discovered alias information. Copyright © 2013 John Wiley & Sons, Ltd.</p> </abstract>