IonMonkey: Greedy allocator produces unexpectedly finite loop

RESOLVED FIXED

Status

()

defect
RESOLVED FIXED
8 years ago
8 years ago

People

(Reporter: adrake, Assigned: dvander)

Tracking

(Blocks 1 bug)

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(3 attachments, 1 obsolete attachment)

Reporter

Description

8 years ago
Posted 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
Posted 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)
Reporter

Comment 3

8 years ago
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+
Reporter

Comment 4

8 years ago
Posted 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).
Posted 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)
Reporter

Updated

8 years ago
Attachment #551387 - Flags: review?(adrake) → review+
http://hg.mozilla.org/projects/ionmonkey/rev/1f849ecde436
Status: ASSIGNED → RESOLVED
Closed: 8 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.