En l'optimització del compilador, l'assignació de registres és el procés d'assignar variables automàtiques locals i resultats d'expressions a un nombre limitat de registres del processador.
L'assignació de registres pot tenir lloc sobre un bloc bàsic (assignació de registres local), sobre una funció o un procediment sencer (assignació de registres global) o a través de límits de funció travessats mitjançant un gràfic de crides (assignació de registres interprocedimental). Quan es fa per funció o procediment, la convenció de crida pot requerir la inserció de desar/restaurar al voltant de cada lloc de crida.
Context Principi Diferent nombre de registres d'ús general en les arquitectures més comunes Arquitectura32 bits64 bitsARM1531Intel x86816MIPS3232POWER/PowerPC3232RISC-V15/3115/31SPARC3131 En molts llenguatges de programació, el programador pot utilitzar qualsevol nombre de variables. L'ordinador pot llegir i escriure registres a la CPU ràpidament, de manera que el programa informàtic s'executa més ràpid quan hi pot haver més variables als registres de la CPU. A més, de vegades l'accés al codi als registres és més compacte, de manera que el codi és més petit i es pot obtenir més ràpidament si utilitza registres en lloc de memòria. Tanmateix, el nombre de registres és limitat. Per tant, quan el compilador tradueix codi a llenguatge màquina, ha de decidir com assignar variables al nombre limitat de registres de la CPU.
No totes les variables estan en ús (o "actives") alhora, de manera que, durant la vida útil d'un programa, un registre determinat es pot utilitzar per contenir diferents variables. Tanmateix, dues variables en ús alhora no es poden assignar al mateix registre sense corrompre una de les variables. Si no hi ha prou registres per contenir totes les variables, algunes variables es poden moure cap a la RAM i des de la RAM. Aquest procés s'anomena "vessament" dels registres. Durant la vida útil d'un programa, una variable es pot vessar i emmagatzemar en registres: aquesta variable es considera llavors com a "dividida". Accedir a la RAM és significativament més lent que accedir als registres i, per tant, un programa compilat s'executa més lentament. Per tant, un compilador optimitzador pretén assignar tantes variables com sigui possible als registres. Una "pressió de registre" alta és un terme tècnic que significa que calen més vessaments i recàrregues; Braun et al. la defineixen com "el nombre de variables simultàniament actives en una instrucció".
A més, alguns dissenys d'ordinadors emmagatzemen a la memòria cau els registres d'accés freqüent. Per tant, els programes es poden optimitzar encara més assignant el mateix registre a una font i destinació d'una instrucció move sempre que sigui possible. Això és especialment important si el compilador utilitza una representació intermèdia com ara la forma d'assignació única estàtica (SSA). En particular, quan SSA no està completament optimitzat, pot generar artificialment instruccions move addicionals.
Components de l'assignació de registres L'assignació de registres consisteix, per tant, a triar on emmagatzemar les variables en temps d'execució, és a dir, dins o fora dels registres. Si la variable s'ha d'emmagatzemar en registres, l'assignador ha de determinar en quin(s) registre(s) s'emmagatzemarà aquesta variable. Finalment, un altre repte és determinar la durada durant la qual una variable ha de romandre a la mateixa ubicació.
Un assignador de registre, independentment de l'estratègia d'assignació escollida, pot confiar en un conjunt d'accions bàsiques per abordar aquests reptes. Aquestes accions es poden agrupar en diverses categories diferents:
Inserció de moviments Aquesta acció consisteix a augmentar el nombre d'instruccions de moviment entre registres, és a dir, fer que una variable visqui en diferents registres durant la seva vida útil, en lloc d'un. Això passa en l'enfocament de rang de vida dividit. Vessament Aquesta acció consisteix a emmagatzemar una variable a la memòria (emmagatzematge primari com la RAM) en lloc de registres. Tasca Aquesta acció consisteix a assignar un registre a una variable. Coalescència Aquesta acció consisteix a limitar el nombre de moviments entre registres, limitant així el nombre total d'instruccions. Per exemple, identificant una variable en directe a través de diferents mètodes i emmagatzemant-la en un sol registre durant tota la seva vida útil.
Molts enfocaments d'assignació de registres optimitzen per a una o més categories específiques d'accions. miniatura|300x300px|Registres Intel 386
Problemes comuns plantejats en l'assignació de registres L'assignació de registres planteja diversos problemes que es poden abordar (o evitar) mitjançant diferents enfocaments d'assignació de registres. Tres dels problemes més comuns s'identifiquen a continuació:
Àlies En algunes arquitectures, assignar un valor a un registre pot afectar el valor d'un altre: això s'anomena aliasing. Per exemple, l'arquitectura x86 té quatre registres de 32 bits d'ús general que també es poden utilitzar com a registres de 16 bits o 8 bits. En aquest cas, assignar un valor de 32 bits al registre eax afectarà el valor del registre al.
Precoloració Aquest problema és un acte per forçar l'assignació d'algunes variables a registres particulars. Per exemple, en les convencions de crida de PowerPC, els paràmetres es passen habitualment a R3-R10 i el valor de retorn es passa a R3.
Problema NP Chaitin et al. van demostrar que l'assignació òptima de registres és un problema NP-complet. Aquesta NP-completitud depèn completament de com està estructurat exactament el problema. S'ha demostrat que per a programes en forma SSA, la part de coloració de grafs del problema d'assignació de registres es pot resoldre en temps lineal. Què fa que el problema general de coloració de grafs sigui NP-complet i què fa que algunes versions del problema d'assignació de registres siguin NP-complets són diferents.
Tècniques d'assignació de registres L'assignació de registres pot tenir lloc sobre un bloc bàsic de codi: es diu que és "local", i va ser esmentat per primera vegada per Horwitz et al. Com que els blocs bàsics no contenen branques, es creu que el procés d'assignació és ràpid, perquè la gestió dels punts de fusió del gràfic de flux de control en l'assignació de registres es revela. una operació que requereix molt de temps. Tanmateix, es creu que aquest enfocament no produeix un codi tan optimitzat com l'enfocament "global", que opera sobre tota la unitat de compilació (un mètode o procediment, per exemple).
Assignació de coloració de gràfics L'assignació per coloració de grafs és l'enfocament predominant per resoldre l'assignació de registres. Va ser proposada per primera vegada per Chaitin et al. En aquest enfocament, els nodes del graf representen rangs actius (variables, temporals, registres virtuals/simbòlics) que són candidats per a l'assignació de registres. Les arestes connecten rangs actius que interfereixen, és a dir, rangs actius que estan simultàniament actius en almenys un punt del programa. L'assignació de registres es redueix al problema de coloració de grafs en què els colors (registres) s'assignen als nodes de manera que dos nodes connectats per una aresta no reben el mateix color.
Mitjançant l'anàlisi de vida, es pot construir un gràfic d'interferències. El gràfic d'interferències, que és un gràfic d'intervals on els nodes són les variables del programa, s'utilitza per modelar quines variables no es poden assignar al mateix registre.
Principi Les fases principals d'un assignador de registres de coloració de grafs a l'estil de Chaitin són: miniatura|700x700px|Assignador de registres basat en la coloració iterativa de grafs de Chaitin et al.
Renumerar : descobreix informació de rang en directe al programa font. Construir: construir el gràfic d'interferència. Coalesce: fusiona els rangs en directe de variables no interferents relacionades per instruccions de còpia. Cost de vessament: calcula el cost de vessament de cada variable. Això avalua l'impacte de mapejar una variable a la memòria sobre la velocitat del programa final. Simplifica: construeix un ordre dels nodes en el graf d'inferències Codi de vessament: inserir instruccions de vessament, és a dir, carregar i emmagatzemar per commutar valors entre registres i memòria. Selecciona: assigna un registre a cada variable.
Inconvenients i millores addicionals L'assignació de coloració de grafs té tres inconvenients principals. Primer, es basa en la coloració de grafs, que és un problema NP-complet, per decidir quines variables es vessen. Tot i que trobar una coloració mínima per a grafs generals és, de fet, un problema NP-complet, la coloració mínima dels grafs d'intervals (inclosos els grafs d'interferència) es pot fer en temps lineal (vegeu l'escaneig lineal a continuació); Per tant, aquesta tècnica no utilitza completament els supòsits del problema. En segon lloc, tret que s'utilitzi la divisió de rang en directe, les variables desallotjades es vessen a tot arreu: les instruccions d'emmagatzematge s'insereixen tan aviat com sigui possible, és a dir, just després de les definicions de variables; les instruccions de càrrega s'insereixen respectivament tard, just abans de l'ús de la variable. En tercer lloc, una variable que no es vessa es manté al mateix registre durant tota la seva vida útil.
D'altra banda, un únic nom de registre pot aparèixer en diverses classes de registres, on una classe és un conjunt de noms de registre que són intercanviables en un rol concret. Aleshores, diversos noms de registre poden ser àlies per a un únic registre de maquinari. Finalment, la coloració de grafs és una tècnica agressiva per assignar registres, però és computacionalment costosa a causa del seu ús del graf d'interferència, que pot tenir una mida en el pitjor dels casos que és quadràtica en el nombre de rangs en directe. La formulació tradicional de l'assignació de registres per coloració de grafs assumeix implícitament un únic banc de registres d'ús general que no se superposen i no gestiona característiques arquitectòniques irregulars com ara parells de registres superposats, registres d'ús especial i múltiples bancs de registres.
Briggs et al. van trobar una millora posterior de l'enfocament de coloració de gràfics a l'estil de Chaitin: s'anomena coalescència conservativa. Aquesta millora afegeix un criteri per decidir quan es poden fusionar dos rangs en directe. Principalment, a més dels requisits de no interferències, dues variables només es poden fusionar si la seva fusió no causarà més vessaments. Briggs et al. introdueixen una segona millora als treballs de Chaitin, que és la coloració esbiaixada. La coloració esbiaixada intenta assignar el mateix color a la coloració del gràfic al rang en directe que està relacionat amb la còpia.
Escaneig lineal L'escaneig lineal és un altre enfocament d'assignació de registres globals. Va ser proposat per primera vegada per Poletto et al. el 1999. En aquest enfocament, el codi no es converteix en un gràfic. En canvi, totes les variables s'escanegen linealment per determinar el seu rang en directe, representat com un interval. Un cop s'han calculat els rangs en directe de totes les variables, els intervals es recorren cronològicament. Tot i que aquest recorregut podria ajudar a identificar variables els rangs en directe de les quals interfereixen, no es construeix cap gràfic d'interferència i les variables s'assignen de manera cobdiciosa.