Nätverk-Ullman-algoritm

Nätverk-Ullman-algoritm
Döpt efter Ravi Sethi [d] ochJeffrey Ullman
ändamål söka efter den optimala översättningsordningen för ett uttryck
Datastruktur Graf

Network-Ullman- algoritmen är en algoritm för att översätta abstrakta syntaxträd till maskinkod som använder så få register som möjligt . Algoritmen är uppkallad efter dess utvecklare Ravi Seti och Jeffrey Ullman ,

Översikt

Vid generering av kod för aritmetiska uttryck måste kompilatorn bestämma vilket som är det bästa sättet att översätta uttrycket i termer av antalet instruktioner som används, såväl som antalet register som behövs för att utvärdera ett visst underträd. Speciellt i de fall där antalet lediga register är litet kan exekveringsordningen vara viktig för längden på den genererade koden, eftersom en annan utvärderingsordning kan resultera i mer eller mindre mellanvärden som kastas in i minnet och sedan återställd. Nätverk-Ullman-algoritmen (även känd som Network-Ullmann-numrering ) har egenskapen att producera kod som kräver det minsta antalet instruktioner såväl som det minsta antalet minnesreferenser (förutsatt att åtminstone operationerna är kommutativa och associativa , men distributiv lag , d.v.s. utförs inte). Observera att algoritmen lyckas även om varken kommutativitet eller associativitet äger rum i uttrycket, och därför kan aritmetiska transformationer inte tillämpas. Algoritmen använder inte heller vanligt detektering av underuttryck eller den explicita användningen av generella riktade acykliska grafer istället för träd.

En enkel Net-Ullman-algoritm

Simple Network-Ullmann-algoritmen fungerar enligt följande (för load/store -arkitekturen ):

  1. Går det abstrakta syntaxträdet framåt eller bakåt
    1. Vi tilldelar 1 till vilken icke-konstant lövnod som helst (det vill säga vi behöver 1 register för att lagra en variabel / fält / etc.). Varje konstant ark (höger sida av operationen - bokstaver, värden) kommer att tilldelas 0.
    2. Varje icke-bladsnod n tilldelas det antal register som behövs för att beräkna motsvarande underträd n . Om antalet register som behövs i det vänstra underträdet ( l ) inte är lika med antalet register som behövs i det högra underträdet ( r ), är antalet register som behövs i den aktuella noden n max(l, r). Om l == r är antalet register som krävs för den aktuella noden .
  2. Kodgenerering
    1. Om antalet register som behövs för att beräkna det vänstra underträdet av nod n är större än antalet register för det högra underträdet, beräknas det vänstra underträdet först (eftersom ett extra register kan behövas för att lagra resultatet av det högra underträdet, överlagras av registret för det vänstra underträdet). Om det högra underträdet kräver fler register än det vänstra, utvärderas det högra trädet först. Om båda underträden kräver lika många register, spelar ordningsföljden för exekvering ingen roll.

Exempel

För ett aritmetiskt uttryck ser det abstrakta syntaxträdet ut så här:

= / \ en* / \ / \ ++ / \ / \ /\d3 + * / \ / \ bcfg

För att exekvera algoritmen behöver vi bara kontrollera det aritmetiska uttrycket , d.v.s. vi behöver bara titta på det högra underträdet för '='-destinationen:

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

Vi börjar nu trädvandringen genom att tilldela antalet register som behövs för att utvärdera varje underträd (observera att den sista termen i uttrycket är en konstant):

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

Från detta träd kan du se att vi behöver 2 register för att beräkna det vänstra underträdet av '*', men att vi bara behöver ett register för att beräkna det högra underträdet. Noderna "c" och "g" behöver inte register av följande anledningar: Om T är ett blad av trädet, är antalet register för att utvärdera T antingen 1 eller 0 beroende på om T är i det vänstra eller högra underträdet (eftersom operationer som att lägga till R1, A, kan bearbeta rätt komponent i A direkt utan att registrera den). Därför bör vi börja med att köra det vänstra underträdet, eftersom vi kan hamna i en situation där vi bara har två register för att utvärdera hela uttrycket. Om vi ​​beräknar det högra underträdet först (som bara kräver ett register), måste vi lagra resultatet av det högra underträdet medan vi beräknar det vänstra underträdet (som fortfarande behöver 2 register), så 3 register behövs. Utvärderingen av det vänstra underträdet kräver två register, men resultatet kan lagras i ett register, och eftersom det högra underträdet kräver ett register för att utvärdera, kan uttrycket utvärderas med endast två register.

Förbättrad Net-Ullman-algoritm

I en förbättrad version av Network-Ullman-algoritmen konverteras aritmetiska uttryck först med hjälp av de aritmetiska egenskaperna för de använda operatorerna.

Se även

Anteckningar

Litteratur

Länkar