SIMD 최적화 · baby steps

현재 Firefox에 제안된 JavaScript SIMD API를 구현하려는 진행 중인 노력이 있습니다. API의 기본 아이디어는 float32x4와 int32x4라는 명시적 벡터 값 타입을 도입하는 것입니다. 이 타입들은 Typed Objects 계층에 들어맞으므로, 이들로 배열을 만들고, 구조체에 내장하고, 기타 다양한 방식으로 사용할 수 있습니다.

이 벡터 타입의 의미론은 JIT 엔진이 그 사용을 감지하고 최적화할 수 있도록 설계되었습니다. 중요한 점은 이들이 값(value)이라는 점이며, 따라서 정체성(identity)이 없습니다. 기본적으로 float32x4 값은 현재의 숫자나 문자열처럼 동작합니다. 즉 같은 값을 가지면 동등합니다. 이는 객체와는 상당히 다릅니다. 객체는 프로퍼티가 같아도 서로 다를 수 있습니다(예: {} !== {}).

이 글의 목적은 IonMonkey에서 SIMD 타입 사용을 최적화하는 하나의 가능한 전략을 개괄하는 것입니다. 초기 최적화 집합은 새로운 분석을 전혀 필요로 하지 않지만, 선택적으로 간단한 분석을 추가해 더 많은 프로그램을 최적화할 수 있습니다. 이 분석은 상당히 일반적이며 다른 종류의 Typed Objects에도 적용할 수 있습니다.

예제

여기 최적화 대상 예제 함수가 있습니다. addArrays()는 입력으로 두 개의 float32x4 값 배열을 받아, 각 원소를 쌍별로 더한 뒤 새로운 배열을 반환합니다.

function addArrays(a, b) { // a와 b는 ArrayType(float32x4)의 인스턴스
    var c = new Float32x4Array(a.length);
    for (var i = 0; i < a.length; i++) {
        c[i] = SIMD.float32x4.add(a[i], b[i]);
    }
    return c;
}

우리가 원하는 것은 CPU가 제공하는 SIMD 연산을 사용하는 최적화된 어셈블리를 내보내는 것입니다.

전략

기본 전략은 모든 Typed Objects에 대해 사용하는 기존 최적화와 유사합니다. 그 경우의 요령은, 처음에는 박싱(boxing) 연산을 모두 포함한 완전한 IR을 생성한다는 점입니다. 그러나 가능한 한 박싱된 값을 실제로 사용하지 않고, 박싱 입력을 끄집어내 직접 사용하는 방식을 취합니다. 비슷한 로직이 현재 파생(derived) 임시 값을 최적화하기 위해 loadTypedObjectElements()에 구현되어 있습니다.

줄 단위로

예제를 보며 더 자세히 설명하겠습니다. 두 벡터를 더하는 루프 본문을 보세요:

c[i] = SIMD.float32x4.add(a[i], b[i]);

논의를 쉽게 하기 위해 임시 변수를 도입하겠습니다:

var tmp0 = a[i];
var tmp1 = b[i];
var tmp2 = SIMD.float32x4.add(tmp0, tmp1);
c[i] = tmp2;

처음 두 임시 변수를 처리할 때 다음과 같은 MIR(mid-level IR)을 생성합니다:

var elem0 = MTypedObjectElements(a);  // (1)
var i0 = MBoundsCheck(i, ...);        // (2)
var arg0 = MLoadVector(elem0, i0);    // (3)
var tmp0 = MVectorTypedObject(arg0);  // (4)

var elem1 = MElements(b);
var i1 = MBoundsCheck(i, ...);
var arg1 = MLoadVector(elem1, i1);
var tmp1 = MVectorTypedObject(arg1);

명령 (1)은 Typed Object의 "elements"를 로드합니다. 이는 본질적으로 a 객체의 원시 이진 데이터에 대한 포인터입니다. a가 float32x4 값의 배열이므로, elem0은 단지 float 배열입니다. 명령 (2)는 i가 배열의 경계를 벗어나지 않는지 검사합니다. 명령 (3)에서 arg0의 로드는 주어진 오프셋에서 elem0로부터 벡터 데이터를 추출합니다. 이는 가능하면 CPU가 제공하는 벡터 로드 명령으로 변환됩니다. 마지막으로 명령 (4)에서, 로드한 벡터들을 새 Typed Object tmp0로 포장합니다. 이는 박싱 연산이며 꽤 비쌉니다. 새 객체를 할당하고 그 안에 벡터 데이터를 복사해야 합니다. 같은 연산 집합이 tmp1에 대해서도 반복됩니다.

흥미로운 부분은 SIMD.float32x4.add(tmp0, tmp1) 호출을 처리할 때 생성되는 것입니다. 두 벡터를 더하려면 언박스된 데이터가 필요합니다. 우리는 tmp0와 tmp1이 박싱된 벡터라는 것을 관찰하고, 이들로부터 추가적인 MLoadVector 명령으로 데이터를 읽어들이는 대신, tmp0와 tmp1을 만들 때 사용한 소스 값 arg0와 arg1을 직접 추출합니다:

var sum2 = MAddVector(arg0, arg1);
var tmp2 = MVectorTypedObject(sum2);

마지막으로 c[i] = tmp2 저장을 처리하며 다음 명령들을 생성합니다:

var elem2 = MElements(c);
var i2 = MBoundsCheck(i, ...);
MStoreVector(elem2, i2, sum2);

여기서도 tmp2에서 데이터를 로드하는 명령을 생성하지 않고, 그 입력 sum2를 바로 사용합니다.

모두 합치기

초기에 우리가 생성하는 전체 IR은 다음과 같습니다:

var elem0 = MElements(a);
var i0 = MBoundsCheck(i, ...);
var arg0 = MLoadVector(elem0, i0 * sizeof(float32x4));
var tmp0 = MVectorTypedObject(arg0);

var elem1 = MElements(b);
var i1 = MBoundsCheck(i, ...);
var arg1 = MLoadVector(elem1, i1 * sizeof(float32x4));
var tmp1 = MVectorTypedObject(arg1);
 
var sum2 = MAddVector(tmp0, tmp1);
var tmp2 = MVectorTypedObject(sum2);

var elem2 = MElements(c);
var i2 = MBoundsCheck(i, ...);
MStoreVector(elem2, i2 * sizeof(float32x4), sum2);

이 코드에서 tmp0, tmp1, tmp2는 모두 데드(dead)입니다(비록 IonBuilder 과정의 일부로 생성해야 하긴 했지만). 또한, 박싱 연산인 MVectorTypedObject는 부작용이 없으므로 필요에 따라 이동시키거나 제거해도 안전하다는 것을 알고 있습니다. 따라서 데드 코드 제거가 수행되면 다음과 같이 단순화됩니다:

var elem0 = MElements(a);
var elem1 = MElements(b);
var arg0 = MLoadVector(elem0, i * sizeof(float32x4));
var arg1 = MLoadVector(elem1, i * sizeof(float32x4));
var sum2 = MAddVector(arg0, arg1);
var elem2 = MElements(c);
MStoreVector(elem2, i * sizeof(float32x4), sum2);

루프 불변 코드 이동(loop-invariant code motion)은 이어서 MElements 호출을 루프 밖으로 끌어올릴 것입니다(경계 검사 등도 가능하지만 여기서는 생략합니다). 따라서 최적화 후 전체 루틴은 다음과 비슷하게 보일 것입니다:

var elem0 = MElements(a);
var elem1 = MElements(b);
var elem2 = MElements(c);
for (...) {
    var i0 = MBoundsCheck(i, ...);
    var i1 = MBoundsCheck(i, ...);
    var i2 = MBoundsCheck(i, ...);
    var arg0 = MLoadVector(elem0, i * sizeof(float32x4));
    var arg1 = MLoadVector(elem1, i * sizeof(float32x4));
    var sum0 = MAddVector(arg0, arg1);
    MStoreVector(elem2, i * sizeof(float32x4), sum0);
}

한계와 개선점

이 전략에는 몇 가지 한계가 있습니다. 예를 들어, 조건부 코드에서는 동작하지 않습니다. 즉, 루프 본문을 조건식으로 수정하면 곤란해집니다:

c[i] = SIMD.float32x4.add((cond ? a[i] : b[i]), b[i]);

여기서 첫 번째 입력은 "phi" 노드가 되며, 따라서 이를 MVectorTypedObject 명령으로 확정적으로 추적할 수 없습니다. 이는 임시값에서 읽어들이는 언박싱 명령을 생성하게 되어, 추가적인 MLoadVector와 라이브 임시값을 도입하게 됩니다. 이 점은 두 번째 패스로 IR을 순회하며 모든 입력이 박싱된 임시이고 출력도 박싱인 phi 노드를 감지해 쉽게 최적화할 수 있습니다. 그런 다음 phi 노드를 변환할 수 있습니다.

또 다른 한계는 박싱된 임시값이 여전히 bailouts를 위한 스택 상태를 인코딩하는 "resumepoint" 명령에 나타난다는 점입니다. 여기서 보여준 단순한 루프의 경우, 특히 경계 검사가 호이스트되면 이들이 최적화되어 사라질 수 있습니다. 하지만 그렇지 않은 경우, 임시값을 언박스된 변형으로 교체하고, 데이터를 다시 박싱하는 방법을 이해하도록 bailout 코드를 수정해야 합니다.

float32 최적화와의 비교

IonMonkey에는 현재 값이 (1) float32에서 기원했고 (2) 다시 float32에 저장될 것임을 감지하면 float64 대신 float32 산술을 사용하는 최적화가 포함되어 있습니다. 이는 위에서 제안한 phi 최적화와 유사합니다. 이 접근 방식과 여기서 제안한 방식의 한 가지 차이점은, float32 최적화는 생산자와 소비자 모두가 float32를 기대할 때에만 수행된다는 점입니다. 반면, 여기서의 접근 방식은 소비자 중 하나라도 언박스된 데이터를 원한다면, 그 소비자는 스스로 박스를 우회할 수 있다고 봅니다. 모든 소비자가 박스를 우회한다면, 그 박스는 데드 코드로 수집되지만, 일부 소비자가 남아 있으면 박스는 라이브로 유지됩니다. 따라서 여기서 설명한 최적화가 더 공격적입니다. 이 접근은 float32에 대해서는 불가능합니다. 왜냐하면 명세상 float64 덧셈을 float32 산술로 수행하려 하며, 그 결과가 항상 float32로 강제 변환될 때에만 합법적이기 때문입니다. 하지만 이 시나리오는 SIMD.float32x4.add()에는 적용되지 않습니다.

필요한 변경 사항

다음은 이를 구현하기 위해 필요한(프런트엔드) 변경 사항 요약입니다.

1. MIRType_float32x4와 MIRType_int32x4 추가

2. 다음 MIR 명령 추가:

   • MPackVector(v1, v2, v3, v4) -> {MIRType_float32x4, MIRType_int32x4}
   • MLoadVector(elements, offset) -> {MIRType_float32x4, MIRType_int32x4}
   • MStoreVector(elements, offset, value) 여기서 value : {MIRType_float32x4, MIRType_int32x4}
   • MAddVector(value1, value2) 여기서 value1, value2 : {MIRType_float32x4, MIRType_int32x4}
   • MVectorTypedObject(value) -> MIRType_object (MDerivedTypeObject와 유사)

3. 다음의 경우 SIMD.float32x4.add 호출을 특별히 인라인 처리:

   • 두 피연산자가 타입 T의 Typed Object이고, T는 float32x4 또는 int32x4 중 하나
   • 그 경우 각 인수에 대해 MLoadVector를 삽입(간접 참조를 건너뛰는 기존 코드를 모델로 사용 – MDerivedTypeObject와 MVectorTypedObject를 감지하고 단축)
   • 언박스된 피연산자로 MAddVector 삽입
   • 결과를 박싱하기 위해 MVectorTypedObject 삽입

4. 타입이 float32x4인 Typed Object 값을 로드하는 코드를 MLoadVector와 MVectorTypedObject를 수행하도록 수정

5. 타입이 float32x4인 Typed Object lvalue에 저장할 때, 저장하려는 값이 MVectorTypedObject인 경우 중간 단계를 피하도록 최적화

6. 적절한 LIR 명령 추가 및 레지스터 할당기 등 수정