Escape Analysis in Turbofan

Tobias Tebbi

V8 Team, Google

Chrome

Chrome

Node.js

Chrome

Escape Analysis: �Removing Temporary Objects

function diagonal(a) {

return abs({x:a, y:a});

}

​

function abs(v) {

return Math.sqrt(v.x*v.x + v.y*v.y);

}

​

​

​

​

​

return Math.sqrt(a*a + a*a);

​

​

​

How do we remove this object allocation?

Chrome

Step 1: Inlining

function diagonal(a) {

let v = {x:a, y:a};

return abs(v);

}

​

function abs(v) {

return Math.sqrt(v.x*v.x + v.y*v.y);

}

function diagonal(a) {

let v = {x:a, y:a};

return Math.sqrt(v.x*v.x + v.y*v.y);

}

Chrome

Step 2: Replacing Field Accesses

function diagonal(a) {

let v = {x:a, y:a};

return Math.sqrt(v.x*v.x + v.y*v.y);

}

function diagonal(a) {

let v = {x:a, y:a};

return Math.sqrt(a*a + a*a);

}

Chrome

Step 3: Removing unused allocation

function diagonal(a) {

let v = {x:a, y:a};

return Math.sqrt(a*a + a*a);

}

​

function diagonal(a) {

return Math.sqrt(a*a + a*a);

}

Chrome

It’s not always that easy...

Chrome

Writing to Fields

function write_field(x) {

let o = {a: 5};

while (x > 0) o.a += x--;

return o.a;

}

​

​

function write_field(x) {

let o_a = 5;

while (x > 0) o_a += x--;

return o_a;

}

​

​

​

Replace object fields with a local variable.

Chrome

Nested Objects

function nested_objects(b) {

let o = {a: {x: 5}};

o.a = {x: 7}

return o.a.x;

}

​

​

function nested_objects(b) {

​

return 7;

}

Chrome

Sometimes, we give up...

Chrome

Escaping Objects

function escaping_object(foo) {

let o = {};

foo(o);

}

When we can’t inline foo, then we cannot dematerialize o because foo could do anything with it.

Chrome

Index Access

let l = [1,2,3];

let sum = 0;

for(let i = 0; i < 3; ++i) sum += l[i];

Index access requires linear memory.

Thus we have to materialize l.

Chrome

Dynamic Object Identity

function object_identity(b) {

let o1 = {x: 5};

let o2 = {x: 7};

(b?o1:o2).x = 1;

return o1.x;

}

​

This computation uses the object identity of o1 and o2.

It’s impossible to map this to local variables: Local variables don’t have identity.

In principle, this could be solved with stack-allocation.

Chrome

The Magic of Deoptimization

function harmless(copy) {}

​

function foo(x) {

let copy = {};

copy.a = x + 1;

harmless(copy);

}

​

​

function foo(x) {

x + 1;

}

function evil(copy) {

global = copy;

}

foo({valueOf: () => harmless=evil});

?

While executing foo, the temporary object might suddenly escape.

​

Monkey patching can destroy any optimization,

while the optimized code is running.

Chrome

The Magic of Deoptimization

function harmless(copy) {}

​

function foo(x) {

let copy = {};

copy.a = x + 1;

harmless(copy);

}

​

​

function foo(x) {

if (typeof x != 'number')

%Deoptimize();

}

​

​

create object copy

When deoptimizing, we have to re-create dematerialized objects.

​

Escape Analysis needs to store the state of dematierialized objects at each deoptimization point.

​

Chrome

Escape Analysis in Turbofan

let a = {x: null};

let b = {y: 5};

a.x = b;

if (i > 10) {

a.x.y = i;

}

foo();

return a.y.x;

​

​

Chrome

Escape Analysis in Turbofan

let a = {x: null};

let b = {y: 5};

a.x = b;

if (i > 10) {

a.x.y = i;

}

foo();

return a.y.x;

​

​

Virtual Object 1

​

+0: var_a_shape

+8: …

+16: …

+24: var_a_x

Chrome

Escape Analysis in Turbofan

let a = {x: null};

let b = {y: 5};

a.x = b;

if (i > 10) {

a.x.y = i;

}

foo();

return a.y.x;

​

​

Virtual Object 1

​

+0: var_a_shape

+8: …

+16: …

+24: var_a_x

Virtual Object 2

​

+0: var_b_shape

+8: …

+16: …

+24: var_b_y

Chrome

Escape Analysis in Turbofan

let a = {x: null};

let b = {y: 5};

a.x = b;

if (i > 10) {

a.x.y = i;

}

foo();

return a.y.x;

​

​

Virtual Object 1

​

+0: var_a_shape

+8: …

+16: …

+24: var_a_x

Virtual Object 2

​

+0: var_b_shape

+8: …

+16: …

+24: var_b_y

Chrome

Escape Analysis in Turbofan

let a = {x: null};

let b = {y: 5};

a.x = b;

if (i > 10) {

a.x.y = i;

}

foo();

return a.y.x;

​

Virtual Object 1

​

+0: var_a_shape

+8: …

+16: …

+24: var_a_x

Virtual Object 2

​

+0: var_b_shape

+8: …

+16: …

+24: var_b_y

Chrome

Escape Analysis in Turbofan

let a = {x: null};

let b = {y: 5};

a.x = b;

if (i > 10) {

a.x.y = i;

}

foo();

return a.y.x;

​

Virtual Object 1

​

+0: var_a_shape

+8: …

+16: …

+24: var_a_x

Virtual Object 2

​

+0: var_b_shape

+8: …

+16: …

+24: var_b_y

Chrome

Escape Analysis in Turbofan

let a = {x: null};

let b = {y: 5};

a.x = b;

if (i > 10) {

a.x.y = i;

}

foo();

return a.y.x;

​

Virtual Object 1

​

+0: var_a_shape

+8: …

+16: …

+24: var_a_x

Virtual Object 2

​

+0: var_b_shape

+8: …

+16: …

+24: var_b_y

+0: shape of {x:?}

+8: …

+16: …

+24:

+0: shape of {y:?}

+8: …

+16: …

+24: Φ(5,i)

Remember Deoptimization Data

Chrome

Escape Analysis in Turbofan

let a = {x: null};

let b = {y: 5};

a.x = b;

if (i > 10) {

a.x.y = i;

}

foo();

return a.y.x; Φ(5,i)

​

Virtual Object 1

​

+0: var_a_shape

+8: …

+16: …

+24: var_a_x

Virtual Object 2

​

+0: var_b_shape

+8: …

+16: …

+24: var_b_y

Chrome

Conclusion

• Escape analysis avoids allocating temporary object.
• This allows for simpler code without performance penalty.
• V8 can dematerialize objects despite deoptimization.
• Limits of escape analysis are: escaping uses, index access, and using the object identity dynamically.

Chrome