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

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

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

  int   я  ,   а  [  100  ];    я   =   0  ;    в то время как   (  я   <   100  )   {      а  [  я  ]   знак равно   0  ;      я  ++  ;    } 

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

  int   я  ,   а  [  100  ];    я   =   0  ;    если   (  я   <   100  )   {      do   {        а  [  я  ]   знак равно   0  ;        я  ++  ;      }   Пока   (  я   <   100  );    } 

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

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

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

 я := 0 L1: если я >= 100, переходим к L2      а[я] := 0      я := я + 1      перейти к L1 Л2:   

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

 если я >= 100  перейти к L2 

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

 перейти к L1  если я < 100  а[я] := 0  я := я + 1  перейти к L1  если я >= 100  перейти к L2  <<на L2>> 

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

 я := 0      если я >= 100, переходим к L2 L1: а[я] := 0      я := я + 1      если я < 100, перейдите к L1 Л2: 

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

 если я >= 100  перейти к L2 

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

 если я < 100  перейти к L1  а[я] := 0  я := я + 1  если я < 100  <<на L2>> 

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