JsCFA

An Abstract Interpreter for JavaScript with Perfect Call/Return Matching.

This a control flow analyzer for JavaScript based on h-CFA. JsCFA can match call/return flow perfectly, and it filters local data flow (stack variables) via abstract garbage collection. Therefore, JsCFA provides very precise result of value-flow analysis.

Applications:

1. Static Type Inference.
2. Call Graph Based Interprocedure Analysis and Optimization.
3. Devirtualization Optimization.

Example

functionf(x){if(x>0){returnfunction(y){returnx*y};}else{returnfunction(z){returnz-x};}}vara=f(2)(0);varb=f(f(a)(a));

The analysis result from JsCFA, which has exact control flows and types:

z -> JSNumber(VariableNumber)
x -> JSNumber(VariableNumber)
y -> JSNumber(VariableNumber)
b -> FunctionObject : function(z) {
return z - x;
}
FunctionObject : function(y) {
return x * y;
}
f -> FunctionObject : function f(x) {
if (x > 0) {
return function(y) {
return x * y;
};
} else {
return function(z) {
return z - x;
};
}
}
a -> JSNumber(VariableNumber)
360 msecs
Miss Match: 0

A more complex example for showing JsCFA type inference:

functiong(x,y){if(y==0){returnx;}else{returng({x: x},y-1);}}vara0=g("a0",0);vara1=g("a1",1);vara2=g(1,10);

There is a loop pointer that represents the recursive data type in the analysis result (object-sensitivity disabled):

a0 -> JSString(ConstantString(a0))
a2 -> JSNumber(ConstantNumber(1.0))
Object : JSString(ConstantString(x)) -> JSReference(21,-1)
JSString(ConstantString(__proto__)) -> JSReference(23,-1)
JSString(ConstantString(constructor)) -> JSReference(24,-1)
a1 -> JSString(ConstantString(a1))
Object : JSString(ConstantString(x)) -> JSReference(21,-1)
JSString(ConstantString(__proto__)) -> JSReference(23,-1)
JSString(ConstantString(constructor)) -> JSReference(24,-1)
x -> JSString(VariableString)
JSNumber(ConstantNumber(1.0))
Object : JSString(ConstantString(x)) -> JSReference(21,-1)
JSString(ConstantString(__proto__)) -> JSReference(23,-1)
JSString(ConstantString(constructor)) -> JSReference(24,-1)
g -> FunctionObject : function g(x, y) {
if (y == 0) {
return x;
} else {
return g({x: x}, y - 1);
}
}
y -> JSNumber(VariableNumber)
546 msecs
Miss Match: 0

Value map of above references:

JSReference(21,-1) ->
JSString(ConstantString(a1))
JSNumber(ConstantNumber(1.0))
Object : JSString(ConstantString(x)) -> JSReference(21,-1)
JSString(ConstantString(__proto__)) -> JSReference(23,-1)
JSString(ConstantString(constructor)) -> JSReference(24,-1)
JSReference(23,-1) ->
Object : JSString(ConstantString(toString)) -> JSReference(-22,-1)
JSString(ConstantString(__proto__)) -> JSReference(-2,-1)
JSString(ConstantString(constructor)) -> JSReference(-7,-1)