Indukční proměnná - Induction variable

v počítačová věda, an indukční proměnná je proměnná, která se dostane zvýšil nebo snížena o pevnou částku při každé iteraci smyčky nebo je a lineární funkce jiné indukční proměnné.[1]

Například v následující smyčce i a j jsou indukční proměnné:

pro (i = 0; i < 10; ++i) {    j = 17 * i;}

Aplikace na snížení pevnosti

Běžný optimalizace kompilátoru je rozpoznat existenci indukčních proměnných a nahradit je jednoduššími výpočty; například výše uvedený kód může kompilátor přepsat následujícím způsobem, za předpokladu, že přidání konstanty bude levnější než násobení.

j = -17;pro (i = 0; i < 10; ++i) {    j = j + 17;}

Tato optimalizace je zvláštním případem snížení síly.

Aplikace ke snížení tlaku v registru

V některých případech je možné tuto optimalizaci obrátit, aby se z kódu úplně odstranila indukční proměnná. Například:

externí int součet;int foo(int n) {    int i, j;    j = 5;    pro (i = 0; i < n; ++i) {        j += 2;        součet += j;    }    vrátit se součet;}

Smyčka této funkce má dvě indukční proměnné: i a j. Buď lze jeden přepsat jako lineární funkci druhého; proto může kompilátor optimalizovat tento kód, jako by byl napsán

externí int součet;int foo(int n) {    int i;    pro (i = 0; i < n; ++i) {        součet += 5 + 2 * (i + 1);    }    vrátit se součet;}

Substituce indukční proměnné

Substituce indukční proměnné je transformace kompilátoru k rozpoznání proměnných, které lze vyjádřit jako funkce indexů ohraničujících smyček, a jejich nahrazení výrazy zahrnujícími smyčkové indexy.

Tato transformace činí vztah mezi proměnnými a indexy smyčky explicitní, což pomáhá další analýze kompilátoru, jako je analýza závislosti.

Příklad:

Vstupní kód: 

int C, i;C = 10;pro (i = 0; i < 10; i++) {    C = C + 5; // c se zvýší o 5 pro každou iteraci smyčky}

Výstupní kód

int C, i;C = 10;pro (i = 0; i < 10; i++) {    C = 10 + 5 * (i + 1);  // c je výslovně vyjádřeno jako funkce indexu smyčky}

Nelineární indukční proměnné

Stejné optimalizace lze použít na indukční proměnné, které nemusí být nutně lineárními funkcemi čítače smyček; například smyčka

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

lze převést na

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

Viz také

Reference

  1. ^ Steven Muchnick; Muchnick and Associates (15. srpna 1997). Pokročilá implementace návrhu kompilátoru. Morgan Kaufmann. ISBN  978-1-55860-320-2. indukční proměnná.

Další čtení