Inverze smyčky - Loop inversion

v počítačová věda, inverze smyčky je optimalizace kompilátoru a transformace smyčky ve kterém a zatímco smyčka se nahrazuje znakem pokud blok obsahující a dělat.. zatímco smyčka. Při správném použití může zlepšit výkon kvůli pipeline potrubí.

Příklad v C

  int i, A[100];  i = 0;  zatímco (i < 100) {    A[i] = 0;    i++;  }

odpovídá:

  int i, A[100];  i = 0;  -li (i < 100) {    dělat {      A[i] = 0;      i++;    } zatímco (i < 100);  }

Navzdory zdánlivě větší složitosti druhého příkladu může ve skutečnosti běžet moderněji rychleji CPU protože používají instrukční potrubí. Jakýkoli skok v kódu přirozeně způsobí a stání potrubí, což je na úkor výkonu.

Navíc inverze smyčky umožňuje bezpečné pohyb kódu invariantního k smyčce.

Příklad v kódu se třemi adresami

      i: = 0 L1: pokud i> = 100 přejde na L2 a [i]: = 0 i: = i + 1 přejde na L1 L2:

Li i byl inicializován na 100, instrukce provedené za běhu by byly:

1   pokud i> = 1002   přejděte na L2

Předpokládejme to i byla inicializována na nějakou hodnotu menší než 100. Nyní se podívejme na instrukce provedené v následující chvíli i byl ve smyčce zvýšen na 99:

1   přejděte na L12   pokud i <1003   a [i]: = 04   i: = i + 15   přejděte na L16   pokud i> = 1007   přejděte na L28   <<at L2>>

Nyní se podívejme na optimalizovanou verzi:

      i: = 0 pokud i> = 100 přejde na L2 L1: a [i]: = 0 i: = i + 1 pokud i <100 přejde na L1 L2:

Znovu se podívejme na provedené instrukce, pokud i je inicializován na 100:

1   pokud i> = 1002   přejděte na L2

Ve srovnání s původní verzí jsme neztráceli žádné cykly. Nyní zvažte případ i byl zvýšen na 99:

1   pokud i <1002   přejděte na L13   a [i]: = 04   i: = i + 15   pokud i <1006   <<at L2>>

Jak vidíte, dva jít dos (a tedy dva stánky potrubí) byly při provádění odstraněny.