stringtranslate.com

Индукционная переменная

В информатике индукционная переменная — это переменная, которая увеличивается или уменьшается на фиксированную величину при каждой итерации цикла или является линейной функцией другой индукционной переменной. [1]

Например, в следующем цикле iи jявляются индукционными переменными:

для ( я = 0 ; я < 10 ; ++ я ) { j = 17 * я ; }

Применение для снижения прочности

Распространенной оптимизацией компилятора является распознавание существования индукционных переменных и замена их более простыми вычислениями; например, приведенный выше код может быть переписан компилятором следующим образом, исходя из предположения, что добавление константы будет дешевле умножения.

j = -17 ;  для ( i = 0 ; i < 10 ; ++ i ) { j = j + 17 ; }

Эта оптимизация является частным случаем снижения прочности .

Применение для снижения давления на регистр

В некоторых случаях можно отменить эту оптимизацию, чтобы полностью удалить индукционную переменную из кода. Например:

внешняя целая сумма ;  int foo ( int n ) { int j = 5 ;        для ( int i = 0 ; i < n ; ++ i ) { j += 2 ; сумма += j ; }                 вернуть сумму ; }

Цикл этой функции имеет две индукционные переменные: iи j. Любую из них можно переписать как линейную функцию другой; поэтому компилятор может оптимизировать этот код, как если бы он был написан

внешняя целая сумма ;  int foo ( int n ) { for ( int i = 0 ; i < n ; ++ i ) { sum += 5 + 2 * ( i + 1 ); }                        вернуть сумму ; }

Индукционная подстановка переменной

Подстановка индукционной переменной — это преобразование компилятора для распознавания переменных, которые могут быть выражены как функции индексов охватывающих циклов, и замены их выражениями, включающими индексы циклов.

Это преобразование делает связь между переменными и индексами циклов явной, что облегчает другой анализ компилятора, например анализ зависимостей .

Пример:

Введите код: 

int c = 10 ;   for ( int i = 0 ; i < 10 ; i ++ ) { c = c + 5 ; // c увеличивается на 5 для каждой итерации цикла }

Выходной код

int c = 10 ;   for ( int i = 0 ; i < 10 ; i ++ ) { c = 10 + 5 * ( i + 1 ); // c явно выражено как функция индекса цикла }

Нелинейные индукционные переменные

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

j = 1 ;  для ( i = 0 ; i < 10 ; ++ i ) { j = j << 1 ; }

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

для ( i = 0 ; i < 10 ; ++ i ) { j = 1 << ( i + 1 ); }

Смотрите также

Ссылки

  1. ^ Стивен Мучник; Muchnick and Associates (15 августа 1997 г.). Advanced Compiler Design Implementation . Морган Кауфманн. ISBN 978-1-55860-320-2. индукционная переменная.

Дальнейшее чтение