Удаление общих подвыражений

Поделись знанием:
Перейти к: навигация, поиск

Удаление общих подвыражений (англ. Common subexpression elimination или CSE) — оптимизация компилятора, которая ищет в программе вычисления, выполняемые более одного раза на рассматриваемом участке, и удаляет вторую и последующие одинаковые операции, если это возможно и эффективно. Данная оптимизация требует проведения анализа потока данных (англ.) для нахождения избыточных вычислений и практически всегда улучшает время выполнения программы в случае применения[1].





Обобщенное описание задачи

Подвыражение в программе называется общим подвыражением, если существует другое такое же подвыражение, которое всегда вычисляется перед данным, и операнды не изменяются в промежутке между вычислениями. Например, в рассматриваемом ниже примере выражение b * c является общим подвыражением.

Исходя из данного определения, удаление общих подвыражений — это преобразование, которое уничтожает повторные вычисления общих подвыражений и заменяет их на использование сохраненного после первого вычисления значения. Однако, в рассматриваемом примере нельзя сразу при вычислении d заменить общее подвыражение на значение переменной a, т.к. данная переменная может изменяться между рассматриваемыми вычислениями.

Рассмотрим следующий фрагмент кода:

a = b * c + g;
d = b * c * d;

К нему применимо следующее преобразование:

tmp = b * c;
a = tmp + g;
d = tmp * d;

которое окажется эффективным, если суммарное время записи и нескольких чтений новой переменной "tmp" окажется меньше, чем суммарное время, затрачиваемое на вычисление выражения "b * c" каждый раз, когда оно встречается в коде.

Различают два вида данной оптимизации:

  • локальное удаление общих подвыражений, которое работает в пределах одного линейного участка;
  • глобальное удаление общих подвыражений, которое работает в пределах целой процедуры.

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

Принцип

Применение оптимизации основано на анализе доступных выражений. Выражение x + y является доступным в некоторой точке p программы, если:[2]

  • вдоль любого пути от начального узла к p выражение x + y вычисляется до достижения точки p;
  • между вычислениями выражений и достижением точки p нет изменения значений переменных x и y.

Эффективность преобразования главным образом определяется тем, что суммарное время записи и нескольких чтений новой переменной "tmp" оказывается меньше, чем суммарное время, затрачиваемое на вычисление выражения "b * c" каждый раз, когда оно встречается в коде. На практике на итоговую эффективность влияет также ряд других факторов, в частности распределение переменных по регистрам.

Выгода

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

В случае глобального применения оптимизации на выгоду влияют дополнительные критерии. Например, надо учитывать счётчики исполнения базовых блоков, так как, сократив статическое количество вычислений выражения, можно увеличить динамическое, что влияет отрицательно на кол-во выполненных операций в программе. Это приводит к тому, что может быть выгодна обратная оптимизация, относящаяся к классу PRE (partial redundancy elimination).

Напишите отзыв о статье "Удаление общих подвыражений"

Примечания

Литература

  • Альфред Ахо, Моника Лам, Рави Сети, Джеффри Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е издание. — М.: «Вильямс», 2008. — 1184 с. — 1500 экз. — ISBN 978-5-8459-1349-4.
  • Steven S. Muchnick. Advanced Compiler Design and Implementation. — 5-е издание. — San Francisco: Morgan Kaufmann Publishers, 1997. — С. 378-396. — 856 с. — ISBN 1-55860-320-4.
  • John Cocke. [dl.acm.org/citation.cfm?id=390013.808480 "Global Common Subexpression Elimination."] Proceedings of a Symposium on Compiler Construction, ACM SIGPLAN Notices 5(7), July 1970, pages 850-856.
  • Briggs, Preston, Cooper, Keith D., and Simpson, L. Taylor. "Value Numbering." Software-Practice and Experience, 27(6), June 1997, pages 701-724.

Отрывок, характеризующий Удаление общих подвыражений

– Mais non, mon cher, [Вовсе нет,] – пожимая плечами, сказал удивленный рассказчик.
– C'est que je deteste les histoires de revenants, [Дело в том, что я терпеть не могу историй о привидениях,] – сказал он таким тоном, что видно было, – он сказал эти слова, а потом уже понял, что они значили.
Из за самоуверенности, с которой он говорил, никто не мог понять, очень ли умно или очень глупо то, что он сказал. Он был в темнозеленом фраке, в панталонах цвета cuisse de nymphe effrayee, [бедра испуганной нимфы,] как он сам говорил, в чулках и башмаках.
Vicomte [Виконт] рассказал очень мило о том ходившем тогда анекдоте, что герцог Энгиенский тайно ездил в Париж для свидания с m lle George, [мадмуазель Жорж,] и что там он встретился с Бонапарте, пользовавшимся тоже милостями знаменитой актрисы, и что там, встретившись с герцогом, Наполеон случайно упал в тот обморок, которому он был подвержен, и находился во власти герцога, которой герцог не воспользовался, но что Бонапарте впоследствии за это то великодушие и отмстил смертью герцогу.
Рассказ был очень мил и интересен, особенно в том месте, где соперники вдруг узнают друг друга, и дамы, казалось, были в волнении.
– Charmant, [Очаровательно,] – сказала Анна Павловна, оглядываясь вопросительно на маленькую княгиню.
– Charmant, – прошептала маленькая княгиня, втыкая иголку в работу, как будто в знак того, что интерес и прелесть рассказа мешают ей продолжать работу.
Виконт оценил эту молчаливую похвалу и, благодарно улыбнувшись, стал продолжать; но в это время Анна Павловна, все поглядывавшая на страшного для нее молодого человека, заметила, что он что то слишком горячо и громко говорит с аббатом, и поспешила на помощь к опасному месту. Действительно, Пьеру удалось завязать с аббатом разговор о политическом равновесии, и аббат, видимо заинтересованный простодушной горячностью молодого человека, развивал перед ним свою любимую идею. Оба слишком оживленно и естественно слушали и говорили, и это то не понравилось Анне Павловне.
– Средство – Европейское равновесие и droit des gens [международное право], – говорил аббат. – Стоит одному могущественному государству, как Россия, прославленному за варварство, стать бескорыстно во главе союза, имеющего целью равновесие Европы, – и она спасет мир!
– Как же вы найдете такое равновесие? – начал было Пьер; но в это время подошла Анна Павловна и, строго взглянув на Пьера, спросила итальянца о том, как он переносит здешний климат. Лицо итальянца вдруг изменилось и приняло оскорбительно притворно сладкое выражение, которое, видимо, было привычно ему в разговоре с женщинами.
– Я так очарован прелестями ума и образования общества, в особенности женского, в которое я имел счастье быть принят, что не успел еще подумать о климате, – сказал он.
Не выпуская уже аббата и Пьера, Анна Павловна для удобства наблюдения присоединила их к общему кружку.


В это время в гостиную вошло новое лицо. Новое лицо это был молодой князь Андрей Болконский, муж маленькой княгини. Князь Болконский был небольшого роста, весьма красивый молодой человек с определенными и сухими чертами. Всё в его фигуре, начиная от усталого, скучающего взгляда до тихого мерного шага, представляло самую резкую противоположность с его маленькою, оживленною женой. Ему, видимо, все бывшие в гостиной не только были знакомы, но уж надоели ему так, что и смотреть на них и слушать их ему было очень скучно. Из всех же прискучивших ему лиц, лицо его хорошенькой жены, казалось, больше всех ему надоело. С гримасой, портившею его красивое лицо, он отвернулся от нее. Он поцеловал руку Анны Павловны и, щурясь, оглядел всё общество.
– Vous vous enrolez pour la guerre, mon prince? [Вы собираетесь на войну, князь?] – сказала Анна Павловна.
– Le general Koutouzoff, – сказал Болконский, ударяя на последнем слоге zoff , как француз, – a bien voulu de moi pour aide de camp… [Генералу Кутузову угодно меня к себе в адъютанты.]
– Et Lise, votre femme? [А Лиза, ваша жена?]
– Она поедет в деревню.
– Как вам не грех лишать нас вашей прелестной жены?
– Andre, [Андрей,] – сказала его жена, обращаясь к мужу тем же кокетливым тоном, каким она обращалась к посторонним, – какую историю нам рассказал виконт о m lle Жорж и Бонапарте!
Князь Андрей зажмурился и отвернулся. Пьер, со времени входа князя Андрея в гостиную не спускавший с него радостных, дружелюбных глаз, подошел к нему и взял его за руку. Князь Андрей, не оглядываясь, морщил лицо в гримасу, выражавшую досаду на того, кто трогает его за руку, но, увидав улыбающееся лицо Пьера, улыбнулся неожиданно доброй и приятной улыбкой.