# 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*