676151 - IonMonkey: don't generate unecessary phi instructions

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Ryan Pearl [:rpearl]]

Attachment: test case

If we insert a phi which merges two copy instructions, one of which is inside a loop and carried to the phi from a back edge, then, once we copy-propagate, we have phi instructions where neither input is from the loop.

This causes issues with GVN, since it cannot reach a fixed point--changing the value number of such a phi necessarily causes a consumer of the instruction to change, so there is a sequence of dependencies which can cause GVN to never reach a fixed point.

Options for fixing (discussed in person) include copy-propagating after GVN, special casing phis and cleaning them up, or not generating them in the first place.

The attached test-case causes GVN to infloop.

Comment 1

[Ryan Pearl [:rpearl]]

Attachment: patch v0

In this patch, we do not generate redundant phis.

Comment 2

[Ryan Pearl [:rpearl]]

Attachment: patch v1

Sorry, that patch had little bit of very incorrect cruft!

Comment 3

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

Comment on attachment 550279 [details] [diff] [review]
patch v1

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

::: js/src/ion/MIRGraph.cpp
@@ +521,5 @@
> +        // So long as we keep local variables separate, and not remove copies
> +        // until after SSA building is complete, then we need not insert phis
> +        // if the entry definition is just a copy of the exit definition.
> +        // If at any point, one local variable is treated in some way that is
> +        // no a copy of the other, then the exit definition will also differ.

What do "separate" and "treated" mean here?

@@ +542,5 @@
> +        if (entryDef->isCopy())
> +            entryDef = entryDef->getOperand(0);
> +
> +        if (exitDef->isCopy())
> +            exitDef = exitDef->getOperand(0);

I'm convinced that it's safe to drop the phi, but this will change semantics in another subtle way: if the inputs are *not* the same, you've just unwrapped the copies, and will now replace uses of the contained name, not the copy. I don't think that's safe.

Comment 4

[Ryan Pearl [:rpearl]]

Attachment: patch v2

Follow copies when determining whether to place a phi, but don't update the entry and exit definitions, so that if we do actually insert a phi, it keeps copies distinct.

Comment 5

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

Comment on attachment 550762 [details] [diff] [review]
patch v2

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

Looks good, thank you for the detailed comment!

::: js/src/ion/MIRGraph.cpp
@@ +1,1 @@
> +const /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-

what

@@ +502,5 @@
>  #endif
>  }
>  
> +static inline MDefinition *
> +FollowCopy(MDefinition *def) {

{ on newline

Comment 6

[Ryan Pearl [:rpearl]]

I blame my mouse magically pasting. With nits addressed,
http://hg.mozilla.org/projects/ionmonkey/rev/a459db11a653