1044578 - Assertion failure: !minimalInterval(interval), at js/src/jit/BacktrackingAllocator.cpp:582

Status: RESOLVED DUPLICATE of bug 1071403

(Core :: JavaScript Engine: JIT, defect)

Description

[Douglas Crosher [:dougc]]

Attachment: IONFLAGS=codegen,regalloc log leading up to the failure.

Fresh assertion failure running a large asm.js demo in the ARM simulator.

Assertion failure: !minimalInterval(interval), at js/src/jit/BacktrackingAllocator.cpp:582

#7  0xf4899340 in js::jit::BacktrackingAllocator::processInterval (this=this@entry=0xffccaddc, interval=interval@entry=0xcee63878) at js/src/jit/BacktrackingAllocator.cpp:582
#8  0xf48997ac in js::jit::BacktrackingAllocator::go (this=this@entry=0xffccaddc) at js/src/jit/BacktrackingAllocator.cpp:156
#9  0xf491f64b in js::jit::GenerateLIR (mir=0xdddfd088) at js/src/jit/Ion.cpp:1643
#10 0xf2644f9a in CheckFunctionsSequential (m=...) at js/src/jit/AsmJS.cpp:5474
#11 CheckFunctionsParallel (m=...) at js/src/jit/AsmJS.cpp:5710
#12 0xf48a65e1 in CheckModule (cx=cx@entry=0xd261cae0, parser=..., stmtList=stmtList@entry=0xdd7823a0, moduleOut=moduleOut@entry=0xffccc3c8, compilationTimeReport=compilationTimeReport@entry=0xffccc3c0)
    at js/src/jit/AsmJS.cpp:6843
#13 0xf48a8acf in js::CompileAsmJS (cx=0xd261cae0, parser=..., stmtList=stmtList@entry=0xdd7823a0, validated=validated@entry=0xffccc43c) at js/src/jit/AsmJS.cpp:6926

(gdb) list
577	
578	        // A minimal interval cannot be split any further. If we try to split
579	        // it at this point we will just end up with the same interval and will
580	        // enter an infinite loop. Weights and the initial live intervals must
581	        // be constructed so that any minimal interval is allocatable.
582	        JS_ASSERT(!minimalInterval(interval));
583	
584	        if (canAllocate && fixed)
585	            return splitAcrossCalls(interval);
586	        return chooseIntervalSplit(interval, conflict);


(gdb) print *interval
$2 = {<js::InlineListNode<js::jit::LiveInterval>> = {<js::InlineForwardListNode<js::jit::LiveInterval>> = {next = 0x0}, prev = 0x0}, <js::jit::TempObject> = {<No data fields>}, 
  ranges_ = {<mozilla::VectorBase<js::jit::LiveInterval::Range, 1u, js::jit::IonAllocPolicy, js::Vector<js::jit::LiveInterval::Range, 1u, js::jit::IonAllocPolicy> >> = {<js::jit::IonAllocPolicy> = {
        alloc_ = @0xdddfd010}, static kElemIsPod = false, static kMaxInlineBytes = 1024, static kInlineCapacity = 1, static kInlineBytes = 8, mBegin = 0xcee63894, mLength = 1, mCapacity = 1, mReserved = 1, 
      mStorage = {u = {mBytes = "\346\002\000\000\350\002\000", mDummy = 3195455668966}}, mEntered = false, static sMaxInlineStorage = <optimized out>}, <No data fields>}, 
  alloc_ = {<js::jit::TempObject> = {<No data fields>}, bits_ = 0, static TAG_BIT = 1, static TAG_SHIFT = 0, static TAG_MASK = 1, static KIND_BITS = 3, static KIND_SHIFT = 1, static KIND_MASK = 7, 
    static DATA_BITS = 28, static DATA_SHIFT = 4, static DATA_MASK = 268435455}, spillInterval_ = 0xcee637b8, vreg_ = 121, index_ = 2, requirement_ = {kind_ = js::jit::Requirement::REGISTER, 
    allocation_ = {<js::jit::TempObject> = {<No data fields>}, bits_ = 0, static TAG_BIT = 1, static TAG_SHIFT = 0, static TAG_MASK = 1, static KIND_BITS = 3, static KIND_SHIFT = 1, static KIND_MASK = 7, 
      static DATA_BITS = 28, static DATA_SHIFT = 4, static DATA_MASK = 268435455}, position_ = {static INSTRUCTION_SHIFT = 1, static SUBPOSITION_MASK = 1, bits_ = 0, static MAX = {static INSTRUCTION_SHIFT = 1, 
        static SUBPOSITION_MASK = 1, bits_ = 4294967295, static MAX = <same as static member of an already seen type>, static MIN = {static INSTRUCTION_SHIFT = 1, static SUBPOSITION_MASK = 1, bits_ = 0, 
          static MAX = <same as static member of an already seen type>, static MIN = <same as static member of an already seen type>}}, static MIN = <same as static member of an already seen type>}}, hint_ = {
    kind_ = js::jit::Requirement::NONE, allocation_ = {<js::jit::TempObject> = {<No data fields>}, bits_ = 0, static TAG_BIT = 1, static TAG_SHIFT = 0, static TAG_MASK = 1, static KIND_BITS = 3, 
      static KIND_SHIFT = 1, static KIND_MASK = 7, static DATA_BITS = 28, static DATA_SHIFT = 4, static DATA_MASK = 268435455}, position_ = {static INSTRUCTION_SHIFT = 1, static SUBPOSITION_MASK = 1, 
      bits_ = 0, static MAX = {static INSTRUCTION_SHIFT = 1, static SUBPOSITION_MASK = 1, bits_ = 4294967295, static MAX = <same as static member of an already seen type>, static MIN = {
          static INSTRUCTION_SHIFT = 1, static SUBPOSITION_MASK = 1, bits_ = 0, static MAX = <same as static member of an already seen type>, static MIN = <same as static member of an already seen type>}}, 
      static MIN = <same as static member of an already seen type>}}, uses_ = {<js::InlineForwardListNode<js::jit::UsePosition>> = {next = 0xcee638d8}, tail_ = 0xcee638d8, modifyCount_ = 1}, 
  lastProcessedRange_ = 4294967295}

Attaching a debug log leading up to the failure. The asm.js function that failed to compile does not appear to be large, so it might be possible to isolate it and make a small test case.

Comment 1

[Douglas Crosher [:dougc]]

Attachment: Test case.

Had some luck extracting a small test case. This reproduces on m-c and Aurora.

Can anyone familiar with this code shot the issue?

Comment 2

[Dan Gohman [:sunfish]]

Attachment: further-reduced.js

I reduced the testcase a little further; attached is the result.

I found the problem. After doing some work, the backtracking allocator finds itself attempting to allocate some live interval which happens to need a d register:

[RegAlloc] Allocating v6[2] [84,86) v6:r@85 [priority 2] [weight 1000000]

Considering all registers, it discovers that every one has a conflict. It decides that the best thing to do is evict one of the existing live intervals, and it picks one which happens to be in s6:

[RegAlloc]   Evicting v8[0] req(r) has(s6) [23,178) v8:r@150 [priority 155] [weight 25]

Ordinarily, evicting a register would be enough to make the register available for register allocation again. However, the key thing here is that we happened to pick an s register to evict, while what we need is a d register.

When we need a d register and there aren't any available and we've decided to evict, we should perhaps try to make sure we evict a d register. We could also think about evicting two adjacent s registers at the same time, though that'll take some heuristic consideration. We could even try to figure out if there's any s register available, and if so evict the adjacent s register.

Comment 3

[Marty Rosenberg [:mjrosenb]]

> When we need a d register and there aren't any available and we've decided
> to evict, we should perhaps try to make sure we evict a d register. We could
> also think about evicting two adjacent s registers at the same time, though
> that'll take some heuristic consideration. We could even try to figure out
> if there's any s register available, and if so evict the adjacent s register.

Yup.  Unfortunately, I think we need this hueristic, since we aren't guaranteed that there is a d register that can be evicted.

Comment 4

[Marty Rosenberg [:mjrosenb]]

As I expected, a simple heuristic of "sum the spill weights of all of the conflicting intervals, and select pconflicting based on the sum of all conflicting weights for the trial register" works, but it is not ideal in that it *requires* multiple passes to get it correct.
E.g. it can decide that s6 + s7 is actually the best to spill, spill s6, then spill s6.  On the next pass, it is guaranteed to select s7, and this happens to work with MAX_ATTEMPTS = 2, but when SIMD support is here, and q2 conflicts with s8, s9, s10, and s11, this breaks down.  If we expand pconflicting to an array (capped at the maximum number of aliases), we can explicitly store every interval that needs to be spilled, and then just spill them all in the spill code.  I'll write up a patch that does this.

Comment 5

[Marty Rosenberg [:mjrosenb]]

Attachment: evictAllAliases-r0.patch

Comment 6

[Marty Rosenberg [:mjrosenb]]

Comment on attachment 8463824 [details] [diff] [review]
evictAllAliases-r0.patch

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

::: js/src/jit/BacktrackingAllocator.cpp
@@ +797,5 @@
> +                // convention). this is non-perfect because this optimization
> +                // also applies if the register-to-be-evicted is strictly
> +                // larger than r. There is currently no api to give this
> +                // information, so check a directly for now.
> +                if (a == 0) {

I can either add this api, or this can be a follow-up.  Also, I realize normally, we add a helper function, rather than setting a flag like this, but it looked like a helper function would need to have more arguments than I was comfortable with.  I can still do that, if you think it will be clearer.

Comment 7

[Dan Gohman [:sunfish]]

Comment on attachment 8463824 [details] [diff] [review]
evictAllAliases-r0.patch

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

This does seem like a reasonable approach, though I'll need to think about the specifics a little more.

::: js/src/jit/BacktrackingAllocator.cpp
@@ +566,5 @@
>              // If that didn't work, but we have a non-fixed LiveInterval known
>              // to be conflicting, maybe we can evict it and try again.
>              if (attempt < MAX_ATTEMPTS &&
>                  !fixed &&
> +                conflict[0] &&

Is checking just conflict[0] instead of all elements being conservative, or is it actually sufficient here?

@@ +797,5 @@
> +                // convention). this is non-perfect because this optimization
> +                // also applies if the register-to-be-evicted is strictly
> +                // larger than r. There is currently no api to give this
> +                // information, so check a directly for now.
> +                if (a == 0) {

This patch currently does make this code rather hard to follow. I'd say a goto would be justified here, since you just need a multi-level break. I don't have any other immediate ideas though.

Comment 8

[Marty Rosenberg [:mjrosenb]]

(In reply to Dan Gohman [:sunfish] from comment #7)
> Comment on attachment 8463824 [details] [diff] [review]
> evictAllAliases-r0.patch
> 
> Review of attachment 8463824 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> This does seem like a reasonable approach, though I'll need to think about
> the specifics a little more.
> 
> ::: js/src/jit/BacktrackingAllocator.cpp
> @@ +566,5 @@
> >              // If that didn't work, but we have a non-fixed LiveInterval known
> >              // to be conflicting, maybe we can evict it and try again.
> >              if (attempt < MAX_ATTEMPTS &&
> >                  !fixed &&
> > +                conflict[0] &&
> 
> Is checking just conflict[0] instead of all elements being conservative, or
> is it actually sufficient here?
This is just checking if there are any conflicts.  There is a (currently) unstated invariant that the array is filled in order, starting with the 0th element.

> 
> @@ +797,5 @@
> > +                // convention). this is non-perfect because this optimization
> > +                // also applies if the register-to-be-evicted is strictly
> > +                // larger than r. There is currently no api to give this
> > +                // information, so check a directly for now.
> > +                if (a == 0) {
> 
> This patch currently does make this code rather hard to follow. I'd say a
> goto would be justified here, since you just need a multi-level break. I
> don't have any other immediate ideas though.

IMO, one of the best improvements C/C++ can get is the ability to specify which loop/switch you're breaking out of.

Comment 9

[Dan Gohman [:sunfish]]

Comment on attachment 8463824 [details] [diff] [review]
evictAllAliases-r0.patch

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

Ok, this looks fine, with comments below addressed. Any ideas you have for encapsulating this code would not be unwelcome :-).

::: js/src/jit/BacktrackingAllocator.cpp
@@ +566,5 @@
>              // If that didn't work, but we have a non-fixed LiveInterval known
>              // to be conflicting, maybe we can evict it and try again.
>              if (attempt < MAX_ATTEMPTS &&
>                  !fixed &&
> +                conflict[0] &&

> This is just checking if there are any conflicts.  There is a (currently)
> unstated invariant that the array is filled in order, starting with the 0th
> element.

Please state the invariant somewhere. A comment in the code above explaining why it's ok to just check comment[0] would be good, since this seems to be the main place where it's assumed.

@@ +1932,5 @@
> +        if (ret == nullptr || conflicts[i]->start() < ret->start())
> +            ret = conflicts[i];
> +    }
> +    return ret;
> +}

These two functions should be marked static.

::: js/src/jit/arm/Architecture-arm.h
@@ +37,5 @@
>  static const uint32_t ShadowStackSpace = 0;
> +
> +// This is for the register allocators. It is so the allocator can keep track
> +// of all intervals that alias a given register. Since S0, S1 and D0 in use
> +// at the same time, the largest number of aliased registers is 2.

This comment should start by explaining what MaxAliasedRegisters means. How about "This is the maximim number of registers which can alias any given register"?

::: js/src/jit/x64/Architecture-x64.h
@@ +24,5 @@
>  static const uint32_t ShadowStackSpace = 0;
>  #endif
>  
> +// This is so the register allocator knows the largest number of intervals
> +// it may have to evict at once

Ditto for this comment.

::: js/src/jit/x86/Architecture-x86.h
@@ +25,5 @@
>  // components of a js::Value.
>  static const int32_t NUNBOX32_TYPE_OFFSET         = 4;
>  static const int32_t NUNBOX32_PAYLOAD_OFFSET      = 0;
> +// This is so the register allocator knows the largest number of intervals
> +// it may have to evict at once

Ditto ditto.

Comment 10

[Ryan VanderMeulen [:RyanVM]]

Backed out for ARM simulator orange.
https://hg.mozilla.org/integration/mozilla-inbound/rev/123d4bd5a50b

https://tbpl.mozilla.org/php/getParsedLog.php?id=46766723&tree=Mozilla-Inbound