Accueil Ti-Gen Foire Aux Questions Chat sur le chan #tigcc sur IRC
Liste des membres Rechercher Aide
Bienvenue Invité !   Se connecter             Mes sujets   
Administrer
0 membre(s) et 1 visiteur(s) actif(s) durant les 5 dernières minutes 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 Déconnecté(e)    Voir le profil de Kevin Kofler Envoyer un email à Kevin Kofler Visiter le site WEB de Kevin Kofler Envoyer un message privé à Kevin Kofler  


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:
  • chercher l'instruction dans la table (hachage, dichotomie, tries, ...),
  • émettre opcode | (op1 << OP1_SHIFT) | (op2 << OP2_SHIFT) | ...,
  • émettre op1, op2, ... (la partie qui vient après l'opcode, genre la valeur d'un immédiat).
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 Déconnecté(e)    Voir le profil de Kevin Kofler Envoyer un email à Kevin Kofler Visiter le site WEB de Kevin Kofler Envoyer un message privé à Kevin Kofler  


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... ;)
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°2   Marquer comme non lu.
Kevin Kofler Ecrit le: Lundi 31 juillet 2006 à 19:22 Déconnecté(e)    Voir le profil de Kevin Kofler Envoyer un email à Kevin Kofler Visiter le site WEB de Kevin Kofler Envoyer un message privé à Kevin Kofler  


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#
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°3   Marquer comme non lu.
geogeo Ecrit le: Lundi 31 juillet 2006 à 19:35 Déconnecté(e)    Voir le profil de geogeo Envoyer un email à geogeo Visiter le site WEB de geogeo Envoyer un message privé à geogeo  


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 Déconnecté(e)    Voir le profil de Vertyos Envoyer un email à Vertyos Visiter le site WEB de Vertyos Envoyer un message privé à Vertyos  

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 Déconnecté(e)    Voir le profil de Onur Envoyer un email à Onur Visiter le site WEB de Onur Envoyer un message privé à Onur  


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 Déconnecté(e)    Voir le profil de Kevin Kofler Envoyer un email à Kevin Kofler Visiter le site WEB de Kevin Kofler Envoyer un message privé à Kevin Kofler  


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-
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°7   Marquer comme non lu.
Onur Ecrit le: Vendredi 11 août 2006 à 18:58 Déconnecté(e)    Voir le profil de Onur Envoyer un email à Onur Visiter le site WEB de Onur Envoyer un message privé à Onur  


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 Déconnecté(e)    Voir le profil de Kevin Kofler Envoyer un email à Kevin Kofler Visiter le site WEB de Kevin Kofler Envoyer un message privé à Kevin Kofler  


Onur :
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.

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. :D (Reste juste à prouver que le problème est NP-hard, ce qui est la partie facile, je pense. :D) 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 :D).
-Edité le Samedi 12 août 2006 à 01:17 par Kevin Kofler-
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!
    
  :: Index » Forum TI-Nspire » Algorithmie et optimisation » Écrire un assembleur pour les futurs experts (8 réponse(s))
Pages : 1/1     « [1] » »|

.Répondre à ce sujet
Les boutons de code
[B]old[I]talic[U]nderline[S]trikethrough[L]ine Flip Hori[Z]ontallyFlip [V]erticallySha[D]ow[G]low[S]poilerCode [G][C]ite
Bullet [L]istList Item [K] Link [H][E]mail[P]icture SmileysHelp
Couleurs :
Saisissez votre message
Activer les smileys
     

Forum de Ti-Gen v3.0 Copyright ©2004 by Geoffrey ANNEHEIM
Webmaster: Kevin KOFLER, Content Admins: list, Server Admins: Tyler CASSIDY and Kevin KOFLER, DNS Admin: squalyl
Page générée en 57.46ms avec 18 requetes