824275 - IonMonkey: refine alias analysis

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Brian Hackett [Laid off!]]

Attachment: patch

IonMonkey's alias analysis is pretty coarse, and can introduce false dependencies that inhibit GVN and LICM.  This bites on the critical loop in v8-richards (see bug 824257 for some context).

Scheduler.prototype.schedule = function () {
  this.currentTcb = this.list;
  while (this.currentTcb != null) {
    if (this.currentTcb.isHeldOrSuspended()) {
      this.currentTcb = this.currentTcb.link;
    } else {
      this.currentId = this.currentTcb.id;
      this.currentTcb = this.currentTcb.run();
    }
  }
};

In the above function, all reads of this.currentTcb are the same, yet the latter two are not folded.  This is because they are treated as dependent on the writes to 'this.currentTcb' and 'this.currentId'.  The problem with the former is that there is no path from the first write to .currentTcb to the later reads, and the problem with the latter is that this.currentId cannot actually alias this.currentTcb (all these are accesses at known slots).  The attached patch refines the alias analysis so that these spurious dependencies are not introduced, by allowing nodes to more precisely indicate whether they can alias another whose AliasSet they intersect, and by (imperfectly, unfortunately) incorporating reachability info into determining the last store that can affect a load.

Comment 1

[Jan de Mooij [:jandem]]

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

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

Awesome, I've wanted to do this for a while but didn't get to it yet.

::: js/src/ion/AliasAnalysis.cpp
@@ +137,5 @@
>                  for (AliasSetIterator iter(set); iter; iter++) {
> +                    MDefinitionVector &aliasedStores = stores[*iter];
> +                    for (int i = aliasedStores.length() - 1; i >= 0; i--) {
> +                        MDefinition *store = aliasedStores[i];
> +                        if (def->mightAlias(store) && BlockMightReach(store->block(), *block)) {

Can we use store->block()->dominates(block) here?

@@ +140,5 @@
> +                        MDefinition *store = aliasedStores[i];
> +                        if (def->mightAlias(store) && BlockMightReach(store->block(), *block)) {
> +                            if (lastStore->id() < store->id())
> +                                lastStore = store;
> +                        }

If we found a store, all other stores in the vector will have lower id's, so I think we can "break;" right before the "}"

::: js/src/ion/MIR.cpp
@@ +1624,5 @@
> +{
> +    if (store->isStoreFixedSlot() && store->toStoreFixedSlot()->slot() != slot())
> +        return false;
> +    if (store->isStoreSlot())
> +        return false;

While you are working on alias analysis, I think it would be good to split the Slot set in FixedSlot and DynamicSlot. Only an idempotent MGetPropertyCache can load from both fixed/dynamic slots.

::: js/src/ion/MIR.h
@@ +456,5 @@
> +    virtual bool mightAlias(MDefinition *store) {
> +        // Return whether this load may depend on the specified store, given
> +        // that the alias sets intersect. This may be refined to exclude
> +        // possible aliasing in cases where alias set flags are too imprecise.
> +        return true;

Nit: JS_ASSERT(store->isEffectful()); here.

Comment 2

[Jan de Mooij [:jandem]]

(In reply to Jan de Mooij [:jandem] from comment #1)
> 
> Can we use store->block()->dominates(block) here?

Er, ignore this, don't know what I was thinking.

Comment 3

[Brian Hackett [Laid off!]]

Attachment: updated

Comment 4

[Boris Zbarsky [:bzbarsky]]

Awesome.  This completely fixes the testcases in bug 746773 (both the attached one and the jsperf one).

Comment 5

[Brian Hackett [Laid off!]]

Hmm, for that testcase (in global scope):

for (var i = 0; i < count; ++i) {
  var pixels = SCREEN_WIDTH * SCREEN_HEIGHT;
  while(--pixels) {
    image.data[4*pixels+0] = 1;
    image.data[4*pixels+1] = 2;
    image.data[4*pixels+2] = 3;
    image.data[4*pixels+3] = 4;
  }
}

We should have been able to CSE the image.data accesses together earlier, but would not be able to hoist it out of the loop because both 'pixels' and 'image' are global properties which were being treated as aliased.  That latter bit is fixed by this patch so that we can tell the two global properties apart, and are able to hoist 'image.data' out of the loop entirely.

Comment 6

[Boris Zbarsky [:bzbarsky]]

Yes, that's exactly what was going on, and this patch definitely fixes it.

Comment 7

[Brian Hackett [Laid off!]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/0e0200b9ef78

Comment 8

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/0e0200b9ef78