LINUX.ORG.RU

Книжки по компиляторостроению


0

0

Есть ли что-либо читаемое, особенно по кодогенерации? Мне надо соорудить JIT для простой числодробилки для x86-64.

Ну и вообще почитать по теории -- вдруг чего интересного прочитается... В топике http://www.linux.org.ru/view-message.jsp?msgid=2969315 анонимус мне посоветовал Dick Grune, Henri E. Bal, Ceriel J.H. Jacobs, Koen G. Langendoen "Modern Compiler Design". Я посмотрел -- книга довольно толстая и старая, конечно, потоньше Драконьей книги, но не намного (730 против 1000 страниц и 2000 год против 2006 второго издания Драконьей книги). Кто читал, отзовитесь -- стОит ли ее искать? Она действительно лучше драконьей книги (Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman "Compilers: Principles, Techniques, and Tools")?

★★★★★

Re: Книжки по компиляторостроению

а зачем его сооружать, если можно воспользоваться GNU lightning? или я неправильно понял требования?

ott ★★★★★ ()
Ответ на: Re: Книжки по компиляторостроению от ott

Re: Книжки по компиляторостроению

> ...если можно воспользоваться GNU lightning?

Меня уверяют, что оно довольно тормознутое... Вот ссылка: http://www.linux.org.ru/view-message.jsp?msgid=2833522#2845526

Мне надо гигабайты триад в нейтив код пелеопачивать, желательно при этом получать максимально эффективный код. А операций у меня -- плюс / минус / умножить / делить /степень / логарифм...

Die-Hard ★★★★★ ()
Ответ на: Re: Книжки по компиляторостроению от marsijanin

Re: Книжки по компиляторостроению

> Накатать транслятор ваших операций в C/Fortran.

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

А вопрос, вообще говоря, про книжку у меня. Кто читал?

Die-Hard ★★★★★ ()
Ответ на: Re: Книжки по компиляторостроению от Die-Hard

Re: Книжки по компиляторостроению

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

Ну или Intel Manual и сразу машкод генерировать по аналогичному принципу. Я не знаю, что может тормозить в лайтнинге, он вроде бы предельно тупой и простой (на сколько может быть простым кроссплатформенный ассемблер).

Legioner ★★★★★ ()
Ответ на: Re: Книжки по компиляторостроению от Legioner

Re: Книжки по компиляторостроению

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

Legioner ★★★★★ ()
Ответ на: Велосипед? от Dselect

Re: Велосипед?

>> Мне надо соорудить JIT для простой числодробилки для x86-64.

> А он уже есть: http://llvm.org

Ну, я не совсем точно выразился: мне надо не абстракный "JIT для числодробилки", а конкретный JIT для моей конкретной программки.

Die-Hard ★★★★★ ()
Ответ на: Re: Книжки по компиляторостроению от Die-Hard

Re: Книжки по компиляторостроению

> Это огромноый монстр,

Во-первых,

du -s /usr/local/stow/llvm-2.3-gcc-4.1/lib
36200 /usr/local/stow/llvm-2.3-gcc-4.1/lib

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

> к тому же ЦеППшный.

И в чём проблема-то? API генерируемого кода -- C'шное.

> А у меня маленькая компактная программка на Це.

Религия не позволяет пользоваться богомерзким C++?

Dselect ★★★ ()
Ответ на: Re: Книжки по компиляторостроению от Legioner

Re: Книжки по компиляторостроению

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

У меня вообще немного другое: мне надо сгенерить код один раз, а потом выполнять его полтора миллиона раз с различными входными данными. Но сам код абсолютно линеен, в смысле, циклов нет, функций нет. Развилки бывают (if-then-else), но очень редко. Шитый код тут совершенно ни при чем, у меня действительно просто последовательность триад (triples) "операция, операнд1, операнд2", где (с точностью до очень редко мелькающих if-then-else) операнды -- double константы, адреса double переменных или ссылки на разультаты предыдущих триад.

Die-Hard ★★★★★ ()
Ответ на: Re: Книжки по компиляторостроению от Dselect

Re: Книжки по компиляторостроению

> ...и никто не заставляет ими пользоваться.

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

> API генерируемого кода -- C'шное.

1. Оно на GCC заточено, да еще и капризное.

2. Я не хочу пользоваться llvm-gcc ради маленького кусочка. Я уже mpicc наелся.

> Религия не позволяет пользоваться богомерзким C++?

Пользовать для числодробильни C++ как-то не хочется.

Die-Hard ★★★★★ ()
Ответ на: Re: Книжки по компиляторостроению от Die-Hard

llvm versus велосипеды

> Я не хочу заставлять ползователя собирать (обходя многочисленные грабли) всего этого крокодила ради маленького нужного мне кусочка.

1. Пользователю вообще нифига не надо собирать.

2. Разработчику надо сказать

apt-get install llvm

Для особо одарённых на офф. сайте есть бинарные сборки.

> 1. Оно на GCC заточено,

1. Ни подо что особо оно не заточено.

2. Даже если б и было заточено -- чем это Вам мешает?

> 2. Я не хочу пользоваться llvm-gcc ради маленького кусочка. Я уже mpicc наелся.

llvm-gcc Вам не нужен. Нужны библиотеки (и то -- далеко не все). Таки советую почитать документацию, например http://llvm.org/docs/tutorial Там как раз разобран недоязычок очень похожий на Ваши триады.

> Пользовать для числодробильни C++ как-то не хочется.

А Вы не пользуйте для числодробильни, пользуйте для кодогенерации.

Dselect ★★★ ()
Ответ на: llvm versus велосипеды от Dselect

Re: llvm versus велосипеды

> Там как раз разобран недоязычок очень похожий на Ваши триады.

:-)

"Мои триады" -- не язык, а стандартное промежуточное представление.

llvm -- средство быстрого построения своего велосипеда. А у меня мой уже готов и шустро ездит. Мне надо к нему JIT прикрутить -- будет крутым мотоциклом. llvm тут явно не поможет, он именно для комфортного велосипедостроительства предназначен.

Die-Hard ★★★★★ ()
Ответ на: Re: Книжки по компиляторостроению от Die-Hard

Re: Книжки по компиляторостроению

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

Burbaka ★★ ()
Ответ на: Re: Книжки по компиляторостроению от Burbaka

Re: Книжки по компиляторостроению

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

Все сделано!

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

Теперь мне надо его в двоичное представление аккуратно заправить. Там могут быть проблемы (типа выравниваний, префетчинга, сброса кышей, барьеров итп). Где б про это прочитать? Это вопрос номер раз.

> Вообщем-то в качестве источника информации и дракона за глаза хватит.

Дракон тут не шибко поможет: я его на будущее хотел почитать. В связи с этим, вопрос номер два:

А что еще есть хорошего (нетолстого / интересного / полезного) на эту тему?

И вопрос номер три:

Что лучше, драконья книга, или Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman "Compilers: Principles, Techniques, and Tools".

Die-Hard ★★★★★ ()
Ответ на: Re: Книжки по компиляторостроению от Die-Hard

Re: Книжки по компиляторостроению

> Теперь мне надо его в двоичное представление аккуратно заправить. Там могут быть проблемы (типа выравниваний, префетчинга, сброса кышей, барьеров итп). Где б про это прочитать? Это вопрос номер раз.

Наверное лучше всего почитать доку от производителя процессоров :) Более подробного наверное ничего не найдешь. Что-нибудь типа "Intel Architecture Optimization Reference Manual" ?

Burbaka ★★ ()
Ответ на: Re: Книжки по компиляторостроению от Die-Hard

libjit?

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

> Теперь мне надо его в двоичное представление аккуратно заправить.

http://cvs.savannah.gnu.org/viewvc/libjit/?root=dotgnu-pnet

Dselect ★★★ ()
Ответ на: libjit? от Dselect

Re: libjit?

> http://cvs.savannah.gnu.org/viewvc/libjit/?root=dotgnu-pnet

(Перекрестился) -- одному мне кажется, что чем-то попахивает?

Впрочем, не читал... Что, есть на что посмотреть?

2Dselect:

Прошу ответить серьезно -- сам-то пробовал? Действительно, есть за что взгляду зацепиться?

Die-Hard ★★★★★ ()
Ответ на: Re: libjit? от Die-Hard

Re: libjit?

Die-Hard

Извиняюсь за оффтоп, но сам интересуюсь компиляторостроением. Почитывал на досуге драгон бук, первое издание, есть в печатном виде. Второе найти не смог пока :(. Не могли бы вы оное переслать мне на fukazzz[гав]gmail.com? буду благодарен ;)

fukazzz ()
Ответ на: Re: libjit? от Die-Hard

Re: libjit?

> (Перекрестился) -- одному мне кажется, что чем-то попахивает?

Чем именно?

> Что, есть на что посмотреть?

Она решает задачу "из низкоуровневого промежуточного представления сделать родной код". Если правильно понял, то именно это и нужно.

> Прошу ответить серьезно -- сам-то пробовал?

Пробовал, но для моих целей она слишком низкоуровневая, llvm мне гораздо лучше подходит.

> Действительно, есть за что взгляду зацепиться?

Не поймёшь -- то "монстр", то "не за что взгляду зацепиться".

Dselect ★★★ ()
Ответ на: Re: Книжки по компиляторостроению от Burbaka

Re: Книжки по компиляторостроению

> > Теперь мне надо его в двоичное представление аккуратно заправить.

> Наверное лучше всего почитать доку от производителя процессоров :)

Согласен. Вряд ли в книжке по компиляторостроению будут такие вещи.

Dselect ★★★ ()
Ответ на: Re: libjit? от fukazzz

Re: libjit?

> Не могли бы вы оное переслать мне на fukazzz[гав]gmail.com? буду благодарен ;)

Я не смог его найти не то что в электронном -- в печатном виде! На английском в центральной библиотеке универа нет вообще, у информатиков -- только один экземпляр, вряд ли когда появится на полке.

Заказал для нашей институтской библиотеки, но пока не ясно, когда придет.

Die-Hard ★★★★★ ()
Ответ на: Re: libjit? от Dselect

Re: libjit?

> Чем именно?

Дотнетом.

Это опенсоцовская имплементация Мелкомягкого CLI.

> Не поймёшь -- то "монстр", то "не за что взгляду зацепиться".

Это был вопрос -- можно его использовать для чего-либо, отличного от CLI?

К тому же оно, как я понял, на Мелкомягком коде завязано...

Die-Hard ★★★★★ ()
Ответ на: Re: Книжки по компиляторостроению от Dselect

Re: Книжки по компиляторостроению

> Вряд ли в книжке по компиляторостроению будут такие вещи.

Должны же быть как-то общие принципы!

Die-Hard ★★★★★ ()
Ответ на: Re: libjit? от Die-Hard

Re: libjit?

Телепат из Вас плохой, так что научитесь ходить по ссылкам.

> Это опенсоцовская имплементация Мелкомягкого CLI.

Нет. Это jit-библиотека, которая поддерживает компиляцию в байт-код (на всех платформах) и/или в родной код (на x86, x86_64 и alpha).

> Это был вопрос -- можно его использовать для чего-либо, отличного от CLI?

Да. Кстати, в исходниках есть примеры.

> К тому же оно, как я понял, на Мелкомягком коде завязано...

1. Нет.

2. Библиотека под LGPL, Вам не всё равно, кто её написал?

Dselect ★★★ ()

Re: Книжки по компиляторостроению

> Мне надо соорудить JIT для простой числодробилки для x86-64.

Hint1: не использовать x86 FPU - он сложный очень, полустековая-полурегистровая машина. Использовать надо SSE2, там самые обычные регистры.

Hint2: генерить промежуточный трехадресный код. Пример, как это делать, недавно на lambda-the-ultimate был, в самом конце туториала вот тут: http://lambda-the-ultimate.org/node/2895

Hint3: Книга "modern compiler design" довольно хорошая, но конечно же для всего лишь jit для простого арифметического языка это многовато. Она лучше драконьей книги в том, что меньше внимания уделено парсерам, и побольше о собственно компиляции.

anonymous ()
Ответ на: Re: Книжки по компиляторостроению от Die-Hard

Re: Книжки по компиляторостроению

Очепятка:

> Что лучше, драконья книга, или Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman "Compilers: Principles, Techniques, and Tools".

Имелось в виду, конечно,

Что лучше, драконья книга, или "Modern Compiler Design"?

Die-Hard ★★★★★ ()
Ответ на: Re: Книжки по компиляторостроению от anonymous

Re: Книжки по компиляторостроению

> ...генерить промежуточный трехадресный код.

Он у меня сгенерен.

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

Thanks.

Die-Hard ★★★★★ ()
Ответ на: Re: libjit? от Dselect

Re: libjit?

>> Это был вопрос -- можно его использовать для чего-либо, отличного от CLI?

> Да. Кстати, в исходниках есть примеры.

Взглянул на примеры -- примерно то, что мне надо, и посимпатичнее, чем gnu lightning. Только, боюсь, тормозить будет (или вообще свалится) на моих масштабах.

И как-то не верится, что оно хороший наитивный код сделает... И сколько времени оно его лепить будет?

Например, как оно регистры будет раскидывать? Если станет деревья раскрашивать, то для функции из миллиона триад она никогда не кончит...

Вообще, thanks за ссылку, попробую, и ее, и lightning. Это просто, хотя, боюсь, ничего, кроме велосипеда при таком подходе не получится...

Die-Hard ★★★★★ ()

Re: Книжки по компиляторостроению

Не совсем JIT, скорее сравнение stacked/register VM байткода для БЫСТРОЙ интерпретации: по ссылке с http://webkit.org/blog/189/announcing-squirrelfish/ в районе "Some great introductory reading on these topics includes:"

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.