A Tale of TurboFan�Four years that changed V8 forever
Benedikt Meurer
@bmeurer
Overview
IGNITION
What is TurboFan?
launched in
and !
Unified code generation architecture
WASM
Compiler
TurboFan
Optimizing
Compiler
Built-in Operations
TurboFan code
generation
architecture
Instruction Selector
Code Generator
Register Allocator
Intel, ARM, PowerPC,
MIPS
Control flow graph
Scheduler
“Sea of nodes” graph
C++ DSL
CodeStubAssembler
Ignition Interpreter
Bytecodes
TurboFan Optimizing Compiler
Bytecode
Bytecode
GraphBuilder
“Sea of nodes” graph
Specialization
Inlining
Bytecode
Profiling Feedback
Frontend
Typed
Optimization
Redundancy Elimination
Escape Analysis
Representation Selection
Optimization
Machine-level Optimization
Scheduling
Control flow graph
Code Generation
Intel, ARM, PowerPC,
MIPS
Backend
Inlining
Inlining
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
function three_add_inlined() {� var x = 1;
var y = 2;� var add_return_value = x + y;� return add_return_value;�}
function three_add_const_folded() {� return 3;�}
Constant-
folding
Inlining
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rax,[rbp+0x18]�test al,0x1�jnz Deoptimize�movq rbx,[rbp+0x10]�testb rbx,0x1�jnz Deoptimize�movq rdx,rbx�shrq rdx, 32�movq rcx,rax�shrq rcx, 32�addl rdx,rcx�jo Deoptimize�shlq rdx, 32�movq rax,rdx�movq rsp,rbp�pop rbp�ret 0x18
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
Inlining
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rax,[rbp+0x18]�test al,0x1�jnz Deoptimize�movq rbx,[rbp+0x10]�testb rbx,0x1�jnz Deoptimize�movq rdx,rbx�shrq rdx, 32�movq rcx,rax�shrq rcx, 32�addl rdx,rcx�jo Deoptimize�shlq rdx, 32�movq rax,rdx�movq rsp,rbp�pop rbp�ret 0x18
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
Prologue
Inlining
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rax,[rbp+0x18]�test al,0x1�jnz Deoptimize�movq rbx,[rbp+0x10]�testb rbx,0x1�jnz Deoptimize�movq rdx,rbx�shrq rdx, 32�movq rcx,rax�shrq rcx, 32�addl rdx,rcx�jo Deoptimize�shlq rdx, 32�movq rax,rdx�movq rsp,rbp�pop rbp�ret 0x18
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
Check x is a small integer
Prologue
Inlining
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rax,[rbp+0x18]�test al,0x1�jnz Deoptimize�movq rbx,[rbp+0x10]�testb rbx,0x1�jnz Deoptimize�movq rdx,rbx�shrq rdx, 32�movq rcx,rax�shrq rcx, 32�addl rdx,rcx�jo Deoptimize�shlq rdx, 32�movq rax,rdx�movq rsp,rbp�pop rbp�ret 0x18
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
Check x is a small integer
Check y is a small integer
Prologue
Inlining
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rax,[rbp+0x18]�test al,0x1�jnz Deoptimize�movq rbx,[rbp+0x10]�testb rbx,0x1�jnz Deoptimize�movq rdx,rbx�shrq rdx, 32�movq rcx,rax�shrq rcx, 32�addl rdx,rcx�jo Deoptimize�shlq rdx, 32�movq rax,rdx�movq rsp,rbp�pop rbp�ret 0x18
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
Check x is a small integer
Check y is a small integer
Convert y from tagged representation to word32
Prologue
Inlining
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rax,[rbp+0x18]�test al,0x1�jnz Deoptimize�movq rbx,[rbp+0x10]�testb rbx,0x1�jnz Deoptimize�movq rdx,rbx�shrq rdx, 32�movq rcx,rax�shrq rcx, 32�addl rdx,rcx�jo Deoptimize�shlq rdx, 32�movq rax,rdx�movq rsp,rbp�pop rbp�ret 0x18
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
Check x is a small integer
Check y is a small integer
Convert y from tagged representation to word32
Convert x from tagged representation to word32
Prologue
Inlining
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rax,[rbp+0x18]�test al,0x1�jnz Deoptimize�movq rbx,[rbp+0x10]�testb rbx,0x1�jnz Deoptimize�movq rdx,rbx�shrq rdx, 32�movq rcx,rax�shrq rcx, 32�addl rdx,rcx�jo Deoptimize�shlq rdx, 32�movq rax,rdx�movq rsp,rbp�pop rbp�ret 0x18
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
Check x is a small integer
Check y is a small integer
Convert y from tagged representation to word32
Convert x from tagged representation to word32
Add x and y (incl. overflow check)
Prologue
Inlining
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rax,[rbp+0x18]�test al,0x1�jnz Deoptimize�movq rbx,[rbp+0x10]�testb rbx,0x1�jnz Deoptimize�movq rdx,rbx�shrq rdx, 32�movq rcx,rax�shrq rcx, 32�addl rdx,rcx�jo Deoptimize�shlq rdx, 32�movq rax,rdx�movq rsp,rbp�pop rbp�ret 0x18
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
Check x is a small integer
Check y is a small integer
Convert y from tagged representation to word32
Convert x from tagged representation to word32
Add x and y (incl. overflow check)
Convert result to tagged representation
Prologue
Inlining
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rax,[rbp+0x18]�test al,0x1�jnz Deoptimize�movq rbx,[rbp+0x10]�testb rbx,0x1�jnz Deoptimize�movq rdx,rbx�shrq rdx, 32�movq rcx,rax�shrq rcx, 32�addl rdx,rcx�jo Deoptimize�shlq rdx, 32�movq rax,rdx�movq rsp,rbp�pop rbp�ret 0x18
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
Check x is a small integer
Check y is a small integer
Convert y from tagged representation to word32
Convert x from tagged representation to word32
Add x and y (incl. overflow check)
Convert result to tagged representation
Epilogue
Prologue
Inlining
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rdi,<JSFunction add>�movq rsi,[rdi+0x1f]�movq rax,<JSGlobal Object>�push rax�movq rax,0x100000000�push rax�movq rax,0x200000000�push rax�movq rdx,[r13-0x60]�movl rax,0x2�movq rcx,[rdi+0x2f]�addq rcx,0x5f�call rcx�movq rsp,rbp�pop rbp�ret 0x8
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
Inlining
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rdi,<JSFunction add>�movq rsi,[rdi+0x1f]�movq rax,<JSGlobal Object>�push rax�movq rax,0x100000000�push rax�movq rax,0x200000000�push rax�movq rdx,[r13-0x60]�movl rax,0x2�movq rcx,[rdi+0x2f]�addq rcx,0x5f�call rcx�movq rsp,rbp�pop rbp�ret 0x8
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
Prologue
Inlining
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rdi,<JSFunction add>�movq rsi,[rdi+0x1f]�movq rax,<JSGlobal Object>�push rax�movq rax,0x100000000�push rax�movq rax,0x200000000�push rax�movq rdx,[r13-0x60]�movl rax,0x2�movq rcx,[rdi+0x2f]�addq rcx,0x5f�call rcx�movq rsp,rbp�pop rbp�ret 0x8
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
Load call target add
Prologue
Inlining
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rdi,<JSFunction add>�movq rsi,[rdi+0x1f]�movq rax,<JSGlobal Object>�push rax�movq rax,0x100000000�push rax�movq rax,0x200000000�push rax�movq rdx,[r13-0x60]�movl rax,0x2�movq rcx,[rdi+0x2f]�addq rcx,0x5f�call rcx�movq rsp,rbp�pop rbp�ret 0x8
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
Load call target add
Load call parameters
Prologue
Inlining
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rdi,<JSFunction add>�movq rsi,[rdi+0x1f]�movq rax,<JSGlobal Object>�push rax�movq rax,0x100000000�push rax�movq rax,0x200000000�push rax�movq rdx,[r13-0x60]�movl rax,0x2�movq rcx,[rdi+0x2f]�addq rcx,0x5f�call rcx�movq rsp,rbp�pop rbp�ret 0x8
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
Load call target add
Load call parameters
Call sequence
Prologue
Inlining
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rdi,<JSFunction add>�movq rsi,[rdi+0x1f]�movq rax,<JSGlobal Object>�push rax�movq rax,0x100000000�push rax�movq rax,0x200000000�push rax�movq rdx,[r13-0x60]�movl rax,0x2�movq rcx,[rdi+0x2f]�addq rcx,0x5f�call rcx�movq rsp,rbp�pop rbp�ret 0x8
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
Load call target add
Load call parameters
Call sequence
Epilogue
Prologue
Inlining
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rax,0x300000000�movq rsp,rbp�pop rbp�ret 0x8
Inlining
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rax,0x300000000�movq rsp,rbp�pop rbp�ret 0x8
Prologue
Inlining
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rax,0x300000000�movq rsp,rbp�pop rbp�ret 0x8
Load tagged value 3
Prologue
Inlining
function add(x, y) {
return x + y;�}
�function three() {� return add(1, 2);�}
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rax,0x300000000�movq rsp,rbp�pop rbp�ret 0x8
Load tagged value 3
Epilogue
Prologue
Inlining
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rax,0x300000000�movq rsp,rbp�pop rbp�ret 0x8
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rdi,<JSFunction add>�movq rsi,[rdi+0x1f]�movq rax,<JSGlobal Object>�push rax�movq rax,0x100000000�push rax�movq rax,0x200000000�push rax�movq rdx,[r13-0x60]�movl rax,0x2�movq rcx,[rdi+0x2f]�addq rcx,0x5f�call rcx�movq rsp,rbp�pop rbp�ret 0x8
leaq rcx,[rip+0x0]�movq rcx,[rcx-0x37]�testb [rcx+0xf],0x1�jnz CompileLazyDeoptimizedCode�push rbp�movq rbp,rsp�push rsi�push rdi�cmpq rsp,[r13+0xdb0]�jna StackCheck�movq rax,[rbp+0x18]�test al,0x1�jnz Deoptimize�movq rbx,[rbp+0x10]�testb rbx,0x1�jnz Deoptimize�movq rdx,rbx�shrq rdx, 32�movq rcx,rax�shrq rcx, 32�addl rdx,rcx�jo Deoptimize�shlq rdx, 32�movq rax,rdx�movq rsp,rbp�pop rbp�ret 0x18
+
vs
Inlining
Escape Analysis and Scalar Replacement
Escape Analysis and Scalar Replacement
Escape Analysis and Scalar Replacement
class Point {� constructor(x, y) {
this.x = x;
this.y = y;� }�� distance(that) {� return Math.abs(this.x - that.x)� + Math.abs(this.y - that.y);� }�}��function manhattan(x1, y1, x2, y2) {� const a = new Point(x1, y1);� const b = new Point(x2, y2);� return a.distance(b);�}
function manhattan_inl(x1, y1, x2, y2) {� const a = {x:x1, y:y1};� const b = {x:x2, y:y2};� return Math.abs(a.x - b.x)� + Math.abs(a.y - b.y);�}
Escape Analysis and Scalar Replacement
function manhattan_inl(x1, y1, x2, y2) {� const a = {x:x1, y:y1};� const b = {x:x2, y:y2};� return Math.abs(a.x - b.x)� + Math.abs(a.y - b.y);�}
Over-simplified conditions for non escaping objects:
a is allocated and doesn’t escape
b is allocated and doesn’t escape
Escape Analysis and Scalar Replacement
function manhattan_inl(x1, y1, x2, y2) {� const a = {x:x1, y:y1};� const b = {x:x2, y:y2};� return Math.abs(a.x - b.x)� + Math.abs(a.y - b.y);�}
function manhattan_ea(x1, y1, x2, y2) {� var a_x = x1;� var a_y = y1;� var b_x = x2;� var b_y = y2;� return Math.abs(a_x - b_x)� + Math.abs(a_y - b_y);�}
Fields | x | y |
a | a_x | a_y |
b | b_x | b_y |
Map fields to local variables
Benefits:
Example: Rest Parameters
function count(...args) {� return args.length;�}
args doesn’t escape and only its length field is accessed
Example: Rest Parameters
function count(...args) {� return args.length;�}
leaq rcx,[rip+0x0]� movq rcx,[rcx-0x37]� testb [rcx+0xf],0x1� jnz CompileLazyDeoptimizedCode� push rbp� movq rbp,rsp� push rsi� push rdi� cmpq rsp,[r13+0xdb0]� jna StackCheck� movq rax,rbp� movq rbx,[rax]� cmpq [rbx-0x8],0x20� jz L0� movq rbx,rax�L0: cmpq rax,rbx� jz L1� movq rax,[rbx-0x18]� cmpq rax,0x0� jge L2�L1: xorl rax, rax�L2: movq rsp,rbp� pop rbp� ret 0x8
Example: Rest Parameters
function count(...args) {� return args.length;�}
leaq rcx,[rip+0x0]� movq rcx,[rcx-0x37]� testb [rcx+0xf],0x1� jnz CompileLazyDeoptimizedCode� push rbp� movq rbp,rsp� push rsi� push rdi� cmpq rsp,[r13+0xdb0]� jna StackCheck� movq rax,rbp� movq rbx,[rax]� cmpq [rbx-0x8],0x20� jz L0� movq rbx,rax�L0: cmpq rax,rbx� jz L1� movq rax,[rbx-0x18]� cmpq rax,0x0� jge L2�L1: xorl rax, rax�L2: movq rsp,rbp� pop rbp� ret 0x8
Prologue
Example: Rest Parameters
function count(...args) {� return args.length;�}
leaq rcx,[rip+0x0]� movq rcx,[rcx-0x37]� testb [rcx+0xf],0x1� jnz CompileLazyDeoptimizedCode� push rbp� movq rbp,rsp� push rsi� push rdi� cmpq rsp,[r13+0xdb0]� jna StackCheck� movq rax,rbp� movq rbx,[rax]� cmpq [rbx-0x8],0x20� jz L0� movq rbx,rax�L0: cmpq rax,rbx� jz L1� movq rax,[rbx-0x18]� cmpq rax,0x0� jge L2�L1: xorl rax, rax�L2: movq rsp,rbp� pop rbp� ret 0x8
Prologue
Find the parameters
Example: Rest Parameters
function count(...args) {� return args.length;�}
leaq rcx,[rip+0x0]� movq rcx,[rcx-0x37]� testb [rcx+0xf],0x1� jnz CompileLazyDeoptimizedCode� push rbp� movq rbp,rsp� push rsi� push rdi� cmpq rsp,[r13+0xdb0]� jna StackCheck� movq rax,rbp� movq rbx,[rax]� cmpq [rbx-0x8],0x20� jz L0� movq rbx,rax�L0: cmpq rax,rbx� jz L1� movq rax,[rbx-0x18]� cmpq rax,0x0� jge L2�L1: xorl rax, rax�L2: movq rsp,rbp� pop rbp� ret 0x8
Prologue
Find the parameters
Count the number of parameters
Example: Rest Parameters
function count(...args) {� return args.length;�}
leaq rcx,[rip+0x0]� movq rcx,[rcx-0x37]� testb [rcx+0xf],0x1� jnz CompileLazyDeoptimizedCode� push rbp� movq rbp,rsp� push rsi� push rdi� cmpq rsp,[r13+0xdb0]� jna StackCheck� movq rax,rbp� movq rbx,[rax]� cmpq [rbx-0x8],0x20� jz L0� movq rbx,rax�L0: cmpq rax,rbx� jz L1� movq rax,[rbx-0x18]� cmpq rax,0x0� jge L2�L1: xorl rax, rax�L2: movq rsp,rbp� pop rbp� ret 0x8
Prologue
Find the parameters
Count the number of parameters
Epilogue
Example: Rest Parameters
function count(...args) {� return args.length;�}
leaq rcx,[rip+0x0]� movq rcx,[rcx-0x37]� testb [rcx+0xf],0x1� jnz CompileLazyDeoptimizedCode� push rbp� movq rbp,rsp� push rsi� push rdi� cmpq rsp,[r13+0xdb0]� jna StackCheck� movq rax,rbp� movq rbx,[rax]� cmpq [rbx-0x8],0x20� jz L0� movq rbx,rax�L0: cmpq rax,rbx� jz L1� movq rax,[rbx-0x18]� cmpq rax,0x0� jge L2�L1: xorl rax, rax�L2: movq rsp,rbp� pop rbp� ret 0x8
Prologue
Find the parameters
Count the number of parameters
Epilogue
Array args is never materialized!
Escape Analysis and Scalar Replacement
Predictable
Performance
Performance cliffs in Crankshaft
(function good() {� const start = Date.now();� for (var i = 0; i < 1e8; i++) {}� console.log(Date.now() - start);�})();
(function bad() {� const start = Date.now();� for (var i = 0; i < 1e8; i++) {}� console.log(Date.now() - start);� const whatever = 1;�})();
Runs ~80ms
Runs ~230ms
~3x slowdown�with Crankshaft
Optimization Killers
Optimization Killers
It’s not just�optimized code...
Octane/Crypto test
TypeScript 2.1.6 compiling itself
Octane/Crypto test
Loading www.nytimes.com
Octane/Crypto test
Performance Results
60% faster web developer tools
1.7× faster on ARES-6
Takeaways
Follow us!
@v8js
Benedikt Meurer�@bmeurer
Thanks!��AMA on V8 & JS Performance�Tuesday 16:00–17:00, Room B