1310710 - Backtracking allocator: infinite loop until memory is exhausted

Status: RESOLVED DUPLICATE of bug 1309903

(Core :: JavaScript Engine: JIT, defect, P1)

Description

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: limit-registers.patch

I am trying to do something probably unsafe: limit the number of registers available to register allocation, just for testing purposes (thus enforcing more spilling and testing that the right code is generated for stack allocations).

So far, the major issue I've been facing is that some LIR have fixed uses or definitions. In most cases when this happens, I get an assertion failure like we're trying to split a minimal bundle (so the assertion is !minimalBundle), and by getting back in time, I can find which fixed register is needed and whitelist it again. (Think for instance the shift instructions which want the shift operand to be in ecx.)

That being said, in some cases, the register allocation just seems to iloop and exhaust memory. The attached patch is enough to run into this situation, by adding it on top of m-i 2ef2b3f6e7fa2c2ccdcdca40eed23069d8e9a769, and then run the jit-test wasm/basic.js. It is also a missing whitelisted register (r10 in this case), but the IONFLAGS=regalloc output looks like this:

[RegAlloc] [RegAlloc] [RegAlloc]   bundle does not contain hot codeAllocating  v1 [8,9) v1:r10@8 [priority 1] [weight 2000]       v1 [8,9) v1:r10@8
[RegAlloc]   Requirement r10, due to use at 8
[RegAlloc] Allocating  v1 [8,9) v1:r10@8 [priority 1] [weight 2000]
[RegAlloc]   bundle does not contain hot code
[RegAlloc] [RegAlloc]   bundle does not have definition
[RegAlloc]   bundle's last use is a register use
  Requirement r10, due to use at 8
[RegAlloc] [RegAlloc] 
[RegAlloc]   bundle does not contain hot code  bundle does not have definition
[RegAlloc]   bundle's last use is a register use
    splitting bundle  v1 [8,9) into:
[RegAlloc]     splitting bundle  v1 [6,7) into:[RegAlloc]        v1 [8,9) v1:r10@8
[RegAlloc] Allocating  v1 [8,9) v1:r10@8 [priority 1] [weight 2000]
[RegAlloc]   Requirement r10, due to use at 8
[RegAlloc] [RegAlloc]        v1 [6,7) v1:r10@6
  bundle does not have definition
[RegAlloc]   bundle does not contain hot code
[RegAlloc]   bundle does not have definition
[RegAlloc]   bundle's last use is a register use[RegAlloc] [RegAlloc] 
Allocating  v1 [6,7) v1:r10@6 [priority 1] [weight 2000]
[RegAlloc]     splitting bundle  v1 [8,9) into:
[RegAlloc] [RegAlloc]        v1 [8,9) v1:r10@8
  bundle's last use is a register use  Requirement r10, due to use at 6
[RegAlloc] Allocating  v1 [8,9) v1:r10@8 [priority 1] [weight 2000]
[RegAlloc]   Requirement r10, due to use at 8

And this gets on and on, until the memory is exhausted.

Should there be a mechanism to stop register allocation when we run into this kind of situation? I wonder if this can happen in the real world, or if this is just introduced by the dangerous testing I am trying to do here.

Comment 1

[Benjamin Bouvier [:bbouvier] (inactive)]

Here's an unmangled output (by limiting the number of threads to 1):

[RegAlloc] Allocating  v1 [6,7) v1:r10@6 [priority 1] [weight 2000]
[RegAlloc]   Requirement r10, due to use at 6
[RegAlloc]   bundle does not contain hot code
[RegAlloc]   bundle does not have definition
[RegAlloc]   bundle's last use is a register use
[RegAlloc]     splitting bundle  v1 [6,7) into:
[RegAlloc]        v1 [6,7) v1:r10@6
[RegAlloc] Allocating  v1 [6,7) v1:r10@6 [priority 1] [weight 2000]
[RegAlloc]   Requirement r10, due to use at 6
[RegAlloc]   bundle does not contain hot code
[RegAlloc]   bundle does not have definition
[RegAlloc]   bundle's last use is a register use
[RegAlloc]     splitting bundle  v1 [6,7) into:
[RegAlloc]        v1 [6,7) v1:r10@6
[RegAlloc] Allocating  v1 [6,7) v1:r10@6 [priority 1] [weight 2000]
[RegAlloc]   Requirement r10, due to use at 6
[RegAlloc]   bundle does not contain hot code
[RegAlloc]   bundle does not have definition
[RegAlloc]   bundle's last use is a register use
[RegAlloc]     splitting bundle  v1 [6,7) into:
[RegAlloc]        v1 [6,7) v1:r10@6
[RegAlloc] Allocating  v1 [6,7) v1:r10@6 [priority 1] [weight 2000]
[RegAlloc]   Requirement r10, due to use at 6
[RegAlloc]   bundle does not contain hot code
[RegAlloc]   bundle does not have definition
[RegAlloc]   bundle's last use is a register use
[RegAlloc]     splitting bundle  v1 [6,7) into:
[RegAlloc]        v1 [6,7) v1:r10@6

Comment 2

[Benjamin Bouvier [:bbouvier] (inactive)]

OK, will try to elaborate a bit:

- in this example (see previous comment), r10 is obviously missing. That's expected it is missing, because I've taken it (as shown in the patch in comment 1).
- The register allocator seems to iloop to allocate the same bundle all the time.
- From what I've understood, the !minimalBundle assert tries to find these cases.

So I think the path forward might be to change minimalBundle, so it can detect this kind of issues, if this is a realistic issue?

Comment 3

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: regalloc.txt

Example of IONFLAGS=regalloc full output (run on the full wasm/basic.js file, so there are many many functions compiled here before the one that fails regalloc).

Comment 4

[Brian Hackett [Laid off!]]

(In reply to Benjamin Bouvier [:bbouvier] from comment #2)
> OK, will try to elaborate a bit:
> 
> - in this example (see previous comment), r10 is obviously missing. That's
> expected it is missing, because I've taken it (as shown in the patch in
> comment 1).
> - The register allocator seems to iloop to allocate the same bundle all the
> time.
> - From what I've understood, the !minimalBundle assert tries to find these
> cases.
> 
> So I think the path forward might be to change minimalBundle, so it can
> detect this kind of issues, if this is a realistic issue?

Well, I don't know if this is a realistic issue, but asserting would definitely be better than ilooping.  I think that minimalUse is not taking into account this bit of logic from when we built the liveness info:

  // Fixed uses on calls are specially overridden to happen
  // at the input position.
  CodePosition to =
      (use->usedAtStart() || (ins->isCall() && use->isFixedRegister()))
      ? inputOf(*ins)
      : outputOf(*ins);

If you change the 'range->to() == (use->use()->usedAtStart() ? outputOf(ins) : outputOf(ins).next())' clause in minimalUse so that it uses <= instead of ==, does the minimalBundle assertion trigger?

Comment 5

[Benjamin Bouvier [:bbouvier] (inactive)]

(In reply to Brian Hackett (:bhackett) from comment #4)
> If you change the 'range->to() == (use->use()->usedAtStart() ? outputOf(ins)
> : outputOf(ins).next())' clause in minimalUse so that it uses <= instead of
> ==, does the minimalBundle assertion trigger?

Yes it does! I really don't know anything about regalloc (especially if this change can be dangerous or impact performance), so let's see if at least try is happy about it.

https://treeherder.mozilla.org/#/jobs?repo=try&revision=2913237ed863

Comment 6

[Jan de Mooij [:jandem]]

The patch in bug 1309903 cleans up the liveness building logic mentioned in comment 4, so it might also fix this one.

Comment 7

[Benjamin Bouvier [:bbouvier] (inactive)]

(In reply to Jan de Mooij [:jandem] from comment #6)
> The patch in bug 1309903 cleans up the liveness building logic mentioned in
> comment 4, so it might also fix this one.

I'm all in for closing this bug as a duplicate of bug 1309903, if the issue described in comment 2 is addressed by your patch (that is, your patch makes us assert rather than ilooping).

Comment 8

[Benjamin Bouvier [:bbouvier] (inactive)]

With a latest inbound including the patches from bug 1309903, we now properly assert instead of ilooping. Thanks Jan!