[JSC] GreedyRegAlloc: Add loop-aware live range splitting (disabled by default)

Component: JSC | 899099b

JSTests/stress/regalloc-loop-splitting.js

//@ requireOptions("--airGreedyRegAllocSplitAroundLoops=true")
function clobber(x) { return x | 0; }
noInline(clobber);
 
function test(p) {
    let v0=p+0, v1=p+1, v2=p+2, v3=p+3, v4=p+4, v5=p+5,
        v6=p+6, v7=p+7, v8=p+8, v9=p+9, v10=p+10, v11=p+11,
        v12=p+12, v13=p+13, v14=p+14, v15=p+15;
    let sum = 0;
    for (let i = 0; i < 100; i++)
        sum = clobber(sum + i);  // call clobbers all caller-saved regs
    return v0+v1+v2+v3+v4+v5+v6+v7+v8+v9+v10+v11+v12+v13+v14+v15+sum;
}
// 16 tmps live across a loop with a register-clobbering call — exactly the
// pressure scenario that loop splitting is designed to handle

B3는 JSC의 optimizing JIT compiler이고, Air는 그 하위 assembly IR로서 물리 레지스터 할당이 이루어지는 계층입니다. Greedy register allocator는 live range를 priority 순서로 처리하면서 가상 레지스터(tmp)에 물리 레지스터를 배정하는데, 배정할 수 없는 tmp는 spill되거나 독립적으로 할당 가능한 sub-range로 split됩니다. Loop-aware splitting도 그런 전략 중 하나입니다. 루프 전체에 걸쳐 live하지만 루프 내부에서는 사용되지 않는 tmp는 루프가 도는 동안 레지스터 하나를 그냥 붙잡고 있는 셈이므로, split을 통해 루프 body 안에서 그 레지스터를 풀어줄 수 있습니다.

이번 commit은 이 방식을 구현합니다. 루프 경계를 가로지르는 live range를 가진 tmp를 loop 구간과 non-loop 구간으로 나누어 각각 독립적으로 할당하고, 루프 진입/탈출 지점에는 두 구간 사이에서 값을 옮기는 fixup 코드를 삽입합니다. 이때 값 이동에는 Air의 Shuffle 명령이 사용되는데, A↔B swap 같은 cycle을 포함한 parallel move를 처리할 수 있는 명령입니다. 또한 새로운 CFG normalization pass인 ensureDedicatedLoopEntryExitBlocks가 함께 도입되었습니다. Fixup 코드는 source block의 successor가 정확히 하나이고 target block의 predecessor가 정확히 하나인 edge에서만 안전하게 삽입할 수 있기 때문입니다. 이 정규화 과정이 없으면 fixup block을 삽입하는 행위 자체가 관련 없는 다른 predecessor들의 control flow까지 바꿔버릴 수 있습니다. 기능 전체는 airGreedyRegAllocSplitAroundLoops 플래그 뒤에 게이트되어 있으며, 기본값은 비활성화 상태입니다.

Before split:
  [pre-loop] ──► [loop header] ──────────────── [loop body] ──► [post-loop]
  tmp0 live ──────────────────────────────────────────────────► tmp0 live
              (register held across entire loop even if unused inside)

After split (with CFG normalization + fixup):
  [pre-loop] ──► [entry fixup] ──► [loop header] ──► [loop body] ──► [exit fixup] ──► [post-loop]
  tmp0 reg  ──►  Shuffle(tmp0→spill)  spill live      spill live    Shuffle(spill→tmp0)  tmp0 reg
                 (physical register freed inside loop body for other tmps)

Significance

CFG 변환, live range 재작성, parallel-move fixup 코드 생성까지 아우르는 새로운 JIT 인프라가, splitting 정책과 priority 기반 할당 순서와의 통합이 명시적으로 미완성인 상태로 반영되었습니다. commit 스스로 이 사실을 밝히고 있는데, 하필 이런 영역이야말로 미묘한 miscompilation을 가장 찾아내기 어려운 지점입니다.

Audit directions

루프 경계에서의 Shuffle cycle 해소: 같은 루프 주변에서 여러 tmp가 함께 split되면, 진입/탈출 fixup들이 parallel Shuffle 명령을 내보내면서 레지스터 cycle을 처리해야 하는 상황이 생깁니다. 예를 들면 tmp0과 tmp1이 서로 물리 레지스터를 맞바꾸는 경우입니다. Cycle 해소는 원래 다루기 까다로운 영역으로 알려져 있고, 버그가 나더라도 crash가 아니라 JIT 출력 결과의 조용한 값 손상으로 이어집니다. Air 안의 parallel move를 내보내는 다른 모든 emitter도 동일한 위험 프로파일을 안고 있습니다.

CFG normalization의 edge case: ensureDedicatedLoopEntryExitBlocks는 루프 진입/탈출 지점에 새로운 basic block을 삽입합니다. 문제가 될 수 있는 형태로는 back-edge가 여러 개인 루프, irreducible loop, header block이 유일한 exit이기도 한 루프, 그리고 OSR entry/exit와의 상호작용이 꼽힙니다. Normalization 이후 CFG가 잘못된 형태가 되면 조용히 miscompile되거나 exploit 가능한 JIT artifact가 만들어질 가능성이 있습니다.

미완성된 allocation ordering: commit 자체가 splitting 정책의 개선과, allocator의 priority 기반 할당 순서와의 통합이 아직 필요하다고 명시하고 있습니다. 이 gap이 남아있다는 것은, 조작된 입력 하에서 allocator가 split-range의 전제와 충돌하는 순서로 할당 결정을 내릴 수 있다는 의미입니다.

Split tmp의 use/def rewrite 정확성: rewriteCoalescedTmps와 addSplitTmp는 원래 tmp의 모든 use/def 지점을 올바른 sub-range를 참조하도록 갱신해야 합니다. 특히 liveness 분석이 경계로 취급하는 def 지점에서 rewrite가 하나라도 누락되면, 레지스터 배정이 조용히 손상됩니다.

trySplitAroundClobbers와의 상호작용: 이 함수는 call clobber 지점을 기준으로 split을 수행합니다. clobber-splitting과 loop-splitting이 같은 tmp에 동시에 적용되는 경우, 어느 split이 우선하는지 그리고 각각의 fixup block이 어떤 순서로 배치되는지가 잠재적인 충돌 지점입니다. 서로 독립적인 두 변환이 같은 live range를 두고 경합하는 이 패턴 자체는, 두 번째 splitting 휴리스틱이 추가되는 곳이라면 어디든 점검해볼 가치가 있습니다.