Почему полиморфизм времени выполнения не может быть решен во время компиляции?

Question

Почему полиморфизм времени выполнения не может быть решен во время компиляции?

считаем:

#include<iostream>
using namespace std;

class Base
{
    public:
        virtual void show() { cout<<" In Base n"; }
};

class Derived: public Base
{
    public:
       void show() { cout<<"In Derived n"; }
};

int main(void)
{
    Base *bp = new Derived;
    bp->show();  // RUN-TIME POLYMORPHISM
    return 0;
}

почему этот код вызывает полиморфизм времени выполнения и почему он не может быть решен во время компиляции?

6 71

c++ polymorphism

6 ответов:

компиляторы обычно девиртуализируют такие вызовы, когда известен статический тип объекта. Вставка кода как есть в Компилятор Обозреватель производит следующую сборку:
main:                                   # @main
        pushq   %rax
        movl    std::cout, %edi
        movl    $.L.str, %esi
        movl    , %edx
        callq   std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
        xorl    %eax, %eax
        popq    %rdx
        retq

        pushq   %rax
        movl    std::__ioinit, %edi
        callq   std::ios_base::Init::Init()
        movl    std::ios_base::Init::~Init(), %edi
        movl    std::__ioinit, %esi
        movl    $__dso_handle, %edx
        popq    %rax
        jmp     __cxa_atexit            # TAILCALL

.L.str:
        .asciz  "In Derived \n"
даже если вы не можете прочитать сборку, вы можете видеть, что только "In Derived \n" присутствует в исполняемом файле. Была оптимизирована не только динамическая отправка, но и весь базовый класс.

79

почему этот код вызывает полиморфизм времени выполнения и почему он не может быть решен во время компиляции?

что заставляет вас думать, что это так?

Вы делаете общее предположение: просто потому что язык определяет этот случай как использование полиморфизма времени выполнения не означает, что реализация удерживается для отправки во время выполнения. Стандарт C++ имеет так называемое правило "как-если":наблюдаемых эффекты из стандартных правил C++ описаны в отношении абстрактной машины, и реализации могут свободно достигать указанных наблюдаемых эффектов, как они хотят.

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

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

некоторые возможности Реал:

вызов a final способ или virtual метод a final класса тривиально devirtualized

вызов a virtual метод класса, определенный в анонимное пространство имен может быть devirtualized, если этот класс является листом в иерархии

вызов a virtual способ через базовый класс может быть devirtualized, если динамический тип объекта может быть установлен во время компиляции (как в случае, например, с построением в одну и ту же функцию)

для тем не менее, вы захотите прочитать блог Хонзы Губички. Хонза является разработчиком gcc и в прошлом году он работал над спекулятивный Реал: цель состоит в том, чтобы вычислить вероятности динамического типа, являющегося либо A, либо B, либо C, а затем спекулятивно девиртуализировать вызовы примерно так же, как преобразование:
Base& b = ...;
b.call();
в:
Base& b = ...;
if      (b.vptr == &VTableOfA) { static_cast<A&>(b).call(); }
else if (b.vptr == &VTableOfB) { static_cast<B&>(b).call(); }
else if (b.vptr == &VTableOfC) { static_cast<C&>(b).call(); }
else                           { b.call(); } // virtual call as last resort
Хонза сделал сообщение из 5 частей:

Девиртуализация в C++, часть 1

Девиртуализация в C++, часть 2 (низкоуровневая девиртуализация среднего уровня путем пересылки хранилищ в нагрузки)

Девиртуализация в C++, часть 3 (построение иерархии типов)

Девиртуализация в C++, часть 4 (анализ графа наследования типов для удовольствия и прибыли)

Девиртуализация в C++, часть 5 (обратная связь управляемая девиртуализация)

28

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

во-первых, модель компиляции C++ основана на отдельных единицах компиляции. Когда компилируется один модуль, компилятор знает только то, что определено в исходном файле(файлах), являющемся составленный. Рассмотрим блок компиляции с базовым классом и функцией, взятой ссылкой на базовый класс:
struct Base {
    virtual void polymorphic() = 0;
};
void foo(Base& b) {b.polymorphic();}
при компиляции отдельно компилятор не знает о типах, которые реализуют Base и таким образом не может удалить динамическую отправку. Это также не то, что мы хотим, потому что мы хотим, чтобы иметь возможность расширить программу с новыми функциональными возможностями, реализуя интерфейс. Это может быть возможно сделать в ссылка время, но только при условии что программа полностью завершена. Динамические библиотеки могут нарушить это предположение, и, как видно из следующего, всегда будут случаи, когда это вообще невозможно.

более фундаментальная причина исходит из теории вычислимости. Даже с полной информацией невозможно определить алгоритм, который вычисляет, будет ли достигнута определенная строка в программе или нет. Если бы вы могли, вы могли бы решить проблему остановки: для программы P Я создаю новую программу P' добавив дополнительную строку в конец P. Теперь алгоритм сможет решить, достигнута ли эта линия, что решает проблему остановки.

неспособность решить в целом означает, что компиляторы не могут решить, какое значение присваивается переменным в целом, например
bool someFunction( /* arbitrary parameters */ ) {
     // ...
}

// ...
Base* b = nullptr;
if (someFunction( ... ))
    b = new Derived1();
else
    b = new Derived2();

b->polymorphicFunction();
даже когда все параметры известны во время компиляции, невозможно вообще доказать, какой путь через программу будет взят и какой статический тип b буду иметь. Приближений и производятся путем оптимизации компиляторов, но всегда есть случаи, когда это не работает.

сказав это, компиляторы C++ очень стараются удалить динамическую отправку, потому что она открывает много других возможностей оптимизации в основном от возможности встроить и распространять знания через код. Если вам интересно, вы можете найти интересные серьезные сообщения в блоге для GCC реализации Реал.

11

Это может быть легко решена во время компиляции, если оптимизатор решил сделать это.

стандарт определяет такое же поведение, как если бы полиморфизм времени выполнения произошел. Это не специфично, что достигается за счет фактического полиморфизма времени выполнения.

10

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

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

последнее не позволяет решить проблему, если вызов может быть devirtualized в общем случае.

The остановить проблема заключается в том, чтобы решить, остановится ли программа с учетом ввода (мы говорим, что программа-входная пара останавливается). Известно, что общего алгоритма нет например,компилятор, что решает для всех возможных пар программа-вход.

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

для этого компилятор должен иметь алгоритм A, который решает, что данная программа P1 и программа P2, где P2 делает виртуальный вызов, затем программа P3 { while ({P1,I} != {P2, I} ) } останавливается для любого ввода I.

таким образом,компилятор, чтобы иметь возможность вычислить всю возможную девиртуализацию, должен иметь возможность решить, что для любой пары (P3, I) над всеми возможными P3 и I;что неразрешимо для всех, потому что A не существует. Однако это может быть решено для конкретных случаев,которые могут быть сосредоточены.

поэтому в вашем случае вызов может быть devirtualized, но не любой случай.

1

Paul Evans · Accepted Answer · 2015-12-20 01:23:07

потому что в общем случае, это невозможно во время компиляции, чтобы определить, какой тип он будет во время выполнения. Ваш пример может быть разрешен во время компиляции (см. ответ @Quentin), но могут быть построены случаи, которые не могут, например:
Base *bp;
if (rand() % 10 < 5)
    bp = new Derived;
else
    bp = new Base;
bp->show(); // only known at run time
EDIT: благодаря @nwp, вот гораздо лучший случай. Что-то вроде:
Base *bp;
char c;
std::cin >> c;
if (c == 'd')
    bp = new Derived;
else
    bp = new Base;
bp->show(); // only known at run time 
также, по следствию доказательство Тьюринга, можно показать, что в общем случае компилятор C++ математически не может знать, на что указывает указатель базового класса во время выполнения.

предположим, что у нас есть компилятор C++ - подобная функция:
bool bp_points_to_base(const string& program_file);
, который принимает в качестве входного параметра program_file имя любой C++ исходный код текстовый файл, где указатель bp (как в ОП) называет его virtual функции-члена show(). И может определить в общем случае (в точке последовательности A здесь virtual функции-члена show() сначала вызывается через bp): является ли указатель bp указывает на экземпляр Base или нет.

рассмотрим следующий фрагмент программы на C++ "q.cpp":
Base *bp;
if (bp_points_to_base("q.cpp")) // invokes bp_points_to_base on itself
    bp = new Derived;
else
    bp = new Base;
bp->show();  // sequence point A
теперь, если bp_points_to_base определяет, что в "q.cpp": bp указывает на экземпляр Base at A тогда "q.cpp-очки bp Для что-то еще в A. И если он определит, что в "q.cpp": bp не указывает на экземпляр Base at A, тогда "q.cpp" точки bp экземпляр Base at A. Это противоречие. Поэтому наше первоначальное предположение неверно. Так что bp_points_to_base не может быть написано для общий случай.