Algoritmul Network-Ullman

Algoritmul Network-Ullman
Numit după Ravi Sethi [d] șiJeffrey Ullman
scop caută ordinea optimă de traducere a unei expresii
Structură de date grafic

Algoritmul Network-Ullman este un algoritm pentru traducerea arborilor de sintaxă abstractă în cod mașină care utilizează cât mai puține registre posibil . Algoritmul poartă numele dezvoltatorilor săi Ravi Seti și Jeffrey Ullman ,

Prezentare generală

Atunci când generează cod pentru expresii aritmetice , compilatorul trebuie să decidă care este cel mai bun mod de a traduce expresia în ceea ce privește numărul de instrucțiuni utilizate, precum și numărul de registre necesare pentru a evalua un anumit subarbore. Mai ales în cazul în care numărul de registre libere este mic, ordinea de execuție poate fi importantă pentru lungimea codului generat, deoarece o ordine diferită de evaluare poate avea ca rezultat valori mai mult sau mai puțin intermediare care sunt evacuate în memorie și apoi restaurat. Algoritmul Network-Ullman (cunoscut și ca numerotare Network-Ullmann ) are proprietatea de a produce cod care necesită numărul minim de instrucțiuni, precum și numărul minim de referințe de memorie (presupunând că cel puțin operațiile sunt comutative și asociative , dar legea distributivă , adică nu este îndeplinită). Rețineți că algoritmul reușește chiar dacă în expresie nu au loc nici comutativitatea , nici asociativitatea și, prin urmare, transformările aritmetice nu pot fi aplicate. De asemenea, algoritmul nu folosește detectarea subexpresiilor comune sau utilizarea explicită a graficelor aciclice direcționate generale în loc de arbori.

Un algoritm simplu Net-Ullman

Algoritmul Simple Network-Ullmann funcționează după cum urmează (pentru arhitectura încărcare/stocare ):

  1. Parcurgerea arborelui de sintaxă abstractă înainte sau înapoi
    1. Atribuim 1 oricărui nod frunză non-constant (adică avem nevoie de 1 registru pentru a stoca o variabilă / câmp / etc.). Orice foaie constantă (partea dreaptă a operației - literale, valori) va fi atribuită 0.
    2. Orice nod n care nu este frunză i se atribuie numărul de registre necesare pentru a calcula subarborele n corespunzător . Dacă numărul de registre necesare în subarborele din stânga ( l ) nu este egal cu numărul de registre necesare în subarborele din dreapta ( r ), numărul de registre necesare în nodul curent n este max(l, r). Dacă l == r , atunci numărul de registre necesare pentru nodul curent este .
  2. Generarea codului
    1. Dacă numărul de registre necesare pentru a calcula subarborele din stânga al nodului n este mai mare decât numărul de registre pentru subarborele din dreapta, atunci subarborele din stânga este calculat mai întâi (deoarece poate fi necesar un registru suplimentar pentru a stoca rezultatul subarborelui din dreapta, suprapus de registrul subarborelui din stânga). Dacă subarborele din dreapta necesită mai multe registre decât cel din stânga, atunci arborele din dreapta este evaluat mai întâi. Dacă ambii subarbori necesită un număr egal de registre, atunci ordinea de execuție nu contează.

Exemplu

Pentru o expresie aritmetică , arborele de sintaxă abstractă arată astfel:

= /\ A* /\ /\ ++ / \ / \ /\d3 + * / \ / \ bcfg

Pentru a executa algoritmul, trebuie doar să verificăm expresia aritmetică , i.e. trebuie doar să ne uităm la subarborele din dreapta al destinației „=”:

* /\ /\ ++ / \ / \ /\d3 + * / \ / \ bcfg

Începem acum mersul arborelui prin alocarea numărului de registre necesare pentru a evalua fiecare subarbore (rețineți că ultimul termen din expresie este o constantă):

* 2 /\ /\ + 2 + 1 / \ / \ / \ d 1 3 0 + 1 * 1 / \ / \ b 1 c 0 f 1 g 0

Din acest arbore, puteți vedea că avem nevoie de 2 registre pentru a calcula subarborele din stânga al lui „*”, dar avem nevoie de un singur registru pentru a calcula subarborele din dreapta. Nodurile „c” și „g” nu au nevoie de registre din următoarele motive: dacă T este o frunză a arborelui, atunci numărul de registre de evaluat T este fie 1, fie 0, în funcție de dacă T este în subarborele din stânga sau din dreapta. (deoarece operațiuni precum adăugarea R1, A pot procesa componenta corectă a lui A direct, fără a o înregistra). Prin urmare, ar trebui să începem prin a executa subarborele din stânga, deoarece putem ajunge la o situație în care avem doar două registre pentru a evalua întreaga expresie. Dacă calculăm mai întâi subarborele din dreapta (care necesită un singur registru), ar trebui să stocăm rezultatul subarborelui din dreapta în timp ce calculăm subarborele din stânga (care încă mai are nevoie de 2 registre), deci sunt necesare 3 registre. Evaluarea subarborelui din stânga necesită două registre, dar rezultatul poate fi stocat într-un singur registru, iar din moment ce subarborele din dreapta necesită un registru pentru evaluare, expresia poate fi evaluată doar cu două registre.

Algoritm Net-Ullman îmbunătățit

Într-o versiune îmbunătățită a algoritmului Network-Ullman, expresiile aritmetice sunt mai întâi convertite folosind proprietățile aritmetice ale operatorilor utilizați.

Vezi și

Note

Literatură

Link -uri