Optimising Compilers Past Paper

Basic concepts

basic block

• a maximal sequence of instructions,
  • each of which has exactly one predecessor (except possibly for the first) and
  • exactly one successor (except possibly for the last);
• a largest-possible piece of straight-line code which contains no interesting control flow, with each instruction being executed in turn.
• useful because they reduce the space and time requirements for analysis algorithms.
  • by allowing data flow info to be calculated and stored once per block rather than per instruction.
  • and recomputed inside a block when necessary.
• y2006p8q8 (a)

flow graph (node is 3-address code)

• the control flow graph of basic blocks has the same topology as of instructions (modulo straight bits).
• y2006p8q8 (b)

Control-flow

Unreachable code elimination

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

• y2011p7q13 (b)
  • vs. dead code elimination

Call graph

• y2013p9q9 (b)

if simplification

• y2023p8q9 (e)

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} in(n) = & \; \{ \} \; || \; \text{Op}_{p\in pred(n)} \; out(p) \\ pos_j(n) = & \; (pos_i(n) \setminus setI(n)) \cup setJ(n) \text{, depends on the property} \\ out(n) = & \; \text{Op}_{s\in succ(n)} \; in(s) \\ \end{aligned}$$

AVAILable expression analysis

• all paths to here include computation of it.

Reaching Definition (RD),

• some path to here includes a definition.
• y2015p7q11 (a, c-d), y2006p8q8 (d)
  • semantic, constant propagation

Write-write anomaly

• y2005p8q7 (a)
  • global variables or with address-taken variables

Live Variable Analysis (LVA)

• some path from here leads to a use.

Very Busy Expression (VBE), Must-use

• all paths from here lead to a use.
• y2009p9q10 (a)

Loop invariant expression

• y2021p9q12 (b)

Dominators analysis

• y2018p27q12 (c)

More: Use-Definition chain

General

• y2012p7q10 (c-f)
• y2010p7q12
• y2009p9q10 (b)
  • must-use-one-of
• y2008p8q8 (b)
  • security

Problem in data-flow analysis

• y2013p9q9 (b)
  • some variables hold the address.
• y2012p7q10 (e)

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}$$

For a variable $x$ at program point $p$,

• semantic liveness
  • some change to the value of x at p will cause the program to have different I/O execution results.
  • not generally computable.
• syntactic liveness
  • there is a path in the flowgraph (not necessarily followed in any execution) from p to a statement that reads the value of x.
  • a computable over-approximation.

Past papers,

• y2016p7q12 (a-b)
• y2024p8q9 (a, d, f)
• y2013p7q11
• y2011p7q13 (a, c)
  • semantic vs. syntactic liveness
• y2009p7q12 (a)

Data-flow anomalies

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

Dead code elimination

• y2023p9q9 (a)
  • compare AST, three-address code, and stack-based IR.
• y2023p8q9 (d)
• y2024p8q9 (e)

Definition, Reference, Un-definition

• y2012p7q10 (a-b)

Clash or interference graph

• y2017p9q10 (e)
• y2002p7q4 (a, b)
  • require iterated LVA since branching is inter-BB analysis.
• y2005p8q7 (b)
  • provide a program for given clash graph.

Register allocation

• map virtual registers to limited physical registers,
• allocate them optimally, i.e. keep data transfers between registers and memory to a minimum.
• via a graph colouring problem, where
  • variables are the nodes, the registers are colours and
  • edges between variables indicate that both variables are live at one time during execution.
• limitation for JIT compiler: layered opt. for cold / hot code.
  • NP-hard problem and thus slow with high complexity.

Past papers

• y2016p7q12 (d-e)
• y2013p9q9 (a)
• y2009p7q12 (b-e)
• y2002p7q4
  • SSA form gives more or less register count: fewer edges vs. more vertices.

Live range splitting

• y2017p9q10 (e)
  • minimum number of registers required

Static single assignment (SSA)

• y2018p27q12
  • static single assignment, dominance
• y2019p9q11 (c)
  • SSA form, register allocation and instruction scheduling
• y2015p7q11 (e)
• y2024p8q9 (b,c,f)
• y2013p9q9 (a)
• y2009p7q12 (f)
• y2006p8q8 (b-c)

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
• y2014p7q11 (a)
• y2008p8q8 (a)

Redundancy elimination

Common sub-expression elimination (CSE)

• y2023p8q9 (a)
• y2014p7q11 (b-d)
• y2007p8q8 (a, b)
  • Code motion transformation: where to move the code?

Copy propagation

• y2017p9q10 (d)
• y2023p8q9 (c)

Code hoisting (VBE analysis)

• y2023p8q9 (b)

Loop-invariant code motion (LICM)

• y2021p9q12
• y2014p7q11 (d)
• y2004p8q7 (b)

Partial redundancy elimination (CSE+LICM)

• y2008p8q8 (a.ii)

Higher-level opt

Strength reduction

• replaces expensive operations with less expensive operations.
  • Examples: replace $x^2$ by $x \cdot x$ or $\frac{x}{2}$ by right shift $x \gg 1$.
  • array access a[i] involves a (hidden) multiplication as *(a + 4*i), assuming that integers have a size of 4.
• y2004p8q7 (a)
  • loop

Abstract interpretation

• y2018p9q11
• y2012p9q9 (b,c)
• y2007p9q16 (a.i)

Strictness analysis

• it is safe to pass an argument by value (CBV) when
  • the function fails to terminate whenever the argument fails to terminate.
  • $\forall x. f^{\#}(x=\bot) = \bot$.
  • the abstract domain $D^\# = \{ \bot, \top \}$, where $\bot = 0$ is guaranteed non-termination and $\top = 1$ is possible termination.
• vs. neededness: the function will always evaluate its argument.
  • neededness $\subseteq$ strictness, since even if the parameter is not evaluated (needed), the termination behaviour of the function remains the same.

Past papers

• y2024p9q9
  • vs. neededness
• y2021p8q12
• y2016p9q9
• y2013p9q9 (d)
• y2012p9q9 (a,c)

Turn data-flow equations into strictness

• y2009p9q10 (c-d)

Conversion among abstract interpretation, set-constraint, rule-based analysis

• y2007p9q16 (b, c)
  • recursive calls

Constraint-based analysis

Set-constraint analysis

• y2007p9q16 (a.ii)

0CFA

• application: reordering or parallelisation.
• generate a tree and identify program points by labelling them,
• each program point with label $i$ gets a flow variable $\alpha_i$.

Past papers

• y2022p8q9
  • safe over-approximation, imprecise
• y2004p9q3

Turn data-flow equations into constraints

• y2015p9q9

Conversion among abstract interpretation, set-constraint, rule-based analysis

• y2007p9q16 (b, c)
  • recursive calls

Inference-based analysis

Rule-based analysis

• y2007p9q16 (a.iii)

Effect system

• y2020p8q12
  • Safety
• y2014p9q9
• y2008p9q16
• y2006p9q8
  • infer type and effect

Conversion among abstract interpretation, set-constraint, rule-based analysis

• y2007p9q16 (b, c)
  • recursive calls

Alias analysis

Points-to analysis (forward)

• y2013p9q9 (c)
  • vs. Anderson's analysis

Anderson's analysis

• y2019p8q11
• y2015p7q11 (b)
• y2011p9q8 (c-d)

Turn data-flow equations into constraints

• y2015p9q9 (d,e)

Conversion among abstract interpretation, set-constraint, rule-based analysis

• y2007p9q16 (b, c)
  • recursive calls

Instruction scheduling

target code level for different architectures

• y2017p7q12
  • Gibbons and Muchnick algorithm
• y2011p9q8 (a-c)
  • VLIW
• y2007p8q8 (b)

Register allocation vs instruction scheduling

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

Decompilation

Dominance

• y2018p27q12
  • static single assignment, dominance
• y2023p9q9 (b)

Optimisation

• y2010p9q10

General opt

Phase ordering

• y2019p9q11 (a)

General optimisations

• y2020p9q12