Module SSA

Provides classes for working with static single assignment form (SSA).

We compute SSA form based on the intra-procedural CFG, without any call graph information. This means that we have to make worst-case assumptions about the possible effects of function calls and yield:

  • For a variable x declared in a function f, if x has assignments in a function other than f, then any function call and yield expression is assumed to write x.
  • If x is not written outside f, then function calls can never affect x, while yield expressions in functions other than f still may affect it.

This is modelled as follows.

Within each function g that accesses a variable x declared in an enclosing function f, we introduce a pseudo-assignment to x called a capture of x at the beginning of g that (conceptually) captures the current value of x.

Additionally, we introduce re-captures for x in the following places:

  • At any function call and yield, if x is assigned outside f.
  • At any yield outside f, if x is not assigned outside f.

Re-captures are introduced only where needed, that is, where there is a live use of x after the re-capture.

To see why re-captures need to be placed at yield expressions, consider the following function:

function k() {
  var x = 0;

  function* iter() {
    console.log(x);
    yield;
    console.log(x);
  }

  var gen = iter();
  gen.next();
  ++x;
  gen.next();
}

Here, iter has a capture for x at its beginning, and a re-capture at the yield to reflect the fact that x is incremented between the two console.log calls.

In the above example, x is only assigned inside its declaring function k, so function calls and yield expressions inside k cannot affect it.

Consider another example:

function* k() {
  var x = 0;
  console.log(x);
  yield () => ++x;
  console.log(x);
}
var gen = k();
gen.next().value();
gen.next();

Here, x is assigned outside its declaring function k, so the yield expression in k induces a re-capture of x to reflect the fact that x is incremented between the two console.log calls.

Import path

semmle.javascript.SSA

Imports

javascript

Provides classes for working with JavaScript programs, as well as JSON, YAML and HTML.

Classes

SsaDefinition

An SSA definition.

SsaExplicitDefinition

An SSA definition that corresponds to an explicit assignment or other variable definition.

SsaImplicitDefinition

An SSA definition that does not correspond to an explicit variable definition.

SsaImplicitInit

An SSA definition representing the implicit initialization of a variable at the beginning of its scope.

SsaPhiNode

An SSA phi node, that is, a pseudo-definition for a variable at a point in the flow graph where otherwise two or more definitions for the variable would be visible.

SsaPseudoDefinition

An SSA definition that has no actual semantics, but simply serves to merge or filter data flow.

SsaRefinementNode

A refinement node, that is, a pseudo-definition for a variable at a point in the flow graph where additional information about this variable becomes available that may restrict its possible set of values.

SsaSourceVariable

A variable that can be SSA converted, that is, a local variable.

SsaVariable

An SSA variable.

SsaVariableCapture

An SSA definition representing the capturing of an SSA-convertible variable in the closure of a nested function.