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

Индуктивная переменная (англ. 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 + 1 );  // c является функцией от индекса
}

Нелинейные индуктивные переменные

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

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

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

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

Литература

• Альфред Ахо, Моника Лам, Рави Сети, Джеффри Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е издание. — М.: «Вильямс», 2008. — 1184 с. — 1500 экз. — ISBN 978-5-8459-1349-4.
• Steven S. Muchnick. Advanced Compiler Design and Implementation. — 5-е издание. — San Francisco: Morgan Kaufmann Publishers, 1997. — 856 с. — ISBN 1-55860-320-4.
• Kennedy, Ken; & Allen, Randy. Optimizing Compilers for Modern Architectures: A Dependence-based Approach (англ.). — Morgan Kaufmann, 2001. — ISBN 1-55860-286-0.
• Allen, Francis E.; Cocke, John; Kennedy, Ken (1981), "Reduction of Operator Strength", in Munchnik, Steven S.; Jones, Neil D. (eds.), Program Flow Analysis: Theory and Applications, Prentice-Hall, ISBN 978-0-13-729681-1
• Cocke, John; Kennedy, Ken (November 1977), "An algorithm for reduction of operator strength", Communications of the ACM, 20 (11){{citation}}: Википедия:Обслуживание CS1 (дата и год) (ссылка)
• Cooper, Keith; Simpson, Taylor; Vick, Christopher (1995), Operator Strength Reduction (PDF), Rice University, Дата обращения: 22 апреля 2010