C++17. Функция стандартной библиотеки std::launder и задача девиртуализации05.02.2021 13:02

В этой статье мы попробуем разобраться с одним из самых неоднозначных и непонятных нововведений стандарта C++17 — функцией стандартной библиотеки std: launder. Мы посмотрим на std: launder с другой стороны, посмотрим на источник. Разберем что лежит в основе функции на примере решения задачи девиртуализации и реализации виртуальных указателей в LLVM.

wv7w1nevjiuqy_f3wp_md8kwwkk.png

Девиртуализация — это крайне важная оптимизация компилятора, которая позволяет заменить виртуальные (dynamic, indirect) вызовы обычными (static, direct). Виртуальные вызовы приводят к снижению производительности, не могут быть встроены, имеют более сложные механизмы спекулятивного выполнения (Indirect branch prediction), которые могут приводить к снижению безопасности и служить вектором атаки (например, Spectre). Clang и LLVM обеспечивают полную девиртуализацию виртуальных вызовов, когда удается статически определить динамический тип объекта или определить отсутствие переопределения метода и устраняют избыточную загрузку динамической информации (виртуальных таблиц) во всех остальных случаях.


Виртуальный вызов

Виртуальные вызовы реализуют концепцию, которая часто называется динамической диспетчеризацией (dynamic dispatch). Динамическая диспетчеризация — это механизм, позволяющий выбрать реализацию полиморфного метода на основе динамического (фактического) типа объекта во время выполнения программы. По умолчанию вызовы методов выполняются в рамках статической диспетчеризации т.е. на основе статического типа известного во время компиляции. Спецификатор virtual у метода позволяет сменить тип диспетчеризации.

В выражение вида E1.E2, например, вызов метода a->foo() или a.foo(), выражение E1 называется object expression. Динамический тип в данном контексте — это тип объекта, на который ссылается текущее значение выражения E1.

struct A
{
    int foo() { return 1; }
    // объявление метода с virtual меняет статическую диспетчеризацию на динамическую.
    virtual int bar() { return 1; }
};

struct B : A
{
    int foo() { return 2; }
    int bar() override { return 2; }
};

int main()
{
    B b;
    A *a = &b;
    // вызов A::foo() на основе статического типа а
    const int v1 = a->foo();
    // вызов B::foo() на основе динамического (фактического) типа а.
    // динамический тип это тип объекта, на который ссылается указатель а.
    // в данном случае, это объект типа B.
    const int v2 = a->bar();
    assert(v1 == 1);
    assert(v2 == 2);
}

Стандарт не регулирует каким именно образом должен быть реализован механизм динамической диспетчеризации. Все современные компиляторы C++ реализуют динамическую диспетчеризацию и виртуальные вызовы с помощью специальных структур: виртуальных таблиц (virtual table, vtable, vtbl).


Виртуальные таблицы

Виртуальные таблицы генерируются для каждого класса с виртуальными методами или виртуальными базовыми классами. Во время создания экземпляра такого класса, адрес соответствующей таблицы записывается в специальное техническое поле: виртуальный указатель (virtual pointer). Виртуальных указателей может быть несколько, для каждого базового класса. При этом под адресом виртуальной таблицы т.е. адрес, который будет записан в виртуальный указатель экземпляра класса, не всегда понимается адрес начала таблицы. В терминах ABI этот адрес называется address point. Доступ ко всем записям таблицы осуществляется фиксированными смещениями, как положительными, так и отрицательными, относительно этого адреса.

Виртуальные таблицы содержат следующую информацию:


  1. Virtual call offsets. Записи содержат смещения для корректировки указателя (this) от виртуального базового класса до класса-потомка. Используются для вызова переопределенного в классе-потомке метода виртуального базового класса.
  2. Virtual base offsets. Записи содержат смешения от адреса поля виртуального указателя до адреса подобъекта виртуального базового класса. Добавляется для каждого виртуального базового класса.
  3. Offset to top. Запись содержит смешение от адреса поля виртуального указателя до адреса начала объекта т.е. адреса первого байта. Смещение позволяет найти начало объекта из любого базового подобъекта с помощью виртуального указателя.
  4. Typeinfo pointer. Запись содержит адрес объекта с данными о типе RTTI.
  5. Virtual function pointers. Записи содержат адреса виртуальных методов класса или адреса вторичных точек входа (thunk). Используются для динамической диспетчеризации. Реализация таких указателей определяется конкретным ABI. Последовательность записей совпадает с последовательностью объявлений соответствующих методов в классах. Все записи в таблицах иерархии совместимых классов находятся в согласованном состояние т.е. для каждого виртуального метода в дереве наследования имеется одно, фиксированное смещение в таблице. Если дочерний класс перегружает реализацию базового метода, то в таблице этого класса меняется соответствующая запись на адрес перегруженного метода. Такая таблица совместима с таблицей базового класса.

Например, для иерархии классов: 

struct A
{
    void s();
    virtual void f();
    virtual void g();
};

struct B : A
{
    void f() override;
    virtual void h();
};

struct C
{
    virtual void k();
};

struct D : A, C
{
    void g() override;
    void k() override;
};

Будут сгенерированы следующие таблицы (x86–64 clang 10.0.0): 

# виртуальная таблица для класса А
vtable for A:
    .quad 0                # Смещение Offset To Top
    .quad typeinfo for A   # адрес объекта typeinfo с данными о типе RTTI
    .quad A::f()           # адрес базовой реализации метода f()
    .quad A::g()           # адрес базовой реализации метода g()

# виртуальная таблица для класса B
vtable for B:
    .quad 0                # Смещение Offset To Top
    .quad typeinfo for B   # адрес объекта typeinfo с данными о типе RTTI
    .quad B::f()           # адрес переопределенного метода f()
    .quad A::g()           # адрес базовой реализации метода g()
    .quad B::h()           # адрес метода h()

# виртуальная таблица для класса C
vtable for C:
    .quad 0                # Смещение Offset To Top
    .quad typeinfo for C   # адрес объекта typeinfo с данными о типе RTTI
    .quad C::k()           # адрес базовой реализации метода k()

# виртуальная таблица для класса D
# состоит из двух таблиц,
# одна совместима с виртуальной таблицей B, другая с виртуальной таблицей C
vtable for D:
    #                        Cовместимая с B таблица
    .quad 0                # Смещение Offset To Top
    .quad typeinfo for D   # адрес объекта typeinfo с данными о типе RTTI
    .quad A::f()           # адрес базовой реализации метода f()
    .quad D::g()           # адрес переопределенного метода g()
    .quad D::k()           # адрес переопределенного метода k()
    #                        Cовместимая с С таблица
    .quad -8               # Смещение Offset To Top
    .quad typeinfo for D   # адрес объекта typeinfo с данными о типе RTTI
    .quad thunk for D::k() # вторичная точка входа для переопределенного метода D::k()

Можно заметить, что записи о виртуальных методах в таблицах совместимы, например, метод f() имеет одно и тоже смещение во всех таблицах совместимых типов (А, B, D).

Класс D использует множественное наследование с несколькими базовыми классами: A и C. Объект типа D содержит два виртуальных указателя. Один принадлежит базовому подобъекту A и указывает на таблицу совместимую с таблицей класса A, другой принадлежит базовому подобъекту C и содержит адрес таблицы совместимой с виртуальной таблицей класса C.

Чтобы понять почему в таблице совместимой с классом С вместо указателя на метод D::k() помещен thunk for D::k(), рассмотрим следующий код: 

D *d = new D;
A *a = dynamic_cast(d);
C *c = dynamic_cast(d);
c->k();

Если посмотреть на адреса d, a, c и this в методе k(), то они будут, например, такими

d:    0x1edcee0
a:    0x1edcee0
c:    0x1edcee8
this: 0x1edcee0

Адреса d, а, this совпадают, а адрес с смещен на 8 байт относительно d. Так происходит из-за того, что в памяти базовый подобъект C смещен на 8 байт из-за технического поля (виртуального указателя) базового подобъекта A. Поэтому при вызове, мы не можем передать c в качестве this в метод k(). Перед вызовом this должен быть скорректирован, чтобы указывать на объект класса, который выполнил переопределение метода. Именно эту корректировку и делает thunk перед передачей управления методу k().

Таким образом, вторичная точка входа thunk — это сегмент кода ассоциированный с целевым методом, который выполняет определенные корректировки входных параметров (например, this) перед передачей управления методу. Thunk может содержать просто дополнительную инcтрукцию, которая будет выполнена до перехода к целевому методу или быть полноценной функцией со своим стековым кадром и дальнейшим полноценным вызовом метода. Используется при множественном наследовании.


Ассоциация виртуальных таблиц

При создании объекта в конструкторах генерируется код, сохраняющий адрес соответствующей виртуальной таблицы в поле виртуального указателя.

void test(A *a)
{
    a->s();
    a->f();
    a->f();
    a->g();
}

int main()
{
    A *a = new B;
    test(a);
}

Будет сгенерирован следующий код (x86–64 clang 10.0.0): 

# виртуальная таблица для класса А
vtable for A:
    .quad 0
    .quad typeinfo for A
    .quad A::f()   # address point
    .quad A::g()

# виртуальная таблица для класса B
vtable for B:
    .quad 0
    .quad typeinfo for B
    .quad B::f()   # address point
    .quad A::g()
    .quad B::h()

main:
    push    rbx
    mov     edi, 8
    # new expression
    # вызов оператора new
    call    operator new(unsigned long)
    mov     rbx, rax
    mov     rdi, rax
    # вызов конструктора B
    call    B::B() [base object constructor]
    mov     rdi, rbx
    call    test(A*)
    xor     eax, eax
    pop     rbx
    ret

# конструктор класса B
B::B() [base object constructor]:
    push    rbx
    mov     rbx, rdi
    # вызов конструктора базового класса A
    call    A::A() [base object constructor]
    # сохраняем адрес виртуальной таблицы (address point) класса B
    # переписываем значение сохраненное в конструкторе базового класса
    # 16 - это смещение до address point таблицы B
    mov     qword ptr [rbx], offset vtable for B+16
    pop     rbx
    ret

# конструктор класса A
A::A() [base object constructor]:
    # сохраняем адрес виртуальной таблицы (address point) класса A
    # 16 - это смещение до address point таблицы A
    mov     qword ptr [rdi], offset vtable for A+16
    ret

Т.к. таблицы в иерархии совместимы с точки зрения адресации, то каждый конструктор просто сохраняет адрес, соответствующей его типу таблицы, переписывая значение базового класса. В данном случае, адресом виртуальной таблицы является адрес записи с адресом первого виртуального метода в иерархии: f(). Относительно этого адреса осуществляется доступ ко всем остальным записям в таблице.


Вызов виртуального метода

В общем случае виртуальный вызов состоит из следующих шагов:


  1. Прочитать адрес виртуальной таблицы из виртуального указателя;
  2. Сместить значение загруженного указателя до записи в таблице с адресом вызываемого метода;
  3. Прочитать адрес метода;
  4. Выполнить косвенный вызов по прочитанному адресу.

Без каких-либо оптимизаций, эти шаги выполняются при каждом виртуальном вызове, независимо от контекста, например, при вызове в цикле.

Сгенерированный код функции test() из предыдущего примера (x86–64 clang 10.0.0 -std=c++17 -O1): 

test(A*):
    push    rbx
    mov     rbx, rdi

    # вызов a->e()
    # прямой вызов метода по фиксированному адресу, статическая диспетчеризация,
    # тип известен на этапе компиляции
    call    A::e()

    # вызов a->f()
    # читаем виртуальный указатель, хранит
    # адрес записи в виртуальной таблице с адресом метода f()
    mov     rax, qword ptr [rbx]
    # читаем адрес f() из таблицы и выполняем косвенный вызов метода
    call    qword ptr [rax]

    # еще один вызов a->f()
    # читаем виртуальный указатель, хранит
    # адрес записи в виртуальной таблице с адресом метода в f()
    mov     rax, qword ptr [rbx]
    mov     rdi, rbx
    # читаем адрес f() из таблицы и выполняем косвенный вызов метода
    call    qword ptr [rax]

    # вызов a->g()
    # читаем виртуальный указатель, хранит
    # адрес записи в виртуальной таблице с адресом метода в f()
    mov     rax, qword ptr [rbx]
    mov     rdi, rbx
    # смещаем на следующую запись относительно f(): adress point + 8
    # запись содержит адрес метода g()
    # читаем адрес g() из таблицы и выполняем косвенный вызов метода
    call    qword ptr [rax + 8]
    pop     rbx
    ret

Задача девиртуализации заключается в замене виртуальных (косвенных) вызовов прямыми (с фиксированным адресом), в случае когда удается статически (во время компиляции) определить динамический тип объекта или убедиться, что виртуальный метод не переопределен. Если на этапе компиляции динамический тип определить не удалось, то устранить избыточное чтение виртуальных указателей и адресов методов.

Девиртуализация может быть выполнена на разных уровнях:


  1. Front-end. На уровне конкретного языка, эксплуатируя конкретные языковые особенности;
  2. Middle-end. На уровне промежуточного представления, в нашем случае LLVM IR, до этапа генерации кода.

Front-end. Девиртуализация на уровне C++

Девиртуализация по своей природе является оптимизацией конкретного языка, поэтому естественно ожидать, что она будет реализована во внешнем интерфейсе. Исключая LTO (Link-Time Optimization), в обрабатываемом юните трансляции есть только несколько случаев, когда компилятор может сделать вывод об отсутствии переопределения метода или статически определить динамический тип объекта.


Динамический тип совпадает со статическим

struct A
{
    virtual void f();
};

struct B : A
{
    void f() override;
};

void test()
{
    B a;
    a.f();
    a.f();
}

По стандарту, вызов a.f() также является виртуальным. Любой вызов виртуального метода является виртуальным, исключая вызовы с явно квалифицированным именем метода. Т.е. вызов a.A::f() выполняется в рамках статической диспетчеризации.

Напомним, что в выражении вида E1.E2, например, вызов метода a.f(), динамический тип — это тип объекта, на который ссылается значение выражения E1 (object expression). Значение выражения в данном случае, является сам объект а, т.е. динамический и статический тип совпадают. Поэтому мы можем просто заменить косвенный вызов на прямой.

Будет сгенерирован следующий код (x86–64 clang 10.0.0 -std=c++17 -O0): 

test():
    push    rbp
    mov     rbp, rsp
    sub     rsp, 16
    lea     rdi, [rbp - 8]
    call    B::B() [base object constructor]
    lea     rdi, [rbp - 8]
    # прямой вызов B::f()
    call    B::f()
    lea     rdi, [rbp - 8]
    # прямой вызов B::f()
    call    B::f()
    add     rsp, 16
    pop     rbp
    ret

Вызов виртуальных методов в конструкторе/деструкторе

struct A
{
    A()
    {
        f();
    }
    virtual ~A()
    {
        f();
    }
    virtual void f();
};

struct B : A
{
    B()
    {
        f();
    }
    ~B()
    {
        f();
    }
    void f() override;
};

Поcмотрим еще раз на генерируемый код и на порядок инициализации виртуального указателя в конструкторе/деструкторе.

# конструктор класса A
A::A() [base object constructor]:
    push    rax
    # сохраняем адрес виртуальной таблицы для класса А
    mov     qword ptr [rdi], offset vtable for A+16
    # прямой вызов A::f();
    call    A::f()
    pop     rax
    ret

# деструктор класса A
A::~A() [base object destructor]:
    push    rax
    # сохраняем адрес виртуальной таблицы для класса А
    mov     qword ptr [rdi], offset vtable for A+16
    # прямой вызов A::f()
    call    A::f()
    pop     rax
    ret

# конструктор класса B
B::B() [base object constructor]:
    push    rbx
    mov     rbx, rdi
    # вызов конструктора базового класса
    call    A::A() [base object constructor]
    # сохраняем адрес виртуальной таблицы для класса B
    mov     qword ptr [rbx], offset vtable for B+16
    mov     rdi, rbx
    # прямой вызов B::f()
    call    B::f()
    pop     rbx
    ret

# деструктор класса B
B::~B() [base object destructor]:
    push    rbx
    mov     rbx, rdi
    # сохраняем адрес виртуальной таблицы для класса B
    mov     qword ptr [rdi], offset vtable for B+16
    # прямой вызов B::()
    call    B::f()
    mov     rdi, rbx
    # вызов деструктора базового класса
    call    A::~A() [base object destructor]
    pop     rbx
    ret

На момент вызова конструктора базового класса, вызов конструктора класса-потомка еще не завершен, указатель на виртуальную таблицу не переписан и указывает на таблицу базового класса. На момент вызова деструктора базового класса (вызывается после деструктора класс-потомка), объект класса-потомка уже деинициализирован и вызов методов такого объекта в общем случае может быть небезопасным. Компилятор не позволяет нам выполнить такой вызов и защищает от ошибок. Поэтому в деструкторе виртуальный указатель инициализируется так же как в конструкторе, т.е. адресом своей виртуальной таблицы. В результате, даже при отсутствии дервиртуазиции, в конструкторе и деструкторе (виртуализация деструктора ни как не влияет на результат) виртуальный указатель всегда будет указывать на свою виртуальную таблицу, а не на таблицу класса-потомка. Т.е. cитуация сводится к ситуации, когда компилятор может сделать вывод о том, что вызываемые виртуальные методы не переопределяются в классах-потомках. Вызовы могут быть замены на прямые вызовы.

На front-end’е эту оптимизацию делают GCC и MSVC. Clang оставляет эту задачу LLVM. LLVM оптимизирует эти вызовы с помощью store to load propagation (в конструкторе/деструкторе видны запись и чтение виртуального указателя) в рамках прохода GVN (Global Value Numbering).


Локализация класса в юните трансляции

namespace
{
    struct A
    {
        virtual int f() { return 1; }
    };
}

int test(A *a)
{
    return a->f();
}

Т.к. класс локализован в юните трансляции (имеет внутреннее связывание) и нет ни одного класса-потомка, то компилятор мог бы выполнить замену вызова, однако ни один компилятор на данный момент этого не делает. Clang не может этого сделать из-за особенностей трансляции исходного кода (не может определить, что ниже по коду нету классов-потомков).


Финализация класса/метода

struct A
{
    virtual int f() final;
    virtual int g();
};

struct B final : A
{
    int g() override;
};

void test(A *a, B *b)
{
    a->f();
    a->g();
    b->g();
}

Сгенерированный код (x86–64 clang 10.0.0 -std=c++17 -O0): 

test(A*, B*):
    push    rbp
    mov     rbp, rsp
    sub     rsp, 32
    mov     qword ptr [rbp - 8], rdi
    mov     qword ptr [rbp - 16], rsi
    mov     rdi, qword ptr [rbp - 8]
    # прямой вызов A::f(),
    # метод f() финализирован в классе А и не может быть переопределен
    call    A::f()
    mov     rcx, qword ptr [rbp - 8]
    mov     rdx, qword ptr [rcx]
    mov     rdi, rcx
    mov     dword ptr [rbp - 20], eax
    # косвенный вызов метода g(), 
    # т.к. может существовать класс-потомок переопределяющий метод
    call    qword ptr [rdx + 8]
    mov     rdi, qword ptr [rbp - 16]
    mov     dword ptr [rbp - 24], eax
    # прямой вызов B::g(), т.к. класс B финализирован
    call    B::g()
    add     rsp, 32
    pop     rbp
    ret

Middle-end. Девиртуализация на уровне промежуточного представления

Рассмотрим небольшой пример, чтобы понять на чем оcнован традиционный подход к девиртуализации: 

struct A
{
    virtual void f();
};

struct B : A
{
    void f() override;
};

void test()
{
    A *a = new B;
    a->f();
}

Для девиртуализации метода, компилятору нужно знать три вещи:


  1. Значение виртуального указателя. Адрес конкретной виртуальной таблицы. Т.е. по сути, компилятор должен видеть значение, которое записывается в виртуальный указатель в конструкторе.
  2. Адрес конкретного метода. Т.к. виртуальные таблицы константны: генерируются для каждого типа в момент компиляции и не могут меняться во время выполнения, то для получения адреса метода из таблицы, наблюдая значение виртуального указателя (конкретную таблицу), нам достаточно просто определения этой таблицы (virtual table definition).
  3. Компилятор должен быть уверен, что с момента инициализации виртуального указателя (записи значения) в конструкторе и до момента вызова конкретного виртуального метода т.е. чтения виртуального указателя, его значение не переписывается (no clobbering).

Если все эти условия соблюдены, то компилятор может выполнить store to load propagation на виртуальном указателе и заменить виртуальный вызов прямым. Здесь важно понимать, что это оптимизация на уровне промежуточного представления (target-independed optimization) и код обрабатывается без какой-либо семантической нагрузки из C++.

Например, выше мы рассматривали вызов виртуального метода в конструкторе. Там все условия соблюдаются, поэтому Clang/LLVM выполнят девиртуализацию таких вызовов.

Для функции test после всех оптимизаций в IR будет сгенерирован следующий код (x86–64 clang 10.0.0 -std=c++17 -O2): 

test():
    push    rax
    mov     edi, 8
    call    operator new(unsigned long)
    # заинлайненый конструктор объекта B
    # сохранение адреса виртуальной таблицы в виртуальный указатель
    mov     qword ptr [rax], offset vtable for B+16
    mov     rdi, rax
    pop     rax
    # прямой вызов f()
    jmp     B::f()

В этом подходе есть ряд ограничений.

Если у нас определен внешний конструктор или его не удалось встроить, то мы нарушим первое условие и компилятор не сможет девиртуализировать вызов. Что бы это продемонстрировать достаточно собрать предыдущий пример с выключенным инлайненгом.

Для функции test будет сгенерирован следующий код (x86–64 clang 10.0.0 -std=c++17 -O2 -fno-inline): 

test():
    push    rbx
    mov     edi, 8
    call    operator new(unsigned long)
    mov     rbx, rax
    mov     rdi, rax
    # внешний конструктор
    call    B::B() [base object constructor]
    mov     rax, qword ptr [rbx]
    mov     rdi, rbx
    pop     rbx
    # косвенный вызов f()
    jmp     qword ptr [rax]

B::B() [base object constructor]:
    push    rbx
    mov     rbx, rdi
    call    A::A() [base object constructor]
    mov     qword ptr [rbx], offset vtable for B+16
    pop     rbx
    ret

В точке вызова компилятор не видит инициализацию виртуального указателя и не может сделать предположение о его значении после вызова конструктора объекта.

Вторая проблема заключается в отслеживании инварианта виртуального указателя. Следует отметить, что ни каких дополнительных знаний о виртуальном указателе у компилятора нет и отслеживание состояния сводится к отслеживанию инструкций записи. Эта задача лежит на модуле Alias Analysis (Pointer Analysis). Это набор алгоритмов, с помощью которых модуль в общем случае пытается определить: могут ли два указателя ссылаться на один и тот же объект в памяти. Для поиска предшествующих операций с памятью, от которых зависит заданная инструкция, LLVM может использовать интерфейс MemDep (Memory Dependence Analysis) или более эффективный MemSSA (Memory SSA). Одно из основных положение такого анализа — это отслеживание: выходит ли указатель за пределы функции или юнита трансляции т.е. обращаются ли к памяти со стороны или мы работаем с памятью локально. Для локальной обработки алгоритмы могут достаточно точно определить какие указатели могут указывать на объект и соответственно какие инструкции этот объект меняют. В случае выхода указателя за пределы анализатор предполагает, что память может быть перезаписана.

Дополним пример выше: 

struct A
{
    virtual void f();
};

struct B : A
{
    void f() override;
};

void test()
{
    A *a = new B;
    a->f();
    // второй вызов виртуального метода, 
    // компилятор не видит определение метода f()
    a->f();
}

void foo(A *a);

void test1()
{
    A *a = new B;
    // вызов внешней функции и передача указателя
    foo(a);
    a->f();
}

Будет сгенерирован следующий код (x86–64 clang 10.0.0 -std=c++17 -O2): 

test():
    push    rbx
    mov     edi, 8
    call    operator new(unsigned long)
    mov     rbx, rax
    mov     qword ptr [rax], offset vtable for B+16
    mov     rdi, rax
    # прямой вызов метода f()
    call    B::f()
    mov     rax, qword ptr [rbx]
    mov     rdi, rbx
    pop     rbx
    # косвенный вызов метода f()
    jmp     qword ptr [rax]

test1():
    push    rbx
    mov     edi, 8
    call    operator new(unsigned long)
    mov     rbx, rax
    # встроенный конструктор
    mov     qword ptr [rax], offset vtable for B+16
    mov     rdi, rax
    # вызов внешней функции
    call    foo(A*)
    mov     rax, qword ptr [rbx]
    mov     rdi, rbx
    pop     rbx
    # косвенный вызов метода f()
    jmp     qword ptr [rax]

Второй вызов метода f() в функции test() не будет оптимизирован. Так происходит потому, что анализатор не знает что на самом деле делает метод f() и у него нет другой альтернативы кроме как предположить худший вариант: представление объекта, на который указывает а может поменяться, смениться динамический тип и соответственно значение виртуального указателя. Аналогичная ситуация с функцией test1() и вызовом foo(a). Еще раз заметим, что с точки зрения LLVM виртуальный указатель — это просто указатель с адресом, как любой другой. Ни какой семантики из C++ на него не наложено.

Ключевой вопрос здесь, каким образом мы может изменить динамический тип объекта и значение виртуального указателя в C++?

Кроме того, что виртуальный указатель несколько раз меняется в процессе вызова конструктора и деструктора, объектная модель C++ дает нам возможность завершить время жизни (lifetime) любого объекта и переиспользовать выделенную под него память, создав там другой объект.

Стандарт не дает нам четкого определения, что такое время жизни. Причина введения в стандарт концепции времени жизни, как свойство объекта — это дать нам знание о том, когда мы можем использовать объект без каких-либо ограничений и выразить правила работы с ним более общими понятиями, независимо от его типа и правил инициализации.

Существование объекта можно разделить на следующие этапы:


  1. Память под объект была выделана, время жизни объекта еще не началось;
  2. Процесс создания объекта (constructor);
  3. Существование объекта;
  4. Процесс уничтожения объекта (destructor);
  5. Время жизни объекта закончилось, память или переиспользуется другим объектом или освобождена.

Если указатель ссылается на выделенную память, но процесс создания объекта еще не начался или указатель ссылается на объект, время жизни которого уже закончилось, то на указатель накладываются следующие ограничения и нарушение хотя бы одного из этих ограничений приводит к Undefined Behavior:


  • Указатель не может выступать в качестве операнда delete expression, если время жизни объекта было закончено. Исключая объекты с тривиальным деструктором;
  • Указатель не может использоваться для доступа к полям и методам класса;
  • Указатель не может быть приведен к указателю на виртуальный базовый класс;
  • Указатель не может выступать в качестве операнда static_cast. Исключая приведение к void* и/или дальнейшее приведение к char*, unsigned char* или std::byte*;
  • Указатель не может выступать операндом dynamic_cast.

Т.е. каждое из этих условий требует доступ к объекту, который еще не был создан или уже был удален.

Здесь есть важное замечание. Если после завершения времени жизни объекта мы переиспользуем память и вновь созданный объект имеет заменяемый тип (transparently replaceable), то все указатели, ссылки и имена, которые ссылались на исходный объект, автоматически начинают указывать на новый и могут быть использованы для оперирования новым объектом. Два типа называются заменяемыми, в данном контексте, если выполнены следующие условия:


  • Новый объект использует в точности всю память старого объекта;
  • Объекты имеют одинаковый тип с точностью до cv-квалификаторов;
  • Тип исходный объект не является константным и тип не содержит константных или ссылочных полей (в случае пользовательского типа данных).

Ниже мы увидим что transparently replaceable является крайне точным термином.

Вернемся к нашему примеру: 

void B::f()
{
    // виртуальный метод класса меняет динамический тип объекта
    // мы завершаем время жизни существующего объекта
    // и создаем новый другого типа
    new(this) A;
}

void test()
{
    A *a = new B;
    a->f();
    // неопределенное поведение
    a->f();
}

Код метода B::f(), с точки зрения описанных выше правил, корректен, но т.к. типы исходного и нового объектов не заменяемы, то все существующие указатели (включая this) мы можем использовать только ограниченным образом, т.е. только как указатели на область памяти, а не как указатели на конкретные объекты. Как следствие, второй вызов метода a->f() приводит к неопределенному поведению, т.к. указатель a ссылается на объект, чье время жизни было закончено.

Для полноты описания так же заметим, что placement new возвращает указатель, который может быть использован для манипулирования новым объектом.

Например: 

void B::f()
{
    // виртуальный метод класса меняет динамический тип объекта
    // мы завершаем время жизни существующего объекта
    // и создаем новый, другого типа
    A *a = new(this) A;
    // a может может использоваться для доступа к методам и полям нового объекта
    // однако вызов g(), используя this является Undefined Behavior,
    // при этом this и a, по умолчанию, указываю на одну и ту же область памяти
    a->g();
    // создаем еще один объект с исходным типом
    // использование this является корректным, а
    // использование указателя a для доступа к полям Undefined Behavior
    new (this) B;
    g();
}

В общем случае, компилятор вправе предполагать, что программа определена корректно и случаев неопределенного поведения в ней нет. В частности, в рамках девиртуализации, компилятор может предположить, что между двумя виртуальными вызовами с разыменованием одного и того же указателя, динамический тип этого указателя измениться не может (иначе поведение стало бы неопределенным). Следовательно, повторная загрузка виртуального указателя и адреса метода является избыточной.

Основная сложность представления в LLVM IR описанной семантики заключается в том, что указатели ссылающиеся на один и тот же адрес могут указывать на объекты с разным временем жизни и не должны рассматриваться как эквивалентные т.е. с точки зрения оптимизатора не могут участвовать в подстановке (substitution).
Реализация Clang/LLVM позволяющая выразить семантику выше, время жизни динамических объектов и инварианты виртуальных указателей, доступна с флагом -fstrict-vtable-pointers.


Инварианты виртуальных указателей

Мы будем рассматривать код: 

struct A
{
    virtual void f();
    virtual void g();
};

struct B : A
{
    void f() override;
    void g() override;
};

A* get_object();

void test()
{
    A *a = get_object();
    a->f();
    a->f();
    a->f();
    a->g();
}

Используя традиционный, описанный выше, подход к девиртуализации, cо всеми оптимизациями в IR мы получим следующий код (x86–64 clang 10.0.0 -std=c++17 -O2, код немного упрощен, убраны несущественные детали, атрибуты, метаданные).

define dso_local void @test()
{
    ; запрос объекта
    %1 = call %struct.A* @get_object()
    %2 = bitcast %struct.A* %1 to void (%struct.A*)***
    ; вызов метода f()
    ; чтение виртуального указателя
    %3 = load void (%struct.A*)**, void (%struct.A*)*** %2
    ; чтение адреса метода f()
    %4 = load void (%struct.A*)*, void (%struct.A*)** %3
    ; косвенный вызов f()
    call void %4(%struct.A* %1)

    ; второй вызов метода f()
    ; повторное чтение виртуального указателя
    %5 = load void (%struct.A*)**, void (%struct.A*)*** %2
    ; повторное чтение адреса метода f()
    %6 = load void (%struct.A*)*, void (%struct.A*)** %5
    ; косвенный вызов f()
    call void %6(%struct.A* %1)

    ; третий вызов f()
    ; еще одно чтение виртуального указателя
    %7 = load void (%struct.A*)**, void (%struct.A*)*** %2
    ; еще одно чтение адреса метода f()
    %8 = load void (%struct.A*)*, void (%struct.A*)** %7
    ; косвенный вызов f()
    call void %8(%struct.A* %1)

    ; вызов метода g()
    ; еще одно чтение виртуального указателя
    %9 = load void (%struct.A*)**, void (%struct.A*)*** %2
    ; смещение адреса виртуальной таблицы до записи с адресом метода g()
    %10 = getelementptr inbounds void (%struct.A*)*, void (%struct.A*)** %9, i64 1
    ; чтение адреса метода g()
    %11 = load void (%struct.A*)*, void (%struct.A*)** %10
    ; косвенный вызов g()
    call void %11(%struct.A* %1)
}

В данном случае, ни один вызов не будет девиртуализирован, потому что компилятор не видит что делает функция get_object, не видит создание объекта и запись виртуального указателя. Задача LLVM, в данном примере, учесть факт того, что динамический тип не может поменяться в процессе вызовов, выразив инвариантность виртуального указателя и константность виртуальной таблицы, избавившись в итоге от избыточного чтения.

LLVM расширяет список возможных метаданных инструкций чтения и записи новым элементом invariant.group. Метаданные инструкций — это подсказка оптимизатору об уникальных свойствах инструкции. Наличие или отсутствие таких метаданных не меняет семантику программы.

Присутствие метаданных в инструкции invariant.group указывает оптимизатору, что чтение/запись с одним и тем же операндом или другими словами, если операнд принадлежит одной и той же инвариантной группе, возвращает/сохраняет одно и тоже значение. Чтобы выразить инвариант виртуального указателя, каждая инструкция чтения виртуального указателя (в рамках виртуального вызова) и каждая инструкция записи виртуального указателя (в рамках инициализации в конструкторе/деструкторе) сопровождается метаданными invariant.group.

Так же каждую инструкцию чтения виртуальной таблицы в процессе виртуального вызова LLVM сопровождает метаданными invariant.load. Эти метаданные указывают на то, что область памяти, на которую ссылается операнд инструкции чтения, содержит одно и тоже значение независимо от того в какой момент и где мы эти данные читаются. Это позволяет выразить тот факт, что содержимое виртуальной таблицы постоянно и в процессе выполнения меняется не может.

define dso_local void @test()
{
    ; запрос объекта
    %1 = tail call %struct.A* @get_object()
    %2 = bitcast %struct.A* %1 to void (%struct.A*)***
    ; вызов метода f()
    ; чтение виртуального указателя,
    ; инструкция содержит метаданные invariant.group
    %3 = load void (%struct.A*)**, void (%struct.A*)*** %2, !invariant.group !{}
    ; чтение адреса метода f() из виртуальной таблицы,
    ; инструкция содержит метаданные invariant.load
    %4 = load void (%struct.A*)*, void (%struct.A*)** %3, !invariant.load !{}
    tail call void %4(%struct.A* %1)

    ; второй вызов метода f()
    ; повторное чтение виртуального указателя, инструкция помечена invariant.group
    ; оптимизатор может предположить что данные уже прочитаны в %3
    %5 = load void (%struct.A*)**, void (%struct.A*)*** %2, !invariant.group !{}
    ; чтение адреса метода f() из виртуальной таблицы,
    ; инструкция содержит метаданные invariant.load
    ; оптимизатор знает что данные загружаемые инструкцией по переданному адресу
    ; постоянны и не могут изменится в процессе выполнения
    %6 = load void (%struct.A*)*, void (%struct.A*)** %5, !invariant.load !{}
    tail call void %6(%struct.A* %1)

    ; третий вызов f()
    ; еще одно чтение виртуального указателя, инструкция помечена invariant.group
    ; оптимизатор может предположить что данные уже прочитаны в %3
    %7 = load void (%struct.A*)**, void (%struct.A*)*** %2, !invariant.group !{}
    ; чтение адреса метода f() из виртуальной таблицы,
    ; инструкция содержит метаданные invariant.load
    ; оптимизатор знает что данные загружаемые инструкцией по переданному адресу
    ; постоянны и не могут изменится в процессе выполнения
    %8 = load void (%struct.A*)*, void (%struct.A*)** %7, !invariant.load !{}
    tail call void %8(%struct.A* %1)

    ; вызов метода g()
    ; еще одно чтение виртуального указателя, инструкция помечена invariant.group
    ; оптимизатор может предположить что данные уже прочитаны в %3
    %9 = load void (%struct.A*)**, void (%struct.A*)*** %2, !invariant.group !{}
    %10 = getelementptr inbounds void (%struct.A*)*, void (%struct.A*)** %9, i64 1
    ; чтение адреса метода g() из виртуальной таблицы,
    ; инструкция содержит метаданные !invariant.load
    %11 = load void (%struct.A*)*, void (%struct.A*)** %10, !invariant.load !{}
    tail call void %11(%struct.A* %1)
}

Обработку этих метаданных берет на себя модуль MemDep. В итоге после оптимизации (-std=c++17 -O2 -fstrict-vtable-pointers) мы получаем следующее: 

define dso_local void @test()
{
    ; запрос объекта
    %1 = tail call %struct.A* @get_object()
    %2 = bitcast %struct.A* %1 to void (%struct.A*)***
    ; чтение виртуального указателя, избыточные чтения удалены
    %3 = load void (%struct.A*)**, void (%struct.A*)*** %2, !invariant.group !{}
    ; чтение адреса метода f() из виртуальной таблицы
    %4 = load void (%struct.A*)*, void (%struct.A*)** %3, !invariant.load !{}
    ; три косвенных вызова метода f()
    tail call void %4(%struct.A* %1)
    tail call void %4(%struct.A* %1)
    tail call void %4(%struct.A* %1)
    ; смещение адреса виртуальной таблицы до записи с адресом метода g()
    %5 = getelementptr inbounds void (%struct.A*)*, void (%struct.A*)** %3, i64 1
    ; чтение адреса метода g() из виртуальной таблицы,
    ; виртуальный указатель уже прочитан
    %6 = load void (%struct.A*)*, void (%struct.A*)** %5, !invariant.load !{}
    ; косвенный вызов метода g()
    tail call void %6(%struct.A* %1)
}

И после генерации кода back-end’ом: 

test():
        push    r15
        push    r14
        push    rbx
        call    get_object()
        mov     rbx, rax
        mov     rax, qword ptr [rax]
        mov     r14, qword ptr [rax]
        mov     r15, rax
        mov     rdi, rbx
        call    r14
        mov     rdi, rbx
        call    r14
        mov     rdi, rbx
        call    r14
        mov     rdi, rbx
        mov     rax, r15
        pop     rbx
        pop     r14
        pop     r15
        jmp     qword ptr [rax + 8]

Проблема внешнего конструктора

Проблема внешнего конструктора решается с помощью техники assumption loads. Это набор дополнительных инструкций, которые генерируются после вызова конструктора и информируют компилято

© Habrahabr.ru