М.Ю. Харламов, ВНУ им. В.Даля, 2010

Оптимизация программы Оптимизация программы это обработка, связанная с переупорядочиванием и из­менением операций в компилируемой программе с целью получения более эф­фективной результирующей объектной программы Критерии объем памяти скорость выпол­нения Виды оптимизирующий преобразований преобразования исходной программы, не зависящие от результирующего объектного языка преобразования результирующей объектной программы Используемые методы оптимизации ни при каких условиях не должны приво­дить к изменению «смысла» исходной программы! Тема 9. Оптимизация кода 2

линейных участков программы; логических выражений; циклов; вызовов процедур и функций; других конструкций входного языка Тема 9. Оптимизация кода 3

Линейный участок программы выполняемая по порядку последователь­ность операций, имеющая один вход и один выход Чаще всего содержит последовательность вычислений, состоящих из арифметических операций и операторов присвоения значений переменным Используются следующие виды оптимизирующих преобразований: удаление бесполезных присваиваний; исключение избыточных вычислений (лишних операций); свертка операций объектного кода; перестановка операций; арифметические преобразования Тема 9. Оптимизация кода 4

Удаление бесполезных присваиваний когда переменной присваивается значение, которое нигде не используется Тема 9. Оптимизация кода 5 А := В * С; D := В * С; А := D * С; А := В * С; D := В * С; А := D * С; Р А := В * С; О := Р^ + С; А := D * С; Р А := В * С; О := Р^ + С; А := D * С; Не всегда очевидно бесполезная операция необходимо учитывать операции с адресами памяти, ссылками и вызовом функций !

Свертка объектного кода - выполнение во время компиляции тех операции исходной программы, для которых значения операндов уже известны Варианты свертки – выполнений операций, операндами которых являются … константы значения которые могут быть известны в результате выполнения предшествующих операций Тема 9. Оптимизация кода 6 I := 1 + 1; I := 3; J := 6*I + I; I := 1 + 1; I := 3; J := 6*I + I; 1. + (1, 1) 2. := (I, ^1) 3. := (I, 3) 4. * (6, I) 5. + (^4, 1) 6. := (J, ^5) 1. + (1, 1) 2. := (I, ^1) 3. := (I, 3) 4. * (6, I) 5. + (^4, 1) 6. := (J, ^5) 1. := (I, 2) 2. := (I, 3) 3. := (J, 21) 1. := (I, 2) 2. := (I, 3) 3. := (J, 21) Исходная программа Результат свертки Внутреннее представление

Исключение лишних операций заключается в нахо­ждении и удалении из объектного кода операций, которые повторно обрабатывают одни и те же операнды Операция линейного участка с порядковым номером i считается лишней, если существует идентичная ей операция с порядковым но­мером j, j<i, и никакой операнд, обрабатываемый этой операцией, не изменялся никакой операцией, имеющей порядковый номер между i и j Тема 9. Оптимизация кода 7 D := D + С*В; А := D + С*В; С := D + С*В; D := D + С*В; А := D + С*В; С := D + С*В; 1. * (С, В) 2. + (D, ^1) 3. := (D, ^2) 4. * (С, В) 5. + (D, ^4) 6. := (А, ^5) 7. * (С, В) 8. + (D, ^7) 9. := (С, ^8) 1. * (С, В) 2. + (D, ^1) 3. := (D, ^2) 4. * (С, В) 5. + (D, ^4) 6. := (А, ^5) 7. * (С, В) 8. + (D, ^7) 9. := (С, ^8) 1. * (С, В) 2. * (D, ^1) 3. := (D, ^2) 4. + (D, ^1) 5. := (А, ^4) 6. := (С, ^4) 1. * (С, В) 2. * (D, ^1) 3. := (D, ^2) 4. + (D, ^1) 5. := (А, ^4) 6. := (С, ^4) Исходная программа Результат свертки Внутреннее представление

Перестановка операций заключается в изменении порядка следования операций, которое может повысить эффективность программы, но не будет влиять на ко­нечный результат вычислений Арифметические преобразования представляют собой выполнение изменения характера и порядка следования операций на основании известных алгебраиче­ских и логических тождеств заме­на возведения в степень на умножение замена целочисленного умножения на константы кратные 2, на выполнение операций сдвига Тема 9. Оптимизация кода 8 А := 2*B*3* С; А := (2 * 3) * (В * С); А := (В + С) + (D + Е); А := В + (С + (D + Е)); А := В * С + В * D; А := В * (С + D);

Операция называется предопределенной для некоторого значения операнда, если ее результат зависит только от этого операнда и остается неизменным (ин­вариантным) относительно значений других операндов операция логического сложения (or) является предопределенной для логиче­ского значения «истина» (true) операция логического умножения (and) - пред­определена для логического значения «ложь» (false) Компиляторы строят объектный код вычисления логических выражений таким образом, что вычисление выражения прекращается сразу же, как только его зна­ чение становится предопределенным Тема 9. Оптимизация кода 9 A or F(В) or G(C) Если A = true, то F и G могут быть не вызваны

Обычно параметры в процедуры и функции передаются через стек Методы повышения эффективности: передача параметров через регистры процессора; подстановка кода функции в вызывающий объектный код ( в c++ inline) Тема 9. Оптимизация кода 10

Вынесение инвариантных вычислений из циклов Тема 9. Оптимизация кода 11 for i:=1 to 10 do A[i] := B * С * A[i]; for i:=1 to 10 do A[i] := B * С * A[i]; D := В * С; for i:=1 to 10 do A[i] := D * A[i]; D := В * С; for i:=1 to 10 do A[i] := D * A[i]; Замена операций с индуктивными переменными Значения индуктивной переменной в процессе выпол­нения цикла образуют арифметическую профессию S := 10; for i:=1 to N do A[i] := i*S; S := 10; for i:=1 to N do A[i] := i*S; S := 10; Т := S; i :=1; while i <= 10 do begin A[i] := T; T := T+ 10; i := i + 1; end; S := 10; Т := S; i :=1; while i <= 10 do begin A[i] := T; T := T+ 10; i := i + 1; end;

Слияние и развертывание циклов Слияние циклов Тема 9. Оптимизация кода 12 for i:=l to N do for j:=1 to M do A[i.j] := 0; for i:=l to N do for j:=1 to M do A[i.j] := 0; К := N*M: for i:=1 to К do A[i] := 0; К := N*M: for i:=1 to К do A[i] := 0; Развертывание циклов for i:=1 to 3 do A[i] := i; for i:=1 to 3 do A[i] := i; А[1] :=1; А[2] := 2; А[3] := 3;

Ориентированы на конкретную архи­тектуру целевой вычислительной системы, на которой будет выполняться ре­ зультирующая программа ! Существует большое количество методов оптимизации для тех или иных архитектур вычислительных систем распределение регистров процессора поро­ждение кода для параллельных вычислений … Тема 9. Оптимизация кода 13