Что нового в методах оптимизации компилятора за последние несколько лет?

14

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

Евгений Гаврин
источник
2
В своей диссертации ( слайды ) я обсуждал и реализовывал выравнивание графов вызовов в LLVM; в основном это межпроцедурное преобразование, которое избавляет от понятия «функция», потому что оно объединяет весь код, предоставляя кучу интересных возможностей, таких как движение межпроцедурного кода, соглашения о вызовах, оптимизированные по месту вызова, выполнение без стека и так далее.
CAFxX
@CAFxX: слайды разбились Open Office .. у вас есть фотографии в Интернете?
Иттрилл
@Yttrill: slideshare.net/CAFxX/…
CAFxX
Спасибо, с этим можно было ознакомиться, хотя графики должны были быть хорошо видны, текст был хорош.
Иттрилл

Ответы:

8

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

Они ссылаются на алгоритм 2002 года Лернера, Гроува и Чамберса, который объединяет простые оптимизации в «супероптимизацию».

Максимум
источник
8

Я полагаю, что метод Equality Saturation , как другой подход к проблеме оптимизации проходов, будет уместен. Насколько мне известно, это пока не доказано практической конкретной реализацией в полноценном компиляторе. Следующая Генерация Оптимизации Компилятора из Испытаний может также представлять интерес.

gasche
источник
6

Было немного возрождения в проверенных оптимизирующих компиляторах. В дополнение к статье Лернера (упомянутой в предыдущем комментарии), вы можете посмотреть на проект CompCert, которым руководит Ксавье Леруа. Они сделали несколько классных вещей с указанием оптимизаций в качестве проверяемых компьютером доказательств (используя Coq ). Я еще не читал статьи, но проект Verified Software Toolchain в Принстоне, похоже, также дает интересные результаты в этой области.

Джон Лассетер
источник
1
Мы также работаем над проектом, похожим на CompCert: CerCo ( cerco.cs.unibo.it ). В отличие от CompCert, мы стремимся создать проверенный конкретный компилятор, сохраняющий стоимость для большого подмножества C (CompCert показывает только то, что свойства расширения исходной программы сохраняются при компиляции). Мы также реализуем в компиляторе несколько умеренно сложных циклических оптимизаций, а также «мягкие» оптимизации, такие как CompCert, которые, конечно, должны быть проверены как экономящие средства.
Доминик Маллиган
5

Признавая, что baz [i] + = force (foo [i], foo [j]) в двойном цикле FOR имеет независимые результаты для (i, j), и переупорядочиваем вызовы в кривую заполнения пространства на (i, j), чтобы сократить кэш промахи.

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

Чад Brewbaker
источник