Sélection d'instruction - Instruction selection
En informatique , la sélection d'instructions est l'étape d'un backend de compilateur qui transforme sa représentation intermédiaire de niveau intermédiaire (IR) en une IR de bas niveau. Dans un compilateur typique, la sélection d'instructions précède à la fois l' ordonnancement d'instructions et l' allocation de registres ; par conséquent, son IR de sortie a un ensemble infini de pseudo-registres (souvent appelés temporaires ) et peut encore être - et est généralement - soumis à l' optimisation du judas . Sinon, il ressemble étroitement au code machine cible , au bytecode ou au langage d'assemblage .
Par exemple, pour la séquence suivante de code IR de niveau intermédiaire
t1 = a t2 = b t3 = t1 + t2 a = t3 b = t1
une bonne séquence d'instructions pour l' architecture x86 est
MOV EAX, a
XCHG EAX, b
ADD a, EAX
Pour une enquête complète sur la sélection des instructions, voir.
Expansion macro
L'approche la plus simple de la sélection d'instructions est connue sous le nom d' expansion de macro ou de génération de code interprétatif . Un sélecteur d'instructions à macro-expansion fonctionne en faisant correspondre des modèles sur l'IR de niveau intermédiaire. Lors d'une correspondance, la macro correspondante est exécutée, en utilisant la partie correspondante de l'IR comme entrée, qui émet les instructions cibles appropriées. L'expansion macro peut être effectuée soit directement sur la représentation textuelle de l'IR de niveau intermédiaire, soit l'IR peut d'abord être transformée en une représentation graphique qui est ensuite parcourue en profondeur d'abord. Dans ce dernier, un modèle correspond à un ou plusieurs nœuds adjacents dans le graphique.
À moins que la machine cible ne soit très simple, l'expansion de macros isolément génère généralement du code inefficace. Pour atténuer cette limitation, les compilateurs qui appliquent cette approche la combinent généralement avec l' optimisation du judas pour remplacer les combinaisons d'instructions simples par des équivalents plus complexes qui augmentent les performances et réduisent la taille du code. Ceci est connu sous le nom d' approche Davidson-Fraser et est actuellement appliqué dans GCC .
Couverture graphique
Une autre approche consiste à d'abord transformer l'IR de niveau intermédiaire en une représentation graphique, puis à couvrir le graphique à l'aide de motifs . Un modèle est un modèle qui correspond à une partie du graphique et peut être implémenté avec une seule instruction fournie par la machine cible. Le but est de couvrir le graphique de telle sorte que le coût total des modèles sélectionnés soit minimisé, le coût représentant généralement le nombre de cycles nécessaires pour exécuter l'instruction. Pour les graphiques en forme d'arbre, la couverture la moins coûteuse peut être trouvée en temps linéaire en utilisant la programmation dynamique , mais pour les DAG et les graphiques à part entière, le problème devient NP-complet et est donc le plus souvent résolu à l'aide d' algorithmes gourmands ou de méthodes d'optimisation combinatoire .
Stratégie du plus petit dénominateur commun
La stratégie du plus petit dénominateur commun est une technique de sélection d'instructions utilisée sur des plates-formes où des instructions supplémentaires de processeur existent pour rendre les programmes exécutables portables sur une large gamme d'ordinateurs. Dans le cadre d'une stratégie au plus petit dénominateur commun, le comportement par défaut du compilateur est de construire pour l'architecture commune la plus basse. L'utilisation de toute extension de processeur disponible est désactivée par défaut, sauf si elle est explicitement activée par des commutateurs de ligne de commande.
L'utilisation d'une stratégie au plus petit dénominateur commun signifie que les instructions et capacités supplémentaires du processeur ne sont pas utilisées par défaut.