Low-Level Virtual Machine

Low-Level Virtual Machine (LLVM)

LLVM은 소스 코드를 최적화하고 대상 플랫폼에 맞는 기계어로 변환하는 모듈식 컴파일러 프레임워크이다.
원래 “Low-Level Virtual Machine"의 약자에서 출발했으나, 현재는 그 이름 그대로 하나의 독립적인 프로젝트가 되어 다양한 언어와 플랫폼을 지원하고 있다.
LLVM은 소스 코드 → 중간 표현(IR) 변환부터, 여러 단계의 최적화, 그리고 최종 기계어 코드 생성을 위한 백엔드로 구성되며, 컴파일 타임, 링크 타임, 런타임, 심지어 유휴 시간까지 전반에 걸친 지속적 최적화(Lifelong Optimization) 를 지원한다.

LLVM의 핵심 아이디어는 컴파일러를 모듈화하여 프론트엔드(언어 파싱), 중간표현(IR) 최적화, 백엔드(코드 생성) 단계를 독립적으로 개발하고 재사용할 수 있게 만든 것으로, 컴파일러 개발의 유연성과 효율성을 크게 향상시켰다.

LLVM의 정의 및 주요 특징

• 언어 및 플랫폼 독립성:
  LLVM은 언어에 구애받지 않고 여러 프로그래밍 언어로부터 IR을 생성할 수 있으며, 다양한 하드웨어 아키텍처(예: x86, ARM, RISC-V 등)에 대해 백엔드를 제공하여 플랫폼 독립적인 최적화를 수행한다.
• 중간 표현(Intermediate Representation, IR):
  LLVM은 SSA(Static Single Assignment) 형태의 IR을 사용한다. 이 방식은 각 변수에 한 번만 값을 할당하여 데이터 종속성 분석과 최적화를 단순화하며, 컴파일의 여러 단계에서 동일한 IR이 재사용될 수 있도록 한다.
• 모듈식 설계:
  LLVM은 프론트엔드, 최적화 라이브러리, 백엔드 등 여러 개별 모듈로 구성되어 있다. 이 구조 덕분에 각 구성 요소를 독립적으로 개선하거나 교체할 수 있으며, 새로운 언어나 플랫폼에 대한 확장이 용이하다.
• 지속적 최적화:
  컴파일 시점뿐만 아니라 링크 타임, 런타임, 그리고 프로그램의 유휴 시간에도 최적화 및 분석을 수행할 수 있어 실행 파일의 성능을 극대화할 수 있다.
• 유연한 타입 시스템 및 주소 산술 지원:
  LLVM은 단순하고 언어 독립적인 타입 시스템을 갖추고 있으며, 정밀한 메모리 주소 조작을 위한 Typed Address Arithmetic 명령어를 제공하여 안전하고 효율적인 메모리 접근을 보장한다.

SSA(Static Single Assignment)

SSA의 정의

• SSA는 각 변수가 정확히 한 번만 할당되는 중간 표현 형식이다.
• 변수에 새 값을 할당할 때마다 새로운 버전의 변수가 생성된다.

SSA의 특징

• 모든 LLVM 명령어는 SSA 형식으로 표현된다.
• 변수는 한 번만 할당될 수 있어, 최적화와 분석이 용이해진다.
• 제어 흐름에 따라 변수 값이 달라질 수 있는 경우, PHI(Φ) 노드를 사용한다.

SSA의 장점

• 최적화 분석이 더 쉬워진다. 변수 사용 시 값이 할당된 곳이 단 한 곳이기 때문이다.
• 대부분의 최적화 기법이 SSA 형식을 유지할 수 있어, 연속적인 최적화 수행이 가능하다.
• SSA 기반 최적화는 일반적으로 더 효율적이고 강력하다.

LLVM에서의 SSA 활용

• LLVM은 모든 스칼라 레지스터 값에 대해 SSA 형식을 사용한다.
• 레지스터 할당이 이루어지는 컴파일 과정 후반부까지 SSA 형식이 유지된다.

LLVM 사용의 이점

1. 모듈성: 프론트엔드, 중간층, 백엔드의 분리로 개발과 유지보수 용이
2. 재사용성: 새로운 언어 또는 타겟 추가 시 전체 파이프라인 재개발 필요 없음
3. 확장성: 커스텀 패스와 플러그인을 통한 기능 확장 가능
4. 호환성: 다양한 플랫폼과 아키텍처 지원
5. 최적화: 강력한 최적화 기능으로 고성능 코드 생성
6. 다양한 언어 지원 → Rust, Swift, Kotlin, Julia 등 현대적 언어에 사용

LLVM의 한계와 도전 과제

1. 복잡성: 완전한 LLVM 스택은 학습 곡선이 가파름
2. 디버깅 난이도: 최적화된 코드의 디버깅이 어려울 수 있음
3. 리소스 요구사항: 메모리와 CPU 사용량이 많을 수 있음
4. 특정 언어 최적화: 일부 언어별 최적화는 일반적인 IR에서 표현하기 어려움
5. GCC에 비해 성숙도가 낮음 → 일부 플랫폼에서는 GCC가 더 안정적
6. 컴파일러가 너무 세분화됨 → 여러 도구(Clang, LLD, LLDB 등)를 조합해야 함

LLVM의 주요 컴포넌트

1. LLVM 코어
   LLVM의 핵심 부분으로, 중간표현(IR)과 이를 위한 최적화 패스를 포함한다.
   LLVM IR은 정적 단일 할당(SSA) 형식을 사용하며, 다양한 소스 언어와 하드웨어 플랫폼을 연결하는 중간 단계 역할을 한다.

2. Clang
   C, C++, Objective-C를 위한 LLVM 프론트엔드로, 소스 코드를 분석하고 LLVM IR로 변환한다.
   GCC보다 빠른 컴파일 속도와 더 명확한 오류 메시지로 널리 사용된다.

3. 컴파일러-RT
   컴파일 시간과 런타임에 필요한 저수준 지원 라이브러리이다. 예를 들어 sanitizer들과 프로파일링 기능을 제공한다.

4. LLDB
   LLVM 기반 디버거로, Clang과 통합되어 C, C++, Objective-C 프로그램의 디버깅을 지원한다.

5. lld
   LLVM의 링커로, 여러 객체 파일과 라이브러리를 최종 실행 파일로 결합한다.

LLVM의 동작 방식

LLVM 컴파일 파이프라인은 다음과 같은 단계로 진행된다:

1. 소스 코드 파싱: 프론트엔드(예: Clang, Swift 컴파일러 등)가 소스 코드를 파싱하여 추상 구문 트리(AST)를 생성한다.
2. LLVM IR 생성: AST가 LLVM IR로 변환된다.
3. 최적화: LLVM 옵티마이저가 IR에 다양한 최적화 패스를 적용한다.
   불필요한 연산 제거, 루프 최적화, 메모리 접근 최적화 등이 포함된다.
4. 코드 생성: 백엔드가 최적화된 IR을 타겟 머신 코드로 변환한다.
5. 링킹: 여러 객체 파일과 라이브러리가 최종 실행 파일로 링크된다.

LLVM의 중간표현(IR)

• LLVM IR은 세 가지 동등한 형태로 존재한다.
  • 메모리 내 표현 (컴파일러 내부 사용)
  • 비트코드 (.bc 파일, 직렬화된 이진 형식)
  • 텍스트 형식 (.ll 파일, 사람이 읽을 수 있는 어셈블리와 유사)
• LLVM IR의 주요 특징:
  • 정적 단일 할당(SSA) 형식
  • 타입 시스템 내장
  • 명시적인 제어 흐름 그래프
  • 하드웨어에 독립적인 명령어 세트

LLVM은 다양한 최적화 패스를 제공한다:

1. 인라인화: 함수 호출을 함수 본문으로 대체
2. 상수 폴딩: 컴파일 시간에 계산할 수 있는 표현식 평가
3. 루프 최적화: 루프 언롤링, 벡터화, 루프 불변 코드 이동 등
4. 명령어 스케줄링: CPU 파이프라인을 최적으로 사용
5. 데드 코드 제거: 도달할 수 없거나 사용되지 않는 코드 제거
6. 전역 값 번호 매기기(GVN): 중복 계산 제거

백엔드와 코드 생성
LLVM 백엔드는 다양한 하드웨어 아키텍처에 대한 코드 생성을 담당한다: - x86, x86-64 - ARM, AArch64 - MIPS, PowerPC - WebAssembly - RISC-V 등

백엔드 프로세스:

1. 명령어 선택: IR 명령을 타겟 머신 명령으로 매핑
2. 레지스터 할당: 변수를 물리적 레지스터에 할당
3. 명령어 스케줄링: 하드웨어 특성을 고려한 최적 명령어 순서 결정
4. 프레임 관리: 스택 프레임 레이아웃 결정

LLVM vs. 기존 컴파일러 비교

LLVM은 기존의 전통적인 컴파일러와 비교할 때 더 많은 유연성과 확장성을 제공한다.

LLVM의 활용 분야

LLVM의 실용적 응용

1. 정적 분석 도구: Clang Static Analyzer와 같은 도구는 LLVM/Clang 인프라를 사용하여 코드의 버그와 취약점을 찾는다.
2. Just-In-Time(JIT) 컴파일: LLVM의 JIT 컴파일 기능은 런타임에 코드를 생성하고 실행할 수 있게 해준다. 이는 성능 중심 애플리케이션과 동적 언어 구현에 유용하다.
3. 크로스 컴파일: LLVM의 모듈식 설계는 다양한 플랫폼을 위한 크로스 컴파일을 단순화한다.
4. 하드웨어 가속기 타겟팅: LLVM은 GPU나 FPGA와 같은 특수 하드웨어를 위한 코드 생성을 지원한다.

LLVM 기반 언어 및 프로젝트

LLVM은 여러 언어 및 프로젝트에서 핵심 기술로 사용된다.

LLVM은 단순한 컴파일러가 아니라, 다양한 프로그래밍 언어와 하드웨어를 지원하는 강력한 프레임워크로 발전 중이다.

참고 및 출처