
Practice Problems & Tests
Practice problems
 Practice 1
 Practice 2
 Practice 3
 Runtime environments, intermediate representations, code generation
 Problems &
solutions
 Practice 4
 Practice 5
 Instruction scheduling, register allocation, dependence analysis
 Problems &
solutions
 Practice 6
Quizzes
 Quiz 1  Thu Feb 27th
 Quiz 2  Thu Apr 10th
Tests
 Midterm 1  Thu Mar 13th
 Midterm 2  Thu May 1st
 Final Exam  Wed, May 21, 10:30am12:30pm, CSI 1121
 Covers everything (about 2530% new material)
 New topics
Dataflow analysis & frameworks
 be able to solve a variety of dataflow problems
 understand properties of dataflow lattices & frameworks
 Instruction scheduling
 compute dependences between statements
 calculate critical path in DAG
 schedule instructions for single/multiple issue CPUs
 Register allocation
 compute live ranges
 build interference graph using live ranges
 globally allocate registers through coloring using graph simplification
 insert spill code
 Static single assignment
 calculate dominance frontiers
 determine where to insert phinodes
 not needed  dominator tree, iterated dominance frontiers
 Advance topics
 data locality  examples of temporal, spatial locality
 data dependence  loop independent, loop carried
 future  power, exploiting new hardware/language features
 Practice problems 4.78, 5.1, 5.2, 5.3a, 5.3b, 6.2a, 6.2d
 Examples 
Spring 09
(solutions)
