Интересные проекты компилятора
В настоящее время я нахожусь в процессе выбора проекта для курса по компиляции на уровне магистратуры, который будет проводиться в течение следующих 8 недель. Я хотел бы сделать что-то, связанное с оптимизацией, так как раньше я мало работал в этой области, но все в этой области - честная игра.
Каким был самый интересный проект, связанный с компилятором? Чему ты больше всего научился?
Изменить: Спасибо всем за ваши отличные предложения. Я прошу прощения за то, что не обновлял это так долго.
Проект, который я закончил, был простой оптимизацией автовекторизации на LLVM. У LLVM есть векторные типы, но, кажется, нет никакого способа использовать их без поддержки внешнего интерфейса. Эта оптимизация преобразовала обычный скалярный код в векторный код.
Поскольку автоматическая векторизация - довольно сложная для реализации оптимизация, мы настолько ограничили нашу область применения. Во-первых, чтобы показать параллелизм на уровне команд в коде, мы искали циклы из одного блока, которые соответствовали нашим критериям, а затем развернули их определенное количество раз, чтобы они были удобно векторизованы. Затем мы реализовали алгоритм упаковки, изложенный в " Использование параллелизма на уровне суперслов с мультимедийными наборами команд " Ларсена и Амарасингхе.
Даже упрощенная версия этой оптимизации довольно сложна. Есть много ограничений; Например, вы не хотите векторизовать переменную, которая живет вне цикла, так как остальная часть программы ожидает, что она будет скалярной. Мы потратили много часов за последние несколько недель. Проект был очень веселым, и мы многому научились.
18 ответов
Если вы заинтересованы в оптимизации, то может быть интересной векторизация циклов с использованием наборов инструкций SSE и MMX.
С 8-недельным таймфреймом вам нужно быть осторожным с "ползучестью". Это не слишком амбициозно, особенно если этот проект включает в себя другие аспекты построения компилятора (lexing/parsing), или если вы все еще изучаете инструменты (отладчик, yacc) и промежуточные структуры данных (DAG).
Тем не менее, мое первое предложение было бы попробовать некоторые Live Variable Analysis. Алгоритмы довольно хорошо проработаны, так что вам достаточно просто кодировать их в соответствии с вашими структурами данных и т. Д.
Это позволит вам сделать ограниченную форму удаления мертвого кода. То есть, если вы обнаружите, что переменная объявлена, но никогда не используется, не выделяйте для нее место. Если вы обнаружите, что значение установлено, но никогда не читается, не генерируйте набор.
Live Variable Analysis также может помочь с Распределением регистра, так что вы можете решить и это, если есть время, и вы сможете повторно использовать часть того, что вы создали для удаления Dead Code.
Несколько лет назад я разработал DSL и написал компилятор для продукта, который произвела моя компания. DSL использовал странную комбинацию декларативных правил, управляемой событиями логики и композиционного наследования. Это был очень веселый проект, и я многому научился.
Это действительно пробудило во мне интерес к парсерам и компиляторам, поэтому я постарался не отставать от интересных новых разработок в технологии компиляторов.
Что касается оптимизации, вот забавная статья, которую я прочитал в прошлом году:
http://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf
В этой статье авторы описывают методику автоматического обнаружения оптимизаций глазка (превосходящую производительность нескольких популярных серверных частей компилятора C++) без необходимости написания кода для особых случаев. В их методике используются неконтролируемые алгоритмы обучения, позволяющие обнаружить ценную замену глазка.
После прочтения мне пришло в голову, что их подход может быть дополнен путем предоставления алгоритму "описания машины", в котором перечислены все инструкции (с их основными и побочными эффектами), поддерживаемые целевой архитектурой процессора. Тогда вместо того, чтобы использовать метод грубой силы для поиска эквивалентных последовательностей команд, решатель мог бы находить эти последовательности гораздо проще.
Алгоритм машинного обучения будет по-прежнему использовать эмпирические наблюдения для определения наиболее эффективной последовательности инструкций (поскольку кэш-эффекты, микрооперации и конвейерная обработка почти требуют эмпирических временных данных), но эквивалентность результатов может быть предсказана с использованием алгебраической проверки теорем, Опираясь на описание машины.
В статье они рассказывают о том, как их оптимизаторы могли обнаружить только последовательности замены глазка из двух или трех инструкций (потому что, в противном случае, поиск методом грубой силы занял бы слишком много времени и потребовал бы слишком много памяти). Размещение интеллектуального решателя в правильном месте в алгоритме может позволить ему работать с более длинными последовательностями замены.
Anyhoo... дайте мне знать, когда вы закончите с этим проектом! И не забудьте упомянуть меня в разделе "Благодарности"!;-)
Я думаю, что написание своего собственного простого встроенного языка сценариев было одним из самых интересных проектов, связанных с компилятором, которые я делал. Он научил меня каждому аспекту процесса от проектирования до концепции, и, поскольку я делал это с нуля, я мог сделать его настолько простым или сложным, насколько мне было нужно, что позволило мне понять концепции без большого шума, что изменило устоявшуюся Проект может иметь.
Для обучающих компиляторов наилучшим решением будет сделать это сквозным. Используя простую бэкэнд-машину, а не x86, выберите какую-нибудь простую машину, например MIPS. Я выполнил свой проект компилятора старшекурсников, нацеленный на симулятор PDP-11, который был отличной целью, поскольку все было очень просто. Благодаря некоторому примеру кода мы могли бы создать простой императивный языковой компилятор примерно за четыре недели. В C!
Сегодня с такими мощными языками, как ML, компилятор должен быть намного проще.
То, что вы делаете, должно зависеть от того, чем вы увлекаетесь. Если речь идет об оптимизации, найдите какую-то простую структуру, в которой все, что вам нужно для беспокойства.
Я думаю, что самая плодотворная область сегодня - компиляция для многопоточных целей или компиляция точно в срок.
Посмотрите на помощь проекта Shed Skin, который компилирует Python в C++. Я думаю, что в течение лета был сделан призыв о помощи. Определение способов улучшения компиляции на C++ обеспечит феноменальную оптимизацию программ на Python!
В дополнение к предложениям "Книги Дракона", я также настоятельно рекомендую Стивена С. Мучника "Усовершенствованное проектирование и внедрение компиляторов", который фокусируется на промежуточных представлениях, генерации кода и методах оптимизации.
Однажды я написал язык программирования и виртуальную машину для его запуска. Язык был способен взаимодействовать с функциями, написанными специально для того, что содержалось в DLL (это было до автоматизации OLE) в 16-битной Windows.
Все, что мне нужно было сделать спереди и сзади, дало мне отличное понимание языка с обеих сторон. В то время я читал различные книги по компиляторам (например, печально известную книгу о Драконах), но она так и не запала, пока я не написал что-то конкретное. Теперь, спустя много лет, работа, которую я проделал, дала мне более глубокое понимание и понимание таких вещей, как Java VM и CLR.
Рассмотрим вывод типа для существующего динамически типизированного языка.
В моем классе компиляторов старшекурсников мы сначала написали парсер рекурсивного спуска (сверху вниз) для языка, подобного Паскалю, с нуля: Lexical Analyzer, парсер, все.
Примерно в середине семестра мы переключились на генераторы синтаксического анализатора / сканера, такие как lex/yacc или flex/bison. Мы создали компилятор, который бы взял наше подмножество Pascal и скомпилировал его до сборки для стековой машины, которую нам дали (стековая машина очень проста, но принципы все те же).
Если вы заинтересованы в компиляторах, я не могу рекомендовать " Книгу Дракона". Он предназначен для обучения в 1 семестре, а во второй половине - в качестве курса для аспирантов и охватывает все теорию и оптимизацию, которые вы когда-либо могли пожелать. Даже Джоэл любит это. знак равно
ура
Вот еще одна идея... хотя она все еще немного неопределенная:
Большая часть оптимизации выполняется во время компиляции (кроме JIT-компиляторов, которые оптимизируют во время выполнения). Но есть также много возможностей для оптимизации во время соединения и во время установки.
Меня особенно интересует идея платформы, на которой вы не будете связывать ссылки до момента установки. Но во время этого процесса установки времени установки вы используете агрессивную стратегию оптимизации, поскольку вы знаете много подробной информации об архитектуре машины и можете принимать более тонкие и обоснованные решения по оптимизации.
Другие интересные проекты могут включать в себя:
Добавьте оптимизацию хвостового вызова в Sun JVM с открытым исходным кодом.
Добавьте именованную оптимизацию возвращаемого значения (NRVO) в виртуальные машины Python или Ruby.
Добавьте своевременную компиляцию регулярных выражений для вашей любимой цели (в.Net она уже есть. Я почти уверен, что в Java ее нет).
Хотя написание собственного языка - это интересная и традиционная академическая деятельность, уже существует слишком много плохо реализованных проектов, связанных с компилятором. Кроме того, 8 недель не хватает времени, чтобы хорошо поработать над полной языковой реализацией.
Если вас интересует "что-то, связанное с оптимизацией", выберите уже существующий язык или ВМ и оптимизируйте его по производительности, размеру или обоим параметрам. Это избавит вас от необходимости заново изобретать полную языковую реализацию, позволит вам сосредоточиться на проблеме оптимизации, создаст продукт, полезный для других людей, а не просто еще одно академическое упражнение, и даже может оказаться полезным для получения работы.
Я считаю, что интерпретатор байт-кода Parrot и различные синтаксические анализаторы.Net Iron могут выиграть даже от простой оптимизации.
Обнаружение петли и параметризованное развертывание должно быть достаточно сложным, чтобы сделать его интересным. Не очень сексуально, но слишком сексуально за 8 недель вас потонет.
Я сделал это в своем собственном учении "когда-нибудь". Я не стал бы уделять столько внимания оптимизации, как другим вещам, таким как вывод типов или JIT, байтовое кодирование или поддержка формата / отладки объектов.
Нет ничего плохого в том, чтобы сконцентрироваться на оптимизации, если вы также говорите, что это намного менее важно, чем думают люди. В коде имеет значение только то, что:
- работает в тесных циклах в нижней части стека вызовов (т.е. без вызова функций, явно или неявно)
- на самом деле занимает значительный процент времени приложения (т. е. если код запускается редко, его оптимизация не сильно поможет).
Это довольно небольшая часть всего кода, который увидит компилятор.
Редактировать: К сожалению, я не могу избежать работы с компиляторами Фортрана, которые беспощадно шифруют код, делая его очень трудным для отладки, в то же время влияя на производительность.
Вы можете написать оптимизатор для IronScheme, так как в настоящее время он делает все, кроме нескольких "встроенных" функций. :)
Автоматическая генерация встроенного кода с использованием эвристических тестов для компромиссов между размером и скоростью.
Компилятор Perl B::CC выиграет от добавления и анализа типов. У меня просто нет на это времени.
В последнее время было достаточно времени. http://blogs.perl.org/users/rurban/2011/02/use-types.html