Supervising - Optimising Compilers

Supervision 1

2006.8.8 Basic blocks, flow graph, C->ASM, SSA, RD
2001.7.4 Very busy expression (VBE) analysis, forwards vs backwards, data flow, call graph, unreachable procedure elimination
2008.8.8 Available expression analysis (AVAIL), CSE, security data flow
2005.8.7 write-write dataflow, RD, register colouring

Common problems: in-FOO and out-FOO equations are merely an intermediate stage in producing the FOO equations. Watch out for edge cases, initialisation conditions and remember to define all your terms.

Supervision 2

2009.7.12 liveness, semantic vs syntactic, register colouring, graph colouring
2002.7.4 (parts b and c) register interference, SSA, register colouring
2007.8.8 (part b) SSA, CSE, spilling, instruction scheduling
2004.8.7 strength reduction, loop invariant lifting, AVAIL

Supervision 3

2003.9.7 Strictness analysis, escape analysis (control flow analysis), abstract analysis
2009.9.10 flow graphs, strictness analysis, abstract analysis
2004.9.3 Alias analysis, lambda calculus
2002.8.7 Effect systems

Supervision 4

2002.9.7 Instruction scheduling
1999.9.7 (Discussions a/b, not the first 14 marks) instruction scheduling, register colouring
2011.9.8 Instruction scheduling, VLIW, alias analysis, Andersen's algorithm
2010.9.10 Decompilation (potentially a rather evil question, leave until last)

There are few past questions on either Anderson's alias analysis, or decompilation. So please just answer the following as well (Questions by Pete Calvert):

1. Anderson's Alias Analysis
   1. Explain the analysis to determine whether variables X and Y might alias, giving the constraints that are generated by each of:

      x := new_l	x := null	x := &y
      x := y		x := *y		*x := y
      

   2. So far our analysis does not include field accesses (x.f = e and x.g = e are both treated as *x := e). What difficulties can you see in adding these?
2. Dominator Analysis
   1. Define what it means for a node in a flow graph to be a dominator of another.
   2. Give dataflow equations for calculating dominators of each node.
   3. What would indicate that we have found the back-edge of a loop?
   4. Are there any types of loop which this analysis might not detect?

Pete Calvert made the original selection of questions which I have adapted