677075 - IonMonkey: Greedy allocator produces unexpectedly finite loop

Status: RESOLVED FIXED

Description

[Andrew Drake [:adrake]]

Attachment: Test case

With --ion --ion-licm=off --ion-regalloc=greedy on x86, the attached test case spins for a couple seconds in generated code (!) and then returns undefined. Correct behavior is to spin forever.

Comment 1

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

The LIR looks like this:

0: param0
1: param1
2: add(0, 1)
3: if(2) goto 2

Since the greedy allocator works in reverse, seeing uses before defs, it thinks 3 is the last use of 2, which is not true as it is in a loop. So we get:

0: edi = param0
1: esi = param1
2: edi = add(edi, esi)
3: if(edi) goto 2

So the result ends up accumulating in edi which is wrong.

Comment 2

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

Attachment: fix

Easiest fix I could think of (save for disabling the last-use optimization): insert moves at the top of the loop for any state that doesn't match the exit of the loop. This inserts some useless moves but we now get correct code:

=> 0xf73ed18c:  mov    %ebx,%edi
=> 0xf73ed18e:  mov    %ebp,%esi
=> 0xf73ed190:  add    %esi,%edi
=> 0xf73ed192:  test   %edi,%edi
=> 0xf73ed194:  jne    0xf73ed1a9
=> 0xf73ed1a9:  jmp    0xf73ed18c

Comment 3

[Andrew Drake [:adrake]]

Comment on attachment 551366 [details] [diff] [review]
fix

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

::: js/src/ion/x86/Trampoline-x86.cpp
@@ +147,5 @@
>          Call passed-in code, get return value and fill in the
>          passed in return value pointer
>      ***************************************************************/
>      // Call code  --code pointer is in ebp + 8
> +    masm.breakpoint();

This probably should go.

Comment 4

[Andrew Drake [:adrake]]

Attachment: Test case 2

This loop is suspiciously finite when run with the same parameters as the first test case, with this fix applied (with the breakpoint removed).

Comment 5

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

Attachment: v2

Okay, the fix was on the right track but it was kind of bogus. It's not valid to just pick a random register and insert a move, because the register might not be free in the loop body. Instead, this patch just always reloads from the stack.

This does not generate very efficient code, but that's what LSRA is for.

Comment 6

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

http://hg.mozilla.org/projects/ionmonkey/rev/1f849ecde436