3. Машинно-независимая оптимизация компилируемого кода (1157510)
Текст из файла
3. Машинно-независимая оптимизация.
Цель машинно-независимой оптимизации – исключить из компилируемой программы избыточные вычисления, мертвый и недостижимый код, оптимизировать поток управления, исключив избыточные передачи управления, оптимизировать циклы и гнезда циклов, оптимизировать вызовы функций (процедур) и возвраты из них.
3.1. Построение графа потока управления.
Машинно-независимая оптимизация выполняется над графом потока управления (ГПУ) процедуры. Посмотрим на простом примере, как строится ГПУ. В качестве такого примера можно взять фрагмент процедуры (функции) quicksort(a, m, j). Этот фрагмент в исходном представлении на языке C показан на рисунке 1, а в промежуточном представлении – на рисунке 2.
| { int i, j; int v, x; if (n <= m) return; /* Начало фрагмента */ i = m - 1; j = n; v = a[n]; while (1) { do i = i + 1; while (a[i] < v); do j = j - 1; while (a[j] > v); | if (i >= j) break; /* Обмен a[i], a[j] */ x = a[i]; a[i] = a[j]; a[j] = x; } /* Обмен a[i], a[n] */ x = a[i]; a[i] = a[n]; a[n] = x; /* Конец фрагмента */ quicksort(a,m,j); quicksort(a,i+1,n); } |
| Рисунок 1. Исходное представление фрагмента процедуры quicksort на языке C. | |
Большая часть инструкций выполняется в «естественном» порядке, т.е. в порядке их написания. Для нарушения естественного порядка используются инструкции перехода, условного (инструкции (8), (12) и (13) на рисунке 2) или безусловного (инструкция (22) на рисунке 2), и помеченные инструкции (инструкции (5), (9) и (23) на рисунке 2), определяющие места, на которые передается управление. Участки процедуры, не содержащие помеченных инструкций и/или инструкций перехода, называются базовыми блоками (или линейными участками).
Определение 1. Базовый блок представляет собой последовательность инструкций, обладающую следующими свойствами:
-
поток управления может входить в базовый блок только через его первую инструкцию, т.е. нет переходов в средину базового блока (единственный вход);
-
управление покидает блок без останова или ветвления, за исключением, возможно, в последней инструкции блока (единственный выход).
Из определения 1 следует, что первой инструкцией, или началом базового блока (НББ) может быть либо первая инструкция процедуры, либо помеченная инструкция, либо инструкция, следующая за инструкцией перехода.
| (1) | i = m-1 НББ | (16) | t7 = 4*i |
| (2) | j = n | (17) | t8 = 4*j |
| (3) | tl = 4*n | (18) | t9 = a[t8] |
| (4) | v = a[tl] | (19) | a[t7] = t9 |
| (5) | L1: i = i+1 НББ | (20) | t10 = 4*j |
| (6) | t2 - 4*i | (21) | a[t10] = x |
| (7) | t3 = a[t2] | (22) | goto L1 |
| (8) | if t3<v goto L1 | (23) | L3: t11 = 4*i НББ |
| (9) | L2: j = j-1 НББ | (24) | x = a[t11] |
| (10) | t4 = 4*j | (25) | t12 = 4*i |
| (11) | t5 - a[t4] | (26) | t13 = 4*n |
| (12) | if t5>v goto L2 | (27) | t14 = a[t13] |
| (13) | if i>=j goto L3 НББ | (28) | a[t12] = tl4 |
| (14) | t6 = 4*i НББ | (29) | t15 = 4*n |
| (15) | x = a[t6] | (30) | a[t15] = x |
| Рисунок 2. Промежуточное представление фрагмента процедуры quicksort. (НББ – начало базового блока; номера инструкций добавлены для ссылок). | |||
| Блок A | Блок E | Блок F | ||||||
| (1) | i = m-1 | (14) | t6 = 4*i | (23) | L3:t11 = 4*i | |||
| (2) | j = n | (15) | x = a[t6] | (24) | x = a[t11] | |||
| (3) | tl = 4*n | (16) | t7 = 4*i | (25) | t12 = 4*i | |||
| (4) | v = a[tl] | (17) | t8 = 4*j | (26) | t13 = 4*n | |||
| Блок B | (18) | t9 = a[t8] | (27) | t14 = a[t13] | ||||
| (5) | L1:i = i+1 | (19) | a[t7] = t9 | (28) | a[t12] = tl4 | |||
| (6) | t2 - 4*i | (20) | t10 = 4*j | (29) | t15 = 4*n | |||
| (7) | t3 = a[t2] | (21) | a[t10] = x | (30) | a[t15] = x | |||
| (8) | if t3<v goto L1 | (22) | goto L1 | |||||
| Блок D | Блок C | |||||||
| (13) | if i>=j goto L3 | (9) | L2:j = j-1 | |||||
| Рисунок 3. Базовые блоки рассмат-риваемого фрагмента процедуры quicksort. | (10) | t4 = 4*j | ||||||
| (11) | t5 - a[t4] | |||||||
| (12) | if t5>v goto L2 | |||||||
Чтобы выделить базовый блок, достаточно к первой инструкции (такие инструкции помечены на рисунке 2 словом НББ) этого блока приписать все инструкции, расположенные между ней и первой инструкцией следующего базового блока (следующим НББ). На рисунке 2 отмечено 6 инструкций, являющихся началами базовых блоков (НББ). Это инструкции (1), (5), (9), (13), (14) и (23). Следовательно, рассматриваемый фрагмент процедуры состоит из 6 базовых блоков A, B, C, D, E, F (см. рисунок 3). Выделив базовые блоки, можно построить граф потока управления (ГПУ).
| | Вершинами графа потока управления процедуры являются базовые блоки, а направленные дуги соединяют каждый базовый блок с базовыми блоками, которые могут выполняться после этого блока. ГПУ рассматриваемого примера представлен на рисунке 4. Отметим, что для удобства в ГПУ добавляются две дополнительные вершины (не содержащие инструкций): entry (единственный вход в процедуру) и exit (выход из процедуры). Для задания ГПУ нужно задать множество N его вершин и множество E N N его направленных дуг. |
| Рисунок 4. ГПУ рассматриваемого фрагмента процедуры quicksort. |
3.2. Локальная оптимизация.
Различают следующие виды оптимизации
-
Локальная оптимизация – оптимизация в пределах одного базового блока (при этом каждый базовый блок рассматривается независимо от остальных).
-
Оптимизация области – оптимизация в пределах части процедуры.
-
Глобальная оптимизация – оптимизация в пределах процедуры.
-
Межпроцедурная оптимизация – оптимизация нескольких процедур, например, составляющих модуль компиляции или библиотеку.
-
Межмодульная оптимизация – оптимизация всей программы (включая используемые ею библиотеки).
Рассмотрим сначала локальную оптимизацию.
3.2.1. Задачи локальной оптимизации.
Локальная оптимизация – это оптимизация в пределах базового блока. Она состоит в выполнении следующих преобразований кода:
-
Сворачивание констант.
-
Удаление избыточных подвыражений.
-
Удаление мертвого кода.
-
Изменение порядка инструкций, там, где это возможно, чтобы сократить время хранения временных значений на регистрах.
Сворачивание констант состоит в замене выражений, операндами которых являются константы с известными значениями, на константы, полученные в результате выполнения соответствующих операций. Например, следующие 3 инструкции:
a = 8
b = aa
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
