Как правило структура промежуточного кода представляет из себя
результат линеаризации синтаксического дерева , содержащего последовательность операторов , каждый из которых является
эквивалентным одной машинной команде либо последовательности
небольшого числа машинных команд. В качестве языковых средств
для описания промежуточного кода выбирают средства , являющиеся
адекватными средствам языков , в которые в конечном итоге
транслируется исходный текст программы (например в язык машинных
кодов или ассемблер ) .
Существуют разные способы представления промежуточных кодов .
Здесь ограничимся рассмотрением так называемого трехадресного
кода , являющегося одним из наиболее распространенных средств
промежуточного кода .Трехадресный код представляется в виде строки
a=b op c , где op -оператор , b , c - адреса операндов ,a - адрес
результата применения оператора к операндам . Например ,
арифметическое выражение a+b*c-d можно представить в виде последовательности следующих операторов :
t1= b*c
t1= t1-d
t2= a+t1 ,
где t1,t2 -временные переменные , создаваемые компилятором .
Допускается также использование унарных операторов , например
T1= - R . Каждый оператор трехадресного содержит максимум три
адреса . Посредством трехадресного кода можно представлять широкий
спектр типичных аспектов языков программирования : присваивание ,
условные и безусловные переходы и т.п. Например :
a=t1
t1=b[i]
if t1 goto L1
goto L2
На основе полученного промежуточного кода и специальных таблиц,
устанавливающих соответствие между помежуточным и машинным
кодами , компилятор генерирует целевой код .
3.6.3.Оптимизация кода.
Оптимизация кода позволяет получить эффективный код , в котором обеспечивается оптимальное сочетание двух важных свойств объектного кода : максимально возможная скорость выполнения и минимально возможный объем используемой памяти . Различают два вида оптимизации :
- локальная , основывающаяся на относительно простом анализе и
преобразованиях кода ;
- глобальная , основывающаяся на более сложном анализе и
преобразованиях кода ;
Примерами локальной оптимизации являются следующие :
- минимизация операций ;
- снижение стоимости ;
- исключение ненужных операторов .
Минимизация операций предусматривает выполнение в процессе
компиляции арифметических операций , которые должны были бы
выполняться при выполнении программы. Например последовательность
limit := 100
index := limit - 1
можно заменить последовательностью
limit := 100
index := 99 .
Примером снижения стоимости является замена произведения или
деления соответствующими операторами сдвига.
Примером исключения ненужных операторов является удаление
оператора LOAD , если регистр уже содержит необходимое значение .
Глобальная оптимизация , основываясь на анализе потоков
управления и информационных связей , обеспечивает более сложные
типы оптимизации :
- удаление бесполезного кода ;
- исключение общих подвыражений ;
- оптимизация циклов.
Удаление бесполезного кода предусматривет удаление конструкций
программы , которые не будут выполняться при любом выполнении
программы . Например в конструкции b:=true ;IF b then P else Q
оператор Q никогда не будет выполняться . Поэтому данную конструкцию
можно заменить эквивалентной конструкцией b:=true ; Q .
Исключение общих подвыражений заключается в исключении лишних вычислений для повторяющихся подвыражений . Например , последовательность операторов
x:= a+b
y:= a+b
можно заменить последовательностью
x:= a+b
y:= x .
Оптимизация циклов . Наиболее типичными действиями по
оптимизации циклов являются вывод из тела цикла "ненужных "
операторов и замена цикла фрагментом последовательного кода .
Примеры .
1) Конструкцию
for i:=1 to 100 do begin x:=y ; write(A[i]) end
можно заменить эквивалентной конструкцией
x:=y ; for i:=1 to 100 do write(A[i])
(вывод из тела цикла "ненужных "операторов) .
2) Конструкцию
while i<N do i:=i+1
можно заменить эквивалентной конструкцией
if i<N then i:=N
(замена цикла фрагментом последовательного кода)
Одним из универсальных подходов к решению проблем оптимизации
программ представляется применение так называемого
трансформационного программирования , в частности механизма
смешанных вычислений , к оптимизации программ . Эти результаты
в свое время были получены идеологом нашего отечественного программирования академиком А.П .Ершовым [8] . Суть упомянутого
подхода сводится к эквивалентным преобразованиям кода программы
на основе применения соответствующих соотношений , например типа
if b then P else P º P , (while false do P );Q º Q и т.п. ( см . р. 2.4.) .
Л И Т Е Р АТ У Р А
1.Хендерсон П. , Функциональное программирование . Применение и реализация . Москва «МИР». ,1983.-349 с.
2.Волож Б.Б. , Мацкин М.Б. , Минц Г.Е. . Система ПРИЗ и исчисление высказываний.- ж. Кибернетика , 1982 , № 6 , с.63-70 .
3.Элиенс А. Принципы объектно-ориентированной разработки программ. 2-ое изд. Изд. дом «Вильямс».Москва – С.- Петербург -Киев, 2002.-495 с.
4. ???????????????????????????????????????????????????????????.
5. Communicating Sequential Processes (CSP) , by C. A. R. Hoare (Electronic Version)
Communicating Sequential Processes (CSP) Communicating Sequential Processes, or CSP, is a language for describing patterns of interaction. It is supported by an elegant, mathematical theory, a set of proof tools, and an extensive literature. ... a message to csp-announce@comlab.ox.ac.uk. The author, Tony Hoare, was Professor of ...
http://www.usingcsp.com/
6.Робин Хантер , Основные концепции компиляторов , Изд. дом “Вильямс” , Москва – С.- Петербург -Киев ,2002.- 252 с.
7. Пинтер Лес , Пинтер Джон , Visual FoxPro : Уроки программирования ,
Mc Graw-Hill (пер. с англ .), 1996 г . - 452 с.
8.Ершов А.П. , Смешанные вычисления : потенциальные применения и проблемы исследования . // Сов.-франц. Симп.
" Теория и практика программного обеспечения ЭВМ " / Новосибирск ,
1981 , -ч.1,
9. Geraint Jones , Programming in Occam ( Prentice-Hall International Series in Computer Science) , Publisher: Prentice Hall (April 1, 1987)
ISBN: 0137297734 , Paperback: 182 pages .
Brookes, S. D., Hoare, C. A. R., and Roscoe, A. W. ‘A Theory of
Communicating Sequential Processes,’ Journal ACM 31 (7), 560–599
(1984)