Instruktionsval
Inom datavetenskap är instruktionsval scenen i en kompilatorbackend som omvandlar sin mellannivårepresentation ( IR) till en lågnivå-IR . I en typisk kompilator föregår instruktionsval både instruktionsschemaläggning och registerallokering ; därför har dess utsignal IR en oändlig uppsättning pseudoregister (ofta kända som temporära ) och kan fortfarande vara – och är vanligtvis – föremål för titthålsoptimering . Annars liknar det målmaskinkoden , bytekoden eller assemblerspråket .
Till exempel för följande sekvens av IR-kod på mellannivå
t1 = a t2 = b t3 = t1 + t2 a = t3 b = t1
en bra instruktionssekvens för x86-arkitekturen är
MOV EAX , a XCHG EAX , b ADD a , EAX
För en omfattande undersökning om instruktionsval, se.
Makroexpansion
Det enklaste sättet att välja instruktion är känt som makroexpansion eller tolkning av kodgenerering . En makroexpanderande instruktionsväljare fungerar genom att matcha mallar över mellannivå-IR. Vid en matchning exekveras motsvarande makro , med användning av den matchade delen av IR som indata, som avger de lämpliga målinstruktionerna. Makroexpansion kan göras antingen direkt på textrepresentationen av IR på mellannivå, eller så kan IR först omvandlas till en grafisk representation som sedan korsas djupet först. I den senare matchar en mall en eller flera intilliggande noder i grafen.
Om inte målmaskinen är väldigt enkel, genererar makroexpansion isolerat vanligtvis ineffektiv kod. För att mildra denna begränsning kombinerar kompilatorer som använder detta tillvägagångssätt vanligtvis det med titthålsoptimering för att ersätta kombinationer av enkla instruktioner med mer komplexa motsvarigheter som ökar prestandan och minskar kodstorleken. Detta är känt som Davidson-Fraser-metoden och används för närvarande i GCC .
Graftäckning
Ett annat tillvägagångssätt är att först omvandla mellannivå-IR till en graf och sedan täcka grafen med mönster . Ett mönster är en mall som matchar en del av grafen och kan implementeras med en enda instruktion från målmaskinen. Målet är att täcka grafen så att den totala kostnaden för de valda mönstren minimeras, där kostnaden typiskt representerar antalet cykler det tar att utföra instruktionen. För trädformade grafer kan den lägsta kostnadstäckningen hittas i linjär tid med dynamisk programmering , men för DAG :er och fullfjädrade grafer blir problemet NP-komplett och löses därmed oftast med antingen giriga algoritmer eller metoder från kombinatorisk optimering .
Lägsta gemensamma nämnarstrategi
Den minsta gemensamma nämnarstrategin är en instruktionsvalsteknik som används på plattformar där det finns processorkompletterande instruktioner för att göra körbara program portabla över ett brett spektrum av datorer. Under en strategi med lägsta gemensamma nämnare är kompilatorns standardbeteende att bygga för den lägsta gemensamma arkitekturen. Användning av alla tillgängliga processortillägg är avstängd som standard, såvida den inte uttryckligen slås på med kommandoradsknappar.
Användningen av en strategi med lägsta gemensamma nämnare innebär att processorkompletterande instruktioner och funktioner inte används som standard.