Инверсия цикла

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

Пример на языке C

  int i, a[100];
  i = 0;
  while (i < 100) {
    a[i] = 0;
    i++;
  }

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

  int i, a[100];
  i = 0;
  if (i < 100) {
    do {
      a[i] = 0;
      i++;
    } while (i < 100);
  }

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

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

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

      i := 0
 L1:  if i >= 100 goto L2
      a[i] := 0
      i := i + 1
      goto L1
 L2:  

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

  if i >= 100
  goto L2

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

  goto L1
  if i < 100
  a[i] := 0
  i := i + 1
  goto L1
  if i >= 100
  goto L2
  <<at L2>>

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

      i := 0
      if i >= 100 goto L2
 L1:  a[i] := 0
      i := i + 1
      if i < 100 goto L1
 L2:

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

  if i >= 100
  goto L2

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

  if i < 100
  goto L1
  a[i] := 0
  i := i + 1
  if i < 100
  <<at L2>>

Как видите, два перехода при выполнении были исключены (и, следовательно, две остановки конвейера).