1038839 - Use type information for alias analysis

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Jan de Mooij [:jandem]]

Currently for a loop like this:

for (var i=0; i<length; i++)
    dest[i] = src[0];

We assume dest[i] can alias src[0], so we can't hoist src[0]. But in practice dest and src will often have a different TypeObject, so if their type sets are disjoint we can hoist src[0] just fine. It should be pretty easy to implement MLoadElement::mightAlias and check for this case.

This is a stupid example of course, but it should be easy to prototype this and see how much it helps.

(I thought we had a bug for this, but I can't find it.)

Comment 1

[Sean Stangl [:sstangl]]

Attachment: 0001-Implement-MLoadElement-mightAlias.patch

I noticed this issue recently and found this bug, and just for fun thought I'd write up a quick patch.

In the example in Comment 0, this patches causes the MElements, MInitializedLength, and MLoadElement instructions of |src[0]| to be hoisted out of the loop.

This saves about 3% on that microbenchmark if the loop dominates, a laughably small amount. Obviously nothing else is even remotely noticeably affected, even though codegen is theoretically improved.

Comment 2

[Jan de Mooij [:jandem]]

Comment on attachment 8571617 [details] [diff] [review]
0001-Implement-MLoadElement-mightAlias.patch

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

Sorry for the delay, looks great.

::: js/src/jit/MIR.cpp
@@ +4015,5 @@
> +    const MDefinition *storeObj = GetStoreObject(store);
> +    if (!storeObj)
> +        return true;
> +
> +    return input()->resultTypeSet()->objectsIntersect(storeObj->resultTypeSet());

Before this we should return true if storeObj->resultTypeSet() is nullptr.

Comment 3

[Sean Stangl [:sstangl]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/851347e26940

Comment 4

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

Backed out in https://hg.mozilla.org/integration/mozilla-inbound/rev/4bdf782dda82 for spidermonkey test failures:
https://treeherder.mozilla.org/logviewer.html#?job_id=7496984&repo=mozilla-inbound
https://treeherder.mozilla.org/logviewer.html#?job_id=7496882&repo=mozilla-inbound

Comment 5

[Sean Stangl [:sstangl]]

That's strange. I checked jit-tests before pushing... I'll investigate.

Comment 6

[Sean Stangl [:sstangl]]

Attachment: Patch v2

The problem is that elements() doesn't necessarily return something of MIRType_Elements. It can also refer to the Object itself, when storage is inline, bypassing the elements altogether.

This new version passes all jit-tests with --ion, except for two which appear to time out on master as well.

If this patch is taken, I'd like to rename "elements" to "elementsOrObj" all over the place where relevant as a follow-up. Maybe "storage".

Comment 7

[Nicolas B. Pierron [:nbp]]

(In reply to Sean Stangl [:sstangl] from comment #6)
> The problem is that elements() doesn't necessarily return something of
> MIRType_Elements. It can also refer to the Object itself, when storage is
> inline, bypassing the elements altogether.

Sounds to me that it might be better to keep the MElement to save the displacement, and always keep the same graph independently of the object representation. Then we can try to fold this address later, in the LIRGenerator.

Comment 8

[Sean Stangl [:sstangl]]

(In reply to Nicolas B. Pierron [:nbp] from comment #7)
> Sounds to me that it might be better to keep the MElement to save the
> displacement, and always keep the same graph independently of the object
> representation. Then we can try to fold this address later, in the
> LIRGenerator.

That would definitely be nicer, yeah.

Comment 9

[Sean Stangl [:sstangl]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/5c0bd25d0a24

Comment 10

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/5c0bd25d0a24

Comment 11

[Daniel Holbert [:dholbert]]

This was missing some MOZ_OVERRIDE annotations, which caused -Winconsistent-missing-override build warnings in clang 3.6 & newer. (which breaks warnings-as-errors builds w/ that compiler version)

I landed a trivial followup to add this annotation, with the blanket r+ that ehsan granted me for fixes of this sort over on bug 1126447 comment 2:
https://hg.mozilla.org/integration/mozilla-inbound/rev/b19e6bcc058a

Comment 12

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/b19e6bcc058a