Värdenumrering

Värdenumrering är en teknik för att bestämma när två beräkningar i ett program är likvärdiga och eliminera en av dem med en semantikbevarande optimering .

Global värdenumrering

Global värdenumrering (GVN) är en kompilatoroptimering baserad på mellanrepresentationen av static single assignment form ( SSA). Det hjälper ibland att eliminera överflödig kod som inte gör det med vanlig subexpression eliminering ( CSE). Samtidigt kan dock CSE eliminera kod som GVN inte gör, så båda finns ofta i moderna kompilatorer. Global värdenumrering skiljer sig från lokal värdenumrering genom att värde-nummermappningarna även gäller över grundläggande blockgränser, och olika algoritmer används för att beräkna mappningarna.

Global värdenumrering fungerar genom att tilldela ett värdenummer till variabler och uttryck. Samma värdenummer tilldelas de variabler och uttryck som bevisligen är ekvivalenta. Till exempel i följande kod:

w := 3 x := 3 y := x + 4 z := w + 4

en bra GVN-rutin skulle tilldela samma värdenummer till w och x , och samma värdenummer till y och z . Till exempel, kartan $\left\{{w}\mapsto 1,{x}\mapsto 1,{y}\mapsto 2, {z}\mapsto 2\right\}$ skulle utgöra en optimal värde-nummermappning för detta block. Med hjälp av denna information kan det tidigare kodfragmentet säkert omvandlas till:

w := 3 x := w y := w + 4 z := y

Beroende på koden som följer efter detta fragment, kan kopieringsförökning ta bort tilldelningarna till x och till z .

Anledningen till att GVN ibland är kraftfullare än CSE kommer från det faktum att CSE matchar lexikalt identiska uttryck medan GVN försöker fastställa en underliggande ekvivalens. Till exempel i koden:

a := c × d e := c f := e × d

Utan kopieringsförökning skulle CSE inte eliminera omräkningen som tilldelats f , men även en dålig GVN-algoritm borde upptäcka och eliminera denna redundans.

SSA-formulär krävs för att utföra GVN så att falska $\left\{{\text{variabelnamn}}\mapsto {\text{värdenummer}}\right\}$ mappningar inte är skapas.

Lokal värdenumrering

Local value numbering (LVN) är en kompilatoroptimering som syftar till att hitta flera instanser av ekvivalenta uttryck (dvs uttryck som ger samma resultat) och ersätta dem med den första förekomsten. LVN är en lokal optimering, vilket innebär att till skillnad från global värdenumrering fungerar den på ett enda grundblock åt gången.

Lokal värdenumrering fungerar genom att tilldela ett unikt nummer till varje operation och komma ihåg dessa associationer. Efterföljande instruktioner slås sedan upp och, om en identisk instruktion redan har registrerats, ersätts den med den tidigare instruktionens resultat. Till exempel:

a ← 4 a är taggat som #1 b ← 5 b är taggat som #2 c ← a + bc (#1 + #2) är taggat som #3 d ← 5 d är taggat som #2, samma som b e ← a + de, som är '#1 + #2', är taggad som #3

Genom att tilldela siffror till instruktioner omvandlas jämförelse för dubbletter till enkla heltalsjämförelser. I detta specifika exempel c och e samma nummer (#3), vilket signalerar till kompilatorn att alla referenser till e helt enkelt kan ersättas med ettor till c .

Svårigheter och förlängningar

Problem när du inte använder SSA

En naiv implementering kan försöka utföra optimeringen genom att direkt använda variabelnamnen istället för siffror. Detta tillvägagångssätt fungerar dock inte när värdena på variabler kan ändras. Tänk på pseudokoden :

a ← 1 a är taggat som #1 b ← 2 b är taggat som #2 c ← a + bc är taggat som #3 b ← 3 d ← a + bd är felaktigt taggat som #3

I det här scenariot tilldelas d felaktigt siffran 3 eftersom argumenten matchar de för c . Detta är dock felaktigt eftersom b har ändrat värde från 2 till 3, vilket gör att de faktiska resultaten skiljer sig. Att använda SSA-representationen löser denna skillnad.

Använda matematiska identiteter

En enkel implementering kanske inte heller kan fånga alla ekvivalenta uttryck, även när de bara skiljer sig åt genom ordningen på deras operander. I följande exempel a och b tilldelas samma nummer:

a ← 1 + 2 b ← 2 + 1

Detta problem kan enkelt lösas antingen genom att tilldela samma nummer till båda fallen (dvs. a + b och b + a är båda registrerade med samma nummer) eller genom att sortera operanderna innan du söker efter motsvarigheter.

Lokala värdenumreringsoptimerare kan också vara medvetna om matematiska identiteter. Om vi ​​antar a är ett heltal kan alla följande uttryck tilldelas samma värde:

 b ← a + 0 c ← a * 1 d ← min(a, MAX_INT) e ← max(a, a) f ← a & 0xFF..FF (förutsatt att '&' anger bitvis  OCH  ) 

Se även

• Partiell redundans eliminering
• Optimerar kompilatorn
• Vanligt eliminering av underuttryck

Vidare läsning

•    Kildall, Gary Arlen (1973). "En enhetlig strategi för global programoptimering" . Handlingar från det första årliga ACM SIGACT-SIGPLAN-symposiet om principer för programmeringsspråk . Popl '73: 194–206. doi : 10.1145/512927.512945 . hdl : 10945/42162 . ISBN 9781450373494 . S2CID 10219496 . Hämtad 2006-11-20 . [1]
• Alpern, Bowen, Wegman, Mark N. och Zadeck, F. Kenneth. "Detecting Equality of Variables in Programs.", Konferensprotokoll från det femtonde årliga ACM-symposiet om principer för programmeringsspråk ( POPL ) , ACM Press, San Diego, CA, USA, januari 1988, sidorna 1–11.
• L. Taylor Simpson, "Värdedriven redundanseliminering." Teknisk rapport 96-308, Institutionen för datavetenskap, Rice University, 1996. (Författarens doktorsavhandling)
•   Muchnick, Steven Stanley (1997). Avancerad kompilatordesign och implementering . Morgan Kaufmann förlag . ISBN 978-1-55860-320-2 .
• Briggs, P.; Cooper, Keith D. ; Simpson, L. Taylor (1997). "Värdenumrering". Programvara-praxis och erfarenhet . 27 (6): 701–724.