Compilador optimitzador

L'abast descriu quina part del codi d'entrada es considera per aplicar optimitzacions.

Les optimitzacions d'abast local utilitzen informació local a un bloc bàsic.^[4] Com que els blocs bàsics no contenen instruccions de flux de control, aquestes optimitzacions requereixen una anàlisi mínima, cosa que redueix els requisits de temps i emmagatzematge. Tanmateix, no es conserva cap informació entre salts.

Les optimitzacions d'abast global, també conegudes com a optimitzacions intraprocedimentals, operen sobre funcions individuals.^[5] Això els dóna més informació amb la qual treballar, però sovint fa que calguin càlculs costosos. Cal fer suposicions en el pitjor dels casos quan es produeixen crides de funcions o s'accedeix a variables globals, ja que hi ha poca informació disponible sobre elles.

Les optimitzacions de mirilla normalment es duen a terme al final del procés de compilació, després que s'hagi generat el codi màquina. Aquesta optimització examina unes quantes instruccions adjacents (de manera similar a "mirar el codi a través d'una mirilla") per veure si es poden substituir per una sola instrucció o per una seqüència d'instruccions més curta.:^[6] 554  Per exemple, una multiplicació d'un valor per dos es podria executar de manera més eficient desplaçant el valor a l'esquerra o sumant el valor a si mateix (aquest exemple també és un cas de reducció de força).

Les optimitzacions interprocedimentals analitzen tot el codi font d'un programa. Com més informació hi hagi disponible, més efectives poden ser les optimitzacions. La informació es pot utilitzar per a diverses optimitzacions, inclosa la funció inline, on una crida a una funció es substitueix per una còpia del cos de la funció.

L'optimització en temps d'enllaç (LTO), o optimització de tot el programa, és una classe més general d'optimització interprocedimental. Durant l'LTO, el compilador té visibilitat a través de les unitats de traducció, cosa que li permet realitzar optimitzacions més agressives com ara la integració entre mòduls i la desvirtualització.

L'optimització de codi màquina implica l'ús d'un optimitzador de codi objecte per analitzar el programa després que tot el codi màquina s'hagi enllaçat. Tècniques com la compressió de macros, que estalvien espai condensant seqüències d'instruccions comunes, es tornen més efectives quan tota la imatge de la tasca executable està disponible per a l'anàlisi.

La majoria dels llenguatges de programació d'alt nivell comparteixen construccions i abstraccions de programació comunes, com ara construccions de ramificació (if, switch), construccions de bucle (for, while) i construccions d'encapsulació (estructures, objectes). Per tant, es poden utilitzar tècniques d'optimització similars entre llenguatges. Tanmateix, certes característiques del llenguatge dificulten algunes optimitzacions. Per exemple, els punters en C i C++ dificulten l'optimització de matrius; vegeu anàlisi d'àlies. Tanmateix, llenguatges com PL/I que també admeten punters implementen optimitzacions per a matrius. Per contra, algunes característiques del llenguatge faciliten certes optimitzacions. Per exemple, en alguns llenguatges, les funcions no poden tenir efectes secundaris. Per tant, si un programa fa diverses crides a la mateixa funció amb els mateixos arguments, el compilador pot inferir que el resultat de la funció només s'ha de calcular una vegada. En llenguatges on es permet que les funcions tinguin efectes secundaris, el compilador pot restringir aquesta optimització a funcions que pot determinar que no tenen efectes secundaris.

Moltes optimitzacions que operen sobre conceptes de programació abstractes (bucles, objectes, estructures) són independents de la màquina a la qual es dirigeix el compilador, però moltes de les optimitzacions més efectives són les que millor exploten les característiques especials de la plataforma de destinació. Alguns exemples són les instruccions que fan diverses coses alhora, com ara decrementar el registre i fer una bifurcació si no és zero.

El següent és un exemple d'optimització dependent de la màquina local. Per establir un registre a 0, la manera òbvia és utilitzar la constant '0' en una instrucció que estableix un valor de registre a una constant. Una manera menys òbvia és fer una operació XOR d'un registre amb si mateix o restar-lo de si mateix. Depèn del compilador saber quina variant d'instrucció utilitzar. En moltes màquines RISC, ambdues instruccions serien igualment apropiades, ja que tindrien la mateixa longitud i trigarien el mateix temps. En molts altres microprocessadors com la família Intel x86, resulta que la variant XOR és més curta i probablement més ràpida, ja que no caldrà descodificar un operand immediat ni utilitzar el "registre d'operand immediat" intern; el mateix s'aplica a IBM System/360 i successors per a la variant de resta.^[7] Un problema potencial amb això és que l'operació XOR o la resta poden introduir una dependència de dades sobre el valor anterior del registre, provocant una aturada de la canonada, que es produeix quan el processador ha de retardar l'execució d'una instrucció perquè depèn del resultat d'una instrucció anterior. Tanmateix, els processadors sovint tracten el XOR d'un registre amb si mateix o la resta d'un registre de si mateix com un cas especial que no causa bloquejos.

L'optimització de bucles actua sobre les instruccions que formen un bucle, com ara un bucle for, per exemple, el moviment de codi invariant en bucles. Les optimitzacions de bucles poden tenir un impacte significatiu perquè molts programes passen un gran percentatge del seu temps dins de bucles.:^[10] 596 

Algunes tècniques d'optimització dissenyades principalment per operar en bucles inclouen:

Anàlisi de variables d'inducció

A grans trets, si una variable d'un bucle és una funció lineal simple de la variable d'índex, com ara j := 4*i + 1, es pot actualitzar adequadament cada vegada que es canvia la variable de bucle. Això és una reducció de força i també pot permetre que les definicions de la variable d'índex esdevinguin codi mort.:^[11] 596–598 Aquesta informació també és útil per a la comprovació de límits, l'eliminació i l'anàlisi de dependències, entre altres coses.

Fissió en bucle o distribució en bucle

La fissió de bucles intenta trencar un bucle en múltiples bucles sobre el mateix rang d'índex, on cada nou bucle només pren una part del cos del bucle original. Això pot millorar la localitat de la referència tant a les dades a les quals s'accedeix dins del bucle com al codi del cos del bucle.

Fusió de bucles o combinació de bucles o pissó de bucles o interferència de bucles

Una altra tècnica que intenta reduir la sobrecàrrega del bucle. Quan dos bucles adjacents iterarien el mateix nombre de vegades independentment de si aquest nombre es coneix o no en temps de compilació, els seus cossos es poden combinar sempre que no facin referència a les dades de l'altre.

Inversió de bucle

Aquesta tècnica canvia un bucle while estàndard en un bucle do/while (també conegut com a repeat/until) embolicat en un condicional if, reduint el nombre de salts en dos, per als casos en què s'executa el bucle. Fer-ho duplica la comprovació de la condició (augmentant la mida del codi) però és més eficient perquè els salts solen provocar una aturada del pipeline. A més, si la condició inicial es coneix en temps de compilació i se sap que no té efectes secundaris, es pot ometre la protecció if.

Intercanvi de bucle

Aquestes optimitzacions intercanvien bucles interns amb bucles externs. Quan les variables del bucle s'indexen en una matriu, aquesta transformació pot millorar la localitat de la referència, depenent de la disposició de la matriu.

Moviment de codi invariant en bucle

Si una quantitat es calcula dins d'un bucle durant cada iteració, i el seu valor és el mateix per a cada iteració, es pot millorar enormement l'eficiència si es treu fora del bucle i es calcula el seu valor només una vegada abans que comenci el bucle.:^[12] 596  Això és particularment important amb les expressions de càlcul d'adreces generades per bucles sobre matrius. Per a una implementació correcta, aquesta tècnica s'ha d'utilitzar amb inversió de bucle, perquè no tot el codi és segur per ser aixecat fora del bucle.

Optimització del niu de bucles

Alguns algoritmes omnipresents com la multiplicació de matrius tenen un comportament de memòria cau molt deficient i accessos excessius a memòria. L'optimització del niu de bucles augmenta el nombre de visites a la memòria cau operant sobre blocs petits i utilitzant un intercanvi de bucles.

Inversió de bucle

La inversió de bucles inverteix l'ordre en què s'assignen els valors a la variable d'índex. Aquesta és una optimització subtil que pot ajudar a eliminar dependències i, per tant, permetre altres optimitzacions. A més, en algunes arquitectures, la inversió de bucles contribueix a un codi més petit, ja que quan es decrementa l'índex del bucle, la condició que s'ha de complir perquè el programa en execució surti del bucle és una comparació amb zero. Sovint es tracta d'una instrucció especial sense paràmetres, a diferència d'una comparació amb un nombre, que necessita el nombre amb què comparar-se. Per tant, la quantitat de bytes necessaris per emmagatzemar el paràmetre s'estalvia mitjançant la inversió de bucles. A més, si el nombre de comparació supera la mida de la paraula de la plataforma, en l'ordre estàndard dels bucles, caldrien executar diverses instruccions per avaluar la comparació, cosa que no passa amb la inversió de bucles.

Desenrotllament del bucle

Desplegar duplica el cos del bucle diverses vegades per disminuir el nombre de vegades que es prova la condició del bucle i el nombre de salts; les proves i els salts poden afectar el rendiment deteriorant la cadena d'instruccions. Una optimització de "menys salts". Desplegar completament un bucle elimina tota la sobrecàrrega, però requereix que el nombre d'iteracions es conegui en temps de compilació.

Divisió de bucles

La divisió de bucles intenta simplificar un bucle o eliminar dependències dividint-lo en diversos bucles que tenen els mateixos cossos però que iteren sobre diferents porcions contigües del rang d'índex. Un cas especial útil és el "loop peeling", que pot simplificar un bucle amb una primera iteració problemàtica realitzant aquesta iteració per separat abans d'entrar al bucle.

Desconnexió del bucle

En desactivar la commutació, es mou un condicional de dins d'un bucle a fora del bucle duplicant el cos del bucle dins de cadascuna de les clàusules if i else del condicional.

Canalització de programari

El bucle es reestructura de manera que el treball realitzat en una iteració es divideix en diverses parts i es fa al llarg de diverses iteracions. En un bucle ajustat, aquesta tècnica amaga la latència entre la càrrega i l'ús de valors.

Paral·lelització automàtica

Un bucle es converteix en codi multifil o vectoritzat (o fins i tot tots dos) per utilitzar diversos processadors simultàniament en una màquina multiprocessador de memòria compartida (SMP), incloses les màquines multinucli.

Les optimitzacions d'emmagatzematge premonitòries permeten que les operacions d'emmagatzematge es produeixin abans del que es permetria en el context de fils i bloquejos. El procés necessita alguna manera de saber per endavant quin valor emmagatzemarà l'assignació que hauria d'haver seguit. L'objectiu d'aquesta relaxació és permetre que l'optimització del compilador realitzi certs tipus de reordenaments de codi que preservin la semàntica dels programes correctament sincronitzats.^[13]

Les optimitzacions del flux de dades, basades en l'anàlisi del flux de dades, depenen principalment de com certes propietats de les dades es propaguen per les vores de control del graf del flux de control. Algunes d'aquestes inclouen:

Eliminació comuna de subexpressions

En l'expressió (a + b) - (a + b)/4, la "subexpressió comuna" fa referència a la (a + b) duplicada. Els compiladors que implementen aquesta tècnica s'adonen que (a + b) no canviarà i, per tant, només calculen el seu valor una vegada.:^[14] 592–594

Plegament i propagació constants

Substitució d'expressions que consisteixen en constants (per exemple, 3 + 5 ) pel seu valor final ( 8 ) en temps de compilació, en lloc de fer el càlcul en temps d'execució.^[15] S'utilitza a la majoria de llenguatges moderns.

Reconeixement i eliminació de variables d'inducció

Vegeu la discussió anterior sobre l'anàlisi de variables d'inducció

Classificació d'àlies i anàlisi de punters

En presència de punters, és difícil fer cap optimització, ja que potencialment qualsevol variable pot haver estat modificada quan s'assigna una ubicació de memòria. En especificar quins punters poden fer d'àlies de quines variables, es poden ignorar els punters no relacionats.

Eliminació de botigues mortes

Eliminació d'assignacions a variables que no es llegeixen posteriorment, ja sigui perquè finalitza el període de vida de la variable o a causa d'una assignació posterior que sobreescriurà el primer valor.

Aquestes optimitzacions estan pensades per fer-se després de transformar el programa en una forma especial anomenada forma estàtica d'assignació única, en què cada variable s'assigna en un sol lloc. Tot i que algunes funcionen sense SSA, són més efectives amb SSA. Moltes optimitzacions enumerades en altres seccions també es beneficien sense canvis especials, com ara l'assignació de registres.

Numeració de valors globals

El GVN elimina la redundància construint un gràfic de valors del programa i, a continuació, determinant quins valors es calculen mitjançant expressions equivalents. El GVN pot identificar alguna redundància que l'eliminació comuna de subexpressions no pot, i viceversa.

Propagació constant condicional dispersa

Combina la propagació constant, el plegament constant i l'eliminació de codi mort, i millora el que és possible executant-los per separat.^[16][17] Aquesta optimització executa simbòlicament el programa, propagant simultàniament valors constants i eliminant parts del gràfic de flux de control que això fa inabastables.

Assignació de registres

Les variables més utilitzades s'han de mantenir als registres del processador per a un accés més ràpid. Per trobar quines variables posar als registres, es crea un graf d'interferència. Cada variable és un vèrtex i quan s'utilitzen dues variables alhora (tenen un rang de temps que s'interseca) tenen una aresta entre elles. Aquest graf es acoloreix utilitzant, per exemple, l'algorisme de Chaitin amb el mateix nombre de colors com registres hi ha. Si la coloració falla, una variable es "vessa" a la memòria i es torna a intentar la coloració.

Selecció d'instruccions

La majoria d'arquitectures, en particular les arquitectures CISC i les que tenen molts modes d'adreçament, ofereixen diverses maneres de realitzar una operació concreta, utilitzant seqüències d'instruccions completament diferents. La tasca del selector d'instruccions és fer una bona feina en general triant quines instruccions implementar quins operadors en la representació intermèdia de baix nivell. Per exemple, en molts processadors de la família 68000 i l'arquitectura x86, es poden utilitzar modes d'adreçament complexos en sentències com ara lea 25(a1,d5*4), a0, permetent que una sola instrucció realitzi una quantitat significativa d'aritmètica amb menys emmagatzematge.

Planificació d'instruccions

La planificació d'instruccions és una optimització important per als processadors moderns en pipeline, que evita bloquejos o bombolles en el pipeline agrupant instruccions sense dependències, alhora que té cura de preservar la semàntica original.

Rematerialització

La rematerialització recalcula un valor en comptes de carregar-lo des de la memòria, eliminant un accés a la memòria. Això es realitza conjuntament amb l'assignació de registres per evitar vessaments.

Factorització de codi

Si diverses seqüències de codi són idèntiques, o es poden parametritzar o reordenar per ser idèntiques, es poden substituir per crides a una subrutina compartida. Això sovint pot compartir codi per a la configuració de subrutines i, de vegades, recursivitat final.^[18]

Trampolins

Molts Les CPU tenen instruccions de crida de subrutines més petites per accedir a poca memòria. Un compilador pot estalviar espai utilitzant aquestes petites crides al cos principal del codi. Les instruccions de salt amb poca memòria poden accedir a les rutines a qualsevol adreça. Això multiplica l'estalvi d'espai derivat de la factorització de codi.^[18]

Reordenació de càlculs

Basats en la programació lineal entera, els compiladors reestructurants milloren la localitat de les dades i exposen més paral·lelisme reordenant els càlculs. Els compiladors que optimitzen l'espai poden reordenar el codi per allargar les seqüències que es poden factoritzar en subrutines.

Tot i que molts d'aquests també s'apliquen a llenguatges no funcionals, o bé s'originen o bé són particularment crítics en llenguatges funcionals com ara Lisp i ML.

Optimització de trucades finals

Una crida de funció consumeix espai de pila i implica una certa sobrecàrrega relacionada amb el pas de paràmetres i el buidatge de la memòria cau d'instruccions. Els algoritmes recursius de cua es poden convertir en iteració mitjançant un procés anomenat eliminació de recursió de cua o optimització de crida de cua.

Desforestació (fusió d'estructures de dades )

En els llenguatges on és comú aplicar una seqüència de transformacions a una llista, la desforestació intenta eliminar la construcció d'estructures de dades intermèdies.

Avaluació parcial

Els càlculs que produeixen la mateixa sortida independentment de l'entrada dinàmica en temps d'execució es poden avaluar en temps de compilació.

Eliminació de comprovació de límits

Molts llenguatges, com ara Java, imposen la comprovació de límits a tots els accessos a matrius. Això és un coll d'ampolla important en certes aplicacions com ara el codi científic. L'eliminació de la comprovació de límits permet al compilador eliminar de manera segura la comprovació de límits en moltes situacions on pot determinar que l'índex ha de caure dins dels límits vàlids; per exemple, si es tracta d'una variable de bucle simple.

Optimització del desplaçament de les bifurcacions (dependent de la màquina)

Trieu el desplaçament de la branca més curt que arribi a l'objectiu.

Reordenació de blocs de codi

La reordenació de blocs de codi altera l'ordre dels blocs bàsics d'un programa per reduir les branques condicionals i millorar la localitat de referència.

Eliminació de codi mort

Elimina les instruccions que no afectaran el comportament del programa, per exemple, les definicions que no tenen cap utilitat, anomenades codi mort. Això redueix la mida del codi i elimina els càlculs innecessaris.

Factorització d'invariants (invariants de bucle)

Si una expressió s'executa tant quan es compleix una condició com quan no es compleix, es pot escriure només una vegada fora de l'instrucció condicional. De la mateixa manera, si certs tipus d'expressions (per exemple, l'assignació d'una constant a una variable) apareixen dins d'un bucle, es poden treure'n perquè el seu efecte serà el mateix independentment de si s'executen moltes vegades o només una vegada. Això també es coneix com a eliminació de redundància total. Una optimització similar però més potent és l'eliminació de redundància parcial (PRE).

Expansió en línia o expansió macro

Quan algun codi invoca un procediment, és possible inserir directament el cos del procediment dins del codi que fa la crida en lloc de transferir-hi el control. Això estalvia la sobrecàrrega relacionada amb les crides de procediment, a més de proporcionar una oportunitat per a moltes optimitzacions específiques de paràmetres diferents, però té un cost d'espai; el cos del procediment es duplica cada vegada que el procediment es crida en línia. Generalment, l'inline és útil en codi crític de rendiment que fa un gran nombre de crides a procediments petits. Aquesta és una optimització de "menys salts". Les sentències dels llenguatges de programació imperatius també són un exemple d'aquesta optimització. Tot i que les sentències es podrien implementar amb crides de funció, gairebé sempre s'implementen amb codi inline.

Compressió de macros

Una optimització d'espai que reconeix seqüències comunes de codi, crea subprogrames ("macros de codi") que contenen el codi comú i substitueix les aparicions de les seqüències de codi comunes per crides als subprogrames corresponents. Això es fa de manera més efectiva com a optimització de codi màquina, quan tot el codi és present. La tècnica es va utilitzar per primera vegada per conservar espai en un flux de bytes interpretatiu utilitzat en una implementació de Macro Spitbol en microordinadors.^[19] Se sap que el problema de determinar un conjunt òptim de macros que minimitzi l'espai requerit per un segment de codi determinat és NP-complet, però les heurístiques eficients aconsegueixen resultats gairebé òptims.^[20]

Reducció de les col·lisions de la memòria cau

(p. ex., alterant l'alineació dins d'una pàgina)

Reducció de l'alçada de la pila

Reorganitzar un arbre d'expressions per minimitzar els recursos necessaris per a l'avaluació d'expressions.

Prova de reordenació

Si tenim dues proves que són la condició per a alguna cosa, primer podem tractar les proves més simples (per exemple, comparar una variable amb alguna cosa) i només després les proves complexes (per exemple, les que requereixen una crida de funció). Aquesta tècnica complementa l'avaluació mandrosa, però només es pot utilitzar quan les proves no depenen l'una de l'altra. El curtcircuit semàntic pot dificultar-ho.

L'optimització interprocedimental funciona en tot el programa, a través dels límits de procediments i fitxers. Funciona estretament amb les contraparts intraprocedimentals, realitzades amb la cooperació d'una part local i una part global. Les optimitzacions interprocedimentals típiques són l'inlineing de procediments, l'eliminació de codi mort interprocedimental, la propagació de constants interprocedimentals i la reordenació de procediments. Com és habitual, el compilador ha de realitzar una anàlisi interprocedimental abans de les seves optimitzacions reals. Les anàlisis interprocedimentals inclouen l'anàlisi d'àlies, l'anàlisi d'accés a matrius i la construcció d'un gràfic de crides.

L'optimització interprocedimental és habitual en els compiladors comercials moderns de SGI, Intel, Microsoft i Sun Microsystems. Durant molt de temps, el GCC de codi obert va ser criticat per la manca d'anàlisi i optimitzacions interprocedimentals potents, tot i que ara això està millorant.^[21] Un altre compilador de codi obert amb una infraestructura completa d'anàlisi i optimització és Open64.

A causa del temps i l'espai addicionals que requereix l'anàlisi interprocedimental, la majoria de compiladors no la realitzen per defecte. Els usuaris han d'utilitzar les opcions del compilador explícitament per indicar-li que activi l'anàlisi interprocedimental i altres optimitzacions costoses.