С++ Concept-Based Polymorphism в продуктовом коде: PassManager в LLVM

    Сегодня речь пойдет про одну интересную идиому, которую ввел Шон Парент (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


    Samsung
    Компания

    Похожие публикации

    Комментарии 22

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

        Боюсь, что без дополнительных crutches сделать это не получится. В чем здесь проблема

        class PassVisitor {
        public:
            excplicit PassVisitor(Module& M) : M(M) {}
        
            void visit(SomeModulePass& m) { m.runOnModule(/*Ok, we know about module*/M); }
            void visit(SomeFunctionPass& m) { m.runOnFunction(/*What function?*/); }
            void visit(SomeLoopPass& m) { m.runOnLoop(/*What loop?*/); }
        
        private:
            Module& M;
        };
        
        class Pass {
            virtual void accept(PassVisitor &v) = 0;
        };
        
        
        class SomeModulePass : public Pass {
        public:
            void accept(PassVisitor &v) override { v.visit(*this); }
            bool runOnModule(Module& M);
        
        };
        
        class SomeFunctionPass : public Pass {
        public:
            void accept(PassVisitor &v) override { v.visit(*this); }
            bool runOnFunction(Function& F);
        };
        
        class SomeLoopPass : public Pass {
        public:
            void accept(PassVisitor &v) override { v.visit(*this); }
            bool runOnLoop(Loop& L);
        };
        
        /// ...
        
        PassManager pm;
        pm.addPass(SomeModulePass());
        pm.addPass(SomeFunctionPass());
        
        // ...
        
        PassVisitor v(M);
        for (auto& pass : pm.getAllPasses()) {
            pass.accept(v);
        }
        


        Это бы хорошо работало, если бы все пассы работали с единой иерархией классов: нечто, от чего наследуется модуль, функций и т.д. В этом случае мы могли бы сделать визитор на каждую из этих сущностей и, таким образом, применить паттерн Visitor. В нашем же случае получается, что непонятно, какую функцию (или любую другую IR сущность) нужно передавать проходу в функции visit
          0
          Это бы хорошо работало, если бы все пассы работали с единой иерархией классов: нечто, от чего наследуется модуль, функций и т.д. В этом случае мы могли бы сделать визитор на каждую из этих сущностей и, таким образом, применить паттерн Visitor.
          Да, конечно. Тут сложно судить со стороны т.к. не понятно почему, находясь под полным контролем разработчика, классы IR-сущностей не сделаны под общим предком с некоторым интерфейсом, который бы давал последующую возможность добавлять выполнение относительно произвольных действий над ними с помощью Visitor.

          Возможно смысл был в том, чтобы сделать новый PassManager никак не трогая определения классов IR-сущностей, а также и определения классов PassT-сущностей.

          Но здесь тоже «без дополнительных crutches» не обходится: PassT-типы завернули в иерархию PassConcept — PassModel, но поскольку в этом случае виртуальная функция-член run не может быть шаблоном, зависимость от IR-типов вышла на уровень классов и далее перешла и на класс PassManager (т.е. это всё каждый раз совершенно разные типы в зависимости от IR). И чтобы зарегистрировать все проходы в красивый единый вектор требуется некий костыль в виде некоего адаптера
          MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
            +2
            Да, конечно. Тут сложно судить со стороны т.к. не понятно почему, находясь под полным контролем разработчика, классы IR-сущностей не сделаны под общим предком с некоторым интерфейсом, который бы давал последующую возможность добавлять выполнение относительно произвольных действий над ними с помощью Visitor.

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

            Повторюсь еще раз: классы Module, Function и Loop не образуют иерархию и не должны этого делать. Введение для них общего предка — прямое нарушение LSP. Более того, даже если у вас будет этот общий предок и у всех проходов будет один метод run, который будет его принимать, то внутри run вам придется делать down-cast к той сущности, которая нужна этому проходу.

            Возможно смысл был в том, чтобы сделать новый PassManager никак не трогая определения классов IR-сущностей, а также и определения классов PassT-сущностей.

            Об этом и речь. Legacy PM тоже не трогал определение IR-сущностей. А New PM, к тому же, не обязует связывать классы проходов в общую иерархию (строгости ради, стоит заметить, что там есть mixin класс для всех пассов, но это уже другой разговор).

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

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

            template <typename FunctionPassT>
            class ModuleToFunctionPassAdaptor {
            ...
            /*ret val*/ run(Module &M,/*params*/) {
                // ...
                for (Function &F : M) {
                    Pass.run(F, /*args*/);
               // ...
            }
            
            private:
              FunctionPassT Pass
            };
            
              0
              А тут я видимо где-то отстал: можете рассказать, с каких это пор классы-адаптеры стали костылями? В данном случае я никаких костылей не наблюдаю. Ниже привожу код данного адаптера. Как по мне, это совершенно нормальное решение, которое хорошо ложится в данный концепт.
              Если для вас это нормальное решение, то тогда именно поэтому вы костылей не наблюдаете. По иронии в GoF паттерн Visitor описывается как раз на примере с компилятором.

              Повторюсь еще раз: классы Module, Function и Loop не образуют иерархию и не должны этого делать. Введение для них общего предка — прямое нарушение LSP.
              А как определить должны или не должны? А как определили что все PassModel вместо этого должны иметь общего предка PassConcept? Не могу понять это «нарушение LSP» или нет.

              Потому что введение дополнительных сущностей только ради того, чтобы использовать паттерн — это не очень хорошая практика проектирования.
              Это вы про «про одну интересную идиому Concept-Based Polymorphism» или про Visitor?
                +2
                А как определить должны или не должны?

                Это определяется из предметной области разрабатываемого проекта. Но если вы можете предложить общего предка для этих сущностей без делания down-cast при каждом использовании, мне интересно будет почитать. Желательно с примерами кода.

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

                Вы считаете это ответом на вопрос?

                По иронии в GoF паттерн Visitor описывается как раз на примере с компилятором.

                А в чем здесь ирония? Если вы считаете, что визиторы здесь применимы, то перечитайте еще раз мой 1й комментарий. А насчет использования визиторов в компиляторах — это очень распространенный паттерн, посмотрите, например класс InstVisitor.
                  0
                  Но если вы можете предложить общего предка для этих сущностей без делания down-cast при каждом использовании, мне интересно будет почитать. Желательно с примерами кода.
                  Я это просто расцениваю как предложение реализовать паттерн Visitor для некоторых упомянутых вами названий сущностей. Для лучшего восприятия я оставил канонические имена для функций accept и visit. И что?
                  int main()
                  int main()
                  {
                    // example: Cartesian product of two independently arranged vectors 
                  
                    std::vector< Unit* > unit_sequence = {
                      new ModuleUnit(),
                      new FunctionUnit(),
                      new LoopUnit(),
                      new LoopUnit(),
                      new FunctionUnit(),
                      new ModuleUnit()
                    };
                    
                    std::vector< Pass* > pass_stages = {
                      new SanityCheckPass(),
                      new ConstPropagationPass(),
                      new FunctionInliningPass(),
                      new LoopFusionPass(),
                      new LoopUnrollingPass(),
                      new SanityCheckPass()
                    };
                    
                    for (Unit *u : unit_sequence)
                    {
                      printf("\n%s: %p\n", typeid(*u).name(), (void*)u);
                      for (Pass *p : pass_stages)
                      {
                        printf("* %s\n", typeid(*p).name());
                        p->visit(*u);
                      };
                    };
                  
                  
                    // example: more precisely arranged pipeline
                    using stage_t = std::pair< Unit*, Pass* >;
                    
                    std::vector< stage_t > stages = {
                      stage_t{ new ModuleUnit(), new SanityCheckPass() },
                      stage_t{ new ModuleUnit(), new ConstPropagationPass() },
                      stage_t{ new FunctionUnit(), new FunctionInliningPass() },
                      stage_t{ new FunctionUnit(), new SanityCheckPass() },
                      stage_t{ new LoopUnit(), new LoopFusionPass() },
                      stage_t{ new LoopUnit(), new LoopUnrollingPass() },
                      stage_t{ new ModuleUnit(), new SanityCheckPass() },
                    };
                    printf("\nStage pipeline:\n");
                    for (auto [u, p] : stages)
                      p->visit(*u);
                  
                    return 0;
                  }

                  Вы считаете это ответом на вопрос?
                  Ваше утверждение: «В данном случае я никаких костылей не наблюдаю. Как по мне, это совершенно нормальное решение, которое хорошо ложится в данный концепт» против моего: «Если для вас это нормальное решение, то тогда именно поэтому вы костылей не наблюдаете». Достаточно корректно. Но если уж действительно отвечать на вопрос
                  Можете рассказать, с каких это пор классы-адаптеры стали костылями?
                  То это начинает происходить с того момента, когда вместо того, чтобы ясно и идеоматично в терминах прикладной области описывать происходящие в ней процессы, код начинает фонтанировать сущностями, необходимыми только для поддержания работоспособности применяемых идиом и дизайн-концепций.

                  Сторонний наблюдатель, которому впервые необходимо разобраться в коде, ещё сможет быстро понять что это за сущности PassConcept/PassModel введены, т.к. они обозначены близкими к предметной области названиями.

                  Почему вдруг PassManager превращается в PassModel на основании того, что в нем тоже присутствует метод, побуквенно совпадающий с имени метода из PassModel, но семантически никак ему не эквивалентный (и он начинает сам выступать как PassModel, сам себя вкладывает, и сам себя вызывает) можно объяснить лишь дизайнерским выпендрёжом — чтобы было красиво. Из-за постоянно возникающих безответных вопросов «зачем?, почему это так надо?» разобраться с этим финтом (без подсказки в виде отдельной статьи или презентации о «новой интересной идиоме») уже сложновато.

                  Ну и под конец когда на сцене вдруг появляется адаптер из PassManager<Function> в PassManager<Module>, то это получается примерно как, если бы сначала по-пуристски заявлять что «яблоки и огурцы не должны иметь общего предка, это прямое нарушение LSP», а затем сразу же: «у нас здесь яблоки, но мы сделаем для них адаптер к огурцам, потому что у нас тут коллекция вообще-то по огурцам».
                    +1
                    Я это просто расцениваю как предложение реализовать паттерн Visitor для некоторых упомянутых вами названий сущностей. Для лучшего восприятия я оставил канонические имена для функций accept и visit. И что?

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

                    Почему так? Представьте, что какому-нибудь отдельно взятому проходу понадобилось что-то добавить в класс Module для удобства работы именно этого прохода. Если он это сделает, то это нарушит ISP, и сделает Module сложным в использовании для остальных. Если каждый вспомогательный компонент (коим является PassManager) будет добавлять в фундаментальные классы LLVM IR средства только для того, чтобы было удобно работать данной компоненте, то архитектура проекта получится не масштабируемой и очень не очевидной в использовании для тех пользователей, которых не интересует как работает PassManager или другие вспомогательные компоненты.

                    Насчет визитора: все проходы должны переопределять метод run для каждой из IR-сущностей (Loop, Module, Function). Если вы посмотрите в код llvm, то увидите, что это далеко не весь список (посмотрите наследников класса Pass).

                    Почему вдруг PassManager превращается в PassModel на основании того, что в нем тоже присутствует метод, побуквенно совпадающий с имени метода из PassModel, но семантически никак ему не эквивалентный (и он начинает сам выступать как PassModel, сам себя вкладывает, и сам себя вызывает) можно объяснить лишь дизайнерским выпендрёжом — чтобы было красиво. Из-за постоянно возникающих безответных вопросов «зачем?, почему это так надо?»

                    Никто ни в кого не превращается. PassManager не наследуется от PassModel. Здесь просто используется статический полиморфизм. Насчет «безответных вопросов»: одно из важных использований этой идиомы — поддержка вложенности (чтобы помодульные/попроцедурные проходы можно было легко чередовать).

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

                    разобраться с этим финтом (без подсказки в виде отдельной статьи или презентации о «новой интересной идиоме») уже сложновато.

                    С этим согласен, тема непростая. В llvm новый PM уже больше 6 лет делают (и ни кто бы то ни было, а сам Chandler Carruth :).

                    Плюс к этому статья предполагает наличие знакомства с llvm, что к сожалению сокращает количество читателей (или оставляет много недопонимания).

                    Ну и под конец когда на сцене вдруг появляется адаптер

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

          Указанный способ — хороший пример того, как сделать типобезопасный type erasure в C++ без интерфейсов и наследования.
            +1
            Так и не понял, чем это лучше отдельных базовых классов с методом run
              +2
              Дело в том, что Module, Function, Loop и остальные IR сущности не образуют иерархию классов, что не позволяет обрабатывать их полиморфно. По этой причине приходится делать различные методы у самих проходов и составлять из этих проходов более сложные иерархии: от Pass наследовать ModulePass, FunctionPass etc, а в свою очередь от них наследовать уже сами проходы, которые работают с определенной IR entity (Inline, LoopFuse etc). Поэтому мы получаем различные виртуальные функции: для ModulePass — runOnModule(Moduel&), для FunctionPass — runOnFunction(Function&), для LoopPass — runOnLoop(Loop*) и т.д.

              А это в свою очередь не позволяет нам работать с любой коллекцией проходов полиморфно. Т.е. нельзя просто взять набор проходов и сделать так:

              for (auto& pass: Passes) {
                pass.run(...);
              }


              А concept-based polymorphism дает такую возможность
                0
                А зачем runOnModule, runOnFunction...? Нельзя просто run?
                  +2
                  Можно и run сделать, но это же не решает проблему. Сигнатуры функций все равно будут разные: один проход будет принимать Module&, другой Function&, третий еще что-то.
                0

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

                +1

                А новый PassManager уже билдится по дефолту? Раньше его вроде флагами при компиляции надо было включать

                  +2
                  К сожалению все так. До сих пор нужна специальная опция, чтобы включить новый PM -fexperimental-new-pass-manager. А разработчики проходов поддерживают две версии — и для Legacy и для нового PM.

                  Но при сборке llvm можно подать влажок, который включает его по умолчанию: -DLLVM_USE_NEWPM=ON
                  +2

                  Это же просто std::function с методом run вместо круглых скобок.

                    0

                    Вот, здравый смысл прозвучал наконец

                      0
                      Да, в std::function тоже используется type erasure. Но здесь он не может быть применим по той причине, что сигнатура функций для run разная у разных проходов.
                        +1

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

                      0

                      А вот самое интересное — адаптер FuncPassManager в ModulePassManager не показан. Я так предполагаю, что там модуль представляется как коллекция функций и для каждой вызывается все что добавленно в функциональный пасс менеджер? Честно Шон очень клёвый, но он не единственный кто до этой идеи дошёл. Впервые я это увидел (не сам додумался) почти 20 лет назад когда из всего с++ мира только про страуса знал и то по книгам. уверен что и раньше это тоже было известно. С тех пор разве что мув добавился для производительности, но и без него на указателях по сути также все и работало.

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое