COMP 621 Program Analysis and Transformations (Winter 2012)

COMP 621 Program Analysis and Transformations (Winter 2012)
This web page has is currently being updated for Winter 2012. It will change throughout the term, so be sure to visit it often for updates.

Announcements

Feb 6, Assignment #2 is posted, due Thursday March 1
Feb 6, Project Topics posted, proposal due Thursday Feb 16
Jan 19, Lecture Notes for Week 2 added, see box below for Week 2
Jan 16, Assignment #1 is posted, due Feb 2. See box "Assignments and Projects" below.
Jan 16, TA office hours announced, TA info found here .
Jan 15, class time changed to 9:00-10:25.

Subscribe to comp621winter2012

Email:

Visit this group

About this course

Time: Tuesdays and Thursdays, 9:05-10:25
Place: McConnell 103
Course Outline (html) (pdf)

People

Lecturer - Professor Laurie Hendren
Teaching assistants

Java Resources

Java Documentation
JDK/SDK at SOCS and at home
Assembling/Disassembling Class Files

AspectJ Resources

abc AspectJ compiler
Eclipse AspectJ project
AspectJ Documentation

Sable Resources

McLAB

Sable Home Page
Soot Javadoc Pages
Soot Tutorials (includes information on options)
Soot-Eclipse Plugin
Getting the most recent Soot (nightly builds)

SABS - Sable Adaptive Benchmarking System

Assignments and Projects

Assignment 1 (.pdf) (.pdf 2-on-1) (.html)
benchmark_setup.template.m
Assignment 2 (.pdf) (.pdf 2-on-1) (.html)
Project Descriptions (.pdf) (.pdf 2-on-1) (.html)

Special Topic Slides

SpecialTopics2008

SpecialTopics2009

Week by week
(* = LECTURE, ** = SPECIAL DAY, ST = SPECIAL TOPIC, GL = GUEST LECTURE, PP = PROJECT PRESENTATIONS, NL = NO LECTURE)

Week 1: Introduction to Optimizations

  January 2012
S  M Tu  W Th  F  S
     *     *     
8  9 10 11 12 13  14

Course Outline ((html), (pdf) )
Aho - Chapters 1 and 2 (for those with no previous compiler course)

Week 2: Intermediate Representations, Control Flow Analysis

    January 2012
 S  M Tu  W Th  F  S
 15 16 17 18 19 20 21 
       *     *

Intermediate Representations
Basic Blocks
Control Flow Graphs (CFGs)
Control Flow Analysis
Loops and Dominators

Reading:

Muchnick - Chapter 4 - Intermediate Representations
Control Flow Analysis Lecture Notes
MATLAB and McLAB Intro Lecture Notes

Week 3: Intro to Dataflow Analysis and McLab Tutorial I

    January 2012
 S  M Tu  W Th  F  S
 22 23 24 25 26 27 28 
       *     *

Dataflow Analysis
Reading:

Appel - Chapter 17 - Dataflow Analysis

Week 4: More Dataflow Analysis

   January/February 2012 
 S  M Tu  W Th  F  S
29 30 31  1  2  3  4  
       *     *

Week 5: Intro to McSAF Analysis Framework and Intro to optimizations

   Feb 2012
 S  M Tu  W Th  F  S
 5  6  7  8  9  10 11  
       *     *

Intro to McSAF
More on dataflow analyses
Intro. to optimizations
Early optimizations
Reading:

Muchnick - Chapter 11 - Introduction to Optimizations
Muchnick - Chapter 12 - Early Optimizations

Week 6: Interprocedural Analysis

   February 2012
 S  M Tu  W Th  F  S
 12 13 14 15 16 17 18 
       *     *     
      (ST)  (ST)

Introduction to interprocedural analysis and optimizations
Reading:

Class notes
Muchnick - Chapter 15 - Procedure Optimizations

STUDY BREAK, Feb 20 to 24

Week 7: Points-to Analysis

February/March 2012
 S  M Tu  W Th  F  S
26 27 28 29  1  2  3  
      *      *   
     (ST)   (ST)

Alias pairs vs points-to relationships
Aliases due to call-by-reference
Aliases due to the & operator
Multi-level pointers
Handling Dynamically-allocated memory
Using the results of points-to analysis
Reading:

Context-Sensitive and Flow-Sensitive

Cont. Sens. Points-to Analysis (.ps)

Flow-Insensitive

Fast Points-to - POPL 96 (.ps)
Fast Points-to - McCAT (.ps)
Points-to and SPARK

Week 8: SSA and Global Value Numbering

     March 2012
Su Mo Tu We Th Fr Sa
4  5  6  7  8  9  10 
      *     *     
     (ST)  (ST)

SSA form
SSA numbers
Global Value Numbering
Reading:

Extended SSA Numbering
GVN handouts for slides
GVN notes for slides
Appel - Chapter 19 - SSA Form

Week 9: Register Allocation

     March 2012     
Su Mo Tu We Th Fr Sa
11 12 13 14 15 16 17
       *     *     
      (ST)  (ST)

Interference Graphs
Graph Colouring
Register Allocation
Simple Instruction Scheduling
Reading:

Appel - Chapter 11 - Register Allocation

Week 10: New Topics

     March 2012     
Su Mo Tu We Th Fr Sa
18 19 20 21 22 23 24 
      *    *    
      (ST) (ST)

Week 11: New Topics

     March 2012
 Su Mo Tu We Th Fr Sa
 25 26 27 28 29 30 31 
        *    *    
       (ST) (ST)

Week 12: No Classes, Project Work

     April 2012     
Su Mo Tu We Th Fr Sa
1  2  3  4  5  6  7 
      NL    NL (Easter)

Weeks 13 and 14: Project Presentations

     April 2012     
Su Mo Tu We Th Fr Sa
8  9  10 11 12 13 14 
      *     *  
     PP     PP

     April 2012     
Su Mo Tu We Th Fr Sa
15 16 17 18 19 20 21
       *       
       PP

Maintained by Laurie J. Hendren. Last modified Mon Jan 9 18:58:56 EST 2012.
Compiler research projects: Soot, a Java analysis, optimization and transformation toolkit ---- abc, an AspectJ compiler. ---- McLAB, a compiler and VM toolkit for MATLAB