COMP 621 Optimizing Compilers (Winter 2005)
This web page has been updated for Winter 2005, but it will change throughout the term, so be sure to visit it often for updates.

Announcements

  • Jan 30: Assignments #2 and #3 are posted. All course deadlines posted.
  • Jan 14: If you are not already very familiar with Unix, then you should attend the Unix seminars. More information at: http://www.cs.mcgill.ca/socsinfo/seminars/ . For this course the intermediate and advanced levels are appropriate.
  • Jan 10: Chris Pickett is the TA for this course. He has prepared an html page with directions for running Soot, see here . His office hours will be Tuesday 11:30-1:00, McConnell 234/226.

About this course

Time: Mondays and Wednesdays, 10:05-11: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
Java Benchmarks and Tools
JDK/SDK at SOCS and at home
Assembling/Disassembling Class Files

Sable Resources

Sable Home Page
Soot Javadoc Pages
Soot Tutorials

Assignments and Projects

Deadlines and Important Dates

  • Assignment 1 due, Monday, January 31
  • Assignment 2 due, Monday, February 14
  • Project Proposal due, Wednesday, February 16
  • Project update #1 due, Wednesday, March 2
  • Project update #2 due, Wednesday, March 16
  • Assignment #3 due, Monday, April 4
  • Project class presentations start - March 30 or April 4
  • Project reports due, Wednesday April 13

Week by week

Week 1: Introduction

  January 2005
S  M Tu  W Th  F  S
2  3  4  5  6  7  8  
      *
Course Outline ((html), (ps) (pdf) )
Optimizing Compilers - How good are they? (pdf, 1-to-1) (pdf, 6-to-1)

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

Special class on Tuesday, no class on Wednesday (only for this week).

Week 2: Intermediate Representations and Control Flow Analysis

    January 2005
 S  M Tu  W Th  F  S
 9 10 11 12 13 14 15 
    *     *
Intermediate Representations
Basic Blocks
Control Flow Graphs (CFGs)
Control Flow Analysis
Loops and Dominators

Reading:
Muchnick - Chapter 4 - Intermediate Representations

Week 3: Dataflow Analysis

    January 2005
 S  M Tu  W Th  F  S
 16 17 18 19 20 21 22 
    *     *
Dataflow Analysis
Reading:
Appel - Chapter 17 - Dataflow Analysis

Week 4: More Dataflow Analysis and Early Optimizations

    January 2005
 S  M Tu  W Th  F  S
23 24 25 26 27 28 29 
    *     *
Intro. to optimizations
Early optimizations

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

Week 5: Using the Soot/Eclipse Framework

   February 2005
 S  M Tu  W Th  F  S
 30 31 1  2  3  4  5  
    *     *
Reading:
Soot tutorials

Week 6: Optimizing Java

   February 2005
 S  M Tu  W Th  F  S
 6  7  8  9 10 11 12 
    *     *
Reading: Feng's references
  • Virtual Method Resolution
  • Using Attributes
  • Array Bounds Check Elimination

Week 7: Invariant Computations and Induction Variables

   February 2005
 S  M Tu  W Th  F  S
13 14 15 16  17 18 19 
    *     *
Loop Invariant Computations
Induction Variables

Reading:
Muchnick - Chapter 14 - Loop Optimizations

Study Break

   February 2003
 S  M Tu  W Th  F  S
20  21 22 23 24 25 26 

Week 8: SSA

     March 2005
 S  M Tu  W Th  F  S
 27 28 1  2  3  4  5  
    *     *
SSA form
SSA numbers
Global Value Numbering
Reading:
Extended SSA Numbering
Appel - Chapter 19 - SSA Form

Week 9: Pointer Analysis and Effects on Other Flow Analyses

     March 2005
 S  M Tu  W Th  F  S
 6  7  8  9 10 11 12 
    *     *

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

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

Flow Insensitive

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

Week 10: Register Allocation and Instruction Scheduling

     March 2005
 S  M Tu  W Th  F  S
13 14 15 16 17 18 19 
   *      *
Interference Graphs
Graph Colouring
Register Allocation

Reading:
Appel - Chapter 11 - Register Allocation

Week 11: Interprocedural Analysis and Procedure Optimizations

     March 2005
 S  M Tu  W Th  F  S
20 21 22 23 24 25 26 
   *      *
Reading:
Muchnick - Chapter 15 - Procedure Optimizations

Week 12: Project Presentations

     March/April 2005
 S  M Tu  W Th  F  S
 27 28 29 30 31 1  2  
   (hol)  *
Project presentations (if needed).

Week 13: Project Presentations

     April 2005
 S  M Tu  W Th  F  S
 3  4  5  6  7  8  9 
    *     *    
Project presentations.

Week 14: Project Presentations

     April 2005
 S  M Tu  W Th  F  S
10 11 12 13 14 15 16 
    *     * 
Project presentations
Final reports due April 13.

Maintained by Laurie J. Hendren Last modified Mon Jan 10 06:42:59 EST 2005. [HOME]
Compiler research projects: Soot, a Java analysis, optimization and transformation toolkit ---- abc, an AspectJ compiler. (AspectJ)