C++ 컴파일러는 언제 호출을 디버추얼라이즈할 수 있을까?

최근 누군가가 디버추얼라이제이션 최적화에 대해 물었다. 언제 일어나는가? 언제 디버추얼라이제이션을 기대할 수 있는가? 컴파일러마다 디버추얼라이제이션 방식이 다른가? 늘 그렇듯, 이 질문은 나를 실험의 토끼굴로 끌고 들어갔다. 답은 대략 이렇다. 현대의 컴파일러는 final 메서드에 대한 호출은 꽤 안정적으로 디버추얼라이즈한다. 하지만 흥미로운 코너 케이스가 아주 많고 — 분명 내가 아직 생각하지 못한 것도 있을 것이다! — 서로 다른 컴파일러는 그 코너 케이스들의 서로 다른 부분집합을 실제로 잡아낸다.

먼저, 디버추얼라이제이션은 LTO를 통해, 전 프로그램 분석을 사용하여 (아마도?) 더 효과적으로 수행될 수 있다는 점을 관찰하자. 나는 링크 타임 디버추얼라이제이션의 최신 기법 상태에 대해서는 아는 바가 없고, Compiler Explorer에서 실험하기도 어렵다. 그래서 여기서는 LTO에 대해서는 전혀 이야기하지 않겠다. 우리는 순수하게 컴파일러 자체가 할 수 있는 일만 살펴본다.

기본적으로 컴파일러가 디버추얼라이즈하기에 충분한 정보를 아는 상황은 두 가지다. 이 둘은 공통점이 별로 없다.

인스턴스의 동적 타입을 아는 경우

이 경우의 전형적인 예는 다음과 같다.

void test() {
    Apple o;
    o.f();
}

Apple::f가 가상 함수인지 여부는 중요하지 않다. 가상 디스패치가 하는 일은 언제나 객체의 실제 동적 타입에 대한 메서드를 호출하는 것뿐이고, 여기서는 실제 동적 타입이 정확히 Apple임을 우리가 알고 있기 때문이다. 이 경우 정적 디스패치와 동적 디스패치는 같은 결과를 내야 한다.

충분히 똑똑한 컴파일러라면 데이터플로 분석을 사용해 다음과 같은 자명하지 않은 경우도 최적화할 것이다.

Derived d;
Base *p = &d;
p->f();

알고 보니 이런 단순한 우회만으로도 MSVC와 ICC는 속아 넘어간다. 다음 테스트 케이스는 이렇다.

Derived da, db;
Base *p = cond ? &da : &db;
p->f();

이는 Clang에게는 너무 벅차지만, GCC는 실제로 이 경우를 견뎌낸다… 조건식 안으로 Base*로의 변환을 옮기기 전까지는 말이다! 심지어 GCC의 분석도 여기서는 실패한다 (Godbolt).

Derived da, db;
Base *p = cond ? (Base*)&da : (Base*)&db;
p->f();

정적 타입에 대한 “leaf임의 증명”을 알고 있는 경우

좋다. 시스템의 다른 곳에서 포인터를 전달받는다고 가정해 보자. 우리는 그 포인터의 정적 타입(예를 들어 Derived*)은 알지만, 그것이 가리키는 객체 인스턴스의 실제 동적 타입은 모른다. 그래도 컴파일러가 프로그램 전체에서 어떤 타입도 Derived::f를 오버라이드할 수 없음을 어떻게든 증명할 수 있다면, Derived::f에 대한 호출을 디버추얼라이즈할 수 있다.

Proof-by-final

가장 단순한 “leaf임의 증명”은 Derived를 final로 표시하는 것이다.

struct Base {
    virtual int f();
};
struct Derived final : public Base {
    int f() override { return 2; }
};
int test(Derived *p) {
    return p->f();
}

Derived* 타입의 포인터는 “적어도 Derived인” 객체 인스턴스를 가리켜야 한다. 즉, Derived 자신이거나 그 자식 중 하나여야 한다. 그런데 Derived는 final이므로 자식을 가질 수 없다. 따라서 그 인스턴스의 동적 타입은 정확히 Derived여야 하고, 컴파일러는 이 호출을 디버추얼라이즈할 수 있다.

또는 특정 메서드 Derived::f 자체를 final로 표시할 수도 있다.

Derived::f가 Derived 자체에서 선언되었든, Base로부터 상속되었든, 같은 분석이 적용되어야 한다. 예를 들어 컴파일러는 다음 경우도 똑같이 디버추얼라이즈할 수 있어야 한다.

struct Base {
    virtual int f() { return 1; }
};
struct Derived final : public Base {};
int test(Derived *p) {
    return p->f();
}

GCC, Clang, MSVC는 이 테스트를 통과한다 (Godbolt, one 케이스). ICC 21.1.9는 속는다.

아주 기묘한 leaf임 증명 하나는, 클래스 C의 소멸자가 final이면 C는 자식이 없어야 한다는 사실을 관찰하는 것이다. 왜냐하면 C에 자식이 있다면, 그 자식은 소멸자를 가져야 하고(소멸자 없는 클래스는 만들 수 없으므로), 그러면 그 소멸자가 C의 소멸자를 오버라이드하게 되는데, 그것은 허용되지 않기 때문이다. Clang은 실제로 final 소멸자에 경고를 내면서, 그에 기반한 최적화도 수행한다. 다른 모든 벤더는 이 상황을 매우 우스꽝스럽다고 여기는 듯하며, 내가 보기엔 아예 이런 코드 경로조차 두지 않는다.

Proof-by-internal-linkage

내부 연결을 가진 이름의 클래스는 현재 번역 단위 밖에서는 이름을 붙일 수 없다. 따라서 현재 번역 단위 밖에서는 그 클래스를 상속할 수도 없다! 현재 TU 안에 자식 클래스가 없거나 — 적어도 그 메서드를 오버라이드하는 자식이 없다면 — 그 가상 함수 호출은 디버추얼라이즈 가능하다.

namespace {
    class BaseImpl : public Base {};
}
int test(Base *p) {
    return static_cast<BaseImpl*>(p)->f();
}

p가 정말로 “적어도 BaseImpl인” 객체 인스턴스를 가리킨다면, 컴파일러는 그 인스턴스가 정확히 BaseImpl이어야 함을 증명할 수 있다. (그리고 p가 “적어도 BaseImpl인” 인스턴스를 가리키지 않는다면, 어차피 그 프로그램은 정의되지 않은 동작을 가진다.)

이 경우는 실제 코드베이스에서 꽤 흔히 등장할 수 있는 사례처럼 보인다. 헤더 파일에는 기반 클래스를 공개해 두고, 파생 구현은 하나 이상을 단일 .cpp 파일 안에만 빡빡하게 한정해 두는 패턴은 흔하다. 여기에 한 걸음 더 나아가 그런 파생 구현들을 익명 네임스페이스 안에 넣는다면, 컴파일러의 디버추얼라이제이션 로직을 도와주게 될 수도 있다. 물론 정의상 그런 이점은 그 단일 .cpp 파일 안으로만 제한된다!

타입 이름이 내부 연결을 갖게 되는 또 다른 방법은, 템플릿 매개변수 중 하나가 내부 연결을 가진 이름을 포함하는 클래스 템플릿 인스턴스화일 때다. 이름 T가 내부 연결을 가지면, E 자체가 외부 연결을 가지더라도 E<T> 역시 내부 연결을 가진다. 왜냐하면 T의 이름을 쓰지 않고서는 E<T>의 이름을 쓸 수 없기 때문이다. (여기서 T는 “진짜 이름”이어야 한다는 점에 주목하자. 타입 별칭 이야기를 하는 것이 아니다.)

타입 이름은 외부 연결을 가지지만, 컴파일러가 그 타입이 다른 모든 TU에서는 반드시 불완전 타입일 수밖에 없음을 증명할 수 있게 만드는 것도 가능하다. 예를 들면 다음과 같다.

namespace {
    class Internal {};
}
class External { Internal m; };

다른 TU는 class External;을 불완전 타입으로 전방 선언하는 것은 허용되지만, 그 데이터 멤버의 타입 이름을 붙일 수 없으므로 그 타입을 완전하게 만들 수는 없다. 불완전 타입으로부터는 상속할 수 없다. 따라서 External에서 파생된 모든 타입이 있다면 반드시 이 TU 안에 존재해야 하며, 여기에 하나도 없다면 그것이 곧 leaf임의 증명이다! 이 상황을 감지하는 것은 GCC뿐이다.

결과 표

동적 타입을 아는 경우의 Godbolt; leaf임 증명 경우의 Godbolt. 후자에서는 Derived::f가 Derived에 직접 정의된 경우와, Derived::g가 Base에서 상속된 경우를 별도 테스트로 만들었다. GCC는 종종 f는 맞게 처리하지만 g는 디버추얼라이즈하지 못한다. 나는 이에 대해 GCC bug #99093를 등록해 두었다.

Steve Dewhurst가 four의 “우스꽝스러운 옛날식 트릭”을 알려주었다. 가상 기반 클래스는 언제나 가장 파생된 클래스의 문맥에서 생성된다. 따라서 클래스 C가 모든 생성자가 private인 가상 기반 클래스를 갖는다면, C의 어떤 자식도 자기 자신을 생성할 수 없고, 결과적으로 C의 자식은 존재할 수 없다. (물론 C 자체를 생성 가능하게 하려면, 그 가상 기반 클래스는 friend 목록에 C를 넣어 두어야 한다.) 나는 이 트릭이 빈틈이 없다고 생각하며, 따라서 C에 대한 leaf임의 증명으로 성립한다고 본다. 다만 물론 어떤 컴파일러도 이런 논리적 얽힘을 따라가려 하지는 않는다. 비록 그것이 정말로 빈틈이 없더라도 말이다.

---

내가 놓친 “leaf임의 증명” 구성 방법이 또 있을까? 있다면 알려 달라!