TurboFan JIT Design

Ben L. Titzer

Google Munich

Google Proprietary

V8 Background

• JavaScript has some difficult to optimize features
• No explicit types
• Prototype-based property lookup
• Dynamic evaluation of code
• V8 was the first really *fast* JavaScript VM
• Sophisticated and efficient object layout
• Compile-only: no interpreter
• Quick, non-optimizing JIT (fullcode)
• Inline caching, type feedback
• Generational GC with low pause times
• V8 launched with Chrome in 2008
• Optimizing JIT (CrankShaft) launched in 2010

Google Proprietary

TurboFan Design Goals

• Achieve best peak performance
• Highest quality machine code
• Within normal constraints of JIT compilation

​

• Make best use of static type information
• asm.js, latent JavaScript types, TypeScript, SoundScript proposal

​

• Reduce platform-specific implementation effort
• Better separation between front, middle, and backend of compiler

​

• Improve testability
• Prevent correctness bugs and verify optimizations activate

Google Proprietary

TurboFan Program Representation (IR)

• NOT: Control Flow Graph (CFG)
• Fully-specified evaluation order; e.g. pure operations like integer addition

​

• INSPIRATION: Sea of Nodes
• Relax evaluation order for most operations
• Effect edges order stateful operations
• Skeleton of a CFG remains
• Why? Better redundant code elimination, more code motion

​

• REALLY: “Soup” of Nodes
• Relax Sea of Nodes control flow subgraph even further
• Disconnected “floating control” islands offer more scheduling freedom
• Why? Lowering of language levels, even more code motion

Google Proprietary

Do not get seasick!

3

x

+

All computations are expressed as nodes in the sea of nodes

Edges represent dependencies between computations

+

3

x

constant

parameter

addition operator

data flow edge

Google Proprietary

Dependencies constrain Ordering

+

3

x

+

3

x

+

3

x

legal

legal

illegal

Google Proprietary

Lack of Ordering means Compiler Freedom!

7

*

5

+

x

x

5

7

x

7

x

5

x

+

7

+

*

7

*

x

+

*

5

5

5

7

x

+

+

*

*

x

x

5

5

x

7

x

+

*

5

+

7

+

*

7

*

+

*

7

+

*

5

5

7

Google Proprietary

Larger class of equivalences

7

*

5

+

x

x

5

7

x

7

x

5

x

+

7

+

*

7

*

x

+

*

5

5

5

7

x

+

+

*

*

x

x

5

5

x

7

x

+

*

5

+

7

+

*

7

*

+

*

7

+

*

5

5

7

graph creation

Google Proprietary

The Sea is SSA

3

[x]

+

No such thing as local variables!

Graph building from source renames locals

3

+

x = 3 * 8

x + 3

*

8

SSA

renaming

Multiple incoming edges possible

Google Proprietary

Effect Edges

LoadField[f]

obj

effect

Read of mutable state obj.f

Read

potential write X

+

3

RAW: prevents X

moving after R

potential write Y

WAR: prevents Y moving before R

StoreField[f]

WAW: prevents X

moving after Y

Google Proprietary

Expressing Control

• Nodes: express computation
• Constants, parameters, arithmetic, load, store, calls
• Source program is SSA renamed so locals are substituted with nodes

​

• Edges: express dependencies (constrain order)
• dataflow edges express using the value output of a computation
• effect edges order operations reading and writing state

​

• NEXT: Control with start, branches, loops, merge, and end
• How do we express non-straight line code?

Google Proprietary

Control nodes and Control edges

Branch

IfTrue

IfFalse

Merge

Branch

IfTrue

IfFalse

Loop

Start

End

straightline program

branch

while loop

Google Proprietary

Our first complete graph

Start

End

3

x

+

function (x) { return x + 3; }

control edge

value edge

effect edge

Google Proprietary

Branch example

Start

End

function (x) { return x ? 1 : 2; }

Branch

IfTrue

IfFalse

Merge

phi

2

1

x

control edge

value edge

effect edge

Google Proprietary

Language Levels

• JavaScript: (“JS”) operators
• Express semantics of JavaScript’s overloaded operators
• Produce and consume effects in the graph
• Intermediate: (“Simplified”) operators
• Express VM-level operations, such as allocation, bounds checks
• Arithmetic independent of number representation
• Machine: (“Machine”) operators
• Correspond closely to single machine instructions
• Most have no side effects
• Must be supported by backend for each platform

Google Proprietary

Language Levels

• JavaScript:

​

​

​

• Intermediate:

​

​

​

• Machine:

JSAdd

JSSubtract

JSMultiply

JSDivide

JSModulus

JSEqual

JSToBoolean

JSToNumber

JSCall

JSStrictEqual

JSBitwiseOr

JSDivide

JSBitwiseAnd

JSBitwiseXor

JSShiftLeft

JSShiftRight

NumberAdd

NumberSub

NumberMul

NumberDiv

NumberMod

NumberEqual

StringEqual

NumberLessThan

StringAdd

LoadField

StoreField

ChangeTaggedToInt32

Int32Add

Int32Sub

Int32Mul

Float64Add

Float64Sub

Float64Mul

Load

Store

Call

ConvertFloat64ToInt32

Google Proprietary

Type and Range Analysis

• JavaScript is not statically typed
• Values have types, not variables
• 8 is a Number, “x” is a String
• All basic operators (+ - * / % == !=) overloaded for objects
• All arithmetic is done in 64-bit floating point
• Empirically, most programs use only small integers (<= 31bits)
• Overflow to double usually causes code to bailout to slow path
• Troublesome cases: NaN, Infinity, -Infinity, -0.0
• asm.js language subset
• Annotations such as (x + y) | 0
• Truncation maps NaN, Infinity, -Infinity, -0.0 to integer 0

Google Proprietary

Type and Range Analysis

typing

alone

x: Int

y: Int

x: Int in [0, 9]

y: Int in [11, 15]

+

+: Num

+

typing + range analysis

+: Int in [11, 26]

typing

alone

x: Int

y: Int

x: Int in [0, 9]

y: Int in [11, 15]

phi

phi: Int

phi

typing + range analysis

phi: Int in [0, 15]

Google Proprietary

Optimization

• Nearly all optimization happens on the sea of nodes
• Top-down or bottom-up graph transformations
• Isolates transformations from error-prone ordering of computations
• Local reasoning leads to incremental transformations

​

• Reachability => Liveness
• Nodes not reachable from end are dead
• Including dead control, dead effects, dead computation
• Most phases never see dead code
• Dead code never placed in final schedule

Google Proprietary

Reduction

3

5

+

x

0

+

x

4

*

x

2

<<

8

x

x

phi

x

7

+

5

+

x

x

12

+

constant

folding

strength

reduction

strength

reduction

phi

simplification

algebraic

reassociation

Google Proprietary

Typed Lowering as Reduction

typed lowering

y: Num

x: Num

JSAdd

y: Num

x: Num

NumAdd

y: String

x: Num

StringAdd

y: String

x: Num

JSAdd

ToString

y: Int

x: Int

JSAdd

JSBitwiseOr

0

y: Int

x: Int

Int32Add

typed lowering

typed lowering

generic lowering

y: Any

x: Any

JSAdd

y: Any

x: Any

BinopIC[+]

Google Proprietary

Global Value Numbering as Reduction

x

y

+

+

x

y

+

LoadField[f]

obj

LoadField[f]

effect

x

sin

sin

x

sin

LoadField[f]

obj

effect

GVN

GVN

GVN

Google Proprietary

Control Optimization as Reduction

C

Branch

true

IfTrue

IfFalse

C

Dead

x

y

x

y

branch folding

Google Proprietary

Control Optimization as Reduction

Merge

C1

Dead

C2

x

phi

y

z

Merge

C1

C2

x

phi

z

merge

reduction

Merge

C1

x

phi

merge

reduction

C1

x

Google Proprietary

Control Optimization as Reduction

Branch

x

IfTrue

IfFalse

Dead

x

y

x

y

control reduction

Dead

Google Proprietary

Reduction as Top-down Graph Rewriting

x

Node

y

z

fully reduced inputs

reduction rules

value uses

effect uses

control uses

x

y

z

value uses

effect uses

control uses

reduced

node(s)

Google Proprietary

Iterative Reduction (recursion with explicit stack)

n1

n2

n3

n4

n5

n6

n7

n8

n9

Reduce top of stack when all its inputs are reduced.

node stack

backwards DFS

end

Pop the stack after applying reduction rules.

Applies reduction to each node once in the optimal order.

Google Proprietary

Iterative Reduction (in the presence of cycles)

n1

n2

n3

n4

n5

n6

n7

n8

n9

Reduce top of stack when all its inputs are either reduced or are themselves on the stack.

node stack

backwards DFS

end

When a node is successfully reduced, revisit any uses that were partially reduced due to cycles.

Computes a fixpoint over reduction rules.

Google Proprietary

Iterative Reduction (in the presence of cycles)

n1

n2

n3

n4

n5

Reduce top of stack when all its inputs are either reduced or are themselves on the stack.

node stack

backwards DFS

end

When a node is successfully reduced, revisit any uses that were partially reduced due to cycles.

Computes a fixpoint over reduction rules.

n6

Google Proprietary

Iterative Reduction (in the presence of cycles)

n1

n2

n3

Reduce top of stack when all its inputs are either reduced or are themselves on the stack.

node stack

backwards DFS

end

When a node is successfully reduced, revisit any uses that were partially reduced due to cycles.

Computes a fixpoint over reduction rules.

n4

n6

Google Proprietary

Iterative Reduction (in the presence of cycles)

n1

n2

Reduce top of stack when all its inputs are either reduced or are themselves on the stack.

node stack

backwards DFS

end

When a node is successfully reduced, revisit any uses that were partially reduced due to cycles.

Computes a fixpoint over reduction rules.

n6

n7

n8

n9

n3

Google Proprietary

Lowering to Machine

• JavaScript:

​

​

​

• Intermediate:

​

​

​

• Machine:

JSAdd

JSSubtract

JSMultiply

JSDivide

JSModulus

JSEqual

JSToBoolean

JSToNumber

JSCall

JSStrictEqual

JSBitwiseOr

JSDivide

JSBitwiseAnd

JSBitwiseXor

JSShiftLeft

JSShiftRight

NumberAdd

NumberSub

NumberMul

NumberDiv

NumberMod

NumberEqual

StringEqual

NumberLessThan

StringAdd

LoadField

StoreField

ChangeTaggedToInt32

Int32Add

Int32Sub

Int32Mul

Float64Add

Float64Sub

Float64Mul

Load

Store

Call

ConvertFloat64ToInt32

Google Proprietary

Lowering to Machine

expand and optimize

JS* and Simplified*

nodes

Google Proprietary

Floating Control

StringEqual

x

y

Branch

IfTrue

IfFalse

Merge

phi

true

PtrEqual

x

y

Call

lower and

expand fast

case

Google Proprietary

Floating Control

StringEqual

x

y

Branch

IfTrue

IfFalse

Merge

phi

x

y

lower and

expand fast

case

floating control diamond

not connected to

“main” control

Google Proprietary

Scheduling the Sea of Nodes

• Sea of nodes expresses many possible legal orderings of code
• Many possible CFGs
• Many possible assignment of nodes to CFG blocks
• Many possible orderings within basic blocks

​

• What is the most efficient order and placement?
• Depends on control dominance, loop nesting, register pressure

​

​

• Outcome: traditional CFG
• Traditional code generation and register allocation can take over

Google Proprietary

Scheduling the Sea of Nodes (sketch)

A

B

C

D

F

E

G

H

Control Flow Graph

A

B

C

D

F

E

G

H

Dominator

Tree

Unscheduled

nodes

Google Proprietary

Scheduling the Sea of Nodes (sketch)

A

B

C

D

F

E

G

H

Control Flow Graph

A

B

C

D

F

E

G

H

Dominator

Tree

Unscheduled

nodes

Place fixed

nodes

(phis, params)

Google Proprietary

Scheduling the Sea of Nodes (sketch)

A

B

C

D

F

E

G

H

Control Flow Graph

A

B

C

D

F

E

G

H

Dominator

Tree

Unscheduled

nodes

Google Proprietary

Scheduling the Sea of Nodes (sketch)

A

B

C

D

F

E

G

H

Control Flow Graph

A

B

C

D

F

E

G

H

Dominator

Tree

Schedulable

nodes

Google Proprietary

Scheduling the Sea of Nodes (sketch)

A

B

C

D

F

E

G

H

Control Flow Graph

A

B

C

D

F

E

G

H

Dominator

Tree

scheduled uses

inputs

must dominate

eligible node

Google Proprietary

Scheduling the Sea of Nodes (sketch)

A

B

C

D

F

E

G

H

Control Flow Graph

A

B

C

D

F

E

G

H

Dominator

Tree

Schedulable

nodes

Google Proprietary

Scheduling the Sea of Nodes (sketch)

A

B

C

D

F

E

G

H

Control Flow Graph

A

B

C

D

F

E

G

H

Dominator

Tree

Schedulable

nodes

Google Proprietary

Scheduling the Sea of Nodes (sketch)

A

B

C

D

F

E

G

H

Control Flow Graph

A

B

C

D

F

E

G

H

Dominator

Tree

Schedulable

nodes

Google Proprietary

Scheduling the Sea of Nodes (sketch)

A

B

C

D

F

E

G

H

Control Flow Graph

A

B

C

D

F

E

G

H

Dominator

Tree

Schedulable

nodes

Google Proprietary

Scheduling the Sea of Nodes (sketch)

A

B

C

D

F

E

G

H

Control Flow Graph

A

B

C

D

F

E

G

H

Dominator

Tree

Schedulable

nodes

Google Proprietary

Scheduling the Sea of Nodes (sketch)

A

B

C

D

F

E

G

H

Control Flow Graph

A

B

C

D

F

E

G

H

Dominator

Tree

Schedulable

nodes

Google Proprietary

Scheduling the Sea of Nodes (sketch)

A

B

C

D

F

E

G

H

Dominator

Tree

A fully scheduled graph is exactly the same as a CFG.

A

B

C

D

F

E

G

H

Control Flow Graph

Google Proprietary

Scheduling the Sea of Nodes (sketch)

A

B

C

D

F

E

G

H

Dominator

Tree

Placement is important!

​

Hoist code out of loops if possible

​

Place code as late as possible

​

Minimize register pressure

​

Eliminate redundancy

​

​

​

​

A

B

C

D

F

E

G

H

Control Flow Graph

Google Proprietary

Where is Loop Invariant Code Motion?

A

B

C

D

F

E

G

H

Dominator

Tree

Nowhere!

​

Scheduling subsumes loop invariant code motion.

​

​

​

A

B

C

D

F

E

G

H

Control Flow Graph

Google Proprietary

Instruction Selection (theory)

Load

obj

effect

*

4

i

Load

obj

effect

*

4

i

maximal

munch

mov %r0, [%r1 + %r2 * 4]

%r0

%r1

%r2

Google Proprietary

Instruction Selection (practice)

obj

effect

*

4

i

call

Load

Call

basic block

instruction sequence

cursor

visit nodes in blocks

in reverse CFG

order

Google Proprietary

Instruction Selection (practice)

obj

*

4

i

call

Load

Call

basic block

instruction sequence

cursor

visit nodes in blocks

in reverse CFG

order

Google Proprietary

Instruction Selection (practice)

obj

effect

*

4

i

call

Load

Call

basic block

instruction sequence

cursor

visit nodes in blocks

in reverse CFG

order

mov %r0, [%r1 + %r2 * 4]

Google Proprietary

Instruction Selection (practice)

obj

*

4

i

call

Load

Call

basic block

instruction sequence

cursor

mov %r0, [%r1 + %r2 * 4]

[%r2 = code for i]

Google Proprietary

Instruction Selection (practice)

obj

*

4

i

call

Load

Call

basic block

instruction sequence

cursor

mov %r0, [%r1 + %r2 * 4]

[%r2 = code for i]

[%r1 = code for obj]

Google Proprietary

Register Allocation

call

instruction sequence

mov %r0, [%r1 + %r2 * 4]

[%r2 = code for i]

[%r1 = code for obj]

TurboFan uses a linear scan allocator with

live range splitting to assign registers and

insert spill code.

​

SSA form can be deconstructed before or

after register allocation with explicit moves.

Google Proprietary

Register Allocation

call

instruction sequence

mov %ecx, [%eax + %ebx * 4]

[%ebx = code for i]

[%eax = code for obj]

TurboFan uses a linear scan allocator with

live range splitting to assign registers and

insert spill code.

​

SSA form can be deconstructed before or

after register allocation with explicit moves.

​

The result of register allocation is to replace uses of virtual registers with real registers and to insert spill code between instructions.

mov [sp + 12], %eax

Google Proprietary

Testability

• Unit testing
• Basic data structures, traversal algorithms, lowering, graph building, graph transformations, type relations, instruction selection, spill code insertion, register allocation, code generation, assemblers
• Integration testing
• Run multiple optimization passes together, create specific graphs explicitly, try all combinations of arithmetic + generate and run code
• Performance tracking
• Microbenchmarks, benchmark suites
• Fuzzing
• Randomly mutate JavaScript source and feed it compiler

Google Proprietary

Status

• TurboFan is now in beta testing in Chrome 41
• Initially enabled for asm.js
• 6 Fully supported platforms
• ia32, x86-64, arm, arm64, mips, mips64
• 2000-3000 lines per platform (vs 13000-16000 for CrankShaft)
• Improves Octane zlib benchmark 30-45%
• Most Emscripten benchmarks 10-25% faster
• Working on “general” JavaScript
• Goal: all of ES6 within a couple of months

Google Proprietary

Thank You!

Andreas Rossberg

Jaroslav Sevcik

Sven Panne

Ben L. Titzer

Michael Starzinger

Daniel Clifford

Benedikt Meurer

Dan Carney

Sigurd Schneider

Georg Neis

Google Proprietary