Индуктивная переменная () — переменная в циклах, последовательные значения которой образуют арифметическую прогрессию. Наиболее распространенный пример — счётчик цикла. Индуктивные переменные часто используются в индексных выражениях массивов.

Например, в следующем примере, i и j являются индуктивными переменными: for ( i = 0; i < 10; i++ ) { j = 17 * i; }

Традиционные методы оптимизации предусматривают распознавание индуктивных переменных и удаление их из цикла.

Применение для снижения стоимости операций Общий принцип оптимизации заключается в распознавании индуктивных переменных и замене их простыми вычислениями. Например, приведённый выше код может быть изменен оптимизирующим компилятором, исходя из предположения о том, что сложение с константой будет дешевле, чем умножение: j = -17; for ( i = 0; i < 10; i++ ) { j = j + 17; } Это применение является частным случаем оптимизации снижения стоимости операций.

Применение для снижения давления на регистры В некоторых случаях можно использовать эту оптимизацию, чтобы совсем удалить индуктивную переменную из кода. Например: extern int sum; int foo(int n) { int i, j; j = 5; for ( i = 0; i < n; i++ )

j += 2; sum += j;

return sum; }

Цикл в функции имеет две индуктивные переменные: i и j. Одну из них можно представить в виде линейной функции от другой, поэтому компилятор может оптимизировать этот код следующим образом: extern int sum; int foo( int n) { int i; for ( i = 0; i < n; i++ )

sum += (5 + 2 * ( i + 1));

return sum; }

Замена индуктивной переменной Замена индуктивной переменной — преобразование, распознающее переменные, которые могут быть представлены в виде функции от индекса цикла, и заменяющее на соответствующие выражения. Это преобразование делает отношения между переменными и индексами циклов явными, что помогает другим оптимизациям компилятора. Рассмотрим пример: int c, i; c = 10; for ( i = 0; i < 10; i++ ) { c = c + 5; // c увеличивается на 5 на каждой итерации цикла } В соответствии с описанным выше методом получим следующее представление исходного кода: int c, i; c = 10; for ( i = 0; i < 10; i++ ) { c = 10 + 5 * ( i + 1 ); // c является функцией от индекса }

Нелинейные индуктивные переменные Те же самые оптимизации могут быть применены к индуктивным переменным, которые не являются линейными функциями счётчика цикла. Например, следующий код: j = 1; for ( i = 0; i < 10; i++ ) { j = j << 1; } может быть преобразован: for ( i = 0; i < 10; i++ ) { j = 1 << i+1; }

Примечания

Литература

Категория:Оптимизации компилятора