Optimising Compilers

Work for each supervision is given below.

• First supervision
• Second supervision
• Third supervision
• Fourth supervision

Please email your solutions (PDF or text) 24 hours before the supervision, or put written work in the box at the CL student reception before midday the day before the supervision.

If you can't do a question after some thought, try to work out exactly where the problem lies and write down your working so far. We will discuss this in the supervision. Leave a question if you definitely haven't covered the material yet in lectures and can't work it out from the notes (apologies if this is the case).

• Course web page
• Past exam questions
• Lecture notes

• Short answer questions: (assume two or three marks each)
  1. How do basic blocks help to make intra-procedural analysis more efficient?
  2. Define the operations of analysis and transformation in an optimising compiler.
  3. What does it mean for a transformation to be safe?
  4. What is the safe interpretation of CALLI a (i.e. indirect call) in the analysis for unreachable-procedure elimination?
  5. Describe a case in which the undecidability of arithmetic may limit the possible transformations which can be performed in a program.
  6. What is the distinction between syntactic and semantic liveness?
• Exam question: CST 2006-08-08 parts a) and b)
  Basic blocks
• Exam question: CST 1998-08-07 parts a) to d)
  Available expressions
• Exam question: CST 2001-07-04
  Very busy expressions

• Short answer questions: (assume two or three marks each)
  1. How are non-orthogonal instructions in a target architecture handled when producing code and its associated register clash graph?
  2. What is a preference graph?
  3. Why might common subexpression elimination increase register pressure?
  4. Describe how copy propagation may reduce code size after the common subexpression elimination transformation has been performed.
  5. Strength reduction in a loop replaces recurring expensive operations with cheaper ones. Why might a compiler produce better target architecture code when strength reduction has not already been performed manually by the programmer?
• CST 2006-08-08 part d)
  Reaching definitions
• CST 2007-08-08 part b)
  Live ranges
• CST 2002-07-04
  Clash graphs, SSA
• CST 2005-08-07 part b)
  Clash graphs
• CST 2004-08-07
  Strength reduction, available expressions

• CST 2005-09-07
  Strictness analysis
• CST 2006-09-08
  Effect systems
• CST 2003-08-07
  Instruction scheduling, dependencies and register allocation
• CST 2002-09-07
  Instruction scheduling

• CST 2003-09-07
  Strictness analysis, escape analysis
• CST 2004-09-03
  Constraint-based analysis
• CST 2007-09-16
  Abstract interpretation, constraint-based analysis, rule-based analysis