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

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

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

для   (  я знак   равно   0  ;   я   <   10  ;   ++  я  )   {      j   знак равно   17   *   я  ;  } 

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

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

j   =   -17  ;  для   (  я   знак равно   0  ;   я   <   10  ;   ++  я  )   {      j   знак равно   j   +   17  ;  } 

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

Заявка на снижение давления регистра

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

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

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

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

Замена индукционной переменной

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

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

Пример:

Входной код:

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

Выходной код

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

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

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

j   =   1  ;  для   (  я   знак равно   0  ;   я   <   10  ;   ++  я  )   {      j   знак равно   j   <<   1  ;  } 

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

для   (  я знак   равно   0  ;   я   <   10  ;   ++  я  )   {      j   знак равно   1   <<   (  я  +  1  );  } 

См. также

• Математическая индукция

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

• Ахо, Альфред В.; Сетхи, Рави; Уллман, Джеффри Д. (1986), Составители: принципы, методы и инструменты (2-е изд.), ISBN  978-0-201-10088-4
• Аллен, Фрэнсис Э.; Кок, Джон ; Кеннеди, Кен (1981), «Снижение силы оператора», в Мюнхнике, Стивен С.; Джонс, Нил Д. (ред.), Анализ потока программы: теория и приложения , Prentice-Hall, ISBN  978-0-13-729681-1
• Кок, Джон ; Кеннеди, Кен (ноябрь 1977 г.), «Алгоритм снижения силы оператора», Communications of the ACM , 20 (11): 850–856, doi : 10.1145/359863.359888 , S2CID   1092505
• Купер, Кейт; Симпсон, Тейлор; Вик, Кристофер (1995), Снижение силы оператора (PDF) , Университет Райса , получено 22 апреля 2010 г.