Bug 67993 – Prediction tracking is not precise enough

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Filip Pizlo]

The predictions deduced from value profiles are not precise.  For example, we can identify something as being an array, or just as a cell, but we don't know when something is an object that is not an array.  We also don't have any way of distinguishing between Top (i.e. "could be anything") and Undefined/Null.  Prediction tracking should be at least precise enough to be able to identify common kinds of objects like JSFinalObject, JSString, and JSArray, and should be able to distinguish between a type being completely unknown and being, say, "Undefined or Null or Object".

[Filip Pizlo]

Created attachment 107158 [details]
the patch

I'm going to let this patch simmer for a bit.  I'm not yet completely convinced that it's neutral or that it actually works.

[WebKit Review Bot]

Attachment 107158 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/ChangeLog', u'Source..." exit_code: 1

Source/JavaScriptCore/wtf/BoundsCheckedPointer.h:249:  One line control clauses should not use braces.  [whitespace/braces] [4]
Source/JavaScriptCore/bytecode/PredictedType.cpp:126:  An else if statement should be written as an if statement when the prior "if" concludes with a return, break, continue or goto statement.  [readability/control_flow] [4]
Source/JavaScriptCore/bytecode/PredictedType.h:154:  The parameter name "profile" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/bytecode/PredictedType.h:157:  The parameter name "value" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/dfg/DFGPropagator.cpp:191:  An else should appear on the same line as the preceding }  [whitespace/newline] [4]
Total errors found: 5 in 13 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Early Warning System Bot]

Comment on attachment 107158 [details]
the patch

Attachment 107158 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/9660072

[Filip Pizlo]

Created attachment 107236 [details]
the patch - fix style

[Geoffrey Garen]

Comment on attachment 107236 [details]
the patch - fix style

View in context: https://bugs.webkit.org/attachment.cgi?id=107236&action=review

> Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj:813
> +		0FD82E82141F3FC900179C94 /* BoundsCheckedPointer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BoundsCheckedPointer.h; sourceTree = "<group>"; };
> +		0FD82E84141F3FDA00179C94 /* PredictedType.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = PredictedType.cpp; sourceTree = "<group>"; };

You'll need to add these guys to the other project files (JavaScriptCore.vcproj, etc.).

> Source/JavaScriptCore/bytecode/PredictedType.h:42
> +static const PredictedType PredictObjectOther   = 0x0010; // It's definitely an object but not JSFinalObject or JSArray.
> +static const PredictedType PredictSomeObject    = 0x0020; // It's some unknown subclass of JSObject.
> +static const PredictedType PredictObject        = 0x003f; // It's definitely a subclass of JSObject.

The distinction between these three object prediction terms is super confusing to me. Can you clarify somehow?

> Source/JavaScriptCore/bytecode/PredictedType.h:60
>  enum PredictionSource { WeakPrediction, StrongPrediction };
>  
>  inline bool isCellPrediction(PredictedType value)
>  {
> -    return (value & PredictCell) == PredictCell && !(value & ~(PredictArray | PredictionTagMask));
> +    return !!(value & PredictCell) && !(value & ~(PredictCell | PredictionTagMask));
> +}

Seems like this could all become an object with member functions, wrapping a uint16_t. Not necessary in this patch, though.

> Source/JavaScriptCore/wtf/BoundsCheckedPointer.h:7
> + *  This library is free software; you can redistribute it and/or
> + *  modify it under the terms of the GNU Library General Public
> + *  License as published by the Free Software Foundation; either
> + *  version 2 of the License, or (at your option) any later version.

Is this newly authored code or LGPL2 code from somewhere else? If newly authored, BSD license, please.

> Source/JavaScriptCore/wtf/BoundsCheckedPointer.h:38
> +class BoundsCheckedPointer {

Probably overkill to do in this patch, but it seems like this class could become an iterator for FixedArray<typename, size_t>. That would simplify the use case a bit, and guarantee that the data and the bounds checked pointer were in agreement about the data's size.

[Filip Pizlo]

(In reply to comment #5)
> (From update of attachment 107236 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=107236&action=review
> 
> > Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj:813
> > +		0FD82E82141F3FC900179C94 /* BoundsCheckedPointer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BoundsCheckedPointer.h; sourceTree = "<group>"; };
> > +		0FD82E84141F3FDA00179C94 /* PredictedType.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = PredictedType.cpp; sourceTree = "<group>"; };
> 
> You'll need to add these guys to the other project files (JavaScriptCore.vcproj, etc.).

Will do!

> 
> > Source/JavaScriptCore/bytecode/PredictedType.h:42
> > +static const PredictedType PredictObjectOther   = 0x0010; // It's definitely an object but not JSFinalObject or JSArray.
> > +static const PredictedType PredictSomeObject    = 0x0020; // It's some unknown subclass of JSObject.
> > +static const PredictedType PredictObject        = 0x003f; // It's definitely a subclass of JSObject.
> 
> The distinction between these three object prediction terms is super confusing to me. Can you clarify somehow?

PredictObjectOther = I definitely saw something that was neither JSFinalObject nor JSArray, but whatever it was, it was definitely a subclass of JSObject.

PredictSomeObject = I saw some objects but I was too lazy to figure out what kinds of objects they were.

PredictObject = This is not meant to be a value that we set PredictedType's to; it's a bit pattern we use to test if it would be OK to speculate that a value is a subtype of JSObject.  If we did set a variable to PredictObject, it would mean that we know for sure that this variable will point to every kind of object.

The interesting thing is what happens when you merge them:

PredictSomeObject + PredictFinalObject = PredictFinalObject.  PredictSomeObject means "I was too lazy to look beyond it being an object", so PredictFinalObject prevails.  Similarly for PredictSomeObject + <any other object prediction>.

PredictFinalObject + PredictOtherObject = PredictFinalObject|PredictOtherObject.  Note that this is not equal to PredictObject, but it is interpreted in a similar way.  It means: we know it's an object but we know that it would be unwise to speculate what kind of object it is.  But in this case the bitpattern still tells us something interesting: it tells us that we never saw arrays.

PredictFinalObject + PredictObject = PredictObject.  PredictObject means somebody definitely saw all kinds of objects, while PredictFinalObject means someone just saw JSFinalObjects.  So we take the union of the two, which is PredictObject.

At a thousand foot view, PredictSomeObject and PredictObject sort of mean the same thing: they both mean that it's safe to assume, based on current profiling information, that the value is an object.  The difference is that:

1) If one guy says PredictSomeObject and another guy gives a different object prediction, then the latter guy wins.  If one guy says PredictObject, then he always trumps everything else.

2) We never explicitly set PredictObject as a prediction.  We only use it as a bitmask to see if we saw any kinds of objects.  The only way that a value prediction would become exactly PredictObject is if we have evidence that suggests that we saw all of the following: JSFinalObject, JSArray, and some object that is neither JSFinalObject nor JSArray.

PredictOtherObject is used to distinguish seeing "some kind of object" (which is what PredictObject and PredictSomeObject do) and seeing an object that we definitely can't optimize for.  We can optimize for JSFinalObject (because it's easy to check that an object is JSFinalObject, so it's a shortcut for speculating on object).  We can, and do, optimize for JSArray.  But we don't want to emit JSFinalObject speculation if we know for sure that the value may be, for instance, JSDateInstance.  Since we don't want to have a bit for every possible subclass of JSObject in PredictedType, we use PredictOtherObject as a placeholder.

Note that it would be unwise to replace PredictOtherObject with PredictObject, since PredictObject means that we've definitely seen JSFinalObject and JSArray.  If PredictOtherObject was just set to PredictObject then we wouldn't be able to detect if an object is never a JSFinalObject, since anytime the value profiler notices, say, a JSFunction, then it would set the bit that corresponds to JSFinalObject (since PredictObject has all object bits set).

> 
> > Source/JavaScriptCore/bytecode/PredictedType.h:60
> >  enum PredictionSource { WeakPrediction, StrongPrediction };
> >  
> >  inline bool isCellPrediction(PredictedType value)
> >  {
> > -    return (value & PredictCell) == PredictCell && !(value & ~(PredictArray | PredictionTagMask));
> > +    return !!(value & PredictCell) && !(value & ~(PredictCell | PredictionTagMask));
> > +}
> 
> Seems like this could all become an object with member functions, wrapping a uint16_t. Not necessary in this patch, though.

Yeah, we're definitely heading in that direction!

> 
> > Source/JavaScriptCore/wtf/BoundsCheckedPointer.h:7
> > + *  This library is free software; you can redistribute it and/or
> > + *  modify it under the terms of the GNU Library General Public
> > + *  License as published by the Free Software Foundation; either
> > + *  version 2 of the License, or (at your option) any later version.
> 
> Is this newly authored code or LGPL2 code from somewhere else? If newly authored, BSD license, please.

New code.  I copy pasted the wrong license header, I guess!  I'll pull in a BSD license header.

> 
> > Source/JavaScriptCore/wtf/BoundsCheckedPointer.h:38
> > +class BoundsCheckedPointer {
> 
> Probably overkill to do in this patch, but it seems like this class could become an iterator for FixedArray<typename, size_t>. That would simplify the use case a bit, and guarantee that the data and the bounds checked pointer were in agreement about the data's size.

Yup!

[Filip Pizlo]

Created attachment 107272 [details]
the patch - fix license, add build stuff

[Oliver Hunt]

Comment on attachment 107272 [details]
the patch - fix license, add build stuff

What happens if we see "o.a" and o varies between an array and an ordinary object?  do we get strong-object or weak-array?

[Geoffrey Garen]

Based on your explanation, I think something like this would help:

+static const PredictedType PredictObjectMask        = 0x003f; // Bitmask used for testing for any kind of object prediction.
+static const PredictedType PredictFinalObject   = 0x0001; // It's definitely a JSFinalObject.
+static const PredictedType PredictArray         = 0x0002; // It's definitely a JSArray.
+static const PredictedType PredictObjectOther   = 0x0010; // It's definitely an object other than JSFinalObject or JSArray.
+static const PredictedType PredictObjectUnknown    = 0x0020; // It's definitely an object, but we didn't record enough information to know more.

[Filip Pizlo]

(In reply to comment #8)
> (From update of attachment 107272 [details])
> What happens if we see "o.a" and o varies between an array and an ordinary object?  do we get strong-object or weak-array?

If by "ordinary object" you mean JSFinalObject then we get Strong|PredictArray|PredictFinalObject.  If by "ordinary object" you mean some subclass of JSObject other than JSFinalObject then we get Strong|PredictArray|PredictObjectOther.  If by "ordinary object" you mean that we inferred that by seeing that there were GetById/GetByVal's executed on the object, or that it came out of some op that's known to return objects but we don't know anything else about it, then we just get Strong|PredictArray.  If by "ordinary object" you mean that we saw a JSFinalObjects and other subclasses of JSObject then we get Strong|PredictArray|PredictFinalObject|PredictObjectOther.  Note that there are bits left behind for other kinds of objects in the future (functions, typed arrays, etc), so this is still different from PredictObject.  Currently we won't ever get PredictObject in any PredictedType variable because of those missing bits, and because nothing in the analysis every returns PredictObject.

[Filip Pizlo]

(In reply to comment #9)
> Based on your explanation, I think something like this would help:
> 
> +static const PredictedType PredictObjectMask        = 0x003f; // Bitmask used for testing for any kind of object prediction.
> +static const PredictedType PredictFinalObject   = 0x0001; // It's definitely a JSFinalObject.
> +static const PredictedType PredictArray         = 0x0002; // It's definitely a JSArray.
> +static const PredictedType PredictObjectOther   = 0x0010; // It's definitely an object other than JSFinalObject or JSArray.
> +static const PredictedType PredictObjectUnknown    = 0x0020; // It's definitely an object, but we didn't record enough information to know more.

Yeah, that's better.  I'll make that change and then land.

[Filip Pizlo]

(In reply to comment #10)
> (In reply to comment #8)
> > (From update of attachment 107272 [details] [details])
> > What happens if we see "o.a" and o varies between an array and an ordinary object?  do we get strong-object or weak-array?
> 
> If by "ordinary object" you mean JSFinalObject then we get Strong|PredictArray|PredictFinalObject.  If by "ordinary object" you mean some subclass of JSObject other than JSFinalObject then we get Strong|PredictArray|PredictObjectOther.  If by "ordinary object" you mean that we inferred that by seeing that there were GetById/GetByVal's executed on the object, or that it came out of some op that's known to return objects but we don't know anything else about it, then we just get Strong|PredictArray.  If by "ordinary object" you mean that we saw a JSFinalObjects and other subclasses of JSObject then we get Strong|PredictArray|PredictFinalObject|PredictObjectOther.  Note that there are bits left behind for other kinds of objects in the future (functions, typed arrays, etc), so this is still different from PredictObject.  Currently we won't ever get PredictObject in any PredictedType variable because of those missing bits, and because nothing in the analysis every returns PredictObject.

Ah sorry, I missed the part where "o" is the base of "o.a".  There are two cases:

1) Value profiling tells us that o is always an array.  Then we just get Strong|PredictArray, because: (a) o.a backward propagates Strong|PredictSomeObject, (b) o's value source forward propagates Strong|PredictArray, and (c) when they meet, mergePredictions(Strong | PredictSomeObject, Strong | PredictArray) = Strong | PredictArray.  The intuition behind PredictSomeObject is that it's a prediction that's only meant to hold if no other prediction is made, or if all of the other predictions say that it isn't an object (which it clearly might be if they user wrote that code).

2) Value profiling tells us that o is sometimes an array and sometimes some other object.  Then my previous comment holds.

[Filip Pizlo]

Landed in r95115.

[Csaba Osztrogonác]

(In reply to comment #13)
> Landed in r95115.

Heyyy, it broke everything. :S

[Filip Pizlo]

(In reply to comment #14)
> (In reply to comment #13)
> > Landed in r95115.
> 
> Heyyy, it broke everything. :S

Yes, yes it did.  Build fix committed in r95116.