Pull to refresh

Comments 36

Устранение общих подвыражений порадовало. Только в сложных программах, наверное, сложно делать подобные оптимизации.

А как обстоят дела по отношению к циклам? Например, будет ли цикл for(i=0; i<2; i++) развёрнут в линейную структуру? При генерации Schematic из VHDL такое точно может происходить
По оптимизациям циклов будет отдельная часть )
В gcc, если мне не изменяет память, есть опция -funroll-loops, которая может разворачивать циклы. Более хитрая оптимизация — swing modulo scheduling, которая умеет выносить из цикла пролог и эпилог с целью уменьшить зависимость по данным внутри одной итерации цикла. А вообще, с циклами много всего есть, поэтому это действительно тема для отдельной части.
> Устранение/Исключение недоступного кода

Недоступный код — unreachable code. Понятие dead code шире — это любой код, который можно удалить не повлияв на результат выполнения програмы. Например, вычисление значения, которое потом не используется нигде. Некоторые бенчмарки грешат тем, что их вычислительная часть по сути dead code.

> А теперь представьте сколько эта оптимизация экономит процессорного времени в рамках большой вычислительной программы.
Устранение общих подвыражений уменьшает количество вычислений, но увеличивает количество живых переменных и тем самым давление на регистры. Поэтому если регистров мало, а выражние простое (стоит меньше чем скажем чтение из памяти), то получается CSE может легко повредить и может надо наоборот делать rematerialization в местах использования.
Да, вы правы, пожалуй я смешал unreachable code elimination и dead code elimination

Устранение общих подвыражений уменьшает количество вычислений, но увеличивает количество живых переменных и тем самым давление на регистры. Поэтому если регистров мало, а выражние простое (стоит меньше чем скажем чтение из памяти), то получается CSE может легко повредить и может надо наоборот делать rematerialization в местах использования.
разве? это для простоты в коде представлено так, как у меня, но на деле, во внутреннем представлении (например, SSA) CSE значительно уменьшит использование регистров, а не увеличит
Скажем так, в моем комментарии было пропущено слово «может», может увеличить, может уменьшить. Представьте допустим, что у нас код:

for (int i = 0; i < N; i++) s += calc(i, j);


мы выполняем открытую подстановку, а потом CSE. после чего оказывается, что в точке где к s прибавляется результат calc у нас живы: i, j, s, tmp1, tmp2, tmp3 (можно считать на x86 регистры почти кончились), а в оригинальном коде живы i, j, s, a, b.

Может так оказаться, что только a * b элиминировать (живы i, j, s, tmp3) выгоднее.

Важно тут не количество переменных (в IR действительно a * b уже само по себе сидит во временной переменной), важно количество живых переменных в каждой отдельно взятой точке программы и удлиннение промежутков жизни для временных переменных.
UFO just landed and posted this here
Статья очень интересная, но примеры слишком очевидные и простые. Поэтому ждем второй части, с оптимизациями посложнее.
Спасибо за статью, очень интересно. Будет так же интересно почитать что-нибудь на тему ран-тайм оптимизаций в динамических языках, если это конечно возможно :)
>> Устранение общих подвыражений
эта оптимизация(как и туча других) была бы гораздо полезнее, если бы в выражениях могли бы участвовать не только локальные переменные, но и вызовы функций. А для этого нужно уметь определять является ли функции чистыми. Либо дать возможность программисту давать хинт компилятору по этому поводу… ИМХО такая фича весьма и весьма помогла бы и в деле ускорения программ, и вообще в понятности кода.
В некоторых компиляторах есть такие хинты. Например __pure в Keil CC.
Кстати, очень часто компиляторы не только удаляют unreachable code, но и ещё и ругаются на него ворнингами. А в специфичных случаях — ошибками.
Ибо наличие такого кода обычно сигнализирует о том, что программист где-то ошибся.
А если просто подключена библиотека с функциями? Не все же используются.
А в таких случаях выкидываются сразу функции целиком, и этим занимается обычно линковщик, а не компилятор.
Кроме случае whole program optimization, как я понимаю. Но это отдельная непростая тема :)
Кстати да — какой вообще статус у whole program optimization. По мне так это именно то что должно координально уменьшить размер программы а также ускорить ее. Но насколько я понял в GCC это все еще в зачаточном состоянии. Это так?
Было бы интересно узнать, насколько успешно разные компиляторы справляются с этими и другими оптимизациями.
Конкретно с этими очень успешно.
UFO just landed and posted this here
ну это может быть 16-битная архитектура, а может быть ошибка автора :)
да, спасибо, действительно, я ошибся… сначала «p» был просто int'ом. Код изменил, а размер поправить забыл.
> Тогда для нахождения числовых выражений и подвыражений достаточно искать соседние узлы дерева, содержащие числовые значения, причём ТОЛЬКО числовые значения.
Это не совсем так, эта оптимизация обычно еще учитывает ассоциативность и коммутативность операций.
Например, 16 + a + 2, может в дереве выглядеть как plus(16, plus(a, 2)).
спасибо, очень меткое замечание, я немного исправил формулировку.
Вопрос к аудитории — есть ли интерес к более подробному описанию классических и не очень оптимизаций? Если да, то почему — для общего развития, применимо к работе или что-то ещё?

Иногда просыпается желание написать что-то подобное, но не совсем понятно кому это может быть интересно и на чём делать акценты, насколько углубляться в ньюансы и т.д.
Есть, для общего развития :) Можно начать с чего-то общего. Если людям будет интересно, наверняка в комментариях будут просьбы описать что-то конкретное.
Если это будет не пересказ соответствующих глав Dragon Book своими словами, а что-то там не затронутое, то интересно.
В DCE было бы интересней последней строкой печатать y, а не x — можно продемонстрировать многопроходность оптимизации.

Кстати попробуйте для рисования графов yEd — многие хвалят.
Спасибо за статью. Интересный материал и хорошая компоновка текста в статье — одно удовольствие читать. Некоторым авторам этого не достает!
«как бы не улучшала оптимизация характеристики программы, она обязательно должна сохранять изначальный смысл программы при любых условиях. Именно поэтому, например, в GCC существуют различные уровни оптимизации»

По моему уровни оптимизации существуют не поэтому — в идеале любая оптимизация должна сохранять смысл программы (в gcc это к сожалению не так, и встречаются опции, которые меняют результат, в основном правда при вычислениях с плавающей запятой).
Есть отличная статья про уровни оптимизации.
Супер, очень интересна эта тема, особенно проект LLVM. Спасибо за статью. Очень хотел бы увидеть продолжение.
<зануда>
В самой первой оптимизации (Constant folding) самое первое AST кажется неприавльно нарисовано. Разве не должно быть так:
- Объявление переменной: int a
- Присваивание =
        - a
        - Умножение *
                - 32
                - 32

Ну то есть присванивание тоже оператор и у него два операнда, которые должны быть его сыновьями в дереве.
</зануда>
Кстати, во всех AST так. Простите за занудство.
Sign up to leave a comment.

Articles