Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

MIR(중간 수준 IR)

MIR은 Rust의 중간 수준 중간 표현(Mid-level Intermediate Representation)입니다. MIR은 HIR로부터 만들어집니다. MIR은 RFC 1211에서 도입되었습니다. MIR은 Rust를 대폭 단순화한 형태로, 특정 흐름 민감(flow-sensitive) 안전성 검사(특히 빌림 검사기!)와 최적화 및 코드 생성에 사용됩니다.

MIR과 MIR이 기반으로 하는 컴파일러 개념(제어 흐름 그래프, 디슈가링 등)을 아주 개략적으로 소개하는 글을 원하신다면 MIR을 소개한 rust-lang 블로그 글을 읽어 보십시오.

MIR 소개

MIR은 compiler/rustc_middle/src/mir/ 모듈에 정의되어 있지만, MIR을 다루는 코드의 상당 부분은 compiler/rustc_mir_build, compiler/rustc_mir_transform, compiler/rustc_mir_dataflow에 있습니다.

MIR의 주요 특징은 다음과 같습니다.

  • 제어 흐름 그래프를 기반으로 합니다.
  • 중첩된 표현식이 없습니다.
  • MIR의 모든 타입은 완전히 명시적입니다.

주요 MIR 용어

이 절에서는 MIR의 주요 개념을 소개합니다. 요약하면 다음과 같습니다.

  • 기본 블록(Basic block): 제어 흐름 그래프의 단위로, 다음으로 구성됩니다.
    • 문(statement): 후속 지점이 하나인 동작입니다
    • 종결자(terminator): 후속 지점이 여러 개일 수 있는 동작이며, 항상 블록의 끝에 위치합니다
    • (기본 블록이라는 용어가 익숙하지 않다면 배경 지식 장을 참고하십시오)
  • 로컬: 함수 인자, 지역 변수, 임시 값처럼 (적어도 개념적으로는) 스택에 할당되는 메모리 위치입니다. 로컬은 인덱스로 식별되며, _1처럼 앞에 밑줄을 붙여 표기합니다. 반환 값을 저장하기 위해 할당되는 특별한 “로컬”(_0)도 있습니다.
  • 플레이스(Place): _1이나 _1.f처럼 메모리의 위치를 식별하는 표현식입니다.
  • R값(Rvalue): 값을 만들어 내는 표현식입니다. “R“은 이 표현식이 대입문의 “오른쪽(right-hand side)“에 온다는 뜻입니다.
    • 피연산자: rvalue에 전달되는 인자로, 상수(22 등)이거나 place(_1 등)일 수 있습니다.

간단한 프로그램을 MIR로 변환하고 보기 좋게 출력된 결과를 읽어 보면 MIR이 어떻게 구성되는지 감을 잡을 수 있습니다. 실제로 플레이그라운드는 프로그램의 MIR을 보여 주는 MIR 버튼을 제공하므로 이를 쉽게 해 볼 수 있습니다. 이 프로그램을 플레이그라운드에 넣고(또는 이 링크를 클릭하고) 상단의 “MIR” 버튼을 클릭해 보십시오.

fn main() {
    let mut vec = Vec::new();
    vec.push(1);
    vec.push(2);
}

다음과 비슷한 결과가 나타날 것입니다.

// WARNING: This output format is intended for human consumers only
// and is subject to change without notice. Knock yourself out.
fn main() -> () {
    ...
}

이것은 main 함수의 MIR 형식입니다. 위 링크에서 보여 주는 MIR은 최적화된 것입니다. StorageLive와 같은 일부 문장은 최적화 과정에서 제거됩니다. 컴파일러가 코드에서 해당 값에 전혀 접근하지 않는다는 것을 알아차리기 때문입니다. 최적화되지 않은 MIR을 보려면 rustc [filename].rs -Z mir-opt-level=0 --emit mir 명령을 사용할 수 있습니다. 이를 위해서는 nightly 툴체인이 필요합니다.

변수 선언. 조금 더 자세히 살펴보면 여러 개의 변수 선언으로 시작한다는 것을 알 수 있습니다. 변수 선언은 다음과 같습니다:

let mut _0: ();                      // return place
let mut _1: std::vec::Vec<i32>;      // in scope 0 at src/main.rs:2:9: 2:16
let mut _2: ();
let mut _3: &mut std::vec::Vec<i32>;
let mut _4: ();
let mut _5: &mut std::vec::Vec<i32>;

MIR의 변수에는 이름이 없고, 대신 _0이나 _1과 같은 인덱스가 있다는 것을 알 수 있습니다. 또한 사용자 변수(예: _1)와 임시 값(예: _2 또는 _3)이 서로 섞여 있습니다. 사용자 정의 변수에는 debuginfo가 연결되어 있으므로 이를 통해 구별할 수 있습니다(아래 참조).

사용자 변수 debuginfo. 변수 선언 아래에서 _1이 사용자 변수를 나타낸다는 유일한 단서를 찾을 수 있습니다:

scope 1 {
    debug vec => _1;                 // in scope 1 at src/main.rs:2:9: 2:16
}

각 debug <Name> => <Place>; 주석은 이름이 있는 사용자 변수와, 디버거가 해당 변수의 데이터를 찾을 수 있는 위치(즉, place)를 설명합니다. 여기서는 매핑이 단순하지만, 최적화로 인해 place가 복잡해지거나 여러 사용자 변수가 같은 place를 공유하게 될 수 있습니다. 또한 클로저 캡처도 같은 체계로 설명되므로 최적화를 하지 않더라도 복잡합니다. 예: debug x => (*((*_1).0: &T));.

“scope” 블록(예: scope 1 { .. })은 소스 프로그램의 어휘 구조(어떤 이름이 언제 스코프 안에 있었는지)를 설명합니다. 따라서 예를 들어 디버거에서 코드를 단계별로 실행한다면, // in scope 0 주석이 달린 프로그램의 모든 부분에서는 vec이 보이지 않습니다.

기본 블록. 계속 읽어 나가면 첫 번째 기본 블록이 보입니다(직접 볼 때는 당연히 약간 다르게 보일 수 있으며, 일부 주석은 생략했습니다):

bb0: {
    StorageLive(_1);
    _1 = const <std::vec::Vec<T>>::new() -> bb2;
}

기본 블록은 일련의 문장과 마지막 종결자로 정의됩니다. 이 경우에는 문장이 하나 있습니다:

StorageLive(_1);

이 문장은 변수 _1이 “살아 있음”(live), 즉 나중에 사용될 수 있음을 나타냅니다. 이 상태는 변수 _1의 사용이 끝났음을 나타내는 StorageDead(_1) 문장을 만날 때까지 유지됩니다. 이러한 “저장소 문장“은 LLVM이 스택 공간을 할당하는 데 사용합니다.

블록 bb0의 종결자는 Vec::new 호출입니다:

_1 = const <std::vec::Vec<T>>::new() -> bb2;

종결자는 둘 이상의 후속 블록을 가질 수 있다는 점, 즉 제어가 여러 곳으로 흐를 수 있다는 점에서 문장과 다릅니다. Vec::new 호출과 같은 함수 호출은 언와인딩(unwinding) 가능성 때문에 항상 종결자입니다. 다만 Vec::new의 경우에는 실제로 언와인딩이 불가능하다는 것을 알 수 있으므로 후속 블록으로 bb2 하나만 나열합니다.

뒤에 나오는 bb2를 미리 살펴보면 다음과 같습니다:

bb2: {
    StorageLive(_3);
    _3 = &mut _1;
    _2 = const <std::vec::Vec<T>>::push(move _3, const 1i32) -> [return: bb3, unwind: bb4];
}

여기에는 두 개의 문장이 있습니다. 하나는 _3 임시 값을 도입하는 또 다른 StorageLive이고, 다른 하나는 대입입니다:

_3 = &mut _1;

대입은 일반적으로 다음과 같은 형태입니다:

<Place> = <Rvalue>

place는 _3, _3.f, *_3과 같은 표현식으로, 메모리상의 위치를 나타냅니다. Rvalue는 값을 생성하는 표현식입니다. 이 경우 rvalue는 &mut <Place> 형태의 가변 빌림 표현식입니다. 따라서 rvalue의 문법을 대략 다음과 같이 정의할 수 있습니다:

<Rvalue>  = & (mut)? <Place>
          | <Operand> + <Operand>
          | <Operand> - <Operand>
          | ...

<Operand> = Constant
          | copy Place
          | move Place

이 문법에서 볼 수 있듯이 rvalue는 중첩될 수 없으며, 오직 place와 상수만 참조할 수 있습니다. 또한 place를 사용할 때는 그것을 복사하는지(이 경우 place의 타입이 T: Copy를 만족하는 T여야 합니다), 아니면 이동하는지(이 경우 어떤 타입의 place에도 사용할 수 있습니다)를 표시합니다. 예를 들어 Rust에서 x = a + b + c라는 표현식이 있다면, 이는 두 개의 문장과 하나의 임시 변수로 컴파일됩니다:

TMP1 = a + b
x = TMP1 + c

(직접 시도해 보십시오. 다만 오버플로 검사를 건너뛰려면 릴리스 모드를 사용하는 것이 좋습니다.)

MIR 데이터 타입

MIR 데이터 타입은 compiler/rustc_middle/src/mir/ 모듈에 정의되어 있습니다. 앞 절에서 언급한 핵심 개념들은 각각 꽤 직관적인 방식으로 Rust 타입에 대응됩니다.

주요 MIR 데이터 타입은 Body입니다. 이 타입은 단일 함수에 대한 데이터를 담고 있습니다(“승격된 상수(promoted constants)“를 위한 Mir 하위 인스턴스도 함께 담고 있지만, 이에 대해서는 아래에서 읽을 수 있습니다).

  • 기본 블록: 기본 블록은 Body::basic_blocks 필드에 저장되며, 이는 BasicBlockData 구조체의 벡터입니다. 기본 블록을 직접 참조하는 일은 없습니다. 대신 이 벡터에 대한 newtype으로 감싼 인덱스인 BasicBlock 값을 주고받습니다.
  • 문장은 Statement 타입으로 표현됩니다.
  • 종결자는 Terminator로 표현됩니다.
  • 로컬은 newtype으로 감싼 인덱스 타입인 Local로 표현됩니다. 지역 변수의 데이터는 Body::local_decls 벡터에 있습니다. 또한 반환 값을 나타내는 특수한 “로컬“을 식별하는 특수 상수 RETURN_PLACE도 있습니다.
  • Place는 Place 구조체로 식별됩니다. 몇 가지 필드가 있습니다:
    • _1 같은 지역 변수
    • 프로젝션: 기본 place로부터 “투영되어 나오는” 필드나 그 밖의 요소입니다. 이는 newtype으로 감싼 타입인 ProjectionElem으로 표현됩니다. 예를 들어 place _1.f는 프로젝션이며, 여기서 f는 “프로젝션 요소“이고 _1은 기본 경로입니다. *_1 역시 프로젝션이며, 여기서 *는 ProjectionElem::Deref 요소로 표현됩니다.
  • Rvalue는 열거형 Rvalue로 표현됩니다.
  • 피연산자는 열거형 Operand로 표현됩니다.

상수 표현하기

코드가 MIR 단계에 도달하면 상수는 일반적으로 MIR 상수(mir::Constant)와 타입 시스템 상수(ty::Const)의 두 가지 형태로 나타납니다. MIR 상수는 피연산자로 사용됩니다. x + CONST에서 CONST는 MIR 상수이며, 마찬가지로 x + 2에서 2도 MIR 상수입니다. 타입 시스템 상수는 타입 시스템에서 사용되며, 특히 배열 길이에 사용되지만 상수 제네릭에도 사용됩니다.

일반적으로 두 종류의 상수 모두 “평가되지 않은” 상태이거나 “이미 평가된” 상태일 수 있습니다. 평가되지 않은 상수는 이 결과를 계산하기 위해 평가해야 하는 대상의 DefId를 저장할 뿐입니다. 평가된 상수(“값”)는 이미 계산된 상태이며, 그 표현은 타입 시스템 상수와 MIR 상수 사이에 차이가 있습니다. MIR 상수는 mir::ConstValue로 평가되고, 타입 시스템 상수는 ty::ValTree로 평가됩니다.

타입 시스템 상수에는 상수 제네릭을 지원하기 위한 배리언트가 몇 가지 더 있습니다. 타입 시스템 상수는 지역 상수 제네릭 매개변수를 참조할 수 있으며, 추론의 대상이 됩니다. 또한 mir::Constant::Ty 배리언트를 사용하면 임의의 타입 시스템 상수를 MIR 상수로 사용할 수 있습니다. 이는 상수 제네릭 매개변수가 피연산자로 사용될 때마다 발생합니다.

MIR 상수 값

일반적으로 MIR 상수 값(mir::ConstValue)은 사용자가 작성한 어떤 상수를 평가하여 계산된 것입니다. 이 상수 평가는 결과를 개별 바이트 단위로 나타내는 매우 저수준의 표현을 생성합니다. 값이 메모리에 저장되므로 이를 “간접” 상수(mir::ConstValue::Indirect)라고 부릅니다.

그러나 모든 것을 메모리에 저장하는 것은 매우 비효율적입니다. 따라서 mir::ConstValue에는 단순하고 흔한 특정 값을 더 효율적으로 표현할 수 있는 다른 변형이 몇 가지 있습니다. 특히 Rust에서 리터럴로 직접 작성할 수 있는 모든 것(정수, 부동소수점 수, 문자, 불리언뿐만 아니라 "string literals"와 b"byte string literals"도 포함)에는 메모리 내 표현의 전체 오버헤드를 피하는 최적화된 변형이 있습니다.

ValTree

평가된 타입 시스템 상수는 “valtree“입니다. ty::ValTree 자료 구조를 사용하면 다음을 표현할 수 있습니다.

  • 배열,
  • 많은 구조체,
  • 튜플,
  • 열거형,
  • 대부분의 원시 타입.

이 표현에서 가장 중요한 규칙은 모든 값이 고유하게 표현되어야 한다는 것입니다. 다시 말해, 특정한 값은 오직 한 가지 특정한 방식으로만 표현될 수 있어야 합니다. 예를 들어, 두 정수로 이루어진 배열을 ValTree로 표현하는 방법은 Branch([Leaf(first_int), Leaf(second_int)]) 한 가지뿐입니다. 이론적으로는 [u32; 2]를 u64로 인코딩하여 단순히 Leaf(bits_of_two_u32)로 만들 수도 있겠지만, 이는 ValTree의 올바른 구성이 아닙니다(또한 그렇게 하기가 매우 복잡하므로 누군가 그렇게 하고 싶어 할 가능성은 낮습니다).

이러한 규칙은 또한 일부 값은 표현할 수 없다는 것을 의미합니다. 타입 수준 상수에는 union이 있을 수 없습니다. 활성 변형을 알 수 없기 때문에 어떻게 표현해야 할지 명확하지 않기 때문입니다. 마찬가지로 컴파일 시점에는 주소를 알 수 없으므로 원시 포인터를 표현할 방법이 없으며, 따라서 원시 포인터에 대해서는 어떠한 가정도 할 수 없습니다. 반면 참조는 표현될 수 있습니다. 참조의 동등성은 그 값의 동등성으로 정의되므로, 주소는 무시하고 참조가 가리키는 값만 살펴보면 되기 때문입니다. 참조의 포인터 값이 컴파일 시점에 관찰될 수 없도록 보장해야 합니다. 따라서 &42를 42와 정확히 동일하게 인코딩합니다. valtree를 다시 MIR 상수 값으로 변환할 때는 반드시 실제 간접 참조를 다시 도입해야 합니다. 코드 생성 시점에 주소는 여러 사용처 간에 중복 제거될 수도 있고 그렇지 않을 수도 있으며, 이는 전적으로 임의의 최적화 선택에 달려 있습니다.

결과적으로 ValTree의 모든 디코딩은 먼저 타입에 대해 매칭하고 그에 따라 결정을 내리는 방식으로 이루어져야 합니다. 값 자체는 그 값에 해당하는 타입 없이는 어떠한 유용한 정보도 제공하지 않습니다.

승격된 상수

const-eval WG의 승격(promotion) 관련 문서를 참고하십시오.