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




JavaScript Engine: JIT
3 years ago
a year ago


(Reporter: sunfish, Assigned: Sander Mathijs van Veen)


(Blocks: 1 bug)

Firefox Tracking Flags

(Not tracked)



(1 attachment)



3 years ago
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


2 years ago
Blocks: 1307062
Priority: -- → P5

Comment 1

a year ago
Created attachment 8827148 [details] [diff] [review]

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)

Comment 2

a year ago
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

a year ago
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

a year ago
Comment on attachment 8827148 [details] [diff] [review]

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)
You need to log in before you can comment on or make changes to this bug.