1269313 - Use TI to break alias between input objects of operations

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Hannes Verschore [:h4writer]]

In kraken-oscillator the alias analysis isn't smart enough to break the dependency between two stores.

> function blaat (array1, array2) {
>     for () {
>        array1[i] = array2[i]
>     }
> }

array1 and array2 could be the same, therefore we cannot break the alias between the loading of array2 and storing of array1. Using TI we can do this by checking that the objects of array1 and array2 don't intersect each-other.

Comment 1

[Hannes Verschore [:h4writer]]

Attachment: Patch

This patch is two parts:
1) Small change in FlowAA to use TI to see if there is an intersection.
2) Normalize a virtual "object" function to every MIR. Which the FlowAA uses to retrieve the object to use TI on.

Comment 2

[Jan de Mooij [:jandem]]

Is the code in GenericLoadMightAlias unable to handle the case in comment 0?

Comment 3

[Hannes Verschore [:h4writer]]

(In reply to Jan de Mooij [:jandem] from comment #2)
> Is the code in GenericLoadMightAlias unable to handle the case in comment 0?

The code doesn't catch it indeed. MGuardShape isn't supported and doesn't call GenericLoadMightAlias.
That is one if the biggest issue I think with this function. It doesn't get called on every store.

That's why I think it would be good to have the following waterfall to test if load aliases stores
1) Compare getAliasSet                 (very broad categories)
2) Use generic TI info to compare      (generic load/store testing)
3) Use mightAlias                      (special cases like slot inequality ...)

Currently we miss a lot in category (2), since the generic load/store testing is done in mightAlias, which we often forget to override.

What if I move that logic into AliasAnalysisShared and don't call it in mightAlias, but call it as part of our testing? That would have a similar effect to what I want to accomplish.

Comment 4

[Hannes Verschore [:h4writer]]

Attachment: Patch

New patch like discussed on IRC. I generalized the GenericLoadMightAlias to work an any object.

- Added genericMightAlias that uses TI info.
- Removed the MElements indirection in current code and always fetch the object. This deduplicates code.
- Added assert that as soon as one overrides the "getAliasSet" function, they will get a runtime assert to also add it to GetObject. I hope that way we are more pro-active in getting it to work.
- This patch still contains the "obj" to "object" normalization. Not needed anymore, but I think it couldn't hurt...

Comment 5

[Jan de Mooij [:jandem]]

Comment on attachment 8748062 [details] [diff] [review]
Patch

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

Sorry for the delay. r=me with comments below addressed.

::: js/src/jit/AliasAnalysisShared.cpp
@@ +46,5 @@
> +static inline const MDefinition*
> +MaybeUnwrap(const MDefinition* object)
> +{
> +    while (object->isSlots() || object->isElements() || object->isConvertElementsToDoubles())
> +        object = object->getOperand(0);

Nit: MOZ_ASSERT(object->numOperands() == 1); before this - if that ever fails we have to reconsider this code.

@@ +89,5 @@
> +      case MDefinition::Op_SetDisjointTypedElements:
> +      case MDefinition::Op_ArrayPopShift:
> +      case MDefinition::Op_ArrayPush:
> +      case MDefinition::Op_ArraySlice:
> +      case MDefinition::Op_ArrayJoin:

GetPropertyCache and ArrayJoin can invoke arbitrary JS code (for ArrayJoin see its getAliasSet), so they should probably belong in the list below. Can we assert or check for "all-side-effects" to catch such cases?

@@ +111,5 @@
> +      case MDefinition::Op_LoadSlot:
> +      case MDefinition::Op_StoreSlot:
> +      case MDefinition::Op_InArray:
> +      case MDefinition::Op_LoadElementHole:
> +        object = ins->getOperand(0);

To help catch bugs when somebody adds a new operand without updating this code, can we assert object->type() is Object, maybe at the end of this function, after unwrapping?

@@ +132,5 @@
> +      case MDefinition::Op_AsmJSStoreGlobalVar:
> +      case MDefinition::Op_TypedArrayElements:
> +      case MDefinition::Op_TypedObjectElements:
> +        object = nullptr;
> +        break;

Nit: if we |return nullptr;| here and in the default case below, we don't need the if (!object) null check.

Comment 6

[Hannes Verschore [:h4writer]]

(In reply to Jan de Mooij [:jandem] from comment #5)
> Comment on attachment 8748062 [details] [diff] [review]
> Patch
> 
> Review of attachment 8748062 [details] [diff] [review]:
> -----------------------------------------------------------------
> @@ +89,5 @@
> > +      case MDefinition::Op_SetDisjointTypedElements:
> > +      case MDefinition::Op_ArrayPopShift:
> > +      case MDefinition::Op_ArrayPush:
> > +      case MDefinition::Op_ArraySlice:
> > +      case MDefinition::Op_ArrayJoin:
> 
> GetPropertyCache and ArrayJoin can invoke arbitrary JS code (for ArrayJoin
> see its getAliasSet), so they should probably belong in the list below. Can
> we assert or check for "all-side-effects" to catch such cases?

Good catch!

> 
> @@ +111,5 @@
> > +      case MDefinition::Op_LoadSlot:
> > +      case MDefinition::Op_StoreSlot:
> > +      case MDefinition::Op_InArray:
> > +      case MDefinition::Op_LoadElementHole:
> > +        object = ins->getOperand(0);
> 
> To help catch bugs when somebody adds a new operand without updating this
> code, can we assert object->type() is Object, maybe at the end of this
> function, after unwrapping?

That indeed helped to find some extra issues. Like TypedObjectElements and TypedArrayElements not being supported and Store/LoadTypedArrayElementStatic

Comment 7

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/6b1e076dbcb7

Comment 8

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/6b1e076dbcb7