Vanligt eliminering av underuttryck

I kompilatorteorin är eliminering av vanliga underuttryck ( CSE ) en kompilatoroptimering som söker efter instanser av identiska uttryck (dvs alla värderas till samma värde), och analyserar om det är värt att ersätta dem med en enda variabel som håller det beräknade värdet .

Exempel

I följande kod:

a = b * c + g; d = b * c * e;

det kan vara värt att omvandla koden till:

tmp = b * c; a = tmp + g; d = tmp * e;

om kostnaden för att lagra och hämta tmp är mindre än kostnaden för att beräkna b * c en extra gång.

Princip

Möjligheten att utföra CSE baseras på tillgänglig uttrycksanalys (en dataflödesanalys) . Ett uttryck b*c är tillgängligt vid en punkt p i ett program om:

  • varje väg från den initiala noden till p utvärderar b*c innan den når p ,
  • och det finns inga uppgifter till b eller c efter utvärderingen utan före p .

Kostnads/nyttoanalysen som utförs av en optimerare kommer att beräkna om kostnaden för butiken till tmp är mindre än kostnaden för multiplikationen; i praktiken är andra faktorer som vilka värden som hålls i vilka register också signifikanta.

Kompilatorförfattare särskiljer två typer av CSE:

  • eliminering av lokalt gemensamt underuttryck fungerar inom ett enda grundläggande block
  • eliminering av globala gemensamma underuttryck fungerar på en hel procedur,

Båda typerna förlitar sig på dataflödesanalys av vilka uttryck som finns tillgängliga vid vilka punkter i ett program.

Fördelar

Fördelarna med att utföra CSE är tillräckligt stora för att det är en vanlig optimering.

I enkla fall som i exemplet ovan kan programmerare manuellt eliminera dubblettuttrycken medan de skriver koden. Den största källan till CSE:er är mellanliggande kodsekvenser som genereras av kompilatorn, till exempel för arrayindexeringsberäkningar , där det inte är möjligt för utvecklaren att manuellt ingripa. I vissa fall kan språkfunktioner skapa många dubbletter av uttryck. Till exempel C- makron , där makroexpansion kan resultera i vanliga underuttryck som inte syns i den ursprungliga källkoden.

Kompilatorer måste vara kloka om antalet tillfälliga som skapas för att hålla värden. Ett för stort antal temporära värden skapar registertryck , vilket möjligen resulterar i att register spills till minnet, vilket kan ta längre tid än att bara beräkna om ett aritmetiskt resultat när det behövs.

Se även

Hämtad från " https://en.wikipedia.org/w/index.php?title=Common_subexpression_elimination&oldid=1081015298 "