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

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

Например, в следующем цикле 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 j = 5;

    for (int i = 0; i < n; ++i) {
        j += 2;
        sum += j;
    }

    return sum;
}

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

extern int sum;

int foo(int n) {
    for (int i = 0; i < n; ++i) {
        sum += 5 + 2 * (i + 1);
    }

    return sum;
}

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

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

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

Пример:

Входной код:

int c = 10;

for (int i = 0; i < 10; i++) {
    c = c + 5; // c is incremented by 5 for each loop iteration
}

Выходной код

int c = 10;

for (int i = 0; i < 10; i++) {
    c = 10 + 5 * (i + 1);  // c is explicitly expressed as a function of loop index
}

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

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

j = 1;

for (i = 0; i < 10; ++i) {
    j = j << 1;
}

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

for (i = 0; i < 10; ++i) {
    j = 1 << (i+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 г.