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

Induction variable

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

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

за (я = 0; я < 10; ++я) {    j = 17 * я;}

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

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

j = -17;за (я = 0; я < 10; ++я) {    j = j + 17;}

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

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

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

внешний int сумма;int фу(int п) {    int я, j;    j = 5;    за (я = 0; я < п; ++я) {        j += 2;        сумма += j;    }    возвращаться сумма;}

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

внешний int сумма;int фу(int п) {    int я;    за (я = 0; я < п; ++я) {        сумма += 5 + 2 * (я + 1);    }    возвращаться сумма;}

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

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

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

Пример:

Код ввода: 

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

Выходной код

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

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

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

j = 1;за (я = 0; я < 10; ++я) {    j = j << 1;}

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

за (я = 0; я < 10; ++я) {    j = 1 << (я+1);}

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

Рекомендации

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

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