Forum de Ti-Gen.org, le site francophone des TI

Bienvenue Invité ! Se connecter Mes sujets	Administrer
Utilisateurs actifs : Aucun membre + 1 visiteur

Avant de poster sur le forum, il y a des régles de bases à respecter pour une bonne entente et un respect de tous.
Veuillez lire la charte du forum.

:: Index » Forum TI-Nspire » Algorithmie et optimisation » Écrire un assembleur pour les futurs experts (8 réponse(s))

./POST DE DEPART (post n°0) Marquer comme non lu.

Kevin Kofler

Ecrit le: Mercredi 26 juillet 2006 à 01:27

Administrateur

Groupe: Staff de Ti-Gen

Messages: 4813

Membre n°40

Inscrit le 08 février 2004

En réponse à "Ecrire un assembleur pour les noobs" de GoldenCrystal...

1. Voir s'il n'y a pas un assembleur existant qui convient.

Avant de réinventer la roue, il faut voir s'il n'y a pas un assembleur déjà existant qu'on pourrait adapter, par exemple GNU as: http://sources.redhat.com/binutils/. GNU as permet même de rajouter un CPU complètement nouveau tout en utilisant l'infrastructure existante. Si l'assembleur existant n'est pas GNU, attention aux licences, certaines interdisent des trucs comme l'usage commercial ou la modification et rendent donc le logiciel non-libre.

2. Préparatifs

Choisir un langage de programmation et récupérer une liste d'instructions du CPU ne font pas vraiment partie du développement de l'assembleur, donc pas la peine d'en parler beaucoup ici: le langage est un choix personnel (mais des langages proposant des outils comme Flex et Bison sont plus adaptés), pour la liste d'instructions, ça se trouve soit dans le manuel du CPU, soit dans un assembleur, désassembleur ou émulateur existant.

3. Lexeur et parseur

Comme déjà annoncé, ce n'est pas la peine de coder un lexeur et un parseur à la main. À la place, on peut utiliser Flex pour le lexeur et Bison pour le parseur, ce qui va beaucoup plus vite. Pour ceux qui préfèreraient coder avec GCJ, il y a JavaCC.

4. Traduction des instructions

Une fois les instructions parsées, il faut générer du code. Vu que les instructions ASM sont en général toutes de la forme insn op1,op2,..., afin d'éviter la duplication de code, le plus simple est de passer par une table: instruction, opcode, nombre d'opérandes, modes d'adressage acceptés. Le code ne doit plus que:

opcode | (op1 << OP1_SHIFT) | (op2 << OP2_SHIFT) | ...

Donc une seule fonction gère tous les opcodes avec peu ou pas de conditionnels (if/switch).

5. Les labels

Vu que les adresses des labels ne sont connues qu'après avoir lu tout le fichier, selon le format de fichier objet, on peut avoir besoin d'une liste de relogements qu'on ne remplit qu'à la fin. Une solution est de d'abord parser tout le fichier en une représentation interne, et seulement quand on a tout parsé, calculer les expressions contenant des labels et après seulement générer le code.

6. Optimisation des relogements

Parlant de "calculer les expressions contenant des labels", avec un bon linker, il vaut mieux ne pas les calculer. À la place, on émet un relogement pour tout label (même ceux à l'intérieur du même fichier), et une paire de relogements (positif/négatif) pour toute différence de labels. Comme ça, l'assembleur ne doit pas se casser la tête sur la taille des références, le linker (s'il est bien fait) la réduira automatiquement au minimum. (Cela dit, ld-tigcc n'optimise actuellement pas la taille des différences d'adresses. La raison pour laquelle il faut les coder en tant que relogements est que ça permet au linker de supprimer des octets entre les 2 labels. Sachez que pour 2 labels dans la même section, la différence ne peut normalement que baisser, pas augmenter, donc il est possible dans l'assembleur d'optimiser en fonction de la taille actuelle.)

Membre de l'équipe de TIGCC: http://tigcc.ticalc.org
Mainteneur du portage Linux/Unix de TIGCC: http://tigcc.ticalc.org/linux/
Membre de l'équipe de CalcForge: http://www.calcforge.org:70/

Participez à la reprise de Ti-Gen!

./Post n°1 Marquer comme non lu.

Kevin Kofler

Ecrit le: Jeudi 27 juillet 2006 à 16:11

Administrateur

Groupe: Staff de Ti-Gen

Messages: 4813

Membre n°40

Inscrit le 08 février 2004

Jyaif :
Je dirais que le l'article de GC a pour but d'expliquer comment marche un assembleur, tandis que celui de KK a pour but d'expliquer comment en faire un.

Euh, ce n'est pas ce que dit son titre...

./Post n°2 Marquer comme non lu.

Kevin Kofler

Ecrit le: Lundi 31 juillet 2006 à 19:22

Administrateur

Groupe: Staff de Ti-Gen

Messages: 4813

Membre n°40

Inscrit le 08 février 2004

Pour Godzil: les topics sont cross-linkés, donc si ta réponse est tellement importante et que c'est tellement insupportable de t'inscrire sur Ti-Gen pour ça ( #roll#

), tu peux répondre sur yN. À moins que ça ne dérange un certain Zephyr... #roll#

./Post n°3 Marquer comme non lu.

geogeo

Ecrit le: Lundi 31 juillet 2006 à 19:35

Fondateur

Groupe: Staff de Ti-Gen

Groupe: Orage Studio

Messages: 4254

Membre n°3

Inscrit le 29 janvier 2004

J'adores le titre du topic.

Webmaster du site.
Programmeur sur TI68K. Arkanoid, Nebulus, GFA-Basic.

Plus d'informations sur GFA-Basic (un langage Basic pour TI68K).
http://www.tigen.org/gfabasic

./Post n°4 Marquer comme non lu.

Vertyos

Ecrit le: Samedi 5 août 2006 à 21:08

Membre

Messages: 165

Membre n°172

Inscrit le 30 mars 2004

Kevin Kofler :
À moins que ça ne dérange un certain Zephyr... #roll#

que Godzil poste ? pas du tout, mais ça risque de ne pas être pratique pour la compréhension, vaudrait mieux qu'il s'inscrive ici

Membre de [ yAronet ]

(et de [ 3l33t ] aussi, mais chut, coté obscur toussa...)

./Post n°5 Marquer comme non lu.

Onur

Ecrit le: Jeudi 10 août 2006 à 18:55

Membre: Maître Ultime

Groupe: Orage Studio

Messages: 1604

Membre n°341

Inscrit le 02 juillet 2004

J'avais pas lu ce topic en pensant que tu ne faisais que critiquer le post de GC. donc je m'étais dit "=> poubelle" mais en fait c'est pas ca, maintenant j'ai lu.

C'est pas mal.

...mais:
Je suis pas d'accord avec 4. Ca dépend vraiment du jeu d'instruction et des opcodes.

5. 6. ne sont pas clairs. On ne peut pas forcément utiliser le linker de tigcc il me semble (je me trompe peut etre) et il faudrait parler mieux de la réduction de la taille, tu ne dis pas clairement que certains sauts peuvent etre codé sur 2 octets pour leur adresse et donc rapprocher deux labels et permettre à d'autres instructions de coder leur adresse sur 2 octets et ainsi de suite.

Je ne veux pas faire quelque chose de bien, je cherche l'excellence:ETP Studio...

et autres projets à finir avant 2010

./Post n°6 Marquer comme non lu.

Kevin Kofler

Ecrit le: Vendredi 11 août 2006 à 13:07

Administrateur

Groupe: Staff de Ti-Gen

Messages: 4813

Membre n°40

Inscrit le 08 février 2004

Bah, ld-tigcc pourrait être adapté pour d'autres architectures. GNU ld permet aussi plus ou moins de faire des optimisations de ce genre ("linker relaxation"), mais il n'y a qu'un ou deux targets qui utilisent ça, et il n'y a pas les astuces comme --reorder-sections. AMHA, ces optimisations ont leur place dans le linker, pas dans l'assembleur, vu qu'elles s'appliquent aussi aux références d'un fichier .s à un autre.
-Edité le Vendredi 11 août 2006 à 13:08 par Kevin Kofler-

./Post n°7 Marquer comme non lu.

Onur

Ecrit le: Vendredi 11 août 2006 à 18:58

Membre: Maître Ultime

Groupe: Orage Studio

Messages: 1604

Membre n°341

Inscrit le 02 juillet 2004

Therefore, the result is not guaranteed to be optimal. There are rare cases where section reordering can still take exponential time, these are due to hardcoded short references between sections rendering some reorderings impossible.

C'est pas terrible ca.. mais bon. C'est deja vraiment pas mal.

Faudrait rajouter un

0. Ne pas lire les tutos inutiles.

Je ne veux pas faire quelque chose de bien, je cherche l'excellence:ETP Studio...

et autres projets à finir avant 2010

./Post n°8 Marquer comme non lu.

Kevin Kofler

Ecrit le: Samedi 12 août 2006 à 01:15

Administrateur

Groupe: Staff de Ti-Gen

Messages: 4813

Membre n°40

Inscrit le 08 février 2004

Onur :

C'est pas terrible ca.. mais bon. C'est deja vraiment pas mal.

Si je me rappelle bien, maintenant, on se tape carrément une erreur si on fait ça (et le résultat du reordering est tel que la référence ne tient plus). Faut pas mettre des bXX.s d'une section à une autre, un point c'est tout. L'algorithme de Sebastian (utilisé maintenant pour tout sauf les sections de démarrage) ne fait pas de backtracking. Faudra que je mette à jour la doc.

Quant au "not guaranteed to be optimal", si tu nous ponds un algo polynomial pour une solution optimale, tu as probablement prouvé P=NP.

(Reste juste à prouver que le problème est NP-hard, ce qui est la partie facile, je pense.

) Les algos exponentiels auquels j'ai pensés étaient vraiment inacceptables en temps d'exécution prévu (et quand moi, je dis inacceptable, c'est qu'il faut des années pour linker un fichier

).
-Edité le Samedi 12 août 2006 à 01:17 par Kevin Kofler-