LLVM и будущее оптимизации - PullRequest
14 голосов
/ 13 июля 2011

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

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

Ответы [ 7 ]

21 голосов
/ 13 июля 2011

В общем, нет.

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

Объяснение: В Haskell функция (Int, Int) -> Int более или менее эквивалентна типу в C:

typedef int (*returns_int)();
struct pair { returns_int first, second};
typedef struct pair *(*returns_pair)();

int function(returns_pair arg);

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

int function(int x, int y); // note that it takes *two* arguments now

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

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

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

10 голосов
/ 13 июля 2011

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

Например, относительно легко оптимизировать код C для максимизации эффективности кэша (сокращения медленного чтения из памяти), в то время как в Haskell это намного сложнее. Взлом указателя невозможен в Java. Как и стратегия выделения огромного куска памяти и ее выделения вручную.

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

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

Редактировать: Указатель хаки в Haskell. Так много возможностей ...

5 голосов
/ 22 июля 2011

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

В компиляторе всегда будет несколько этапов оптимизации.

  • Некоторые оптимизации зависят от правил языка, например, в C ++ вы можете оптимизировать некоторые вызовы конструкторов копирования / перемещения.
  • Некоторые оптимизации широко доступны (циклические преобразования, оконечные вызовы)
  • Некоторые оптимизации зависят от аппаратного обеспечения (SSE, MMX)

Компилятор LLVM применяет все 3 ... но, начиная с LLVM IR, а не с C, Java или чего-либо еще.

Работа переднего конца заключается в предоставлении подходящего ИК LLVM.

Например, как отмечает @Dietrich Epp, ИК не очень подходит для функциональных языков. Поэтому необходимо выполнить множество оптимизаций на Haskell до , когда представление понижено до IR.

Другим источником неоптимизации является то, что специфическая среда выполнения может поставляться с языками. У Haskell есть сложная среда выполнения с пулом искр, легкими потоками, вытеснением перед системными вызовами, кражами работы и т. Д. IR не подходит для представления этой богатой среды, и в этой организации не производится оптимизация.

2 голосов
/ 21 июля 2011

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

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

1 голос
/ 07 августа 2011

Возвращаясь к вашему вопросу "теоретически это возможно?" , давайте представим / предположим - просто для обсуждения - следующее:

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

ИМХО - с точки зрения информатики, это в основном вопрос ресурсов, применять почти все.

Теперь давайте попробуем следовать

function machinecode_to_sourcecode( given_machinecode ){
  it = all_posibble_strings_iterator()
  while (true) {
    possible_sourcecode = it->get_string()
    machine_code = compile possible_sourcecode with X
    if (compilation succeeded)
        if(machine_code == given_machinecode)
           return possible_sourcecode;
    else
       it = it->next_string()
  }
}

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

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

Все выглядит очень дорого, но, как вы спросили "теоретически", я скажу

  • это займет конечное количество времени

потому что

  • исходный код имеет конечную длину

так

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

Вся операция займет конечное время вычислений.

0 голосов
/ 07 августа 2011

Здесь я нашел отчет с легким для начинающих обзором различий между GCC и LLVM: Отчет об оценке зрелости Clang / LLVM от Dominic Fandrey

0 голосов
/ 13 июля 2011

Я не знаю никаких подробностей о формате байт-кода, используемого LLVM, но я думаю, что ответ на ваш вопрос - нет.

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

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

...