TypeInference - Revision history

Dvander: /* Implementation */

2010-12-15T23:26:30Z

Implementation

← Older revision		Revision as of 23:26, 15 December 2010
Line 79:		Line 79:
	For both, the type information forms the constraint graph necessary for propagating new additions to type sets, causing recompilation.		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~~, and thus~~ the interpreter and VM helpers must carefully place type checks where necessary.		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.		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:		To account for this, there are two JM modifications:
	* As loop-carried ~~register~~ are allocated, previously generated out-of-line paths need to be patched to restore the register.		* As loop-carried registers are allocated, previously generated out-of-line paths need to be patched to restore the register.
	* ~~The entry~~ of the loop is deferred until all loop-carried registers are ~~unknown~~.		* Code generation of the loop entry is deferred until all loop-carried registers are known.

	= Future optimizations =		= Future optimizations =

Dvander at 22:50, 15 December 2010

2010-12-15T22:50:38Z

← Older revision		Revision as of 22:50, 15 December 2010
Line 23:		Line 23:

	== Some Numbers ==		== Some Numbers ==

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

	{\| cellspacing="10" cellpadding="1" border="0"		{\| cellspacing="10" cellpadding="1" border="0"
	\|-		\|-

Dvander at 22:49, 15 December 2010

2010-12-15T22:49:56Z

← Older revision		Revision as of 22:49, 15 December 2010
Line 23:		Line 23:

	== Some Numbers ==		== Some Numbers ==
	{\| ~~width="50%"~~ cellspacing="1" cellpadding="1" border="0"		{\| cellspacing="10" cellpadding="1" border="0"
	\|-		\|-
	\|		\|
	\| align="right" \| '''v8-crypto'''		\| align="right" \| '''v8-crypto'''
	\| align="right" \| '''access-fannkuch(10)'''		\| align="right" \| '''access-fannkuch(10)'''
	\| align="right" \| '''sudoku'''		\| align="right" \| '''sudoku solver'''
	\| align="right" \| '''array microbench'''		\| align="right" \| '''array microbench'''
	\|-		\|-
	\| JM+TI		\| '''JM+TI'''
	\| align="right" \| 56ms		\| align="right" \| 56ms
	\| align="right" \| 832ms		\| align="right" \| 832ms
Line 37:		Line 37:
	\| align="right" \| 662ms		\| align="right" \| 662ms
	\|-		\|-
	\| v8		\| '''V8'''
	\| align="right" \| 51ms		\| align="right" \| 51ms
	\| align="right" \| 1552ms		\| align="right" \| 1552ms
Line 43:		Line 43:
	\| align="right" \| 983ms		\| align="right" \| 983ms
	\|-		\|-
	\| JM		\| '''JM'''
	\| align="right" \| 97ms		\| align="right" \| 97ms
	\| align="right" \| 1930ms		\| align="right" \| 1930ms
Line 49:		Line 49:
	\| align="right" \| 3173ms		\| align="right" \| 3173ms
	\|-		\|-
	\| JM+TM		\| '''JM+TM'''
	\| align="right" \| 127ms		\| align="right" \| 127ms
	\| align="right" \| 1913ms		\| align="right" \| 1913ms

Dvander at 22:48, 15 December 2010

2010-12-15T22:48:45Z

@@ Line 21: / Line 21: @@
 The inference engine is working in the shell. GP and FPU register allocation works, as does registers across control-flow edges.
 == Next Steps  ==
@@ Line 37: / Line 72: @@
 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 eventually be merged with js::Shape and JSObject::prototype. For both, the type information forms the constraint graph necessary for propagating new additions to type sets, causing recompilation if necessary.
+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.
 This propagation is critical for correctness in code that depends on type inference information, and thus the interpreter and VM helpers must carefully place type checks where necessary.

Dvander: /* Implementation */

2010-12-15T21:33:06Z

Implementation

← Older revision		Revision as of 21:33, 15 December 2010
Line 38:		Line 38:

	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 eventually be merged with js::Shape and JSObject::prototype. For both, the type information forms the constraint graph necessary for propagating new additions to type sets, causing recompilation if necessary.		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 eventually be merged with js::Shape and JSObject::prototype. For both, the type information forms the constraint graph necessary for propagating new additions to type sets, causing recompilation if necessary.

			This propagation is critical for correctness in code that depends on type inference information, and thus the interpreter and VM helpers must carefully place type checks where necessary.

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

Dvander at 21:27, 15 December 2010

2010-12-15T21:27:02Z

← Older revision		Revision as of 21:27, 15 December 2010
Line 33:		Line 33:
	= Technology =		= Technology =

	~~:TODO: explain inference algorithm.~~		== 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 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 eventually be merged with js::Shape and JSObject::prototype. For both, the type information forms the constraint graph necessary for propagating new additions to type sets, causing recompilation if necessary.

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

Dvander at 21:17, 15 December 2010

2010-12-15T21:17:40Z

← Older revision		Revision as of 21:17, 15 December 2010
Line 37:		Line 37:
	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 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.		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 register are allocated, previously generated out-of-line paths need to be patched to restore the register.
			* The entry of the loop is deferred until all loop-carried registers are unknown.

	= Future optimizations =		= Future optimizations =

Dvander: Created page with "[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 ana..."

2010-12-15T20:28:39Z

Created page with "[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 ana..."

New page

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

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

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

← Older revision		Revision as of 22:49, 15 December 2010
Line 23:		Line 23:

	== Some Numbers ==		== Some Numbers ==
	{\| ~~width="50%"~~ cellspacing="1" cellpadding="1" border="0"		{\| cellspacing="10" cellpadding="1" border="0"
	\|-		\|-
	\|		\|
	\| align="right" \| '''v8-crypto'''		\| align="right" \| '''v8-crypto'''
	\| align="right" \| '''access-fannkuch(10)'''		\| align="right" \| '''access-fannkuch(10)'''
	\| align="right" \| '''sudoku'''		\| align="right" \| '''sudoku solver'''
	\| align="right" \| '''array microbench'''		\| align="right" \| '''array microbench'''
	\|-		\|-
	\| JM+TI		\| '''JM+TI'''
	\| align="right" \| 56ms		\| align="right" \| 56ms
	\| align="right" \| 832ms		\| align="right" \| 832ms
Line 37:		Line 37:
	\| align="right" \| 662ms		\| align="right" \| 662ms
	\|-		\|-
	\| v8		\| '''V8'''
	\| align="right" \| 51ms		\| align="right" \| 51ms
	\| align="right" \| 1552ms		\| align="right" \| 1552ms
Line 43:		Line 43:
	\| align="right" \| 983ms		\| align="right" \| 983ms
	\|-		\|-
	\| JM		\| '''JM'''
	\| align="right" \| 97ms		\| align="right" \| 97ms
	\| align="right" \| 1930ms		\| align="right" \| 1930ms
Line 49:		Line 49:
	\| align="right" \| 3173ms		\| align="right" \| 3173ms
	\|-		\|-
	\| JM+TM		\| '''JM+TM'''
	\| align="right" \| 127ms		\| align="right" \| 127ms
	\| align="right" \| 1913ms		\| align="right" \| 1913ms