Оптимальні програми обчислення виразів, Детальна інформація

b = 0;

a = b;

перший оператор є зайвим присвоюванням і може бути безпечно видалений. Зайві присвоювання можуть виникати ненавмисно, коли проміжок існування змінної великий і між входженнями змінної є доволі багато коду. Зайві присвоювання можуть бути також результатом попередніх проходів оптимізації.

Ціль "розподілу змінних по регістрах" полягає в спробі забезпечити оптимальне використання регістрів шляхом збереження часто використовуваних змінних в регістрах так довго, як це можливо, щоб виключити більш повільний доступ до пам’яті. Кількість регістрів, доступних для використання, залежить від архітектури процесора. Найбільш поширене сімейство процесорів Intel 80x86 резервує багато регістрів для спеціального використання і має декілька універсальних регістрів.

При призначенні змінних регістрам компілятор приймає до уваги не тільки змінні, які потрібно виділити, але також і регістри, яким вони призначаються. Вибір змінних залежить від частоти їх використання, проміжків існування поточних регістрових змінних (які визначаються при аналізі потоків даних) і кількості доступних регістрів. В залежності від ступеня виконуваної компілятором оптимізації проміжок життя змінної може визначатися всередині єдиного оператора, всередині базового блоку або перекривати декілька базових блоків. Змінна зберігається в регістрі тільки якщо вона буде знову використовуватися. Якщо надалі немає посилань на змінну, то вона зберігається в оперативній пам’яті, звільняючи регістр для іншої змінної.

Оскільки оптимізуючому компілятору відомий проміжок життя змінної, то він не буде навмисно генерувати зайві операції збереження і завантаження регістрів. Зайві операції збереження знищуються шляхом видалення зайвих присвоювань; зайві операції завантаження обходяться за допомогою вдосконаленого розподілу змінних по регістрам.

Компілятор, що генерує код для математичного сопроцесора, прискорює виконання програми, яка виконує багато операцій з плаваючою комою. Для того, щоб підтримувати сопроцесор і максимізувати ефективність плаваючої арифметики, оптимізуючий компілятор може генерувати безпосередньо послідовність команд сопроцесора, на противагу використанню програмної емуляції функцій плаваючої арифметики.

Розглянувши основні типи оптимізації, потрібно також зауважити, що її застосування не завжди дає потрібний ефект. Оптимізація не є панацеєю і її використання не безкоштовне. В залежності від ступеня оптимізації час, потрібний для компіляції, може значно зрости. Для невеликих програм потрібний час можна не приймати до уваги, але для великих він може бути важливим.

Оптимізація також може утруднити відлагодження програми внаслідок генерації коду, який важко безпосередньо пов’язати з вихідними операторами в програмі. Оптимізація може не очікувано внести помилки в код, згенерований з цілком правильного тексту програми. Ситуація, коли до змінної звертаються як безпосередньо за іменем, так і засобами одного чи декількох вказівників, може утруднити роботу компілятора по визначенню того, чи "живе" ще змінна і, відповідно, повинна залишатися в регістрі, чи вона "померла" і тоді має бути збереженою в пам’яті.

§5. Результати і висновки.



В даній роботі було розглянуто основні способи представлення арифметичних та логічних виразів - дерево виразу, інфіксна, префіксна та постфіксна форми запису; вказано на однозначність обчислення виразу в префіксній та постфіксній формах, і на необхідність використання дужок або пріоритету операцій в інфіксній формі. Розглянуто алгоритм POSTFIX обчислення виразу в постфіксній формі, доведено правильність його роботи, описано алгоритм переведення виразу в постфіксну форму (ІТР). В теоретичній частині сформульовано та доведено твердження 1 - 3, розглянуто основні типи аналізу виразів, звернуто увагу на корисність та важливість виконання лексичної згортки виразу перед його обчисленням, показано недоцільність використання префіксної форми запису виразів та дано оцінку складності алгоритмів POSTFIX, ІТР і абстрактного алгоритму обчислення виразу в інфіксній формі INFIX. Зокрема виявлено, що жоден алгоритм INFIX в загальному випадку не є кращим за алгоритм POSTFIX, на основі чого зроблено висновок про корисність використання постфіксної форми запису в компіляторах. Також наведено багато методів оптимізації вихідного коду компілятора.

В практичній частині було реалізовано алгоритми POSTFIX та ІТР в одній програмі, з метою їх сумісного використання. Також розроблено простий компілятор виразів, який генерує послідовність команд на асемблері процесорів сімейства Intel 80x86 для обчислення значення вхідного виразу. В додатках подано тексти програм і приклади їх роботи.

Використана література.

Дьяконов В.Ю. и др. Системное программирование, – М.: 1990. - с. 254–264.

Креншоу Дж. Давайте создадим компилятор. Мережа інтернет, HYPERLINK "http://www.kulichki.com/kit/crenshaw/crenshaw.html" http://www.kulichki.com/kit/crenshaw/crenshaw.html .

Aaby А. Compiler construction using Flex and Bison. Мережа інтернет, HYPERLINK "http://www.kulichki.com/kit" http://www.kulichki.com/kit .

Додаткова література.

Баррон Д. Рекурсивные методы в программировании, - М.: 1974

Дмитриева М.В., Кубенский А.А. Элементы современного программирования, - СПб.: 1991.

Барашенков В.В. Анализ и преобразование операторных схем алгоритмов: учебное пособие. - Л.: ЛЭТИ, 1979.

Кинг Д. Создание еффективного программного обеспечения. - М.: Мир, 1991.

Барашенков В.В. Интерпретация операторных схем алгоритмов. - Л.: ЛЭТИ, 1978.

Бентли Дж. Жемчужины творчества программистов. - М.: Мир, 1990.

Шауман А.М. Основы машинной арифметики. - 1979.

Ахо, Альфред В. и др. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979

Криницкий Н.А. Программирование и алгоритмические языки. - 1975.

Прикладные вопросы системного анализа. Межвузовский тематический сборник. Вып. 2. Куйбышев, 1976.

Автоматическое построение ассоциативного списка со сжатием информации. - К., 1976.

Квиттнер П. Задачи, программы, вычисления, результаты. - М.: Мир, 1980.