COMP 621 Program Analysis and Transformations (Winter 2009)

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

Announcements

Assignment #3 is posted, DUE April 14th.
Dates for Projects corrected. Project presentations start Monday, March 30th. Last class is TUESDAY, April 14th. Project reports due Monday April 20th (or accepted earlier - last day of term is Tuesday April 14th).
Project ideas posted, Feb 9, project proposal DUE Friday Feb 20
Assignment #2 posted, Feb 2, DUE Monday, Feb 16
Assignment #1 posted, January 14, DUE January 28.
First class is Monday, January 5, 2009. McConnell 103, 9:35-10:25

Special Topics and Project Presentations

Special Topics

Friday, March 6th
- Array Dependence Analysis (Nurudeen)
- Loop Parallelization and Vectorization (Toheed)
Monday, March 16th
- Program Dependence Graphs (Arash)
- Program Slicing (Theresa)
Wednesday, March 18th
- Loop Transformations for Scientific Computing (Ning)
- TBA (Arin)
Friday, March 20th
- BDDs for Points-to Analysis (PLDI 2003) (Maja)
- Context-sensitive Points-to, Is it worth it? (CC 2006) (Sameer)
Friday, March 27th
- Optimizing programs with dynamic types (Amina)
- Array bounds check elimination (Onur)

Projects

STARTS at 9:35: Monday March 30, Maja (1) and Toheed (2)
STARTS at 9:35: Wednesday April 1, Theresa (3) and Sameer (4)
STARTS at 9:20: Friday April 3, Kaiwen (5), Alex C. (6), and Arash (7)
STARTS at 9:20: Monday April 6, Alex L. (8), Neeraj (9) and Shamir (10)
STARTS at 9:20: Wednesday April 8, Ning (11), Nurudeen (12) and Arin (13)
STARTS at 9:20: Tuesday April 14, Amina (14), Jean-Sebastien (15) and Onur (16)

Subscribe to cs621-2009

Email:

Visit this group

About this course

Time: Mondays, Wednesdays and Fridays, 9:35-10:25
Place: McConnell 103
Who should take this course?
Course Outline (html) (postscript) (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

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)
Assignment 2 (.pdf) (.pdf 2-on-1) (.html)
Assignment 3 (.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 and AspectJ

  January 2009
S  M Tu  W Th  F  S
   *     *     *
4  5  6  7  8  9 10

Course Outline ((html), (ps) (pdf) )
Optimizing Compilers - How good are they? (pdf, 1-to-1) (pdf, 6-to-1)
AspectJ lecture notes as slides.
Introduction to AOP, Ch1 - Mastering AspectJ
AspectJ Quick Reference
AspectJ Grammar
Slides from class on AspectJ/abc
AspectJ: syntax basics , Ch 3 - AspectJ in Action.

Aho - Chapters 1 and 2 (for those with no previous compiler course)

Week 2: Intermediate Representations, Control Flow Analysis

    January 2008
 S  M Tu  W Th  F  S
11 12 13 14 15 16 17 
    *     *     *

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

Reading:

Muchnick - Chapter 4 - Intermediate Representations
Notes on SABS (.pdf)

Week 3: Intro to Dataflow Analysis and Soot Tutorial I

    January 2009
 S  M Tu  W Th  F  S
 18 19 20 21 22 23 24
    *     *     *

Dataflow Analysis
Reading:

Appel - Chapter 17 - Dataflow Analysis
Soot tutorials

Week 4: More Dataflow Analysis

    January 2009
 S  M Tu  W Th  F  S
25  26 27 28 29 30 31 
    *     *     *

Week 5: Fancy Abstractions and Intro to optimizations

   Feb 2009
 S  M Tu  W Th  F  S
 1  2  3  4  5  6  7
    *     *     *

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 2009
 S  M Tu  W Th  F  S
 8  9  10 11 12 13 14 
    *     *     **
                (ST)

Introduction to interprocedural analysis and optimizations
Reading:

Class notes
Muchnick - Chapter 15 - Procedure Optimizations

Week 7: Points-to Analysis

     February 2009
 S  M Tu  W Th  F  S
15  16 17 18 19 20 21
    *      *    *

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 2009     
Su Mo Tu We Th Fr Sa
 1  2  3  4  5  6  7
    *     *     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: Invariant Computations and Induction Variables

     March 2009     
Su Mo Tu We Th Fr Sa
 8  9 10 11 12 13 14
    *     *     *

Loop Invariant Computations
Induction Variables
Reading:

Muchnick - Chapter 14 - Loop Optimizations

Week 10: Special Topics Week

     March 2009     
Su Mo Tu We Th Fr Sa
15 16 17 18 19 20 21
   **    **    **
   (ST)  (ST)  (ST)

Week 11: Register Allocation and Instruction Scheduling

     March 2009
 S  M Tu  W Th  F  S
22 23 24 25 26 27 28
   *      *    **
               (ST)

Interference Graphs
Graph Colouring
Register Allocation
Simple Instruction Scheduling
Reading:

Appel - Chapter 11 - Register Allocation

Weeks 12 and 13: Project Presentations

     March/April 2009     
Su Mo Tu We Th Fr Sa
29 30 31  1  2  3  4
    *     *     *   
   PP     PP    PP

     April 2009     
Su Mo Tu We Th Fr Sa
 5  6  7  8  9 10 11
    *     *  
    PP    PP 

     April 2009     
Su Mo Tu We Th Fr Sa
 12 13 14 
        *   
        PP

Note: Tuesday April 14th is a class on the Friday schedule.
Final Reports Due Monday, April 20th.

Maintained by Laurie J. Hendren Last modified Thu Jan 3 12:12:16 EST 2008. [HOME]
Compiler research projects: Soot, a Java analysis, optimization and transformation toolkit ---- abc, an AspectJ compiler. (AspectJ)