Open Bug 1135834 Opened 9 years ago Updated 2 years ago

Backtracking allocator should recover better when a live interval has conflicting fixed requirements

Categories

(Core :: JavaScript Engine: JIT, enhancement, P5)

enhancement

Tracking

()

People

(Reporter: sunfish, Unassigned)

References

(Blocks 1 open bug)

Details

Attachments

(1 file)

In the following testcase:

function Module() {
  "use asm";

  function h(n, r) {
    n = n|0;
    r = r|0;
    if (0 < (n|0))
      return 0;
    return r|0;
  }

  return h;
}

var m = Module();

The backtracking allocator needlessly spills |r| here.

The IONFLAGS=regalloc spew looks like this (|r| is v2)

[RegAlloc] Allocating v2[0] [5,8) [12,14) v2:rax@13 [priority 5] [weight 800]
[RegAlloc]   Requirement rsi, fixed by definition
[RegAlloc]   Requirement rax, due to use at 13
[RegAlloc]   interval does not contain hot code
[RegAlloc]   interval is defined by a register
[RegAlloc]   interval's last use is a register use
[RegAlloc]   split at all register uses
[RegAlloc]     splitting interval v2[0] req(rsi) [5,8) [12,14) v2:rax@13 into:
[RegAlloc]       v2[0] [5,6)
[RegAlloc]       v2[0] [12,14) v2:rax@13
[RegAlloc]       v2[0] [6,8) [12,14)

So the situation is that the live interval has two FIXED requirements; a FIXED def in rsi, and a FIXED use in rax. None of the backtracking allocator's optimizations kick in, and it ends up falling back on the spill-everywhere approach. Ideally, what we want here is for the regalloc to split the interval in one place, so that it can insert a simple copy.
Blocks: 826741
Blocks: sm-js-perf
Priority: -- → P5
I've made a patch that tries to split fixed def and use requirements in the backtracking register allocator. It solves the test case's problem. See the log file:

[RegAlloc] Allocating  v2 [5,10) (def) ## v2 [14,16) v2:rax@15 [priority 7] [weight 571]
[RegAlloc]   Requirement rsi, fixed by definition
[RegAlloc]   Requirement rax, due to use at 15
[RegAlloc]   bundle does not contain hot code
[RegAlloc]   bundle is defined by a register
[RegAlloc]   bundle's last use is a register use
[RegAlloc]   split between fixed def/use at 14
[RegAlloc]     splitting bundle  v2 [5,10) (def) ## v2 [14,16) into:
[RegAlloc]        v2 [5,10) (def)
[RegAlloc]        v2 [14,16) v2:rax@15

and the resulting MIR graph:

Block 0 [successor 1] [successor 2]
[2,3 WasmParameter] [def v1<i>:rdi]
[4,5 WasmParameter] [def v2<i>:rsi]
[6,7 WasmParameter] [def v3<g>:r14]
[8,9 CompareAndBranch] [use v1:r rdi] [use c]

Block 1
[10,11 Integer] [def v4<i>:rax]
[12,13 WasmReturn] [use v4:rax rax] [use v3:r14 r14]

Block 2
[MoveGroup] [rsi -> rax]
[14,15 WasmReturn] [use v2:rax rax] [use v3:r14 r14]

I'm not sure who to ask for a review, but since you are reporter I set the flag on your username.
Assignee: nobody → sandervv
Attachment #8827148 - Flags: review?(sunfish)
Interesting! Yes, I hope to review this soon. Have you looked at the impact of this patch on other testcases to gauge the overall impact?
Overall, the patch looks good to me. Have you looked at all at how often this new heuristic performs splits in real-world code?
Comment on attachment 8827148 [details] [diff] [review]
try-split-between-fixed-def-use.patch

Clearing r? for now; please re-request review when you've had a chance to look at the impact of this patch on other code. Thanks!
Attachment #8827148 - Flags: review?(sunfish)

The bug assignee didn't login in Bugzilla in the last 7 months.
:sdetar, could you have a look please?
For more information, please visit auto_nag documentation.

Assignee: sandervv → nobody
Flags: needinfo?(sdetar)
Flags: needinfo?(sdetar)
Severity: normal → S3
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: