Лекция 15 Оптимизация кода результирующей объектной программы. - презентация

1 Лекция 15 Оптимизация кода результирующей объектной программы

2 Оптимизация кода Оптимизация линейных участков программ Пример 1 A:=B*C; D:=B+C; A:=D*C; Удаление бесполезных присваиваний: Пример 2 A:=B*C; D:=P^*C; A:=D*C; Свертка объектного кода: Пример 3 До: A:=2*B*С*3; после свертки: А:=6*B*С Правильно: B:=sin(2*PI*A); Не рекомендуется: B:=sin(2*A*PI).

3 Перестановка операций: До: A:= 2*B*3*C После перестановки: A:= (2*3)*(B*C) Арифметические преобразования: До: A:= B*C+B*D После преобразования: A:= B*(C+D)

4 Cвертка объектного кода (, ) Специальная триада С(K, 0) Алгоритм свертки объектного кода 1) Операнд – таблицы, то замена операнда на. 2) Операнд – ссылка на С(K, 0), то замена операнда на K. 3) Все операнды – константы, то замена на С(K, 0). 4) Триада A:=B, то: а) В – константа, то в таблицу - (А, ); б) В – не константа, то удалить из таблицы А.

5 Пример 4 Фрагмент исходной программы: I:=1+1; I:=3; J:=6*I+I: Работа алгоритма свертки: Триада Шаг 1Шаг 2Шаг 3Шаг 4Шаг 5Шаг 6 C(2, 0) :=(I, ^1) :=(I, 3) *(6, I) +(^4, I) :=(J, ^5) (, ) 1. +(1, 1) 2. :=(I, ^1) 3. :=(I, 3) 4. *(6, I) 5. +(^4, I) 6. :=(J, ^5) T C(2, 0) :=(I, 2) :=(I, 3) *(6, I) +(^4, I) :=(J, ^5) (I, 2) C(2, 0) :=(I, 2) :=(I, 3) *(6, I) +(^4, I) :=(J, ^5) (I, 3) C(2, 0) :=(I, 2) :=(I, 3) C(18, 0) +(^4, I) :=(J, ^5) (I, 3) C(2, 0) :=(I, 2) :=(I, 3) C(18, 0) C(21, 0) :=(J, ^5) (I, 3) C(2, 0) :=(I, 2) :=(I, 3) C(18, 0) C(21, 0) :=(J, 21) (I, 3) (J, 21) Результат: 1. :=(I, 2); 2. :=(I, 3); 3. :=(J, 21).

6 Исключение лишних операций Числа зависимости: 1) dep(A) = 0; 2) после i-ой триады A:=E dep(A) = i; 3) dep(i) = max(dep op )+1. Специальная триада SAME(i, 0) Алгоритм исключение лишних операций 1) операнд – ссылка SAME(i, 0), то замена на ^i. 2) dep(j) = max(dep op )+1. 3) идентичная i-я триада (i

7 Пример 5 Фрагмент исходной программы: D:=D+C*B; A:=D+C*B; C:=D+C*B; Исходные триады Числа зависимости переменных ABCD Числа зависимости триад Результи- рующие триады 1) *(С, B) 2) +(D, ^1) 3) :=(D, ^2) 4) *(C, B) 5) +(D, ^4) 6) :=(A, ^5) 7) *(С, B) 8) +(D, ^7) 9) :=(C, ^8) ) *(С, B) 2) +(D, ^1) 3) :=(D, ^2) 4)SAME(1, 0) 5) +(D, ^1) 6) :=(A, ^5) 7)SAME(1, 0) 8)SAME(5, 0) 9) :=(C, ^5)

8 1) *(С, B) 2) +(D, ^1) 3) :=(D, ^2) 4) SAME(1, 0) 5) +(D, ^1) 6) :=(A, ^5) 7) SAME(1, 0) 8) SAME(5, 0) 9) :=(C, ^5) Ответ: 1) *(С, B) 2) +(D, ^1) 3) :=(D, ^2) 4) +(D, ^1) 5) :=(A, ^4) 6) :=(C, ^4) Результирующие триады: Оптимизированный код:

9 Оптимизация вычисления логических выражений A or B or C or D A or F(B) or G(C) Оптимизация циклов Вынесение инвариантных вычислений из циклов ДО: For i:=1 to 10 do Begin A[i]:=B*C*A[i]; … End; ПОСЛЕ: D:=B*C; For i:=1 to 10 do Begin A[i]:=D*A[i]; … End;

10 Замена операций с индуктивными переменными ДО: S:=10; for i:=1 to n do a[i]:=i*S ПОСЛЕ: S:=10; T:=S; i:=1; while i<=1 10 do begin a[i]:=T; T:=T+10; i:=i+1; end; ДО: S:=10; for i:=1 to n do begin R:=R+F(S); S:=S+10; end; ПОСЛЕ: S:=10; M:=10+n*10; while S<=M do begin R:=R+F(S); S:=S+10; end;

11 Слияние циклов ДО: for i:=1 to N do for j:=1 to M do A[i,j]:=0; ПОСЛЕ: К:=N*M; for i:=1 to K do A[i]:=0; ДО: for i:=1 to 3 do A[i]:=i; ПОСЛЕ: A[1]:=1; A[2]:=2; A[3]:=3;