Cтраница 1
Исключение повторных вычислений является одним из тех оптимизирующих преобразований, применение которых улучшает оба основных критерия эффективности программ. [1]
Для оптимизирующих преобразований типа исключения повторных вычислений, замены операции деления операцией умножения и уменьшения числа обращений к индексированным переменным в соответствующей области Т, кроме записи, являющейся признаком возможности выполнения данного преобразования, необходимо произвести некоторые дополнительные записи. [2]
В существующих оптимизирующих трансляторах, в частности трансляторах в ЕС ЭВМ, оптимизирующие преобразования, например исключение повторных вычислений, производятся в основном лишь в пределах линейных участков программы. [3]
Полная оптимизация линейных участков достигается благодаря тому, что с помощью метода нумерации значений выполняются не только исключение повторных вычислений и распространение констант, но и такие оптимизирующие преобразования, как замена операции деления операцией умножения и уменьшение числа обращений к индексированным переменным. Кроме того, рассматриваемая здесь процедура оптимизации предусматривает выполнение еще двух оптимизирующих преобразований: исключение мертвых переменных и вычислений, определяющих эти переменные, а также сокращение числа преобразований типов данных с помощью группирования переменных. [4]
Метод нумерации значений впервые был предложен в [38] для выполнения в пределах линейных участков программы таких оптимизирующих преобразований, как исключение повторных вычислений ( подвыражений и ( или) выражений) и распространение констант. Эта цель достигается следующим образом. [5]
Интуитивно понятно, что во время генерации нового промежуточного представления программы, соответствующего ее оптимизированному варианту, при реализации оптимизирующего преобразования исключение повторных вычислений новые переменные необходимо вводить всякий раз, когда в промежуточном представлении исходной программы встречается вычисление ( подвыражение), которое повторяется в программе. [6]
Если в программе линейные участки, содержащие эти вычисления, находятся в различных ветвях ( на различных путях), то можно выполнить чистку фрагментов; в противном случае - исключение повторных вычислений. [7]
Принцип ввода новых переменных является общим для различных оптимизирующих преобразований, при реализации которых необходимо это делать. Однако наиболее сложно этот вопрос решить при исключении повторных вычислений, так как реализация этого преобразования в общем случае может охватить всю программу. [8]
В процессе выполнения оптимизирующих преобразований более высокий приоритет имеют те преобразования, которые облегчают выполнение последующих преобразований, а в некоторых участках программы даже устраняют необходимость приложения других преобразований. Например, если в теле цикла имеются повторные инвариантные вычисления, то исключение повторных вычислений освобождает оптимизатор от необходимости перемещения из тела цикла каждого инвариантного вычисления. [9]
Для каждого оптимизирующего преобразования в соответствующей таблице ( в данном случае в таблице VALUE, LOOP или BRANCH) должна быть выделена самостоятельная область. Записываемая в этой области информация должна содержать как признак, указывающий возможность приложения оптимизирующего преобразования, так и информацию, которая необходима для последующей реализации этого преобразования. Например, для оптимизирующего преобразования исключение повторных вычислений в соответствующей области Т таблицы VALUE следует произвести следующие записи. [10]
Это означает, что данное выражение и ( или) подвыражение должно участвовать при выполнении каждого из этих оптимизирующих преобразований. Однако в таких случаях выполнение какого-либо одного оптимизирующего преобразования может устранять необходимость выполнения преобразования или нескольких преобразований другого типа. В частности, выполнение преобразования типа распространения констант может устранять необходимость исключения повторных вычислений, а выполнение исключения мертвой переменной - необходимость выполнения над вычислением, определяющим эту мертвую переменную, какого-либо другого преобразования. [11]
В процессе обнаружения неэффективных мест в программе формируется таблица VALUE и модифицируются таблицы LOOP и BRANCH. Таблица VALUE формируется как результат нумерации значений. В ней записывается информация о возможности выполнения таких оптимизирующих преобразований, как исключение мертвых переменных, распространение констант, инициирование переменных, исключение повторных вычислений, чистка фрагментов, замена операции деления операцией умножения, уменьшение числа обращений к индексированным переменным, уменьшение числа обращений к встроенным ( стандартным) функциям и процедурам-функциям, исключение из цикла инвариантных вычислений, замена операции деления операцией умножения в цикле, перемещение вычислений в менее часто выполняемые участки программы, сокращение числа преобразований данных с помощью перегруппировки переменных. [12]