CMPUT 605-JIT  ADVANCED TOPICS IN COMPILERS: ON-DEMAND CONTEXT-SENSITIVE POINTER ANALYSIS Department of Computing Science  University of Alberta

Winter 2009

TIME: TR 1400-1520
INSTRUCTOR: José Nelson Amaral
 

Calendar Description:   Study the issues involved with the implementation of modular context-sensitive, flow-sensitive, and inclusion-based inter-procedural pointer analysis in an industrial-strength compiler infrastructure.

Course Description and Goals:

There is a vast literature describing many flavors of pointer and reference analysis. However no one has described an interprocedural analysis for the the C programming language that is at the same time flow sensitive, context sensitive, field sensitive, and inclusion based. There are several reasons that prevent the development of such an analysis: field-sensitivity is harder to implement in C than in Java because C allows the address of an structure field to be taken and manipulated in arbitrary ways. Full context-sensitivity may result in unwieldy spatial and temporal complexity when applied to large pointer-rich programs.

A recent trend in pointer and reference analysis is to limit the scope of the analysis by selecting a subset of variables in the program for which we demand accurate points-to information. Such analyses are called on-demand or incremental. The idea is that variables that are referenced in portions of the program that are candidates for potentially highly profitable code transformations should be analysed with more care to create more opportunities for such tranformations. For instance, variables that are referenced in loops that are candidates for auto-parallelization should be analysed more precisely than variables that are only referenced outside of loops.

The goal of this course is to study the recent literature on on-demand interprocedural pointer analysis and to discover the requirements to engineer an on-demand interprocedural analysis for a commercial compiler. At the end of the course the student should not only understand the trade-offs that must be negotiated in the implementation of such an analysis, but must also be able to propose a plausible set of algorithms and data structures that would be necessary to implement such an analysis framework in an industry-grade compiler.

Grading:

Class Presentations        30%
Homeworks                    20%
Practical Experiments    20%
Final Paper                      30%

Course Plan:

• January 06 - February 12: Literature Review:
  bi-weekly meetings for presentation/discussion of papers;
• February 13 - March 17: Requirements, Algorithm, Data Structure Design:
  student works independently to draft requirements docuemnt, design algorithms and required major data structures
• March 17 - April 15: Implementation and review:
  bi-weekly meetings to review implementation, and refine design;

Literature:

• M. Emami, R. Ghiya, L. J. Hendren, "Context-sensitive interprocedural points-to analysis in the presence of function pointers." PLDI 1994, pp. 242-246.
• J.-D. Choi, R. Cytron, J. Ferrante, "On the Efficient Engineering of Ambitious Program Analysis," IEEE Trans. on Soft. Enginer, Vol. 20, No. 2, Feb, 1994, pp, 105-114
• F. Chow, S. Chan, S.-M. Liu, R. Lo, M. Streich, "Effective Representation of Aliases and Indirect Memory Operations in SSA Form," CC 1996, pp. 253-167.
• J. Whaley, M. Rinard, "Compositional Pointer and Escape Analysis for Java Programs," OOPSLA 99, pp. 187-206.
• M. Fahndrich, J. Rehof, M. Das, "Scalable context-sensitive flow analysis using instantiation constraints," PLDI 2000, 253-263.
• M. Hind, "Pointer analysis: haven't we solved this problem yet?," Workshop on Program Analysis for Software Tools and Engineering, 2001, pp. 54-61.
• Alex Salcianu, "Pointer Analysis for Java Programs: Novel Techniques and Applications," Ph.D. Thesis, MIT, http://www.cag.csail.mit.edu/~salcianu/publications.html
• F. Vivien, M. Rinard, "Incrementalized Pointer and Escape Analysis," PLDI 2001, pp. 35-46.
• M. Berndl, O. Lhotak, F. Qian, L. Hendren, N. Umanee, "Points-to analysis using BDDs," PLDI 2003, pp. 103-114.
• Lhotak O., "Spark: A flexible points-to analysis framework for Java," M.Sc. thesis, School of Computer Science, McGill University, February 2003.
• E. M. Nystrom, H.-S. Kim, W. W. Hwu, "Importance of Heap Specialization in Pointer Analysis," PASTE 2004, pp. 43-48.
• D. Liang, M. Pennings, M. J. Harrold, "Evaluating the Impact of Context-Sensitivity on Andersen's Algorithm for Java Programs," PASTE05, pp. 6-12.
• B. Hackett, R. Rugina, "Region-Based Shape Analysis with Tracked Locations," POPL05, pp. 310-323.
• M. Sridharan, D. Gopan, L. Shan, R. Bodik, "Demand-Driven Points-to Analysis for Java," OOPSLA05, 59-76
• M. Sridharam, R. Bodik, "Refinement-Based Context-Sensitive Points-To Analysis for Java,", PLDI06, pp. 387-400
• O. Lhotak, L. Hendren, "Evaluating the benefits of context-sensitive points-to analysis using a BDD-based implementation," Transactions on Software Engineering and Methodology (TOSEM), September 2008.
• Chris Lattner, "Macroscopic Data Structure Analysis and Optimization," Ph.D. thesis, UIUC, http://llvm.org/pubs/2005-05-04-LattnerPHDThesis.html.
• C. Lattner, A. Lenharth, V. Adve, "Making context-sensitive points-to analysis with heap cloning practical for the real world," PLDI 2007, pp. 278-289.
• X. Zheng, R. Rugina, "Demand-Driven Alias Analysis for C," POPL 2008, pp. 197-208

University of Alberta

Computing Science