Алгоритмы, структуры данных

       

В статье рассмотрен метод анализа


В статье рассмотрен метод анализа циклов с помощью производящих функций. Несмотря на то, что не все циклы могут быть подвергнуты анализу с помощью данного метода, его можно применить для решения нижеперечисленных задач.
1. Данный метод выполняет задачу, обратную описанной в [3, разд. 14.1.1] – т.е. заменяет инкрементальные вычисления вычислениями по формуле. Кроме того, в процессе анализа цикла с помощью данного метода можно найти все его индуктивные переменные.
2. Компилятор, проделав все вышеприведенные вычисления, может либо заменить результат вычислений на константу (если все параметры являются постоянными), либо использовать вместо цикла соответствующую формулу.
3. Если цикл, подобный вышеприведенному, является вложенным в какой-либо другой, то производящие функции для переменных из V можно использовать описанным выше способом при оптимизации главного цикла.
4. Данный метод, как и многие другие методы алгебраической оптимизации, может быть использован только для целых чисел из-за возможной потери точности или переполнения чисел с плавающей точкой.
5. Полученные выражения для переменных могут быть использованы при анализе зависимостей между переменными, определении псевдонимов, устранении общих подвыражений (в том числе и полученных при выполнении аналогичных действий в различных циклах), при устранении незначимых вычислений, при определении индуктивных переменных.
6. Аналогичный подход может быть применен при оптимизации некоторых видов рекурсивных вычислений.

Содержание раздела