Комментарии 50
Два фактора сделали возможным построение полнофункционального компилирующего тулчейна за 120 человеко-дней.
Хотя это был проект на 120 дней, над ним работала команда из пяти человек
120 человеко-дней, не 600, не?
В статье речь идет о портировании LLVM для уже готового специализированного процессора. Конечно же, 120 дней — неприемлемый срок для подхода compiler-in-loop. Понятно, что LLVM был выбран по требованиям заказчика, но можно задаться вопросом: не была бы разработка своего backend для специализированного 16-битного процессора более эффективным (по времени, качеству кода) решением, чем адаптация LLVM?
Разработка компилятора это, разумеется, очень нелегкое занятие. Как и в случае многих других OSS-проектов, в основе «народных» компиляторов лежат идеи и код, разработанный в академической сфере. В частности, без работ Davidson и Fraser не было бы GCC. Но далеко не все «академические» компиляторы попадают в OSS. В таких, например, системах, как Synopys ASIP Designer и Reservoir Labs R-Stream, используются более изощренные методы компиляции, чем в LLVM и GCC. В целом, активность по разработке инструментального ПО за пределами этих двух «народных» компиляторов, безусловно, есть.
Конечно же, 120 дней — неприемлемый срок для подхода compiler-in-loop.
А вы можете разработать компилятор быстрее, хотя бы прототип? Вообще я cчитаю, что приведённые в статье сроки нереально занижены, в несколько раз.
Понятно, что LLVM был выбран по требованиям заказчика
Из чего это понятно? Компания Embecosm специализируется на компиляторах LLVM и GCC:
Embecosm are able to provide new and upgraded ports of binutils, GCC, GDB, GNU libraries, LLVM, LLDB, LLVM utilities and LLVM libraries
Нет ничего удивительного, что они выбрали LLVM для данного проекта.
не была бы разработка своего backend для специализированного 16-битного процессора более эффективным (по времени, качеству кода) решением, чем адаптация LLVM?
То есть вы предлагаете написать компилятор с нуля, и считаете, что это будет " более эффективным (по времени, качеству кода) решением"? Вы шутите, надеюсь. Нет, не будет, ни по одному из параметров.
Synopsys использует LLVM. Бэкенд Synopys ARC включен в релиз LLVM, и все вакансии Synopsys по компиляторам — это разработчики под LLVM.
«They had an existing compiler, but it was very old and porting it to the new generation DSP was not feasible. Embecosm were tasked with providing a LLVM based tool chain capable of compiling their C codecs and delivering high quality code.»
И будьте внимательнее, Synopys ARC не имеет отношения к ASIP Designer.
Бессмысленно меня убеждать в массовой распространенности LLVM. Гораздо интереснее, на мой взгляд, посмотреть на эту систему критически и оценить риски ее использования.
Если мы разрабатываем еще один 32-битный RISC-процессор, то использование LLVM вполне оправдано. Именно на такого вида архитектуры ориентирована эта система. У любого универсального промежуточного представления есть свои границы применимости. Специалисты это знают еще со времен UNCOL.
Задача усложняется, если мы имеем дело с нетрадиционной процессорной архитектурой: стековой, VLIW, CGRA и т.д. Здесь уже необходимо вводить собственные внутренние представления и трансформации. Если Вы не специалист по коду LLVM и не участвуете регулярно в соотв. списках рассылки, но ориентируетесь в методах компиляции, то вопрос уже не стоит так однозначно.
С точки зрения разработчика это вечная дилемма: использовать сторонний фреймворк, который потребует основательной переработки или же создать свое специализированное решение. Нужно учитывать, что сложность изучения самих алгоритмов компиляции значительно ниже, чем сложность реализаций из гигантских систем в духе LLVM. Вам придется читать источники по разработке компиляторов, вместо изучения деталей фреймворка. Но ключевой здесь момент: все это возможно при наличии соответствующего инструментария разработки компиляторов. Если же Вы просто вооружились «книгой Дракона» и решили написать на C/C++ компилятор, то, скорее всего, находитесь на неверном пути.
P.S. И, да, у меня есть свой опыт быстрого прототипирования компиляторов для специализированных процессоров.
Embecosm were tasked with providing a LLVM based tool chain
Возможно, LLVM был выбран по согласованию с заказчиком, мы не знаем деталей сделки и не можем об этом судить.
LLVM поддерживает бэкенды с разрядностью 8 и 16 бит, стековые и VLIW таргеры.
Я разрабатывал бэкенд для LLVM, 32-битный, но тоже со своими нестандартными особенностями.
Представление о том, что LLVM заточен только на 32-битные RISC-машины, в корне неверно.
Впрочем, не буду вас разубеждать.
Не знаю насчёт compiler-in-loop, но, например, разработчики Risc-V изначально стали ориентироваться на LLVM и GCC, и на мой взгляд, это абсолютно правильное решение.
Какие же есть альтернативы GCC/LLVM среди компиляторов и соотв. фреймворков общего назначения?
1. CompCert. compcert.inria.fr
Компилятор (подмножества) C99, реализованный на Ocaml, с формально доказанной реализацией. Использует практически все методы улучшения кода из классических учебников.
2. Firm. pp.ipd.kit.edu/firm
Компактная альтернатива LLVM, реализованная на чистом Си. Имеет множество готовых к использованию фаз трансформации кода.
Вариант подхода compiler-in-loop в Synopsys:
www.springer.com/cda/content/document/cda_downloaddocument/9781441911759-c1.pdf?SGWID=0-0-45-813305-p173915907
www.chipex.co.il/_Uploads/dbsAttachedFiles/AddingCProgrammabilitytoDataPathDesign.pdf
Ранние достижения в этой области связаны с работой коллективов из Европы:
www.ace.nl/compiler/cosy.html
pdfs.semanticscholar.org/presentation/3fbe/58c3e1f588aa467f0158a0d47e803ac79149.pdf
P.S. Скорее всего, разработчики RISC-V приняли правильное решение. Но сама ситуация, когда создатели процессорных архитектур ограничивают себя в выразительных средствах ради совместимости с существующими GCC/LLVM-инструментами допустима не во всех случаях, согласитесь.
вот из моей библиотеки
и решили.
В книге есть все блок схемы и код
1. Статья Instruction Selection by Graph Transformation на тему реализации этапа выбора инструкций с помощью системы переписывания (произвольных) графов. Вещь перспективная в том смысле, что даже в LLVM выбор инструкций осуществляется только на уровне DAG.
2. Алгебра программ в DSL-системах SPIRAL и Faust для DSP-программирования.
3. Взгляд на полиэдральный подход со стороны мат. формализма Пресбургера.
Я, конечно, не специалист по "большим" компьютерам, но мне видится сомнительным что те компиляторы могли делать хитрые оптимизации. Это попросту слишком дорого.
То что тогда считалось компилятором — по современным меркам просто парсер с прикрученным генератором машинного кода…
Пишу компилятор формально верифицируемых языков — постоянно сталкиваюсь с проблемами производительности в кодогенераторе LLVM… LLVM приходиться поддерживать из-за Vendor lock-in'a в яблоках.
Проблема в том, что IR(mIR) преобразования далеко не всегда применяют очевидные оптимизации по упаковке/распаковке данных — не учитывается сложность операций для отдельных версий микроархитектур и не применяются специфические оптимизации.
Например, существует ряд инструкций в x86 которые эмулируются программно микрокодом, реализация Intel'a имеет ряд недостатков… компилятор мог бы использовать более эффективные реализации, с учетом существующей SSA.
Очевидные оптимизации, например, при упаковке FP и SIMD'ах для ARMv9/11 не применяются просто из-за "обратной совместимости" с ARMv6.
В первую очередь, приоритетом для LLVM является универсальность, простота и совместимость, а утилизация аппаратных ресурсов вторична.
У LLVM есть целый ряд недостатков при работе с SSA (Array/Memory) оптимизациями. К сожалению, существующие полиэдральные (polyhedral) оптимизации в условиях реальных приложений работают "только в теории" из-за ограничений IR'a и результирующего SSA.
Да, под LLVM/GCC можно уместиться в 250 человеко/дней при разработке фронтенда/бэкенда, но это будет далеко не самое производительное решение.
компилятор формально верифицируемых языков
Интересно. Расскажите, пожалуйста, что за языки.
Это два языка — Shift и Snap.
Shift — это формально верифицируемый язык на каппа-числении и расширениях Кана (Kan Extensions), может транслироваться как в VHDL/Verilog, в биткод LLVM'а, так и в бинарники, со "своим" ассемблером и проходами SSA. Без GC полный zero-alloc — работа с памятью "один раз выделили и больше никаких free/realloc". Есть возможность работы в афинных окружениях, когда логическое ядро процессора кроме потока приложения больше ничего не выполняет — нету context switching'a между user-space / kernel-space, системные планировщики "не вливают". Также транслируется в Snap.
Snap — это формально верифицируемый статически типизированный JavaScript, который можно обратно транслировать в Shift и применить всяких оптимизаций. Также Snap транслируется в WASM без LLVM тулчейна.
"Формально верифицируемы" означает что нет, и не может быть, оптимизаций которые могут что-либо "сломать", можно "доказать" количество потребляемой памяти и вычислительную сложность для каждой конкретной модели процессора, не только архитектуры.
Cейчас решаются сугубо политические вопросы — патенты, инвестиции, монетизация и т.п. Я вот думаю начать разрабатывать таргет под GraalVM, и внедрить поддержку poll-mode драйверов на подобие SPDK/DPDK.
Но если вы разрабатываете бэкенд, то вы сам хозяин всех оптимизаций. Если ядро, для которого пишется бэкенд, новое/уникальное, то нет проблем совместимости с более ранними версиями, и можно использовать множество паттернов выбора инструкций для того, чтобы в каждой ситуации выбирались наиболее оптимальные инструкции, и можно дописывать свои проходы оптимизации. Это долго, конечно, но можно добиться очень хороших результатов.
Есть много нюансов при работе с Array и Memory SSA.
Если с первой еще более-менее понятно, то работа с Memory SSA, к сожалению, сводиться к аннотациям сборщика мусора...
то вы сам хозяин всех оптимизаций
Не стоит идеализировать LLVM, есть ряд полиэдральных оптимизаций которые просто неприменимы из-за недостатков дизайна промежуточных проходов SSA.
(я не к тому, чтобы с вами поспорить, мне реально интересно понять суть проблемы).
Из OpenSource проектов наиболее хорошим примером является OpenCV и TensorFlow.
В OpenCV все SIMD операции с матрицами выполнены вручную, посредством Intrinsic x86 вызовов, так как полноценно утилизировать все инструкции современные тулчейны не в состоянии. В TensorFlow вообще отдельные кастомные LLVM бэкенды с JIT'ом для тензоров доступны, что бы можно было и под PTX и под CPU без bottleneck'ов больших.
Часто проскакивают новости типа "вот cloudflare свой сишный роутер под AVX2 допилила, и получила хороший прирост".
Существующий полиэдральный оптимизатор в GCC даже умножение матриц не умеет уже довольно давно. В LLVM ситуация была получше, правда там он работает "только в теории". В TensorFlow оптимизаторах тоже часто используют полиэдральщину.
Не стоит идеализировать LLVM, есть ряд полиэдральных оптимизаций которые просто неприменимы из-за недостатков дизайна промежуточных проходов SSA.
А нужно ли вообще иметь дело с Array/Memory SSA там, где мы можем использовать промежуточное представление на основе модели многогранников? Я не очень уловил, как работе на уровне этого промежуточного представления мешают какие-то «недостатки дизайна промежуточных проходов SSA». Ведь в таких коммерческих компиляторах, как R-Stream, а также в расширениях Polly (LLVM) и Graphite (GCC) осуществляется переход из SSA на другой уровень представления для совершения преобразований по векторизации/распараллеливанию/проч., а потом возвращается результат в SSA (или другом виде).
А нужно ли вообще иметь дело с Array/Memory SSA
Нужно — нет прямого способа преобразовать AST в представления на многогранниках, и не для всех интервалов значений можно строить эти самые многогранники. Часто приходиться разбивать 2 вложенных цикла, на допустим 3 или 5 многогранников, в зависимости от количества объединений (фи-функция) в SSA.
расширениях Polly (LLVM) и Graphite (GCC)
Из-за этих самых недостатков большая часть возможных оптимизаций в Polly сейчас неприменима, не может оно нормально на эти самые многогранники разбить код по существующему SSA. Graphite очень сырой — бывает вызывает segfault'ы и прочие радости, матрицы множить не умеет.
R-Stream в основном работает под TensorFlow: там есть интервалы всех значений — можно нормально многогранников построить. Для тензорных функций особо строить SSA не нужно — используются инлайновый ассемблер afaik. R-Stream не является полноценным компилятором.
В LLVM нету интервалов значений — этот пробел мог был заполнить JIT, либо зависимые типы данных. Полиэдральная оптимизация не является приоритетом разработчиков LLVM, скорее воспринимается как "академическая поделка" за которую никто денег толком не заплатит.
Что касается, R-Stream, то я сужу о нем по доступным публикациям и патентам. Это, безусловно, полноценный распараллеливающий компилятор, который поддерживает гетерогенные массово-параллельные архитектуры. Просто последняя публикация на их сайте посвящена именно TensorFlow :)
P.S. Большое спасибо за критику Polly и Graphite!
Во многих существующих инструментах от пользователя требуется добавить #pragma или иную аннотацию для соответствующего гнезда циклов.
Советую почитать статью — хорошо объясняет примеры задач которые можно решить полиэдральными моделями.
Полиэдральные оптимизации позволяют, к примеру, полностью распаралелить код — не нужно заморачиваться с блокировками и соответствующими deadlock / livelock / race-condition проблемами. Существующие race-condition детекторы, например в golang'e, успешно используют полиэдральную модель поверх существующего SSA.
Также разработчики Rust'a рассматривают возможность использования Memory SSA с полиэдральными оптимизациями — хотят совсем отказаться от Arena аллокатора.
Существуют работы по совмещению полиэдрального подхода с классическим динамическим анализом зависимостей inspector/executor. Также представляет интерес, на мой взгляд, техника взаимодействующих полиэдральных процессов — polyhedral process network.
А вот об использовании данного подхода в golang я ничего не слышал. Не поделитесь ссылкой?
Cейчас golang использует TSan, но также были нативные решения, пока что они не публиковались.
Сколько стоит компилятор?