русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Оптимизация промежуточного кода программы

Компиляция - трансляция программы (кода) или отдельного программного модуля, составленных на языке программирования высокого уровня (исходная программа, исходный модуль) в программу или модуль на машинном языке или языке, близком к машинному.

Стадии работы компилятора:

  • Входной текст
  • Лексический анализ
  • Синтаксический анализ
  • Семантический анализ
  • Генерация промежуточного кода
  • Оптимизация промежуточного кода
  • Генерация машинного кода.

Оптимизация промежуточного кода – это удаление избыточных команд и упрощение (где это возможно) кода с сохранением его смысла, то есть реализуемого им алгоритма (в том числе пред вычисляются (то есть вычисляются на фазе трансляции) выражения, результаты которых практически являются константами). Оптимизация может быть на разных уровнях и этапах — например, над промежуточным кодом или над конечным машинным кодом.

 

Оптимизация кода методом свертки

Триады представляют собой запись операций в форме из трех составляющих: <операция>(<операнд1>,<операнд2>), при этом один или оба операнда могут быть ссылками на другую триаду в том случае, если в качестве операнда данной триады выступает результат выполнения другой триады. Поэтому триады при записи последовательно номеруют для удобства указания ссылок одних триад на другие. Например, выражение A := B*C + D - B*10, записанное в виде триад будет иметь вид:

1)    *  (   B, C  )
2)    +  (  ^1, D  )
3)    *  (   B, 10  )
4)    -   (  ^2, ^3  )
5)    := (   A, ^4  )

Здесь операции обозначены соответствующим знаком (при этом присвоение также является операцией), а знак ^ означает ссылку операнда одной триады на результат другой.

Программа может программный код преобразовать в триады, посредством алгоритма преобразования. И оптимизировать при помощи метода свертки.

Свертка объектного кода - это выполнение во время компиляции тех операций исходной программы для которых значения операндов уже известны. Поэтому нет необходимости многократно выполнять их в самой результирующей программе - вполне достаточно один раз выполнить их при ее компиляции.

Простейший вариант свертки - выполнение в компиляторе операций, операндами которых являются константы. Несколько более сложен процесс определения тех операций, значения которых могут быть известны в результате выполнения других операций. Для этого служит специальный алгоритм свертки.

Алгоритм свертки работает со специальной таблицей T, которая содержит пары <переменная>-<константа> для всех переменных, значения которых уже известны. Кроме того, алгоритм свертки помечает те операции во внутреннем представлении программы, для которых в результате свертки уже не требуется генерация кода. Так как при выполнении алгоритма свертки учитывается взаимосвязь операций, то удобной формой представления для него являются триады, так как в других формах представления операций (таких как тетрады или команды ассемблера) требуются дополнительные структуры, чтобы отразить связь результатов одних операций с операндами других.

Алгоритм свертки триад последовательно просматривает триады линейного списка и для каждой триады делает следующее:

  • Если операнд есть переменная, которая содержится в таблице T, то операнд заменяется на соответствующее значение константы.
  • Если операнд есть ссылка на особую триаду типа C(K,0), то операнд заменяется на значение константы K.
  • Если все операнды триады являются константами, то триада может быть свернута. Тогда данная триада выполняется и вместо нее помещается особая триада вида C(K,0), где K - константа, результат выполнения свернутой триады. (При генерации кода для особой триады объектный код не порождается, а потому она в дальнейшем может быть просто исключена).
  • Если триада является присваиванием типа A:=B, тогда:
  • если B - константа, то A со значением константы заносится в таблицу T (если там уже было старое значение для A, то это старое значение исключается).
  • если B - не константа, то A вообще исключается из таблицы T, если оно там есть.

 

 

2 Разработка алгоритма оптимизации кода методом свертки

 

Программа должна иметь переменную, в которой будет записан код программы, который нужно будет разбить на триады и оптимизировать. После этого нужно будет с этой переменной получить строковые выражения типа: x = 1 + x.

После этого полученные выражения разбиваются на операнды и знаки в массив. По нашему примеру – это будет так: (x,=,1,+,x). Программа будет записывать массив в обратном порядке для того, чтобы проще было разбивать на триады.

После того как мы получили массив операндов и знаковых символов, мы будем вызывать метод обработки ( Obrabotka('/');). Данный метод принимает знаковый символ, в котором мы будем получать триаду. Цикл в этом методе будет длиться пока формирование триады не закончилось. Готовая триада будет записываться в переменную TriadaMas, где элемент 0 – хранит знаки триады, 1, 2 – операнды. Массив Triada хранит триаду целиков без разбиения на операнды и знаки, она нужна для быстрого вывода в таблицу.

Метод Raspoznat_Click будет заниматься принятием строки, разбиения ее на выражения и построения триад.

Метод Optimazation_Click будет реализовывать метод свертки. Для оптимизации триад методом свертки мы будем использовать 7 возможных ситуаций и для них будет 7 блоков.

  • Если 2 операнда - это числа
  • Если в конце есть указатель на числовое выражение
  • Если 1-й операнд - это буква, второй – цифра и между ними есть знак равно
  • Если первый операнд - это цифра, а второй - это буква
  • Если первый операнд - это указатель (^)
  • первый операнд - это буква,второй слово и замена еще не производилась. Для этого объявим переменную identOpt и приравняем ее нулю. Если в какой-то блок уже выполнялся, то identOpt будет равен 1.
  • Если первый и второй операнд - это буква.

Каждая триада будет проходить один из семи блоков и будет выполняться метод свертки.

Метод Proverka принимает значение элемента массива (операнда массива) и проверяет на одну из трех ситуаций. Операнд – это буква, цифра или указатель. И возвращает значение соответственно: 1, 2 или 3.

В программе будет предусмотрена защита от неинициализированной переменной. То есть если переменная есть, но ей не присвоено значение, то программа скажет нам об этом.

 

3 Результат работы программы оптимизации кода методом свертки

 

Если мы введем самую простую строку кода:
I = 1 + 1;
То нажимаем на кнопку «Распознать» и «Оптимизация». Программа выдаст результат показанный на Рис. 1.

Рисунок 1 – Результат работы программы оптимизации методом свертки

 

Если же мы введем к примеру строку кода:

I = 1 + 1;
I = 3;
J = 6*I + I;

Нажимаем на кнопку «Распознать» и «Оптимизация». Программа выводит следующие данные Рис. 2.

Рисунок 2 – Результат работы программы оптимизации методом свертки

Теперь если мы изменим код на следующий:

I = 1 + 1;
I = 3 + I;
J = 6*I + I;

То программа покажет следующий результат, показанный на Рис. 3.

Рисунок 3 – Результат работы программы оптимизации методом свертки

Если же мы в первом коде впишем переменную, которую мы не присваивали значение, то программа сообщит нам об этом. К примеру:

I = 1 + C;
I = 3 + I;
J = 6*I + I;

Программа выдаст следующее оповещение. Рис. 4.

Рисунок 4 – Ошибка инициализации переменной

 

4 Оптимизация кода методом исключения лишних операций

 Программа может программный код преобразовать в триады, посредством алгоритма преобразования. И оптимизировать при помощи метода исключения лишних операций.

Определим понятие лишней операции. Операция линейного участка с порядковым номером i считается лишней, если существует более ранняя идентичная ей операция с порядковым номером j и никакая переменная, от которой зависит эта операция, не изменялась никакой третьей операций, имеющей порядковый номер между i и j.

Алгоритм исключения лишних операций просматривает операции в порядке их следования. Также как и алгоритму свертки, алгоритму исключения лишних операций проще всего работать с триадами, потому что они полностью отражают взаимосвязь операций.
Чтобы следить за внутренней зависимостью переменных и триад алгоритм присваивает им некоторые значения, называемые числами зависимости, по следующим правилам:

  1. изначально для каждой переменной ее число зависимости равно 0, так как в начале работы программы значение переменной не зависит ни от какой триады;
  2. после обработки i-ой триады, в которой переменной A присваивается некоторое значение, число зависимости A (dep(A)) получает значение i, так как значение A теперь зависит от данной i-ой триады;
  3. при обработке i-ой триады ее число зависимости (dep(i)) принимается равным значению: 1+(максимальное из чисел зависимости операндов).

Таким образом, при использовании чисел зависимости триад и переменных можно утверждать, что если i-ая триада идентична j-ой триаде (j<i), то i-ая триада считается лишней в том и только в том случае, когда dep(i)=dep(j).

Алгоритм исключения лишних операций использует в своей работе также особого вида триады SAME(j,0), которые означают, что некоторая триада i идентична триаде j.

Алгоритм исключения лишних операций последовательно просматривает триады линейного участка. Он состоит из следующих шагов, выполняемых для каждой триады:

  1. Если операнд ссылается на особую триаду вида SAME(j,0), то он заменяется на ссылку на триаду с номером j (^j).
  2. Вычисляется число зависимости текущей триады с номером i, исходя из чисел зависимости ее операндов.
  3. Если существует идентичная j-ая триада, причем j<i и dep(i)=dep(j), то текущая триада i заменяется на триаду особого вида SAME(j,0).
  4. Если текущая триада есть присвоение, то вычисляется число зависимости соответствующей переменной.

 

5 Разработка алгоритма оптимизации кода методом исключения лишних операций

Программа должна иметь переменную, в которой будет записан код программы, который нужно будет разбить на триады и оптимизировать. После этого нужно будет с этой переменной получить строковые выражения типа: X = D + V.

После этого полученные выражения разбиваются на операнды и знаки в массив. По нашему примеру – это будет так: (X,=,D,+,V). Программа будет записывать массив в обратном порядке для того, чтобы проще было разбивать на триады.

После того как мы получили массив операндов и знаковых символов, мы будем вызывать метод обработки ( Obrabotka('/');). Данный метод принимает знаковый символ, в котором мы будем получать триаду. Цикл в этом методе будет длиться, пока формирование триады не закончилось. Готовая триада будет записываться в переменную TriadaMas, где элемент 0 – хранит знаки триады, 1, 2 – операнды. Массив Triada хранит триаду целиков без разбиения на операнды и знаки, она нужна для быстрого вывода в таблицу.

Метод Raspoznat_Click будет заниматься принятием строки, разбиения ее на выражения и построения триад. А также в отличии от предыдущей программы в нем будет формироваться массив букв, которые имеются в строке кода. Полученный массив сортируется по алфавиту методом пузырьковой сортировки.

Метод Optimazation_Click будет реализовывать метод исключения лишних операций. В этом методе будет инициализироваться таблица, если она еще не была построена. После этого идет цикл прохода всех триад. В первом проходе мы записываем строку: триады записываются без изменений, весовые значения букв равны нулю, dip(i) = 1. В остальных шагах прохода весовые значения будут изменяться только при операторе присваивания. А dip(i) будет вычисляться по своему алгоримту. После каждого построения dip(i) программа проверяет было ли такое значение раньше. Если да, то проверяем одинаковые ли знаки при этом. Если да, то идет замена триады на SAME(x,0), где x – это самое первое повторяющееся значение. Далее программа проверяет указатели, если указатели указывали на тот указатель, где сейчас триада заменена на SAME(x,0), то указатель заменяется на значение x.

Метод Positionbukvi – это метод для выявления позиции буквы в массиве. То есть метод возвращает значение позиции буквы в массиве.

 

6 Результат работы программы оптимизации методом исключения лишних операций

 

Вводим к примеру строку кода:

D = D + C*B;
A = D + C*B;
C = D + C*B;

Программа выдает следующий результат показанный на Рис. 5

Рисунок 5 – Результат работы программы оптимизации методом исключения лишних операций

Если мы изменим этот код на следующий:

D = D + C/B;
A = D + C*B;
C = D + C*B;

То в 4 уже не будет триад заменена на SAME, и указатель в 5 не будет заменен на 1 (Рис. 6).

Рисунок 6 – Результат работы программы оптимизации методом исключения лишних операций

 

Если мы изменим этот код так, чтобы было 3 буквы, например:
C = C/B;
A = B + C*B;
B = A + C*B;
То таблица букв будет состоять из 3-х букв. (Рис.7).

Рисунок 7 – Результат работы программы оптимизации методом исключения лишних операций

 

Купить и скачать говотую рабочую программу с ее проектом можно у нас... Этот вариант Вы нигде не скачаете, т.е. это авторская программа на языке Си Шарп. Ее вы можете использовать для курсовой работы или диплома.
Стоимость: 480 рублей. Для заказа пишите нам: dyalexxx@ukr.net

Просмотров: 3745

Вернуться в оглавление:Проектирование системных программ




Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.