Closed Bug 901086 Opened 11 years ago Closed 10 years ago

IonMonkey: Infinite loop in LinearScanAllocator::allocateRegisters

Categories

(Core :: JavaScript Engine, defect)

x86_64
Windows 7
defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla30

People

(Reporter: vladan, Assigned: jandem)

References

()

Details

Attachments

(2 files)

The LSRA regalloc gets into an infinite loop within the following stack:

>	mozjs.dll!js::ion::LinearScanAllocator::splitInterval() Line 602
 	mozjs.dll!js::ion::LinearScanAllocator::assign() Line 722
 	mozjs.dll!js::ion::LinearScanAllocator::spill() Line 837
 	mozjs.dll!js::ion::LinearScanAllocator::allocateRegisters() Line 204
 	mozjs.dll!js::ion::LinearScanAllocator::go() Line 1171
 	mozjs.dll!js::ion::GenerateLIR(js::ion::MIRGenerator * mir) Line 1195
...

The splitInterval is hit repeatedly, and the loop within |allocateRegisters| is never exited.  This seems like it might reproduce on google docs, but at present no clear reproduction path.

It seems like the |unhandled| queue in the LSRA never becomes empty.
I can consistently reproduce this hang in Nightly on Windows 7. The Gecko profiler (extension version 1.12.19) needs to be running, and then I just load http://sweetjs.org/browser/editor.html for a permanent hang
This is usually an instruction that wants too many registers. NI mjrosenb as he's looking into it based on the IRC conversation. Let me know if you need help; should be easy to track down once you have it in a debugger.
Flags: needinfo?(mrosenberg)
Ion log (IONFLAGS=regalloc,logs) for the test case, ends with an assertion failure on my Windows debug build: 
http://people.mozilla.org/~vdjeric/lsaHang.txt
[Scripts] Analyzing script http://sweetjs.org/browser/scripts/parser.js:963 (0xdaf5a6f8) (usecount=1011, level=Optimization_Normal)
[Scripts] Inlining script http://sweetjs.org/browser/scripts/parser.js:279 (0xdaf5a450)
[Scripts] Inlining script http://sweetjs.org/browser/scripts/parser.js:301 (0xdaf29d58)
seems to be the offending compilation.

The issue seems to be the sequence of instructions:
js::jit::LStoreFixedSlotV
js::jit::LBinaryV
where the BinaryV has 4 inputs, and StoreFixedSlotV has 3 inputs, and all of their live ranges start on the StoreFixedSlot, so nothing can be evicted.  Still looking into it.
Ok, I think I found the culprit.  BinaryV's four operands are all UseAtStart, whereas StoreFixedSlotV's are all regular Use.  This means that all seven operands start on the StoreFixedSlotV, three on it's input half, four on its output half.  I am not 100% clear why this slight difference exists in the start of ranges for UseAtStart vs. Use.
Flags: needinfo?(mrosenberg) → needinfo?(jdemooij)
Attached file regalloc.js
reduced test case.  Things to note about it:
All of obj, x, y, and z must be *fully* on the stack before obj.x = x.
If any of them are in registers, their range will start earlier, and be viewed as evictable.  x must match obj.x.  If there is a type monitor before the assignment, then part of x will need to be loaded into a register for the monitor, and we'll fall back into the previous non-asserting case.
Attached patch PatchSplinter Review
LSRA's findBestBlockedRegister is too strict when it looks for available registers. When the current interval starts at the output half of an instruction, it considers intervals that start at the input half of the same instruction as unavailable, but this can cause problems (no available registers) when there are two LIR instructions and the second one has some at-start uses.

This patch fixes both this bug and bug 975940.
Assignee: general → jdemooij
Status: NEW → ASSIGNED
Attachment #8381406 - Flags: review?(dgohman)
Flags: needinfo?(jdemooij)
Comment on attachment 8381406 [details] [diff] [review]
Patch

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

Oh my god, I spent so long looking at that line.  I had no clue that such a simple fix could be correct.
Comment on attachment 8381406 [details] [diff] [review]
Patch

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

I'm not super familiar with LSRA and its way of doing liveness, but in general, rounding the interval start to its ins() does seem like trouble.
Attachment #8381406 - Flags: review?(dgohman) → review+
https://hg.mozilla.org/mozilla-central/rev/2c92141f39bf
Status: ASSIGNED → RESOLVED
Closed: 10 years ago
Flags: in-testsuite+
Resolution: --- → FIXED
Target Milestone: --- → mozilla30
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: