900683 - Assertion failure: *to != *moves_[i].to(), at ion/LIR.cpp with --ion-regalloc=backtracking

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Attachment: stack

ParallelArray(11701, function() {
    return /x/
}).reduce(function(a) {
    if (a % 9) {
        for (var y = 0; y; ++y) {}
        return []
    }
})

asserts js debug (32-bit threadsafe deterministic) shell on m-c changeset 129ce98f4cb2 with --ion-regalloc=backtracking at Assertion failure: *to != *moves_[i].to(), at ion/LIR.cpp

Setting needinfo from bhackett because this seems to involve the backtracking allocator.

Comment 1

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

autoBisect shows this is probably related to the following changeset:

The first bad revision is:
changeset:   http://hg.mozilla.org/mozilla-central/rev/6336284c7f1f
user:        Hannes Verschore
date:        Fri May 10 14:49:58 2013 +0200
summary:     Bug 768288: IonMonkey: Inline small functions with loops, r=djvj r=shu

Comment 2

[Hannes Verschore [:h4writer]]

I don't see anything particular about this inlined loop. It looks just like a regular loop. I assume this is not related to the "inline loops" patch, but that inlining just creates a graph where we have this issue, but that it would be possible to create such a graph without inlining.

I tried to look into the reason why we fail, but I'm not too familiar with this code. Also this isn't production code. (Or are we trying to get this finally enabled?). So I decided to not take to long to investigate this issue. I noticed we are adding the same "move" to the loopheader twice and that's why we are failing. Now I didn't directly where we add the other "move" and which one is correct. So I'll leave it for now.

@Brain: if you do think this is caused by my patch, or that it would be important to get this fixed, I could take a second look...

Comment 3

[Christian Holler (:decoder)]

Attachment: [crash-signature] Machine-readable crash signature

Comment 4

[Christian Holler (:decoder)]

I also found this on mozilla-beta, here's the test (doesn't need ParallelArray, so it might be easier to add this one):


function test() {
var a = [1, 2, 3];
var s = '';
for (var x of a)
  for (var i=0 of 'y')
    s += '' + foo() 
} test();

Comment 6

[Dan Gohman [:sunfish]]

The backtracking allocator is splitting a particular live interval with splitAcrossCalls and then splitting part of the remainder with splitAtAllRegisterUses. The problem is that both of these split routines are creating their own "spill interval", so they end up with two spill intervals. The spill intervals are assigned the same stack slot, so it's not entirely inconsistent, but when the code in resolveControlFlow goes to insert moves, it naively emits a store for each spill interval, and the move emitter thinks it's a bug to have two moves to the same destination. That's the assertion failure.

One way to fix this would be to make the move emitter silently ignore a move when there's another move with the same source and destination. But, it seems nicer to make the register allocator avoid this situation in the first place.

Comment 7

[Dan Gohman [:sunfish]]

Attachment: regalloc-niceties.ptach

This is just some random cleanups I made while preparing the other patch.

Comment 8

[Dan Gohman [:sunfish]]

Attachment: regalloc-remember-spill.patch

This fixes the bug by adding a field to LiveInterval to record an available spill interval, if one has been created. This allows the register allocator to avoid creating a second spill interval.

I'm still learning my way around this code, so don't hesitate to tell me to find a different approach to fixing this bug, if appropriate.

Comment 9

[Brian Hackett [Laid off!]]

Comment on attachment 808861 [details] [diff] [review]
regalloc-remember-spill.patch

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

::: js/src/jit/BacktrackingAllocator.cpp
@@ +1613,5 @@
>  
>      LiveIntervalVector newIntervals;
>      uint32_t vreg = interval->vreg();
>  
> +    bool spillIntervalIsNew = false;

Can you add a short comment here describing why a new spill interval isn't needed (i.e. the entire interval is covered by an existing spill interval).

@@ +1663,5 @@
>              }
>  
>              newIntervals.back()->addUse(new UsePosition(iter->use, iter->pos));
>          } else {
> +            if (spillIntervalIsNew)

I think you can JS_ASSERT(spillIntervalIsNew) here instead.

@@ +1769,5 @@
>              }
>              newIntervals.back()->addUse(new UsePosition(iter->use, iter->pos));
>              lastRegisterUse = iter->pos;
>          } else {
> +            if (spillIntervalIsNew)

Ditto.

Comment 10

[Dan Gohman [:sunfish]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/2f924314efe8 https://hg.mozilla.org/integration/mozilla-inbound/rev/e894f34f6286

Comment 11

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/2f924314efe8
https://hg.mozilla.org/mozilla-central/rev/e894f34f6286

Comment 12

[Christian Holler (:decoder)]

Attachment: [crash-signature] Machine-readable crash signature

Comment 13

[Catalin Varga [QA][:VarCat]]

Can someone provide STR or a testcase the help the QA reproduce this issue and verify the fix?

Comment 14

[Ioana (away)]

Tested with the testcase from comment 0 and the one from comment 4 - Firefox 27 js shell from 09/20 and 01/26 - Mac OS X 10.9.

I couldn't reproduce the bug on either build. All I got were code errors and warnings:
Testcase comment 0:
"warning: Bailed out of parallel operation: unsupported at t2.js:2", "warning: Bailed out of parallel operation: unsupported at t2.js:4" on the build with the bug. "ReferenceError: ParallelArray is not defined" on the build with the fix.

Testcase comment 4:
"ReferenceError: foo is not defined", so I replaced foo with i and x. In both cases (i,x), the testcase ran without errors or assertions on the buggy build and gave " SyntaxError: for-of loop variable declaration may not have an initializer: for (var i=0 of 'y')" on the build with the fix.

Please re-add the "verifyme" keyword if you can provide a testcase that we can actually reproduce/verify this bug with.

Comment 15

[Dan Gohman [:sunfish]]

(In reply to Ioana Budnar, QA [:ioana] from comment #14)
> Tested with the testcase from comment 0 and the one from comment 4 - Firefox
> 27 js shell from 09/20 and 01/26 - Mac OS X 10.9.

This bug was specific to 32-bit x86. Mac OS X builds are probably 64-bit, which is probably why you weren't able to reproduce the failure.

Comment 16

[Ioana (away)]

(In reply to Dan Gohman [:sunfish] from comment #15)
> (In reply to Ioana Budnar, QA [:ioana] from comment #14)
> > Tested with the testcase from comment 0 and the one from comment 4 - Firefox
> > 27 js shell from 09/20 and 01/26 - Mac OS X 10.9.
> 
> This bug was specific to 32-bit x86. Mac OS X builds are probably 64-bit,
> which is probably why you weren't able to reproduce the failure.

That's what happened... Unfortunately, I don't have access to any 32-bit Mac machines. Is there a way I can force the JSShell to go 32-bit mode?

Comment 17

[Dan Gohman [:sunfish]]

(In reply to Ioana Budnar, QA [:ioana] from comment #16)
> (In reply to Dan Gohman [:sunfish] from comment #15)
> > (In reply to Ioana Budnar, QA [:ioana] from comment #14)
> > > Tested with the testcase from comment 0 and the one from comment 4 - Firefox
> > > 27 js shell from 09/20 and 01/26 - Mac OS X 10.9.
> > 
> > This bug was specific to 32-bit x86. Mac OS X builds are probably 64-bit,
> > which is probably why you weren't able to reproduce the failure.
> 
> That's what happened... Unfortunately, I don't have access to any 32-bit Mac
> machines. Is there a way I can force the JSShell to go 32-bit mode?

No; the jit only supports code generation for the architecture it's hosted on.