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

Status: NEW

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

Description

[Dan Gohman [:sunfish]]

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.

Comment 1

[Sander Mathijs van Veen]

Attachment: try-split-between-fixed-def-use.patch

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.

Comment 2

[Dan Gohman [: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?

Comment 3

[Dan Gohman [:sunfish]]

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 4

[Dan Gohman [:sunfish]]

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!

Comment 5

[BugBot [:suhaib / :marco/ :calixte]]

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.