Titthålsoptimering
Titthålsoptimering är en optimeringsteknik som utförs på en liten uppsättning kompilatorgenererade instruktioner; den lilla uppsättningen är känd som titthålet eller fönstret.
Titthålsoptimering innebär att den lilla uppsättningen instruktioner ändras till en motsvarande uppsättning som har bättre prestanda.
Till exempel:
- istället för att trycka på register A på stapeln och sedan omedelbart skjuta tillbaka värdet i register A, skulle en titthålsoptimering ta bort båda instruktionerna;
- istället för att lägga till A till A, kan en titthålsoptimering göra en aritmetisk förskjutning åt vänster;
- istället för att multiplicera ett flyttalsregister med 8, kan en titthålsoptimering skala flyttalsregistrets exponent med 3; och
- istället för att multiplicera ett index med 4, lägga till resultatet till en basadress för att få ett pekarvärde och sedan därav referera till pekaren, kan en titthålsoptimering använda ett hårdvaruadresseringsläge som ger samma resultat med en instruktion.
Termen titthålsoptimering introducerades av William Marshall McKeeman 1965.
Ersättningsregler
Vanliga tekniker som används vid titthålsoptimering:
- Nollsekvenser – Ta bort onödiga operationer.
- Kombinera operationer – Ersätt flera operationer med en motsvarighet.
- Algebraiska lagar – Använd algebraiska lagar för att förenkla eller ändra ordning på instruktioner.
- Instruktioner för specialfodral – Använd instruktioner avsedda för speciella operandfodral.
- Adresslägesoperationer – Använd adresslägen för att förenkla koden.
Det kan finnas andra typer av titthålsoptimeringar.
Exempel
Ersätt långsamma instruktioner med snabbare
Följande Java-bytekod
... aload 1 aload 1 mul ...
kan ersättas av
... aload 1 dup mul ...
Denna typ av optimering, liksom de flesta titthålsoptimeringar, gör vissa antaganden om hur effektiva instruktionerna är. Till exempel, i det här fallet, antas det att dup -operationen (som duplicerar och trycker på toppen av stacken ) är mer effektiv än aload X -operationen (som laddar en lokal variabel identifierad som X och trycker den på stacken).
Tar bort redundant kod
Ett annat exempel är att eliminera redundanta lastlager.
a = b + c; d = a + e;
är enkelt implementerat som
MOVb , R0 ; _ Kopiera b till registret ADD c , R0 ; Lägg till c till registret, registret är nu b+c MOV R0 , a ; Kopiera registret till en MOV a , R0 ; Kopiera a till registret ADD e , R0 ; Lägg till e till registret, registret är nu a+e [(b+c)+e] MOV R0 , d ; Kopiera registret till d
men kan optimeras till
MOVb , R0 ; _ Kopiera b till registret ADD c , R0 ; Lägg till c till registret, som nu är b+c (a) MOV R0 , a ; Kopiera registret till en ADD e , R0 ; Lägg till e till registret, som nu är b+c+e [(a)+e] MOV R0 , d ; Kopiera registret till d
Ta bort redundanta stackinstruktioner
Om kompilatorn sparar register i stacken innan du anropar en subrutin och återställer dem när de återvänder, kan på varandra följande anrop till subrutiner ha redundanta stackinstruktioner.
Anta att kompilatorn genererar följande Z80- instruktioner för varje proceduranrop:
PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR POP HL POP DE POP BC POP AF
Om det fanns två på varandra följande subrutinsamtal skulle de se ut så här:
PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR1 POP HL POP DE POP BC POP AF PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR2 POP HL POP DE POP BC POP AF
Sekvensen POP-regg följt av PUSH för samma register är i allmänhet redundant. I de fall det är överflödigt, skulle en titthålsoptimering ta bort dessa instruktioner. I exemplet skulle detta göra att ytterligare ett redundant POP/PUSH-par dyker upp i titthålet, och dessa skulle tas bort i sin tur. Om vi antar att subrutinen _ADDR2 inte beror på tidigare registervärden, skulle ta bort all redundant kod i exemplet ovan så småningom lämna följande kod:
PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR1 CALL _ADDR2 POP HL POP DE POP BC POP AF
Genomförande
Moderna kompilatorer implementerar ofta titthålsoptimeringar med en mönstermatchningsalgoritm .
Se även
- Objektkodsoptimerare , diskussion i relation till generell algoritmisk effektivitet
- Capex Corporation – producerade COBOL optimizer , en tidig stordatorobjektkodoptimerare för IBM Cobol
- Superoptimering
- Digital Research XLT86 , en optimerande sammanställning källa-till-källa-kompilator
externa länkar
Ordboksdefinitionen av titthålsoptimering på Wiktionary