Интересные проекты компиляторов

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

Какой самый интересный проект, связанный с компилятором, вы сделали? Что вы узнали больше всего?

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

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

Поскольку автоматическая векторизация представляет собой довольно сложную оптимизацию для реализации, мы ограничили нашу область действия настолько, насколько могли. Во-первых, чтобы выявить уровень кода parallelism в коде, мы искали одноблочные циклы, которые соответствовали нашим критериям, а затем разворачивали их определенное количество раз, чтобы они были удобно векционируемыми. Затем мы реализовали алгоритм упаковки, описанный в Использование уровня суперслова parallelism с помощью наборов мультимедийных инструкций Ларсена и Амарасингхе".

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

Ответ 1

Если вас интересует оптимизация, может потребоваться вложение векторов с использованием наборов инструкций SSE и MMX.

Ответ 2

С 8-недельным таймфреймом вам нужно будет быть осторожным в отношении "ползучести области". Это не слишком амбициозно, особенно. если этот проект включает другие аспекты построения компилятора (лексирование/синтаксический анализ) или если вы все еще изучаете инструменты (отладчик, yacc) и промежуточные структуры данных (DAG).

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

Это позволит вам сделать ограниченную форму удаления Dead Code. То есть, если вы обнаружите, что переменная объявлена, но никогда не используется, не выделяйте место для нее. Если вы обнаружите, что значение установлено, но никогда не читается, не сгенерируйте набор.

Анализ переменных в реальном времени может также помочь в распределении регистров, поэтому вы можете справиться с этим, если есть время, и вы должны иметь возможность повторно использовать некоторые из того, что вы создаете для удаления кода мертвого кода.

Ответ 3

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

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

Что касается оптимизации, вот интересная статья, которую я прочитал в прошлом году:

http://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf

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

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

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

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

Anyhoo... дайте мне знать, когда вы закончите с этим проектом! И не забудьте упомянуть меня в разделе "Благодарности"!; -)

Ответ 4

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

Ответ 5

Для обучения компиляторам наилучшая идея - это сквозная идея. Используя простой бэкэнд-компьютер, а не x86, скорее выберите некоторую простую машину, такую как MIPS с голыми костями. Я выполнил свой проект компилятора подголовника, ориентированный на симулятор PDP-11, который был отличной мишенью, поскольку он делал все очень просто. Благодаря некоторому образцу кода мы могли сделать простой императивный компилятор языка примерно за четыре недели. В C!

Сегодня, с мощными языками, такими как ML, делать компилятор должен намного проще.

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

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

Ответ 6

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

Выполнение всей вещи "вперед-назад" дало мне большое понимание языка с обоих концов. В то время я читал разные книги компиляторов (например, печально известную книгу Драконов), но он никогда не погружался, пока я не написал что-то конкретное. Теперь, спустя много лет, работа, которую я сделал, дала мне более высокую оценку и понимание того, что у меня есть такие вещи, как Java VM и CLR.

Ответ 7

В моем классе компиляторов undergrad мы сначала написали рекурсивный спуск (сверху вниз) синтаксический анализатор для Pascal-подобного языка с нуля: Lexical Analyzer, парсер, все.

Примерно в середине семестра мы переводим на генераторы синтаксического анализатора/сканера, такие как lex/yacc или flex/bison. Мы построили компилятор, который возьмет подмножество Pascal и скомпилирует его для сборки для машины стека, которую нам дали (машина стека является простой, но принципы все те же).

Если вы заинтересованы в компиляторах, я не могу рекомендовать достаточно высоко Dragon Book. Он предназначался для обучения в течение 1 семестра, а второй - как курс на уровне выпускников, и он охватывает все части теории и оптимизации, которые вы когда-либо хотели. Даже Joel ему нравится. =)

Приветствия

Ответ 8

Рассмотрим тип вывода для существующего динамически типизированного языка.

Ответ 9

В дополнение к предложениям "Драконьей книги" я также настоятельно рекомендую "Разработка и внедрение расширенного компилятора" Стивена С. Мучника, который фокусируется на промежуточных представлениях, генерации кода и методах оптимизации.

Ответ 10

Посмотрите на помощь проекту Shed Skin, который компилирует Python на С++. Я думаю, что в течение лета был вызван призыв о помощи. Определение путей улучшения компиляции на С++ обеспечило бы феноменальную оптимизацию для программ python!

http://code.google.com/p/shedskin/

Ответ 11

Вот еще одна идея... хотя она все еще немного расплывчата:

Большая оптимизация выполняется во время компиляции (за исключением компиляторов JIT, которые оптимизируются во время выполнения). Но также есть много возможностей для оптимизации во время соединения и во время установки.

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

Ответ 12

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

Ответ 13

Вы можете написать оптимизатор для IronScheme, так как в настоящее время он славится всем, кроме нескольких "внутренних" функций. :)

Ответ 14

Другие интересные проекты могут включать:

Добавьте оптимизацию хвостового вызова в JVM с открытым исходным кодом.
Добавьте именованную оптимизацию возвращаемого значения (NRVO) в Python или Ruby VM.
Добавьте компиляцию с регулярным выражением-в-байт-код в определенный момент времени для вашей любимой цели (у .NET уже есть это. Я почти уверен, что Java нет.)

Ответ 15

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

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

Я считаю, что интерпретатор байт-кода Parrot и различные анализаторы .Net Iron-language могут извлечь выгоду из даже простых оптимизаций.

Ответ 16

Я сделал это в своем собственном учении "назад, когда". Я бы не уделял столь большого внимания оптимизации, как и другим вещам, таким как вывод типа или JIT или байт-код или поддержка формата объекта/отладки.

Нет никакого вреда в концентрации на оптимизации, если вы также говорите, что это намного менее важно, чем люди думают. В коде есть только что:

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

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

Изменить: К сожалению, я не могу избежать работы с компиляторами Fortran, которые безжалостно скрепили код, что очень затруднило его отладку, при этом эффект epsilon влияет на производительность.

Ответ 17

Автоматическая генерация встроенного кода с использованием эвристических тестов для компромиссов по размеру/скорости.

Ответ 18

Компилятор B:: CC perl выиграет от добавления и анализа типов. У меня просто нет времени для этого.

Было достаточно времени в последнее время. http://blogs.perl.org/users/rurban/2011/02/use-types.html