компилятор

Существуют математические методы, позволяющие любую логику реализовать в железе наиболее оптимальным образом. Поэтому, всем пофиг, где и как вести разработку железа (там тоже есть несколько разных языков) - результат одинаков. По этой же причине багов в железе почти нет.

В случае с ЯПВУ таких методов (пока?) нет. Поэтому преобразование ЯПВУ1->ЯПВУ2->Бинарный код будет отличаться от ЯПВУ1->Бинарный код. Зачастую в худшую сторону.

Вероятно, это и есть основная причина. Ничто не хочет добавлять отдельный уровень вылавливания глюков (C->бинарник), когда можно без него обойтись.

Обычно компиляторы все равно используют некое промежуточное представление, которое уже компилируется в непостредственно в машинный код.

Я полагаю, здесь ключевое значение имеет эффективность результирующего бинарного кода.

Также согласен с предыдущеми ораторами по поводу нецелесообразности наличия доп. уровня преобразования.

Я сегодня в роли К.О.

Чтобы из AST получить бинарь, нужен бекэнд для данной архитектуры. Свой, родимый!

в простом случае разница в том, что при трансляции в машкоды я использую напрямую регистры и элементарные процедуры процессора, а при использовании промежуточного языка я возлагаю эту работу на него. Так в чём в общем случае основной выигрыш? В прямой манипуляции регистрами? В использовании элементарных процедур в отличии от процедур ЯП более ВУ? В работе с памятью?

сейчас имхо стоит посмотреть на LLVM.

скачайте исходники gcc (4.5 к примеру)
и загляните в gcc/configs

ну допустим в gcc/configs/rx
как пример того, что требуется для поддержки новой архитектуры (RX была добавлена недавно) там немного

вопрос в том, что целесообразно взять в роли бекэнда - машкоды или ЯПВУ(не знаю можно ли С отнести к ВУ относительно машкодов)

>вопрос в том, что целесообразно взять в роли бекэнда - машкоды или ЯПВУ(не знаю можно ли С отнести к ВУ относительно машкодов)

Смотря для каких целей, имхо.

т.е. её набор RISC-подобных инструкций даёт кроссплатформенный ассемблер?

Между AST и маш.кодом лежит пачка оптимизаций, опирающихся на информацию, содержащейся в AST. Это всё равно, как перевести Достоевского на другой язык, но буржуи будут читать не того Достоевского. И понимать его будут по-другому, потому что не в той культуре развивались.

По исходникам строится AST, его оптимизируют и далее генерят машкод? Всем этим занимается компилятор? А если сгенерировать в код другого языка и оставить эту работу на его компилятор? Наверное это не хорошо?

Может ли быть выгода, если соптимизированный AST ЯВУ преобразовать в AST С и отправить на дальнейшие, более низкоуровневые, оптимизации? Преобразование AST->AST вообще делают? И стоит ли строить AST или есть альтернативные способы оптимизации сорцев(не считая тех, которые можно сделать без AST)

> Существуют математические методы, позволяющие любую логику реализовать в железе наиболее оптимальным образом.

Существуют методы, позволяющие валидировать некоторые аспекты реализации логики. Кроме того, существуют методы, позволяющие реализовывать логику автоматически, причем результат их работы далек от оптимального.

По этой же причине багов в железе почти нет.

4.2. Ошибки обычно возникают при описании той логики, которую надо бы реализовать. Можно провести прямую аналогию с ошибками в исходных текстах программ (а компилятор почти безошибочно реализует описанную в исходном тексте логику в ассемблерный код).

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

По исходникам строится AST, его оптимизируют и далее генерят машкод? Всем этим занимается компилятор? А если сгенерировать в код другого языка и оставить эту работу на его компилятор?

И стоит ли строить AST или есть альтернативные способы оптимизации сорцев(не считая тех, которые можно сделать без AST)

Это как? AST - это программа после её протаскивания через парсер. Текст программы - для программиста, а её AST - для компилятора.

Вся высокоуровневая оптимизация (dead code elimination, tail recursion, type propagation, etc) делается над AST. Низкоуровневая оптимизация, типа peephole, ssa, конечно, улучшается маш.код, но без высокоуровневой оптимизации это будет буллшит. Если даже из уже оптимизированного AST сгенерировать сишный код, то придётся учитывать особенности работы (eql городить огород) сишного компилятора и его рантайма. Далее, родной бэкэнд знает, что, вот, ага, именно в этом случае можно схитрить и сделать финт ушами. Сишный компилятор компилирует сишную программу и делает финты ушами для сишной программы, а не лисповой, из которой сишный сорец и был получен.

т.е. последоваиельность типа

exp -> compile-from-lang-form+optimization

exp -> parsing-in-ast -> ast-optimization -> compile-from-ast+optimization

tail recursion

это ведь достаточно низкоуровневая оптимизация(в скомпиленном коде) над записью в стек или стек при таком раскладе также на уровне AST?

это ведь достаточно низкоуровневая оптимизация(в скомпиленном коде) над записью в стек или стек при таком раскладе также на уровне AST?

На низком уровне TC - это команда условного перехода. Определение того, что рекурсивную функцию можно трансформировать в цикл происходит на высоком уровне.

> позволяющие валидировать некоторые аспекты реализации логики. Кроме того, существуют методы, позволяющие реализовывать логику автоматически

По таблице истинности любой нужной функции легко построить математическое выражение и его упростить.

причем результат их работы далек от оптимального.

Результат их работы - наиболее короткая цепь логических элементов. Проблема упаковки пока до конца не решена.

а компилятор почти безошибочно реализует описанную в исходном тексте логику в ассемблерный код

В случае с таблицей истинности, преобразование совершенно однозначно. Ну-ка, расскажи нам, в какую последовательность команд преобразуется printf?

Компилятор тестируется на ограниченной кодовой базе (весьма большой), поэтому уверенности, что в самом преобразовании ошибок не будет нет. В случае сомнений, см. changelog gcc.

я так понимаю, что вся разница между кодом(выданным компилером) для хвостовой рекурсии и для обычной рекурсии в сохранении или не сохранении на стеке на каждой итерации значений некоторых переменных. Но зачем здесь AST, это и так тривиально выражается при парсинге выражения? Где нибудь можно познакомиться с оптимизациями на AST? Ведь именно для этих оптимизаций его придумали?

нужно изменить на

алгоритм компиляции я правильно изобразил?

Проблема упаковки

имеется ввиду создание путей данных между ними?

> По таблице истинности любой нужной функции легко построить математическое выражение и его упростить. Результат их работы - наиболее короткая цепь логических элементов. Проблема упаковки пока до конца не решена.

Задача нахождения самого короткого выражения NP-полна. Так что при большом количестве переменных остается довольствоваться эвристиками.

В случае с таблицей истинности, преобразование совершенно однозначно.

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

Ну-ка, расскажи нам, в какую последовательность команд преобразуется printf?

См исходники libc ;) Ответный вопрос: расскажи нам, какая СФУ реализует оптимальный протокол когерентности l1, l2 и l3 кэшей в восьмисокетной системе. Да так, чтоб без дедлоков и без про***нных данных :D

Компилятор тестируется на ограниченной кодовой базе (весьма большой), поэтому уверенности, что в самом преобразовании ошибок не будет нет.

Тем не менее, 99% ошибок - это ошибки не компилятора, а человека, который описывал логику.

> Так что при большом количестве переменных остается довольствоваться эвристиками.

Это вопрос архитектуры, функции, которую хочется описать и имеющегося в распоряжении времени.

И еще менее однозначным оно становится, когда нужно учесть топологию кристалла, задержки, распределить логику по разным стадиям конвейера

Здесь согласен. В процессе переноса абстрактной логической схемы в схему конкретного процессора есть неоднозначность.

расскажи нам, какая СФУ реализует оптимальный протокол когерентности l1, l2 и l3 кэшей в восьмисокетной системе.

Ну-ну. Я ведь спрашивал про последовательность команд, намекая, что там возможна целая куча различных реализаций. А ты у меня спрашиваешь оптимальное решение, которое и вовсе может быть единственным. (оно мне неизвестно, если что вдруг)

Тем не менее, 99% ошибок - это ошибки не компилятора, а человека, который описывал логику.

Ок, как будем сравнивать сложность задач, чтобы провести анализ соотношения ошибок? Предлагаю, один ЛЭ = 1 строка кода.

один ЛЭ = 1 строка кода

извиняюсь за своё незнание вопроса, но хочется спросить - а разве человеку нужно вручную оперировать элементами ф-ций, кроме как при задании таблицы истинности? остальная работа вроде как неплохо автоматизируется с помощью известных алгоритмов(если прога по алгоритму составлена правильно). Т.е. достаточно знать входы и выходы

> Я ведь спрашивал про последовательность команд, намекая, что там возможна целая куча различных реализаций. А ты у меня спрашиваешь оптимальное решение, которое и вовсе может быть единственным.

Неа. Это был пример железячной задачи, куда более сложной и неоднозначной, чем реализация printf :) Там все неформально, и очень часто бывает не валидровано на предмет корректности. Не взирая даже на бешеную стоимость багов. В качестве примера - нашумевшая ошибка когерентности в первых ревизиях AMD K10. Тестили-тестили, но все равно недотестили.

Ок, как будем сравнивать сложность задач, чтобы провести анализ соотношения ошибок?

Да не надо ничего сравнивать. Я просто хотел указать на то, источник ошибок - это не реализация логики, а её первоначальное описание. И разработка железа не менее error-prone занятие, чем разработка софта. С софтом наоборот проще, потому что он живет в идеальном мире нулей и единиц.

Если схема небольшая, самодельная, то логика реализуется с помощью стандартных микросхем, в каждой из которых по 6-8 ЛЭ типа ИлиНе. Простая последовательная компоновка оставит около 80-90% ЛЭ неиспользуемыми; поэтому на реальной схеме стараются на одной микросхеме использовать как можно больше ЛЭ, что не всегда получается.

Так что, в некотором смысле - приходится ;)

В случае с разработкой непосредственно ЦПУ, ЛЭ создаются каждый отдельно. Однако, проблема их взаимного расположения всё равно остаётся.

Ты что с Fyodor-ом общался?! :)))

> По исходникам строится AST, его оптимизируют и далее генерят машкод?

Нет.

И тебе лучше генерить Си.

> И разработка железа не менее error-prone занятие, чем разработка софта.

Отличия довольно существенны, тем не менее. ИМХО, конечно.

С софтом наоборот проще, потому что он живет в идеальном мире нулей и единиц.

Это кажущаяся, иллюзорная, обманчивая простота. Ибо софт работает и вовсе без всяких гарантий. (в случае отсутствия ошибок в проге и компиляторе всегда может найтись баг в ОС)

>Существуют математические методы, позволяющие любую логику реализовать в железе наиболее оптимальным образом.

По моему доказано, что это NP-полная задача, не?

> Вся высокоуровневая оптимизация (dead code elimination, tail recursion, type propagation, etc) делается над AST.

Это в каком компиляторе?

> И разработка железа не менее error-prone занятие, чем разработка софта

При этом многие ошибки железа можно прикрыть софтом %)

С софтом наоборот проще, потому что он живет в идеальном мире нулей и единиц.

С софтом проще, потому что его модифицировать на порядки легче.

Это вообще говоря, для произвольной логической функции. Насколько мне известно, реальные процессорные команды вполне удаётся представить в нужном виде достаточно быстро.

>По таблице истинности любой нужной функции легко построить математическое выражение и его упростить.

Практически любая нетривиальная цифровая схема не есть реализация таблицы истинности в куске кремния. Кроме комбинационной логики существуют еще всякие триггеры и защелки. И их роль столь же важна, как и комбинационной логики. Кроме того, как заметил Manhunt, даже если синтезатор HDL (точнее весь тулчейн) лишен ошибок, ничто не мешает ошибиться в констрейнтах, в самом HDL из которого синтезатор произведет схему и т.д. Так что основная причина того, что железо работает хорошо --- это цена ошибки, которая не дает халявить при проектировании.

> Так что основная причина того, что железо работает хорошо

ПМСМ это существенно меньшее количество уровней абстракции - легче изолировать и найти проблему. Вдобавок, часть этих самых уровней вводится заведомо без ошибок.

это цена ошибки, которая не дает халявить при проектировании.

А тестировать надо в любом случае, с этим я даже не спорю.

> реальные процессорные команды вполне удаётся представить в нужном виде достаточно быстро.

1. Нужном != оптимальном. Эвристики.

2. Насмешил. Вот тебе ссылка про то, как «представлены» «реальные процессорные команды» http://www.fcenter.ru/img/article/CPU/P4_arch/54329.gif Это делает отнюдь не автоматика, в этом искусстве соревнуются друг с другом инжерены. Лучшие из лучших. На то, чтобы породить «представление», у этих инженеров, окруженных кластерами из сотен тысяч компьютеров и огромной свитой сотрудников, уходят долгие годы.

> Вот тебе ссылка про то, как «представлены» «реальные процессорные команды» http://www.fcenter.ru/img/article/CPU/P4_arch/54329.gif

Открой уже мне глаза и покажи на той схеме хоть одну процессорную команду. Там уже введён дополнительный уровень абстракции, когда АЛУ представлены отдельными блоками. Именно на этом уровне и возникла ошибка, о которой ты говорил в последний раз. Отдельные АЛУ работали вполне корректно.

>Я так понимаю не имеет смысла делать компилятор для каждой архитектуры отдельно, используя напрямую регистры

Вы имеете в виду assembler? Его профит не только в прямом управлении регистрами. Кроме того, смысл есть, man оптимизация.

> Отдельные АЛУ работали вполне корректно.

АЛУ - это лишь малая часть того, что нужно, чтобы хорошо реализовать «процессорные команды».

Там уже введён дополнительный уровень абстракции

Человек способен удерживать в голове около 7 сущностей. Эффективно оперировать - еще меньшим количеством. Если не ввести вовремя очередной уровень абстракции, получится непонятная каша из сотен квадратиков.

> Если не ввести вовремя очередной уровень абстракции, получится непонятная каша из сотен квадратиков.

Не спорю, но при его введении они забыли учесть хитрый race condition, который возникал крайне редко (вычисления над одним блоком данных несколькими процессорами). В результате получили ошибку.

Только к чему этот спор? В железе бывают ошибки. Редко.

я вот и не могу разобраться на каких уровнях и какими способами стоит делать оптимизацию. AST - для каких-то хитрых оптимизаций, которые мне так и не назвали(наиболее общие и часто используемые). Оптимизация над маш.кодами - разве не лучше на это дело натравить крутой компилятор низкоуровнего языка? И простая оптимизация, типа хвостовой рекурсии, на уровне разбора выражения.

> AST - для каких-то хитрых оптимизаций, которые мне так и не назвали(наиболее общие и часто используемые).

Не делают на AST оптимизаций. Про уровни GCC почитай, например, тут: http://www.cse.iitb.ac.in/~uday/courses/cs715-09/gcc-gimple.pdf

в смысле из-за недостатка знаний?

> в смысле из-за недостатка знаний?

Да. Или, если не срочно, осваивай теорию компиляции.

спасибо, в SICP читал как делается компиллер для scheme, видимо там очень упрощённый вариант

>не лучше на это дело натравить крутой компилятор низкоуровнего языка

Не мне судить, но в крупных программах, например mplayer, ffmpeg, google chrome etc, используется ручная оптимизация. А всё потому, что компилятор не может эффективно использовать векторные расширения набора инструкций процессора.

Кроме того, компилятор не может глубоко анализировать оптимизируемый алгоритм, он производит низкоуровневую оптимизацию, в то время как человек может оптимизировать с оглядкой на исходный алгоритм.

может оптимизировать с оглядкой на исходный алгоритм

получается, что можно совмещать. к примеру, если ф-ция обладает св-ом хв. рекурсии, я генерю для неё код сам(в один регистр тело, в другой аргументы, результат в третий, причём на каждой итерации не мусорю в стек), а если она просто применения какой-то последовательности операция, или цикл, или ещё что-то простое, то отправляю на крутой компиллер) Это так, мысли вслух, неподкреплённые ничем.

п.с. перехожу к изучению уровней gcc

> перехожу к изучению уровней gcc

Если ты сгенерируешь разумный Си-код, ты сможешь использовать всю эту крутизну автоматически :)

>в один регистр тело

Разве только что указатель на него..

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

конечно, аргументы - тоже не по значению, а указатель на список(к примеру реализованный 2мя векторами [имена] [значения])

Не делают на AST оптимизаций.

В CMUCL/SBCL делают.