Closed Bug 824275 Opened 7 years ago Closed 7 years ago

IonMonkey: refine alias analysis

Categories

(Core :: JavaScript Engine, defect)

Other Branch
x86
macOS
defect
Not set

Tracking

()

RESOLVED FIXED
mozilla20

People

(Reporter: bhackett, Unassigned)

References

Details

Attachments

(1 file, 1 obsolete file)

Attached patch patch (obsolete) — Splinter Review
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.
Attachment #695232 - Flags: review?(jdemooij)
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.
Attachment #695232 - Flags: review?(jdemooij)
(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.
Attached patch updatedSplinter Review
Attachment #695232 - Attachment is obsolete: true
Attachment #695265 - Flags: review?(jdemooij)
Awesome.  This completely fixes the testcases in bug 746773 (both the attached one and the jsperf one).
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.
Yes, that's exactly what was going on, and this patch definitely fixes it.
Attachment #695265 - Flags: review?(jdemooij) → review+
https://hg.mozilla.org/mozilla-central/rev/0e0200b9ef78
Status: NEW → RESOLVED
Closed: 7 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla20
You need to log in before you can comment on or make changes to this bug.