prepack icon indicating copy to clipboard operation
prepack copied to clipboard

Refactor (abstract) value creations

Open NTillmann opened this issue 8 years ago • 0 comments

Prepack wraps all values into instance of (subtypes of) the Value class. Structurally identical values can end being represented as multiple values.

For concrete values, this just means that Prepack uses more memory than necessary. But for abstract values, this actually results in missed optimization opportunities.

Consider what happens when prepacking this code:

(function() {
  let x = Date.now();
  global.a = x + 1 + 2 + 3;
  global.b = x + 1 + 2 + 3;
})();

Prepack will actually have two different abstract value instances representing the expressions x + 1 + 2 + 3, and will serialize it twice. If Prepack would consistently fold structurally equivalent (abstract) values, then all these problems would go away.

So here's what should happen: All value creations should go through a new ValueManager class.

  1. All value constructor calls like new Number(...) should get replaced by calls to functions like realm.valueManager.createNumber(...).
  2. Those calls to realm.createAbstract which create algebraic expressions, meaning functional/pure/stateless/side-effect expressions, (see for example how binary expressions are created in BinaryExpression.js) should get replaced by calls to functions like realm.valueManager.createAbstractBinary(...).
  3. For all createAbstractXXX values, the value manager can try to apply constant folding, general simplification, and normalization. In particular, for logical expressions, consider doing value numbering and normalization to an if-then-else (ite) form, see here.
  4. Apply hash-consing to ensure that there's only one instance for each structurally unique value.
  5. Design a scheme how all those values can be garbage collected. This will become necessary, as every intermediate value will now be referenced by the value manager.
  6. #906: Once we have all a set of well-defined algebraic expressions identified, we can also consider hooking up an SMT solver such as Z3 in order to reason about and further simplify expressions. Especially the ability to simplify !!(x) and !(x) queries to constants might help greatly to reduce the number of execution paths. See here for some more ideas of what kind of optimizations we can do by hooking up an SMT solver, including refinement #620.

NTillmann avatar May 08 '17 18:05 NTillmann