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):
- Anderson's Alias Analysis
- 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
- 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?
- Explain the analysis to determine whether variables X and Y might alias, giving the constraints that are generated by each of:
- Dominator Analysis
- Define what it means for a node in a flow graph to be a dominator of another.
- Give dataflow equations for calculating dominators of each node.
- What would indicate that we have found the back-edge of a loop?
- Are there any types of loop which this analysis might not detect?
Pete Calvert made the original selection of questions which I have adapted