Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 36
позновательно, буду ждать второй части
Устранение общих подвыражений порадовало. Только в сложных программах, наверное, сложно делать подобные оптимизации.
А как обстоят дела по отношению к циклам? Например, будет ли цикл for(i=0; i<2; i++) развёрнут в линейную структуру? При генерации Schematic из VHDL такое точно может происходить
А как обстоят дела по отношению к циклам? Например, будет ли цикл for(i=0; i<2; i++) развёрнут в линейную структуру? При генерации Schematic из VHDL такое точно может происходить
По оптимизациям циклов будет отдельная часть )
В gcc, если мне не изменяет память, есть опция -funroll-loops, которая может разворачивать циклы. Более хитрая оптимизация — swing modulo scheduling, которая умеет выносить из цикла пролог и эпилог с целью уменьшить зависимость по данным внутри одной итерации цикла. А вообще, с циклами много всего есть, поэтому это действительно тема для отдельной части.
> Устранение/Исключение недоступного кода
Недоступный код — unreachable code. Понятие dead code шире — это любой код, который можно удалить не повлияв на результат выполнения програмы. Например, вычисление значения, которое потом не используется нигде. Некоторые бенчмарки грешат тем, что их вычислительная часть по сути dead code.
> А теперь представьте сколько эта оптимизация экономит процессорного времени в рамках большой вычислительной программы.
Устранение общих подвыражений уменьшает количество вычислений, но увеличивает количество живых переменных и тем самым давление на регистры. Поэтому если регистров мало, а выражние простое (стоит меньше чем скажем чтение из памяти), то получается CSE может легко повредить и может надо наоборот делать rematerialization в местах использования.
Недоступный код — unreachable code. Понятие dead code шире — это любой код, который можно удалить не повлияв на результат выполнения програмы. Например, вычисление значения, которое потом не используется нигде. Некоторые бенчмарки грешат тем, что их вычислительная часть по сути dead code.
> А теперь представьте сколько эта оптимизация экономит процессорного времени в рамках большой вычислительной программы.
Устранение общих подвыражений уменьшает количество вычислений, но увеличивает количество живых переменных и тем самым давление на регистры. Поэтому если регистров мало, а выражние простое (стоит меньше чем скажем чтение из памяти), то получается CSE может легко повредить и может надо наоборот делать rematerialization в местах использования.
Да, вы правы, пожалуй я смешал unreachable code elimination и dead code elimination
Устранение общих подвыражений уменьшает количество вычислений, но увеличивает количество живых переменных и тем самым давление на регистры. Поэтому если регистров мало, а выражние простое (стоит меньше чем скажем чтение из памяти), то получается CSE может легко повредить и может надо наоборот делать rematerialization в местах использования.разве? это для простоты в коде представлено так, как у меня, но на деле, во внутреннем представлении (например, SSA) CSE значительно уменьшит использование регистров, а не увеличит
Скажем так, в моем комментарии было пропущено слово «может», может увеличить, может уменьшить. Представьте допустим, что у нас код:
мы выполняем открытую подстановку, а потом CSE. после чего оказывается, что в точке где к s прибавляется результат calc у нас живы: i, j, s, tmp1, tmp2, tmp3 (можно считать на x86 регистры почти кончились), а в оригинальном коде живы i, j, s, a, b.
Может так оказаться, что только a * b элиминировать (живы i, j, s, tmp3) выгоднее.
Важно тут не количество переменных (в IR действительно a * b уже само по себе сидит во временной переменной), важно количество живых переменных в каждой отдельно взятой точке программы и удлиннение промежутков жизни для временных переменных.
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 уже само по себе сидит во временной переменной), важно количество живых переменных в каждой отдельно взятой точке программы и удлиннение промежутков жизни для временных переменных.
Статья очень интересная, но примеры слишком очевидные и простые. Поэтому ждем второй части, с оптимизациями посложнее.
Спасибо за статью, очень интересно. Будет так же интересно почитать что-нибудь на тему ран-тайм оптимизаций в динамических языках, если это конечно возможно :)
>> Устранение общих подвыражений
эта оптимизация(как и туча других) была бы гораздо полезнее, если бы в выражениях могли бы участвовать не только локальные переменные, но и вызовы функций. А для этого нужно уметь определять является ли функции чистыми. Либо дать возможность программисту давать хинт компилятору по этому поводу… ИМХО такая фича весьма и весьма помогла бы и в деле ускорения программ, и вообще в понятности кода.
эта оптимизация(как и туча других) была бы гораздо полезнее, если бы в выражениях могли бы участвовать не только локальные переменные, но и вызовы функций. А для этого нужно уметь определять является ли функции чистыми. Либо дать возможность программисту давать хинт компилятору по этому поводу… ИМХО такая фича весьма и весьма помогла бы и в деле ускорения программ, и вообще в понятности кода.
В некоторых компиляторах есть такие хинты. Например __pure в Keil CC.
__attribute__((pure)) в gcc, начиная с gcc3.
Вспомнилась замечательная история про оптимизацию xD: ithappens.ru/story/2959
Кстати, очень часто компиляторы не только удаляют unreachable code, но и ещё и ругаются на него ворнингами. А в специфичных случаях — ошибками.
Ибо наличие такого кода обычно сигнализирует о том, что программист где-то ошибся.
Ибо наличие такого кода обычно сигнализирует о том, что программист где-то ошибся.
Было бы интересно узнать, насколько успешно разные компиляторы справляются с этими и другими оптимизациями.
> Тогда для нахождения числовых выражений и подвыражений достаточно искать соседние узлы дерева, содержащие числовые значения, причём ТОЛЬКО числовые значения.
Это не совсем так, эта оптимизация обычно еще учитывает ассоциативность и коммутативность операций.
Например, 16 + a + 2, может в дереве выглядеть как plus(16, plus(a, 2)).
Это не совсем так, эта оптимизация обычно еще учитывает ассоциативность и коммутативность операций.
Например, 16 + a + 2, может в дереве выглядеть как plus(16, plus(a, 2)).
Вопрос к аудитории — есть ли интерес к более подробному описанию классических и не очень оптимизаций? Если да, то почему — для общего развития, применимо к работе или что-то ещё?
Иногда просыпается желание написать что-то подобное, но не совсем понятно кому это может быть интересно и на чём делать акценты, насколько углубляться в ньюансы и т.д.
Иногда просыпается желание написать что-то подобное, но не совсем понятно кому это может быть интересно и на чём делать акценты, насколько углубляться в ньюансы и т.д.
В DCE было бы интересней последней строкой печатать y, а не x — можно продемонстрировать многопроходность оптимизации.
Кстати попробуйте для рисования графов yEd — многие хвалят.
Кстати попробуйте для рисования графов yEd — многие хвалят.
Спасибо за статью. Интересный материал и хорошая компоновка текста в статье — одно удовольствие читать. Некоторым авторам этого не достает!
«как бы не улучшала оптимизация характеристики программы, она обязательно должна сохранять изначальный смысл программы при любых условиях. Именно поэтому, например, в GCC существуют различные уровни оптимизации»
По моему уровни оптимизации существуют не поэтому — в идеале любая оптимизация должна сохранять смысл программы (в gcc это к сожалению не так, и встречаются опции, которые меняют результат, в основном правда при вычислениях с плавающей запятой).
Есть отличная статья про уровни оптимизации.
По моему уровни оптимизации существуют не поэтому — в идеале любая оптимизация должна сохранять смысл программы (в gcc это к сожалению не так, и встречаются опции, которые меняют результат, в основном правда при вычислениях с плавающей запятой).
Есть отличная статья про уровни оптимизации.
Супер, очень интересна эта тема, особенно проект LLVM. Спасибо за статью. Очень хотел бы увидеть продолжение.
<зануда>
В самой первой оптимизации (Constant folding) самое первое AST кажется неприавльно нарисовано. Разве не должно быть так:
Ну то есть присванивание тоже оператор и у него два операнда, которые должны быть его сыновьями в дереве.
</зануда>
В самой первой оптимизации (Constant folding) самое первое AST кажется неприавльно нарисовано. Разве не должно быть так:
- Объявление переменной: int a
- Присваивание =
- a
- Умножение *
- 32
- 32
Ну то есть присванивание тоже оператор и у него два операнда, которые должны быть его сыновьями в дереве.
</зануда>
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Оптимизации в компиляторах. Часть 1