[JSC] Inline small sorting in DFG / FTL

Component: JSC | cab7a45

JSC의 tier 구조는 LLInt(bytecode interpreter) → DFG(speculative JIT) → FTL(B3 기반 top tier) 순으로 동작합니다. DFG는 array element type을 speculative하게 가정하고 guard를 삽입하는데, guard가 실패하면 OSR exit를 통해 interpreter로 deoptimize됩니다. 기존에는 Array.prototype.sort가 JIT 바깥에서 C++ runtime sort를 그대로 호출하는 방식이었습니다.

JSTests/stress/array-sort-inline-boolean-comparator.js

+// Before the fix the intrinsic did only `cmp < 0`, which gave false for boolean
+// `false` (since 0 < 0 is false), so a `() => false` comparator was a no-op and
+// the legacy `(a, b) => a > b` pattern never sorted. The fix routes `cmp === false`
+// through an extra branch that also goes to the shift target.
+
+function sortIt(a, c) { return a.sort(c); }
+
+// Warm up with Int32 comparator so DFG inlines the intrinsic on the hot path.
+for (let i = 0; i < testLoopCount; ++i)
+    sortIt([5, 3, 1, 4, 2], (a, b) => a - b);
+
+const cmp = (a, b) => {
+    if ((a ^ b) & 1) return a > b;  // boolean path
+    return a - b;                   // int32 path
+};

이제 Contiguous/Int32/Undecided array 중 원소 개수가 16개 이하인 경우, sort가 inline으로 emit되며 16개짜리 scratch buffer를 대상으로 insertion sort를 수행합니다. 이를 담당하는 새로운 DFG node가 두 개 추가되었습니다. ArraySortCompact는 element를 추출해 scratch로 정규화하는데, hole이 있거나 Double array이거나 크기가 초과되는 경우에는 slow path로 넘어갑니다. ArraySortCommit은 정렬이 끝난 scratch를 다시 써넣는 역할을 합니다. 까다로운 부분은 OSR exit입니다. User comparator 내부에서 speculation이 실패하면 JIT는 임의의 sort iteration 지점에서 재개할 수 없기 때문에, 새로 추가된 LLInt trampoline(array_sort_comparator_return_trampoline)이 return PC를 조정하고 op_call(sort) 전체를 slow path로 다시 시작하도록 만듭니다. Comparator의 호출 순서는 spec상 명시되어 있지 않으므로, 이런 재시작 방식도 spec을 위반하지 않습니다.

Normal path:
  array.sort(cmp)
       │
  ┌────▼────────────────────┐
  │   ArraySortCompact       │  type-check; copy ≤16 elems to scratch
  │                          │──► slow-path call if: >16, Double, or holey
  └────┬────────────────────┘
       │ scratch[16]
  ┌────▼────────────────────┐
  │  Inline insertion sort   │
  │    inlined cmp() call    │◄─── user JS runs here, can mutate array
  └────┬────────────────────┘
       │ sorted scratch
  ┌────▼────────────────────┐
  │   ArraySortCommit        │  write sorted scratch → original array
  └─────────────────────────┘

OSR-exit path (speculation failure inside inlined cmp()):
  cmp() executes in JIT
       │ guard fails
  array_sort_comparator_return_trampoline  (new LLInt thunk)
       │ adjust return PC
  restart op_call(Array.prototype.sort)    (entire sort, slow path)
       │
  slow-path sort runs on array that cmp() may have already mutated

Significance

최근 JavaScriptCore에 추가된 speculative JIT 코드 경로 중 가장 규모가 큰 축에 속합니다. 새로운 DFG node, 새로운 LLInt trampoline, 새로운 type-speculation guard, 그리고 comparator inlining이 한꺼번에 맞물려 동작합니다. Security 관점에서 중요한 구조적 사실은, 임의의 user JS인 comparator가 JIT가 제어하는 두 메모리 연산 — ArraySortCompact와 ArraySortCommit — 사이에서 실행된다는 점입니다.

Audit directions

좁은 범위부터 보면, compact와 commit 사이에서 발생하는 comparator side effect가 핵심입니다. Comparator는 array를 키우거나 줄일 수 있고, structure를 전환시킬 수 있으며(Contiguous → Dictionary), GC를 유발하거나 element를 직접 쓸 수도 있습니다. 이후 ArraySortCommit은 원본 indexed storage를 scratch 내용으로 덮어씁니다. Commit 단계에서 butterfly와 structure가 compact 이후 변경되지 않았는지 재검증하는지를 확인할 필요가 있습니다. 이런 종류의 JIT diff에서 흔히 나타나는 신호는, snapshot node와 writeback node 사이에 user code로 진입 가능한 call이 끼어 있는 패턴입니다.

범위를 넓혀 보면, 부분적으로 mutation이 일어난 이후 OSR-exit state를 살펴봐야 합니다. Comparator 내부에서 exit가 발생하면 trampoline이 op_call부터 다시 시작하는데, 이 시점에 comparator는 이미 여러 번 실행되어 array를 변경했을 수 있습니다. 이후 slow-path sort는 이렇게 변경된 array를 대상으로 동작하게 됩니다. Scratch buffer의 lifetime, 그리고 exit 이전에 scratch의 일부가 이미 다시 쓰였는지 여부를 구체적으로 확인해야 하는 지점입니다. 이 문제는 resume 대신 restart 방식을 쓰는 모든 JIT 연산에 동일하게 적용됩니다. Restart-on-exit 방식을 사용하는 다른 intrinsic들에서도, 중단된 시도가 이미 commit해버린 부분이 무엇인지 같은 질문으로 점검할 필요가 있습니다.

함께 점검할 만한 부분으로 boolean-comparator dispatch가 있습니다. Test 파일에는 초기 구현이 boolean false를 shift signal이 아닌 0으로 처리했다는 점이 문서화되어 있고, fix에서는 이를 위해 CompareStrictEq branch가 추가되었습니다. NaN, valueOf를 가진 object, boxed double 같은 다른 comparator 반환 타입은 서로 다른 branch를 타게 되는데, 이 중 동일한 방식으로 잘못 처리되는 경우가 있는지 확인이 필요합니다. 별도로, sort-comparator context를 위해 새로 추가된 InlineCallFrame call mode는 call stack을 재구성하는 모든 지점(debugger, Error.stack, structured stack trace)에서 처리되어야 합니다. 누락된 case가 있으면 잘못된 출력이 나오거나, 해당 mode가 dispatch에 쓰이는 경우라면 잘못된 동작으로 이어질 수 있습니다.