А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 144
Текст из файла (страница 144)
707 9.1. Основные источники оптимизации При компиляции программы каждое из таких обращений к высокоуровневым структурам данных разворачивается в ряд низкоуровневых арифметических операций, таких как вычисление (1,7')-го элемента матрицы А. Обращения к одной и той же структуре данных часто используют много одинаковых низкоуровневых операций. Программист не осведомлен об этих операциях и не может устранить их избыточность самостоятельно.
Более того, с точки зрения инженерии программного обеспечения предпочтительно, чтобы программист обращался к элементам данных только по их высокоуровневым именам; такие программы проще писать и, что более важно, проше понимать и развивать. Обладая компилятором с устранением избыточности, мы получаем лучшее из двух миров — программы оказываются одновременно эффективными и легко поддерживаемыми. 9.1.2 Конкретный пример: быстрая сортировка Далее для иллюстрации некоторых важных улучшаюших код преобразований мы будем использовать фрагмент программы быстрой сортировки дп!с~Ьогс Программа на С на рис. 9.1 взята у Седжвика (Яебдетч]с]г)!, который рассматривал варианты ручной оптимизации этой программы.
Мы не будем рассматривать все тонкости этой программы, например тот факт, что элемент а [О] должен содержать наименьший из сортируемых элементов, а а [тах] — наибольший. Перед тем как мы сможем оптимизировать код путем удаления избыточности в вычислениях адресов, операции с адресами должны быть разбиты на низкоуровневые арифметические операции для выявления избыточности. В оставшейся части этой главы мы полагаем, что промежуточное представление состоит из трехадресных инструкций, а для хранения всех результатов промежуточных выражений используются временные переменные.
Промежуточный код для помеченного фрагмента программы на рис. 9.1 приведен на рис. 9.2. В этом примере мы полагаем, что размер целого числа — 4 байт. Присваивание х = а[1] транслируется, как в разделе 6.4.4, в две приведенные в шагах 14 и 15 на рис. 9.2 трехадресные инструкции: сб = 4*1 х = а[сб] Аналогично а [ т ] = х в шагах 20 и 21 преврашается в т.10 = 4*7 а[с10] = х Обратите внимание, что каждое обращение к массиву в исходной программе транслируется в пару шагов, состоящих из умножения и оператора индексирова- 'К. 8ейяев!с1с, "1тр!етеп!!пя ! >а!сх4ол Рговтюпя", Соте.
АСМ, 21, !978, рр. 847-857. 708 Глава 9. Машинно-независимые оптимизации чоЫ с[ийс)свох~(1п1 ш, 1пс и) /* Рекурсивная сортировка диапазона от а[в] до а[п] */ 1п~ 1, 1п~ ч, х; 1й (и <= гп) ге~окпз /* Начало фрагмента */ 1 = ш-11 3 = и; ч = а[п]; ы)з11е (1) ( с(о 1 = 1+1; ы)з11е (а[1] < ч); с1о З = Э-11 и)з11е (а[3] > ч); Н (1 >= 3) Ькеа)сг х = а[з.]; а[з.] = а[3]; а[3] = х; /* Обмен а[з.], а[З] */ х = а[з.]; а[1] = а[п]; а[п] = х; /* Обмен а[1], а[п] */ /* Конец фрагмента */ с(ц1с)снох~(ш,3)г с(ц1с)снох~(1+1,п); Рис. 9.1. Код быстрой сортировки на языке программирования С Рис. 9.2.
Трехадресный код для фрагмента на рис. 9.1 (1) 1 = гв-1 (2) 3 = и (3) ~1 = 4*п (4) ч = а[~1] (5) 1 = 1+1 (б) С2 = 4*1 (7) 13 = а[~2] (8) 1т ~3<ч 9о1о (5) (9) 3 = 3-1 (10) ~4 = 4*3 (11) ~5 = а[~4] (12) 11' г5>ч до~о (9) (13) Н 1>=Э цо~о (23) (14) ~б = 4*з. (15) х = а[~б] (16) ~7 = 4*1 (17) ~8 = 4*3 (18) ~9 = а[~8] (19) а[~7] = 19 (20) ~10 = 4*3 (21) а[~10] = х (22) до~о (5) (23) ~11 = 4*з. (24) х = а[~11] (25) 112 = 4*1 (2б) 113 = 4*п (27) ~14 = а[~13] (28) а[~12] = ~14 (29) ~15 = 4*п (30) а[~15] = х 709 9.!. Основные источники оптимизации ния массива.
В результате короткий фрагмент исходной программы транслируется в существенно более длинную последовательность трехадресных операций. На рис. 9.3 показан граф потока для программы на рис. 9.2. Блок В1 представляет собой входной узел. Все условные и безусловные переходы к инструкциям на рис.
9.2 заменены на рис. 9.3 переходами к блокам, в которых эти инструкции являются лидерами, как в разделе 8.4. На рис. 9.3 имеется три цикла. Блоки Вз и Вз являются циклами сами по себе; еще один цикл с единственной точкой входа Вз образуют блоки Вз„Вз, В4 и Вз.
Рис. 9.3. Граф потока для фрагмента быстрой сортировки 710 Глава 9. Машинно-независимые оптимизации 9.1.3 Трансформации, сохраняющие семантику Существует ряд способов, которыми компилятор может улучшить программу без изменения вычисляемой функции. Устранение общих подвыражений, размножение копий, удаление недоступного кода и дублирование констант — вот основные примеры таких преобразований, сохраняющих функции (или сохраняющих семантику (вешал)гол-ргелегтгшй)). Мы рассмотрим все их по очереди. Зачастую программа включает несколько вычислений одного и того же значения, например смещения в массиве. Как упоминалось в разделе 9.1.2, некоторые из этих повторений не могут быть устранены программистом, поскольку они возникают на более низком уровне детализации, чем доступный в исходном языке.
Например, блок Вы показанный на рис. 9.4, а, дважды вычисляет значения 4 * г и 4 * у, хотя ни одно из этих вычислений в исходном тексте явно не указано. Вг Вг б) После а) До Рис. 9.4. Локальное устранение общих подвыражений 9.1.4 Глобальные общие подвыражения Выражение Е называется общим подвыражением (сопппоп ьцЬехргеьа)оп), если Е было ранее вычислено и значения переменных в Е с того времени не изменились. Повторного вычисления можно избежать, если использовать ранее вычисленное значение; т.е. если переменная х, которой присвоен результат предыдущего вычисления Е, не изменялась между вычислениями.~ Пример 9.1.
Присваивания ~7 и С10 на рис. 9.4, а вычисляют общие подвыражения 4 * т и 4 * у соответственно. Эти шаги устранены на рис. 9.4, б, где вместо ~7 используется сб, а вместо т.10 — с8. о Если х изменялась, все равно можно повторно использовать предыдущее вычисление Г, если сохранить полученное значение в новой переменной у наряду с сохранением в х и использовать значение у вместо повторного вычисления Е. 711 9.1. Основные источники оптимизации Пример 9.2. На рис.
9.5 показан результат устранения как локальных, так и глобальных общих подвыражений из блоков Вь и Вв в графе потока на рис. 9.3. Рассмотрим сначала преобразование Вы а затем упомянем о нескольких тонкостях использования массивов, в. Рис. 9.5. Вв и Ве после устранения общих подвыражений После устранения локальных общих подвыражений Вь все равно вычисляет 4*г и 4*1, как показано на рис. 9.4, б. Оба они являются общими подвыражениями; в частности, инструкции с8 = 4*1 т9 = а1с8] а[с8] = х в Вь могут быть заменены инструкциями 712 Глава 9. Машинно-независимые оптимизации с9 = а(с4] а(т41 = х с использованием значения 14, вычисленного в блоке Вз.
На рис. 9.5 видно, что при переходе управления от вычисления 4 * з в блоке Вз к блоку Вз значение з не изменяется, как не изменяется и 14, так что значение этой переменной можно использовать вместо 4 * у. Еще одно общее подвыражение появляется в Вз после того, как 14 заменяет 18. Новое выражение а [г4] соответствует значению а [з] на уровне исходного текста. При передаче управления из блока Вз в блок Ва свое значение сохраняет не только у, но н а [Я, значение, вычисленное в переменную 15, поскольку в промежутке нет никаких присваиваний элементам массива а.
Инструкции С9 = а(с4] а(сб] = с9 в Вы таким образом, могут быть заменены инструкцией а(сб] = с5 Аналогично значение, присвоенное х в блоке Вз на рис. 9.4, б, как видно, то же, что и значение, присвоенное 13 в блоке Вз. Блок Вз на рис. 9.5 представляет собой результат устранения общих подвыражений, соответствующих на уровне исходного текста значениям а [1] и а [7], из блока Вз на рнс. 9.4, б. Аналогичная серия преобразований выполнена и в блоке Ва на рис.
9.5. Выражения а [П] в блоках В1 и Ва на рис. 9.5 не являются общими подвыражениями, хотя в обоих случаях может использоваться 11. После того как управление покидает В1 и перед тем как оно достигает Ва, оно может пройти через блок Вы где имеются присваивания массиву о. Следовательно, а [11] может не иметь то же значение при достижении Вв, что и при покидании Вы так что рассматривать а, [1Ц как общее подвыражение небезопасно. и 9.1.5 Распространение копий Блок Вз на рис.
9.5 может быть улучшен удалением х путем применения двух новых преобразований. Одно из них связано с присваиванием вида ц = и, именуемого инструкцией копирования или для краткости — просто копированием. Если пристально рассмотреть пример 9.2, мы поймем, что копирования становятся более частыми хотя бы потому, что алгоритм устранения общих подвыражений, как и ряд других алгоритмов, вносит в код новые инструкции копирования. Пример 9.3. На рис. 9.6, а при удалении общего подвыражения в с = с(+е используется новая переменная 1 для хранения значения г(+ е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
