View source for TypeInference

[https://bugzilla.mozilla.org/show_bug.cgi?id=557407 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 <tt>eval</tt> 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.

[https://bugzilla.mozilla.org/show_bug.cgi?id=608741 Bug 608741] is the meta bug for integrating into JM.

The project repository is [http://hg.mozilla.org/projects/jaegermonkey 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.

== Some Numbers ==

Some initial numbers from tests where we know type inference does really well.

{| cellspacing="10" cellpadding="1" border="0"
|-
| 
| align="right" | '''v8-crypto''' 
| align="right" | '''access-fannkuch(10)'''
| align="right" | '''sudoku solver'''
| align="right" | '''array microbench'''
|-
| '''JM+TI'''
| align="right" | 56ms 
| align="right" | 832ms
| align="right" | 794ms
| align="right" | 662ms
|-
| '''V8'''
| align="right" | 51ms 
| align="right" | 1552ms
| align="right" | 871ms
| align="right" | 983ms
|-
| '''JM'''
| align="right" | 97ms 
| align="right" | 1930ms
| align="right" | 1120ms
| align="right" | 3173ms
|-
| '''JM+TM'''
| align="right" | 127ms 
| align="right" | 1913ms
| align="right" | 1170ms
| align="right" | 2120ms
|}


== Next Steps  ==

*JS peers need to read, understand, and audit the jaegermonkey branch.
*[https://bugzilla.mozilla.org/show_bug.cgi?id=619425 bug 619425] Find, understand, and fix benchmarks which have regressed.
*[https://bugzilla.mozilla.org/show_bug.cgi?id=613221 bug 613221] Type inference data structures need memory management.
*[https://bugzilla.mozilla.org/show_bug.cgi?id=619433 bug 619433] Integrate TI+JM into the browser.
*[https://bugzilla.mozilla.org/show_bug.cgi?id=619415 bug 619415] Fuzz bugs and the like.
*Possible retuning of the trace profiler.

= Technology =

== Implementation ==

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.

Type sets for stack slots are queried based on a script, program counter, and stack/local/argument index. Type information for object properties is stored in each JSObject, and contains the set of properties and types of those properties that can be visible from that object at any point in time. For each js::Shape, there is exactly one type object; but a type object can be shared across multiple shapes.

For both, the type information forms the constraint graph necessary for propagating new additions to type sets, causing recompilation.

This propagation is critical for correctness in code that depends on type inference information. Thus the interpreter and VM helpers must carefully place type checks where necessary, triggering a re-analysis if a new type is added to a type set.

The register allocator uses liveness information computed in a backwards pass. During loop compilation the compiler decides which values should be kept in registers across the backwards edge. That means the full set of loop-carried registers is not unknown until the bottom of the loop.

To account for this, there are two JM modifications:
* As loop-carried registers are allocated, previously generated out-of-line paths need to be patched to restore the register.
* Code generation of the loop entry is deferred until all loop-carried registers are known.

= 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.