Optimising Compilers Past Paper

Basic concepts

basic block

flow graph (node is 3-address code)

Control-flow

Unreachable code elimination

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

Call graph

if simplification

Data-flow analysis framework

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

Let Position posipos_i or posjpos_j be in(n)in(n) / out(n)out(n), the set of values setA(n)setA(n) / setB(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=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

in(n)=  {}    Opppred(n)  out(p)posj(n)=  (posi(n)setI(n))setJ(n), depends on the propertyout(n)=  Opssucc(n)  in(s)\begin{aligned} in(n) = & \; \{ \} \; || \; \text{Op}_{p\in pred(n)} \; out(p) \\ % & \Updownarrow \\ pos_j(n) = & \; (pos_i(n) \setminus setI(n)) \cup setJ(n) \text{, depends on the property} \\ % & \Updownarrow \\ out(n) = & \; \text{Op}_{s\in succ(n)} \; in(s) \\ \end{aligned}

\cap \cup
pred AVAIL RD
succ VBE LVA

AVAILable expression analysis

Reaching Definition (RD),

Write-write anomaly

Live Variable Analysis (LVA)

Very Busy Expression (VBE), Must-use

Loop invariant expression

Dominators analysis

More: Use-Definition chain

General

Problem in data-flow analysis

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

inlive(n)=(outlive(n)def(n))ref(n)outlive(n)=ssucc(n)inlive(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 xx at program point pp,

Past papers,

Data-flow anomalies

Dead code elimination

Definition, Reference, Un-definition

Clash or interference graph

Register allocation

Past papers

Live range splitting

Static single assignment (SSA)

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)
  ...

inavail(n)=  {}    ppred(n)outavail(p)outavail(n)=(inavail(n)kill(n))gen(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}

Redundancy elimination

Common sub-expression elimination (CSE)

Copy propagation

Code hoisting (VBE analysis)

Loop-invariant code motion (LICM)

Partial redundancy elimination (CSE+LICM)

Higher-level opt

Strength reduction

Abstract interpretation

Strictness analysis

Past papers

Turn data-flow equations into strictness

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

Constraint-based analysis

Set-constraint analysis

0CFA

Past papers

Turn data-flow equations into constraints

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

Inference-based analysis

Rule-based analysis

Effect system

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

Alias analysis

Points-to analysis (forward)

Anderson's analysis

Turn data-flow equations into constraints

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

Instruction scheduling

target code level for different architectures

Register allocation vs instruction scheduling

Decompilation

Dominance

Optimisation

General opt

Phase ordering

General optimisations