동적 타입 시스템을 가진 Ruby와 같은 언어는 컴파일러 최적화를 위한 정밀한 정적 타입 분석에 어려움이 있습니다. 상속, `T.unsafe`, `T.untyped`와 같은 기능은 타입 시스템의 정확성을 저해합니다. 따라서 컴파일러는 자체적으로 정밀한 타입 정보를 추적해야 할 필요가 있습니다. 본 글은 이러한 문제를 해결하기 위해, Ruby의 서브셋에 적용 가능한 절차 간 희소 조건부 타입 전파(Interprocedural Sparse Conditional Type Propagation, ISCTP)라는 정적 타입 분석 기법을 소개하고 그 가능성을 탐구합니다. 이는 기존의 타입 추론 엔진과 달리 함수 간 데이터 흐름을 추적하며, 프로그램 최적화에 활용될 수 있습니다.
ISCTP 분석은 먼저 프로그램을 정적 단일 할당(SSA) 형태로 변환하여 각 변수가 단 하나의 타입을 갖도록 단순화합니다. 타입 정보는 유한 높이 격자(finite-height lattice)를 사용하여 표현하며, 이는 타입 집합의 크기가 무한히 커지는 것을 방지하고 분석 시간을 합리적으로 유지합니다. 예를 들어, 두 개 이상의 다른 정수 상수가 합쳐지면 더 이상 특정 상수가 아닌 Integer 타입으로 추상화됩니다.
분석의 핵심은 희소 조건부 상수 전파(Sparse Conditional Constant Propagation, SCCP) 기법을 확장한 것입니다. 기존 SCCP는 상수를 기반으로 도달 불가능한 코드 경로를 식별하고 분석에서 제외함으로써 정밀도를 높입니다. ISCTP는 이를 타입 격자 전체로 확장하여, 조건문의 분기 조건 타입을 분석하여 실행될 가능성이 없는 분기를 분석 대상에서 제외합니다. 이는 특히 if true와 같이 분석 시점에 조건이 알려진 경우 유용합니다.
이 기법을 절차 간(interprocedural)으로 확장하기 위해, 분석은 애플리케이션의 진입점부터 시작하여 함수 호출 관계를 동적으로 탐색하고 호출 그래프를 구축합니다. 함수 호출 시, 실제 인수의 타입 정보는 피호출 함수의 매개변수로 전파되며, 여러 호출 사이트에서 동일한 매개변수로 데이터가 흐를 경우 타입 격자의 합집합 연산을 통해 병합됩니다. 함수의 반환 타입 또한 마찬가지로 호출 사이트로 역전파됩니다. 이를 통해 함수 내부의 분석이 호출 맥락에 따라 더 정밀해질 수 있습니다.
분석의 정밀도를 높이는 방법으로는 민감도(sensitivity) 개념이 있습니다. 특히 호출 사이트 민감도(call-site sensitivity)는 각 호출 사이트를 분리하여 분석함으로써, 동일한 함수라도 다른 인수로 호출될 경우 각각 독립적인 타입 정보를 유지하게 합니다. 이는 오버헤드를 증가시키지만, to_s와 같이 다형적인(polymorphic) 또는 메가모픽(megamorphic) 함수 호출의 분석 정밀도를 크게 향상시킬 수 있습니다. 본 분석은 1-call-site-sensitivity를 고려하며, 객체 시스템 처리를 위해 필드 민감도(field-sensitive) 접근 방식을 채택하여 각 클래스의 인스턴스 변수(ivar) 타입을 개별적으로 추적합니다.
분석의 확장성을 검증하기 위해 대규모 합성 테스트 프로그램을 생성했습니다. 하나는 20만 개의 함수로 구성된 큰 호출 DAG이며, 다른 하나는 5000개의 클래스와 수십만 개의 함수, 그리고 최대 144개의 클래스를 처리하는 메가모픽 호출을 포함하는 테스트입니다. 이러한 ‘고문 테스트(torture tests)’를 통해 분석 성능을 측정했습니다.
합성 테스트 결과는 고무적입니다. 클래스가 없는 20만 함수 프로그램은 단일 코어에서 1.3초, 클래스와 메가모픽 호출을 포함하는 17.5만 함수 프로그램은 2.5초 내에 분석이 완료되었습니다. 이는 예상보다 훨씬 빠른 성능이며, 분석이 수십만 메서드를 포함하는 대규모 실제 Ruby 프로그램에도 충분히 적용 가능함을 보여줍니다. 객체 민감도나 더 높은 k값의 호출 사이트 민감도를 적용하면 정밀도는 더욱 향상되겠지만 분석 시간이 증가할 수 있습니다. 하지만 분석의 기본 속도가 빠르기 때문에, 특정 핵심 라이브러리 메서드에 선택적으로 민감도를 적용하는 방식이 효과적일 수 있습니다. 본 분석 코드는 실험적인 프로토타입으로 공개되었으며, 프로그램 분석 분야에 대한 더 깊은 탐구를 위한 참고 자료로 활용될 수 있습니다.