Сколько стоит такой большой, сложный и важный компонент системы? Благодаря опенсорсу, не так много, как вы можете подумать. В этом посте, я приведу реальный пример, который показывает нам, что построение нового коммерческого компилирующего тулчейна возможно без огромных затрат.
Сколько нужно кода?
Анализ, проделанный с помощью (SLOCCount, автор David A Wheeler) показывает, что GCC содержит больше 5 миллионов строк. LLVM меньше, всего 1.6миллионов строк, но он более молодой, поддерживает по умолчанию только C и C++ и имеет в три раза меньше целевых архитектур. Однако полезный тулчейен имеет больше компонентов.
- Отладчик: либо GDB (800К строк), либо LLDB (600К строк)
- Линкер: GNU ld (160К строк), gold (140К строк), либо lld (60К строк)
- Ассемблер/дизассемблер: GNU gas (850К строк), либо ассемблер LLVM
- Binary utilities: GNU (90К строк) и/или LLVM (включено в исходники LLVM)
- Emulation library: libgcc (входит в исходники GCC) или CompilerRT (340К строк)
- Стандартная библиотека C: newlib (850К строк), glibc (1.2M строк), musl (82К строк) или uClibC-ng (251К строк)
Кроме этого, тулчейн нуждается в тестировании. В большинстве инструментов GNU, регрессионные тесты встроены в исходники. В LLVM, регрессионные тесты имеют отдельную кодовую базу, 500К строк. Плюс к этому, во встраиваемых системах нужен отладочный сервер для взаимодействия с отладчиком при тестировании.
Что нужно для портирования компилятора?
Нам нужно портировать тулчейн для коммерческого применения. Многие аспиранты по всему миру портируют компиляторы в ходе своих исследований, но их усилия сосредоточены в одной узкой области данного исследования. В результате компилятор портируется быстро, но он не является ни полным, ни надёжным, так как это не было целью исследовательской программы.
Эта статья посвящена созданию набора инструментальных средств, который надёжно генерирует корректные и эффективные бинарники для любого исходного кода, и предназначен для коммерческого и индустриального применения.
К счастью, большая часть огромной кодовой базы является обобщённой. При разработке всех основных компиляторов были приложены значительные усилия для хорошего отделения кода, зависящего от целевой платформы, и портирование компиляторного тулчейна на новую архитектуру является посильной задачей. Эта задача включает в себя пять стадий.
1. Прототипирование
Вначале создаётся порт, содержащий все компоненты. Создание прототипа важно для того, чтобы выявить наиболее проблемные места при полном портировании, и должно занять несколько месяцев. По окончании этой стадии мы должны уметь компилировать программы, демонстрирующие, что все компоненты работают вместе, как ожидается.
2. Реализация полной функциональности
Завершение всех функций компилятора и других инструментов. Атрибуты, встроенные/intrinsic — функции, а также эмуляция недостающей функциональности должны быть завершены. Должен работать линкер, написан BSP, и, при необходимости, добавлены кастомные опции. В конце этого процесса пользователь получает полнофункциональный тулчейн. Самое важное, полный набор регрессионных тестов должен проходить.
3. Тестирование.
Самая большая часть проекта. Тестирование должно покрывать три области:
— регрессионное тестирование, показывающее, что тулчейн не сломан и может работать для разных архитектур.
-Аттестационное тестирование (compliance testing), часто используются тесты заказчика, показывающие, что вся требуемая функциональность присутствует.
-бенчмарки, показывающие, что сгенерированный тулчейном код удовлетворяет критериям требуемой скорости выполнения кода, размера кода и энергоэффективности.
4. Развёртывание
На этой стадии вам нужно помочь пользователям изучить новый компилятор и то, насколько он отличается от предыдущих инструментов, и обычно для этого нужны руководства в письменной форме и на видео. Будут обнаруживаться новые баги, и также будет много сообщений о багах, вызванных различиями между старым и новым компилятором. Так бывает, когда LLVM и GCC заменяют старые проприетарные компиляторы, в связи с тем, что они гораздо более развиты в плане функциональности. Если пользовательская база велика, фаза развёртывания становится очень существенной.
5. Сопровождение
LLVM и GCC очень активно развиваются, и новая функциональность добавляется постоянно, как для поддержки новых языковых стандартов во фронтенд, так и для добавления новых оптимизаций в бэкенд. Вы должны поддерживать свой компилятор в актуальном состоянии при всех этих изменениях. Плюс к этому, конечно, у вас будет новая функциональность, специфичная для целевой архитектуры, и багрепорты от пользователей.
Сколько нужно усилий в общем случае
Рассмотрим общий случай. Новая архитектура с большой пользовательской базой, должна поддерживать C и C++, и для bare metal, и для Linux. В этом случае, вероятно, архитектура поддерживает различные реализации, от маленьких процессоров, используемых для bare metal приложений или RTOS во встраиваемых системах, до больших процессоров, способных выполнять полноценное Linux-окружение.
Полный релиз такого тулчейна занимает 1-3 человеко-года. Начальная версия тулчейна (proof of concept) должна быть реализована в течение 3-х месяцев. Реализация всей функциональности должна занять 6-9 месяцев, и ещё 3 месяца, если требуется поддержка bare metal и Linux.
Тестирование занимает как минимум 6 месяцев, но с большим количеством специфических тестов может занять до 12 месяцев. Начальное развёртывание занимает 3 месяца, но с большой пользовательской базой, может занять на 9 месяцев больше.
Усилия по поддержке сильно зависят от количества репортов от пользователей и количества новых функций. Эти усилия могут отнимать от 0,5 человеко-месяца в месяц до, что более вероятно, 1 человеко-месяца в месяц.
Важно отметить, что над проектом должна работать целая команда инженеров: специалист по компиляторам, специалист по отладке, инженер по реализации библиотеки и т.д. Разработка компиляторов является одной из наиболее сложных дисциплин, и ни один инженер не может иметь опыт сразу во всех областях.
Сколько нужно усилий в простейшем случае
Не всегда нужен компилятор, который будет использоваться большим количеством пользователей. Существуют различные специфичные процессоры, особенно DSP, которые разработаны в маленьких компаниях, состоящих из одного инженера. Там, где такие процессоры доказали свою коммерческую успешность, они начинают развиваться, и вместо крошечного ядра, программируемого на ассемблере инженером-одиночкой, становятся гораздо более мощными процессорами с большой командой программистов на ассемблере. В этом случае переход на компиляцию языка С будет означать огромный прирост продуктивности и снижение стоимости разработки.
Для таких случаев, тулчейн должен поддерживать С, без С++, и минимально необходимую библиотеку С. Также архитектура может иметь уже готовый ассемблер и линковщик, который можно использовать. Это сильно уменьшает усилия, до одного человеко-года для создания полностью работающего компилятора.
Стадия proof-of-concept по-прежнему занимает 3 месяца, но затем доводится до полнофункциональной версии ещё за 3 месяца. Тестирование по-прежнему занимает больше всего усилий, и продолжается от 3 до 6 месяцев, но при маленькой пользовательской базе 3 месяца более чем достаточно.
Поддержка также необходима, но для маленькой системы с небольшой пользовательской базой будет достаточно 0,25 человеко-месяца в месяц.
Для маленьких заказчиков, может быть важно остановиться после реализации всей функциональности. Если небольшая горстка стандартных программ компилируется, этого может быть достаточно для демонстрации эффективности компилятора, без прохождения полного набора тестов.
Исследование темы
В 2016 году в Embecosm обратилась компания, занимающаяся разработкой микроэлектроники, которая много лет использовала свой собственный DSP c 16-битным адресным пространством, разработнный специально для их узкой области. Они использовали уже третье поколение своего процессора, когда осознали, что тратят слишком большие усилия на программирование на ассемблере. Ситуация усугублялась тем, что стандартные кодеки, которые они использовали, имели референсную реализацию на С. У них был компилятор, но очень старый, и портирование кода на новое поколение DSP было невозможно.
Embecosm был заказан тулчейн на основе LLVM, способный компилировать кодеки LLVM и производить высококачественный код. Предполагалось, что код при необходимости будет дорабатываться вручную. У заказчика был готовый ассеблер и линковщик, который комбинировал все ассемблерные файлы в один, связывал все ссылки, и генерировал бинарный файл, загружаемый в DSP. Заказчик также хотел получить опыт построения компиляторов, поэтому один из инженеров заказчика присоединился к команде Embecosm и занимался поддержкой компилятора, когда проект был закончен.
В первые три месяца мы разработали тулчейн на основе существующего ассемблера и дизассемблера. Для того, чтобы использовать newlib, мы создали псевдолинкер, который извлекает требуемые файлы из newlib в виде ассемблерных исходников, и объединяет их с тестовой программой. Т.к. процессор в кремнии был недоступен, мы проводили тестирование на Verilator-модели чипа. Для этого мы написали gdb-сервер, позволяющий GDB взаимодействовать с моделью. При отсутствии ELF, отладка на уровне исходника невозможна, но GDB способен загрузить программу и получить результат, что достаточно для тестирования.
Это позволило нам скомпилировать тестовую программу и продемонстрировать, что компилирующий тулчейн работает. Стало ясно, что есть два препятствия для достижения полной функциональности: 1) отсутствие поддержки бинарных ELF-файлов и 2) отсутствие поддержки 16-битных char.
На второй фазе мы реализовали GNU-ассемблер/дизассемблер, используя CGEN, на это ушло около 10 дней. Мы также реализовали поддержку 16-битных char в LLVM, как описано в этом посте. С этими двумя вещами завершение полнофункционального тулчейна стало более простым, и мы смогли запускать стандартные LLVM lit и регрессионные тесты GCC для тулчейна, большинство из которых прошли успешно. DSP имеет ряд специальных режимов поддержки арифметики с фиксированной точкой. Для их поддержки мы реализовали специальные встроенные и intrinsic-функции.
На этой стадии у нас получился компилятор, который корректно компилирует код заказчика. Поддержка ELF означает, что возможны такие техники, как link-time optimization (LTO) и garbage collection для секций, что приводит к успешной оптимизации кода, и это соответствует требованиям заказчика при ограниченном объёме памяти. При затратах в 120 человеко-дней, была достигнута цель компиляции С-кода для нового DSP.
Заказчик решил, что на этой стадии функциональность его устраивает, и продолжения работы не требуется. Если они решат, что компилятор будет доступен широкому потребителю, они могут продолжить работу с полным тестированием тулчейна.
Выводы
Два фактора сделали возможным построение полнофункционального компилирующего тулчейна за 120 человеко-дней.
Использование опенсорсного компилятора
Инструменты, использованные в проекте, представляют собой результат общих усилий в тысячи человеко-лет, потраченных компиляторным сообществом на протяжении последних трёх десятилетий. Наши заказчики смогли использовать это преимущество для получения современного тулчейна.
Команда экспертов
Хотя это был проект на 120 дней, над ним работала команда из пяти человек, каждый из которых имеет многолетний опыт. Ни один человек не может знать всё про эмуляцию, GDB, CGEN-ассемблеры, GNU-линкер и компилятор LLVM.
Комментарии (46)
Roaming
03.05.2018 10:12+5С другой стороны, очень похоже на правду, если вы Крис Латнер, вы последнии 20 лет разрабатываете LLVM, то все сходится. В декабре сделал бранч. В марте показал рабочий концепт.
true-grue
03.05.2018 12:51К сожалению, практика совместной разработки процессорной архитектуры и компилятора для нее все еще мало распространена. Что странно, ведь данный подход успешно использовался еще Джоном Коком (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. В целом, активность по разработке инструментального ПО за пределами этих двух «народных» компиляторов, безусловно, есть.32bit_me Автор
03.05.2018 16:19+2Конечно же, 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.true-grue
03.05.2018 17:13Требования заказчика, как мне кажется, понятны из статьи. См. цитату:
«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. И, да, у меня есть свой опыт быстрого прототипирования компиляторов для специализированных процессоров.32bit_me Автор
03.05.2018 17:25+1Embecosm were tasked with providing a LLVM based tool chain
Возможно, LLVM был выбран по согласованию с заказчиком, мы не знаем деталей сделки и не можем об этом судить.
LLVM поддерживает бэкенды с разрядностью 8 и 16 бит, стековые и VLIW таргеры.
Я разрабатывал бэкенд для LLVM, 32-битный, но тоже со своими нестандартными особенностями.
Представление о том, что LLVM заточен только на 32-битные RISC-машины, в корне неверно.
Впрочем, не буду вас разубеждать.true-grue
03.05.2018 17:29Послушайте, я вовсе не против LLVM. И могу сам предложить ссылки на работы по адаптации LLVM для стековой и VLIW-архитектуры. Я с уважением отношусь к Вашему опыту работы с этой системой. Моя основная мысль в том, что LLVM (как и GCC, и большинство других компиляторов) не подходят для разработки compiler-in-loop. Мне показалось, что взглянуть за пределы мира GCC/LLVM будет интересно читателю :)
32bit_me Автор
03.05.2018 17:39Поделитесь ссылками, пожалуйста.
Не знаю насчёт compiler-in-loop, но, например, разработчики Risc-V изначально стали ориентироваться на LLVM и GCC, и на мой взгляд, это абсолютно правильное решение.true-grue
03.05.2018 18:06С удовольствием!
Какие же есть альтернативы 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-инструментами допустима не во всех случаях, согласитесь.32bit_me Автор
03.05.2018 18:19И могу сам предложить ссылки на работы по адаптации LLVM для стековой и VLIW-архитектуры.
Я хотел бы эти ссылки.true-grue
03.05.2018 18:27Пожалуйста.
ac.els-cdn.com/S1571066111001538/1-s2.0-S1571066111001538-main.pdf?_tid=86c677b1-94c4-4dd7-9b05-07a8149a9fe9&acdnat=1525361214_da2b9d1c18fe5baa768a31e46bbafc90
llvm.org/devmtg/2011-11/Simpson_PortingLLVMToADSP.pdf32bit_me Автор
03.05.2018 18:35Большое спасибо.
Кстати, llvm.org заблокировали. А то террористы смогут собрать компилятор!
erondondon
03.05.2018 16:59Ну и сколько стоит?
32bit_me Автор
03.05.2018 17:04+1Зарплата Compiler Engineer — ?45K to ?85K. Можете подсчитать примерно.
ChePeter
03.05.2018 17:45-1Задачу автоматизации построения компиляторов они решали еще на IBM-360\370
вот из моей библиотеки
и решили.
В книге есть все блок схемы и кодtrue-grue
03.05.2018 18:21+3В этой книге работа над компилятором толком не доходит до стадии, когда уже можно использовать что-то в духе LLVM. Для тех времен типичен акцент на лексическом и синтаксическом анализе. Это наиболее проработанная тема, ей с удовольствием занимались исследователи-теоретики. В современном же учебнике практической направленности по компиляторам теме разбора исходного текста должно быть уделено от силы 20-30% содержания. В настоящее время серьезные объемные монографии написаны по таким частным вопросам, как упорядочивание инструкций или выбор инструкций.
tyomitch
03.05.2018 21:41+1Большая проблема в том, что в университетских курсах построения компиляторов больше половины всего времени уделяется лексическому и синтаксическому анализу. Просто потому, что опыт у профессоров ещё с тех пор, когда основная сложность компиляции была в этом.
true-grue
03.05.2018 21:49+1Согласен. Но ведь достойные современные учебники существуют. В этом смысле печально, что до сих пор нет русских переводов Appel (версия для ML, на мой взгляд, до сих пор является одним из лучших примеров такого учебника) и популярного курса от Cooper & Torczon. Я уже не говорю о более узкоспециальной литературе.
mayorovp
03.05.2018 18:31+2Я, конечно, не специалист по "большим" компьютерам, но мне видится сомнительным что те компиляторы могли делать хитрые оптимизации. Это попросту слишком дорого.
То что тогда считалось компилятором — по современным меркам просто парсер с прикрученным генератором машинного кода…
true-grue
03.05.2018 18:44Уже в 50-е годы использовались методы экономии регистров, удаления общих подвыражений и базовые варианты анализа потока данных. Первая книга дракона вышла еще в 77 году. Среди впечатляющих проектов по созданию оптимизирующих компиляторов и средств разработки 70-х — компилятор BLISS и инструментарий построения компиляторов PQCC. PQCC, как и система BETA коллектива Ершова, в полном объеме так и не был завершен.
voidnugget
04.05.2018 02:53Пишу компилятор формально верифицируемых языков — постоянно сталкиваюсь с проблемами производительности в кодогенераторе 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 человеко/дней при разработке фронтенда/бэкенда, но это будет далеко не самое производительное решение.
32bit_me Автор
04.05.2018 04:50компилятор формально верифицируемых языков
Интересно. Расскажите, пожалуйста, что за языки.voidnugget
05.05.2018 02:50+2Это два языка — 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.
32bit_me Автор
05.05.2018 06:34+1Ничего себе. Очень круто. Это не опенсорс-проекты, как я понимаю?
voidnugget
05.05.2018 07:38+2Будем опенсорсить, надеюсь что скоро.
"Жесткого роялти" не будет, но я планирую % от дохода как это сделано с Unreal'ом четвертым.32bit_me Автор
05.05.2018 07:40+1Круто. А как вы планируете это монетизировать, если не секрет?
voidnugget
05.05.2018 08:06+2Пока рассматриваем варианты.
Snap и пару сервисов в разработке, по этому все "покрыто туманом войны".32bit_me Автор
05.05.2018 08:07+1Ясно. Надеюсь почитать о ваших разработках на хабре, когда доберётесь до релиза.
32bit_me Автор
04.05.2018 18:22Наверное, если вы пишете фронтенд, вы можете столкнуться с подобными проблемами.
Но если вы разрабатываете бэкенд, то вы сам хозяин всех оптимизаций. Если ядро, для которого пишется бэкенд, новое/уникальное, то нет проблем совместимости с более ранними версиями, и можно использовать множество паттернов выбора инструкций для того, чтобы в каждой ситуации выбирались наиболее оптимальные инструкции, и можно дописывать свои проходы оптимизации. Это долго, конечно, но можно добиться очень хороших результатов.voidnugget
05.05.2018 02:31+1Есть много нюансов при работе с Array и Memory SSA.
Если с первой еще более-менее понятно, то работа с Memory SSA, к сожалению, сводиться к аннотациям сборщика мусора...
то вы сам хозяин всех оптимизаций
Не стоит идеализировать LLVM, есть ряд полиэдральных оптимизаций которые просто неприменимы из-за недостатков дизайна промежуточных проходов SSA.
32bit_me Автор
05.05.2018 06:32Вы можете привести приер программы, в которой проявляются эти нюансы?
(я не к тому, чтобы с вами поспорить, мне реально интересно понять суть проблемы).voidnugget
05.05.2018 08:16+1Из OpenSource проектов наиболее хорошим примером является OpenCV и TensorFlow.
В OpenCV все SIMD операции с матрицами выполнены вручную, посредством Intrinsic x86 вызовов, так как полноценно утилизировать все инструкции современные тулчейны не в состоянии. В TensorFlow вообще отдельные кастомные LLVM бэкенды с JIT'ом для тензоров доступны, что бы можно было и под PTX и под CPU без bottleneck'ов больших.
Часто проскакивают новости типа "вот cloudflare свой сишный роутер под AVX2 допилила, и получила хороший прирост".
Существующий полиэдральный оптимизатор в GCC даже умножение матриц не умеет уже довольно давно. В LLVM ситуация была получше, правда там он работает "только в теории". В TensorFlow оптимизаторах тоже часто используют полиэдральщину.
true-grue
05.05.2018 13:30+1Не стоит идеализировать LLVM, есть ряд полиэдральных оптимизаций которые просто неприменимы из-за недостатков дизайна промежуточных проходов SSA.
А нужно ли вообще иметь дело с Array/Memory SSA там, где мы можем использовать промежуточное представление на основе модели многогранников? Я не очень уловил, как работе на уровне этого промежуточного представления мешают какие-то «недостатки дизайна промежуточных проходов SSA». Ведь в таких коммерческих компиляторах, как R-Stream, а также в расширениях Polly (LLVM) и Graphite (GCC) осуществляется переход из SSA на другой уровень представления для совершения преобразований по векторизации/распараллеливанию/проч., а потом возвращается результат в SSA (или другом виде).voidnugget
05.05.2018 14:08+2А нужно ли вообще иметь дело с 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, скорее воспринимается как "академическая поделка" за которую никто денег толком не заплатит.
true-grue
05.05.2018 14:34+1Мне представляется, что Вы решаете слишком амбициозную задачу для LLVM. Во многих существующих инструментах от пользователя требуется добавить #pragma или иную аннотацию для соответствующего гнезда циклов. Способы обойтись без таких ручных указаний известны: динамический анализ (JIT, о котором Вы сказали выше) или DSL (ограничивающие программиста конструкции, в том числе сложные системы типов). В случае LLVM и собственного языка/DSL целесообразно, на мой взгляд, сделать собственный backend для LLVM-машины, который будет генерировать IR, прошедший ряд высокоуровневых преобразований.
Что касается, R-Stream, то я сужу о нем по доступным публикациям и патентам. Это, безусловно, полноценный распараллеливающий компилятор, который поддерживает гетерогенные массово-параллельные архитектуры. Просто последняя публикация на их сайте посвящена именно TensorFlow :)
P.S. Большое спасибо за критику Polly и Graphite!voidnugget
05.05.2018 15:29+1Во многих существующих инструментах от пользователя требуется добавить #pragma или иную аннотацию для соответствующего гнезда циклов.
Советую почитать статью — хорошо объясняет примеры задач которые можно решить полиэдральными моделями.
Полиэдральные оптимизации позволяют, к примеру, полностью распаралелить код — не нужно заморачиваться с блокировками и соответствующими deadlock / livelock / race-condition проблемами. Существующие race-condition детекторы, например в golang'e, успешно используют полиэдральную модель поверх существующего SSA.
Также разработчики Rust'a рассматривают возможность использования Memory SSA с полиэдральными оптимизациями — хотят совсем отказаться от Arena аллокатора.
true-grue
05.05.2018 18:30+1Спасибо, я эту статью читал. В ней описан консервативный подход к анализу зависимостей для поддержки гнезд нерегулярных циклов, кроме того, вопросы производительности трансформаций остаются открытыми. Поэтому представленный по ссылке подход все равно может быть полезно дополнить динамическим анализом, аннотациями и эвристиками.
Существуют работы по совмещению полиэдрального подхода с классическим динамическим анализом зависимостей inspector/executor. Также представляет интерес, на мой взгляд, техника взаимодействующих полиэдральных процессов — polyhedral process network.
А вот об использовании данного подхода в golang я ничего не слышал. Не поделитесь ссылкой?voidnugget
05.05.2018 20:06+1Cейчас golang использует TSan, но также были нативные решения, пока что они не публиковались.
yurrig
120 человеко-дней, не 600, не?
32bit_me Автор
В оригинале engeneering-days.
Vitalley
6 месяцев на одного инженера выполнять?