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

899099b

JSTests/stress/regalloc-loop-splitting.js

+//@ requireOptions("--airGreedyRegAllocSplitAroundLoops=true")
+function test(p) {
+    let v0=p+0, v1=p+1, ..., v15=p+15;
+    let sum = 0;
+    for (let i = 0; i < 100; i++)
+        sum = clobber(sum + i);  // call은 caller-saved register를 모두 clobber합니다
+    return v0+v1+...+v15+sum;
+}

B3는 JSC의 optimizing JIT compiler이고, Air는 physical register 할당이 이루어지는 low-level assembly IR입니다. Greedy register allocator는 live range를 우선순위 순서로 처리하며, virtual register(tmp)에 physical register를 할당합니다. 이때 tmp를 할당할 수 없으면 spill하거나 독립적으로 할당 가능한 sub-range로 분리합니다. Loop-aware splitting은 loop 전체 구간에 걸쳐 점유되어 있지만 loop 내부에서는 사용되지 않는 register를 해제하는 기법입니다. Live range를 분리하고 loop entry/exit에 Shuffle 기반 fixup을 삽입하는 방식으로 동작합니다.

이 commit은 JSC의 greedy register allocator에 loop-aware live range splitting을 추가하였습니다. 새로운 CFG normalization pass인 ensureDedicatedLoopEntryExitBlocks는 loop entry/exit edge에 Shuffle 기반 fixup 코드를 안전하게 삽입할 수 있도록 보장합니다. 이 기능은 airGreedyRegAllocSplitAroundLoops 플래그 뒤에 숨겨져 있으며, 기본값은 비활성화입니다. Air의 Shuffle instruction은 cycle(예: A↔B 교환)을 포함한 parallel move를 처리합니다. 다만 commit에서는 splitting policy와 allocator의 우선순위 기반 할당 순서와의 통합이 아직 완전하지 않다고 명시하고 있습니다.

Significance

Loop entry/exit에서 Shuffle 기반 parallel-move fixup은 register cycle을 정확하게 해소해야 합니다. Cycle resolution에 버그가 있으면 crash가 아닌 JIT 출력에서 조용히 값이 오염되는 결과로 이어집니다.

Audit directions

Shuffle cycle resolution at loop boundaries. 동일한 loop를 기준으로 여러 tmp가 분리되어 physical register를 교환하는 경우, parallel Shuffle은 cycle을 정확하게 처리해야 합니다. Cycle resolution은 미묘하기로 악명이 높습니다. 여기서 버그가 발생하면 값이 조용히 오염됩니다.
CFG normalization edge cases. ensureDedicatedLoopEntryExitBlocks는 loop entry와 exit 지점에 새로운 basic block을 삽입합니다. 문제가 될 수 있는 경우로는 여러 개의 back-edge를 가진 loop, irreducible loop, header가 유일한 exit이기도 한 loop, 그리고 OSR entry/exit과의 상호작용이 있습니다.
Acknowledged-incomplete allocation ordering. Commit에서는 splitting policy와 우선순위 기반 할당 순서가 미완성임을 명시하고 있습니다. 악의적인 입력이 있으면 ordering 결정이 split-range 가정과 충돌할 가능성이 있습니다.
rewriteCoalescedTmps and addSplitTmp use/def coverage. 원본 tmp의 모든 use와 def는 올바른 sub-range를 참조하도록 재작성되어야 합니다. Liveness analysis가 경계로 처리하는 def 지점에서 재작성이 누락되면, register 할당이 조용히 오염됩니다.
trySplitAroundClobbers interaction with loop splitting. 동일한 tmp에 clobber-splitting과 loop-splitting이 모두 적용되는 경우, 두 방식의 우선순위와 fixup-block 순서가 충돌의 원인이 될 가능성이 있습니다.