Ціль "розподілу змінних по регістрах" полягає в спробі забезпечити оптимальне використання регістрів шляхом збереження часто використовуваних змінних в регістрах так довго, як це можливо, щоб виключити більш повільний доступ до пам’яті. Кількість регістрів, доступних для використання, залежить від архітектури процесора. Найбільш поширене сімейство процесорів Intel 80x86 резервує багато регістрів для спеціального використання і має декілька універсальних регістрів.
При призначенні змінних регістрам компілятор приймає до уваги не тільки змінні, які потрібно виділити, але також і регістри, яким вони призначаються. Вибір змінних залежить від частоти їх використання, проміжків існування поточних регістрових змінних (які визначаються при аналізі потоків даних) і кількості доступних регістрів. В залежності від ступеня виконуваної компілятором оптимізації проміжок життя змінної може визначатися всередині єдиного оператора, всередині базового блоку або перекривати декілька базових блоків. Змінна зберігається в регістрі тільки якщо вона буде знову використовуватися. Якщо надалі немає посилань на змінну, то вона зберігається в оперативній пам’яті, звільняючи регістр для іншої змінної.
Оскільки оптимізуючому компілятору відомий проміжок життя змінної, то він не буде навмисно генерувати зайві операції збереження і завантаження регістрів. Зайві операції збереження знищуються шляхом видалення зайвих присвоювань; зайві операції завантаження обходяться за допомогою вдосконаленого розподілу змінних по регістрам.
Компілятор, що генерує код для математичного сопроцесора, прискорює виконання програми, яка виконує багато операцій з плаваючою комою. Для того, щоб підтримувати сопроцесор і максимізувати ефективність плаваючої арифметики, оптимізуючий компілятор може генерувати безпосередньо послідовність команд сопроцесора, на противагу використанню програмної емуляції функцій плаваючої арифметики.
Розглянувши основні типи оптимізації, потрібно також зауважити, що її застосування не завжди дає потрібний ефект. Оптимізація не є панацеєю і її використання не безкоштовне. В залежності від ступеня оптимізації час, потрібний для компіляції, може значно зрости. Для невеликих програм потрібний час можна не приймати до уваги, але для великих він може бути важливим.
Оптимізація також може утруднити відлагодження програми внаслідок генерації коду, який важко безпосередньо пов’язати з вихідними операторами в програмі. Оптимізація може не очікувано внести помилки в код, згенерований з цілком правильного тексту програми. Ситуація, коли до змінної звертаються як безпосередньо за іменем, так і засобами одного чи декількох вказівників, може утруднити роботу компілятора по визначенню того, чи "живе" ще змінна і, відповідно, повинна залишатися в регістрі, чи вона "померла" і тоді має бути збереженою в пам’яті.
§5. Результати і висновки.
В даній роботі було розглянуто основні способи представлення арифметичних та логічних виразів - дерево виразу, інфіксна, префіксна та постфіксна форми запису; вказано на однозначність обчислення виразу в префіксній та постфіксній формах, і на необхідність використання дужок або пріоритету операцій в інфіксній формі. Розглянуто алгоритм POSTFIX обчислення виразу в постфіксній формі, доведено правильність його роботи, описано алгоритм переведення виразу в постфіксну форму (ІТР). В теоретичній частині сформульовано та доведено твердження 1 - 3, розглянуто основні типи аналізу виразів, звернуто увагу на корисність та важливість виконання лексичної згортки виразу перед його обчисленням, показано недоцільність використання префіксної форми запису виразів та дано оцінку складності алгоритмів POSTFIX, ІТР і абстрактного алгоритму обчислення виразу в інфіксній формі INFIX. Зокрема виявлено, що жоден алгоритм INFIX в загальному випадку не є кращим за алгоритм POSTFIX, на основі чого зроблено висновок про корисність використання постфіксної форми запису в компіляторах. Також наведено багато методів оптимізації вихідного коду компілятора.
В практичній частині було реалізовано алгоритми POSTFIX та ІТР в одній програмі, з метою їх сумісного використання. Також розроблено простий компілятор виразів, який генерує послідовність команд на асемблері процесорів сімейства Intel 80x86 для обчислення значення вхідного виразу. В додатках подано тексти програм і приклади їх роботи.
Використана література.
1. Дьяконов В.Ю. и др. Системное программирование, – М.: 1990. - с. 254–264.
2. Креншоу Дж. Давайте создадим компилятор. Мережа інтернет, http://www.kulichki.com/kit/crenshaw/crenshaw.html .
3. Aaby А. Compiler construction using Flex and Bison. Мережа інтернет, http://www.kulichki.com/kit .
Додаткова література.
1. Баррон Д. Рекурсивные методы в программировании, - М.: 1974
2. Дмитриева М.В., Кубенский А.А. Элементы современного программирования, - СПб.: 1991.
3. Барашенков В.В. Анализ и преобразование операторных схем алгоритмов: учебное пособие. - Л.: ЛЭТИ, 1979.
4. Кинг Д. Создание еффективного программного обеспечения. - М.: Мир, 1991.
5. Барашенков В.В. Интерпретация операторных схем алгоритмов. - Л.: ЛЭТИ, 1978.
6. Бентли Дж. Жемчужины творчества программистов. - М.: Мир, 1990.
7. Шауман А.М. Основы машинной арифметики. - 1979.
8. Ахо, Альфред В. и др. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979
9. Криницкий Н.А. Программирование и алгоритмические языки. - 1975.
10. Прикладные вопросы системного анализа. Межвузовский тематический сборник. Вып. 2. Куйбышев, 1976.
11. Автоматическое построение ассоциативного списка со сжатием информации. - К., 1976.
12. Квиттнер П. Задачи, программы, вычисления, результаты. - М.: Мир, 1980.
13. Шауман А.М. Основы машинной арифметики. - 1979.
14. Малоземов В.Н. Певный А.Б. Рекуррентные вычисления. - Л., изд. ун-та, 1976.
Додаток 1.
Програмна реалізація алгоритмів POSTFIX та ITP.
Для демонстрації роботи алгоритмів POSTFIX та ITP було складено програму, котра, отримавши на вході список змінних разом із значеннями та арифметичний вираз у інфіксній формі, спочатку переводить вираз у постфіксну форму (функція ITP), а потім обчислює його значення (функція CalculatePostfix).
Обмеження, що накладаються програмою на вхідні дані:
· всі змінні позначаються одним символом;
· у виразі немає числових констант;
· вираз не містить посилання на арифметичні функції;
· вираз є правильно записаним (відсутні перевірки на правильність).
Для обчислення виразу в постфіксній формі функція CalculatePostfix використовує стек, реалізований в наступному модулі:
Unit Stack;
Interface
Var S:Array[1..100] Of Real;
Top:Integer;
Procedure Push(Number:Real);
Procedure Pop(Var Number:Real);
Function IsEmpty:Boolean;
Procedure ClearStack;
Implementation
Procedure ClearStack;
Begin
Top:=0;
End;
Procedure Push(Number:Real);
Begin
Inc(Top);
S[Top]:=Number;
End;
Procedure Pop(Var Number:Real);
Begin
Number:=S[Top];
Dec(Top);
End;
Function IsEmpty:Boolean;
Begin
If Top=0 Then IsEmpty:=True Else IsEmpty:=False;
End;
Begin
Top:=0;
End.
Текст програми:
Uses Crt, Stack;
Type Id=Record
c:Char;
v:Real;
End;
Var Ex,S:String;
Stek:Array[1..255] Of Char;
N:Integer;
Tab:Array[1..26] Of Id;
Function InputExpression:String;
Var s:String;
i:Integer;
Begin
WriteLn('Скільки змінних буде у виразі ?');
ReadLn(N);
For i:=1 To N Do
Begin
WriteLn('Введіть один символ для позначення змінної номер ',i);
ReadLn(Tab[i].c);
WriteLn('Введіть значення ',Tab[i].c);
ReadLn(Tab[i].v);
End;
WriteLn('Введіь арифметичний вираз у інфіксній формі ');
ReadLn(s);
InputExpression:=s;
End;
Function IsOperation(c:Char):Boolean;
Begin
If c in ['/','*','+','-','^'] Then IsOperation:=True
Else IsOperation:=False;
End;
Function IsVariable(c:Char):Integer;
Var i:Integer;
Begin
For i:=1 To N Do
If Tab[i].c=c Then
Begin
IsVariable:=i;
Exit;
End;
IsVariable:=0;
End;
Function MakeOperation(p1,p2:Real; Op:Char):Real;
Begin
Case Op Of
'+' : MakeOperation:=p1+p2;
'-' : MakeOperation:=p1-p2;
'*' : MakeOperation:=p1*p2;
'/' : MakeOperation:=p1/p2;
'^' : MakeOperation:=Exp(Ln(p1)*p2);
End;
End;
Function CalculatePostfix(Ex:String):Real;
Var i,j:Integer;
p1,p2:Real;
b:Boolean;
Begin
For i:=1 To Length(Ex) Do
Begin
b:=IsOperation(Ex[i]);
j:=IsVariable(Ex[i]);
If b Then
Begin
Pop(p1);
Pop(p2);
Push(MakeOperation(p2,p1,Ex[i]));
End
Else
Begin
Push(Tab[IsVariable(Ex[i])].v);
End;
End;
Pop(p1);
CalculatePostfix:=p1;
End;
Function Priority(c:Char):Byte;
Begin
Case c Of
'e' : Priority:=0;
'(' : Priority:=0;
')' : Priority:=0;
'-' : Priority:=1;
'+' : Priority:=1;
'*' : Priority:=2;
'/' : Priority:=2;
'^' : Priority:=3;
End;
End;
Function ITP(Ex:String):String;
Var i,j:Integer;
Rez:String;
Begin
Rez:='';
Stek[1]:='e'; j:=1;
For i:=1 To Length(Ex) Do
Begin
If Ex[i] in ['A'..'Z','a'..'z'] Then Rez:=Rez+Ex[i];
If Ex[i]='(' Then Begin j:=j+1; Stek[j]:='('; End;
If Ex[i]=')' Then
Begin
While Stek[j]<>'(' Do Begin Rez:=Rez+Stek[j]; Dec(j); End;
Dec(j);
End;
If Ex[i] in ['+','-','*','/','^'] Then
Begin
While Priority(Ex[i])<=Priority(Stek[j]) Do
Begin Rez:=Rez+Stek[j]; Dec(j); End;
Inc(j); Stek[j]:=Ex[i];
End;
End;
While Stek[j]<>'e' Do
Begin Rez:=Rez+Stek[j]; Dec(j); End;
ITP:=Rez;
End;
Begin
ClrScr;
Ex:=InputExpression;
S:=ITP(Ex);
WriteLn('Вираз у постфіксній формі: ',S);
WriteLn('Результат ',CalculatePostfix(S):12:6);
WriteLn('Натисніть довільну клавішу');
ReadLn;
End.
Приклади роботи програми.
Приклад 1.
Скiльки змiнних буде у виразi ?
4
Введiть один символ для позначення змiнної номер 1
a
Введiть значення a
1
Введiть один символ для позначення змiнної номер 2
b
Введiть значення b
2
Введiть один символ для позначення змiнної номер 3
c
Введiть значення c
3
Введiть один символ для позначення змiнної номер 4
d
Введiть значення d
4
Введiть арифметичний вираз у iнфiкснiй формi
b^(c*(d+a))
Вираз у постфiкснiй формi: bcda+*^
Результат 32768.000000
Натиснiть довiльну клавiшу
Приклад 2.