Go 관점에서 본 LLVM

컴파일러를 개발하는 것은 매우 어려운 작업입니다. 그러나 다행스럽게도 LLVM과 같은 프로젝트의 개발로 이 문제에 대한 해결책이 크게 단순화되어 단일 프로그래머라도 성능이 C에 가까운 새로운 언어를 만들 수 있습니다. 시스템은 문서가 거의 없는 엄청난 양의 코드로 표현됩니다. 이러한 단점을 바로잡기 위해 오늘 우리가 번역한 자료의 저자는 Go로 작성된 코드의 예를 보여주고 이것이 처음으로 어떻게 번역되는지 보여줄 것입니다. SSA로 이동, 그리고 컴파일러를 사용하여 LLVM IR에서 타이니고. Go SSA 및 LLVM IR 코드는 설명을 더 이해하기 쉽게 만들기 위해 여기에 제공된 설명과 관련이 없는 항목을 제거하도록 약간 편집되었습니다.

첫 번째 예

여기서 살펴볼 첫 번째 함수는 숫자를 추가하는 간단한 메커니즘입니다.

func myAdd(a, b int) int{
    return a + b
}

이 기능은 매우 간단하며 아마도 이보다 더 간단한 것은 없을 것입니다. 이는 다음 Go SSA 코드로 변환됩니다.

func myAdd(a int, b int) int:
entry:
    t0 = a + b                                                    int
    return t0

이 보기를 사용하면 데이터 유형 힌트가 오른쪽에 배치되며 대부분의 경우 무시할 수 있습니다.

이 작은 예를 통해 이미 SSA의 한 측면의 본질을 볼 수 있습니다. 즉, 코드를 SSA 형식으로 변환할 때 각 표현식은 구성되는 가장 기본적인 부분으로 구분됩니다. 우리의 경우 명령은 return a + b는 실제로 두 개의 숫자를 더하고 결과를 반환하는 두 가지 작업을 나타냅니다.

또한 여기서는 프로그램의 기본 블록을 볼 수 있으며, 이 코드에는 입력 블록이라는 단 하나의 블록만 있습니다. 아래에서 블록에 대해 더 자세히 이야기하겠습니다.

Go SSA 코드는 LLVM IR로 쉽게 변환됩니다.

define i64 @myAdd(i64 %a, i64 %b) {
entry:
  %0 = add i64 %a, %b
  ret i64 %0
}

여기서 알 수 있는 것은 다양한 구문 구조가 사용되더라도 함수의 구조는 기본적으로 변경되지 않는다는 것입니다. LLVM IR 코드는 C와 유사하게 Go SSA 코드보다 약간 더 강력합니다. 여기서 함수 선언에는 먼저 반환하는 데이터 유형에 대한 설명이 있으며 인수 유형은 인수 이름 앞에 표시됩니다. 또한 IR 구문 분석을 단순화하기 위해 전역 엔터티 이름 앞에 기호가 붙습니다. @, 지역 이름 앞에 기호가 있습니다 % (함수는 전역 엔터티로도 간주됩니다).

이 코드에서 주목해야 할 점은 Go의 유형 표현 결정이 int컴파일러와 컴파일 대상에 따라 32비트 또는 64비트 값으로 표시될 수 있는 는 LLVM이 IR 코드를 생성할 때 허용됩니다. 이는 많은 사람들이 생각하는 것처럼 LLVM IR 코드가 플랫폼 독립적이지 않은 많은 이유 중 하나입니다. 한 플랫폼용으로 생성된 이러한 코드는 다른 플랫폼용으로 간단히 가져와서 컴파일할 수 없습니다(이 문제를 해결하는 데 적합하지 않은 한). 극도의 주의를 기울여).

주목할만한 또 다른 흥미로운 점은 유형이 i64 부호 있는 정수가 아닙니다. 숫자의 부호를 나타내는 측면에서 중립적입니다. 명령어에 따라 부호 있는 숫자와 부호 없는 숫자를 모두 나타낼 수 있습니다. 덧셈 연산의 표현의 경우에는 이것이 중요하지 않으므로 부호 있는 숫자나 부호 없는 숫자로 작업하는데 차이가 없습니다. 여기서는 C 언어에서 부호 있는 정수 변수를 오버플로하면 정의되지 않은 동작이 발생하므로 Clang 프런트엔드가 작업에 플래그를 추가한다는 점에 주목하고 싶습니다. nsw (서명된 랩 없음) 이는 추가가 오버플로되지 않는다고 가정할 수 있음을 LLVM에 알려줍니다.

이는 일부 최적화에 중요할 수 있습니다. 예를 들어 두 개의 값을 추가하면 i16 32비트 플랫폼(32비트 레지스터 사용)에서는 추가 후 범위 내에 유지하기 위해 부호 확장 작업이 필요합니다. i16. 이 때문에 기계 레지스터 크기를 기반으로 정수 연산을 수행하는 것이 더 효율적인 경우가 많습니다.

이 IR 코드로 다음에 무슨 일이 일어날지는 현재 우리에게 특별한 관심이 아닙니다. 코드는 최적화된 다음(그러나 우리와 같은 간단한 예제의 경우 아무것도 최적화되지 않음) 기계어 코드로 변환됩니다.

두 번째 예

우리가 살펴볼 다음 예는 좀 더 복잡할 것입니다. 즉, 우리는 정수 조각을 합하는 함수에 대해 이야기하고 있습니다.

func sum(numbers []int) int {
    n := 0
    for i := 0; i < len(numbers); i++ {
        n += numbers[i]
    }
    return n
}

이 코드는 다음 Go SSA 코드로 변환됩니다.

func sum(numbers []int) int:
entry:
    jump for.loop
for.loop:
    t0 = phi [entry: 0:int, for.body: t6] #n                       int
    t1 = phi [entry: 0:int, for.body: t7] #i                       int
    t2 = len(numbers)                                              int
    t3 = t1 < t2                                                  bool
    if t3 goto for.body else for.done
for.body:
    t4 = &numbers[t1]                                             *int
    t5 = *t4                                                       int
    t6 = t0 + t5                                                   int
    t7 = t1 + 1:int                                                int
    jump for.loop
for.done:
    return t0

여기서는 SSA 형식으로 코드를 표현하는 일반적인 구성을 더 많이 볼 수 있습니다. 아마도 이 코드의 가장 분명한 특징은 구조화된 흐름 제어 명령이 없다는 사실일 것입니다. 계산의 흐름을 제어하려면 조건부 점프와 무조건 점프만 있고, 이 명령을 흐름 제어 명령으로 간주하면 반환 명령이 있습니다.

실제로 여기서는 프로그램이 중괄호를 사용하여 블록으로 구분되지 않는다는 사실에 주목할 수 있습니다(C 언어 계열에서와 같이). 어셈블리 언어를 연상시키는 라벨별로 나누어 기본 블록 형태로 표현되어 있습니다. SSA에서 기본 블록은 레이블로 시작하고 기본 블록 완성 명령으로 끝나는 연속적인 코드 시퀀스로 정의됩니다. return и jump.

이 코드의 또 다른 흥미로운 세부 사항은 다음 명령어로 표현됩니다. phi. 지침은 매우 특이하며 이해하는 데 시간이 걸릴 수 있습니다. 기억 SSA 정적 단일 할당의 약자입니다. 이는 각 변수에 한 번만 값이 할당되는 컴파일러에서 사용되는 코드의 중간 표현입니다. 이는 우리 함수와 같은 간단한 함수를 표현하는 데 적합합니다. myAdd위에 나와 있지만 이 섹션에서 설명하는 함수와 같은 더 복잡한 함수에는 적합하지 않습니다. sum. 특히 루프 실행 중에 변수가 변경됩니다. i и n.

SSA는 소위 명령어를 사용하여 변수 값을 한 번 할당하는 제한을 우회합니다. phi (그 이름은 그리스 알파벳에서 따왔습니다). 사실 C와 같은 언어에 대해 SSA 코드 표현을 생성하려면 몇 가지 트릭을 사용해야 합니다. 이 명령어를 호출한 결과는 변수의 현재 값(i 또는 n), 기본 블록의 목록이 매개변수로 사용됩니다. 예를 들어 다음 지침을 고려해보세요.

t0 = phi [entry: 0:int, for.body: t6] #n

그 의미는 다음과 같습니다. 이전 기본 블록이 블록이었던 경우 entry (입력), 그런 다음 t0 상수이다 0, 그리고 이전 기본 블록이 for.body, 그런 다음 값을 가져와야 합니다. t6 이 블록에서. 이 모든 것이 매우 신비스러워 보일 수 있지만 이 메커니즘이 SSA를 작동하게 만드는 것입니다. 인간의 관점에서 보면 이 모든 것이 코드를 이해하기 어렵게 만듭니다. 그러나 각 값이 한 번만 할당된다는 사실은 많은 최적화를 훨씬 쉽게 만듭니다.

자신만의 컴파일러를 작성하면 일반적으로 이런 종류의 작업을 처리할 필요가 없습니다. Clang조차도 이러한 명령어를 모두 생성하지는 않습니다. phi, 메커니즘을 사용합니다 alloca (일반적인 지역 변수를 사용하는 것과 유사합니다). 그런 다음 LLVM 최적화 패스를 실행할 때 mem2reg, 지침 alloca SSA 형식으로 변환됩니다. 그러나 TinyGo는 편리하게도 이미 SSA 형식으로 변환된 Go SSA로부터 입력을 받습니다.

고려 중인 중간 코드 조각의 또 다른 혁신은 인덱스에 의한 슬라이스 요소에 대한 액세스가 주소를 계산하는 작업과 결과 포인터를 역참조하는 작업의 형태로 표현된다는 것입니다. 여기서는 IR 코드에 상수가 직접 추가되는 것을 볼 수 있습니다(예: - 1:int). 함수가 포함된 예에서 myAdd 이것은 사용되지 않았습니다. 이제 이러한 기능을 제거했으므로 이 코드가 LLVM IR 형식으로 변환되면 어떻게 되는지 살펴보겠습니다.

define i64 @sum(i64* %ptr, i64 %len, i64 %cap) {
entry:
  br label %for.loop

for.loop:                                         ; preds = %for.body, %entry
  %0 = phi i64 [ 0, %entry ], [ %5, %deref.next ]
  %1 = phi i64 [ 0, %entry ], [ %6, %deref.next ]
  %2 = icmp slt i64 %1, %len
  br i1 %2, label %for.body, label %for.done

for.body:                                         ; preds = %for.loop
  %3 = getelementptr i64, i64* %ptr, i64 %1
  %4 = load i64, i64* %3
  %5 = add i64 %0, %4
  %6 = add i64 %1, 1
  br label %for.loop

for.done:                                         ; preds = %for.loop
  ret i64 %0
}

여기서는 이전과 마찬가지로 다른 구문 구조를 포함하는 동일한 구조를 볼 수 있습니다. 예를 들어 통화 중 phi 값과 라벨이 바뀌었습니다. 그런데 여기서 특별히 주목해야 할 점이 있다.

우선 여기에서 완전히 다른 기능 서명을 볼 수 있습니다. LLVM은 슬라이스를 지원하지 않으며 결과적으로 최적화를 위해 이 중간 코드를 생성한 TinyGo 컴파일러는 이 데이터 구조에 대한 설명을 여러 부분으로 분할했습니다. 이는 세 개의 슬라이스 요소를 나타낼 수 있습니다(ptr, len и cap)를 구조(struct)로 나타내지만 이를 세 개의 별도 엔터티로 표시하면 일부 최적화가 가능합니다. 다른 컴파일러는 대상 플랫폼 함수의 호출 규칙에 따라 다른 방식으로 슬라이스를 나타낼 수 있습니다.

이 코드의 또 다른 흥미로운 특징은 명령어를 사용한다는 것입니다. getelementptr (흔히 GEP로 약칭함)

이 명령어는 포인터와 함께 작동하며 슬라이스 요소에 대한 포인터를 얻는 데 사용됩니다. 예를 들어 C로 작성된 다음 코드와 비교해 보겠습니다.

int* sliceptr(int *ptr, int index) {
    return &ptr[index];
}

또는 다음과 동일합니다.

int* sliceptr(int *ptr, int index) {
    return ptr + index;
}

여기서 가장 중요한 것은 지침입니다. getelementptr 역참조 작업을 수행하지 않습니다. 단지 기존 포인터를 기반으로 새 포인터를 계산합니다. 지침으로 받아 들일 수 있습니다. mul и add 하드웨어 수준에서. GEP 지침에 대해 자세히 알아볼 수 있습니다. 여기에.

이 중간 코드의 또 다른 흥미로운 특징은 명령어를 사용한다는 것입니다. icmp. 이는 정수 비교를 구현하는 데 사용되는 범용 명령어입니다. 이 명령어의 결과는 항상 유형의 값입니다. i1 — 논리값. 이 경우 키워드를 사용하여 비교가 이루어집니다. slt (보다 작게 부호 있음), 이전에 유형으로 표시되었던 두 숫자를 비교하고 있기 때문입니다. int. 두 개의 부호 없는 정수를 비교하는 경우 다음을 사용합니다. icmp, 비교에 사용된 키워드는 다음과 같습니다. ult. 부동 소수점 숫자를 비교하려면 다른 명령어가 사용됩니다. fcmp, 비슷한 방식으로 작동합니다.

결과

나는 이 자료에서 LLVM IR의 가장 중요한 기능을 다루었다고 믿습니다. 물론 여기에는 더 많은 것이 있습니다. 특히, 코드의 중간 표현에는 IR에서 달리 표현할 수 없는 컴파일러에 알려진 코드의 특정 기능을 고려하기 위한 최적화 패스를 허용하는 많은 주석이 포함될 수 있습니다. 예를 들어 이것은 플래그입니다. inbounds GEP 명령 또는 플래그 nsw и nuw, 지침에 추가할 수 있음 add. 키워드도 마찬가지 private, 표시하는 함수가 현재 컴파일 단위 외부에서 참조되지 않음을 최적화 프로그램에 나타냅니다. 이를 통해 사용되지 않는 인수 제거와 같은 흥미로운 프로시저 간 최적화가 가능해집니다.

LLVM에 대한 자세한 내용은 다음에서 확인할 수 있습니다. 선적 서류 비치, 자체 LLVM 기반 컴파일러를 개발할 때 자주 참조하게 됩니다. 여기 지도력, 매우 간단한 언어용 컴파일러 개발을 살펴봅니다. 이 두 가지 정보 소스는 자신만의 컴파일러를 만들 때 유용합니다.

독자 여러분! LLVM을 사용하고 있나요?

출처 : habr.com