How to become an author
Search
Write a publication
Pull to refresh

Comments 22

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

Боюсь, что без дополнительных 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
Total votes 2: ↑2 and ↓0+2
Это бы хорошо работало, если бы все пассы работали с единой иерархией классов: нечто, от чего наследуется модуль, функций и т.д. В этом случае мы могли бы сделать визитор на каждую из этих сущностей и, таким образом, применить паттерн Visitor.
Да, конечно. Тут сложно судить со стороны т.к. не понятно почему, находясь под полным контролем разработчика, классы IR-сущностей не сделаны под общим предком с некоторым интерфейсом, который бы давал последующую возможность добавлять выполнение относительно произвольных действий над ними с помощью Visitor.

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

Но здесь тоже «без дополнительных crutches» не обходится: PassT-типы завернули в иерархию PassConcept — PassModel, но поскольку в этом случае виртуальная функция-член run не может быть шаблоном, зависимость от IR-типов вышла на уровень классов и далее перешла и на класс PassManager (т.е. это всё каждый раз совершенно разные типы в зависимости от IR). И чтобы зарегистрировать все проходы в красивый единый вектор требуется некий костыль в виде некоего адаптера
MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
This comment wasn’t rated yet0
Да, конечно. Тут сложно судить со стороны т.к. не понятно почему, находясь под полным контролем разработчика, классы 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
};
Total votes 2: ↑2 and ↓0+2
А тут я видимо где-то отстал: можете рассказать, с каких это пор классы-адаптеры стали костылями? В данном случае я никаких костылей не наблюдаю. Ниже привожу код данного адаптера. Как по мне, это совершенно нормальное решение, которое хорошо ложится в данный концепт.
Если для вас это нормальное решение, то тогда именно поэтому вы костылей не наблюдаете. По иронии в GoF паттерн Visitor описывается как раз на примере с компилятором.

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

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

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

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

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

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

А в чем здесь ирония? Если вы считаете, что визиторы здесь применимы, то перечитайте еще раз мой 1й комментарий. А насчет использования визиторов в компиляторах — это очень распространенный паттерн, посмотрите, например класс InstVisitor.
Total votes 2: ↑2 and ↓0+2
Но если вы можете предложить общего предка для этих сущностей без делания 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», а затем сразу же: «у нас здесь яблоки, но мы сделаем для них адаптер к огурцам, потому что у нас тут коллекция вообще-то по огурцам».
This comment wasn’t rated yet0
Я это просто расцениваю как предложение реализовать паттерн 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, что к сожалению сокращает количество читателей (или оставляет много недопонимания).

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

Адаптер здесь как раз уместен: функции вложены в модули, а адаптер нужен, чтобы достать функции из модуля и пробежаться по ним, вызвав все зарегистрированные для функции проходы.
Total votes 1: ↑1 and ↓0+1
Так же этот чувак использовал вельюс тайпы при написании фотошопа, и они позволили реализовать такую кисть, которая при рисовании ей отменяет слой за слоем последние действия именно над кистью, не говоря уже о простом откате в табличке истории.
This comment wasn’t rated yet0
Спасибо за статью. Лаконично и понятно написано.

Указанный способ — хороший пример того, как сделать типобезопасный type erasure в C++ без интерфейсов и наследования.
This comment wasn’t rated yet0
Так и не понял, чем это лучше отдельных базовых классов с методом run
Total votes 1: ↑1 and ↓0+1
Дело в том, что 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 дает такую возможность
Total votes 2: ↑2 and ↓0+2
А зачем runOnModule, runOnFunction...? Нельзя просто run?
This comment wasn’t rated yet0
Можно и run сделать, но это же не решает проблему. Сигнатуры функций все равно будут разные: один проход будет принимать Module&, другой Function&, третий еще что-то.
Total votes 2: ↑2 and ↓0+2

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

This comment wasn’t rated yet0

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

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

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

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

Total votes 2: ↑2 and ↓0+2

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

This comment wasn’t rated yet0
Да, в std::function тоже используется type erasure. Но здесь он не может быть применим по той причине, что сигнатура функций для run разная у разных проходов.
Total votes 2: ↑1 and ↓10

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

Total votes 1: ↑1 and ↓0+1

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

This comment wasn’t rated yet0
Sign up to leave a comment.

Your account

Sections

Information

Services

Support
© 2006–2024, Habr