DFG/FTL ArrayUnshift intrinsic

5965900

JSTests/stress/array-unshift-intrinsic-ftl.js

+(function () {
+    function unshiftDouble(a, v) { return a.unshift(v); }
+    noInline(unshiftDouble);
+    for (var i = 0; i < testLoopCount; ++i) {
+        var array = [1.5];
+        shouldBe(unshiftDouble(array, 2.5), 2);
+    }
+    var array = [1.5];
+    var r = unshiftDouble(array, NaN);
+    shouldBe(r, 2);
+    shouldBe(array.length, 2);
+    shouldBe(Number.isNaN(array[0]), true);
+    shouldBe(array[1], 1.5);
+})();

JSC는 Baseline → DFG → FTL로 이어지는 계층형 JIT 구조를 사용합니다. 자주 호출되는 내장 함수에 대해 DFG bytecode parser는 "intrinsic"을 인식하고 전용 DFG 노드를 생성합니다. Array.prototype.unshift는 push보다 구조적으로 복잡합니다. 기존 원소 전체를 더 높은 인덱스 방향으로 한 칸 이상 이동시켜야 하므로, butterfly storage에 대한 memmove가 수반됩니다. Contiguous 배열(GC가 관리하는 JSValue를 저장하는 배열)의 경우, 이동하는 원소 하나하나에 write barrier가 필요합니다.

이 commit은 Array.prototype.unshift를 DFG 및 FTL의 first-class intrinsic으로 구현했습니다. Int32, Double, Contiguous 세 가지 storage 타입에 대해 0개 및 1개 인수 처리를 위한 inline fast path를 지원하며, ArrayStorage는 slow path로 처리됩니다. 이 intrinsic은 bytecode parser, fixup, clobberize, abstract interpreter, speculative JIT (64-bit), FTL B3 lowering에 이르는 전 단계에 걸쳐 연결되었습니다.

Significance

메모리 내 기존 원소 전체를 오른쪽으로 이동시키는, 대규모 변형을 수반하는 배열 연산에 대해 JIT 컴파일된 코드 경로가 새로 추가되었습니다. 이 영역은 JIT 컴파일러에서 type confusion과 bounds 오류가 역사적으로 자주 발생해 온 곳입니다.

Audit directions

Inline memmove bounds. 1개 인수를 처리하는 inline path는 JIT가 생성한 코드 안에서 source/destination butterfly offset을 계산하여 기존 원소를 이동시킵니다. memmove 전의 capacity 또는 length 체크에서 off-by-one이 발생하면, butterfly 영역 밖으로의 out-of-bounds write가 발생할 가능성이 있습니다.
Write barrier completeness. Contiguous 배열에서는 이동하는 슬롯 하나하나에 write barrier가 필요합니다. 이동된 슬롯 중 하나라도 barrier 없이 기록되는 경우를 고려해야 합니다. 예를 들어 barrier loop가 [0..length-1]을 커버하면서도 인덱스 0의 새 슬롯에는 barrier를 생성하지 않는 경우입니다. 이때 GC의 remembered set이 일관성을 잃고, 이후 GC 수집 시점에 use-after-free로 이어질 가능성이 있습니다.
Type speculation vs structure transitions. type guard와 실제 butterfly 변형 사이의 window에서, concurrent GC나 중간에 끼어드는 store 연산이 배열의 IndexingType을 변경할 가능성이 있습니다. 예를 들어 hole 삽입을 통해 Contiguous가 ArrayStorage로 전환되는 경우입니다. OSR-exit guard가 이 window를 포함하지 않는다면, Contiguous memmove 로직이 ArrayStorage 레이아웃에 그대로 적용될 수 있습니다.
Multi-element scratch buffer. 인수가 2개 이상인 경우, 원소는 인수 개수를 기반으로 할당된 scratch buffer에 임시 저장됩니다. JIT가 vararg 처리 과정에서 off-by-one으로 buffer 할당 크기를 잘못 계산한다면, scratch 영역 끝을 넘어서는 기록이 발생할 가능성이 있습니다.
Length overflow. 원소 수가 2^32-1에 근접한 배열에서 length 덧셈이 overflow되는 경우를 점검할 필요가 있습니다. type propagation 과정에서 결과가 Int32 범위 내에 들어온다고 JIT가 가정하면, overflow check를 생략할 가능성이 있습니다.