TypeInference

Type Inference is Brian Hackett's type inference engine for JavaScript. It is a whole-program, hybrid static and dynamic analysis that attempts to find the set of possible types for stack slots, arguments, and local variables.

Some information can only be deduced at run-time, for example, the effects of an eval or integer overflow. If assumptions about type information are broken, the analysis is re-run on anything depending on that information. This can cause methods to be recompiled, even replacing currently running methods on the stack.

Bug 608741 is the meta bug for integrating into JM.

The project repository is http://hg.mozilla.org/projects/jaegermonkey.

Planning

Firefox 5

In order to ship with Firefox 5, tentatively we must land by the end of March 2011. Minimally, this is what we should aim for:

• Type inference engine integrated into JägerMonkey, with cross-branch register allocation for both GP and FPU registers.
• With TI enabled, JägerMonkey is epsilon faster than JägerMonkey without type inference.
• JägerMonkey and TraceMonkey, with TI disabled, are no slower than pre-TI.
• Browser works and tinderbox is green.

Completed Work

The inference engine is working in the shell. GP and FPU register allocation works, as does registers across control-flow edges.

Next Steps

• JS peers need to read, understand, and audit the jaegermonkey branch.
• bug 619425 Find, understand, and fix benchmarks which have regressed.
• bug 613221 Type inference data structures need memory management.
• bug 619433 Integrate TI+JM into the browser.
• bug 619415 Fuzz bugs and the like.
• Possible retuning of the trace profiler.

Technology

TODO: explain inference algorithm.

Type inference has a somewhat invasive integration into the engine as a whole, but is designed to integrate with JaegerMonkey with as few changes to the compiler as possible. It uses the existing FrameState API to act as an oracle for JaegerMonkey's register allocator and type information queries.

The linear scan register allocator uses liveness information computed in a backwards pass.

Future optimizations

Post Firefox 5, we're looking to:

• Add loop invariant code motion, hoisting guards, and possibly even array dslots loads.
• Common sub-expression elimination within basic blocks.
• Function inlining.
• Combine js::Shape, type objects, and JSObject::prototype.
• Use object type information to eliminate shape guards.