Closed Bug 660967 Opened 13 years ago Closed 13 years ago

IonMonkey: Box insertion results in iterator modification during iteration

Categories

(Core :: JavaScript Engine, defect)

x86_64
Linux
defect
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: adrake, Assigned: dvander)

References

Details

Attachments

(2 files, 1 obsolete file)

Noticed this in C1visualizer when variables being boxed died in the middle of a block with no use:

        if (required == MIRType_Value) {
            // The input is a specific type, but it must be boxed.
            MBox *box = MBox::New(ins);

MBox::New adds a new use to the use chain. The iterator gets confused later at:

            }
            use->replaceOperand(uses, box);
        } else if (actual == MIRType_Value) {

and ends up simply removing both uses. Even in the case that that worked, though, it would be a double use, so the right thing to do is to remove the old use entirely.
So, I see a couple ways to solve this neatly:

- Doubly link the use chain, so the iterator doesn't have any state to be inconsistent.
- Add a special case for use.unlink() that can deal with modifications to the iterator.

My quick hackaround was to do the replaceOperand by index and then replace the iterator with a new one since the old one is toast, which works but makes the algorithm staggeringly inefficient.
This patch makes MUse be doubly-linked. This is probably the cleanest way to preserve iterator correctness in the presence of modification while preserving constant time insertion/removal/iteration. Thoughts?
Ack. Good catch.
Status: NEW → ASSIGNED
Attached patch slower fix (obsolete) — Splinter Review
Here's a slow version. I'm on the edge about this because on one hand, the LSRA literature notes that having small instruction-related structures was important for compiler performance. On the other hand, we'll be creating tons of snapshots, combined with our guard-at-def strategy means longer use chains and more replacing.

Worst case, we can just wait and measure once we have bigger programs to test. The double-linked solution looks good though I'd advocate using InlineList.
Attachment #536516 - Flags: review?(adrake)
Another option would be to make iterators implicitly push themselves on a fix-up list, but really I'm starting to feel like MUseIterator feels weird and is gross. InlineListNode has its own normal-ish iterator. (For the record, v8 uses a single linked list and always does a search to remove a use.)
Comment on attachment 536516 [details] [diff] [review]
slower fix

On the following test case, this patch allows fixup to infinite loop:

function loop(x,y,z,w) {
	do {
		if (z)
			return 1;
		else if (x & y)
			return 2;
	} while(w);
}
loop(1,2,3,0)

The replaceOperand function does not affect the in-progress iterator, so the fixup iterator never advances once this block is entered:

        } else if (actual == MIRType_Value) {
            // The input is a value, but it wants explicit unboxing.
            MUnbox *unbox = MUnbox::New(ins, required);
            use->block()->insertBefore(use, unbox);
            unbox->assignSnapshot(use->snapshot());
            use->replaceOperand(uses, unbox);
Attachment #536516 - Flags: review?(adrake)
I filed bug 661090 as a follow-up for the performance question.

Yeah, I felt a little uneasy adding another field, and InlineList definitely is the way to go if we do end up needing it; it had slipped my mind when I was fixing this up.
See Also: → 661090
Attached patch slower fix v2Splinter Review
Assignee: general → dvander
Attachment #536516 - Attachment is obsolete: true
Attachment #536814 - Flags: review?(adrake)
Attachment #536814 - Flags: review?(adrake) → review+
http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/03ae9d85fcdb
Status: ASSIGNED → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.