Practice Problems & Tests

Practice problems

• Practice 1
  • Parsing
  • Problems & solutions
• Practice 2
  • Syntax-directed translation, type checking
  • Problems & solutions
• Practice 3
  • Run-time environments, intermediate representations, code generation
  • Problems & solutions
• Practice 4
  • Dataflow analysis, optimization
  • Problems & solutions
• Practice 5
  • Instruction scheduling, register allocation, dependence analysis
  • Problems & solutions
• Practice 6
  • Value numbering, static single assignment (SSA)
  • Problems & solutions

Quizzes

• Quiz 1 - Thu Feb 27th
  • FIRST & FOLLOW, LL(1) parsing, LR(0) parsing
  • Practice problems 1
  • Practice midterm & solutions
  • Samples (Spring 09) - Quiz 1 (solutions), Quiz 2 (solution 2), Midterm 1 (solutions), Spring 11 (solutions)
  • Quiz - Spring 14 (solutions)

• Quiz 2 - Thu Apr 10th
  • Attribute grammars, syntax-directed translation, type checking, run-time environments, intermediate representations
  • Practice problems 2,3.1-2
  • Samples (Spring 09) - Midterm 1 (solutions), Midterm 2 (solutions), Spring 11 (solutions)
  • Quiz - Spring 14 (solutions)

Tests

• Midterm 1 - Thu Mar 13th
  • Parsing
  • Practice problems 1
  • Practice midterm & solutions
  • Samples (Spring 09) - Quiz 1 (solutions), Quiz 2 (solution 2), Midterm 1 (solutions), Spring 11 (solutions)
  • Test - Spring 14 (solutions)

• Midterm 2 - Thu May 1st
  • Quiz 2 topics, code generation, optimization, dataflow analysis (not including dataflow frameworks)
  • Practice problems 2, 3, 4.1-6
  • Examples - Spring 09 (solutions), Spring 11 (solutions)
  • Test - Spring 14 (solutions)

• Final Exam - Wed, May 21, 10:30am-12:30pm, CSI 1121
  • Covers everything (about 25-30% 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 phi-nodes
      • 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.7-8, 5.1, 5.2, 5.3a, 5.3b, 6.2a, 6.2d
  • Examples - Spring 09 (solutions)