660967 - IonMonkey: Box insertion results in iterator modification during iteration

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Andrew Drake [:adrake]]

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.

Comment 1

[Andrew Drake [:adrake]]

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.

Comment 2

[Andrew Drake [:adrake]]

Attachment: Doubly-linked patch.

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?

Comment 3

[David Anderson [:dvander] - inactive, e-mail if emergency]

Ack. Good catch.

Comment 4

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: slower fix

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.

Comment 5

[David Anderson [:dvander] - inactive, e-mail if emergency]

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 6

[Andrew Drake [:adrake]]

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);

Comment 7

[Andrew Drake [: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.

Comment 8

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: slower fix v2

Comment 9

[David Anderson [:dvander] - inactive, e-mail if emergency]

http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/03ae9d85fcdb