Last Comment Bug 756094 - IonMonkey: Assertion failure: defdata->classPrev == __null, at ion/ValueNumbering.cpp:464
: IonMonkey: Assertion failure: defdata->classPrev == __null, at ion/ValueNumbe...
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: All All
-- normal (vote)
: ---
Assigned To: Ryan Pearl [:rpearl]
: Jason Orendorff [:jorendorff]
Depends on:
Blocks: IonFuzz
  Show dependency treegraph
Reported: 2012-05-17 08:01 PDT by Jan de Mooij [:jandem]
Modified: 2012-05-23 17:26 PDT (History)
9 users (show)
See Also:
Crash Signature:
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---

breakClass() before adding to the value map (1.28 KB, patch)
2012-05-18 19:43 PDT, Ryan Pearl [:rpearl]
no flags Details | Diff | Splinter Review
Alternate approach (2.79 KB, patch)
2012-05-22 08:19 PDT, Kannan Vijayan [:djvj]
no flags Details | Diff | Splinter Review
Alternative approach, take 2 (5.00 KB, patch)
2012-05-22 10:31 PDT, Ryan Pearl [:rpearl]
marty.rosenberg: review+
Details | Diff | Splinter Review

Description User image Jan de Mooij [:jandem] 2012-05-17 08:01:26 PDT
The following testcase asserts on revision 8958cc186a4f, 32-bit and 64-bit, with and without --ion-eager.

Marty, I got this assert a lot with chunked compilation, I hope it's the same issue.

function f() {
    for (var i=0; i<100; i++) {
        var x, y, z;
        y = null;
        for (var j=0; j<100; j++) {
            for(var l in []) { }
Comment 1 User image Ryan Pearl [:rpearl] 2012-05-18 19:43:26 PDT
Created attachment 625341 [details] [diff] [review]
breakClass() before adding to the value map

Sorry to take your bug, but I was staring this because I was bored. I am pretty sure that the attached fixes the bug, but it would be good if you could convince me that my reasoning is correct. We just need to re-lookup the value number if |breakClass(ins)| changes it, and add it otherwise. Luckily, there is already a hashtable method to do this!
Comment 2 User image Ryan Pearl [:rpearl] 2012-05-19 18:16:49 PDT
Hmm, I am actually a little dubious of my fix. I think it works still, but I suspect it is fixing a symptom, rather than the underlying problem. I believe that the main problem is that we are selecting an incorrect new representative--one that is actually still congruent to the evicted representative.

I believe it is the case that we should select the representative that causes needSplit() to return true. I have a patch for this, but it does a lot of crappy linked list manipulations. I'll clean it up and post it later.
Comment 3 User image Kannan Vijayan [:djvj] 2012-05-22 08:19:07 PDT
Created attachment 626017 [details] [diff] [review]
Alternate approach

I think your take on the last comment is correct.  The real problem is that an incorrect representative is being picked.  I think your patch probably will show correct behaviour, though.  Here's what'll happen:

1. The next member in the class will get picked, even if it's in the same class as the head of the class.
2. It'll be entered into the hashtable as the new head.
3. The relookupOrAdd will put the original head on the tail of the class list.

The next member will be marked for processing, so it'll get hit at some point and likewise migrate to the tail of its own list, picking a new representative - until any same-class members on the head of the list are exhausted, at which point the class will split.

I don't think the patch is incorrect behaviour, but it is a bit roundabout and it seems to add potential for a quadratic runtime as we iterate through the list multiple times (e.g. a case where the all but the last element of the list migrate to the same new class, and we process the members in order).

This was my approach to fixing it: basically modifying breakClass to iterate through the head of the list, manually migrating the heads of the list to the new class, until a proper new representative member shows up.

Lemme know what you think.
Comment 4 User image Ryan Pearl [:rpearl] 2012-05-22 10:31:52 PDT
Created attachment 626080 [details] [diff] [review]
Alternative approach, take 2

Okay, after discussing it on IRC, djvj and I think this is the right approach: break the class into two lists--the prefix is still congruent to the old canonical element--and then split off everything after the first non-congruent element, call it |newRep| into its own list with |newRep| as the canonical element.

I think it's right but please review carefully since linked list code is generally annoying. Also, since I haven't made IM commits in a while... the test suite needs to be run and I don't know how to do that. I think we have some sort of test bot these days?
Comment 5 User image Kannan Vijayan [:djvj] 2012-05-22 14:40:55 PDT
FYI on the testing: I ran a build against jstests on OSX 64-bit and it seems to come up with no regressions.
Comment 6 User image Marty Rosenberg [:mjrosenb] 2012-05-22 15:07:45 PDT
Comment on attachment 626080 [details] [diff] [review]
Alternative approach, take 2

Review of attachment 626080 [details] [diff] [review]:

::: js/src/ion/ValueNumbering.cpp
@@ +479,5 @@
> +        // |newdata| to a new list, with |defdata| still as the canonical
> +        // element.
> +        //
> +        // We then want to take |newdata| and everything after, and
> +        // mark them for processing (since |newdata| is now a new canonical

I can't think of any reasons that we'd ever see this, or it would affect correctness, but it is not the case that everything after |newdata| should be in the congruence class for |newdata|.  Some of them may still be congruent to the old class.
Comment 7 User image Ryan Pearl [:rpearl] 2012-05-23 12:27:20 PDT
Comment 8 User image Ryan Pearl [:rpearl] 2012-05-23 12:54:55 PDT
Addendum to address mjrosenb's comment on the review: the bug is that we select an incorrect representative. Identical behavior would happen if we just moved newRep to the front of the list and marked the whole thing for processing, but this way is no more complex and saves a bit of time, since we already did a search (in |needsSplit()| / now |findSplit()|) to find out which def isn't congruent any more.

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