747289 - Do some sort of CSE on DOM getters when possible

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Boris Zbarsky [:bzbarsky]]

There are some that should be trivial to CSE if only we can get the right metadata about them to the JIT.

Comment 1

[Nicolas B. Pierron [:nbp]]

Is this bug still valid?  Are we folding prefix of the DOM getters and setters when we can, or even the getter it-self if we have enough garantee on the getter — but I doubt it.

Comment 2

[Boris Zbarsky [:bzbarsky]]

> Is this bug still valid?

I think so, yes.

> Are we folding prefix of the DOM getters and setters when we can, or even the getter
> it-self if we have enough garantee on the getter 

We want to fold the prefix, of course, if we can.

We want to fold the getter itself if we can too; there are some that we do have enough info for that are somewhat commonly used in frameworks, I believe (localName, nodeType, tagName).

Comment 3

[Eric Faust [:efaust]]

The following seems to be true:

We should be able to CSE and hoist if necessary the DOM bottom-half call itself. We will of course have to perform the checks at compile time individually for each site.

There is also one guard instruction generated on the shape of one of the prototypes. While in theory there are cases in which this is safe to CSE this as well, it's not really tractable to attempt such a scheme for shape guards in general. If we try to think about this case in particular, it's still not easy to come up with a useful heuristic for when it is safe to move them (perhaps I am missing one, but I don't expect so).

I also posit the following:
We can do CSE on the getter call itself independently of the shapeguard that protects the use site. The returned value is valid iff we pass the guard, so leaving them before the constant usesites should leave us safe.

All of this is of course dependent on idempotency data to come from DOM codegen.

Comment 4

[Eric Faust [:efaust]]

It's also worth noting that idempotency isn't enough to move them. Justk nowing that the getter has no side effects is insufficient to avoid running it at every access, as the answer might change.

Comment 5

[Boris Zbarsky [:bzbarsky]]

Ah.  So... the cases I talked about above (localName, nodeType, tagName) never change.  Ever.

The case you're thinking of is something like .firstChild, where there are not side-effects but the answer could change if something modifies the DOM.

Comment 6

[Eric Faust [:efaust]]

In light of bug 773546 and bug 773549, it becomes *overwhelmingly* cleaner in the JIT to route the getters though the generic method call logic, which will handle all DOM specifics. If we do that, though, it will become very hard indeed to move such calls, as argument build is an inherently effectful operation, and is very hard to hoist en masse.

My question is this: Do we have any idea about how often this actually benefits us in the wild? 

The resulting code, even if we keep getters special to allow us to move this call, results in many dynamic guards, which is still faster than calling out to C++, but leaves a bit of a mess in its wake.

Comment 7

[Boris Zbarsky [:bzbarsky]]

> Do we have any idea about how often this actually benefits us in the wild? 

No.  We've never measured, because we've never had the option.

I'm not sure which "resulting code" comment 6 is talking about...  The code needed to properly CSE?

Comment 8

[Eric Faust [:efaust]]

Turns out we can do better than just "isConstant". I didn't know, but we have infrastructure in place to be able to say "as long as there are no DOM sets or function calls, we can hist this safely" which may apply to more than the constant did. Either way, we can add this third option when the time comes.

Comment 9

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to Eric Faust [:efaust] from comment #4)
> It's also worth noting that idempotency isn't enough to move them. Justk
> nowing that the getter has no side effects is insufficient to avoid running
> it at every access, as the answer might change.

We need some new terminology, like "final". A final getter would be guaranteed to return the same result every time it's called on the same object.

Comment 10

[Boris Zbarsky [:bzbarsky]]

For what it's worth, I mentioned this bug to Peter and Johnny today and they quickly came up with two more examples of "final" getters: .style and .childNodes.  And there are lots more of that sort of thing, actually.  So this could actually be a very nice win on code that is not hand-optimized to cache things like that.

Comment 11

[Boris Zbarsky [:bzbarsky]]

Just discussed with Eric two issues worth being careful with:

1)  A number of DOM getters always return the same _C++_ object (.style, .childNodes).  Whether they return the same JS object depends: if the object they returned last time is still alive, they return it, but if it got GCed they create a new one, obviously.  We could change things so these JSObjects have the same lifetime as the C++ object, but if we can avoid that, great.  In practice, what that means is that if we loop-hoist such a getter we need to keep the gotten object alive for the lifetime of the loop or call the getter again if it gets collected or something.

2)  We should be a bit careful with situations in which the LHS of the getprop gets adopted in the middle of the loop: that will cause a brain-transplant and obviously after that gets will return something different (in particular, some sort of cross-compartment wrapper).  Not sure what the best way to deal is here.

Comment 12

[David Anderson [:dvander] - inactive, e-mail if emergency]

For (1), I think no matter what the returned object would act as a GC root, so you might be okay.

Comment 13

[Eric Faust [:efaust]]

Attachment: Patch V1

OK, so: win some, lose some. The Ion Alias Analysis system can't tell much of anything, so any slot set conflicts with any slot get globally. In practice, this means that getprops are hard to hoist, because the object is probably looked up on some scope object, and so will conflict and not be hoistable.

In theory, this should allow for hoisiting, though. It certainly does CSE as prescribed.

Testcase goes from 555 ms to 195 ms or so in an optimized build.

Comment 14

[Boris Zbarsky [:bzbarsky]]

I assume you're testing on the testcase in bug 746773?

If so, given those numbers, presumably we're doing CSE within a single loop iteration but we're not loop-hoisting the whole thing?  And the reason for that is that the get of "data" is not hoistable?

Comment 15

[Boris Zbarsky [:bzbarsky]]

Oh, and the get of "data" is not hoistable because we're doing sets on the typed array?

Can we at least teach alias analysis about the difference between string and integer property names?

Comment 16

[Boris Zbarsky [:bzbarsky]]

Oh, and as far as comments on the patch go:

1)  conststr = toStringBool(constant);
2)  The WebIDL parser should probably throw an error if [Constant] is used on a
    non-readonly attribute.  Or are there sane semantics we could assign to an attribute
    that has a setter but whose getter is marked [Constant]?

Comment 17

[Boris Zbarsky [:bzbarsky]]

Hrm.  Looking at AliasSet, it does differentiate between "Slot" and "TypedArrayElement"....

And if I change the testcase so that it's an actual slot get to get the image.data (by doing "var image2 = { data: image.data }" outside the loop and using image2.data inside the loop), not a getter, then we do seem to loop-hoist it.  Or at least we get the same numbers as I do if I just put "data" in a var outside the loop.

Comment 18

[Eric Faust [:efaust]]

(In reply to Boris Zbarsky (:bz) from comment #17)
> Hrm.  Looking at AliasSet, it does differentiate between "Slot" and
> "TypedArrayElement"....
> 
I don't think it has anything to do with the typed arrays. When I looked at it, it looked very much like the load that was blocking hoisting was the load of |image| off the global object, which is a conflicting slot-load.

> And if I change the testcase so that it's an actual slot get to get the
> image.data (by doing "var image2 = { data: image.data }" outside the loop
> and using image2.data inside the loop), not a getter, then we do seem to
> loop-hoist it.  Or at least we get the same numbers as I do if I just put
> "data" in a var outside the loop.

That is consistent with the way I believe the patch to work, at least inasmuch as it *should* do hoisting, if it believes it can.

Comment 19

[Eric Faust [:efaust]]

(In reply to Eric Faust [:efaust] from comment #18)
> I don't think it has anything to do with the typed arrays. When I looked at
> it, it looked very much like the load that was blocking hoisting was the
> load of |image| off the global object, which is a conflicting slot-load.

dvander has said in passing on IRC that he thinks this might not be true, though. A little more investigation is warranted. AliasAnalysis is known to be a little finnicky.

Comment 20

[Boris Zbarsky [:bzbarsky]]

So the reason we're not getting loop hoisting is that getOperand(0) returns an operand that tests true for isInLoop() and false for isLoopInvariant().  So our MGetDOMProperty also tests false for isLoopInvariant().

Comment 21

[Boris Zbarsky [:bzbarsky]]

And yeah, the 0 operand (the "image") claims to have a dependency.

Wait.  Are we aliasing the get of "image" against the set of "i"?

Comment 22

[Boris Zbarsky [:bzbarsky]]

Or perhaps "pixels", I guess.

Comment 23

[Eric Faust [:efaust]]

Yessir. It's global. We can't tell what objects shadow each other, so all slot sets alias all slot loads :/

Comment 24

[Boris Zbarsky [:bzbarsky]]

So yeah, looks like it's probably "pixels".

If I make the testcase look like this:

var image = whatever;
(function() {
   var pixels = something;
   while (--pixels) {
     // use image.data
   }
})();

then we do get loop hoisting.

So I think we should get this patch landed, then see about fixing licm/alias analysis somehow to make the loop counter not alias other things that happen to be slots on the same scope, since that seems like a pretty common situation.

Comment 25

[Jan de Mooij [:jandem]]

Yeah, when I added alias analysis we needed it for correctness and had much bigger performance problems, so the current set mechanism did the job. Now that everything is in place, it would be good if we could get somebody to look into improving/replacing it.

JM+TI uses a list of (TypeObject *, jsid) to track modified properties inside loos. It's a bit more complicated for Ion since we also have to consider GVN and don't store that information in the MIR right now, but even using the slot index would help here.

Comment 26

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Wouldn't a more realistic testcase have the loop counter and ImageData object as local variables?

Comment 27

[Boris Zbarsky [:bzbarsky]]

> Wouldn't a more realistic testcase have the loop counter and ImageData object as local
> variables?

Yes, exactly.

I did some more experimenting and thinking here.  Two thoughts:

1)  LICM as we have it right now is very fragile.  It will only hoist instructions that it can guarantee have no dependency on anything in the loop.  In particular, as soon as you have any sort of stubcall in the loop (I tried a firstChild getter and tan() with two arguments to bypass ion's inlining of trig functions) you lose.  While we might be able to fix the slot thing, fixing the stubcall issue seems like it involves a lot more infrastructure and manual annotation of things, so I'm not sure it'll ever really work in realistic DOM testcases, though chances are we can get there for canvas imagedata manipulation in many cases.

2)  Hoisting the DOM getter doesn't _really_ depend on hoisting the slot get.  Specifically, given code like this:

  var image = getImage(), count = 100;
  for (var i = 0; i < count; ++i) {
    image.data[i] = i;
  }

LICM basically tries to rewrite it as:

  var image = getImage(), count = 100, data = image.data;
  for (var i = 0; i < count; ++i) {
    data[i] = i;
  }

whereas for our purposes it might be good enough to rewrite as something more like:

  var image = getImage(), myProps = { image: image, data: image.data }, count = 100;
  for (var i = 0; i < count; ++i) {
    var image2 = image;
    if (image2 == myProps.image) {
      myProps.data[i] = i;
    } else {
      myimage2.data[i] = i;
    }
  }

So basically, instead of hoisting the DOM get completely, hoist it conditional on the slot get returning the thing we expect (myProps is contained in the compiled jitcode, basically).  In fact, maybe we could even make it be:

  var image = getImage(), myProps = { image: image, data: image.data }, count = 100;
  for (var i = 0; i < count; ++i) {
    var image2 = image;
    if (image2 != myProps.image) {
      myProps.image = image2;
      myProps.data = image2.data;
    }
    myProps.data[i] = i;
  }

(starting to look IC-like now, I guess).

Comment 28

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to Boris Zbarsky (:bz) from comment #27)
> 1)  LICM as we have it right now is very fragile.  It will only hoist
> instructions that it can guarantee have no dependency on anything in the
> loop.  In particular, as soon as you have any sort of stubcall in the loop
> (I tried a firstChild getter and tan() with two arguments to bypass ion's
> inlining of trig functions) you lose.

For those two examples, and many others, we could annotate methods as "pure" to indicate they don't change anything. We could extend that to setters to indicate that they don't change anything other than the corresponding slot on the object (if there is such a thing? I don't know) or else the value returned by the corresponding getter.

Would it be too much to hope that that, plus TI-based alias analysis, might take us a long way?

Comment 29

[Boris Zbarsky [:bzbarsky]]

> Would it be too much to hope that that, plus TI-based alias analysis, might take us a
> long way?

That would take us a long way, yes.  We'd need to do a bunch manual annotation, and anything that adds/removes elements from the DOM would not be pure, of course, but the vast majority of getters should be fine to mark as pure in that sense, of course.

Comment 30

[Eric Faust [:efaust]]

Attachment: IM changes

I am /really/ not in love with the changes to TestCommonPropFunc. The Guard maybe should also be made an operand on Sets, just on principle? Also, if you have any ideas about potential refactors to TestCommonPropFunc in such a way that it doesn't have 4 out parameters, I would be greatly appreciative.

Comment 31

[Eric Faust [:efaust]]

Attachment: Paris Binding changes

Comment 32

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 677421 [details] [diff] [review]
Paris Binding changes

r=me if you put the [Constant] on a line by itself in the webidl.

Comment 33

[Sean Stangl [:sstangl]]

Comment on attachment 677420 [details] [diff] [review]
IM changes

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

Very clean patch. TestCommonPropFunc is a huge mess, but it's beyond the scope of this bug to fix, and adding yet another outparam doesn't make it any harder to unravel. Filing a low-priority follow-up bug so we remember to clean it up would be useful.

::: js/src/ion/MIR.h
@@ +5016,5 @@
> +    }
> +    bool isInfallible() const {
> +        return info_->isInfallible;
> +    }
> +    bool isConstant() const {

Conflicts with the "isConstant()" that means "is MConstant?". Perhaps isDomConstant?

Comment 34

[Boris Zbarsky [:bzbarsky]]

Eric, any progress here?

Note that you should be able to mark all the properties on ImageData as const, by the way, not just .data.

Comment 35

[Eric Faust [:efaust]]

College life came splashing in. The patches are just sitting in a queue on my other laptop ready to land as posted with nits. I should at least get that done, and then we can talk more about potential extensions (cross compartment wrappers, for example), and then go through in a big patch and [Constant] annotate everything that needs it.

Comment 36

[Boris Zbarsky [:bzbarsky]]

All good.  Let me know if I can help somehow!

Comment 37

[Sean Stangl [:sstangl]]

Pushed for Eric:

https://hg.mozilla.org/integration/mozilla-inbound/rev/70c54d5c94b7
https://hg.mozilla.org/integration/mozilla-inbound/rev/c5c30b93ee5e

Comment 38

[Boris Zbarsky [:bzbarsky]]

Added some documentation at https://developer.mozilla.org/en-US/docs/Mozilla/WebIDL_bindings#.5BConstant.5D

Comment 39

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/70c54d5c94b7
https://hg.mozilla.org/mozilla-central/rev/c5c30b93ee5e