08.06.2020 13:16
robofreak 19 3500 Источник
Сегодня речь пойдет про одну интересную идиому, которую ввел Шон Парент (Adobe) — известный деятель в C++-сообществе. Он часто выступает с докладами и публикует цикл статей Better Code. Одна из его идей, которую используют в Photoshop — это Concept-Based Polymorphism. Это когда мы реализуем полиморфизм не через явное наследование, а с помощью техники, включающей обобщенное программирование, и по итогам получаем некоторые дополнительные преимущества.

Статья устроена следующим образом:

  1. Что вообще такое Concept-Based Polymorphism и зачем он нужен
  2. Немного про LLVM и ее устройство
  3. Пример Concept-Based Polymorphism в LLVM PassManager
  4. Преимущества подхода



Картинка, иллюстрирующая тезис «Наследование — это зло». Источник


Что вообще такое Concept-Based Polymorphism и зачем он нужен


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

Явное использование наследования зачастую приводит к избыточной связности кода и нарушению принципа разделения интерфейса (ISP). Как реализовать динамический полиморфизм без этих недостатков?

Шон Парент предложил идиому под названием Concept-Based Polymorphism, где наследование неявно, и оно скрыто от пользователя. Подробнее об этом можно узнать из его доклада Inheritance Is The Base Class Of Evil — где он показывает всю идею на примере Photoshop и истории действий — вы узнаете, как работает в действительности «историческая кисть».

Немного про LLVM и ее устройство


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



Так выглядит архитектура LLVM, и в принципе, любого современного компилятора

Основные части такие:

  • Front End берет исходный код программы и превращает его в промежуточное представление (intermediate representation, IR). Это упрощает работу всего остального компилятора, чтобы он не разбирался со сложным C++-кодом.
  • Middle End — набор оптимизаций, анализов и трансформаций. В самом общем виде представляет собой набор проходов (Passes). Все проходы регистрируются и запускаются специальной компонентной, называемой PassManager.
  • Back End генерирует непосредственно целевой код.

Компилятор представляет программу в виде нескольких основных сущностей. Это модуль (условно .cpp-файл), функция, базовый блок, который содержит в себе набор инструкций.



Сейчас в LLVM есть две версии PassManager: 

  • LegacyPassManager, в нем используется классический run-time полиморфизм, основанный на наследовании. В иерархию наследования входят проходы, запускаемые на модуль, функцию, цикл и т.д. 
  • PassManager — новая версия, как раз на основе Concept-Based полиморфизма, она предлагается на замену LegacyPassManager. Обе версии существуют параллельно и развиваются независимо.

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

Пример Concept-Based Polymorphism в LLVM PassManager


Как реализовано в Legacy


Вначале, как всё устроено классически, в LegacyPassManager. Допустим, у нас есть некий класс PassManager и есть класс Pass — один проход. Имеем такую иерархию: ModulePass, от которого идет наследование нашего класса, к примеру Constant Propagation. Есть метод runOnModule, здесь он виртуальный. Итак, мы имеем обычный runtime-полиморфизм:

/// ModulePass class - This class is used to implement unstructured
/// interprocedural optimizations and analyses. ModulePasses may do anything
/// they want to the program.
///
class ModulePass : public Pass {
...
/// runOnModule - Virtual method overriden by subclasses to process the module
/// being operated on.
virtual bool runOnModule(Module &M) = 0;
};

...

/// IPCP - The interprocedural constant propagation pass
///
struct IPCP : public ModulePass {
...
bool runOnModule(Module &M) override;
};

Давайте посмотрим на код, в чем здесь проблема? Мы видим, что в этой иерархии методы запуска прохода различны в зависимости от того, над чем они должны выполняться (над функцией — runOnFunction, модулем — runOnModule, циклом — runOnLoop и тд). В свою очередь, это делает невозможным обрабатывать коллекцию проходов, которые работают с разными IR сущностями, единым способом (собственно применять полиморфизм). Казалось бы, очевидно, как сделать правильно: нужен виртуальный метод run, который будет переопределяться в наследниках. Но тут же возникает проблема: у методов run в классах-наследниках будет разная сигнатура, поскольку передается параметр всегда своего типа — функция, модуль и так далее. Значит, придется делать фиктивный базовый класс для Module, Function и т.д., передавать в run указатель на этот класс, а внутри метода делать down-cast, в зависимости от того, что за объект находится по данному указателю. И начинается что-то странное: при появлении новой нижестоящей сущности мы вынуждены теперь переписывать каждый раз вышестоящий код, что противоречит всем принципам проектирования.

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

Как было предложено в новой версии


В новом PassManager происходит следующее. Понятие полиморфного объекта обобщаем следующим образом. Говорим, что если объект реализует какой-то метод, то мы вводим набор методов, которые мы хотим, чтобы были полиморфные, и говорим, что все классы, которые реализуют данный метод, являются полиморфными, то есть мы можем их использовать во взаимозаменяемых контекстах в этом PassManager.

Рассмотрим класс PassManager в LLVM. Здесь приведена его упрощенная версия, а полную можно посмотреть в llvm/include/llvm/IR/PassManager.h. Шаблонный параметр IR специализируется непосредственно сущностью, над которой мы выполняем проход (функция run). Это может быть модуль, функция либо цикл. Смотрим код, дальше будут пояснения:

template <typename IR, typename... ArgTs> class PassManager {
public:
     void run(IR& ir, ArgTs... args) {
         for (auto& Pass : Passes) {
             Pass->run(ir, args...);
         }
     }

     template <typename PassT>
     void addPass(PassT Pass) {
         Passes.emplace_back(new detail::PassModel<IR, PassT, ArgTs...>(std::move(Pass)));
     }

private:
     std::vector<std::unique_ptr<detail::PassConcept<IR, ArgTs...>>> Passes;

};

Давайте посмотрим на следующие основные сущности:

  • Метод run пробегает по всему вектору проходов, и для каждого прохода вызывает свой метод run
  • Функция addPass нужна для регистрации прохода (добавления его в вектор с остальными проходами) с заданным типом PassT
  • Поле Passes — вектор, который хранит все наши зарегистрированные проходы. Но так как проходы при добавлении имели разные типы, а вектор может хранить только однородные элементы, то для обеспечения такого хранения используется техника type erasure, о которой речь пойдет ниже

Итак, что это должен быть за тип? Что хранится в векторе Passes?

Для начала разберемся, что такое PassModel и PassConcept. Это вспомогательные классы, внутренние для PassManager. Они оба находятся в пространстве имен detail. Вначале посмотрим, как выглядит класс PassConcept. В нем находится опять тот же самый метод run, здесь это чисто виртуальный метод. 

namespace detail {

template <typename IR, typename... ArgTs> class PassConcept {
public:
 
     virtual ~PassConcept() = default;

     virtual void run(IR& ir, ArgTs... args) = 0;

};

Второй класс, PassModel, тоже шаблонный. Он унаследован от PassConcept. 

template <typename IR, typename PassT, typename... ArgTs> class PassModel final : public PassConcept<IR, ArgTs...> {
public:

     explicit PassModel(PassT Pass) : pass_(std::move(pass)) {}

     void run(IR& ir, ArgTs... args) final {
        pass_.run(ir, args...);
     }

private:

     PassT pass_;

};

} // end namespace detail

Что в нем содержится:

  • Приватное поле pass_, имеющее тип PassT
  • Конструктор, который принимает на вход объект типа PassT. Он ничего интригующего не делает, лишь инициализирует pass_ используя семантику перемещения
  • Метод run, который просто вызывает у pass’a метод run. Передавая, соответственно, все аргументы, которые могут там быть.

Вспоминаем теперь, с чего начинали. В свою очередь, PassManager хранит в себе все эти проходы. В векторе Passes из элементов типа PassConcept.

Итак, общая картина. Создается PassManager. С помощью AddPass в нем регистрируются те проходы, которые мы хотим сделать над модулем, функцией циклом и т.д. Например, inline, constant propagation, loop unrolling, etc. Сами они ни от кого не наследуются, они должны только иметь метод run. И как раз вся эта концепция это обеспечивает. Каким образом? 

Допустим, у нас есть Inline-оптимизация. Мы в addPass передаем объект типа Inline. Соответственно в Passes, в вектор, мы кладем этот Inline, уже в виде PassConcept. Как мы можем это сделать? Inline же не наследуется от класса PassConcept. Как же мы положим элемент в вектор? Приведение к базовому типу (upcasting) мы не можем здесь сделать, потому что нет никакого наследования И вот здесь как раз делается такой трюк. У нас есть вот этот вспомогательный класс PassConcept, который определяет интерфейс. Он говорит, что все его наследники должны реализовать метод run. У нас есть PassModel, который в свою очередь шаблонный. И вот, когда кладем Inline, происходит инстанциация этого PassModel с этим типом Inline, внутри этого класса композируется этот объект. Сам PassModel переопределяет run, который для себя вызывает уже run для вот этого прохода, то есть run из класса Inline. Все это в compile-time разруливается: если у нас Inline не определит метод run, у нас будет ошибка времени компиляции. 

Таким образом достигается этот полиморфизм без наследования. Может возникнуть вопрос: а как это нет наследования, ведь вот оно же, PassModel унаследовано от PassConcept? Ответ: тут есть наследование, но оно внутреннее, оно не торчит наружу, пользователь не знает о нем ничего.

Мы говорим на концептуальном уровне. Вот у нас есть пользователь, он хочет переопределить некий метод. При этом он не хочет наследоваться, чтобы лишние зависимости к себе не тянуть. Как это сделать? Мы внутри себя, через PassConcept, PassModel-ом, делаем runtime-полиморфизм, через наследование, но пользователь об этом не знает: это все внутренности этих двух классов, они там в своем namespace определены.

Еще раз, как это достигается? У меня есть класс, назовем его, пусть это будет Inline, в терминах компилятора. Мы добавляем Inline в вектор, соответственно создаем объект PassModel. Он имеет конструктор, который принимает в себя объект вот этого шаблонного параметра. И вот, когда мы в PassManager вызываем метод run, он бежит по всем проходам, в данном случае у нас только один проход, он имеет тип Inline. Он вызывает метод run у PassConcept’а. Тот самый метод run, который внутри PassModel лежит, который инстанциирован типом Inline. И уже этот метод вызывает метод run у зарегистрированного прохода, в данном случае Inline, и в итоге у нас вызывается run у Inline’а.

Преимущества подхода


Вот так мы сделали разное поведение без явного использования наследования. У нас теперь нет явной зависимости, которая была раньше, в LegacyPassManager. 

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

Получается, мы можем всё смешать. В старом PassManager, который Legacy, есть четкое разделение. Там есть модульная оптимизация, которая на модуль делается; есть оптимизация, которая происходит на функцию. А здесь это всё происходит плавно. Мы делаем PassManager, инстанциируем его типом «Модуль», кладем в него Inline, еще что-то, еще какие-нибудь помодульные оптимизации. Потом второй PassManager, инстанциируем его типом «Функция», кладем оптимизации на функцию. И потом в PassManager, который инстанциирован модулем, можно положить другой PassManager, который инстанциирован функцией, через этот вектор Passes. 

PassManager<Module> MPM;
// ... register passes on module
MPM.addPass(GlobalDCEPass())
MPM.addPass(PGOInstrumentationGen());
//... register passes on function
PassManager<Function> FPM; 
FPM.addPass(CallSiteSplittingPass());
//... register all registered passes on function in module pass manager
MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));

Успеваете следить? У нас есть два PassManager’а. Один с типом IR Module, другой с типом IR Function. Допустим, в тот, который с модулем, мы уже положили какое-то количество проходов. Теперь мы хотим перемешать их с проходами, которые выполняются на функцию. Что мы делаем? Мы вызываем addPass и в качестве Pass’а передаем PassManager, который инстанциирован IR-типом «Функция» (в реальном коде там кладется не сам PassManager, а специальный класс, который его оборачивает, но на концептуальном уровне это не имеет значения). 

Таким образом, мы можем перемешивать разные уровни оптимизации — благодаря вложенности PassManager'ов, попеременно выполнять проходы на модуль, на функцию, цикл и т.д. В Legacy PassManager с этим сложнее, там отдельный класс для модулей, который имеет виртуальную функцию runOnModule, отдельный класс для функций c виртуальным методом runOnFunction и т.д. Оба эти класса наследуются от общего предка Pass, но между собой они независимы и имеют различный интерфейс, что делает использование LegacyPassManager неудобным для вызова проходов на разных IR сущностях (модуль, функция, цикл)

Материалы для дополнительного чтения:
 
  • LLVM for Grad Students — Простое введение в LLVM
  • Презентация Чандлера Каррута о том, как устроены проходы в LLVM
  • Презентация Чандлера Каррута о деталях реализации PassManager
  • Тред в mailing-листе, где обсуждается различие между LegacyPassManager и PassManager

Авторы:

Роман Русяев,
Expert Engineer
AI Compiler Team
Samsung R&D Institute, Russia

Скоро Роман выступит на конференции С++ Russia 2020 Moscow вместе с Антоном Полухиным: там они поговорят о настоящем и будущем copy elision: ссылка на доклад

Татьяна Волкова,
Lead Specialist
Business Development Team
Samsung R&D Institute, Russia