894596 - IonMonkey: inline global variable

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Hannes Verschore [:h4writer]]

V8 has added this same optimization, increasing their score on octane-richards with 5%.

The idea is to mark global variables as constants and use their value in scripts, instead of adding code the get the value of the variable. This enables more optimizations, since we have the real value.

Comment 1

[Hannes Verschore [:h4writer]]

First impression is that we can do better. We can inline any property access on a singleton object that is constant. The idea would be to add an extra flag on the shape "maybeConstant()". Allowing us to inline that value and bailout when that would change.

Comment 2

[Hannes Verschore [:h4writer]]

Attachment: bug894596-inline-constant-prop: WIP

Ok I had some fun with this. I enabled inlining of GETPROP and GETGNAME using the flags on a shape to know if a property is constant or not.

(Note: I'm not invalidating ioncode yet. So if a property goes from constant to non_constant, during execution we will do wrong things. That's the next todo for this. This is only to measure potential.)

>    105 IsConstant
>      1 Richards: 27010
>   3480 IsConstant
>      1 DeltaBlue: 27003
>    454 IsConstant
>      1 Crypto: 24528
>      1 RayTrace: 34187
>      1 EarleyBoyer: 27048
>      1 RegExp: 3949
>     20 IsConstant
>      1 Splay: 17643
>      1 NavierStokes: 27492
>      1 ----
>      1 Score (version 7): 20540

So currently this inlines constants in richards/deltablue/crypto and splay.

Though I can only see an improvement on richards:
> trunk:                             26200
> trunk + patch:                     25400
> trunk + patch + remove shapeguard: 27000

So that would be a 4%-7% improvement. Similar to what v8 clocked.
But this is only if we can remove the shapeguard.

Originally I thought to implement this idea in StackTypes etc, but when I talked to Brian before starting this experiment he pointed me to Shapes. So I assumed that we would differentiate the shapes w/wo constant shape. That way we could just add shapeGuard to the lastProperty() and be fine. (If we would split the tree when a property changes from constant to non-constant). 

Now I think we need to come with a way to remove the shapeguard. I.e. when doing setprop/setgname on shapes that are marked "constant" recompile all scripts that depend on this... Else there isn't really a reason to add this.

Comment 3

[Hannes Verschore [:h4writer]]

Exemple testcase that fails, since we don't recompile upon changing a "constant" marked property:

>try {} catch(e){}
>var j = 1;
>
>function test() {
>  return j
>}
>
>for(var i = 0; i < 2000; i++) {
>  if (i==1500)
>    j = 2;
>  print(test());
>}

Comment 4

[Kannan Vijayan [:djvj]]

The only way to avoid guards is to have the shape changes trigger invalidation.  This should be doable, though.

We can't add a pointer to an invalidation list to Shapes, since it'll bloat them.

However, we can keep a HashTable (hanging off of IonCompartment) that maps Shapes to IonCodes that need to be invalidated if they change.

The only thing to keep in mind is that the table needs to be cleared (and IonCode invalidated) whenever we sweep shapes or do shape regeneration.

Comment 5

[Till Schneidereit [:till]]

This has just been brought up on es-discuss[1] and I agree with Filip: `var foo; if (foo) {..}` is probably expected by many developers to be optimized out.


[1]: https://mail.mozilla.org/pipermail/es-discuss/2013-November/035049.html

Comment 6

[Kannan Vijayan [:djvj]]

Stealing this (talked to Hannes, and he's ok with it).

Comment 7

[Hannes Verschore [:h4writer]]

This potentially also gives a 40000 to 42000 increase on deltablue. (inlining Direction.* and Strength.*)

Comment 8

[Kannan Vijayan [:djvj]]

After some discussion on IRC, there seems to be a clean way of supporting this optimization by leveraging TI, and extending TypeSets to be able to store single values.  Either a typeset is in Single-Value mode, in which case it holds a value directly, or in Regular mode, in which case it behaves as TypeSets do currently.

Construction of TypeObjects for singleton-typed objects is lazy, and done on-demand when optimizing on singleton-typed objects.

When the singleton TypeObject is constructed, its typesets can be filled with the object values instead of the types of the object values.  This then makes these values available for constraint-based optimization.

Comment 9

[Kannan Vijayan [:djvj]]

Attachment: inferred-constant-optimization.patch

This patch builds, passes jit-tests.

On linux64, I clocked the following improvements on octane (20 runs with patch, 20 runs without):

DeltaBlue improves by about 4.75%
SplayLatency improves by about 6.25%
PdfJS improves by about 2.8%
Box2D improves by about 3%
Gameboy improves by about 1.8%
RegExp improves by 2.86%
Splay improves by 1.5%
MandreelLatency improves by 6%
Mandreel improves by 1.5%

Overall score improves by 1.8%

Comment 10

[Kannan Vijayan [:djvj]]

Ok, I'm running this in try and getting failures, although jit-tests passes for all my builds on linux (debug/opt/debugopt x arm/x64/x86).  Did some fixups and trying again now.

Here's an explanation of how this works:

We take advantage of the fact that TypeObjects for Singleton-typed objects are generated lazily.  For these objects, when we lazily construct the TypeObject, we know the exact value in the slot value represented by a given TypeSet.  If this value is expected not to change, then the typeset is flagged with an "InferredConstant" bit.

If a new value is stored to a heap slot described by an InferredConstant bit, then the InferredConstant bit is cleared and any constraints triggered.

During GetProp, if the type of a particular value is a Singleton, and the heap typeset for the property is marked InferredConstant, then a constraint can be attached and the constant value inspected from the object and embedded into the jitcode.

During SetProp and SetElem, we have to take care never to generate optimized sets to slots that may be InferredConstant, since the optimized writes would not clear the flag on the typeset and trigger constraints.

The last piece is figuring out which slots are likely to be constant, when creating the singleton TypeObject.  This is done using a hinting mechanism on shapes.  Every shape acquires an "overwritten" bit.

When a new slotful shape is created for a singleton object, the overwritten bit is clear.  Any write to a slot on a singleton object will clear the overwritten bit.  During lazy TypeObject construction, the shape of the object is consulted for the OVEWRITTEN bit.  If the slot has never been overwritten since creation, then it is inferred that it is likely to stay constant, and the InferredConstant bit is set in the TypeSet.



Potential holes:

I'm not sure if I'm covering all the write cases properly.  I added checks to generation of JSOP_SETPROP and JSOP_GETPROP in IonBuilder to not optimize writes to these fields.  I think baseline jitcode still needs to be updated to make sure to trigger constraints properly on slot updates.

One option is to change IonBuilder and Baseline so that if they are about to generate code that might set InferredConstant slots, then they eagerly clear the InferredConstant bit on the TypeSet before proceeding.  This will actively invalidate all code relying on the assumed constant.

Anyway.. Brian: can you take a look at this patch and let me know if the general approach is sound?  And give feedback on potential holes in the implementation, the holes mentioned above, and the relative merits of different approaches for fixing them?

Comment 11

[Kannan Vijayan [:djvj]]

Try run is still not looking good.  This very clearly has unaddressed holes:

https://tbpl.mozilla.org/?tree=Try&rev=a759965fa3c7

Comment 12

[Brian Hackett [Laid off!]]

(In reply to Kannan Vijayan [:djvj] from comment #10)
> Ok, I'm running this in try and getting failures, although jit-tests passes
> for all my builds on linux (debug/opt/debugopt x arm/x64/x86).  Did some
> fixups and trying again now.

Generally I think this patch looks really good, and the approach looks sound.  A few comments below but from the stacks I saw on the try run it's not clear why things are crashing.  I would think that if the optimization is buggy we would get incorrect behavior rather than crashes, since it just causes Ion to bake in a constant, which would be traced and accounted for properly by other optimized code.

> I'm not sure if I'm covering all the write cases properly.  I added checks
> to generation of JSOP_SETPROP and JSOP_GETPROP in IonBuilder to not optimize
> writes to these fields.  I think baseline jitcode still needs to be updated
> to make sure to trigger constraints properly on slot updates.
> 
> One option is to change IonBuilder and Baseline so that if they are about to
> generate code that might set InferredConstant slots, then they eagerly clear
> the InferredConstant bit on the TypeSet before proceeding.  This will
> actively invalidate all code relying on the assumed constant.

We don't want IonBuilder to be actively making changes to type information; this requires a JSContext, which IonBuilder doesn't have (except during the definite properties analysis) and letting the compiler change things leads to some weird behaviors.

I think we want both IonBuilder and Baseline to be generating caches when they might be overwriting inferred constants.  With the patch, we'll end up making a lot of slow calls on SetProp since somePropertyMightBeInferredConstant() returns true on unknownObject() type sets, which are a lot more common in web code than in benchmarks, and we want to still be able to emit caches in these cases.  Making this change should also let you remove somePropertyMightBeInferredConstant.

For the inline caches to work correctly with inferredConstant(), we need a couple things:

- Generated stubs which might be on inferredConstant() objects need to guard on both the shape and type of objects they are updating.  Baseline ICs should already do this, and Ion ICs will do this if the needsBarrier bit has been set on the cache (see IonBuilder::setPropTryCache).

- When generating a stub a VM call needs to be made that clears the inferred constant bits.  I think that Ion and Baseline already do this.

Comment 13

[Kannan Vijayan [:djvj]]

Went back and re-wrote this patch.  The earlier failures were because I had some crufty changes form when I was prototyping the work that I forgot to remove.

The new patches do better on try, but still orange on a few tests due to TI errors probably caused by these patches.  Still, getting pretty close.

Comment 14

[Kannan Vijayan [:djvj]]

Attachment: 1-add-overwritten-flag-to-shape.patch

Comment 15

[Kannan Vijayan [:djvj]]

Attachment: 2-add-inferred-constant-flag-to-typeobject.patch

Comment 16

[Kannan Vijayan [:djvj]]

Attachment: 3-use-inferred-constant-flag.patch

Comment 17

[Kannan Vijayan [:djvj]]

Better on try, still failing some android tests with a crash on ::generateTypeConstraint (weirdly, for ConstraintDataFreezeObjectForTypedArrayData.. not the constraint I added).

Try run here: https://tbpl.mozilla.org/?tree=Try&rev=93019dc8e9c5

Comment 18

[Brian Hackett [Laid off!]]

Taking this, at Kannan's request.

Comment 19

[Kannan Vijayan [:djvj]]

Just gonna post my latest revision of patches having only ARM mochitest(3) failures.

Comment 20

[Kannan Vijayan [:djvj]]

Attachment: 1-add-overwritten-flag-to-shape.patch

Comment 21

[Kannan Vijayan [:djvj]]

Attachment: 2-add-inferred-constant-flag-to-typeobject.patch

Comment 22

[Kannan Vijayan [:djvj]]

Attachment: 3-use-inferred-constant-flag.patch

Comment 23

[Brian Hackett [Laid off!]]

Attachment: patch

This patch seems to fix the orange.  The problem was that we were trying to bake in the view data and length of a typed array which didn't have singleton type, which isn't possible and was causing the inference code to crash.  This patch also makes a few fixes and does some cleanups / simplifications / renaming.

Comment 24

[Jan de Mooij [:jandem]]

Comment on attachment 8477894 [details] [diff] [review]
patch

Review of attachment 8477894 [details] [diff] [review]:
-----------------------------------------------------------------

Nice, this is much cleaner and simpler than I expected.

::: js/src/jit/IonBuilder.cpp
@@ +8792,5 @@
> +
> +    Value constVal = UndefinedValue();
> +    if (objTypes->propertyIsConstant(constraints(), NameToId(name), &constVal)) {
> +        IonSpew(IonSpew_MIR, "Optimized constant property at %s:%d (line %d)",
> +                script()->filename(), script()->lineno(), PCToLineNumber(script(), pc));

Nit: spew("Optimized constant property");

If the problem is that IonBuilder::spew() does not include the script's lineno, just PCToLineNumber, we should fix spew() instead.

@@ +9417,5 @@
>      if (!setPropTryTypedObject(&emitted, obj, name, value) || emitted)
>          return emitted;
>  
> +    // Do not emit optimized stores to slots that may be constant.
> +    if (!objTypes || !objTypes->propertyMightBeConstant(constraints(), NameToId(name))) {

If objTypes == nullptr, do we really want to optimize? Shouldn't it be:

  if (objTypes && !objTypes->...)

?

Comment 25

[Brian Hackett [Laid off!]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/3a545eb9828b

Comment 26

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/3a545eb9828b

Comment 27

[Jan de Mooij [:jandem]]

This didn't affect benchmarks much, I think because it only handles GETPROP. This bug was filed for the global (GETGNAME) case.

See the micro-benchmark below, it'd be great if we could bake in "gx" there.

var gx = 2;
function f() {
    var t = new Date;
    var res = 0;
    for (var i=0; i<1000000; i++) {
	for (var j=0; j<gx; j++)
	    res += gx;
    }
    print(new Date - t);
}
f();

Comment 28

[Brian Hackett [Laid off!]]

Attachment: static name patch

This patch lets us inline global names and names from singleton scope objects.  This unfortunately ended up being more complicated than the original patch; global and static scope properties are defined before the property is actually written to, so we need to support non-defining writes that don't clear the constant flag.

Comment 29

[Jan de Mooij [:jandem]]

Comment on attachment 8480765 [details] [diff] [review]
static name patch

Review of attachment 8480765 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks for fixing this.

::: js/src/jit/BaselineIC.cpp
@@ +7451,5 @@
>      }
>  
>      if (IsCacheableSetPropWriteSlot(obj, oldShape, holder, shape)) {
> +        // For some property writes, such as the initial overwrite of global
> +        // global properties, TI will not mark the property as having been

Nit: "global global"

Comment 30

[Brian Hackett [Laid off!]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/686300375fd6

Comment 31

[Guilherme Lima]

This patch regressed format-xparb on the Mac machines on AWFY:
http://arewefastyet.com/#machine=11&view=single&suite=ss&subtest=format-xparb
http://arewefastyet.com/#machine=12&view=single&suite=ss&subtest=format-xparb

Comment 32

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/686300375fd6

Comment 33

[Brian Hackett [Laid off!]]

(In reply to Guilherme Lima from comment #31)
> This patch regressed format-xparb on the Mac machines on AWFY:
> http://arewefastyet.com/#machine=11&view=single&suite=ss&subtest=format-xparb
> http://arewefastyet.com/#machine=12&view=single&suite=ss&subtest=format-xparb

I'll try to look at this tomorrow.

Comment 34

[Chris Peterson [:cpeterson]]

And may also have regressed asmjs-ubench-skinning on "Firefox (no asmjs)" by 3.8%:

http://arewefastyet.com/#machine=11&view=single&suite=asmjs-ubench&subtest=skinning

Comment 35

[Brian Hackett [Laid off!]]

I filed bug 1063598 for the date-format-xparb regression.  Looking at AWFY, I don't see any regression or other change on asmjs-ubench-skinning.