Closed Bug 723536 Opened 12 years ago Closed 12 years ago

IonMonkey: Optimistic GVN can miss breaking dependent congruences

Categories

(Core :: JavaScript Engine, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: h4writer, Unassigned)

References

Details

Attachments

(3 files, 3 obsolete files)

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.
I forgot to say that "--ion -n --ion-gvn=off" and "--ion -n --ion-gvn=pessimistic" don't fail.
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.
(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.
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
OS: Linux → All
Hardware: x86_64 → All
Summary: IonMonkey: fault in GVN, reduced from deltablue.js → IonMonkey: Optimistic GVN can miss breaking dependent congruences
Blocks: 725254
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 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
Attachment #597263 - Flags: review+
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)
So I've noticed.  I'm reducing it now, hopefully it won't be too painful to fix
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
(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.
Attachment #602572 - Flags: review?(dvander)
Attached patch now with 500% more qrefresh (obsolete) — Splinter Review
this one also passes the same tests
Attachment #602572 - Attachment is obsolete: true
Attachment #602572 - Flags: review?(dvander)
Attachment #602575 - Flags: review?(dvander)
(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
Attached patch more different patch (obsolete) — Splinter Review
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.
Attachment #602575 - Attachment is obsolete: true
Attachment #602575 - Flags: review?(dvander)
Attachment #602706 - Flags: review?(sstangl)
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.
Attachment #602706 - Flags: review?(sstangl) → review+
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.
Attachment #602706 - Flags: review+
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.
Attachment #602706 - Attachment is obsolete: true
Attachment #603939 - Flags: review?(sstangl)
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.
Attachment #603939 - Flags: review?(sstangl) → review+
landed: http://hg.mozilla.org/projects/ionmonkey/rev/488290bd2644
Status: NEW → RESOLVED
Closed: 12 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.