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

Индуктивная переменная (англ. 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 (Ноябрь 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