Closed Bug 677075 Opened 10 years ago Closed 10 years ago

IonMonkey: Greedy allocator produces unexpectedly finite loop

Categories

(Core :: JavaScript Engine, defect)

x86_64
Linux
defect
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: adrake, Assigned: dvander)

References

(Blocks 1 open bug)

Details

Attachments

(3 files, 1 obsolete file)

Attached file 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.
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.
Assignee: general → dvander
Status: NEW → ASSIGNED
Attached patch fix (obsolete) — Splinter Review
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
Attachment #551366 - Flags: review?(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.
Attachment #551366 - Flags: review?(adrake) → review+
Attached file 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).
Attached patch v2Splinter Review
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.
Attachment #551366 - Attachment is obsolete: true
Attachment #551387 - Flags: review?(adrake)
Attachment #551387 - Flags: review?(adrake) → review+
http://hg.mozilla.org/projects/ionmonkey/rev/1f849ecde436
Status: ASSIGNED → RESOLVED
Closed: 10 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.