Closed Bug 669795 Opened 13 years ago Closed 13 years ago

IonMonkey: separate functionality for a pessimistic GVN pass

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)

Follow up to Bug 659729.

We can perform a one-pass, pessimistic value numbering using the same framework as the current, more expensive phase. This will uncover the same set of congruences on code with no back-edges, but will not uncover congruences in back edges of loops.
Attachment #545757 - Flags: review?(dvander)
Attached patch patch v0Splinter Review
This implements pessimistic GVN. That is to say, rather than checking our assumption that values through back-edges are congruent (and breaking this assumption and rechecking if necessary) as in the optimistic algorithm, instead we do one pass through.

This doesn't discover as many congruences, but it is very fast. Example:

With pessimistic patch on a simple test case (Attachment 545757 [details]):
[GVN] Numbering instructions
[GVN] Eliminating redundant instructions
[GVN] Looking at block 0
[GVN] instruction 10 is dominated by instruction 8 (from block 0)
[GVN] instruction 12 is dominated by instruction 8 (from block 0)
[GVN] instruction 18 is dominated by instruction 16 (from block 0)
[GVN] instruction 60 is dominated by instruction 58 (from block 0)
[GVN] Looking at block 1
[GVN] Looking at block 2
[GVN] instruction 52 is dominated by instruction 8 (from block 0)
[GVN] instruction 66 is dominated by instruction 56 (from block 0)
[GVN] Looking at block 3
[GVN] instruction 30 is dominated by instruction 16 (from block 0)
[GVN] instruction 36 is dominated by instruction 16 (from block 0)

The optimistic version, without this patch (more congruences):
[GVN] Numbering instructions
[GVN] Eliminating redundant instructions
[GVN] Looking at block 0
[GVN] instruction 10 is dominated by instruction 8 (from block 0)
[GVN] instruction 12 is dominated by instruction 8 (from block 0)
[GVN] instruction 18 is dominated by instruction 16 (from block 0)
[GVN] instruction 60 is dominated by instruction 58 (from block 0)
[GVN] Looking at block 1
[GVN] instruction 62 is dominated by instruction 64 (from block 1)
[GVN] Looking at block 2
[GVN] instruction 52 is dominated by instruction 8 (from block 0)
[GVN] instruction 66 is dominated by instruction 56 (from block 0)
[GVN] Looking at block 3
[GVN] instruction 30 is dominated by instruction 16 (from block 0)
[GVN] instruction 36 is dominated by instruction 16 (from block 0)
[GVN] instruction 40 is dominated by instruction 34 (from block 3)
[GVN] instruction 70 is dominated by instruction 68 (from block 3)

An example of the difference: the instruction eliminated in block 1 is an unbox of a phi. We discover that the phi is congruent to another phi node using the optimistic pass, but in the pessimistic one we ignore the back edge to the phi node and must assume that the two phis are not congruent.

Note that we don't eliminate phi instructions from the vector yet... I need to file a bug for that. 

I want to wait to land this patch until the option parser lands, because I really want a run-time option on which GVN pass to use (right now it is a #define).
Attachment #545759 - Flags: review?(dvander)
Attachment #545759 - Flags: review?(dvander) → review?(adrake)
Attachment #545757 - Flags: review?(dvander)
Comment on attachment 545759 [details] [diff] [review]
patch v0

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

Looks good! A couple small things:

::: js/src/ion/Ion.cpp
@@ +150,5 @@
>      if (!ApplyTypeInformation(graph))
>          return false;
>      spew.spewPass("Apply types");
>  
> +    // FIXME this should be an option

FIXMEs in the code should have a bug number attached to them.

::: js/src/ion/ValueNumbering.cpp
@@ +86,5 @@
>      // The algorithm is the simple RPO-based algorithm from
>      // "SCC-Based Value Numbering" by Cooper and Simpson
>      //
> +    // If we are performing a pessimistic pass, then we assume that every
> +    // definition is in its own congruence class, since we know noithing about

Typo: noithing

::: js/src/ion/ValueNumbering.h
@@ +44,5 @@
>  
>  #include "MIR.h"
>  #include "MIRGraph.h"
>  
> +// FIXME this should be an option

You can stick both of these FIXMEs on the same bug.
Attachment #545759 - Flags: review?(adrake) → review+
http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/ce932530b72a

Follow up for the option: bug 671442
Status: NEW → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.