2 of 34

Advanced Optimizations

Type Analysis

Where possible, determine the type of an operand (Type check elimination)

Shape Analysis

Where possible, determine the shape of an operand
Example: a record {a : 1, b : 2} has the set of fields {a, b}

Value Analysis

Where possible, determine the value of an operand (Constant Propagation)

Dependence and Liveness Analysis

Dead code elimination
Register Allocation

Takeaways:

Much to be infer about a program that can be leveraged for optimization
IR serves as a way to encode this information in the representation

Interpret or code gen from transformed program rather than carry aux information
Optimizations can interact and may need to run multiple times. IR serves as uniform encoding

3 of 34

Much much more….

P5 overview includes pointers to many other optimizations
6.035: (More dataflow optimizations (common subexpression elimination, automatic parallelization, data layout optimizations)
C294 @ Berkeley: http://www.wolczko.com/CS294/

5 of 34

Takeaway of Optimization

Rich landscape of optimizations…. developed since the 1960s.

“Frances Allen’s 1966 paper, Program Optimization, laid the �conceptual basis for systematic analysis and transformation �of computer programs.” – ACM Turing Award Citation�

Use benchmarks to guide selection of optimizations

6 of 34

Last Time

Type Analysis

Shape Analysis

Value Analysis

- Stack Caching

7 of 34

Last Time (How?)

Type Analysis

Shape Analysis

Value Analysis

- Stack Caching

8 of 34

Intermediate Representation (Illustrative)

Operands

Constants (1, 2, 4, 3)
Registers (r1, r2, …) (finite set according to ISA)
Virtual Registers (aka, ”Temporaries”) (t1, t2, …)

Types

Integer, Bool, String, .. Etc
New Types

int32 – a primitive integer value (sometimes called unboxed vs boxed above)

Instructions

Simple “three address code” or register transfer language (RTL)

Op <register>
<register> = op
<register> = opcode <operand>
<register> = opcode <operand> <operand>

<register> = load_local <op 0>, <register> = load_const <op 0>
<register> = assert_integer <operand>
<register> = get_integer <operand>
<register> = sub_int32 <operand> <operand>

9 of 34

Stack to Three-Address Code

Stack
t1

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_const_2 2

return

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

]

}

(Code after Type and Constant Analysis)

10 of 34

Stack to Three-Address Code

Stack
t1

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_const_2 2

return

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

]

}

11 of 34

Stack to Three-Address Code

Stack
t2

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

t2 = assert_integer t1

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_const_2 2

return

]

}

12 of 34

Stack to Three-Address Code

Stack
t3

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

t2 = assert_integer t1

t3 = get_integer t2

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_const_2 2

return

]

}

13 of 34

Stack to Three-Address Code

Stack
t4

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

t2 = assert_integer t1

t3 = get_integer t2

t4 = sub_int32 t3 2

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_const_2 2

return

]

}

14 of 34

Stack to Three-Address Code

Stack

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

assert_integer

get_integer

sub_const_2 2

return

]

}

function {

parameter_count = 1

local_vars = [y, x],

constants = [None, 2],

instructions = [

t1 = load_local 0

t2 = assert_integer t1

t3 = get_integer t2

t4 = sub_int32 t3 2

return t4

]

}

15 of 34

Virtual Machine Showdown: Stack Versus Registers

Yunhe Shi, David Gregg, Andrew Beatty, and M. Anton Ertl

Which is a better virtual machine specification?

Representation size, performance, etc

Translations and Optimizations

Copy Propagation
Dead code elimination

16 of 34

Is a Constant in s = s+a*b?

s = 0;

a = 4;

i = 0;

k == 0

b = 1;

b = 2;

i < n

s = s + a*b;

i = i + 1;

return s

Yes!

On all reaching

definitions

a = 4

17 of 34

Constant Propagation Transform

s = 0;

a = 4;

i = 0;

k == 0

b = 1;

b = 2;

i < n

s = s + 4*b;

i = i + 1;

return s

Yes!

On all reaching

definitions

a = 4

18 of 34

Is b Constant in s = s+a*b?

s = 0;

a = 4;

i = 0;

k == 0

b = 1;

b = 2;

i < n

s = s + a*b;

i = i + 1;

return s

No!

One reaching

definition with

b = 1

One reaching

definition with

b = 2

19 of 34

How? Static Analysis: Key Concepts

Facts

Space of properties to track (a set, properly a lattice to support control flow, loops, and reasoning about termination)

Symbolic/Abstract Execution

How to specify the effect of a basic block on facts? Transfer Functions

Merging

How to merge from multiple branches? (joins and and meets)

Algorithm

How to compute? Chaotic Iteration

Termination

When does an analysis terminate? (Fixpoints)

20 of 34

Chaotic Iteration

y=0;

t=1;

x=x+1;

y=y+2;

t=t+2;

y=t-1;

end

21 of 34

General Analysis Framework

Dataflow Analysis

Developed by Kildall in 1973
Traditionally used for compiler optimization

Abstraction Interpretation

Developed by Cousot and Cousot, 1977
Similar in intent, but more richly developed than dataflow

Frame analysis question as a set of equations on a CFG

22 of 34

FORMAL FRAMEWORK

23 of 34

Key Concepts

Facts

Space of properties to track (a set, properly a lattice to support control flow, loops, and reasoning about termination)

Merging

How to merge from multiple branches? (joins and and meets)

Symbolic/Abstract Execution

How to specify the effect of a basic block on facts? Transfer Functions

Algorithm

How to compute? Chaotic Iteration

Termination

When does an analysis terminate? (Fixpoints)

24 of 34

Is a Constant in s = s+a*b?

s = 0;

a = 4;

i = 0;

k == 0

b = 1;

b = 2;

i < n

s = s + a*b;

i = i + 1;

return s

Yes!

On all reaching

definitions

a = 4

25 of 34

Fact/Property

26 of 34

Analysis: Set of Facts/Properties

An analysis is a set of facts/properties that it tracks.
Constant Analysis

Variable has a fact in Z that denotes its known value
Example: Constant propagation

Sign Analysis

A variable has a fact in {0, positive, negative}

Range Analysis

Variable has a fact in the set of closed intervals [a, b], where a and b are integers
Example: trim size of integer representation or check for overflow

Mark Stephenson, Jonathan Babb and Saman Amarasinghe,�Bidwidth analysis with application to silicon compilation, PLDI'00

Value Set

Track set of values of variable
Example: specialize code to small set of values

27 of 34

Key Concepts

Facts

Space of properties to track (a set, properly a lattice to support control flow, loops, and reasoning about termination)

Merging

How to merge from multiple branches? (joins and and meets)

Symbolic/Abstract Execution

How to specify the effect of a basic block on facts? Transfer Functions

Algorithm

How to compute? Chaotic Iteration

Termination

When does an analysis terminate? (Fixpoints)

28 of 34

Is b Constant in s = s+a*b?

s = 0;

a = 4;

i = 0;

k == 0

b = 1;

b = 2;

i < n

s = s + a*b;

i = i + 1;

return s

No!

One reaching

definition with

b = 1

One reaching

definition with

b = 2

29 of 34

Merging Facts

Control flow join points

Require merging facts to produce a new fact
New fact should be a union of facts from both branches
Also, new fact should in the set of facts of the analysis

Often new fact is an overapproximation – set of values for a new fact may be larger than the union of values of each.
Introduces a concept of precision – analysis may not track the most precise fact for a property

30 of 34

Merging Facts

b = 1;

Constant

Sign

Interval

Set

31 of 34

Merging Facts

b = 1;

b = 2;

b = 1;

b = 2;

b = 1;

b = 2;

b = 1;

b = 2;

Constant

Sign

Interval

Set

32 of 34

Merging Facts

b = 0;

b = 1;

b = 0;

b = 1;

b = 0;

b = 1;

b = 0;

b = 1;

Constant

Sign

Interval

Set

33 of 34

Merging Facts

b = -1;

b = 1;

b = -1;

b = 1;

b = -1;

b = 1;

b = -1;

b = 1;

Constant

Sign

Interval

Set

34 of 34

Merging Facts

Control flow join points

Require merging facts to produce a new fact
New fact should be a union of facts from both branches
Also, new fact should in the set of facts of the analysis
Often new fact is an overapproximation – set of values for a new fact may be larger than the union of values of each.
Introduces a concept of precision – analysis may not tract the most precise fact for a property

Questions, which fact to use as merge? What is “?”

Solution: place facts into a lattice that relate the precision of facts to each other and yield operations for unioning facts together