Какие виды оптимизации выполняет LLVM и какие виды оптимизации должны реализовывать его интерфейсы? - PullRequest
7 голосов
/ 05 сентября 2011

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

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

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

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

Ответы [ 2 ]

6 голосов
/ 05 сентября 2011

Это, вероятно, сильно зависит от языка ... Clang (C / C ++) может делать очень мало с точки зрения оптимизации во внешнем интерфейсе.Единственная оптимизация, которую я могу придумать, выполняется для производительности сгенерированного кода, это то, что clang выполняет некоторую девиртуализацию методов C ++ во внешнем интерфейсе.clang выполняет некоторые другие оптимизации, такие как постоянное свертывание и устранение мертвого кода, но в основном это делается для ускорения времени компиляции, а не для производительности сгенерированного кода.

РЕДАКТИРОВАТЬ: На самом деле, думаяоб этом чуть больше, я только что вспомнил еще одну важную оптимизацию, которую выполняет clang для C ++: clang знает несколько хитростей, чтобы исключить конструкторы копирования в C ++ (google для NRVO).

В некоторых случаях IR для конкретного языкаОптимизация может быть полезна.Существует проход SimplifyLibCalls, который знает, как оптимизировать вызовы в стандартную библиотеку C.Для новой функции языка ARC в Objective-C clang помещает в конвейер некоторые проходы, специфичные для ARC;они оптимизируют вызовы различных функций времени выполнения Objective C.

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

См. Также http://llvm.org/docs/tutorial/LangImpl7.html;Правильное использование alloca - это одна вещь, которая существенно помогает оптимизаторам, хотя сама по себе она не является оптимизацией.

2 голосов
/ 06 сентября 2011

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

С другой стороны, языком LLVM является RISC , поэтому теряется много информации высокого уровня.

Итак, answer : front-end способен выполнять оптимизацию, требующую потери информации после перевода в SSA. Примеры, которые приходят мне на ум:

  • предпочтительные оптимизации ветвления, некоторые примеры
    • языки. расширения, такие как объявление предпочтительных веток (в ядре Linux некоторые ветки помечаются как почти всегда выполняемые)
    • реализация бросающих и ловящих исключений
    • Совместная реализация и информация о зависимостях
  • Оптимизации, которые растут в геометрической прогрессии (например, увеличение размера кода при циклическом переключении), возможно, потребуется применить к конкретным местам в соответствии с информацией высокого уровня. - может быть из исходного кода (front-end).
  • языковые особенности (это может быть отражение или что-то еще), которые переводятся в «много-указательные» (например, указатели на указатели ...) взаимосвязанные структуры, которые может быть трудно угадать на низком уровне - как на низком уровне, все может выглядеть как доступ к массиву, в то время как он может иметь некоторые ограничения на уровне высоты, которые могут помочь в оптимизации.
  • сложные функции могут быть реализованы по-разному в зависимости от доступного оборудования. Давайте возьмем несколько примеров: умножение матриц, преобразование БПФ (алгоритмы сжатия и распаковки), арифметика больших чисел и т. Д. И т. Д. ... в зависимости от базового оборудования это может быть реализовано по-разному для достижения максимальной производительности. После перевода материала в LLVM может быть очень-очень-очень дорого (с точки зрения сложности вычислений) изменить реализацию на более подходящую для имеющегося оборудования. Вот почему решение должно приниматься внешним интерфейсом при компиляции в более низкий уровень.

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

...