Индуктивная переменная

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Например, в следующем примере, 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;  // c является функцией от индекса
}

Нелинейные индуктивные переменные[править | править исходный текст]

Те же самые оптимизации могут быть применены к индуктивным переменным, которые не являются линейными функциями счётчика цикла. Например, следующий код:

j = 1;
for ( i = 0; i < 10; i++ ) 
{
  j = j << 1;
}

может быть преобразован:

for ( i = 0; i < 10; i++ ) 
{
  j = 1 << i+1;
}

Примечания[править | править исходный текст]

Литература[править | править исходный текст]