Системное программное обеспечение. Лабораторный практикум

Видно, что результирующая последовательность триад может быть подвергнута дальнейшей оптимизации – в ней присутствуют лишние присваивания, но другие методы оптимизации выходят за рамки данной лабораторной работы (с ними можно познакомиться в [1, 2, 7]).

Алгоритм свертки объектного кода позволяет исключить из линейного участка программы операции, для которых на этапе компиляции уже известен результат. За счет этого сокращается время выполнения,[7] а также объем кода результирующей программы.

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

Исключение лишних операций

Исключение избыточных вычислений (лишних операций) заключается в нахождении и удалении из объектного кода операций, которые повторно обрабатывают одни и те же операнды.

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

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

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

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

• изначально для каждой переменной ее число зависимости равно 0, так как в начале работы программы значение переменной не зависит ни от какой триады;

• после обработки i-й триады, в которой переменной А присваивается некоторое значение, число зависимости A (dep(A)) получает значение i, так как значение А теперь зависит от данной i-й триады;

• при обработке i-й триады ее число зависимости (dep(i)) принимается равным значению 1+ (максимальное_из_чисел_зависимости_операндов).