Analyse syntaxique - Page 3

Brunni (./59) :
Ca c'est sûr, j'aimerais bien savoir le faire ^^
D'ailleurs il ressemble à quoi?

RISC 16 bits, chaque instruction est conditionnée par 3 bits (mais 8 conditions, ça fait peu ), il y a 5 bits pour le code d'instruction (32 au total), 1 bit signale si le SR est mis à jour, et 7 bits sont utilisés numéroter les registres (on a un processeur de type 1 adresse)

Flanker (./61) :

Brunni (./59) :
Ca c'est sûr, j'aimerais bien savoir le faire ^^
D'ailleurs il ressemble à quoi?

RISC 16 bits, chaque instruction est conditionnée par 3 bits (mais 8 conditions, ça fait peu ), il y a 5 bits pour le code d'instruction (32 au total), 1 bit signale si le SR est mis à jour, et 7 bits sont utilisés numéroter les registres (on a un processeur de type 1 adresse)

marrant tu (enfin est-ce toi qui a fait cet exo a la base?) a un CPU qui reprend des principes de l'ARM ^^

oui carrément, c'est même plus que de l'inspiration là

Godzil (./62) :

Flanker (./61) :

Brunni (./59) :
Ca c'est sûr, j'aimerais bien savoir le faire ^^
D'ailleurs il ressemble à quoi?

RISC 16 bits, chaque instruction est conditionnée par 3 bits (mais 8 conditions, ça fait peu ), il y a 5 bits pour le code d'instruction (32 au total), 1 bit signale si le SR est mis à jour, et 7 bits sont utilisés numéroter les registres (on a un processeur de type 1 adresse)

marrant tu (enfin est-ce toi qui a fait cet exo a la base?) a un CPU qui reprend des principes de l'ARM ^^

Non, ce sont les élèves qui ont décidé de l'assembleur ^^ (bon, ok, un peu influencés )
c'était une des possibilités, et c'est vrai que ça aidait pas mal

Flanker (./61) :
7 bits sont utilisés numéroter les registres (on a un processeur de type 1 adresse)

Hmm je comprends pas cette partie... les registres source/dest? Y a pas de zone pour la constante? Et c'est quoi un processeur de type 1 adresse?
Sinon t'as carrément des bits de statut?
En tous cas le mien n'a rien de tout ça, il ressemble plus à un MIPS downgradé en fait. Il est d'ailleurs pas super performant, des fois je me dis que j'aurais dû faire à la THUMB: 3 opérandes avec accès seulement aux 8 premiers registres, et pour les autres on les utilise comme une "pile" rapide avec une instruction dédiée. Ou alors peut être en ayant plusieurs jeux de registres... mais il en faudrait toujours qui soient fixes (pc et at au moins, après on peut discuter sur lr et sp), du coup on est limité
Je viens de voir que sur un autre forum où j'ai posté mon truc (ici) y a un type qui s'est amusé avec, en plus avec la release où le CPU était à 8 kHz. Ca n'a pas l'air de fonctionner si mal en fait, il a fait plein de macros et tout, il a pas dû s'amuser

$main
BLDCTL_OR(BLDCTL_NONE) ; configure le blending
BG0CTL_OR(BGXCTL_MODE(0) | BGXCTL_MAPBASEBLOCK(0) | BGXCTL_CHARBASEBLOCK(0)) ; configure BG0
DISPCTL_OR(DISPCTL_BG0_ENABLE) ; active BG0

Une question: c'est dur d'implémenter un CPU comme celui que tu as fait sur une FPGA?
(par dur j'entends pour qqn qui a des bases comme moi en info mais à peu près aucun souvenir de VHDL)
Et tu pourrais faire tourner un tel CPU à quelle vitesse?

Brunni (./65) :

Flanker (./61) :
7 bits sont utilisés numéroter les registres (on a un processeur de type 1 adresse)

Hmm je comprends pas cette partie... les registres source/dest? Y a pas de zone pour la constante? Et c'est quoi un processeur de type 1 adresse?
Sinon t'as carrément des bits de statut?
En tous cas le mien n'a rien de tout ça, il ressemble plus à un MIPS downgradé en fait. Il est d'ailleurs pas super performant, des fois je me dis que j'aurais dû faire à la THUMB: 3 opérandes avec accès seulement aux 8 premiers registres, et pour les autres on les utilise comme une "pile" rapide avec une instruction dédiée. Ou alors peut être en ayant plusieurs jeux de registres... mais il en faudrait toujours qui soient fixes (pc et at au moins, après on peut discuter sur lr et sp), du coup on est limité
Je viens de voir que sur un autre forum où j'ai posté mon truc (ici) y a un type qui s'est amusé avec, en plus avec la release où le CPU était à 8 kHz. Ca n'a pas l'air de fonctionner si mal en fait, il a fait plein de macros et tout, il a pas dû s'amuser

$main
BLDCTL_OR(BLDCTL_NONE) ; configure le blending
BG0CTL_OR(BGXCTL_MODE(0) | BGXCTL_MAPBASEBLOCK(0) | BGXCTL_CHARBASEBLOCK(0)) ; configure BG0
DISPCTL_OR(DISPCTL_BG0_ENABLE) ; active BG0

Une question: c'est dur d'implémenter un CPU comme celui que tu as fait sur une FPGA?
(par dur j'entends pour qqn qui a des bases comme moi en info mais à peu près aucun souvenir de VHDL)
Et tu pourrais faire tourner un tel CPU à quelle vitesse?

sur un fpga t'es pas obligé de coder en vhdl... y'a plein de langages possibles (dont une grosse partie scriptés)

Brunni (./65) :
Hmm je comprends pas cette partie... les registres source/dest? Y a pas de zone pour la constante? Et c'est quoi un processeur de type 1 adresse?

Un processeur 1 adresse, c'est que les opérations ne précisent qu'une seule opérande. Pour les opérations binaires, l'autre opérande est dans un registre fixe.

Sinon t'as carrément des bits de statut?

Il y a un registre de statut, oui

Une question: c'est dur d'implémenter un CPU comme celui que tu as fait sur une FPGA?
(par dur j'entends pour qqn qui a des bases comme moi en info mais à peu près aucun souvenir de VHDL)
Et tu pourrais faire tourner un tel CPU à quelle vitesse?

Je n'ai pas trop touché à la partie FPGA, on était 2 chargés de TD, et l'autre maîtrisait bien le VHDL

Flanker (./67) :

Brunni (./65) :
Hmm je comprends pas cette partie... les registres source/dest? Y a pas de zone pour la constante? Et c'est quoi un processeur de type 1 adresse?

Un processeur 1 adresse, c'est que les opérations ne précisent qu'une seule opérande. Pour les opérations binaires, l'autre opérande est dans un registre fixe.

Ok ben j'ai bien fait de demander, là comme ça je pensais à une machine à pile mais y en a qd même qui ont besoin d'opérandes ^^
Sinon rien à voir, ptet que qqn s'y connait ici mais il existe des algos / tutos pour la génération de code depuis une machine à pile? Enfin j'entends pas la bête génération de code toute dégueulasse genre:

; a := b + c
; LOAD c
  ld r0, :c
  push r0
; LOAD b
  ld r0, :b
  push r0
; ADD
  pop r0, r1
  add r0, r1
  push r0
; STORE a
  pop r0
  st r0, :a

En d'autres termes un algo de conversion machine à pile -> machine à registre plus efficace que ça?

il faut faire un allocateur de registre mais je sais pas si le code sera meilleur

Je crois que l'attribution des registres se fait à l'aide d'un algo de coloration de graphe. n couleurs représentent n registres et les liens entre les nœuds représentent les dépendances.


J'avais étudié à l'époque l'algo 'Strahler number'.

tiens intéressant ça.
donc en entrée de l'algo t'as une liste d'affectations, et en sortie les registres à utiliser pour chaque symbole?

et on colore comment?

plus précisément en entrée tu as un graphe d'interférence que tu cherches à colorier avec k couleurs
manque de pot le problème est NP complet
du coup, il y a des tonnes (j'exagère peut être là) d'heuristiques qui ont été pondues pour quand même essayer de résoudre ce problème
va faire un petit tour sur wikipedia ou google, tu devrais trouver des choses à "allocation de registres" ou "coloriage/coloration de graphes"

c'est surtout l'algo de création de ce graphe qui m'intéresse
(le coloriage, je sais ce que c'est ^)

La méthode la plus naïve de construction est de parcourir chaque ligne et de se poser les questions suivantes :
- Quelles sont les variables qui sont modifiées après l'exécution de cette ligne (nœuds de départs).
- Quelles sont les variables que j'ai besoins pour réaliser l'opération (nœuds d'arrivés (dépendances)).
A savoir que le graphe n'est pas orienté.

La construction du graphe est assez simple en soit, le plus lourd c'est le calcul des couleurs qui n'est pas forcément optimal suivant l'algo choisi. L'algo de Welsh-Powel serait soit dit en passant suffisante mais comme dit précédemment n'assure pas une coloration optimal.
Ainsi, chaque couleur représente un registre. Si le nombre de couleur dépasse le nombre de registre de la machine, l'utilisation de la pile est nécessaire sauf si on augmente de façon virtuelle le nombre de registres. Par exemple partitionner un registre de 32 bits en 2 registres de 16 bits mais cela nécessite l'ajout d'instructions.

Mais une optimisation optimale est lié au ré ordonnancement des instructions. L'allocation des registres n'est pas suffisant en soit.

Ah oui sur un code conséquent, il risque d'y avoir énormément de nœuds (de variables) et donc l'algo de coloration risque d'être gourant en calculs (NP complet). L'idée est donc lors de la création du graphe d'essayer de minimiser le nombre de variables par prédiction. C'est-à-dire pondérer les nœuds avec une ancienneté. Un noeud avec une anciennetée élevée (c'est-à-dire avec une affectation la plus ancienne) aura une plus faible probabilité d'être réutilisé à x lignes d'instructions plus lointaines.

La coloration de graphes est un des algorithmes possibles (ou plutôt une famille d'algorithmes, il y a plein de manières de colorer un graphe), ce n'est pas le seul.

Oui mais le calcul reste toujours NP-complet ?

Ah oui y a pas que la coloration de graphe pour réaliser une allocation de registres, il existe des algos génétiques http://aggregate.org/KYARCH/lcpc05-paper-37.pdf mais alors là je sais pas comment ça fonctionne.

d'après ce que j'ai compris on teste des réordonnancements d'instructions pour trouver la config qui améliore l'allocation, en calculant un "score" a chaque essai, en faisant des "mutations" de la config courante, puis on relance le programme et on cherche ce qui améliore le score.

je crois. peut être c'est ça.

Hmm je vois. Pour la coloration ça ok c'est un autre problème. A priori j'aurais tendance à tenter une heuristique SLS, faudrait voir ce que ça donne.
Mais concernant le graphe en lui même il faut donc créer un sommet pour toute variable (incluant les constantes au sens registre = constante) et ensuite relier d'un arc celles qui sont modifiées alors qu'une autre peut toujours être utilisée par la suite, c'est ça?
Ensuite si on trouve plus de n couleurs (pour n registres sur la machines) alors il faut commencer à déterminer quels registres peuvent être "lâchés" (dans le cas de constantes on peut les recharger facilement) ou poussés dans la pile (recalculer la valeur contenue prendrait plus de temps qu'empiler / désempiler ou bien aurait des effets de bord). C'est ça?
Après le réordonnancement ça je trouve bizarre de tout tester comme un bourrin, surtout qu'il y a une énormité de combinaisons possibles non?

squalyl (./78) :
d'après ce que j'ai compris on teste des réordonnancements d'instructions pour trouver la config qui améliore l'allocation, en calculant un "score" a chaque essai, en faisant des "mutations" de la config courante, puis on relance le programme et on cherche ce qui améliore le score.

je crois. peut être c'est ça.

Le réordonnancement du code est en soit une autre optimisation. Elle n'est pas indispensable pour faire une allocation de registres ?

Une autre idée, je ne sais pas si elle apporterait un gain sur d'autres optimisations ?
Pour le ré ordonnancement du code on créer cette fois un graphe de dépendance des lignes d'instructions. Connaissant les dépendances entres instructions, on en déduit des blocs ainsi que des optimisations. Sur un processeur avec pipeline c'est indispensable mais sur un processeur comme le 68000 ça permet juste de trouver une instruction ou un ensemble d'instructions capable de remplacer un bloc plus efficacement (moins de cycles). En gros l'idée est d'associer des modèles de code optimisés suivant un automate de succession d'instructions. Le réordonnancement sur 68000 n'apporterai pas grand chose je pense, c'est plutôt les optimisations combinatoires qui donneraient de meilleures résultats.

Je n'ai pas regardé l'algo génétique en détail mais bon une allocation de registres simple devrait déjà largement suffire surtout sur un 68000.

Brunni (./79) :
Hmm je vois. Pour la coloration ça ok c'est un autre problème. A priori j'aurais tendance à tenter une heuristique SLS, faudrait voir ce que ça donne.
Mais concernant le graphe en lui même il faut donc créer un sommet pour toute variable (incluant les constantes au sens registre = constante) et ensuite relier d'un arc celles qui sont modifiées alors qu'une autre peut toujours être utilisée par la suite, c'est ça?
Ensuite si on trouve plus de n couleurs (pour n registres sur la machines) alors il faut commencer à déterminer quels registres peuvent être "lâchés" (dans le cas de constantes on peut les recharger facilement) ou poussés dans la pile (recalculer la valeur contenue prendrait plus de temps qu'empiler / désempiler ou bien aurait des effets de bord). C'est ça?
Après le réordonnancement ça je trouve bizarre de tout tester comme un bourrin, surtout qu'il y a une énormité de combinaisons possibles non?

C'est l'allocation de registres qui va te donner les registres donc il ne faut pas (à mon avis) parler de registre avant l'application de l'algorithme d'allocation de registres (constante pour toi).
Les seules lignes d'instructions a analyser sont les lignes qui modifie une variable (par affectation ou autre).
Si la variable V modifiée existe déjà tu prend le nœud du graphe, sinon tu créer un nouveau nœud V.
Tu analyses la ligne afin de déterminer les dépendances (les variables S dont tu as besoin pour effectuer l'affectation). A chaque dépendance tu créer un arc entre V et S.

geogeo (./76) :
Oui mais le calcul reste toujours NP-complet ?

Il y a des heuristiques approximatives, comme d'habitude.

Mais il y a aussi d'autres algorithmes heuristiques pour l'allocation de registres qui ne passent pas par de la coloration de graphes (ni des algorithmes génétiques d'ailleurs, ça, c'est une technique très générale qui peut être utilisée pour pratiquement tout ce qui touche à l'optimisation (au sens mathématique, ce qui est aussi bien plus vaste comme domaine que l'optimisation de code!), donc forcément aussi ici, mais ce n'est pas la seule).

Typiquement, dans un premier temps le code est généré en utilisant des "variables temporaires" au lieu des registres de la machine (ie on suppose qu'on a en fait une infinité de registres).

Ensuite, il y a une analyse de durée de vie des temporaires qui permet de construire le graphe d'interférences.
La construction de ce graphe est assez simple:
- chaque instruction lit un ensemble de temporaires et écrit un ensemble de temporaires
- un temporaire est vivant s'il existe une instruction suivante dans le flot de controle qui le lit, sinon il est mort -> définition des intervalles de durée de vie
- le graphe a pour sommets les temporaires. une arete relie deux temporaires si leur intervalle de durée de vie se chevauche

Et après la coloration intervient.

Ca, c'est le schéma classique de génération de code tel qu'on l'enseigne à l'école (cf par exemple le Dragon book)
Mais évidemment, il y a surement d'autres approches.

Je crois me souvenir qu'il y a des cas où l'allocation se fait bien (ça parlait en vrac de chordal graphs, de SSA form, ...)