Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 50
Два фактора сделали возможным построение полнофункционального компилирующего тулчейна за 120 человеко-дней.
Хотя это был проект на 120 дней, над ним работала команда из пяти человек
120 человеко-дней, не 600, не?
С другой стороны, очень похоже на правду, если вы Крис Латнер, вы последнии 20 лет разрабатываете LLVM, то все сходится. В декабре сделал бранч. В марте показал рабочий концепт.
.
К сожалению, практика совместной разработки процессорной архитектуры и компилятора для нее все еще мало распространена. Что странно, ведь данный подход успешно использовался еще Джоном Коком (John Cocke) в разработке первой в мире RISC-архитектуры. Этот подход иногда называют compiler-in-loop и он подразумевает, что прототипы компилятора для оценки вводимых архитектурных решений можно будет создать за считанные недели.
В статье речь идет о портировании LLVM для уже готового специализированного процессора. Конечно же, 120 дней — неприемлемый срок для подхода compiler-in-loop. Понятно, что LLVM был выбран по требованиям заказчика, но можно задаться вопросом: не была бы разработка своего backend для специализированного 16-битного процессора более эффективным (по времени, качеству кода) решением, чем адаптация LLVM?
Разработка компилятора это, разумеется, очень нелегкое занятие. Как и в случае многих других OSS-проектов, в основе «народных» компиляторов лежат идеи и код, разработанный в академической сфере. В частности, без работ Davidson и Fraser не было бы GCC. Но далеко не все «академические» компиляторы попадают в OSS. В таких, например, системах, как Synopys ASIP Designer и Reservoir Labs R-Stream, используются более изощренные методы компиляции, чем в LLVM и GCC. В целом, активность по разработке инструментального ПО за пределами этих двух «народных» компиляторов, безусловно, есть.
В статье речь идет о портировании 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. И, да, у меня есть свой опыт быстрого прототипирования компиляторов для специализированных процессоров.
«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-машины, в корне неверно.
Впрочем, не буду вас разубеждать.
Послушайте, я вовсе не против LLVM. И могу сам предложить ссылки на работы по адаптации LLVM для стековой и VLIW-архитектуры. Я с уважением отношусь к Вашему опыту работы с этой системой. Моя основная мысль в том, что LLVM (как и GCC, и большинство других компиляторов) не подходят для разработки compiler-in-loop. Мне показалось, что взглянуть за пределы мира GCC/LLVM будет интересно читателю :)
Поделитесь ссылками, пожалуйста.
Не знаю насчёт compiler-in-loop, но, например, разработчики Risc-V изначально стали ориентироваться на LLVM и GCC, и на мой взгляд, это абсолютно правильное решение.
Не знаю насчёт 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-инструментами допустима не во всех случаях, согласитесь.
Какие же есть альтернативы 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-инструментами допустима не во всех случаях, согласитесь.
.
Ну и сколько стоит?
Задачу автоматизации построения компиляторов они решали еще на IBM-360\370
вот из моей библиотеки
и решили.
В книге есть все блок схемы и код
вот из моей библиотеки
и решили.
В книге есть все блок схемы и код
В этой книге работа над компилятором толком не доходит до стадии, когда уже можно использовать что-то в духе LLVM. Для тех времен типичен акцент на лексическом и синтаксическом анализе. Это наиболее проработанная тема, ей с удовольствием занимались исследователи-теоретики. В современном же учебнике практической направленности по компиляторам теме разбора исходного текста должно быть уделено от силы 20-30% содержания. В настоящее время серьезные объемные монографии написаны по таким частным вопросам, как упорядочивание инструкций или выбор инструкций.
Большая проблема в том, что в университетских курсах построения компиляторов больше половины всего времени уделяется лексическому и синтаксическому анализу. Просто потому, что опыт у профессоров ещё с тех пор, когда основная сложность компиляции была в этом.
Согласен. Но ведь достойные современные учебники существуют. В этом смысле печально, что до сих пор нет русских переводов Appel (версия для ML, на мой взгляд, до сих пор является одним из лучших примеров такого учебника) и популярного курса от Cooper & Torczon. Я уже не говорю о более узкоспециальной литературе.
Например (что вспомнилось сейчас):
1. Статья Instruction Selection by Graph Transformation на тему реализации этапа выбора инструкций с помощью системы переписывания (произвольных) графов. Вещь перспективная в том смысле, что даже в LLVM выбор инструкций осуществляется только на уровне DAG.
2. Алгебра программ в DSL-системах SPIRAL и Faust для DSP-программирования.
3. Взгляд на полиэдральный подход со стороны мат. формализма Пресбургера.
1. Статья Instruction Selection by Graph Transformation на тему реализации этапа выбора инструкций с помощью системы переписывания (произвольных) графов. Вещь перспективная в том смысле, что даже в LLVM выбор инструкций осуществляется только на уровне DAG.
2. Алгебра программ в DSL-системах SPIRAL и Faust для DSP-программирования.
3. Взгляд на полиэдральный подход со стороны мат. формализма Пресбургера.
Я, конечно, не специалист по "большим" компьютерам, но мне видится сомнительным что те компиляторы могли делать хитрые оптимизации. Это попросту слишком дорого.
То что тогда считалось компилятором — по современным меркам просто парсер с прикрученным генератором машинного кода…
Уже в 50-е годы использовались методы экономии регистров, удаления общих подвыражений и базовые варианты анализа потока данных. Первая книга дракона вышла еще в 77 году. Среди впечатляющих проектов по созданию оптимизирующих компиляторов и средств разработки 70-х — компилятор BLISS и инструментарий построения компиляторов PQCC. PQCC, как и система BETA коллектива Ершова, в полном объеме так и не был завершен.
компилятор формально верифицируемых языков
Интересно. Расскажите, пожалуйста, что за языки.
Наверное, если вы пишете фронтенд, вы можете столкнуться с подобными проблемами.
Но если вы разрабатываете бэкенд, то вы сам хозяин всех оптимизаций. Если ядро, для которого пишется бэкенд, новое/уникальное, то нет проблем совместимости с более ранними версиями, и можно использовать множество паттернов выбора инструкций для того, чтобы в каждой ситуации выбирались наиболее оптимальные инструкции, и можно дописывать свои проходы оптимизации. Это долго, конечно, но можно добиться очень хороших результатов.
Но если вы разрабатываете бэкенд, то вы сам хозяин всех оптимизаций. Если ядро, для которого пишется бэкенд, новое/уникальное, то нет проблем совместимости с более ранними версиями, и можно использовать множество паттернов выбора инструкций для того, чтобы в каждой ситуации выбирались наиболее оптимальные инструкции, и можно дописывать свои проходы оптимизации. Это долго, конечно, но можно добиться очень хороших результатов.
Вы можете привести приер программы, в которой проявляются эти нюансы?
(я не к тому, чтобы с вами поспорить, мне реально интересно понять суть проблемы).
(я не к тому, чтобы с вами поспорить, мне реально интересно понять суть проблемы).
Не стоит идеализировать LLVM, есть ряд полиэдральных оптимизаций которые просто неприменимы из-за недостатков дизайна промежуточных проходов SSA.
А нужно ли вообще иметь дело с Array/Memory SSA там, где мы можем использовать промежуточное представление на основе модели многогранников? Я не очень уловил, как работе на уровне этого промежуточного представления мешают какие-то «недостатки дизайна промежуточных проходов SSA». Ведь в таких коммерческих компиляторах, как R-Stream, а также в расширениях Polly (LLVM) и Graphite (GCC) осуществляется переход из SSA на другой уровень представления для совершения преобразований по векторизации/распараллеливанию/проч., а потом возвращается результат в SSA (или другом виде).
Мне представляется, что Вы решаете слишком амбициозную задачу для LLVM. Во многих существующих инструментах от пользователя требуется добавить #pragma или иную аннотацию для соответствующего гнезда циклов. Способы обойтись без таких ручных указаний известны: динамический анализ (JIT, о котором Вы сказали выше) или DSL (ограничивающие программиста конструкции, в том числе сложные системы типов). В случае LLVM и собственного языка/DSL целесообразно, на мой взгляд, сделать собственный backend для LLVM-машины, который будет генерировать IR, прошедший ряд высокоуровневых преобразований.
Что касается, R-Stream, то я сужу о нем по доступным публикациям и патентам. Это, безусловно, полноценный распараллеливающий компилятор, который поддерживает гетерогенные массово-параллельные архитектуры. Просто последняя публикация на их сайте посвящена именно TensorFlow :)
P.S. Большое спасибо за критику Polly и Graphite!
Что касается, R-Stream, то я сужу о нем по доступным публикациям и патентам. Это, безусловно, полноценный распараллеливающий компилятор, который поддерживает гетерогенные массово-параллельные архитектуры. Просто последняя публикация на их сайте посвящена именно TensorFlow :)
P.S. Большое спасибо за критику Polly и Graphite!
Спасибо, я эту статью читал. В ней описан консервативный подход к анализу зависимостей для поддержки гнезд нерегулярных циклов, кроме того, вопросы производительности трансформаций остаются открытыми. Поэтому представленный по ссылке подход все равно может быть полезно дополнить динамическим анализом, аннотациями и эвристиками.
Существуют работы по совмещению полиэдрального подхода с классическим динамическим анализом зависимостей inspector/executor. Также представляет интерес, на мой взгляд, техника взаимодействующих полиэдральных процессов — polyhedral process network.
А вот об использовании данного подхода в golang я ничего не слышал. Не поделитесь ссылкой?
Существуют работы по совмещению полиэдрального подхода с классическим динамическим анализом зависимостей inspector/executor. Также представляет интерес, на мой взгляд, техника взаимодействующих полиэдральных процессов — polyhedral process network.
А вот об использовании данного подхода в golang я ничего не слышал. Не поделитесь ссылкой?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сколько стоит компилятор?