COMP 621 Program Analysis and Transformations (Winter 2013)

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

Announcements

April 3: Assignment #3 posted
March 26: Project Presentation Schedule posted
February 11: Assignment #2 posted
February 11: Project List posted
February 8: Special Topic Schedule posted
January 29: Special Topics posted
January 14: Assignment #1 posted
January 7: Assignment #0 posted
First class, Tuesday, January 8.

Subscribe to comp621-winter2013

Email:

Visit this group

About this course

Time: Tuesdays and Thursdays, 8:35 - 9:55
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

More will be posted here as the term progresses.

Assignment 0 (.pdf) (.pdf 2-on-1) (.html)
Assignment 1 (.pdf) (.pdf 2-on-1) (.html)
benchmark_setup.template.m
Assignment 2 (.pdf) (.pdf 2-on-1) (.html)
Assignment 3 (.pdf) (.pdf 2-on-1) (.html)
Special Topics(.pdf) (.pdf 2-on-1) (.html)
Special Topics Schedule (.pdf) (.pdf 2-on-1) (.html)
Project Descriptions (.pdf) (.pdf 2-on-1) (.html)

Project Presentations Schedule (.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 2013
S  M Tu  W Th  F  S
     *     *     
6  7  8  9 10 11 12

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

Week 2: Intermediate Reps, Control Flow Analysis

    January 2013
 S  M Tu  W Th  F  S
 13 14 15 16 17 18 19 
       *     *

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 2013
 S  M Tu  W Th  F  S
 20 12 22 23 24 25 26 
       *     *

Dataflow Analysis
Reading:

Appel - Chapter 17 - Dataflow Analysis

Week 4: More Dataflow Analysis and McLab Tutorial II

   January/February 2013 
 S  M Tu  W Th  F  S
27 28 29 30 31  1  2  
       *     *

Week 5: Intro to optimizations

   Feb 2013
 S  M Tu  W Th  F  S
 3  4  5  6  7  8  9  
       *     *

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 2013
 S  M Tu  W Th  F  S
 10 11 12 13 14 15 16 
       *     *

Introduction to interprocedural analysis and optimizations
Reading:

Class notes
Muchnick - Chapter 15 - Procedure Optimizations

Week 7: Points-to Analysis

February 2013
 S  M Tu  W Th  F  S
17 18 19 20 21 22 23  
      *      *   
     (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

     February/March 2013
Su Mo Tu We Th Fr Sa
24 25 26 27 28 1  2
      *     *     
     (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 2013     
Su Mo Tu We Th Fr Sa
10 11 12 13 14 15 16 
       *     *     
      (ST)  (ST)

Interference Graphs
Graph Colouring
Register Allocation
Simple Instruction Scheduling
Reading:

Appel - Chapter 11 - Register Allocation

Week 10: Special Topics

     March 2013     
Su Mo Tu We Th Fr Sa
17 18 19 20 21 22 23 
      *    *    
    (2ST) (2ST)

Week 11: Project Presentations

     March 2013
 Su Mo Tu We Th Fr Sa
 24 25 26 27 28 29 30 
        *    *

Week 12: Project Presentations

     March/April 2013     
Su Mo Tu We Th Fr Sa
31 1  2  3  4  5  6  
      *     *

Week 13 Guest Lectures, Week 14 No Lecture

     April 2013     
Su Mo Tu We Th Fr Sa
7  8  9  10 11 12 13 
      *     *  
      GL    GL 

     April 2013     
Su Mo Tu We Th Fr Sa
14 15 16 17 18 19 20 
       *       
       NL

Maintained by Laurie J. Hendren Last modified Sun Jan 6 18:47:15 EST 2013. [HOME]
Compiler research projects: Soot, a Java analysis, optimization and transformation toolkit ---- abc, an AspectJ compiler. ---- McLab, a compiler and VM toolkit for MATLAB