Индуктивная переменная
Индуктивная переменная (англ. 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., 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)
- Cooper, Keith; Simpson, Taylor & Vick, Christopher (1995), Operator Strength Reduction, Rice University, <http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR95635-S.pdf>. Проверено 22 апреля 2010.