Last Comment Bug 723536 - IonMonkey: Optimistic GVN can miss breaking dependent congruences
: IonMonkey: Optimistic GVN can miss breaking dependent congruences
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: All All
: -- normal (vote)
: ---
Assigned To: general
:
: Jason Orendorff [:jorendorff]
Mentors:
Depends on:
Blocks: 725254
  Show dependency treegraph
 
Reported: 2012-02-02 08:11 PST by Hannes Verschore [:h4writer]
Modified: 2012-03-16 16:11 PDT (History)
5 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
fix via list (10.07 KB, patch)
2012-02-14 17:54 PST, Marty Rosenberg [:mjrosenb]
dvander: review+
Details | Diff | Splinter Review
fix via map (6.72 KB, patch)
2012-02-14 17:54 PST, Marty Rosenberg [:mjrosenb]
no flags Details | Diff | Splinter Review
add in MCompare::congruentTo spport (944 bytes, patch)
2012-03-02 21:49 PST, Marty Rosenberg [:mjrosenb]
no flags Details | Diff | Splinter Review
now with 500% more qrefresh (2.20 KB, patch)
2012-03-02 22:07 PST, Marty Rosenberg [:mjrosenb]
no flags Details | Diff | Splinter Review
more different patch (3.93 KB, patch)
2012-03-04 04:32 PST, Marty Rosenberg [:mjrosenb]
sstangl: review+
Jacob.Bramley: review+
Details | Diff | Splinter Review
/home/mrosenberg/patches/89299.diff-r0.patch (3.24 KB, patch)
2012-03-07 18:17 PST, Marty Rosenberg [:mjrosenb]
sstangl: review+
Details | Diff | Splinter Review

Description Hannes Verschore [:h4writer] 2012-02-02 08:11:25 PST
Deltablue doesn't segfaults anymore, but still does something bogus. (It still 
doesn't complete). I've reduced it to the next problem:

Testcase:

function change(src) {
    src.value = 2;
}

function projectionTest() {
    var src = null;
    var dst = null;

    for (var i = 0; i < 1; i++) {
        src = new Object();
        dst = new Object();
    }

    dst.value = 1;

    change(src);

    // The next condition should always be FALSE,
    // but ionmonkey makes a mistake here.
    // src.value is suddenly 1 (= dst.value)
    var t = src.value
    if (t != 2)
        return t

    for (var i = 0; i < 100; i++) {
    }
}

for (var n = 0; n < 20; n++) {
    print(projectionTest())
}

Expected (-n -m):
undefined (20x)

Actual (--ion -n):
undefined (3x)
1         (17x)

I pinpointed the problem to the GVN phase. Before that phase the argument to genericsetproperty (dst.value = 1) and callgetproperty (t = src.value) are different. But GVN changes the callgetproperty to the same argument as genericsetproperty.
Comment 1 Hannes Verschore [:h4writer] 2012-02-02 09:34:34 PST
I forgot to say that "--ion -n --ion-gvn=off" and "--ion -n --ion-gvn=pessimistic" don't fail.
Comment 2 Marty Rosenberg [:mjrosenb] 2012-02-02 10:29:04 PST
I looked at this a bit, it looks like the issue is ordering.
Giving some (approximate) value numbers from the run I looked at:

(27) src = new Object() // technically, 27/28 are the phi nodes from when they are rejoined after the loop
(28) dst = new Object()
(51) dst.value = 1 // technically, 51 and 61 are the unboxings.
(61) t = src.value

Initially, we break the null congruence for 27 and 28, setting them both to vn27.
then we break the null congruence for 51 and 61, setting them both to vn51
finally, we break the congruence for 27 and 28, setting 28 to vn28.
Then, all of the uses of 28 are marked for inspection, the only use of 28 is 51. Upon inspection, 51 is fine because it still matches 51.  However, 61 is never inspected because it is not a use of 28.  I suspect we should be marking all uses of anything that had vn27, rather than just the variable that we changed.
Comment 3 Marty Rosenberg [:mjrosenb] 2012-02-03 14:49:44 PST
(In reply to Marty Rosenberg [:Marty] from comment #2)
> (27) src = new Object() // technically, 27/28 are the phi nodes from when
> they are rejoined after the loop
> (28) dst = new Object()
> (51) dst.value = 1 // technically, 51 and 61 are the unboxings.
> (61) t = src.value

> 51. Upon inspection, 51 is fine because it still matches 51.  However, 61 is
> never inspected because it is not a use of 28. 
This is not entirely true,  we correctly attempt to break Instruction 51's congruence with anything.  The congruence breaking algorithm is to set your VN to be your ID.  This usually ensures that you are no longer congruent with your old congruency class, EXCEPT if your congruency class already has your VN.

> I suspect we should be
> marking all uses of anything that had vn27, rather than just the variable
> that we changed.
That will work, but it will be much less efficient than the actual solution proposed in the paper
It will also require us to have some way to look up all MDefinitions* that have a particular VN.
The solution outlined in the initial paper was to have the set of all MDefinitions in the congruence class VN listed in the "Representative member" of the class.  In this case, we want it to be the member that gave its id to the class.  With this extra data, when you need to break your congruence with your class, but you are already the representative member of your class, you need to kick everyone else out of your class, by choosing a new representative member, and changing the VN of every other member of the class to its ID.
Initially, I tried to put this set (as a js::Vector) into the hash table that we use to look up the VN of a given element.  This does not work because we can't actually access the vector.  In this example, initially, both val27 and val28 have VN27, and both val51 and val61 have VN61.  Looking up val51 should return a structure that has {VN27, {val61}} in it, both the VN, and the list of other values.  When we change val28 to VN28 (breaking its congruence with val27), we also change the hash for vn51, so we know to break its congruence (if it initially had VN50, we'd want the lookup to fail so we could create a new entry with {VN51, blah}). This means the vector of its congruence class would be stored with a key that is inaccessible.  I believe there are two different ways of proceeding from here.
First would be to keep the vector/list attached to the individual MDefinitions, It should be relatively painless to make an inline list that runs through the entire congruence class.  The other solution would be to make a new map that maps VNs to their congruence class, but we'll need to do a bit of work to either keep this up to date, or ignore entries that are out of date.
Comment 4 David Anderson [:dvander] 2012-02-03 16:07:00 PST
Thanks for analyzing this, Marty. For now we've agreed to switch GVN to its pessimistic mode, instead (which, luckily, exists!) - which also significantly cuts down on the cost of running the algorithm. Once we're more complete on benchmarks we should take a look at this bug again to see if we could gain anything.

http://hg.mozilla.org/projects/ionmonkey/rev/8b540f91f5cf
Comment 5 Marty Rosenberg [:mjrosenb] 2012-02-14 17:54:00 PST
Created attachment 597263 [details] [diff] [review]
fix via list
Comment 6 Marty Rosenberg [:mjrosenb] 2012-02-14 17:54:33 PST
Created attachment 597264 [details] [diff] [review]
fix via map
Comment 7 David Anderson [:dvander] 2012-02-28 18:26:23 PST
Using gaussian-blur as a benchmark, optimistic GVN removes a lot of redundancies, which really helps every subsequent pass, so overall this noticeably reduces compile-time (by about 10%) and memory use (by about 13%).

Patch #2 uses about 5% more memory than patch #1, and patch #2 *might* be a hair faster but it's not really clear.
Comment 8 David Anderson [:dvander] 2012-02-29 14:12:02 PST
Comment on attachment 597263 [details] [diff] [review]
fix via list

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

Nice work, sorry for the late review!

::: js/src/ion/ValueNumbering.cpp
@@ +434,5 @@
> +    valueNumber_->setValueNumber(vn);
> +}
> +// Set the class of this to the given representative value.
> +void
> +ValueNumberer::setClass(MDefinition *def, MDefinition *rep) {

style nits: brace on new line, newline above the comment

@@ +439,5 @@
> +    def->valueNumberData()->setClass(def, rep);
> +}
> +
> +void
> +ValueNumberer::breakClass(MDefinition *def) {

style nit: brace on new line

::: js/src/ion/ValueNumbering.h
@@ +122,5 @@
> +    friend void ValueNumberer::breakClass(MDefinition*);
> +    uint32 number;
> +    MDefinition *classNext;
> +    MDefinition *classPrev;
> +  public:

style nits: newline below friend, above public: (here and above)

@@ +130,5 @@
> +    }
> +    uint32 valueNumber() {
> +        return number;
> +    }
> +    // Set the class of this to the given representative value.

style nits: newlines in between these functons
Comment 9 Hannes Verschore [:h4writer] 2012-03-02 15:58:03 PST
As far as I can see. This landed as:
https://hg.mozilla.org/projects/ionmonkey/rev/b31d5321db9e

It indeed succeeds on the given testcase in my first comment,
but now V8-crypto started failing.
So probably there is still a bug in optimistic GVN.
(--ion -n fails, --ion -n --ion-gvn=pessimistic succeeds)
Comment 10 Marty Rosenberg [:mjrosenb] 2012-03-02 16:29:14 PST
So I've noticed.  I'm reducing it now, hopefully it won't be too painful to fix
Comment 11 Hannes Verschore [:h4writer] 2012-03-02 17:54:04 PST
Reducing gave back the following testcase:

function bnpDivRemTo(q) {
    var j = 37;
    if (q == null) ;
    while (0 < 0) ;
    while (--j >= 0) ;
    if (q != null)
        print("SHOULDN'T REACH")
}
bnpDivRemTo(null);
bnpDivRemTo(null);

prints "SHOULDN'T REACH" on --ion -n and nothing on --ion -n --ion-gvn=pessimistic
Comment 12 David Anderson [:dvander] 2012-03-02 18:10:55 PST
backed out due to added orange @ http://hg.mozilla.org/projects/ionmonkey/rev/c027cce870d2
Comment 13 Marty Rosenberg [:mjrosenb] 2012-03-02 19:13:09 PST
(In reply to Hannes Verschore from comment #11)
> Reducing gave back the following testcase:
> 
> function bnpDivRemTo(q) {
>     var j = 37;
>     if (q == null) ;
>     while (0 < 0) ;
>     while (--j >= 0) ;
>     if (q != null)
>         print("SHOULDN'T REACH")
> }
> bnpDivRemTo(null);
> bnpDivRemTo(null);
> 
> prints "SHOULDN'T REACH" on --ion -n and nothing on --ion -n
> --ion-gvn=pessimistic

Thank you very much! my copy was still reducing, and looked to be about 200 lines long.

The issue wasn't with GVN per se.
Recently, MCompare was added, and congruentTo was not implemented, so MBinaryInst's congruentTo was used.
turns out MCompare::op() for == and != is the same, so |q != null| was being replaced with the result of |q == null|
i've implemented MCompare::congruentTo, which checks the MCompare-specific jsop() field.
Comment 14 Marty Rosenberg [:mjrosenb] 2012-03-02 21:49:35 PST
Created attachment 602572 [details] [diff] [review]
add in MCompare::congruentTo spport
Comment 15 Marty Rosenberg [:mjrosenb] 2012-03-02 22:07:24 PST
Created attachment 602575 [details] [diff] [review]
now with 500% more qrefresh

this one also passes the same tests
Comment 16 Hannes Verschore [:h4writer] 2012-03-03 00:36:57 PST
(In reply to Marty Rosenberg [:Marty] from comment #13)
> The issue wasn't with GVN per se.

Yeah sorry. I was indeed a bit fast to blame optimistic GVN.
I didn't take the time to look into it and just posted the testcase. 
(It was already very late here)
Glad you figured it out :D
Comment 17 Marty Rosenberg [:mjrosenb] 2012-03-04 04:32:02 PST
Created attachment 602706 [details] [diff] [review]
more different patch

I'd also fixed a "logical error" in an incorrect way. In some cases, this resulted in an infinite loop.  The initial fix has been undone, but the comment left in place in case my logic was actually wrong.
Comment 18 Sean Stangl [:sstangl] 2012-03-05 13:00:03 PST
Comment on attachment 602706 [details] [diff] [review]
more different patch

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

::: js/src/ion/ValueNumbering.cpp
@@ +475,5 @@
>          // Insert the new representative => number mapping into the table
> +        // Logically, there should not be anything in the table currently, but
> +        // old values are never removed, so there's a good chance something will
> +        // already be there.  If putNew fails, and it turns out to be this case,
> +        // change it to put.

Can this be made an assertion? Assertions are stronger than comments.

::: js/src/ion/arm/Assembler-arm.cpp
@@ +2102,5 @@
>          return false;
>      if (!(inst->is<InstBXReg>() || inst->is<InstBImm>()))
>          return false;
> +    // See if the next instruction is a pool header.
> +    *ph = (inst+1)->as<const PoolHeader>();

Related to this patch? I don't understand this part.
Comment 19 Jacob Bramley [:jbramley] 2012-03-06 00:37:41 PST
Comment on attachment 602706 [details] [diff] [review]
more different patch

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

::: js/src/ion/arm/Assembler-arm.cpp
@@ +2102,5 @@
>          return false;
>      if (!(inst->is<InstBXReg>() || inst->is<InstBImm>()))
>          return false;
> +    // See if the next instruction is a pool header.
> +    *ph = (inst+1)->as<const PoolHeader>();

It's a fix for the patch in bug 730108. It looks correct.
Comment 20 Marty Rosenberg [:mjrosenb] 2012-03-07 18:17:33 PST
Created attachment 603939 [details] [diff] [review]
/home/mrosenberg/patches/89299.diff-r0.patch

ugh.  Found another bug in it right as I was going to commit.  The bug only appeared in v8-splay but not check-splay.  jit-tests and all of the bench suites look clean with this patch.  I think some comments need to be cleaned up.
Comment 21 Sean Stangl [:sstangl] 2012-03-08 15:28:00 PST
Comment on attachment 603939 [details] [diff] [review]
/home/mrosenberg/patches/89299.diff-r0.patch

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

::: js/src/ion/ValueNumbering.cpp
@@ +454,5 @@
>          // then there isn't anything for us to do.
> +        bool needsSplit = false;
> +        for (MDefinition *vncheck = def->valueNumberData()->classNext;
> +             vncheck != NULL;
> +             vncheck = vncheck->valueNumberData()->classNext) {

As a general rule, this pattern is better implemented as a static function (say, named "NeedsSplit(MDefinition *)"). Then the check below can just be "if (!NeedsSplit(def)) return;", and we don't need the break logic, since it can just |return true;|.

@@ +462,5 @@
> +                        def->id(), vncheck->id());
> +                break;
> +            }
> +        }
> +        // If we don't need the split, don't do a split.

Comment is self-evident.
Comment 22 Marty Rosenberg [:mjrosenb] 2012-03-16 16:10:48 PDT
landed: http://hg.mozilla.org/projects/ionmonkey/rev/488290bd2644

Note You need to log in before you can comment on or make changes to this bug.