Important Dates:

2/15: Research Proposal Group and Topic Identification
3/1: Deadline 1: ref list
3/8: Deadline 2: lit review outline
3/22: Deadline 3: background and lit review
4/6: Deadline 4: proposed idea from brainstorming session
4/18: Deadline 5: first complete draft
4/14: Quest 1
5/6: Deadline 6: Final proposal draft
5/17: Quest 2
Finals Week: Research Proposal Review (having read 3 proposals)

2/8: Introduction, Overview, and Organization of Talks

2/10: Intraprocedural Control Flow Analysis and Representation
Speaker: Lori
The Control Flow Graph - Definition, Construction, Properties
Refs: MU 7.1-7.5 or ASU 9.4, 10.4

2/15: Control Flow and Low-level Transformations
Speaker: Lori
Refs: MU ch 18

2/17: Data Flow Problems: Lattice Formulation, Examples, Classification
Speakers: Chris, Eric
Refs: MU ch 8.1-8.3, 8.5, 11.2

2/22: Using Data Flow Analysis for Code Optimization 1
Speaker: Lori
Constant propagation and folding, copy propagation, register allocation
Refs: MU 12.1-5, 16.1, 16.3

2/24: Using Data Flow Analysis for Code Optimization 2
Speakers: Antony
Redundancy Elimination: common subexpression elimination, loop invariant code motion, code hoisting, PRE
Refs: MU 13

3/1: Iteration-based Intraprocedural Data Flow Analysis
Speakers: Chris, Eric
Refs: MU 8.4, 8.6, 8.12

3/3: Going Interprocedural
Speakers: Emily, Sreedevi
The Call Graph and Supergraph
Refs: MU pp 609-11
Hall, Mary and Kennedy, Ken, ``Efficient Call Graph Analysis," ACM Letters on Programing Languages and Systems (LOPLAS), v.1, no. 3, 9/1992.
Myers, E.A., "A Precise Interprocedural Data Flow Algorithm," ACM SIGPLAN Symposium on Principles of Programming Languages, Jan. 1981, pp. 219-230

3/8: Procedure-level Transformations
Speakers: Pravesh, Liang
Refs: MU ch 15,
Tom Way and Lori Pollock, ``A Region-based Partial Inlining Algorithm for an ILP Optimizing Compiler," International Conference on Parallel and Distributed Processing Techniques and Applications, (PDPTA'02), June 2002.

3/10: Interprocedural Flow-sensitive side effect analysis
Speakers: Weirong, Songjie
Refs: MU 19.2.2, Call88

3/15: Interprocedural Data Flow Analysis Techniques
Speakers: Kalyan, Lori
Flow-insensitive side effect analysis
Refs: MU 19.2.1, CooK88b

3/17: Extending Program Analysis for Object-oriented Programs
Speakers: Sara, Emily
Ref: Souter dissertation (www.cis.udel.edu/~hiper) ch 2
Type and Class Hierarchy Analysis -

CHA: Ref: Jeffrey Dean, Greg DeFouw, Davie Grove, Vassily Litinov, Craig Chambers, ``Vortex: An optimizing compiler for object-oriented languages," OOPSLA 1996.

Rapid Type Analysis (RTA): Ref: Rapid Type Analysis (RTA): David Bacon and Peter Sweeney, ``Fast static analysis of C++ Virtual function calls," OOPSLA, 1996.

3/22: Data-flow-based Optimization for Object-oriented Codes -
Speakers: Vikram, Ryan
Selective specialization
Ref: Jeffrey Dean, Craig Chambers, and David Grove, ``Selective specialization for object-oriented languages, PLDI 1995.

3/24: Type analysis and call graph construction in OOP
Speakers: Jan, Kalyan
Refs: Greg DeFouw, David Grove, Jeffrey Dean, and Craig Chambers, ``Call graph construction in object-oriented languages," OOPSLA 1997.

or: ``A Framework for Call Graph Construction Algorithms," David Grove and Craig Chambers, ACM Transactions on Programming Languages and Systems, Vol 23, No. 6, November 2001.

4/5: Pointer Alias Analysis -
Flow-insensitive, context-insensitive:
Speakers: Pravesh, Liang
Refs: Bjarne Steensgaard, "Points-to Analysis in Almost Linear Time," ACM Symposium on Principles of Programming Langauges, 1996, pages 32-41

Flow-sensitive, context-sensitive:
Ref: Robert Wilson and Monica Lam, ``Efficient context-sensitive pointer analysis for C programs," PLDI 1995.

4/7: Flow-sensitive, context-insensitive:
Speakers: Antony
Ref: Donglin Liang and Mary Jean Harrold, ``Efficient points-to analysis for whole programs," FSE 1999.

4/12:Escape Analysis
Speakers: Vikram, Ryan
Refs: Jong-Deok Choi, Manish Gupta, Mauricio J. Serrano, Vugranam C. Sreedhar, Samuel P. Midkiff ``Stack Allocation and Synchronizatoin Optimizations for Java using Escape Analysis," ACM Transactions on Programming Languages and Systems (TOPLAS)", Volume 25 Issue 6, November 2003

4/14: Quest Number 1

4/19: Software Engineering Applications of Data Flow Analysis
Speakers: Dave
Def-use chains and Data Flow Testing -
Refs: MU 8.10,
Mary Jean Harrold and Mary Lou Soffa, "Efficient Computation of Interprocedural Definition-Use Chains," TOPLAS, Volume 16, No. 2, March 1994, pages 175-204.

Making analysis more scalable:

4/21: Static Single Assignment (SSA)
Speakers: Jan
Refs: MU 8.11, Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph," ACM Transactions on Programming Languages and Systems, Vol. 12, No. 4, October 1991, pages 451-490.

4/26: Program Dependence and System Dependence Graphs (Avoid all points/quantities)
Speakers: Lori
Refs: Jeanne Ferrante, Karl J. Ottenstein, Joe D. Warren, "The Program Dependence Graph and Its Use in Optimization," ACM Transactions on Programming Languages and Systems, Vol. 9, No. 3, July 1987, pages 319-349.

Susan Horwitz, Thomas Reps, David Binkley, "Interprocedural Slicing Using Dependence Graphs," ACM Transactions on Programming Languages and Systems, Vol. 12, No. 1, January 1990, pages 26-60.

4/28: Software Engineering Applications of Data Flow Analysis 2
Speakers: Divya, Madhusri
Program Slicing and Its Applications
Ref: A Survey of Program Slicing Techniques, Frank Tip, Journal of Programming Languages, 1995.

5/3: Software Engineering Applications of Program Analysis
Speakers: Ben
Impact Analysis and Software Maintenance/Regression Testing
Ref: ``A Comparison of Online and Dynamic Impact Analysis Algorithms," Ben Breech, Mike Tegtmeyer, Lori Pollock, CSMR 2005.

5/5:Demand Driven Data Flow Analysis
Speakers: Songjie, Weirong

Evelyn Duesterwald, Rajiv Gupta, Mary Lou Soffa, "A Practical Framework for Demand-driven Interprocedural Data Flow Analysis," ACM Transactions on Programming Languages and Systems, Vol. 19, No. 6, November 1997, pages 992-1030.

5/10: No Class
5/12: Path-based Techniques to eliminate paths and improve precision
Speakers: Divya, Madhusri
Refs: R. Bodik, R. Gupta, M.L. Soffa, "Refining Data Flow Information using Infeasible Paths," Proceedings of ACM SIGSOFT Symposium on Foundations of Software Engineering and Sixth European Software Engineering Conference, Sept. 1997.

Rastislav Bodik and Sadun Anik,"Path-Sensitive Value-Flow Analysis," POPL98.

5/17: Quest Number 2

Final Exam Class Period: Research Proposal Review Panel Session