Optimising Compilers Past Paper

Control-flow

Unreachable code elimination

Reachability, control-flow property: will the control reach here?

Call graph

Data-flow analysis framework

Data-flow equations: relationship between values of that property immediately before $in()$ and after $out()$ each node $n$ in a flow graph.

• y2017p9q10 (a)
  • General framework, propagating information either forwards (AVAIL) or backwards (LVA) through the flowgraph.
  • Operator: either the intersection $\cap$ (AVAIL) or union $\cup$ (LVA) is used, so as to under/over-approximate the property.

Let Position $pos_i$ or $pos_j$ be $in(n)$ / $out(n)$, the set of values $setA(n)$ / $setB(n)$ involved with the property immediately before / after the instruction. Depending on the property, one of the first or third equation with operator $Op=\bigcup_{} || \bigcap_{}$ is used in the data-flow equations.

  Nodes p
     |  pos = in(n)
  Node n : setA(n) <=> setB(n)  ...
     |  pos = out(n)
  Nodes s

$$\begin{aligned} pos_i(n) = & \; \{ \} \; || \; \text{Op}_{p\in pred(n)} \; pos_j(p) \\ pos_j(n) = & \; (pos_i(n) \setminus setI(n)) \cup setJ(n) \text{, depends on the property} \\ pos_i(n) = & \; \text{Op}_{s\in succ(n)} \; pos_j(s) \\ \end{aligned}$$

• y2015p7q11 (a, c-d)
  • semantic Reaching Definition analysis
  • constant propagation
• y2018p27q12 (c)
  • Dominators analysis
• More: Very Busy Expression analysis, Use-Definition chain

Live variable analysis (LVA)

Liveness, data-flow property: will the value be used later?

  ...
   ↑  in(n)
 Node n : def(n) => ref(n)  ...
   ↑  out(n)
 Nodes s

$$\begin{aligned} & in-live(n) = (out-live(n) \setminus def(n)) \cup ref(n) \\ & out-live(n) = \bigcup_{s\in succ(n)} in-live(s) \end{aligned}$$

• y2016p7q12 (a-b)

Data-flow anomalies

• y2017p9q10 (b), y2016p7q12 (c)
  • dead code & uninitialised variables

Clash / interference graph

Available expression analysis (AVAIL)

Availability, data-flow property: will the value be assigned before?

 Nodes p
   ↓   in(n)
 Node n : gen(n) <= kill(n)  ...
   ↓   out(n)
  ...

$$\begin{aligned} & in-avail(n) = \; \{ \} \; || \; \bigcap_{p\in pred(n)} out-avail(p) \\ & out-avail(n) = (in-avail(n) \setminus kill(n)) \cup gen(n) \end{aligned}$$

• y2017p9q10 (c)
  • semantic and syntactic expression availability, safe

Redundancy elimination

Common sub-expression elimination

Copy propagation

• y2017p9q10 (d.e.)

Code motion optimisation

Register allocation

• y2016p7q12 (d-e)

Static single assignment (SSA) and Strength reduction

• y2018p27q12
  • static single assignment, dominance
• y2019p9q11 (c)
  • SSA form, register allocation and instruction scheduling
• y2015p7q11 (e)

Higher-level opt

Abstract interpretation

• y2018p9q11

Strictness analysis

• y2021p8q12
• y2016p9q9

Constraint-based analysis (0CFA)

• y2022p8q9
  • safe over-approximation, imprecise

Inference-based analysis

Effect system

• y2020p8q12
  • Safety

Alias and points-to analysis

• y2019p8q11
• y2015p7q11 (b)

Instruction scheduling

target code level for different architectures

• y2017p7q12
  • Gibbons and Muchnick algorithm

Register allocation vs instruction scheduling

• y2022p9q9
  • Register allocation, instruction scheduling, optimisation
• y2019p9q11 (b,c)
• y2017p7q12 (d,e)

Decompilation

• y2018p27q12
  • static single assignment, dominance

General opt

Phase ordering

• y2019p9q11 (a)

General optimisations

• y2020p9q12