Теперь кажется начинаю понимать. То есть, для вас критична не столько
изменяемость и алиасинг, сколько локальность полученного значения в пределах
параграфа (либо наличие информации об источнике)?
Да, примерно так. Нам важно знать о локализации значений. С одной стороны — это
дополнительные сложности. С другой, может быть, появятся новые возможности при
трансформации программ.
Aliasing нам тоже важен, но уже на стадии оптимизации для принятия решений о том,
какие параграфы можно комбинировать, что можно читать из памяти однократно и т.д.
Подойдут стандартные методы анализа, только с учётом особенностей работы с
параграфами.
Тело блока представляет собой линейную последовательность инструкций, которые могут обрабатываться одним куском.
Они могут, если все необходимые для них данные сохранены в какой-то памяти (регистрах). То есть, они не замкнуты в общем случае по потоку данных. Под ссылками я понимаю как раз ссылки на результаты других вычислений. И эти ссылки могут вести в другие линейные участки.
Ну подождите. IR код LLVM вообще не оперирует понятиями регистров или памяти. Единственная операция аллокации — alloca подарзумевает, что память надо выделить «где-то» (обычно на стеке). Да и то, применяется она только в тех случаях, когда действительно необходимо описать формальную работу с переменными. Операции с памятью тоже жестко формализованы в load/store и вспомогательную GEP (get element pointer).
SSA в чистом виде описывает только отношения неизменяемых сущностей, которые могут быть обработаны бакендом по своему усмотрению.
Под регистрами понимаются переменные, которые обозначаются %X. «Регистровость» их поведения проявляется в том, что если в такую переменную присвоено значение, то потом на него можно ссылаться по этому имени на протяжении всего кода процедуры (за исключением привязок в phi-узлах, конечно). Изнутри, в структурах данных LLVM, ссылки расставляются по тем же принципам.
В нашем процессоре подобные ссылки не переживают архитектурные линейные блоки — параграфы. И нам пришлось бы делать нетривиальный анализ того, что именно LLVM имеет в виду под каждой ссылкой в каждой конкретной ситуации. И нам бы пришлось, так или иначе, переводить внутреннее представление LLVM в какое-то своё внутреннее представление, а потом уже с ним работать. Но если мы переводим в своё внутреннее представление, то выгоднее делать это из исходного текста программы, чтобы сохранить больше деталей для последующих оптимизаций.
Если вынесение инвариантов за пределы циклов, алиас анализ и другие виды оптимизаций вас не устраивают — ради бога, просто не используйте их и все. Каждая оптимизация — это отдельный проход преобразования CFG, который может быть отключен или заменен на собственный.
Собственно, один из frontend-ов к новой системе компиляции у нас именно такой. Мы берём не-оптимизированный биткод и получаем из него удобное для нас представление программы, из которого мы генерируем текст на ассемблере. Но таким образом полученный код всё-равно плохо учитывает особенности архитектуры, для которой лучше всего получать не SSA, а именно замкнутые графы линейных участков. Эти кусочки можно в разной форме представлять, но лучше без концепции присваивания чего-то в регистр, доступный потом из любого места процедуры (что, всё-таки, подразумевает SSA).
В нашем внутреннем представлении есть разделение на просто графы (именно, как взаимосвязи значений), и на символы (переменные), через которые информация передаётся между графами. И это ещё увязано с самим процессом компиляции, которые построен как процесс вывода графа по заранее задаваемым формам (подробности будут на Хабре, как только отладим систему до alpha-версии).
LCC был выбран, потому что в кодогенератор он передаёт кусочки графа программы, что идеально подходит для архитектуры Multiclet. При этом, в каждом линейном блоке графа нет ссылок на узлы из других блоков. Это соответствует концепции параграфов.
«Монстры» же ориентированы на генерацию кода для чисто регистровых машин, к которым наши процессоры не относятся в полной мере: внутри параграфов у нас стоит потоковое (dataflow) описание вычисления. Поэтому мы не можем автоматически использовать оптимизации, которые есть в LLVM и GCC. При помощи абстракций, используемых в них для описания архитектуры целевой машины, такие потоковые машины не выражаются (по крайней мере, штатными API). Например, LLVM при оптимизации спокойно выносит общие выражения в линейные блоки за циклы, а в линейных блоках циклов ставит на этот результат ссылку, подразумевая, что она соответствует абстрактному регистру, который не меняется. Для нас разрешение такой ситуации — совсем не тривиальная задача.
Поэтому нам приходится изобретать свой компилирующий велосипед. Надеемся, что в нём будет достаточно интересных фишек, чтобы привлечь к оптимизациям и разработке нормальных API сообщество.
Сравнительные тесты планирую провести и оформить в ближайшее время.
Да, к сожалению LCC по прежнему не оптимизирует, но имеется кодогенератор с оптимальной расстановкой инструкций и удалением лишних инструкций чтения, что немного ускоряет код. Надеюсь не ошибся в заключении.
На портирование ушло около недели, сильно помог отладчик. Параллельно была найдена ошибка в компиляторе LCC (Ошибка инициализации статических локальных и глобальных указателей). Да, проект планируется развивать далее. Хочется портировать более продвинутый эмулятор терминала и текстовый редактор, ещё есть плата с GSM модулем M20 от QUECTEL, которую тоже хочется подключить. Разработчики Мултиклета отнеслись к новости хорошо, узнали первыми, т. к. я на них работаю, но проект по портированию был начат и закончен как любительский.
setRegister(TIM1,«PERIOD: %i PREDDIV: %i TOV2: %i»,1001,1002,1003);
вики:
как так?
изменяемость и алиасинг, сколько локальность полученного значения в пределах
параграфа (либо наличие информации об источнике)?
Да, примерно так. Нам важно знать о локализации значений. С одной стороны — это
дополнительные сложности. С другой, может быть, появятся новые возможности при
трансформации программ.
Aliasing нам тоже важен, но уже на стадии оптимизации для принятия решений о том,
какие параграфы можно комбинировать, что можно читать из памяти однократно и т.д.
Подойдут стандартные методы анализа, только с учётом особенностей работы с
параграфами.
Спасибо за развернутый ответ.
Да не за что. Вам спасибо за интерес!
Они могут, если все необходимые для них данные сохранены в какой-то памяти (регистрах). То есть, они не замкнуты в общем случае по потоку данных. Под ссылками я понимаю как раз ссылки на результаты других вычислений. И эти ссылки могут вести в другие линейные участки.
SSA в чистом виде описывает только отношения неизменяемых сущностей, которые могут быть обработаны бакендом по своему усмотрению.
Под регистрами понимаются переменные, которые обозначаются %X. «Регистровость» их поведения проявляется в том, что если в такую переменную присвоено значение, то потом на него можно ссылаться по этому имени на протяжении всего кода процедуры (за исключением привязок в phi-узлах, конечно). Изнутри, в структурах данных LLVM, ссылки расставляются по тем же принципам.
В нашем процессоре подобные ссылки не переживают архитектурные линейные блоки — параграфы. И нам пришлось бы делать нетривиальный анализ того, что именно LLVM имеет в виду под каждой ссылкой в каждой конкретной ситуации. И нам бы пришлось, так или иначе, переводить внутреннее представление LLVM в какое-то своё внутреннее представление, а потом уже с ним работать. Но если мы переводим в своё внутреннее представление, то выгоднее делать это из исходного текста программы, чтобы сохранить больше деталей для последующих оптимизаций.
Если вынесение инвариантов за пределы циклов, алиас анализ и другие виды оптимизаций вас не устраивают — ради бога, просто не используйте их и все. Каждая оптимизация — это отдельный проход преобразования CFG, который может быть отключен или заменен на собственный.
Собственно, один из frontend-ов к новой системе компиляции у нас именно такой. Мы берём не-оптимизированный биткод и получаем из него удобное для нас представление программы, из которого мы генерируем текст на ассемблере. Но таким образом полученный код всё-равно плохо учитывает особенности архитектуры, для которой лучше всего получать не SSA, а именно замкнутые графы линейных участков. Эти кусочки можно в разной форме представлять, но лучше без концепции присваивания чего-то в регистр, доступный потом из любого места процедуры (что, всё-таки, подразумевает SSA).
В нашем внутреннем представлении есть разделение на просто графы (именно, как взаимосвязи значений), и на символы (переменные), через которые информация передаётся между графами. И это ещё увязано с самим процессом компиляции, которые построен как процесс вывода графа по заранее задаваемым формам (подробности будут на Хабре, как только отладим систему до alpha-версии).
«Монстры» же ориентированы на генерацию кода для чисто регистровых машин, к которым наши процессоры не относятся в полной мере: внутри параграфов у нас стоит потоковое (dataflow) описание вычисления. Поэтому мы не можем автоматически использовать оптимизации, которые есть в LLVM и GCC. При помощи абстракций, используемых в них для описания архитектуры целевой машины, такие потоковые машины не выражаются (по крайней мере, штатными API). Например, LLVM при оптимизации спокойно выносит общие выражения в линейные блоки за циклы, а в линейных блоках циклов ставит на этот результат ссылку, подразумевая, что она соответствует абстрактному регистру, который не меняется. Для нас разрешение такой ситуации — совсем не тривиальная задача.
Поэтому нам приходится изобретать свой компилирующий велосипед. Надеемся, что в нём будет достаточно интересных фишек, чтобы привлечь к оптимизациям и разработке нормальных API сообщество.
Да, к сожалению LCC по прежнему не оптимизирует, но имеется кодогенератор с оптимальной расстановкой инструкций и удалением лишних инструкций чтения, что немного ускоряет код. Надеюсь не ошибся в заключении.