Оптимизация вычисления логических выражений. Особенность оптимизации логических выражений заключается в том, что не всегда необходимо полностью выполнять вычисление всего выражения для того, чтобы знать его результат. Иногда по результату первой операции или даже по значению одного операнда можно заранее определить результат вычисления всего выражения.
Операция называется предопределенной для некоторого значения операнда, если ее результат зависит только от этого операнда и остается неизменным (инвариантным) относительно значений других операндов. Операция логического сложения (оr) является предопределенной для логического значения “истина” (true), а операция логического умножения – предопределена для логического значения “ложь” (false). Эти факты могут быть использованы для оптимизации логических выражений. Действительно, получив значение “истина” в последовательности логических сложений или значение “ложь” в последовательности логических умножений, нет никакой необходимости далее производить вычисления – результат уже определен и известен.
Например, выражение A or В or С or D не имеет смысла вычислять, если известно, что значение переменной А есть true (“истина”). Компиляторы строят объектный код вычисления логических выражений таким образом, что вычисление выражения прекращается сразу же, как только его значение становится предопределенным. Это позволяет ускорить вычисления при выполнении результирующей программы. В сочетании с преобразованиями логических выражений на основе тождеств булевой алгебры и перестановкой операций эффективность данного метода может быть несколько увеличена.
He только логические операции могут иметь предопределенный результат. Некоторые математические операции и функции также обладают этим свойством. Например, умножение на 0 не имеет смысла выполнять.
Другой пример такого рода преобразований – это исключение вычислений для инвариантных операндов.
Операция называется инвариантной относительно некоторого значения операнда, если ее результат не зависит от этого значения операнда и определяется другими операндами.
Например, логическое сложение (оr) инвариантно относительно значения “ложь”, логическое умножение (and) – относительно значения “истина”; алгебраическое сложение инвариантно относительно 0, а алгебраическое умножение – относительно 1.
Выполнение такого рода операций можно исключить из текста программы, если известен инвариантный для них операнд. Этот метод оптимизации имеет смысл в сочетании с методом свертки операций.
Оптимизация передачи параметров в процедуры и функции. Существуют методы, позволяющие снизить затраты кода и времени выполнения на передачу параметров в процедуры и функции и повысить в результате эффективность результирующей программы:
· передача параметров через регистры процессора;
· подстановка кода функции в вызывающий объектный код.
Метод передачи параметров через регистры процессора позволяет разместить все или часть параметров, передаваемых в процедуру или функцию, непосредственно в регистрах процессора, а не в стеке. Это позволяет ускорить обработку параметров функции, поскольку работа с регистрами процессора всегда выполняется быстрее, чем с ячейками оперативной памяти, где располагается стек. Если все параметры удается разместить в регистрах, то сокращается также и объем кода, поскольку исключаются все операции со стеком при размещении в нем параметров.
Понятно, что регистры процессора, используемые для передачи параметров в процедуру или функцию, не могут быть задействованы напрямую для вычислений внутри этой процедуры или функции. Поскольку программно доступных регистров процессора всегда ограниченное количество, то при выполнении сложных вычислений могут возникнуть проблемы с их распределением. Тогда компилятор должен выбрать: либо использовать регистры для передачи параметров и снизить эффективность вычислений (часть промежуточных результатов, возможно, потребуется размещать в оперативной памяти или в том же стеке), либо использовать свободные регистры для вычислений и снизить эффективность передачи параметров. Поэтому реализация данного метода зависит от количества программно доступных регистров процессора в целевой вычислительной системе и от используемого в компиляторе алгоритма распределения регистров. В современных процессорах число программно доступных регистров постоянно увеличивается с разработкой все новых и новых их вариантов, поэтому и значение этого метода постоянно возрастает.
Этот метод имеет ряд недостатков. Во-первых, очевидно, он зависит от архитектуры целевой вычислительной системы. Во-вторых, процедуры и функции, оптимизированные таким методом, не могут быть использованы в качестве процедур или функций библиотек подпрограмм ни в каком виде. Это вызвано тем, что методы передачи параметров через регистры процессора не стандартизованы (в отличие от методов передачи параметров через стек) и зависят от реализации компилятора. Наконец, этот метод не может быть использован, если где бы то ни было в процедуре или функции требуется выполнить операции с адресами (указателями) на параметры.
Метод подстановки кода функции в вызывающий объектный код (так называемая inline-подстановка) основан на том, что объектный код функции непосредственно включается в вызывающий объектный код всякий раз в месте вызова функции.
Для разработчика исходной программы такая функция (называемая inline-функцией) ничем не отличается от любой другой функции, но для вызова ее в результирующей программе используется принципиально другой механизм. По сути, вызов функции в результирующем объектном коде вовсе не выполняется – просто все вычисления, производимые функцией, выполняются непосредственно в самом вызывающем коде в месте ее вызова.
Очевидно, что в общем случае такой метод оптимизации ведет не только к увеличению скорости выполнения программы, но и к увеличению объема объектного кода. Скорость увеличивается за счет отказа от всех операций, связанных с вызовом функции, – это не только сама команда вызова, но и все действия, связанные с передачей параметров. Вычисления при этом идут непосредственно с фактическими параметрами функции. Объем кода растет, так как приходится всякий раз включать код функции в место ее вызова. Тем не менее, если функция очень проста и включает в себя лишь несколько машинных команд, то можно даже добиться сокращения кода результирующей программы, так как при включении кода самой функции в место ее вызова оттуда исключаются операции, связанные с передачей ей параметров.
Оптимизация циклов. Циклом в программе называется любая последовательность участков программы, которая может выполняться повторно.
Циклы обычно содержат в себе один или несколько линейных участков, где производятся вычисления. Поэтому методы оптимизации линейных участков позволяют повысить также и эффективность выполнения циклов, причем они оказываются тем более эффективными, чем больше кратность выполнения цикла. Но есть методы оптимизации программ, специально ориентированные на оптимизацию циклов.
Для оптимизации циклов используются следующие методы:
· вынесение инвариантных вычислений из циклов;
· замена операций с индуктивными переменными;
· слияние и развертывание циклов.
Вынесение инвариантных вычислений из циклов заключается в вынесении за пределы циклов тех операций, операнды которых не изменяются в процессе выполнения цикла. Очевидно, что такие операции могут быть выполнены один раз до начала цикла, а полученные результаты потом могут использоваться в теле цикла. Например, цикл
for i:=1 to 10 do
begin
A[i]:= В * С * A[i];
…
end;
может быть заменен на последовательность операций
D:= В * С;
for i:=1 to 10 do
begin
A[i]:= D * A[i];
…
end;
если значения В и С не изменяются нигде в теле цикла. При этом операция умножения В*С будет выполнена только один раз, в то время как в первом варианте она выполнялась 10 раз над одними и теми же результатами.
Замена операций с индуктивными переменными заключается в изменении сложных операций с индуктивными переменными в теле цикла на более простые операции. Как правило, выполняется замена умножения на сложение.
Переменная называется индуктивной в цикле, если ее значения в процессе выполнения цикла образуют арифметическую прогрессию. Таких переменных в цикле может быть несколько, тогда в теле цикла их иногда можно заменить на одну-единственную переменную, а реальные значения для каждой переменной будут вычисляться с помощью соответствующих коэффициентов соотношения (за пределами цикла значения всем переменным должны быть присвоены, если, конечно, они используются).
Простейшей индуктивной переменной является переменная-счетчик цикла с перечислением значений (цикл типа for, который встречается в синтаксисе многих современных языков программирования). Более сложные случаи присутствия индуктивных переменных в цикле требуют специального анализа тела цикла. Не всегда выявление таких переменных является тривиальной задачей.
После того как индуктивные переменные выявлены, необходимо проанализировать те операции в теле цикла, где они используются. Часть таких операций может быть упрощена. Как правило, речь идет о замене умножения на сложение.
Например, цикл
S:=10;
for i:=1 to N do A[i]:= i*S;
может быть заменен на последовательность операций
S:= 10;
Т:= S; i:=1;
while i <= 10 do
begin
A[i]:= Т; Т:=Т + 10; i:=i + 1;
end;
Здесь использован синтаксис языка Pascal, а Т – это некоторая новая временная переменная (использовать для той же цели уже существующую переменную S не вполне корректно, так как ее значение может быть использовано и после завершения этого цикла). В итоге удалось отказаться от выполнения N операций умножения, заменив их на N операций сложения (которые обычно выполняются быстрее). Индуктивной переменной в первом варианте цикла являлась i, а во втором варианте – i и Т.
В современных реальных компиляторах такие преобразования используются достаточно редко, поскольку они требуют достаточно сложного анализа программы, в то время как достигаемый выигрыш невелик – разница в скорости выполнения сложения и умножения, равно как и многих других операций, в современных вычислительных системах не столь существенна. Кроме того, существуют варианты циклов, для которых эффективность указанных методов преобразования является спорной.
Слияние и развертывание циклов предусматривает два различных варианта преобразований: слияния двух вложенных циклов в один и замена цикла на линейную последовательность операций.
Слияние двух циклов можно проиллюстрировать на примере следующих циклов:
for i:=l to N do
for j:=l to M do A[i,j]:= 0;
Здесь происходит инициализация двумерного массива. Но в объектном коде двумерный массив – это всего лишь область памяти размером N*M, поэтому (с точки зрения объектного кода, но не входного языка!) эту операцию можно представить так:
К:= N*M:
for i:=l to К do A[i]:= 0;
Развертывание циклов можно выполнить для циклов, кратность выполнения которых известна уже на этапе компиляции. Тогда цикл, кратностью N, можно заменить на линейную последовательность N операций, содержащих тело цикла. Например, цикл
for i:=l to 3 do A[i]:=i;
можно заменить операциями
А[1]:=1;
А[2]:=2;
А[3]:=3;
