정적 분석은 프로그램의 타입을 추적하는 핵심적인 방법입니다. a = 1 이후 a = "hello"와 같이 변수의 타입이 변경되는 상황을 처리하기 위해 ‘정적 단일 할당(SSA: Static Single Assignment)’ 형식이 도입됩니다. SSA는 모든 변수가 단일하고 불변하는 타입을 갖도록 프로그램을 재구성하여 분석의 복잡성을 줄입니다. 예를 들어, a0 = 1, a1 = "hello"와 같이 변수 이름을 달리하여 각 할당 시점의 타입을 명확히 구분합니다.
타입 분석 시 발생할 수 있는 무한한 값의 집합 문제를 해결하기 위해 ‘유한 높이 래티스(finite-height lattice)’ 개념이 활용됩니다. 이는 정밀도와 분석 시간 사이의 균형을 맞추기 위해 타입 정보를 제한된 수준으로 추상화하는 방식입니다. 예를 들어, Integer[3]과 Integer[4]가 병합될 경우, 이들은 Integer라는 더 일반적인 타입으로 추상화되어 메모리 사용량과 분석 시간을 효율적으로 관리합니다.
‘희소 조건부 상수 전파(SCCP: Sparse Conditional Constant Propagation)’는 제어 흐름 그래프(CFG)를 탐색할 때 타입 정보를 활용하여 도달 불가능한 분기(예: if true인 경우 else 브랜치)를 분석에서 제외함으로써 분석의 정밀도를 높이는 기법입니다. 본문에서는 이 SCCP를 확장하여 상수뿐만 아니라 전체 타입 래티스를 사용하고, 이를 함수 간(interprocedural)으로 적용하는 방법을 설명합니다.
프로시저 간 SCCP는 함수 호출 관계가 정적으로 알려지지 않은 경우에도 효과적으로 작동합니다. 분석 과정에서 함수 호출 에지를 점진적으로 구축하고, 여러 호출 사이트에서 전달되는 인자들의 타입을 병합(union)하여 함수의 파라미터 타입을 결정합니다. 이는 단일 함수 분석으로는 얻을 수 없는 정밀한 정보를 제공합니다.
‘민감도(Sensitivity)’는 분석의 정밀도를 높이는 또 다른 중요한 개념입니다. 특히 ‘호출 사이트 민감도(Call-site sensitivity)’는 각 호출 사이트를 독립적인 컨텍스트로 분석하여, 동일한 함수라도 호출 인자에 따라 다른 타입 정보를 얻을 수 있게 합니다. 이는 to_s나 each와 같이 다양한 타입의 인자를 받을 수 있는 라이브러리 함수에 특히 유용합니다. 또한, Ruby와 같은 객체 지향 언어의 특성을 고려하여 ‘필드 민감(field-sensitive)’ 방식을 통해 객체의 인스턴스 변수 타입(p.x의 타입)까지 정밀하게 추적합니다. 이는 SetIvar와 GetIvar 명령 간의 복잡한 의존 관계를 관리하는 것을 포함합니다.
이러한 복잡한 분석 기법의 실제 성능을 평가하기 위해, 대규모 실제 프로그램의 벤치마크가 부족한 문제를 해결하고자 ‘고문 테스트(torture tests)’를 고안했습니다. 이는 인위적으로 대규모의 호출 그래프와 다형적/메가모픽(polymorphic/megamorphic) 호출 사이트를 포함하는 프로그램을 생성하여 분석 기법의 확장성과 효율성을 극한으로 시험합니다. 테스트 결과, 클래스가 없는 20만 함수 프로그램은 1.3초, 클래스가 포함된 17.5만 함수(약 3백만 명령어, 최대 144개 클래스 메가모픽) 프로그램은 2.5초 만에 단일 코어에서 분석이 완료되었습니다. 이는 예상보다 훨씬 빠른 결과로, 본 분석 기법이 대규모 실제 소프트웨어에도 충분히 적용 가능성이 있음을 시사합니다.