WikiDer > Инверсия петли

Loop inversion

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

Пример на C

  int я, а[100];  я = 0;  пока (я < 100) {    а[я] = 0;    я++;  }

эквивалентно:

  int я, а[100];  я = 0;  если (я < 100) {    делать {      а[я] = 0;      я++;    } пока (я < 100);  }

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

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

Пример в трехадресном коде

      i: = 0 L1: если i> = 100 перейти к L2 a [i]: = 0 i: = i + 1 перейти к L1 L2:

Если я был инициализирован на 100, инструкции, выполняемые во время выполнения, были бы такими:

1   если i> = 1002   перейти к L2

Предположим, что я был инициализирован некоторым значением меньше 100. Теперь давайте посмотрим на инструкции, выполняемые в момент после я увеличено до 99 в цикле:

1   перейти L12   если я <1003   a [i]: = 04   я: = я + 15   перейти L16   если i> = 1007   перейти к L28   <<at L2>>

Теперь посмотрим на оптимизированную версию:

      i: = 0, если i> = 100 перейти к L2 L1: a [i]: = 0 i: = i + 1 if i <100 перейти к L1 L2:

Опять же, давайте посмотрим на инструкции, выполняемые, если я инициализируется значением 100:

1   если i> = 1002   перейти к L2

Мы не тратили зря циклов по сравнению с исходной версией. Теперь рассмотрим случай, когда я увеличено до 99:

1   если я <1002   перейти L13   a [i]: = 04   я: = я + 15   если я <1006   <<at L2>>

Как видите, два идти кs (и, таким образом, две остановки конвейера) были устранены при выполнении.