Optimeringar i en traditionell kompilator tillämpas sekventiellt, med varje optimering destruktivt modifiera programmet för att producera ett transformerat program som sedan skickas till nästa optimering. Vi presenterar en ny metod för att strukturera optimeringsfasen av en kompilator. I vårt synsätt tar optimeringar formen av jämställdhetsanalyser som tillför jämställdhetsinformation till en gemensam mellanrepresentation. Optimatorn fungerar genom att upprepade gånger applicera dessa analyser för att inferera ekvivalenser mellan programfragment, vilket mättar den mellanliggande representationen med jämlikheter. En gång mättad, den mellanliggande representation kodar flera optimerade versioner av inmatningsprogrammet. Vid denna punkt, en lönsamhet heuristic plockar det slutliga optimerade programmet från de olika program som representeras i den mättade representationen. Vårt föreslagna sätt att strukturera optimerare har en mängd fördelar jämfört med tidigare tillvägagångssätt: vårt tillvägagångssätt undanröjer behovet av att oroa sig för optimeringsbeställning, möjliggör användning av en global optimering heuristic som väljer bland fullt optimerade program, och kan användas för att utföra översättningsvalidering, även på kompilatorer andra än våra egna. Vi presenterar vårt tillvägagångssätt, formaliserar det och beskriver vårt val av mellanrepresentation. Vi presenterar också experimentella resultat som visar att vår strategi är praktisk när det gäller tid och rum overhead, är effektiv på att upptäcka intrikata optimeringsmöjligheter, och är effektiv på att utföra översättningsvalidering för en realistisk optimizer.
Peggy REF utför översättningsvalidering för LLVM-kompilatorn med hjälp av jämlikhetsmättnad.
Equality saturation: a new approach to optimization
{'venue': "POPL '09", 'journal': None, 'mag_field_of_study': ['Computer Science']}