Jan. 9, 2006: Website created, lecture notes posted.
Jan. 13, 2006: Lecture notes for Jan. 17 posted. Assignment 1 should be out by Jan. 17. There will be no lecture during reading week. The course now has a TA: Blair Fort.
Jan. 17, 2006: Assignment 1 posted.
Jan. 23, 2006: Lecture notes for the next lecture are posted on my website. They will appear on ccnet after I can log into it. I will cover the simple optimizations and the first part of data flow analysis tomorrow. I will cover the remainder of data flow analysis next week.
Jan. 31, 2006: Someone asked in class how to compute backward edges. You can use any of the approaches mentioned in class: dominators, depth first search, or both. Also, a typo has been found in Assignment 1. Your program needs to output the total number of loops when printing the natural_loops header and the corresponding line on page 2 should be: "natural_loops Feb. 6, 2006: I updated the last three slides of the Simple Optimizations lecture, and posted the lecture notes for Feb. 7. Also, the midterm will be on Monday, March 13, between 7pm and 9pm in GB304. Feb. 8, 2006: Assignment 2 has been posted. The assignment is due Thursday March 2nd 2006 at 9:59:59pm. The reference program will be made available soon, as will source code for a reference solution to assignment 1. Also, the TA will be in the computer lab on Monday February 27th. Feb. 13, 2006: I have put up a feedback form on ccnet that you can fill in over the next two weeks. Also, I have posted the lecture notes for tomorrow. Feb. 13, 2006: Assignment 1 marks have been made available. The TA will distribute the assignments tomorrow in class at 11:50. If you cannot pick your assignment up in class, please email the TA about picking it up from his cubicle. Feb. 27, 2006: Notes for tomorrow's lecture have been posted. I did not realize that the iron ring ceremony is on March 2nd. Assignment 2 is now due on Monday, March 6nd, at 11:59:59pm. The late penalty is 1 mark per day that the assignment is late (the assignment is out of 13). Please email all late assignments to me (bradel@eecg). Mar. 4, 2006: I posted all of the old midterms and exams for the course. I will not post links to these on ccnet. You can access them directly from www.eecg.utoronto.ca/~bradel/ece540_06/ Mar. 6, 2006: Notes for tomorrow lecture have been posted. Mar. 8, 2006: Assignment 3 has been posted. Mar. 11, 2006: I updated the IntroAndIRs, DFA, SimpleOpts, Redund, DeadCode, and LoopOpt slides. Almost all the changes are content that was covered in class. The full errata list is on the bulletin board. Mar. 13, 2006: Assignment 2 marks were posted yesterday. Notes for tomorrow's lecture have been posted. Mar. 18, 2006: The grades for the midterm have been posted. I will be in GB243 on Monday between 2pm and 3pm to give back the midterms. Once you receive your midterm please ensure that your mark has been entered correctly into ccnet. Mar. 20, 2006: The notes for Tuesday's class have been posted. Mar. 20, 2006: This year's midterm with solutions has been posted on this website (and not on ccnet). Also, I made a mistake when marking and gave a bonus mark to those people who I marked incorrectly. Mar. 20, 2006: I updated the CFA, DFA, DeadCode, RegAlloc, and DepAndPar slides. The errata can be found on the ccnet bulletin board. I also posted the LaTeX and DIA source code for the midterm. Mar. 21, 2006: Students have asked for an extension for Assignment 3. Assignment 3 is now due on Wednesday April 12, 2006 at 11:59:59 pm. Mar. 27, 2006: The lecture notes for tomorrow have been posted. Mar. 28, 2006: The Alias Analysis lecture slides have been updated. They will be updated again after today's class in preparation for next week. Mar. 30, 2006: I have a few announcements: 1. the assignment 3 description has been updated to include an explanation of the passkey file and stating that constant propagation is copy propagation and constant folding, 2. constant propagation is copy propagation and constant folding, 3. I have fixed the problem of certain lecture slides not being accessible, 4. Blair will be in the lab on April 10 to answer your questions about assignment 3, 5. the exam is scheduled for April 18 at 9:30am, and 6. I will give out the course evaluation forms at the end of class on April 4. Mar. 31, 2006: A student pointed out a mistake in the loop invariant
code motion algorithm slide (Redund, slide 28). The algorithm indicates
that an
instruction is movable even if the variables that it uses are defined in
instructions that are not movable. I'm guessing that a 4th necessary case
is that all variables used in s must be defined in instructions that have
been moved. I'll post a corrected algorithm as soon I check the Muchnick
book. Apr. 2, 2006: I looked in the Muchnick book. The condition that states "v is not defined elsewhere in L" is incorrect, and should be removed. There are only two conditions that are both necessary and sufficient, and no other conditions need to be added.
Apr. 4, 2006: I updated the Redundancy Optimizations and Alias Analysis slides. I have also added the slides for today's lecture. I added a little bit of text in the assignment 3 html page regarding constant propagation, referring people to today's lecture, which covers constant propagation. Finally, both the Muchnick and Dragon books have incorrect conditions for loop invariant code motion. I hope that the following four conditions result in correct code (see the Redundancy Optimization slides for more details):
Apr. 10, 2006: Assignment 3 is now due on Thursday April 13 at 11:59:59pm. Also, Blair will be in GB243 today during lab hours. Apr. 10, 2006: The SSA slides have been updated. I will go through them in tomorrow's class. Apr. 11, 2006: My supervisor, who originally created all the slides, has asked me to remove all of the powerpoint files from the website. The ps and pdf files are still accessible though. Apr. 12, 2006: I have created the exam. The exam has 12 questions. You are responsible for the material presented in all of the lectures. The exam will be held on Tuesday April 18 starting at 9:30am in BA3012 (according to www.ecf.utoronto.ca/apsc/registrar/Winter2006_Final_Exam_Schedule.htm). There will be a tutorial on Monday April 17 between 4pm and 7pm in PT473 (4th floor of DL Pratt). Please bring material that you want me to cover in the tutorial. Finally, the late penalty for assignment 3 is the same as for assignment 2: 1 mark per day (the assignment is worth 15 marks). Please email me the assignment file if you hand the assignment in late. Apr. 17, 2006: Today in the tutorial I was unable to do a software pipelining question and I said that I do not know an algorithm for software pipelining. You can infer what you will regarding the probability of software pipelining appearing on the exam. I figure it's only fair to let everyone know since the people in the tutorial made their own inference. Apr. 23, 2006: The marks for assignment 3 and the exam have been posted on ccnet. Class: T10-12 BAB026 PowerPoint 1 slide per page, PostScript 6 slides per page January 10, 2006: January 17, 2006: January 24, 2006: February 7, 2006: February 14, 2006: February 28, 2006: March 7, 2006: March 14, 2006: March 21, 2006: March 28, 2006: April 4, 2006: April 11, 2006: If you do not have an ugsparc account please contact me. Students with eecg accounts need to tell me their login id, and other students need to tell me their name, student number, and preferred login id. Assignment 1: Control Flow Analysis (12 marks) Word, ps Assignment 2: Data Flow Analysis (13 marks) Word, ps Assignment 3: Optimizations (15 marks) html The following are all the past tests that I could find, typos and all. Midterm Solution PDFs: 2002,2005 Exam Solution PDFs: 2003 This year's midterm: ps; solution: ps; LaTeX and DIA source for both tgz
Also, a reminder about the assignment 2 update announced by Blair: live variables should be defined in left to right order as printed by printsimple.
The conditions specified on slide 28 in Redund.ppt should be
1. BB s dominates all exits of L
2. all uses of v in L can only be reached by the definition of v in s
1. BB of s dominates all exits of L
2. v is not defined elsewhere in L (can be relaxed a little)
3. all uses of v in L can only be reached by the definition of v in s
4. all defs of u1,u2, are outside of the loop (initially or moved
Schedule
Labs: M1-4 GB243Notes
Introduction and Intermediate Representation ps
Control Flow Analysis pdf, ps
Data Flow Analysis pdf 0.5M, ps 4.9M
Simple Optimizations ps
Redundancy Optimization ps, pdf
Dead and Unreachable Code ps
Loop Optimizations ps
Register Allocation ps
Instruction Scheduling ps
Dependence Analysis/Automatic Parallelization ps
Locality Optimizations ps
Alias Analysis ps
Alias Analysis
Single Static Assignment Form and Constant Propagation ps
Single Static Assignment Form and Constant Propagation. Slides from last week.Assignments
The Simple-SUIF Compiler Guide
Using Simple-SUIF on the Ugsparcs
Word,
ps
Assignment due 9:59:59pm Monday Feb. 6, 2006
Assignment due 11:59:59pm Monday Mar. 6, 2006
Assignment due 11:59:59pm Thursday Apr. 13, 2006Tests
The archive contains files in a "midterm" directory. If you want to create ps or pdf files you will need, LaTeX, Dia (www.gnome.org/projects/dia/), and uoftexam.sty (www.chass.utoronto.ca/~osborne/latex/).Websites