1071403 - IonMonkey: !minimalInterval(interval), at js/src/jit/BacktrackingAllocator.cpp:536

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Douglas Crosher [:dougc]]

With the patch in bug 1070971 a register allocation failure is tickled testing a large asm.js demo on the ARM simulator:

[282,283 NegD] [def v112<d>] [use v105:r]
[284,285 NegD] [def v113<d>] [use v110:r]
[286,287 BitOpI] [def v114<i>] [use v8:r] [use c]
[288,289 DoubleToFloat32] [def v115<f>] [use v112:r]
[290,291 AsmJSStoreHeap] [use v114:r] [use v115:r]

[RegAlloc] Allocating v112[2] [288,290) v112:r@289 [priority 2] [weight 1000000]
[RegAlloc]   d0 collides with v100[0] [259,473) [weight 37]
[RegAlloc]   d1 collides with v102[0] [263,477) [weight 37]
[RegAlloc]   d2 collides with v87[0] [233,401) [weight 59]
[RegAlloc]   d3 collides with v98[0] [255,471) [weight 37]
[RegAlloc]   d4 collides with v91[0] [241,403) [weight 61]
[RegAlloc]   d5 collides with v95[0] [249,407) [weight 63]
[RegAlloc]   s12 collides with v51[0] [161,361) [weight 30]
[RegAlloc]   s14 collides with v104[0] [267,433) [weight 84]
[RegAlloc]   s16 collides with v55[0] [169,367) [weight 30]
[RegAlloc]   s18 collides with v63[0] [185,363) [weight 33]
[RegAlloc]   s20 collides with v109[0] [277,437) [weight 87]
[RegAlloc]   s22 collides with v75[0] [209,365) [weight 38]
[RegAlloc]   s24 collides with v115[0] [289,427) [weight 86]
[RegAlloc]   d13 collides with v111[0] [281,294) [weight 307]
[RegAlloc]   d14 collides with v113[0] [285,298) [weight 307]
[RegAlloc]   Evicting v51[0] req(r) has(s12) [161,361) v51:r@162 v51:r@360 [priority 200] [weight 30]
[RegAlloc]   d0 collides with v100[0] [259,473) [weight 37]
[RegAlloc]   d1 collides with v102[0] [263,477) [weight 37]
[RegAlloc]   d2 collides with v87[0] [233,401) [weight 59]
[RegAlloc]   d3 collides with v98[0] [255,471) [weight 37]
[RegAlloc]   d4 collides with v91[0] [241,403) [weight 61]
[RegAlloc]   d5 collides with v95[0] [249,407) [weight 63]
[RegAlloc]   s13 collides with v59[0] [177,357) [weight 33]
[RegAlloc]   s14 collides with v104[0] [267,433) [weight 84]
[RegAlloc]   s16 collides with v55[0] [169,367) [weight 30]
[RegAlloc]   s18 collides with v63[0] [185,363) [weight 33]
[RegAlloc]   s20 collides with v109[0] [277,437) [weight 87]
[RegAlloc]   s22 collides with v75[0] [209,365) [weight 38]
[RegAlloc]   s24 collides with v115[0] [289,427) [weight 86]
[RegAlloc]   d13 collides with v111[0] [281,294) [weight 307]
[RegAlloc]   d14 collides with v113[0] [285,298) [weight 307]
[RegAlloc]   Evicting v55[0] req(r) has(s16) [169,367) v55:r@170 v55:r@366 [priority 198] [weight 30]
[RegAlloc]   d0 collides with v100[0] [259,473) [weight 37]
[RegAlloc]   d1 collides with v102[0] [263,477) [weight 37]
[RegAlloc]   d2 collides with v87[0] [233,401) [weight 59]
[RegAlloc]   d3 collides with v98[0] [255,471) [weight 37]
[RegAlloc]   d4 collides with v91[0] [241,403) [weight 61]
[RegAlloc]   d5 collides with v95[0] [249,407) [weight 63]
[RegAlloc]   s13 collides with v59[0] [177,357) [weight 33]
[RegAlloc]   s14 collides with v104[0] [267,433) [weight 84]
[RegAlloc]   s17 collides with v107[0] [273,435) [weight 86]
[RegAlloc]   s18 collides with v63[0] [185,363) [weight 33]
[RegAlloc]   s20 collides with v109[0] [277,437) [weight 87]
[RegAlloc]   s22 collides with v75[0] [209,365) [weight 38]
[RegAlloc]   s24 collides with v115[0] [289,427) [weight 86]
[RegAlloc]   d13 collides with v111[0] [281,294) [weight 307]
[RegAlloc]   d14 collides with v113[0] [285,298) [weight 307]
Assertion failure: !minimalInterval(interval), at js/src/jit/BacktrackingAllocator.cpp:536

It looks like an issue with the float32 support for the ARM. It needs a free double sized register but evicts only the float sided half and when it retries it still fails. Should it be evicting float sized pairs to free up a double sized register?

It might be possible to reduce the demo to a test case.

Comment 1

[Jan de Mooij [:jandem]]

Needinfo from Marty since it seems to be float32-related.

Comment 2

[Brian Hackett [Laid off!]]

Attachment: patch

This bug also bites on octane-mandreel.  In one function the backtracking allocator iloops, so we end up not being able to Ion compile anything until that compilation ends up being canceled.

This patch fixes this issue by keeping track of conflict lists rather than individual conflicting intervals.  If we are trying to allocate an interval to a physical register which has multiple conflicts due to register aliasing, we evict all those conflicts at once, so that when we then retry to allocate we are guaranteed to succeed.  An interval can only evict a set of other intervals if it has a higher spill weight than each of them (a property the backtracking allocator requires for termination).

Comment 4

[Nicolas B. Pierron [:nbp]]

(In reply to Jan de Mooij [:jandem] from comment #1)
> Needinfo from Marty since it seems to be float32-related.

I've got this issue while adding SIMD to x64 register sets.  Somehow, I think I managed to fix it on x64 without the above patch.

Comment 5

[Nicolas B. Pierron [:nbp]]

Just a side-note, while fixing again some issue with this assertion, I noticed that the source of the issue was not in the register allocator but caused by the fact that the fixed register of one of the uses is not compatible with the type of the definition.

Comment 6

[Dan Gohman [:sunfish]]

Comment on attachment 8562877 [details] [diff] [review]
patch

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

Register aliases strike again :)

::: js/src/jit/BacktrackingAllocator.cpp
@@ +809,5 @@
>              if (existing.interval->hasVreg()) {
> +                MOZ_ASSERT(existing.interval->getAllocation()->toRegister() == rAlias.reg);
> +                bool duplicate = false;
> +                for (size_t i = 0; i < aliasedConflicting.length(); i++)
> +                    duplicate |= aliasedConflicting[i] == existing.interval;

One hopes that aliasedConflicting will never be quite large, but breaking out of the loop early when a duplicate is detected would make it a little more clear that this is a search loop.

Comment 7

[Brian Hackett [Laid off!]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/3e172dcfa9a5

Comment 8

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/3e172dcfa9a5