Closed Bug 676151 Opened 13 years ago Closed 13 years ago

IonMonkey: don't generate unecessary phi instructions

Categories

(Core :: JavaScript Engine, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: rpearl, Assigned: rpearl)

References

(Blocks 1 open bug)

Details

Attachments

(2 files, 2 obsolete files)

Attached file 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.
Attached patch patch v0 (obsolete) — Splinter Review
In this patch, we do not generate redundant phis.
Attachment #550275 - Flags: review?(dvander)
Attachment #550275 - Flags: feedback?(sstangl)
Attached patch patch v1 (obsolete) — Splinter Review
Sorry, that patch had little bit of very incorrect cruft!
Attachment #550275 - Attachment is obsolete: true
Attachment #550275 - Flags: review?(dvander)
Attachment #550275 - Flags: feedback?(sstangl)
Attachment #550279 - Flags: review?(dvander)
Attachment #550279 - Flags: feedback?(sstangl)
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.
Attachment #550279 - Flags: review?(dvander)
Attached patch patch v2Splinter Review
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.
Attachment #550279 - Attachment is obsolete: true
Attachment #550279 - Flags: feedback?(sstangl)
Attachment #550762 - Flags: review?(dvander)
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
Attachment #550762 - Flags: review?(dvander) → review+
I blame my mouse magically pasting. With nits addressed,
http://hg.mozilla.org/projects/ionmonkey/rev/a459db11a653
Status: ASSIGNED → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.