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

Моя цель - предложение широкого ассортимента товаров и услуг на постоянно высоком качестве обслуживания по самым выгодным ценам.

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



Девиртуализация — это крайне важная оптимизация компилятора, которая позволяет заменить виртуальные (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<A*>(d);
C *c = dynamic_cast<C*>(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. Это набор дополнительных инструкций, которые генерируются после вызова конструктора и информируют компилятор о фактическом значение виртуального указателя нового объекта. Напомним, что из-за внешнего конструктора традиционный подход к девиртуализации не справляется с вызовами.


Рассмотрим пример с отключенным инлайненгом (x86-64 clang 10.0.0 -std=c++17 -O2 -fno-inline -fstrict-vtable-pointers):


struct A
{
    virtual void f();
};

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

define void @test()
{
    %1 = call dereferenceable(8) i8* @New(i64 8)
    %2 = bitcast i8* %1 to %struct.A*
    ; вызов конструктора объекта A::A()
    call void @Constructor_A(%struct.A* nonnull %2)
    %3 = bitcast i8* %1 to i8***
    ; читаем адрес сохраненный в виртуальном указателе
    ; важно что чтение также сопровождается метаданными invariant.group
    %4 = load i8**, i8*** %3, !invariant.group !{}
    ; сравниваем прочитанное значение с адресом виртуальной таблицы для класса A
    %5 = icmp eq i8** %4, @VTABLE_A
    ; вызываем llvm.assume и передаем результат сравнения.
    call void @llvm.assume(i1 %5)
    ; в итоге прямой вызов метода A::f()
    call void @f(%struct.A* nonnull %2)
    ret void
}

; конструктор класса A
define void @Constructor_A(%struct.A* %0)
{
    %2 = getelementptr %struct.A, %struct.A* %0, i64 0, i32 0
    ; сохранение адреса виртуальной таблицы A в виртуальный указатель объекта
    store i32 (...)** @VTABLE_A, i32 (...)*** %2, !invariant.group !{}
    ret void
}

После вызова конструктора генерируются три дополнительные инструкции:


  1. Чтение виртуального указателя вновь созданного объекта. Чтение сопровождается метаданными invariant.group.
  2. Сравнение загруженного адреса виртуальной таблицы с адресом предполагаемой таблицы (исходя из типа объекта);
  3. Вызов и передача результата сравнения в @llvm.assume. Встроенная функция @llvm.assume не генерирует ни каких дополнительных инструкций. Семантически вызов похож на assert на уровне оптимизатора и позволяет предположить, что переданный результат сравнения всегда истинен, если условие нарушается, то дальнейшее поведение считается неопределенным.

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


В случае когда удалось встроить конструктор, все инструкции выше могут быть оптимизированы:


    %1 = call dereferenceable(8) i8* @New(i64 8)
    %2 = bitcast i8* %1 to %struct.A*
    %3 = bitcast i8* %1 to i8***
    ; встроенный конструктор,
    ; сохраняем адрес виртуальной таблицы в виртуальном указателе.
    ; запись помечена invariant.group, это значит  что в рамках этой инвариантной группы
    ; в этом виртуальном указателе может быть сохранен только @VTABLE_A
    store i32 (...)** @VTABLE_A, i32 (...)*** %3, !invariant.group !{}
    ; читаем адрес сохраненный в виртуальном указателе.
    ; чтение сопровождается метаданными invariant.group
    ; чтение принадлежит той же инвариантной группе, что и запись выше.
    ; у оптимизатора уже есть информация, что по этому адресу может быть записан только @VTABLE_A
    ; и чтение может быть заменено на @VTABLE_A
    %4 = load i8**, i8*** %3, !invariant.group !{}
    ; после оптимизации чтения это условие всегда true: @VTABLE_A == @VTABLE_A
    %5 = icmp eq i8** %4, @VTABLE_A
    ; вызов llvm.assume(true) можно удалить
    call void @llvm.assume(i1 %5)

Барьеры оптимизации


Существует ряд семантических случаев, когда виртуальный указатель меняет свое значение:


  • Конструкторы. Конструктор каждого класса в иерархии инициализирует виртуальный указатель адресом своей виртуальной таблицы;
  • Деструкторы. Деструкторы каждого класса восстанавливают значение виртуального указателя для безопасного использования виртуальных методов;
  • Placement new. Выражение завершает время жизни объекта (если используется тривиальный деструктор) и переиспользует выделенную под него память, создав там другой объект. В результате меняется динамический тип и соответственно значение виртуального указателя. Возвращает указатель, для доступа к новому объекту.

В рамках семантики инвариантных групп у инструкций чтения и записи нам нужны инструменты, чтобы сообщить оптимизатору, что информация об инварианте обновилась или ее не нужно учитывать. Необходимо предусмотреть случай сравнения двух указателей в рамках оптимизации. Указатели могут ссылаться на одну и туже область памяти, но на объекты с разным временем жизни. Равенство таких указателей не должна вводить в заблуждение оптимизатор: оптимизатор не должен иметь возможность выполнить подстановку (substitution). Необходимо выразить концепцию equal-but-not-equivalent.


LLVM вводит две дополнительные операции: strip и launder.


Операция strip


Операция strip может использоваться, когда нам нужен указатель на те же данные с возможностью доступа к ним, но без инвариантной информации установленной метаданными invariant.group.
Операция представлена новой встроенной функцией @llvm.strip.invariant.group. Функция возвращает новый указатель, который является псевдонимом (alias) переданному аргументу, т.е. указывает и может использоваться для доступа к той же памяти что и аргумент и убирает ассоциацию указателя с инвариантной группой.


Свойства операции:


  • Операция является детерминированной и не обладает побочными эффектами. Т.е. возвращаемое значение зависит только от переданного аргумента. Такие операции часто называются чистыми (pure);
  • Возвращает псевдоним аргумента (alias). Возвращает указатель, который указывает и может использоваться для доступа к той же памяти что и аргумент;
  • strip(X) == strip(strip(X)). Т.к. операция не берет во внимание ассоциированные инвариантные данные.

Один из случаев использования операции strip — это сравнение указателей:


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

    ...
    ; читаем адрес виртуальной таблицы а
    %vtable_a = load void (%struct.A*)**, void (%struct.A*)*** %a, !invariant.group !{}
    ...
    ; if(a == b)
    %res = icmp eq %struct.A* %a, %b
    br %res, label %if, label %after
    if:
        ; если %b будет заменен на %a,
        ; то оптимизатор заменить чтение адреса виртуальной таблицы %vtable_b
        ; на уже прочитанный %vtable_a.
        ; т.к. чтение сопровождается метаданными invariant.group
        %vtable_b = load void (%struct.B*)**, void (%struct.B*)*** %b, !invariant.group !{}
        ...
    ...

Проблема в том, что LLVM основываясь на результате сравнения a и b может заменить SSA значение b на a (в проходе GVN). Это абсолютно легальная оптимизация. Но в рамках девиртуализации и обработки инвариантов, такая замена приведет к неопределенному поведению, потому что при втором вызове метода f() будет использоваться не та виртуальная таблица.


Решение заключается в сравнение указателей без учета инвариантной информации:


    ...
    ; читаем адрес виртуальной таблицы a
    %vtable_a = load void (%struct.A*)**, void (%struct.A*)*** %a, !invariant.group !{}
    ...
    ; if(a == b)
    ; сравниваем указатели без инвариантов
    ; strip_a и strip_b имеют доступ и указывают на ту же область,
    ; на которую указывают a и b соответственно
    %strip_a = call i8 * @llvm.strip.invariant.group(i8 * %a)
    %strip_b = call i8 * @llvm.strip.invariant.group(i8 * %b)
    %res = icmp eq %struct.A* %strip_a, %strip_b
    br %res, label %if, label %after
    if:
        ; Равенство псевдонимов не является достаточной причиной для оптимизатора,
        ; чтобы выполнить подстановку исходных указателей
        %vtable_b = load void (%struct.B*)**, void (%struct.B*)*** %b, !invariant.group !{}
        ...
    ...

Операция launder


Операция launder используется, когда нам нужен указатель на те же данные с возможностью доступа к ним, но c очищенной информацией об инварианте.
Операция представлена новой встроенной функцией @llvm.launder.invariant.group. Функция возвращает новый указатель, который является псевдонимом (alias) переданному аргументу, т.е. указывает и может использоваться для доступа к той же памяти что и аргумент и ассоциирует указатель с новой инвариантной группой. Т.е. переданный в функцию указатель и новый указатель, в контексте обработки метаданных invariant.group на операциях чтения и записи, рассматриваются как два разных указателя.


Свойства операции:


  • Операция по своей сути является недетерминированной. Ни какие два вызова не возвращают одинаковое значение;
  • Возвращает псевдоним аргумента (alias). Возвращает указатель, который указывает и может использоваться для доступа к той же памяти что и аргумент;
  • strip(x) == strip(launder(x)).

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


В случае конструктора/деструктора, каждый класс-потомок передает в конструктор/деструктор базового класса launder(this):


; конструктор класса A
define void @Constructor_A(%struct.A* %0)
{
    %2 = getelementptr %struct.A, %struct.A* %0, i64 0, i32 0
    ; запись адреса виртуальной таблицы A
    store i32 (...)** @VTABLE_A, i32 (...)*** %2, !invariant.group, !{}
    ret void
}

; конструктор класса B
define void @Constructor_B(%struct.B* %0)
{
    %2 = bitcast %struct.B* %0 to i8*
    ; запрос нового указателя с новой инвариантной группой launder(this)
    %3 = call i8* @llvm.launder.invariant.group(i8* %2)
    %4 = bitcast i8* %3 to %struct.A*
    ; передача launder(this) в конструктор базового класса A
    call void @Constructor_A(%struct.A* %4)
    %5 = getelementptr %struct.B, %struct.B* %0, i64 0, i32 0, i32 0
    ; запись адреса виртуальной таблицы B
    store i32 (...)** @VTABLE_B, i32 (...)*** %5, !invariant.group, !{}
    ret void
}

Детально рассмотрим случай выражения placement new:


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

Если мы используем умалчиваемую реализацию оператора размещающего new, то указатель a будет побитово равен указателю b. Но в рамках объектной модели C++, a и b указывают на разные объекты: a указывает на объект типа A, время жизни которого завершено, b указывает на вновь созданный, в той же области памяти, объект типа B. Соответственно, в контексте девиртуализации вызов b->f() должен загружать правильную виртуальную таблицу: таблицу класса B и указатели a и b не должны рассматриваться как эквивалентные. С помощью операции launder оптимизатор может достичь описанной семантики.


define void @test()
{
    ; new expression
    ; вызов оператора new
    %1 = call dereferenceable(8) i8* @New(i64 8)
    %2 = bitcast i8* %1 to %struct.A*
    ; создание объекта типа A, вызов конструктора A
    %3 = call %struct.A* @Constructor_A(%struct.A* nonnull %2)
    %4 = bitcast i8* %1 to void (%struct.A*)***
    ; чтение виртуального указателя созданного объекта типа A
    ; т.к. чтение сопровождается метаданными invariant.group
    ; для указателя регистрируется новая инвариантная группа
    %5 = load void (%struct.A*)**, void (%struct.A*)*** %4, !invariant.group !{}
    %6 = load void (%struct.A*)*, void (%struct.A*)** %5, !invariant.load !{}
    ; косвенный вызов A::f(). После того как оптимизатор заинлайнет конструктор
    ; (или сделает предположение о значение виртуального указателя, assumtion loads)
    ; вызов будет девиртуализирован в прямой вызов A::f()
    call void %6(%struct.A* nonnull %2)

    ; placement new expression
    ; создание нового указателя и
    ; ассоциация его с новой инвариантной группой.
    ; указатель ссылается и имеет доступ к области памяти,
    ; которая была выделена ранее под объект типа A
    %7 = call i8* @llvm.launder.invariant.group(i8* nonnull %1)
    %8 = bitcast i8* %7 to %struct.B*
    ; создание объекта типа B, вызов конструктора B
    ; в конструктор передается новый указатель
    ; это важно т.к. конструктор меняет значение виртуального указателя
    %9 = call %struct.B* @Constructor_B(%struct.B* nonnull %8)
    %10 = bitcast i8* %7 to void (%struct.B*)***
    ; чтение виртуального указателя созданного объекта типа B
    ; оптимизатор не сможет здесь использовать ранее загруженную таблицу для старого объекта
    ; т.к. указатели принадлежат разным инвариантным группам.
    %11 = load void (%struct.B*)**, void (%struct.B*)*** %10, !invariant.group !{}
    %12 = load void (%struct.B*)*, void (%struct.B*)** %11, !invariant.load !{}
    ; косвенный вызов B::f(). После того как оптимизатор заинлайнет конструктор
    ; (или сделает предположение о значение виртуального указателя, assumtion loads)
    ; вызов будет девиртуализирован в прямой вызов B::f()
    call void %12(%struct.B* nonnull %8)
    ret void
}

Важно, что операции strip и launder возвращают псевдонимы (aliases) своих аргументов, это не дает оптимизатору выполнить неверную подстановку, но дает возможность делать предположения о значение, не позволяя подавлять существующие оптимизации. Вызовы соответствующих функций удаляются перед фазой генерации кода back-end'ом и не несут нагрузки на выполнение и размер объектного кода.


std::launder


Если посмотреть более внимательно на последний пример использования операции launder с placement new, то можно заметить, что на уровне LLVM IR, указатель b — это не что иное, как launder(a). И семантика выражения размещающего new сводится к следующему:


  1. Запрос нового указателя вызовом функции @llvm.launder.invariant.group на основе переданного аргумента.
  2. Создание нового объекта в заданной области памяти: вызов конструктора. В нашем случае переиспользование памяти завершает время жизни, существующего в переданной области памяти, объекта. В конструктор передается новый указатель, т.к. конструктор меняет значение виртуального указателя (та же семантика, что и при вызове конструктора базового класса). В итоге новый указатель ссылается на новый объект со своим значением виртуального указателя и ассоциирован с "чистой" (новой) инвариантной группой. Этот указатель рассматривается как результат вычисления выражения placement new.

Вернемся к коду и к уже упомянутому состоянию Undefined Behavior:


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

На состояния Undefined Behavior можно смотреть как на компромисс, договоренность между программистом и компилятором. Это набор дополнительных правил и ограничений, позволяющий компилятору генерировать более эффективный код. В нашем случае оптимизатор эксплуатирует объектную модель C++ и описанное неопределенное поведение, что бы реализовать девиртуализацию методов. Если девиртуализация не используется, то второй вызов a->f() будет иметь ожидаемое поведение: косвенный вызов B::f(). Но с описанной моделью девиртуализации, вызов a->f() будет оптимизирован в прямой вызов A::f(). Вызов b->f() всегда имеет ожидаемой поведение, т.к. указатель учитывает состояние инварианта и не позволяет оптимизатору выполнить подстановку (substitution), т.е. использовать, прочитанные для исходного объекта, данные в рамках вновь созданного объекта.


Операция launder позволяет правильно оперировать инвариантными группами в рамках девиртуализации. С++ дает возможность принудительно генерировать вызов операции в промежуточном представление.


Вызов std::launder — это принудительная (ручная) генерация вызова функции @llvm.launder.invariant.group в IR. Точная реализация на стороне IR зависит от настройки компиляции и обрабатываемого типа. Если мы не используем описанную модель девиртуализации (флаг -fstrict-vtable-pointers) или обрабатываем не полиморфный тип, то в IR просто генерируется алиасный указатель.


Таким образом, исходя из семантики выражения placement new эти две реализации функции test генерируют один и тот же код и не приводят к неопределенному поведению:


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


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


Использование std::launder


Мотивирующий пример из стандарта:


struct X
{
    const int n;
};

void test()
{
    X *p = new X{1};
    const int a = p->n;
    X *p1 = new (p) X{2};
    // определенное поведение
    const int b = p1->n;
    // неопределенное поведение, значение p->n может быть 1.
    const int c = p->n;
    // определенное поведение
    const int d = std::launder(p)->n;

}

Выше мы описывали, что такое заменяемый тип (transparently replaceable) в терминах объектной модели C++. После переиспользования памяти, все имена, ссылки и указатели ссылающиеся на исходный объект, станут автоматически указывать на вновь созданный объект, только если типы исходного и нового объекта являются заменяемыми.


В этом примере как и в примере с девиртуализацией неопределенное поведение обусловлено тем, что типы не являются заменяемыми, из-за наличия константных полей. Это дает возможность оптимизатору предположить, что динамический тип объекта измениться не может и значение константного поля не меняется. Поэтому значение поля n можно прочитать только один раз и заменить все дальнейшие чтения этого поля через данный указатель на прочитанное значение. Ситуация аналогичная чтению виртуального указателя. Указатели p1 или std::launder(p) должны учитывать состояние инвариантов и не позволять оптимизатору выполнить подстановку (substitution), т.е. использовать, прочитанные для исходного объекта, данные (значение a) в рамках вновь созданного.


Более абстрактно семантику std::launder можно свести к следующему:


Функция всегда возвращает указатель на текущий объект размещенный в памяти, запрещая в точке вызова выполнять подстановку ранее прочитанных данных исходного объекта, если мы нарушили требования к заменяемым типам. Тем самым избежав неопределенного поведения.

Из определения этой семантики можно сделать следующие выводы:


  • std::launder не оказывает ни какого эффекта, если аргумент не указывает на объект, время жизни которого закончилось, после переиспользования памяти.
  • В области памяти, на который ссылается аргумент функции, должeн существовать новый объект, который переиспользует память.

Ограничения на использование ссылок и констант в таком контексте было введено еще в C++03 3.8 §7. Но, на данный момент ни один из популярных компиляторов (GCC, Clang, MSVC) не эксплуатирует это неопределенное поведение. Следует отметить только компилятор IBM XL, который выполняет подобную оптимизацию константных полей, но только в ограниченных случаях:


struct A
{
    const int x;
    int y;
};

// оптимизация выполняется только для static storage duration
A a = { 42, 0 };

void foo();

int test()
{
    // внешняя функция, компилятор не видит определения
    foo();
    // чтение a.х заменяется на 42
    return a.x;
}

Причин, почему компиляторы не делают такую const/reference оптимизацию несколько. До введения функции std::launder избежать неопределенного поведения можно было только использовав возвращаемое значение placement new. Но, на практике, не всегда легко это сделать, например:


template <typename T>
union Storage
{
    constexpr Storage(T &&v)
        : value(std::forward<T>(v))
    {}

    unsigned char dummy;
    T value;
};

template <typename T>
struct SimpleOptional
{
    constexpr SimpleOptional(T&& v)
        : storage{std::forward<T>(v)}
    {}

    template <typename... Args>
    void emplace(Args&&... args)
    {
        storage.value.~T();
        ::new (&storage.value) T{std::forward<Args>(args)...};
    }

    constexpr const T& operator*() const
    {
        // чтение значение может привести к неопределенному поведению
        // после переиспользования памяти
        return storage.value;
    }

private:
    Storage<T> storage;
};

struct A
{
    const int x;
    int y;
}

void test()
{
    SimpleOptional<A> so = A{1, 0.5f};
    const int n = (*so).x;
    so.emplace(2, 0.4f);
    // неопределенное поведение, x может быть равен 1 или 2
    const int n1 = (*so).x;
}

В данном случае, чтобы избежать неопределенного поведения придется отдельно хранить результат выражения placement new.


Более интересный пример — это стандартные аллокаторы. Точнее метод construct, который используя placement new, возвращает void. Такой интерфейс аллокаторов приводит к неопределенному поведению при использование стандартных контейнеров, например, std::vector с элементами содержащими константные или ссылочные поля. Заметим, что до С++11 использование таких типов в стандартных контейнерах было невозможно. С приходом C++11 и move-семантики этого ограничение не стало.


Пример использования в контейнере:


template <typename T, typename A = std::allocator<T>>
class vector
{
public:
    using allocator_traits = typename std::allocator_traits<A>;
    using pointer = typename allocator_traits::pointer pointer;
    ...
public:
    ...
    void push_back(const T& value)
    {
        // reserve
        ...
        // вызов std::allocator::construct,
        // использование placement new и игнорирование возвращаемого значения
        allocator_traits::construct(allocator, end, value);
        ++end;
    }

    T& operator[] (size_t i)
    {
        // чтение значение может приводит к неопределенному поведению
        // после переиспользования памяти в случае нарушения требований 
        // к заменяемым типам
        return begin[i];
    }
    ...
private:

    pointer begin;
    pointer end;
    A allocator;
    size_t capacity;
};

struct A
{
    const int x;
    int y;
};

void test()
{
    vector<X> c;
    c.push_back(X{1});
    c.clear();
    c.push_back(X{2});
    // неопределенное поведение
    assert(c[0].x == 2);
}

Использование std::launder в общем случае так же не может решить проблему с использованием стандартных аллокаторов:


...
    using pointer = typename allacoter_traits::pointer pointer;
...
    T& operator[] (size_t i)
    {
        // тип pointer в общем случае может не быть указателем
        // в этом случае мы не можем использовать std::launder
        return std::launder(begin)[i];
    }

В результате использование стандартных аллокаторов с пользовательскими типами, содержащими константные или ссылочные поля и стандартных контейнеров будет приводить к неопределенному поведению. Эта одна из причин, почему начиная с C++17 метод construct помечен как deprecated и удален в C++20. И в конечном итоге в C++20 изменили требования к заменяемым типам, убрав ограничение на наличие константных и ссылочных подобъектов в пользовательских типах данных RU007. Поэтому пример выше формально больше не приводит к неопределенному поведению.


Заключение


К счастью, стандарт языка C++ не разрабатывается в вакууме. Автор std::launder и связанных с ним изменений является также тех.лидом в Clang и одним из авторов новой модели девиртуализации. Новые требования и std::launder хорошо ложатся в архитектуру Clang, чего нельзя сказать о GCC. В GCC эта фича до сих пор носит статус экспериментальной и не во всех случаях работает правильно. Например, Bug 95349.



Буду рад комментариям и предложениям (можно по почте yegorov.alex@gmail.com)
Спасибо!

Источник: https://habr.com/ru/post/540954/

Вернуться к списку

Интересные статьи

Интересные статьи

Как быстро получить много данных от Битрикс24 через REST API
Как быстро получить много данных от Битрикс24 через REST API
Нередко при работе с Bitrix24 REST API возникает необходимость быстро получить содержимое определенных полей всех элементов какого-то списка (например, лидов). Традиционн...
Разработка бизнес-процесса в битрикс24. Советы директору
Разработка бизнес-процесса в битрикс24. Советы директору
Одна из самых важных (на мой взгляд) функций в Битрикс24 это бизнес-процессы. Теоретически они позволяют вам полностью избавиться от бумажных служебок и перенести их в эл...
Электронная амеба и задача коммивояжера
Электронная амеба и задача коммивояжера
Какой самый ценный ресурс на планете? Нефть, вода или может чистый воздух? Самый ценный ресурс, по мнению многих, это время. Его всегда не хватает, люди постоянно куда-то спешат, а лю...
Система контроля библиотеки на Flask-Potion, Часть 0: готовим всё, что понадобится
Введение В своей работе я уже некоторое время использую Flask-Potion — фреймворк, основными достоинствами которого являются: весьма удобная интеграция с SQLAlchemy моделями, автогенерация crud-э...
Автоматически импортируем избранные библиотеки в IPython или Jupyter Notebook
Автоматически импортируем избранные библиотеки в IPython или Jupyter Notebook
Всем привет! Сегодня мы разберем очень короткий, но полезный лайфхак о том, что нужно сделать, чтобы не вводить, к примеру, «import pandas as pd» по 10 раз в день. Для этого нужно: Перейт...