Evaluation de la quantité de travail (in)utile dans l’exécution des programmes

Rapport de stage de DEA

Evaluation de la quantite de travail utile

dans l’execution des programmes

Benjamin VidalResponsable de stage : Pierre Michaud

Projet CAPS

Sujet de stage

La recherche en architecture de processeur est confrontee actuellement a des contraintes quirendent de plus en plus difficile l’augmentation des performances des processeurs. Ces contraintessont multiples : consommation electrique, latence de propagation des signaux sur les connexions,temps et cout de developpement, etc. . . Pour esperer trouver d’eventuelles solutions permettantd’augmenter les performances de maniere significative sur une large gamme d’applications, il fauttrouver de nouveaux paradigmes d’architecture. Pour cela, il faut d’abord avoir une bonne compre-hension du comportement des programmes.

Le sujet propose a pour but d’evaluer la quantite de travail reellement utile dans l’execution desprogrammes. L’idee sous-jacente est que si une fraction importante de l’execution d’un programmeconsiste en du travail inutile, il peut etre interessant de chercher un paradigme architectural per-mettant d’exploiter cette propriete.

Le probleme consiste a donner une definition de l’utilite d’un travail. Par exemple, dans lareference [1], un resultat intermediaire est considere inutile s’il est ecrit dans un registre et estecrase sans avoir ete utilise. Dans la reference [5], un store a une adresse memoire est considereinutile s’il ecrit une valeur egale a la valeur deja stockee a cette adresse. Nous proposons d’etudierune autre definition, selon laquelle une instruction dynamique est consideree utile si

– Elle produit un resultat emis en sortie du programme (ex. printf)– Elle produit un resultat utilise comme operande d’une instruction utile– C’est un branchement dominant une instruction utile

La partie recherche du stage consiste a concevoir un algorithme efficace en temps et en memoirepermettant d’evaluer la quantite d’instructions dynamiques utiles. La partie mise-en-œuvre consistea ecrire le programme correspondant, et a l’utiliser pour obtenir des statistiques sur la fraction detravail utile, et d’autres statistiques, a definir, permettant de mieux apprehender le comportementdes programmes. La mise en œuvre se fera a l’aide des outils developpes au sein du projet CAPS.On travaillera sur des traces d’execution des programmes de la suite SPEC CPU2000.

2

Remerciements

Au cours de ce stage au sein de l’equipe CAPS de l’IRISA, il m’a ete possible de rencontrerun grand nombre de personnes qui m’ont aide a comprendre le fonctionnement d’un laboratoire derecherche en informatique et surtout a acquerir le recul necessaire pour mieux apprehender le mondede l’architecture des microprocesseurs. Je voudrais donc remercier Ronan Amicel, Laurent Bertaux,Francois Bodin, Henri-Pierre Charles, Assia Djabelkhir, Romain Dolbeau, Antony Fraboulet, KarineHeydemann, Thierry Lafage, Antoine Monsifrot, Laurent Morin, Gilles Pokam, Olivier Rochecouste,Andre Seznec et Eric Toullec.

Je tiens aussi a remercier Yannos Sazeides (Enseignant a l’universite de Chypre) avec qui j’ai eul’occasion d’echanger des idees sur la facon d’elaborer automatiquement un graphe de dependancede donnee a partir de l’execution d’un programme.

Et enfin je tiens a remercier tres chaleureusement mon maıtre de stage, Pierre Michaud, qui m’adonne la liberte de travail que j’aurais aime trouver tout au long de mon experience universitaireet professionnelle et m’a permis ainsi de suivre les pistes que je souhaitais. Je tiens egalement a leremercier pour tous les conseils qu’il a pu me donner concernant le monde de la recherche (publiqueou privee) et de m’avoir fait partager sa vision des choses sur de nombreux sujets.

3

Table des matieres

1 Bibliographie 9

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 Compilation et travail inutile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.2.1 Vous avez dit « instructions inutiles » ? . . . . . . . . . . . . . . . . . . . . . 10

1.2.2 Instructions statiques inutiles . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3 Premiere approche :Instructions inutiles detectees dynamiquement . . . . . . . . . . . . . . . . . . . . . . 11

1.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.3.2 Description du principe de detection et d’elimination des instructions inutiles 11

1.3.3 Idees d’implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.3.4 Conclusion sur cette approche . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.4 Deuxieme approche :Ecritures silencieuses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.4.2 Le phenomene d’ecriture silencieuse . . . . . . . . . . . . . . . . . . . . . . . 13

1.4.3 Les consequences de l’elimination des ecritures silencieuses . . . . . . . . . . . 14

1.4.4 Idees d’implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14


4

1.5 Troisieme approche :Travail inutile global lors de l’execution d’un programme . . . . . . . . . . . . . . . . 16

1.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.5.2 Evaluer l’utilite d’une instruction ? . . . . . . . . . . . . . . . . . . . . . . . . 16

1.5.3 Mise en œuvre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17


1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2 Compte rendu du stage 20

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.1.1 Le travail inutile, qu’est ce que c’est ? . . . . . . . . . . . . . . . . . . . . . . 20

2.1.2 Notre protocole de test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2 La methode utilisee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.2.1 L’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.2.2 L’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.2.3 Le resultat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.3 L’environnement de travail : Les choix de mise en œuvre . . . . . . . . . . . . . . . . 29

2.3.1 Les Outils . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.3.2 L’instrumentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.3.3 Le choix de la Plateforme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.3.4 SPARC : Le Meilleur des Mondes ? . . . . . . . . . . . . . . . . . . . . . . . . 32

2.3.5 S’affranchir de la numerotation des registres faite par Salto . . . . . . . . . . 34

2.3.6 Les expressions regulieres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.3.7 La gestion des fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5

2.4 Resultats & Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.4.1 Les chiffres. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.4.2 Le doute. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.4.3 La repartition du travail inutile . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3 Annexes 46

3.1 Petit historique du stage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3.2 A propos de la description machine Salto du Sparc . . . . . . . . . . . . . . . . . . . 47

3.2.1 Gestion des instructions Save et Restore . . . . . . . . . . . . . . . . . . . . . 47

3.2.2 L’instruction call & link . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.2.3 L’instruction addx . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.2.4 Un detail : les instructions nop, ba et bn . . . . . . . . . . . . . . . . . . . . . 47

3.3 Resultat de l’evaluation du travail inutile sur un exemple simple . . . . . . . . . . . 49

3.3.1 Code source en C de l’exemple . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3.3.2 Code source en assembleur Sparc de l’exemple . . . . . . . . . . . . . . . . . 49

3.3.3 Identifiant d’instruction statique . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.3.4 Trace d’execution dynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.3.5 Graphe de dependance de donnee . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.3.6 Trace d’execution dynamique 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 57

3.4 Exemple de donnees stockees en cours d’execution . . . . . . . . . . . . . . . . . . . 59

3.5 Code source du programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

6

Table des figures

1.1 Mise en evidence de l’inutilite des instructions ne produisant des resultats utilisesque par des instructions inutiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.1 La structure de donnee d’un nœud du graphe . . . . . . . . . . . . . . . . . . . . . . 24

2.2 Exemple de graphe genere par l’algorithme 1 & 3 . . . . . . . . . . . . . . . . . . . . 25

2.3 Du code source en langage de haut niveau au graphe de dependance de donneedynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.4 Instrumentation de code source en assembleur . . . . . . . . . . . . . . . . . . . . . . 30

2.5 Principe de l’instrumentation faite par le programme d’evaluation de la quantite detravail inutile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.6 Le principe de la fenetre de registres du Sparc . . . . . . . . . . . . . . . . . . . . . . 33

2.7 Quantite d’instructions assembleurs inutiles lors de l’execution de gzip dans differentesconditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.8 Mise en evidence d’un probleme d’implementation par divergence du flot de controle 38

2.9 Evolution de la quantite de travail inutile en fonction du temps . . . . . . . . . . . . 40

3.1 Graphe d’exemple genere par l’utilitaire « dot » . . . . . . . . . . . . . . . . . . . . . 56

3.2 Les structures de donnees utilisees par le programme pour construire le graphe dedependance de donnee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

7

Liste des Algorithmes

1 Construction du graphe de dependance de donnee . . . . . . . . . . . . . . . . . . . 23

2 Parcours du graphe (Nœud) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3 Detection des instructions inutiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

8

Chapitre 1

Bibliographie

1.1 Introduction

Aujourd’hui, pour ameliorer les performances d’un programme, il ne suffit plus seulement d’ajou-ter du materiel dans un systeme donne. Il faut avant tout etudier le comportement de ce programmeafin d’adapter au mieux les ajouts qui doivent etre faits au systeme. De ce constat, les architectesdes microprocesseurs ont tire des idees aujourd’hui fondamentales (tels les differents niveaux dememoires caches qui exploitent la propriete de localite temporelle et spatiale d’acces aux donneesdans les programmes).

En ce sens, certains travaux de recherche s’interessent aujourd’hui au probleme du travail ef-fectue inutilement par un microprocesseur. Ils mettent en evidence une quantite non negligeablede travail inutile. Dans cette bibliographie, trois approches principales de travail inutile ont eteretenues.

1. Une instruction produisant un resultat jamais utilise par une autre instruction est considereecomme inutile (approche de « l’instruction morte » retenue par l’article [1]).

2. Une instruction d’ecriture est consideree comme inutile si cette derniere ne modifie pas l’etatde la memoire (i.e. la meme valeur est ecrite a la meme adresse memoire) (approche de« l’ecriture silencieuse » retenue dans de nombreux articles [5, 3, 7]).

3. Une instruction est consideree comme utile si elle produit un resultat en sortie (affichage d’unresultat par exemple) ou qu’elle est elle meme utile a une instruction utile (approche retenuepour le stage).

Apres un bref tour d’horizon des travaux deja effectues dans le domaine au niveau des compila-teurs, chacun des trois aspects decrits ci-dessus du travail inutile sera developpe dans un paragraphede cette bibliographie. S’en suivra un paragraphe de discussion sur la possibilite de meler ces deuxapproches pour essayer d’obtenir une cooperation compilation/execution dans l’elimination desinstructions inutiles.

9

1.2 Compilation et travail inutile

1.2.1 Vous avez dit « instructions inutiles » ?

Il peut paraıtre surprenant au premier abord d’entendre parler de travail inutile dans un pro-gramme. En effet, a partir du moment ou le programmeur demande d’effectuer un travail a lamachine, (encore que celui-ci ne soit pas infaillible. . .) ce travail doit avoir une utilite (au sensinformatique du terme bien entendu. . .). Cependant, au dela du programmeur, il existe toute unechaıne de mecanismes permettant de passer du langage de haut niveau (i.e. langage de program-mation classique) au code machine executable. Ainsi ce programme va passer par toute sortes detransformations qui vont introduire du travail inutile. De plus, il est possible de trouver, dans lafacon dont sont concus les programmes, du travail inutile (redondance de calculs par exemple).

1.2.2 Instructions statiques inutiles

Pour commencer, il est important de rappeler ce que sont les instructions statiques et les ins-tructions dynamiques. Une instruction statique est une instruction telle qu’on peut la trouver dansle code source d’un programme. Une instruction dynamique est une instance d’instruction statique.A chaque instruction statique peut correspondre plusieurs instructions dynamiques (autant que defois ou l’on execute cette instruction statique).

Exemple simple :

pour i de 1 à n fairet[i] := 0;

fpour

Instruction statique : t[i] := 0Instructions dynamiques associées : t[1] := 0, t[2] := 0, …, t[n] := 0

Dans l’exemple suivant, il est important de noter que si n n’est pas fixe lors de la compilation, laseule connaissance du compilateur est l’instruction statique. Il ne pourra donc pas, a priori se servirde la valeur de n a des fins d’optimisation. Supposons maintenant qu’un programme ne soit composeque des instructions de l’exemple et n’affiche aucun resultat. Le compilateur peut en deduire quel’ensemble du travail a effectuer pour executer cette boucle est inutile. Cependant, il suffit d’ajouterune instruction qui utilise t[m] en lecture (m etant un parametre d’entree du programme inconnua la compilation) pour que, potentiellement, l’ensemble du travail de la boucle devienne utile. Eneffet, le compilateur ne sachant pas quelle case du tableau t va etre accede, il est oblige de considererque l’ensemble de la boucle fournit du travail utile.

Il existe de nombreuses autres manieres d’eliminer du travail inutile lors de la compilation [2, 4]que nous n’aborderons pas ici car seul l’aspect decrit ci-dessus se rapproche des travaux vises danscette etude.

Dans la suite de cette bibliographie, nous ne nous interesserons qu’aux instructions inutilesdynamiques (i.e. qui ne peuvent pas etre detectees par le compilateur puisqu’elles dependent devaleurs d’entrees du programme non connues au moment de la compilation).

10

1.3 Premiere approche :Instructions inutiles detectees dynamiquement

1.3.1 Introduction

Les auteurs de l’article [1] se sont apercus que le rearrangement des instructions fait par les com-pilateurs lors des phases d’optimisations cree des instructions inutiles. En effet, comme le montreleurs resultats, une compilation faite sans optimisations montre un niveau faible d’instructions in-utiles alors qu’une compilation avec un fort niveau d’optimisation montre un taux d’instructionsinutiles relativement eleve (parfois superieur a 10 %). Cependant, malgre ce travail effectue inuti-lement, il est bon de rappeler que globalement, le temps d’execution de ces programmes diminue(i.e. on a bien l’effet desire). La question qui vient alors est :« Comment conserver ces optimisations tout en reduisant le travail inutile qui leur est associe ? »

1.3.2 Description du principe de detection et d’elimination des instructionsinutiles

Dans un premier temps, l’important est d’analyser les instructions executees inutilement afinde savoir comment les detecter. Les auteurs de l’article [1] se sont ainsi apercus que les instructionsdynamiques inutiles etaient tres souvent des instances d’un nombre reduit d’instructions statiques.Ces instructions statiques sont appelees des instructions partiellement inutiles. En marquant cesinstructions particulieres comme etant propices a generer des instructions dynamiques inutiles,il est possible de ne faire un traitement particulier que sur ces dernieres afin de savoir si uneinstance precise sera reellement inutile. Lors de l’execution, pour chaque instance d’une instructionpartiellement inutile, une estimation de l’utilite de cette instruction dynamique sera faite. De cetteestimation decoulera son execution ou non. Dans le cas d’une mauvaise prediction, un mecanismede recuperation permet de lancer l’execution de cette instruction au moment ou l’on apprend quela prediction est erronee.

1.3.3 Idees d’implementation

Les auteurs de l’article [1] ont donne quelques idees d’implementation qui pourraient etre misesen œuvre pour la detection de ce type d’instructions. La plus simple consiste a memoriser dans uncache totalement associatif les instructions statiques ayant deja genere des resultats inutiles par lepasse. Du fait qu’un faible nombre de ces instructions generent un grand nombre des instructionsdynamiques inutiles, ce cache permettra de « suspecter » la prochaine instance d’une instructionstatique ayant deja genere des resultats inutiles.

Par la suite, lors de la detection d’une instruction dynamique « suspectee » d’etre inutile, sonexecution sera suspendue jusqu’au « verdict » final permettant de savoir si il etait juste de la sus-pecter. Si tel est le cas, cette instruction ne sera pas executee, dans le cas contraire, cette instructionsera executee ajoutant ainsi un surcout du au retard d’execution pris par cette instruction. Il est

11

donc tres important d’avoir une estimation la plus fine possible afin d’eviter ce genre de cas et afind’augmenter le nombre d’instruction inutiles suspectees a juste titre. Pour cela, des optimisationssont proposees : utilisation de l’information de flot de controle et ajout d’un compteur deux bits asaturation principalement.

Il est important de noter que ces implementations ne tiennent pas compte des resultats calculesqui ne servent qu’a des instructions inutiles. Autrement dit, cette implementation ne prend pas encompte le caractere transitif que peuvent avoir certaines instructions inutiles.

Instructionproduisant un résultat R

Instructionutilisant R et produisant R’

Instructionutilisant R’ et produisant R’’

Si R’’ est un résultat inutile R’ et R auront été produits inutilement

Fig. 1.1 – Mise en evidence de l’inutilite des instructions ne produisant des resultats utilises quepar des instructions inutiles

1.3.4 Conclusion sur cette approche

En conclusion, nous pouvons dire que les auteurs de l’article [1] ont mis en evidence une quantitenon negligeable de travail inutile meme si elle reste, aujourd’hui, difficile a exploiter. En effet, dansun environnement ou les ressources sont peu limitees, l’efficacite de l’implementation decrite ci-dessus offre des gains en performance negligeables. En revanche, dans des conditions de ressourcesplus limitees, les gains peuvent atteindre 10 % d’amelioration des performances. De plus le faitd’executer moins d’instructions permet une diminution de la charge des Unites Arithmetiques etLogiques (UAL) et de la consommation electrique relativement importante. D’apres les auteurs, unmecanisme materiel diminuant l’impact des instructions inutiles sur la performance et la consom-mation electrique permettrait d’appliquer des optimisations de code plus poussees a la compilation.

12

1.4 Deuxieme approche :Ecritures silencieuses

1.4.1 Introduction

D’apres les auteurs de l’article [5], il existe principalement deux types d’ecritures silencieuses.D’une part les mises a jours de valeurs silencieuses (qui ne changent pas l’etat de la memoire danslaquelle elles ecrivent) et d’autre part les ecritures silencieuses stochastiques qui mettent a jour lamemoire de maniere previsible. Dans la suite de ce chapitre, nous nous concentrerons sur les misesa jour de valeurs silencieuses et parlerons, par abus de langage, d’ecritures silencieuses pour lesdesigner.

1.4.2 Le phenomene d’ecriture silencieuse

Au vu de la definition de ce qu’est une ecriture silencieuse, il parait difficile de croire que cesinstructions puissent avoir un impact negatif important sur les performances d’un programme.Pourtant, les articles sur le sujet montrent que souvent plus de 30 % des ecritures sont silencieusesdans les applications testees. En effet, il existe de nombreux cas ou, lors du parcours des elementsd’un tableau, les modifications apportees par ce parcours ne concernent qu’un petit nombre deselements de ce tableau.

Exemples simples :

pour i de 1 à n faireb := (b & t[i]);

fpour

t étant un tableau de booléensb étant un booléen

l'opération & étant un "ET" logique

pour i de 1 à n fairet[i] := (t[i] & b);

fpour

pour i de 1 à n fairet[i] := t[i] + e(i);

fpour

t étant un tableau d'entierse étant une fonction

(a) (b) (c)

Dans l’exemple (a), nous pouvons voir que pour chaque case du tableau t dont le booleen est avrai, l’execution du corps de la boucle ne produit aucun travail utile (la meme valeur sera re-ecritedans b). Dans l’exemple (b), le simple fait que b soit egal a vrai entraıne une inutilite de l’ensemblede la boucle. Dans l’exemple (c), lorsque ε(i) renvoi zero, le corps de la boucle peut-etre considerecomme inutile. Un autre cas assez frequent de travail inutile est celui ou un tableau est initialiseapres avoir ete utilise une premiere fois. Si lors de la premiere utilisation de ce tableau, toutes sesvaleurs n’ont pas ete modifiees, il est inutile de re-initialiser l’ensemble des cases de ce tableau.

Il existe d’autres situations dans lesquelles un grand nombre d’ecritures silencieuses peuvent etreobservees : lors de l’appel d’un sous-programme, si les registres sauvegardes n’ont pas ete utilisesdans ce sous-programme, leur restauration sera inutile. Ce meme phenomene peut-etre observe lorsde la sauvegarde/restauration de contexte d’un processus par un systeme d’exploitation.

13

1.4.3 Les consequences de l’elimination des ecritures silencieuses

Au dela du gain evident que provoquerait un mecanisme fiable de suppression des ecrituressilencieuses, un tel systeme permettrait egalement de supprimer une certaine quantite de travailassez importante liee a ces instructions. En premier lieu, les informations de controle liees a cesinstructions ne sont plus necessaires (Ex : si une serie d’ecritures silencieuses se trouve dans uneboucle, il est inutile d’executer la boucle). De plus, lors de l’execution d’une instruction de range-ment en memoire, tout un mecanisme lourd de rapatriement de la ligne de cache concernee vers lamemoire est mis en place (ecriture de la donnee dans le cache, marquage de la ligne de cache commeetant modifiee puis, lors du chargement de nouvelles donnees dans cette ligne de cache, ecriturede l’ancienne ligne de cache consideree comme modifiee en memoire). De fait, la suppression d’uneecriture evite d’avoir a passer par toute ces operations d’acces a la memoire tres couteuses. Commeexplique dans l’article [3], cette remarque prend encore plus d’importance dans un systeme multi-processeur puisque a chaque ecriture memoire est associe un message d’invalidation a destinationdes autres processeurs provoquant un defaut de cache lors du prochain acces a ces donnees. . . Ilest egalement important de noter que si certaines ecritures ne sont pas effectuees, de fait, certainesdependances de donnees n’existent plus. De cette facon, le processeur n’est plus oblige d’attendreque ces valeurs soient ecrites pour pouvoir les utiliser. Le rendement du pipeline du processeur estalors ameliore.

1.4.4 Idees d’implementation

Les auteurs de l’article [5] ont propose une implementation basique permettant de supprimerles ecritures silencieuses. Cette implementation consiste a remplacer toute les operations de ran-gement en memoire par trois operations : Chargement de l’ancienne valeur presente en memoire,comparaison avec la valeur qui doit y etre ecrite et enfin, dans le cas ou ces deux valeurs ne seraientpas egales, ecriture de la nouvelle valeur en memoire. Cette methode est sure et permet de detecterl’ensemble des ecritures silencieuses. De plus, les lectures pouvant etre servies en paralleles, il peutetre interessant de remplacer les ecritures par des lectures suivies de comparaisons. Cependant,dans la mesure ou le nombre d’ecritures silencieuses ne represente pas la majorite des ecrituresmemoire, les auteurs ont ajoute une « implementation parfaite » dans laquelle un mecanisme per-met de savoir si une ecriture va etre utile et, dans ce cas, n’effectuera que l’ecriture en memoiresans avoir a comparer la nouvelle valeur a la valeur precedente.

D’autres idees d’implementations apparaissent egalement dans l’article [5] comme par exemplela possibilite que la ligne de cache ne soit pas marquee comme modifiee lorsqu’elle recoit une ecrituresilencieuse evitant ainsi d’avoir a propager l’ecriture en memoire centrale (avantage principal del’elimination des ecriture silencieuses).

L’implementation retenue pour les simulations faites par les auteurs de [5] est la premiereproposee avec pour caracteristique supplementaire que seules les ecritures mises en attente vontsubir une verification de leur utilite. Ce qui veut dire qu’une ecriture survenant a un moment ou aumoins un port d’ecriture de la memoire est disponible sera servie avant que la verification de sonutilite n’ai pu etre faite. De cette facon, les performances des ecritures ne sont jamais degradeespuisque le mecanisme n’agit que sur la file d’attente des ecritures afin de la reduire.

14


Les auteurs de l’article [5] ont mis en evidence une grande quantite de travail inutile a travers lesecritures silencieuses. En effet, les proportions d’ecritures silencieuses obtenues lors des tests sontparfois tres importantes et laissent penser qu’elles pourraient avoir une influence tres importantesur les performances, notamment dans les systemes dont la purge des lignes de cache en memoire estun goulet d’etranglement. Les auteurs mettent egalement en avant la reduction du trafic sur le busd’un systeme multiprocesseur a memoire partagee qui est souvent un point critique dans ce type desystemes (ce trafic limite le nombre de processeurs sur un meme bus). D’autres travaux elargissant letheme de l’ecriture silencieuse ont egalement ete presentes comme celui sur les ecritures silencieusestemporaires [6] considerant que si une valeur en memoire est modifiee puis remise a son anciennevaleur et qu’aucune lecture ne soit intervenue sur la valeur transitoire, elle peut-etre considereecomme silencieuse. Ce modele semble bien s’adapter aux cas decrits ci-dessus de sauvegarde etde restauration de contexte frequents (appel de sous-programmes, passage d’un processus a unautre. . .).

15

1.5 Troisieme approche :Travail inutile global lors de l’execution d’un programme

1.5.1 Introduction

Dans cette approche, la problematique est un peu differente de celle vue dans les deux premiersparagraphes. En effet, le but de ces deux approches etait de detecter (soit par prevision, soit demaniere dynamique) une categorie d’instructions inutiles afin d’eviter leur execution « au vol ».Dans l’approche retenue pour le stage, il s’agit d’abord de regarder quelle est la quantite de travailinutile de facon globale (essayer d’evaluer l’ensemble du travail fait inutilement par un programme)afin d’avoir ensuite une idee du type de comportement ou d’application execute par un processeurqui produit le plus de travail inutile. De cette facon, si certains resultats montrent une quantite nonnegligeable de travail inutile dans certains types d’applications, il sera ensuite possible d’etudierpourquoi ce travail inutile est si important et si il peut etre evite d’une maniere ou d’une autre.

1.5.2 Evaluer l’utilite d’une instruction ?

La methode retenue ici pour evaluer l’utilite d’une instruction est assez simple : Une valeur quiest affichee en sortie d’un programme est consideree comme un resultat utile. Toute instructionayant servi a calculer ce resultat est une instruction utile. Ainsi, les instructions utiles a un resultatpeuvent etre representees par un arbre de dependance entre ces dernieres dont la racine est leresultat lui-meme et chaque nœud represente les instructions utiles au calcul de ce resultat (aussibien les instructions de rangement/recuperation en memoire, de calcul et de branchement). Lesfeuilles seront alors les valeurs d’entrees (parametres fixes lors de la compilation ou de l’execution)du programme. En regroupant l’ensemble des arbres ainsi obtenus pour chaque resultat en un grapheoriente dont les sources sont les resultats et les puits sont les valeurs d’entree du programme, ilest possible d’identifier quelles sont les instructions reellement utiles au programme. En effet, lesinstructions et les valeurs d’entrees inutiles au programme n’appartiendront pas a ce graphe etseront ainsi mises en evidence.

16

Exemple simple :

a := lire();b := VRAI;c := 0;

si a=0 faireb := FAUX;c := 5;

fsi

si b alors écrire(c) sinon écrire(a)

Exemple de graphe d’exécution si a vaut 0 :

écrire(a)

b := FAUX

nécessite b

Test a=0

branchementcorrespondant

nécessite a

nécessite a

a := lire()

Valeur d’entréedu programme

a := lire()


b := VRAI

c := 5

c := 0

Instructions exécutéesinutilement

Exemple de graphe d’exécution si a vaut 1 :

Test a=0

nécessite a

a := lire()


Aucune instruction n’estexécutée inutilement

écrire(c)

nécessite b nécessite c

c := 0


b := VRAI


Cet exemple permet de mettre en evidence le fait que selon les valeurs d’entrees du programme,il peut y avoir du travail inutile ou pas. De plus, il met en lumiere (dans le cas ou a vaut 1) lefait que le test a=0 correspondant au branchement du « si » doit etre pris en compte comme etantdu travail utile puisque de ce branchement vont dependre les instructions qui vont suivre (Nouspouvons dire que ces instructions « exigent » l’execution de ce branchement et donc du test quipermet de savoir si ce branchement doit etre pris).

Cette methode d’identification des instructions inutiles semble parfaite (meme si elle ne prendpas en compte certaines ecritures silencieuses). Cependant, elle necessite le deroulement complet duprogramme afin de savoir si oui ou non une instruction dynamique du programme sera utile pourun resultat final. De fait, cette methode ne peut pas etre utilisee directement pour eliminer « auvol » les instructions inutiles. En revanche, elle permet d’exhiber de nombreux cas d’instructionsinutiles que les autres methodes ne detectent pas. Par exemple, le cas d’une instruction inutile partransitivite mis en evidence figure 1.1 sera detecte par cette methode.

1.5.3 Mise en œuvre

Comme decrit dans le sujet de stage, la mise en œuvre de cette approche du travail inutile consis-tera a elaborer un programme permettant de detecter les instructions dynamiques inutiles, d’apresla definition donnee ci-dessus, afin de faire des statistiques sur la quantite de travail inutile dans unensemble de programmes a tester. Differentes categories de travail inutile pourront egalement etremises en evidence (Ex : chargements inutiles, rangements en memoire inutiles, calculs inutiles. . .).Une fois les tests effectues, un travail de regroupement des applications testees selon les resultatspourra etre fait afin de degager, eventuellement, des « motifs » de comportements permettant en-suite de savoir quelles applications sont le plus concernees par quel type de travail inutile. Nouspouvons imaginer, a partir de la, que des ebauches de solutions materielles et/ou logicielles ne soient

17

trouvees pour reduire cette quantite de travail inutile. Cependant, l’objet du stage reste celui-ci :« Concevoir et ecrire un programme permettant de calculer la quantite de travail inutile dans unprogramme particulier apres son execution » .

Dans ce sens, le travail a effectuer en stage sera, dans un premier temps, de reflechir a la manierede detecter quelles sont les instructions qui ont ete executees inutilement lorsque l’execution d’unprogramme sera terminee (algorithme de construction puis d’exploration du graphe de dependancedes instructions decrit dans cette section). Ces resultats devront ensuite etre mis en forme afin dedegager des statistiques sur la quantite de travail inutile (pourcentage d’instructions inutiles) etsur la nature de ces instructions (de quel type d’instructions s’agit-il ?). Une fois cet algorithmeimplemente, il sera interessant de le tester sur different type de programme afin de savoir quelleest la quantite de travail reellement inutile (d’apres la definition donnee en introduction de cettesection) dans ces programmes.


En conclusion nous pouvons dire que l’approche retenue pour le stage est une demarche scien-tifique experimentale permettant de savoir quelle est la proportion globale de travail inutile dansun programme. Si les resultats revelent une grande quantite de travail inutile, de nombreusesouvertures paraissent possibles : Detection de ces instructions grace a des compilateurs « intel-ligents », detection de ces instructions « au vol » (approche deja retenue par [1]), cooperationcompilateur/materiel ou encore ajout de nouvelles instructions afin de faciliter leur detection.

18

1.6 Conclusion

En conclusion, nous pouvons dire que plusieurs manieres d’eliminer le travail inutile ont deja eteabordees (tant dans le domaine de la compilation qu’en architecture). En effet, lors de la compila-tion, une certaine quantite de travail inutile peut deja etre supprimee (en fonction des informationsque le compilateur peut exploiter). Cependant, nous avons egalement vu que certaines optimisa-tions de ces memes compilateurs generent des instructions inutiles. De fait, differentes methodes ontete proposees pour eliminer ce travail inutile lors de l’execution (instructions dynamiques inutiles).Une autre approche interessante consistait a eliminer les ecritures silencieuses, une autre forme detravail inutile.

Apres ce tour d’horizon global, il est assez difficile de savoir de maniere precise quelle est laquantite de travail inutile effectuee par un microprocesseur lors de l’execution d’un programme.C’est a cette question que va tenter de repondre le travail a venir en stage. . .

19

Chapitre 2

Compte rendu du stage

2.1 Introduction

2.1.1 Le travail inutile, qu’est ce que c’est ?

Le travail inutile est une notion difficile a cerner. Il existe differentes approches pour traiter leprobleme du travail effectue inutilement par un programme. Tout d’abord, le travail inutile peut-etre de nature statique (detectable et supprimable lors de la compilation) ou de nature dynamique(visible uniquement lors de l’execution). L’elimination du travail inutile statique est deja bienconnue et fait partie integrante de toute chaıne de compilation optimisee digne de ce nom. Ici nousnous interesserons seulement au travail inutile de nature dynamique puisque ce dernier n’est pasexploite par les processeurs ou les langages de programmation actuels.

Une fois le cadre du travail inutile dynamique pose, il est necessaire de se donner une definitionprecise du travail inutile afin de pouvoir en evaluer la quantite lors de l’execution d’un programmesur un jeu de donnees particulier de facon automatique. Cette definition, dans un premier tempstres large, a ete restreinte pour des raisons d’implementation.

La definition prise comme base de depart a cette evaluation etait la suivante :

Tout travail qui ne sert, ni directement, ni indirectement, a produire un resultat est juge inutile.

De facon plus precise :

Une instruction dynamique est consideree comme utile si- Elle produit un resultat emis en sortie du programme (ex : affichage a l’ecran).- Elle produit un resultat utilise comme operande d’une instruction utile.- C’est un branchement dominant une instruction utile.

20

Exemple simple :

instruction 1;

si booléen faireinstruction 2;instruction 3;

fpour

instruction 4;

Dans cet exemple, le branchement conditionnel « domine » les instructions 2 et 3. Si le booleenest vrai et que les instructions 2 et 3 sont inutiles, alors on peut considerer le branchement commeinutile.

Note

Par abus de langage, dans la suite de ce document, nous designerons toutes les instructions detransfert de controle (branchement conditionnels et inconditionnels, sauts, appels de fonctions. . .)par l’expression « instruction de branchement ».

En regardant cette definition de plus pres, un probleme se pose dans le cas general : Supposonsque l’instruction 2 soit un « store » qui range une valeur a une adresse memoire, que l’instruction4 soit un « load » et que le booleen soit a faux. Dans ce cas, si l’instruction 4 est considereecomme utile et si les deux acces pointent sur la meme adresse memoire, alors le branchement devraetre considere comme utile. Cependant, l’adresse de l’acces a la memoire qui aurait pu etre faitpar l’instruction 2 n’est pas connue puisque cette instruction n’a pas ete executee. A cause de cetype d’acces a la memoire (dont l’adresse accedee n’est connue qu’a l’execution) nous avons dufaire l’hypothese conservatrice suivante : Toutes les instructions de branchements sont considereescomme utiles.

Ce qui nous donne la definition suivante :

Une instruction dynamique est consideree comme utile si- Elle produit un resultat emis en sortie du programme (ex : affichage a l’ecran).- Elle produit un resultat utilise comme operande d’une instruction utile.- C’est un branchement.

Note

Par abus de langage, dans la suite de ce document, nous utiliserons le mot « ressource » pourdesigner soit un registre soit un emplacement memoire.

Partant de cette nouvelle definition, l’objectif etait de construire un graphe de dependance dedonnee en reliant les instructions lisant une ressource a la derniere instruction ayant ecrit dans cettememe ressource. De cette facon, lorsqu’une ressource apparaıt comme utile (lorsque sa valeur estecrite en sortie ou qu’elle est utilisee par une instruction de branchement), il devient possible, enparcourant les arcs de ce graphe, de trouver toutes les instructions qui ont ete utiles pour produire

21

ce resultat (le resultat est un graphe ressemblant a la figure 2.2 page 25).

2.1.2 Notre protocole de test

A partir de cette definition, nous avons essaye de mesurer la quantite de travail inutile dans despetits programmes d’exemple, puis, une fois ces exemples valides, nous avons teste notre protocolepour mesurer le travail inutile sur un programme plus consequent et surtout n’ayant pas ete concudans le but d’en mesurer la quantite de travail inutile. Pour faire nos tests, nous avons choisil’utilitaire de compression/decompression de donnees gzip.

22

2.2 La methode utilisee

2.2.1 L’algorithme

Pour construire notre graphe de dependance de donnee, nous avons choisi d’instrumenter chaqueinstruction assembleur afin de controler de facon precise les entrees et les sorties de chacune d’elles.Les entrees etant les operandes d’une instruction (les ressources etant lues par l’instruction) et lessorties etant les resultats d’une instruction (les ressources etant ecrites par l’instruction).

Dans le cas general, notre implementation de la detection de dependance de donnee peut seresumer par l’algorithme 1.

Algorithme 1: Construction du graphe de dependance de donnee

Entree : Programme dont on veut evaluer la quantite de travail inutile.Donnees a fournir en entree a ce programme.

Sortie : Graphe de dependance de donnee dynamique.

1 pour chaque instruction executee faire2 Creer une representation interne de cette instruction;3 L’ajouter a la liste des instructions dynamiques executees;

{Cette representation interne contient des informations concernant l’instruction : sonnumero dynamique, le fichier source auquel elle appartient, son numero statique dans cefichier, son type. . . }

4 pour chaque operande de l’instruction {ressource lue} faire5 Lire dans la table des ressources quelle est la derniere instruction qui a ecrit dans

cette ressource;6 Creer un lien de dependance {arc dans le graphe} entre l’instruction courante et la

derniere instruction ayant ecrit dans la ressource en question;{Associe a l’operande le numero de l’instruction dynamique qui l’a produit}

fin

7 pour chaque resultat de l’instruction {ressource ecrite} faire8 Ecrire dans la table des ressources que l’instruction courante a modifiee l’etat de

cette ressource;fin

fin

Une fois cet algorithme execute sur un programme particulier, il est possible de connaıtre lesdependances directes entre les instructions grace aux arcs construits mais aussi les dependancesindirectes grace aux chemins formes par des suites d’arcs dans le graphe (le graphe de la figure 2.2page 25 en est un exemple).

En ajoutant a l’algorithme precedent une condition dans la boucle principale permettant deparcourir le graphe construit lorsqu’on rencontre une instruction de sortie (affichage), il devient

23

possible de connaıtre les instructions utiles lors de l’execution d’un programme (d’apres la premieredefinition donnee ci-dessus) (cf. algorithme 3).

Procedure Parcours du graphe (Nœud)

1 si le nœud est marque inutile alors2 Marquer ce nœud {representant une instruction} comme etant utile;

pour chaque nœud operande de ce nœud faire3 Appeler la procedure Parcours du graphe (Nœud operande);

finfin

Algorithme 3: Detection des instructions inutiles

Entree : Graphe de dependance de donnee dynamique.Sortie : Quantite d’instructions dynamiques inutiles.

Localisation de ces instructions dans le code source.

pour chaque nœud du graphe fairesi le nœud represente une instruction de sortie ou de branchement alors

Appeler la procedure Parcours du graphe (Nœud);fin

fin

Numéro d'instruction dynamiqueIdentificateur d'instruction statique

Type de l'instruction

Nombre d'opérandesListe des instructions ayant écrit en dernier dans les opérandes

Fig. 2.1 – La structure de donnee d’un nœud du graphe

Un point interessant de cet algorithme, dont nous nous sommes rendu compte une fois l’imple-mentation operationnelle, est qu’il permet de detecter les acces fait en lecture a une zone memoirenon initialisee prealablement. Par exemple, si un tableau de taille n est declare et initialise, le faitde tenter d’acceder a l’adresse de la zone memoire n+1, qui n’a donc pas etait initialisee, provoqueune incoherence dans l’algorithme puisqu’il est impossible de trouver la derniere instruction ayantecrit dans cette zone memoire (ligne 5 dans l’algorithme 1 page precedente). De cette facon, il estpossible de trouver, lors de l’execution, une erreur d’acces a la memoire.

24

39

40 38

36

37

35

34

3

14

33

0

13

25

24

32

31

30

29

28

26

27

23

17

16

22

21

20 19

18

15

9

8

12 11

10

7

2

6

5

4

1

Dans ce graphe, les nœuds sont etiquetes par les numeros dynamiques des instructions (ordred’execution). Les nœuds en gris sont des instructions inutiles alors que les nœuds en noir sont desinstructions utiles.Les instructions dynamiques 4, 12 et 20 sont issues d’une seule et meme instruction statique derangement en memoire dont seulement une instance est utile : l’instruction dynamique numero 12.

Fig. 2.2 – Exemple de graphe genere par l’algorithme 1 & 3

25

2.2.2 L’optimisation

Le gros probleme de cette approche est que le graphe devient tres rapidement enorme, memeavec des programmes de petite taille. En effet, etant donne qu’il faut conserver des informationsconcernant chaque instruction dynamique jusqu’a la fin de l’execution, seule une execution ayantun nombre reduit d’instructions dynamiques peut etre envisagee (aux alentours de 300 000 dansnotre implementation).

Nous avons donc tente de reduire le graphe au maximum en eliminant au cours de l’executionles informations qui ne nous etaient plus necessaires.

Ce qui est fait. . .

Dans un premier temps, pour reduire ce graphe et donc augmenter la taille des programmestestables, nous avons decide de supprimer a la volee les informations concernant les instructions« certifiees » utiles. Ces informations etant le nœud representant cette instruction et les arcs sor-tant de celle-ci. Ces informations ne sont plus d’aucune utilite une fois que le parcours de l’arbredont cette instruction est la racine est effectue. Il est alors possible de les supprimer sans perdred’information utile a notre calcul de quantite de travail inutile. Cette methode permet, a mesureque le programme se deroule et envoi des informations en sortie, (affichage. . .) de reduire le graphe.Il est alors d’autant plus reduit que la quantite de travail utile est importante (sur nos tests, le gainreel en occupation memoire est d’un facteur trois a quatre ce qui permet de tester des programmesdepassant le million d’instructions dynamiques sans avoir un temps d’execution redhibitoire).

La courbe de l’occupation memoire de l’algorithme au cours du temps devient alors identique(a quelques details d’implementation pres) a la courbe representant la quantite de travail inutilecumule (figure 2.9 page 40).

Quelques petites optimisations ont aussi etaient apportees au programme concernant le tempsd’execution. Bien que ce facteur ne soit pas le point crucial de notre algorithme, il semblaitinteressant de s’y pencher pour eviter d’avoir des durees de tests trop importantes.

Nous avons par exemple, a la ligne 1 de la procedure Parcours du graphe page 24, supprime leparcours d’une branche lorsque cette derniere possede comme racine une instruction utile. En effet,si tel est le cas, cela signifie que cette branche a deja ete entierement exploree et qu’il est inutile dela parcourir a nouveau.

Ce qu’il reste a faire. . .

Dans un second temps, il est interessant de voir que si une instruction ecrit dans une ou plu-sieurs ressources, puis que ces ressources sont de nouveau ecrites sans etre lues entre temps, lesinformations concernant cette instruction inutile ne nous serviront jamais puisque cette instructionne sera jamais rendue utile (notion de « valeur morte »). De cette facon, il est possible, ici encore,

26

de reduire notre graphe en supprimant les nœuds representant ce type d’instructions ainsi que leursarcs sortants.

Une maniere simple d’implementer un tel mecanisme serait de considerer que chaque instructioninutile est un objet et que les ressources (registres et zones memoire) sont des moyens d’acceder a cesobjets. Si une instruction est accessible depuis au moins une ressource, alors il n’est pas possiblede supprimer les informations concernant cette instruction. En revanche, si aucune ressource ne« reference » l’objet, alors cet objet est inaccessible depuis les ressources et le restera jusqu’a la finde l’execution du programme. Cet objet peut donc etre supprime (nœud ainsi que ses arcs sortants).Cette methode s’apparente a un systeme de ramasse-miettes comme il est souvent mis en place dansun environnement d’execution pour liberer des zones memoires n’etant plus referencees par aucunpointeur.

2.2.3 Le resultat

La figure 2.3 page suivante est un exemple simple permettant de comprendre comment estconstruit le graphe de dependance de donnee a partir du code assembleur du programme dont onveut evaluer la quantite de travail inutile.

Dans la figure 2.3 page suivante, les nœuds sources sont les instruction utiles par hypothese (encaractere gras). Ces instructions sont soit des instructions de sortie (print %valeur dans l’exemple)soit des instructions de branchement (bne boucle dans l’exemple). Une fois ces instructions jugeescomme etant utile au programme, nous pouvons appliquer la definition recursive permettant detrouver toutes les instructions ayant servi a produire les valeurs utiles a ces instructions. Ainsi,dans notre exemple, l’instruction dynamique numero 18 (print %valeur) possede comme entree leregistre %valeur. Il est donc necessaire de trouver la derniere instruction ayant ecrit dans ce registre.Cette instruction est l’instruction dynamique numero 17 (load [@tab+2],%valeur). Ainsi de suiterecursivement, l’instruction dynamique numero 17 possede comme entree la seconde case du tableaurange a l’adresse memoire @tab dont la derniere ecriture a ete faite par l’instruction dynamiquenumero 8 et ainsi de suite jusqu’a n’arriver qu’a des instructions n’ayant aucune entree (copied’une constante dans un registre (mov 1,%indice dans l’exemple), instruction d’entree au clavierpar l’utilisateur. . .).

De cette maniere, en parcourant le graphe, il est possible d’identifier le travail utile. Les ins-tructions n’etant accessible depuis aucune des sources (instructions de sorties ou de branchement)sont identifiees comme etant du travail inutile (instructions dynamiques 2, 3, 12 et 13 dans notreexemple).

Grace a cet exemple, nous avons mis en evidence un cas simple comportant peu de travail inutile.En revanche, il est facile de prendre conscience de l’importance que peut atteindre ce travail inutiledes lors que le traitement a l’interieur d’une boucle du type de celle presentee dans l’exemple devientimportant. En effet, dans notre exemple, seule la multiplication par 10 et le rangement en memoiresont inutiles mais si la valeur a ranger dans le tableau avait ete un calcul effectue par une fonctioncomportant 10 000 instructions, les chiffres auraient ete differents. De meme, si la taille du tableauavait ete de 10 000 cases dont seulement une aurait ete utilisee, la quantite de travail inutile auraitete beaucoup plus importante. En revanche si, dans notre exemple, les trois cases du tableau avaient

27

Dépendances de données permettant d’identifier le travail utile (arcs du graphe parcourus par l’algorithme).

Dépendance de donnée n’étant pas parcourues par l'algorithme.

Trace d’exécution des instructions(dynamique)

1ère itération de la boucle

2ème itération de la boucle

3ème itération de la boucle

NuméroDynamique

NuméroStatique

123456789101112131415161718

123456234562345678 n Numéro d’instruction dynamique (indique l’ordre

d’éxécution des instructions dans le temps)

n Numéro d’instruction statique utile après parcours du graphe de dépendance (définition récursive).

nNuméro d’instruction statique jugés comme étant inutile d’après la définition (instruction n’appartenant pas au graphe de dépendance de données).

n Numéro d’instruction statique utile par essence (instructions de sorties ou de branchement).

1: mov 1,%indice

boucle:2: mul %indice,10,%valeur3: store %valeur,[%indice+@tab-1]4: add %indice,1,%indice5: cmp 4,%indice6: bne boucle

7: load [@tab+2],%valeur8: print %valeur

Code en assembleur RISC(code statique)

CompilationPour i de 1 à 3 faire t[i] := i*10;Finpour

Ecrire (t[2]);

Code source original

Fig. 2.3 – Du code source en langage de haut niveau au graphe de dependance de donnee dynamique

ete affichees (instruction print), la quantite de travail inutile aurait ete nulle.

Un exemple plus complet montrant dans le detail comment l’algorithme a ete implemente esten annexe (figure 3.2 page 59).

28

2.3 L’environnement de travail : Les choix de mise en œuvre

2.3.1 Les Outils

Pour la mise au point de notre programme d’evaluation de la quantite de travail inutile, plusieursoutils ont ete mis a contribution :

- Salto : Salto est une bibliotheque de fonctions permettant d’analyser du code source enassembleur pour en extraire les informations semantiques sous une forme exploitable en C++.Ces informations peuvent etre de differentes natures : Il est possible de connaıtre le decoupageen blocs de base du code source, les ressources utilisees par une instruction precise (dans notrecas, ce qui nous interesse sont les acces a la memoire et aux differents registres). De plus,une des fonctionnalite indispensable a notre realisation disponible dans Salto est la possibilited’instrumenter le code source (figure 2.4 page suivante).

- Le compilateur GCC pour processeur Sparc : Compilateur C/C++ gratuit sous licence GNU.- Le compilateur CC pour processeur Sparc : Compilateur C proprietaire de Sun disponible

seulement pour la plateforme Sparc.- Les expressions regulieres en C.

2.3.2 L’instrumentation

L’instrumentation c’est quoi ?

L’instrumentation d’instruction est un mecanisme qui consiste a inserer des instructions supple-mentaires entre les instructions du code source d’un programme deja etabli afin « d’ausculter » cedernier. Les informations qu’il est possible de recuperer par ce mecanisme sont de nature dynamiquepuisque les instructions rajoutees par instrumentation sont executees autant de fois que le sont lesinstructions appartenant au code source d’origine. Prenons comme exemple le cas d’une boucledont le corps est execute n fois, alors le code rajoute par instrumentation du code source d’originedans le corps de cette boucle sera lui aussi execute n fois. Ceci permet de savoir de facon precisequelles sont les instructions statiques qui ont ete executees par le processeur sequentiellement. Deplus, l’instrumentation permet de recuperer d’autres informations dynamiques comme les adressesdes acces a la memoire.

Dans l’exemple de la figure 2.4 page suivante, le code source original est instrumente afin derecuperer la valeur du resultat produit par l’instruction a instrumenter et pour le traiter dans lafonction fct (tmp etant par exemple un registre de debuggage dont le code source original ne faitjamais usage mais qui peut etre utilise par la fonction fct pour effectuer son traitement).

29

mov r1,r2add r2,3,r2store r2,[a0]

Code source

mov r1,r2mov r2,tmpcall fctadd r2,3,r2mov r2,tmpcall fctstore r2,[a0]load [a0],tmpcall fct

Code source instrumenté

instrumentation

Fig. 2.4 – Instrumentation de code source en assembleur

Note

Dans l’exemple de la figure 2.4, les instructions sont instrumentees apres leur execution, cequi n’est pas le cas dans notre implementation : l’instrumentation se trouve avant l’execution del’instruction pour des raisons de suivi des branchements (pour pouvoir instrumenter correctementles branchements, il est necessaire de placer le code d’instrumentation avant ceux-ci).

L’instrumentation dans notre programme

L’instrumentation, dans le cas general, permet d’inserer des instructions dans un programme. Apartir de ce concept simple, nous avons decide d’utiliser l’instrumentation pour inserer des appelsde fonctions (ecrites en C et compilees par ailleurs). De fait, les appels de fonctions en assembleurne faisant pas de sauvegarde des registres globaux (accessible de n’importe ou dans le programme).Il nous a fallu ajouter a cette instrumentation une sauvegarde de contexte avant l’appel a cettefonction puis une restauration apres (figure 2.5 page suivante). Mais ce n’est pas tout : Chaqueinstruction assembleur ayant un nombre variable d’operandes et de resultats, il nous a fallu ajouterune instruction d’appel a une fonction pour chaque operande et pour chaque resultat. De plus,chaque acces a la memoire necessitant la recuperation de l’adresse de cet acces, il nous a fallurecuperer des informations sur la valeur des registres utilises par l’instruction a instrumenter afinde savoir quelle etait l’adresse de cet acces memoire.

L’instrumentation d’une instruction dans notre programme d’evaluation de la quantite de travailinutile peut-etre resumee en sept phases :

– Sauvegarde : Une phase de sauvegarde du contexte (registres globaux, decalage de la fenetrede registres. . .).

– Debut : Une phase de creation de la structure de donnee representant une instruction (fi-gure 2.1 page 24).

– Operandes : Une phase permettant de creer les arcs vers les instructions ayant ecrit endernier dans les ressources operandes de l’instruction.

30

inst1inst2inst3

Code source

sauvegardecall fctrestaurationinst1sauvegardecall fctrestaurationinst2sauvegardecall fctrestaurationinst3

Code source instrumenté

instrumentation

Fig. 2.5 – Principe de l’instrumentation faite par le programme d’evaluation de la quantite detravail inutile

– Milieu : Une phase, utile seulement pour les instruction « save » et « restore », permettantde mettre a jour le niveau de la fenetre de registres.

– Resultats : Une phase permettant de mettre a jour l’etat des ressources en fonction desresultats produits par l’instruction.

– Fin : Une phase permettant d’evaluer l’utilite de l’instruction courante. Si cette derniere estutile, on parcour son arbre de dependance de donnee.

– Restauration : Une phase de restauration du contexte.

2.3.3 Le choix de la Plateforme

Pour choisir notre plateforme de travail, nous avons pris en compte plusieurs parametres. Nousavions le choix entre le jeu d’instruction x86 (CISC) et le jeu d’instruction Sparc (RISC). En premierlieu, l’outil mis a notre disposition (Salto) semblait plus adapte a un jeu d’instruction reduit.En effet, Salto etant base sur la reconnaissance des instructions assembleur par des expressionsregulieres, il est tres difficile de supporter un jeu d’instruction aussi vaste que le x86 d’Intel (CISC).De fait, le support d’un tel jeu d’instruction par Salto est apparu comme etant insuffisant. De plus,le travail a effectuer etant, entre autre, d’identifier les acces a la memoire, un jeu d’instructionreduit avec seulement une instruction pour le chargement et une pour le rangement en memoirenous est apparu plus simple a manipuler. Cependant, le Sparc possede quelques inconvenients qui,nous le verrons plus loin, ne nous ont pas facilite la tache. Nous avons donc decide de travailleravec un jeu d’instruction RISC pleinement supporte par Salto : le Sparc de Sun.

31

2.3.4 SPARC : Le Meilleur des Mondes ?

Le Sparc est une architecture RISC assez classique ce qui signifie que le nombre d’instructionsest assez reduit, qu’elles ont toutes la meme taille (quatre octets pour le Sparc) et que, choserelativement importante pour notre implementation, les instructions d’acces a la memoire sont aunombre de deux (load pour charger une valeur de la memoire vers un registre et store pour rangerune valeur d’un registre vers la memoire). Tout aurait ete parfait si la description du Sparc s’etaitarretee la. . .

- Le delay slot est une des particularites de l’architecture Sparc. Il s’agit d’executer l’instruc-tion qui suit immediatement une instruction de branchement avant que cette instruction debranchement ne modifie le flot de controle de l’execution du programme. Pour resumer, l’ins-truction qui se trouve dans le delay slot d’un branchement (elle se trouve juste apres dans lecode source) se comporte comme si elle se trouvait avant le branchement pour ce qui est ducontrole mais comme si elle etait apres pour ce qui est des donnees.

- L’annul bit est une autre particularite « amusante » du Sparc qui est en relation directe avec ledelay slot. Lorsqu’une instruction se trouve dans le delay slot d’un branchement dont l’annulbit est active, (be,a : la virgule et le a indique que l’annul bit est active) cette instruction nes’execute que lorsque le branchement est pris. Dans le cas contraire, l’instruction se trouvantdans le delay slot n’est pas executee (on dit qu’elle est annulee).

- La fenetre de registres tournante est une facon de pallier a la lenteur des acces a la pile lors dupassage de parametres a une fonction. En effet, le Sparc se propose de resoudre le problemedu passage de parametres a une fonction de maniere originale au moyen de cette fenetre deregistres tournante. Il s’agit de ranger les valeurs que l’on souhaite passer en parametres ala fonction qui va etre appelee dans des registres speciaux nommes registres de sortie (%o0a %o5) qui, une fois la fonction appelee, seront renommes en registres d’entree (%i0 a %i5)(cf. figure 2.6 page suivante). De cette facon, la fonction appelee peut se servir de ces valeurssans qu’elles n’aient ete recopiees dans une quelconque pile (a l’exception du cas ou la taillede la fenetre de registres tournante n’est pas suffisante).

Le delay slot

Dans notre implementation, nous avons du prendre en compte cette particularite de l’archi-tecture Sparc. En effet, afin d’instrumenter les instructions se trouvant dans le delay slot d’unbranchement, nous avons du utiliser differentes techniques consistant a « remonter » notre instru-mentation de ce type d’instructions avant le branchement. Ceci a conduit a pas mal de problemesde coherence entre la representation des instructions creees par l’instrumentation et les instructionsreellement executees.

Mais le cas ou le delay slot nous a pose le plus de probleme est celui ou il nous a fallu ajouter dessauts afin d’eviter l’execution de certaines instructions. En effet, dans ce cas, si l’instruction que l’onveut « sauter » se trouve dans le delay slot d’un branchement, il faut dupliquer cette instructiondes branchement : mettre dans le code source une version normale avec l’instruction qui se trouvaitdans son delay slot dans le code source d’origine et une seconde version du meme branchementcontenant un nop dans son delay slot. De cette facon, selon que l’instruction se trouvant dans le

32

delay slot de ce branchement doit etre executee ou non, le flot de controle est aiguillee vers l’uneou l’autre des deux versions de ce branchement. Il faut ensuite faire converger les deux versions enun meme point representant la suite du programme.

La fenetre de registres du Sparc

La fenetre de registre tournante est une des particularite du processeur Sparc. Nous allons enexpliquer rapidement le principe afin d’exposer la maniere dont nous avons traite cette particularitedans notre programme.

Registres de sortie%o0 à %o7

Registres locaux%l0 à %l7

Registres d’entrée%i0 à %i7Re

gist

res

acce

ssib

les

au n

iveau

n+1

nive

au n



Registres d’entrée%i0 à %i7

Désigne les mêmesregistres physiques



Registres d’entrée%i0 à %i7

nive

au n

+2

Désigne les mêmesregistres physiques

L’instruction « save » permet de passer d’un niveau n a un niveau n+1 (utilise generalement commeune sauvegarde de contexte avec en plus la possibilite de passer des parametres d’un contexte al’autre au niveau de la zone de recouvrement de la fenetre n et n+1).L’instruction « restore » permet de passer d’un niveau n a un niveau n-1 (utilise generalementcomme une restauration de contexte avec en plus la possibilite de passer des resultats d’un contextea l’autre au niveau de la zone de recouvrement de la fenetre n et n-1).

Fig. 2.6 – Le principe de la fenetre de registres du Sparc

Lorsque le nombre de registres utilises depasse le nombre de registres physiques reellementpresents dans le processeur, un mecanisme invisible pour l’utilisateur utilise une pile en memoirepour sauvegarder la fenetre de registres la plus ancienne et reutiliser ainsi cette derniere commeune nouvelle fenetre vierge. De cette facon, le nombre de registres virtuellement utilisables parl’utilisateur n’est limite que par la taille de la pile et non par la taille du fichier de registres dans leprocesseur. Cette fenetre est souvent representee, dans les differentes documentations sur le Sparc,de facon circulaire pour montrer que la plus ancienne fenetre et la plus recente peuvent se recouvrirsi le nombre de fenetres disponibles dans le fichier de registres est insuffisant pour l’execution d’unprogramme donne.

33

2.3.5 S’affranchir de la numerotation des registres faite par Salto

Les registres du Sparc s’organisent en deux parties. D’une part, des registres dit globaux qui secomportent de maniere classique, et d’autre part une fenetre de registres coulissante comme decritsur la figure 2.6 page precedente. Pour les registres globaux, nous avons utilise la numerotationproposee par Salto qui convenait tout a fait etant donne qu’un nom de registre designe toujours lememe registre physique.

En revanche, pour la fenetre de registres coulissante, nous avons du mettre en place notre propresysteme d’identification de registres :

En effet, Salto etant un outil qui travaille sur du code assembleur, il lui est impossible d’avoiracces a des informations concernant l’execution du programme (les seules informations disponibleau niveau de Salto sont les informations statiques sur le programme). De fait, les informationsque nous donne Salto concernant les acces aux registres sont les noms de ces registres. Il lui estimpossible de connaıtre le niveau de la fenetre de registre en un point donne du code et donc dedesigner un registre physique de maniere unique. Afin d’identifier de maniere unique chacun desregistres physiques, il a donc fallu s’affranchir du systeme de numerotation des registres proposepar Salto pour le remplacer par un calcul fait de maniere dynamique (au cours de l’execution duprogramme) permettant de savoir a quel registre physique correspondait chaque acces a un registreappartenant a la fenetre de registre courante.

Pour ce faire, nous avons instrumente les instructions save qui decalent la fenetre de registrevers le haut et les instructions restore qui decalent la fenetre de registre vers le bas (cf. figure 2.6page precedente). De cette facon, il est possible de tenir a jour une variable globale indiquant leniveau actuel de la fenetre de registre. En utilisant ce niveau comme decalage par rapport a unpoint de reference, (la premiere fenetre disponible lors du lancement du programme) il est possiblede savoir dans quelle fenetre de registre seront fait les acces aux registres de la fenetre couranteindiques par Salto.

Grace a cette methode, il est possible d’identifier de maniere unique chacun des registres d’unefenetre precise meme si celle-ci peut avoir ete sauvegardee dans la pile par manque de place dansle fichier de registres. Les acces a ces registres restent ce qu’ils sont puisque cette operation esttransparente pour l’utilisateur du processeur (en l’occurrence notre programme).

2.3.6 Les expressions regulieres

L’utilisation des expressions regulieres est particulierement utile pour analyser une chaıne decaracteres ayant un motif fixe et une partie variable. C’est justement le cas d’une instructionassembleur dont la partie fixe est le mnemonique de cette instruction et dont les parties variablessont les arguments.

De cette facon, nous avons utilise les expressions regulieres pour « decouper » les instructionsload et store en plusieurs parties : le mnemonique d’une part (permettant de connaıtre la taille del’acces a la memoire : octet, mot, double mot ou quadruple mot) et les arguments d’autre part. Une

34

fois chaque argument recupere, il est possible d’acceder aux valeurs contenues dans les registreset aux eventuelles constantes. Il est donc possible de connaıtre de facon exacte a quelle adressememoire va acceder l’instruction et a combien d’octets elle va acceder.

De plus, les expressions regulieres nous ont ete utiles pour recuperer les etiquettes des appelsde fonctions afin de savoir si ces fonctions etaient definies en local (dans le code source du pro-gramme etudie) ou si elles appartenaient a une bibliotheque externe au programme (stdio en Cpar exemple).

2.3.7 La gestion des fonctions

Une fois notre definition implementee et testee, il reste encore de nombreux problemes a resoudrepour pouvoir confronter cet algorithme au « monde reel » (a des programmes classiques tel quegzip). En effet, ce modele theorique serait parfait si l’ensemble du code source assembleur d’uneapplication etait visible par le programme d’evaluation. Or les programmes classiques utilisent desfonctions definies dans des bibliotheques dont on n’a pas le code source (Un programme en Ctravaillant sur des fichiers utilisera par exemple stdio pour lire et ecrire dans un fichier). Afin deregler cette difficulte, nous avons du utiliser l’options de compilation -SO de cc permettant de savoirquels sont les registres du Sparc et les adresses memoires utilisees dans la pile comme parametreslors de l’appel a une fonction. Ainsi, il nous a ete possible de rajouter « artificiellement » des arcsde dependance entre l’appel a une fonction definie dans une bibliotheque externe (call printfpar exemple) et les parametres passes a cette fonction. Pour cette raison, cc pour Sparc est apparucomme etant ideal dans notre protocole de test.

Afin de resoudre ce probleme, les fonctions appelees par le programme etudie ont ete classeesen trois categories, chacune correspondant a un traitement particulier a faire pour les prendre encompte correctement :

Les fonctions « internes »

Les fonctions internes sont les fonctions dont le code source est disponible (peut-etre utilise parnotre programme d’evaluation). Les appels a ce type de fonctions peuvent donc etre traites commede simple branchements inconditionnels puisque les arcs du graphe de dependance peuvent tres bienrelier une instruction appartenant a cette fonction a une instruction appartenant au programmeappelant. Le graphe de dependance de donnee n’est donc pas interrompu par un tel appel defonction.

Les fonctions « externes » utilisant des pointeurs

Les fonctions externes sont les fonctions dont le code source n’est pas disponible (code sourced’une bibliotheque d’entree/sortie par exemple). Dans ces cas la, il est necessaire de considerer queles parametres passes a la fonction sont lus par l’instruction d’appel de la fonction et que le resultat

35

est ecrit par cette instruction.

Cependant, dans le cas general, il est necessaire de detourner l’appel a une telle fonction pourfaire ajouter « artificiellement » des arcs de dependance de donnee pour traiter les donnees quivont etre lues et ecrites a l’interieur de cette fonction. En effet, notre programme est incapablede connaıtre le type des parametres d’une fonction (si il s’agit d’entiers, de pointeurs. . .) et donc,de savoir si une fonction definie dans une bibliotheque dont on n’a pas le code source accede ounon a une zone memoire dont l’adresse est un de ses parametres. De plus, meme en sachant qu’unparametre est un pointeur, rien ne dit si la fonction dont on n’a pas le code source va y accederen lecture, en ecriture ou pire encore, a combien d’elements elle va acceder ! (Il ne faut pas oublierqu’en C les tableaux sont implicites et que, par consequent, on ne connaıt pas leur taille simplementen connaissant l’adresse de leur premier element). Afin de regler cette difficulte, nous avons choisi dedetourner les appels a ces fonctions (au nombre de trente cinq dans gzip) afin de leur faire executerdu code permettant de simuler leur comportement en matiere d’acces a la memoire. Ces fonctionssont, le plus souvent des fonctions d’entrees/sorties (ex : read, write, fflush. . .), des fonctions delecture/ecriture dans des chaınes de caracteres (ex : strcat, strcpy, strcmp. . .) ou des fonctionsde lecture/ecriture de zones memoire en general (ex : memset, memcpy, memcmp. . .).

Exemple simple :

char *my_strcpy(char *c1, const char *c2){

/* On simule un acces en lecture a une zone memoire debutant a l’adressecontenue dans le pointeur c2 et de longueur strlen(c2)+1 (taille de lachaıne de caractere a lire avec son terminateur) */instrumentationEntreeMemoire((int)c2, strlen(c2)+1);

/* On simule un acces en ecriture a une zone memoire debutant a l’adressecontenue dans le pointeur c1 et de longueur strlen(c2)+1 (taille de lachaıne de caractere a copier avec son terminateur) */instrumentationSortieMemoire((int)c1, strlen(c2)+1);

/* On retourne la valeur retournee par la vraie fonction strcpy */return strcpy(c1, c2);

}

Les fonctions « externes » n’utilisant pas de pointeurs

Les fonctions externes n’utilisant pas de pointeurs sont des fonctions dites externes d’apres ladefinition ci-dessus a la difference qu’elles ne font pas d’acces a la memoire a partir de pointeur.Elles peuvent donc etre traitees simplement en considerant que les parametres passes a la fonctionsont lus et que le resultat est ecrit.

36

2.4 Resultats & Analyse

2.4.1 Les chiffres. . .

Une fois l’evaluation de la quantite de travail inutile effectuee de cette maniere, nous obtenonsles chiffres suivants (cf. figure 2.7).

gzipa gzipb gzipc

O0d 11.03 % 9.53 % 11.03 %O1 12.05 % 10.73 % 16.44 %O2 11.40 % 10.28 % 16.17 %O3 12.77 % 12.10 % 21.83 %O4 12.66 % 12.55 % 23.35 %O5 12.66 % 12.55 % 23.35 %

gunzipe gunzipf gunzipg

O0 1.09 % 1.14 % 0.21 %O1 2.94 % 3.10 % 0.29 %O2 3.51 % 4.28 % 0.41 %O3 10.01 % 10.51 % 0.47 %O4 9.83 % 10.26 % 0.52 %O5 9.83 % 10.26 % 0.52 %

aCompression d’un fichier texte (RTF) de 2127 octets avec gzip (fort taux de compression (facteur : 1.9))bCompression d’un fichier image (GIF) de 1704 octets avec gzip (faible taux de compression (facteur : 1.4))cRe-compression d’un fichier compresse par gzip de 1506 octets avec gzip (taux de compression nul (facteur : 0.98))dSeuls ces resultats ont ete valides avec le programme de verification pour des raisons d’implementationeDecompression du fichier texte de 2127 octetsfDecompression du fichier image de 1704 octetsgDecompression du fichier compresse deux fois par gzip de 1506 octets

Conditions de test : gzip version 1.2.4 recompile avec cc de Sun pour le processeur Sparc versionv8plus. Ces chiffres s’entendent en ne comptant pas les eventuelles instructions nop qui se trouventdans le delay slot de certaines instructions de branchement.

Fig. 2.7 – Quantite d’instructions assembleurs inutiles lors de l’execution de gzip dans differentesconditions

2.4.2 Le doute. . .

Introduction

Ces chiffres n’etant qu’une evaluation, rien ne permet de dire avec certitude que ce travail esteffectivement inutile. D’autant plus que l’implementation laisse souvent apparaıtre des failles quel’on n’imagine pas lorsqu’on raisonne de facon abstraite sur les dependances de donnees (la gestiondes fonctions dont on n’a pas le code source en est un exemple). Afin de valider notre programmeet d’avoir la certitude que le travail inutile evalue en etait bien, nous avons mis au point un secondprogramme re-executant exactement le meme programme de test (gzip dans notre cas) sur le memejeu de donnees (avec le meme fichier en entree) en n’executant pas les instructions qui avaient etejugees comme etant inutiles lors de la premiere execution. Ainsi, si la seconde execution donnerigoureusement le meme resultat que la premiere (le meme fichier compresse dans le cas de gzip),nous pouvons dire que les deux executions sont equivalentes et que, par consequent, les instructionsqui n’ont pas ete executees lors de la seconde execution n’etaient effectivement pas utiles.

37

somewhere :sub r3,r4,r5...

mov r1,r2add r2,3,r2cmp 0,r2be somewherestore r2,(a0)...

Code source

mov r1,r2add r2,3,r2cmp 0,r2be somewheresub r3,r4,r5...

Trace dynamique de la première exécution

(détection du travail inutile)

Trace dynamique de la deuxième exécution (non

exécution du travail inutile)

mov r1,r2add r2,3,r2cmp 0,r2be somewherestore r2,(a0)...

L'instruction add est jugée inutile :elle ne sera donc pas exécutée

lors de la seconde exécution

Fig. 2.8 – Mise en evidence d’un probleme d’implementation par divergence du flot de controle

Note

Reproduire une execution a l’identique ne fonctionne que sur un programme deterministe : deuxexecutions successives sur un meme jeu de donnee doivent s’executer rigoureusement de la mememaniere. De fait, il serait complexe de traiter des programmes utilisant des fonctions de tiragesaleatoires ou conservant des informations d’une execution sur l’autre (cache dans un fichier parexemple). Ce n’est pas le cas de gzip ce qui nous a permis de mener nos tests de facon correctesur ce programme.

L’interet

Un aspect tres interessant de l’utilisation de ce programme de verification est qu’il a permisd’affiner le programme d’evaluation de la quantite de travail inutile. En effet, en observant lesdivergences entre la premiere et la seconde execution (figure 2.8), il a ete possible de trouver lespoints faibles du programme d’evaluation de la quantite de travail inutile et de les consolider afin derendre les deux executions equivalentes. Par exemple, lorsque la seconde execution du programmede test divergeait de la premiere (un branchement pris alors qu’il n’aurait pas du par exemple), celasignifiait qu’une instruction utile au flot de controle avait etait jugee comme etant inutile a tort. Decette maniere, il a ete possible de trouver les incorrections du programme d’evaluation du travailinutile et surtout de mettre en lumiere les lacunes d’une implementation trop « naıve » par rapportaux appels de fonctions definies dans des bibliotheques dont le code source n’est pas disponible.

Dans l’exemple de la figure 2.8, le branchement be (branch if equal) est pris lors de la premiereexecution alors qu’il n’est pas pris lors de la seconde, ce qui entraıne une incoherence entre les deux

38

executions qui ne sont alors plus equivalentes. Ceci se produit en raison d’un mauvais jugementporte sur l’instruction add. En effet, celle-ci est utile au bon deroulement du programme alorsqu’elle a ete jugee comme ne l’etant pas par le programme de detection du travail inutile. Grace ace systeme, il est facile de corriger les incorrections et imprecisions que comporte le programme dedetection du travail inutile. Par processus incremental, il est alors possible de corriger ces erreursune a une jusqu’a l’obtention d’un programme qui ne juge inutile que du travail reellement inutile(Ce qui ne prouve pas pour autant qu’il detecte tout le travail inutile que peut comporter unprogramme).

La Methode

Pour pouvoir mettre au point ce deuxieme programme, il faut tout d’abord que le programmed’evaluation de la quantite de travail inutile laisse une trace des instructions inutiles dans unfichier qui sera utilise par le programme de verification. Pour la mise au point de ce programme deverification, Salto a, la encore, ete sollicite afin d’instrumenter chaque instruction. Lorsque cetteinstruction est jugee inutile (d’apres la trace de la premiere execution) alors cette instruction estsautee au moyen d’un jump d’une valeur constante puisque, dans les processeurs Sparc, toutes lesinstructions ont une taille de quatre octets (« merci » les jeux d’instructions RISC). De cette facon,il est assez facile de « sauter » une instruction lorsqu’elle apparaıt dans la trace des instructionsinutiles.

Conclusion

Ce programme a permis, sur des exemples simples, de verifier que la quantite de travail inutileevaluee etait bien du travail inutile quelque soit le niveau d’optimisation utilise et les cas de figurerencontres. Cependant, par manque de temps, nous n’avons reussi a le faire fonctionner que sur gzipcompile avec un niveau d’optimisation de 0. Neanmoins, cette verification nous a permis d’accroıtrela confiance en nos resultats (figures 2.7 page 37 et 2.9 page suivante).

2.4.3 La repartition du travail inutile

Une fois les informations sur le travail inutile lors de l’execution d’un programme recuperees,il est necessaire de les organiser afin de pouvoir analyser d’ou provient ce travail inutile. Dansun premier temps, nous avons essaye de voir a quelles instructions statiques correspondaient nosinstructions dynamiques inutiles. Nous avons trouve, sans surprise etant donne les resultats del’article [1], que seul un petit nombre d’instructions statiques etaient concernees. Ce qui signifieque la plupart des instructions dynamiques inutiles sont concentrees sur un nombre d’instructionsstatiques reduit (de l’ordre de 12.4 % des instructions statiques totales generent au moins uneinstance dynamique inutile). Une fois ces instructions statiques en assembleur identifiees, nousavons cherche a « remonter », lorsque c’etait possible, au code source en C correspondant afinde mieux comprendre la raison pour laquelle ce travail est juge comme etant inutile par notredefinition.

39

0.0 268685.0 537370.0 806055.0 1074740.00.0

18146.0

36292.0

54438.0

72584.0

90730.0

108876.0

Compression d’un fichier RTF de 2127 octetsAlgorithme GZIP compile avec cc et un niveau d’optimisation de 0

(a) Sans optimisations de compilation

0.0 105695.0 211390.0 317085.0 422780.00.0

8898.0

17796.0

26694.0

35592.0

44490.0

53388.0

Compression d’un fichier RTF de 2127 octetsAlgorithme GZIP compile avec cc et un niveau d’optimisation de 5

(b) Avec optimisations de compilation

Abscisse : Numero d’instruction dynamiques : represente le temps ecoule en nombre d’instructions

Ordonnee : Quantite d’instructions inutiles (cumulees)

Fig. 2.9 – Evolution de la quantite de travail inutile en fonction du temps

Travail inutile algorithmique

Introduction En observant les courbes de la figure 2.9 on s’apercoit que l’algorithme de gzip,dans nos conditions de test, se decompose en plusieurs phases generant chacune des quantites detravail inutile differentes. En premier lieu, il est interessant de noter que la phase d’initialisationcomporte une grande proportion de travail inutile (presque 50 % avec un niveau d’optimisationde 0 et plus de 50 % avec un niveau de 5). Ensuite, vient une courte phase durant laquelle aucuntravail inutile n’est present (quelque soit le niveau d’optimisation).

Vient ensuite un ensemble de phases que nous appellerons le cœur de l’algorithme durant lequelon observe une quantite de travail inutile moyen non negligeable avec un niveau d’optimisation de0 (de l’ordre de 6,9 %) et plus important encore avec un niveau d’optimisation de 5 (de l’ordre de9,9 %).

La phase d’initialisation Dans certains cas, le travail inutile semble etre d’origine algorith-mique. En effet, en observant le code source en C de gzip, il apparaıt parfois du travail inutile qu’ilserait simple d’eviter en modifiant une petite partie du code. De fait, nous pouvons dire que cetravail inutile est inherent a la facon dont l’algorithme de gzip est implemente.

De plus, etant donne une tres forte proportion de travail inutile durant la phase d’initialisationdes structures de donnees utiles a l’algorithme de gzip (aux alentours de 50%), il semble raisonnablede penser qu’une tres grande partie de ces structures de donnees sont initialisees puis jamais utiliseesou reutilisees pour etre ecrites (ce qui genere des valeurs mortes). Ce type de travail inutile semble

40

etre reellement inherent a l’algorithme et non du a une mauvaise implementation de celui-ci.

Exemple simple :

Dans la fonction local void gen codes (tree, max code), on observe que le code sourcesuivant est inutile la plupart du temps (lors de l’execution sur un fichier de test) :

for (bits = 1; bits <= MAX_BITS; bits++) {next_code[bits] = code = (code + bl_count[bits-1]) << 1;

}

L’affectation dans le tableau next code est inutile 52 fois sur 60 dans l’exemple teste (le nombred’iterations de la boucle est MAX BITS et est egal a 60). Le fait que cette affectation soit inutile uncertain nombre de fois engendre qu’une partie des calculs fait dans la boucle devient inutile. Cequi nous donne, pour l’ensemble de la boucle, un nombre de 824 instructions inutiles pour 1440 autotal (soit une proportion de 57 %).

Etant donne ces resultats, il est interessant de se pencher sur le cas de l’initialisation desstructures de donnees en general. En effet, le premier reflexe d’un programmeur, lorsqu’il declareune structure de donnee (tableau, liste. . .) est de l’initialiser pour eviter, par la suite, d’y faireun acces en lecture sans y avoir prealablement range une valeur. Or ce reflexe de programmationest probablement ce que nous observons ici etant donne que les structures de donnees de gzipn’echappent apparemment pas a cette regle.

Le cœur de l’algorithme Au cœur de l’algorithme, nous observons differents cas d’instructionsdynamiques inutiles. Parfois, nous observons que le travail inutile est du a l’initialisation de va-riables locales dont le contenu est, la plupart du temps, re-ecrit avant d’etre lu. Parfois, il s’agit deparametres passes a une fonction et qui ne servent que dans certaines conditions. Et enfin, un casassez frequent egalement est celui des variables globales qui sont maintenues a jour de facon inutile.En effet, si une telle variable reflete une valeur lors du dernier passage dans une certaine fonction,il est possible que cette fonction soit appelee plusieurs fois sans que cette valeur n’ai ete lue entretemps.

Exemples :

L’affectation prev match = match start ; peut-etre inutile car la seule utilisation de la variableprev match en lecture est le cas suivant :

if (prev_length >= MIN_MATCH && match_length <= prev_length) {check_match(strstart-1, prev_match, prev_length);flush = ct_tally(strstart-1-prev_match, prev_length - MIN_MATCH);...

}

41

Ce qui signifie que lorsque la condition ci-dessus sera fausse, l’affectation de la variable prev matchsera inutile (c’est le cas 78 fois 82 dans notre test). En supposant que le calcul de la valeur de lavariable match start puisse etre couteux, et que cette variable ne soit pas re-utilisee en lectureentre temps, on prend conscience de la portee que peut avoir le travail inutile.

Note

Dans l’exemple precedent, il est interessant de noter que le deplacement de l’instruction d’affec-tation prev match = match start ; dans le corps de la conditionnelle aurait suffit a eliminerce travail inutile (dans la mesure ou on ne fait pas d’ecriture dans match start entre temps).En effet, la variable prev match n’etant utilisee que dans ce bloc, il est inutile de faire cetteaffectation si la condition n’est pas vraie.

Une macro un peu particuliere a egalement retenu notre attention. Elle se trouve au cœur del’algorithme de compression, dans la fonction deflate(). Il s’agit de la macro INSERT STRING quiinsere une chaıne de caractere dans la liste des chaınes de caracteres qu’utilise gzip pour trouverles chaınes les plus frequemment presentes dans le fichier a compresser.

Voici le code de cette macro apres passage du pre-processeur :

((ins_h = (((ins_h)<<((15+3-1)/3)) ^( window[(strstart) + 3-1])) &((unsigned)(1<<15)-1)),

prev[(strstart) & (0x8000-1)] = hash_head = (prev+0x8000)[ins_h],(prev+0x8000)[ins_h] = (strstart));

Pour des raisons de lisibilite, nous avons re-ecrit ce code :

ins_h = ( ins_h<<5 ^ window[strstart+2] & (unsigned)(1<<15)-1 );hash_head = (prev+0x8000)[ins_h];prev[strstart & (0x8000-1)] = hash_head;(prev+0x8000)[ins_h] = strstart;

Dans cette macro, qui se trouve au cœur de l’algorithme de compression, les deux dernieresinstructions (remplissage du tableau prev) se trouvent etre tres souvent inutile (77 fois sur 82 dansnotre exemple). Ceci tend a montrer que l’algorithme de compression utilise par gzip contient, parnature, du travail inutile.

Travail inutile introduit par le compilateur. . .

. . . lors des phases d’optimisation de compilation On observe egalement que la versioncompilee avec un niveau d’optimisation de 0 presente une quantite globale de travail inutile moinsimportant (proportionnellement) a la version compilee avec un niveau d’optimisation de 5. De plus,

42

l’ecart entre les deux versions s’accentue dans le cœur de l’algorithme. En effet, durant la phased’initialisation, les deux versions se comportent a peu pres de la meme facon (aux alentours de50 % de travail inutile) alors que dans le cœur de l’execution, la version non optimisee comporte enmoyenne 6.9 % de travail inutile a comparer aux 9.9 % observe dans le cas de la version optimisee.Ce phenomene avait deja ete constate dans l’article [1] mais uniquement au sujet des valeurs mortes.

. . . du au jeu d’instruction du processeur Cette etude n’est absolument pas exhaustive surles diverses causes que peut avoir le travail inutile. Cependant, meme si cet aspect n’a pu etreexplore pour des raisons de temps, il parait raisonnable de penser qu’une partie du travail inutilepourrait avoir ete introduit en raison des contraintes imposees par le jeu d’instructions utilise. Eneffet, dans un jeu d’instruction RISC (comme le Sparc) une instruction de haut niveau (en langageC par exemple) peut etre convertie par le compilateur en une suite tres importante d’instructionscomme en une seule. Ceci depend de l’eloignement de cette instruction en langage C par rapport auxinstructions disponibles dans le jeu d’instruction assembleur utilise. A contrario, un jeu d’instructionCISC (comme le x86) aura des instructions assembleur plus proche des instructions en langage dehaut niveau. De cette facon, les proportions d’instructions assembleur inutiles peuvent ne pas etreidentiques aux proportions d’instructions inutiles de haut niveau (en langage C par exemple).De plus, certaines optimisations de compilation effectuant un re-ordonnancement des instructionsassembleur, il est parfois difficile de savoir quel ensemble d’instructions assembleur represente quelleinstruction de haut niveau.

Conclusion

En conclusion, nous pouvons dire que les proportions de travail inutile trouvees se rattachentmajoritairement au travail inutile present dans l’algorithme en langage de haut niveau. De fait, unepiste qui pourrait etre interessante pour reduire ce travail inutile serait de signaler au programmeur,lors des premieres executions d’un prototype de programme, que certaines parties de l’algorithmegenerent une grande quantite de travail inutile et que, par consequent, une re-ecriture en prenant encompte cet etat de fait pourrait eviter ce travail. Il est meme possible d’imaginer un outil proposantau programmeur une ebauche de solution pour l’aider a restructurer une partie de son code afind’eviter ce travail inutile. Cependant, ce type d’outils ne peut rien pour aider a eliminer le travailinutile intrinseque a l’algorithme.

43

2.5 Conclusion

Cette etude est, en premier lieu, une etude permettant de comprendre un phenomene, a priori,contre intuitif : Le travail inutile. Pour ce faire, nous nous sommes base sur des resultats existantsqui ont deja ete publies et qui montre que le travail inutile existe bel et bien dans des programmesclassiques.

Le but de ce stage etait d’elargir les definitions donnees dans ces articles afin d’avoir uneidee du travail inutile global qui peut se trouver dans un programme. Cette etude, contrairementa celles citees ci-contre, n’avait pas pour but de trouver un moyen d’exploiter ce travail inutilepour en reduire l’impact sur le temps d’execution ou la consommation electrique mais seulementde comprendre ce phenomene et de savoir pourquoi ce travail inutile est present (est-ce du aucompilateur ?, au programmeur ?. . .).

En conclusion, nous pouvons dire que cette etude a permis de confirmer l’existence du travailinutile et de comprendre, en partie, d’ou il provient.

44

Bibliographie

[1] G. Sohi A. Butt. Dynamic dead-instruction detection and elimination. ASPLOS X, October2002.

[2] Jeffrey D. Ullman Alfred V. Aho, Ravi Sethi. Compilers : Principles, Techniques and Tools.Addison-Wesley, 1986.

[3] Gordon B. Bell. Characterization of silent stores. Submitted in partial fulfillment of the M.S.Degree in Electrical and Computer Engineering, May 2001.

[4] F. Bodin. Cours d’optimisation : Transformer pour la performance. Septembre 2002.

[5] M. Lipasti K. Lepak, G. Bell. Silent stores and store value locality. IEEE Transactions onComputers, 50(11), November 2001.

[6] Mikko H. Lipasti Kevin M. Lepak. Temporally silent stores. ASPLOS X, October 2002.

[7] Kevin M. Lepak. Silent stores for free : Reducing the cost of store verification. Submitted inpartial fulfillment of the M.S. Degree in Electrical and Computer Engineering, December 2000.

[8] Charles N. Fischer Milo M. Martin, Amir Roth. Exploiting dead value information. Proceedingsof Micro-30, December 1997.

45

Chapitre 3

Annexes

3.1 Petit historique du stage. . .

11/2002 : Elaboration de la bibliographie : Recherche et lecture d’articles sur le travail inutile.

12/2002 : Elaboration de la bibliographie : Redaction du rapport bibliographique et reflexionautour de la partie personnelle a ajouter (Troisieme approche du chapitre Bibliographie).

02/2003 : Debut du stage : Prise en main de l’environnement de travail (C++, gcc, cc, conceptgeneraux de compilation. . .) et de l’outils Salto mis a disposition par l’equipe.

03/2003 : Elaboration du squelette de l’application d’evaluation du travail inutile et mise aupoint d’un programme simple permettant de construire le graphe de dependance de donneeen utilisant l’outil Salto.

04/2003 : Implementation et test sur gzip du programme d’evaluation de la quantite de travailinutile et mise au point du programme de verification que ce travail est bien inutile.

05/2003 : Test du protocole, optimisation, collecte des resultats, et ecriture du rapport de stage.

06/2003 : Fin du rapport et presentation orale du travail effectue en stage

46

3.2 A propos de la description machine Salto du Sparc

3.2.1 Gestion des instructions Save et Restore

Les instructions save et restore du Sparc possedent trois arguments (generalement save%sp,constante,%sp et restore %g0,%g0,%g0). Ces deux instructions font glisser la fenetre deregistre dans le sens positif pour save (creation d’un nouveau contexte) et dans le sens negatifpour restore (restauration de l’ancien contexte). De plus, ces instructions se comportent commel’instruction add a un detail pres : les registres lus (deux premiers arguments) sont lus dans l’an-cienne fenetre de registres alors que le registre ecrit (troisieme argument) est ecrit dans la nouvellefenetre (apres la creation ou la restauration du contexte). Or la description machine Salto du Sparcconsidere que les trois registres passes en argument des instructions save et restore sont lus alorsque le troisieme est ecrit (erreur invisible dans la mesure ou save et restore ecrivent aussi tous lesregistres de la fenetre. . . sauf lorsqu’on utilise comme troisieme argument un registre n’appartenantpas a la fenetre (registre global par exemple)).

3.2.2 L’instruction call & link

L’instruction call sert a faire un appel de fonction. Cette instruction effectue deux actions :elle branche a l’adresse passee en parametre (constante sur 30 bits) et elle sauvegarde la valeurdu PC au moment de son execution dans le registre %o7 (registre 15 dans le manuel du Sparc),permettant ainsi a la fonction appelee de revenir a la suite dans le code source une fois la fonctionexecutee au moyen de l’instruction ret. Or cette deuxieme fonction n’est pas vue par la descriptionmachine Salto du Sparc. Il faut donc rajouter une ecriture dans le registre %o7 dans la definitionde l’instruction call pour la rendre correcte.

3.2.3 L’instruction addx

L’instruction addx a le meme effet que l’instruction add a ceci pret qu’elle utilise le registre descodes conditions pour ajouter, si elle est positionnee, la retenue de celui-ci (bit carry) au resultatde l’addition. Or dans la description machine Salto du Sparc, l’instruction addx est vue commeetant equivalente a l’instruction addcc qui, elle, positionne le bit carry en fonction des argumentspasses a l’instruction addcc. Donc, l’instruction addx lit le registre des codes condition alors quel’instruction addcc le modifie. L’instruction addx n’est utilisee par les compilateurs que lorsqu’onactive les optimisations de compilation.

3.2.4 Un detail : les instructions nop, ba et bn

D’apres la description machine Salto du Sparc, l’instruction nop (No operation) consommeraitun registre en entree (dont le numero d’identification dans la description machine est 39). Or,d’apres la documentation sur le Sparc, l’instruction nop ne fait aucune action donc elle ne devrait

47

pas utiliser de ressources en entree. De plus, les instructions ba (Branch always) et bn (Branchnever) utilisent, d’apres la description machine du Sparc, le registre des codes condition en entree.Or, si les instructions de branchement conditionnel utilisent en effet le registre des codes condition,les instructions ba et bn peuvent etre considerees comme des instructions de branchement incon-ditionnel puisque le fait que le branchement ai lieu ne depend pas des bits actives dans le registredes codes condition.

48

3.3 Resultat de l’evaluation du travail inutile sur un exemplesimple

3.3.1 Code source en C de l’exemple

1 #include <stdio.h>234 int main(void)5 {6 int tab[3],i;789 for(i=0; i<3; i++) tab[i]=i*10;1011 printf("%d",tab[1]);1213 exit(0);14 }

3.3.2 Code source en assembleur Sparc de l’exemple

Ce code est genere par le compilateur cc avec les options ”-SO” et ”-XO0” (niveau d’optimisationegal a 0).

! FILE exemple.c

! 1 !#include <stdio.h>! 4 !int main(void)! 5 !{

!! SUBROUTINE main!! OFFSET SOURCE LINE LABEL INSTRUCTION

.global mainmain:

/* 000000 5 */ save %sp,-120,%sp

! 6 ! int tab[3],i;! 9 ! for(i=0; i<3; i++) tab[i]=i*10;

49

.L90:/* 0x0004 9 */ or %g0,0,%g2/* 0x0008 */ st %g2,[%fp-20]/* 0x000c */ ld [%fp-20],%g3/* 0x0010 */ cmp %g3,3/* 0x0014 */ bl .L95/* 0x0018 */ nop/* 0x001c */ ba .L94/* 0x0020 */ nop

.L95:

.L92:/* 0x0024 9 */ ld [%fp-20],%g2/* 0x0028 */ sll %g2,2,%g3/* 0x002c */ add %g3,%g2,%g4/* 0x0030 */ sll %g4,1,%o2/* 0x0034 */ ld [%fp-20],%o3/* 0x0038 */ sll %o3,2,%o4/* 0x003c */ add %fp,-16,%o3/* 0x0040 */ st %o2,[%o4+%o3] ! volatile/* 0x0044 */ ld [%fp-20],%o4/* 0x0048 */ add %o4,1,%o5/* 0x004c */ st %o5,[%fp-20]/* 0x0050 */ ld [%fp-20],%o7/* 0x0054 */ cmp %o7,3/* 0x0058 */ bl .L92/* 0x005c */ nop/* 0x0060 */ ba .L96/* 0x0064 */ nop

.L96:

! 10 ! printf("%d\n",tab[1]);

.L94:/* 0x0068 10 */ sethi %hi(.L97),%g2/* 0x006c */ add %g2,%lo(.L97),%g3/* 0x0070 */ or %g0,%g3,%g4/* 0x0074 */ or %g0,%g4,%o0/* 0x0078 */ ld [%fp-12],%o2/* 0x007c */ or %g0,%o2,%o1/* 0x0080 */ call printf ! params = %o0 %o1 ! Result =/* 0x0084 */ nop

! 11 !! 12 ! exit(0);

/* 0x0088 12 */ or %g0,0,%o3/* 0x008c */ or %g0,%o3,%o0/* 0x0090 */ call exit ! params = %o0 ! Result =

50

/* 0x0094 */ nop/* 0x0098 */ ba .L89/* 0x009c */ nop

.L89:/* 0x00a0 */ ret ! Result =/* 0x00a4 */ restore %g0,%g0,%g0/* 0x00a8 0 */ .type main,2/* 0x00a8 0 */ .size main,(.-main)/* 0x00a8 0 */ .global __fsr_init_value/* 0x00a8 */ __fsr_init_value=0

3.3.3 Identifiant d’instruction statique

Ce fichier texte est obtenu apres passage de Salto sur le code source en assembleur de notreexemple. Le numero statique permettant d’identifier une instruction se trouve entre crochets.

Salto rev. 1.4.2beta1 (built with g++ on sun4u)Copyright (C) 1997 Inria, France

Machine description file ok.CFG (0) :

BB (0) :INST (0) [1] : save %o6,-120,%o6 in : 55 out : 55

BB (1) :INST (0) [2] : or %g0,0,%g2 in : 41 out : 43INST (1) [3] : st %g2,[%i6-20] in : 71 in : 43 out : 113INST (2) [4] : ld [%i6-20],%g3 in : 71 in : 113 out : 44INST (3) [5] : subcc %g3,3,%g0 in : 44 out : 74 out : 41INST (4) [6] : bl .L95 in : 74

BB (2) :INST (0) [7] : nop in : 39INST (1) [8] : ba .L94 in : 74

BB (3) :INST (0) [9] : nop in : 39

BB (4) :INST (0) [10] : ld [%i6-20],%g2 in : 71 in : 113 out : 43INST (1) [11] : sll %g2,2,%g3 in : 43 out : 44INST (2) [12] : add %g3,%g2,%g4 in : 44 in : 43 out : 45INST (3) [13] : sll %g4,1,%o2 in : 45 out : 51INST (4) [14] : ld [%i6-20],%o3 in : 71 in : 113 out : 52INST (5) [15] : sll %o3,2,%o4 in : 52 out : 53INST (6) [16] : add %i6,-16,%o3 in : 71 out : 52INST (7) [17] : st %o2,[%o4+%o3] in : 53 in : 52 in : 51 out : 113INST (8) [18] : ld [%i6-20],%o4 in : 71 in : 113 out : 53INST (9) [19] : add %o4,1,%o5 in : 53 out : 54

51

INST (10) [20] : st %o5,[%i6-20] in : 71 in : 54 out : 113INST (11) [21] : ld [%i6-20],%o7 in : 71 in : 113 out : 56INST (12) [22] : subcc %o7,3,%g0 in : 56 out : 74 out : 41INST (13) [23] : bl .L92 in : 74


BB (6) :INST (0) [26] : nop in : 39

BB (7) :INST (0) [27] : sethi %hi(.L97),%g2 out : 43INST (1) [28] : add %g2,%lo(.L97),%g3 in : 43 out : 44INST (2) [29] : or %g0,%g3,%g4 in : 41 in : 44 out : 45INST (3) [30] : or %g0,%g4,%o0 in : 41 in : 45 out : 49INST (4) [31] : ld [%i6-12],%o2 in : 71 in : 113 out : 51INST (5) [32] : or %g0,%o2,%o1 in : 41 in : 51 out : 50

BB (8) :INST (0) [33] : call printf out : 56

BB (9) :INST (0) [34] : nop in : 39INST (1) [35] : or %g0,0,%o3 in : 41 out : 52INST (2) [36] : or %g0,%o3,%o0 in : 41 in : 52 out : 49

BB (10) :INST (0) [37] : call exit out : 56


BB (12) :INST (0) [40] : nop in : 39

BB (13) :INST (0) [41] : jmpl %i7+8,%g0 in : 72 out : 41

BB (14) :INST (0) [42] : restore %g0,%g0,%g0 in : 41 in : 41 out : 41

3.3.4 Trace d’execution dynamique

La trace d’execution dynamique de ce programme de test est donnee par le programme d’evaluationde la quantite de travail inutile.

I.Dynamic 66 -- I.Static 38 -- File 1 -- nop -- Depend de 0I.Dynamic 65 -- I.Static 37 -- File 1 -- utile -- Depend de 64I.Dynamic 64 -- I.Static 36 -- File 1 -- utile -- Depend de 63I.Dynamic 63 -- I.Static 35 -- File 1 -- utileI.Dynamic 62 -- I.Static 34 -- File 1 -- nop -- Depend de 0I.Dynamic 61 -- I.Static 33 -- File 1 -- utile -- Depend de 58,60

52

I.Dynamic 60 -- I.Static 32 -- File 1 -- utile -- Depend de 59I.Dynamic 59 -- I.Static 31 -- File 1 -- utile -- Depend de 0,30,30,30,30I.Dynamic 58 -- I.Static 30 -- File 1 -- utile -- Depend de 57I.Dynamic 57 -- I.Static 29 -- File 1 -- utile -- Depend de 56I.Dynamic 56 -- I.Static 28 -- File 1 -- utile -- Depend de 55I.Dynamic 55 -- I.Static 27 -- File 1 -- utileI.Dynamic 54 -- I.Static 26 -- File 1 -- nop -- Depend de 0I.Dynamic 53 -- I.Static 25 -- File 1 -- utile -- Depend de 50I.Dynamic 52 -- I.Static 24 -- File 1 -- nop -- Depend de 0I.Dynamic 51 -- I.Static 23 -- File 1 -- utile -- Depend de 50I.Dynamic 50 -- I.Static 22 -- File 1 -- utile -- Depend de 49I.Dynamic 49 -- I.Static 21 -- File 1 -- utile -- Depend de 0,48,48,48,48I.Dynamic 48 -- I.Static 20 -- File 1 -- utile -- Depend de 0,47I.Dynamic 47 -- I.Static 19 -- File 1 -- utile -- Depend de 46I.Dynamic 46 -- I.Static 18 -- File 1 -- utile -- Depend de 0,33,33,33,33I.Dynamic 45 -- I.Static 17 -- File 1 -- INUTILE -- Depend de 43,44,41I.Dynamic 44 -- I.Static 16 -- File 1 -- INUTILE -- Depend de 0I.Dynamic 43 -- I.Static 15 -- File 1 -- INUTILE -- Depend de 42I.Dynamic 42 -- I.Static 14 -- File 1 -- INUTILE -- Depend de 0,33,33,33,33I.Dynamic 41 -- I.Static 13 -- File 1 -- INUTILE -- Depend de 40I.Dynamic 40 -- I.Static 12 -- File 1 -- INUTILE -- Depend de 39,38I.Dynamic 39 -- I.Static 11 -- File 1 -- INUTILE -- Depend de 38I.Dynamic 38 -- I.Static 10 -- File 1 -- INUTILE -- Depend de 0,33,33,33,33I.Dynamic 37 -- I.Static 24 -- File 1 -- nop -- Depend de 0I.Dynamic 36 -- I.Static 23 -- File 1 -- utile -- Depend de 35I.Dynamic 35 -- I.Static 22 -- File 1 -- utile -- Depend de 34I.Dynamic 34 -- I.Static 21 -- File 1 -- utile -- Depend de 0,33,33,33,33I.Dynamic 33 -- I.Static 20 -- File 1 -- utile -- Depend de 0,32I.Dynamic 32 -- I.Static 19 -- File 1 -- utile -- Depend de 31I.Dynamic 31 -- I.Static 18 -- File 1 -- utile -- Depend de 0,18,18,18,18I.Dynamic 30 -- I.Static 17 -- File 1 -- utile -- Depend de 28,29,26I.Dynamic 29 -- I.Static 16 -- File 1 -- utile -- Depend de 0I.Dynamic 28 -- I.Static 15 -- File 1 -- utile -- Depend de 27I.Dynamic 27 -- I.Static 14 -- File 1 -- utile -- Depend de 0,18,18,18,18I.Dynamic 26 -- I.Static 13 -- File 1 -- utile -- Depend de 25I.Dynamic 25 -- I.Static 12 -- File 1 -- utile -- Depend de 24,23I.Dynamic 24 -- I.Static 11 -- File 1 -- utile -- Depend de 23I.Dynamic 23 -- I.Static 10 -- File 1 -- utile -- Depend de 0,18,18,18,18I.Dynamic 22 -- I.Static 24 -- File 1 -- nop -- Depend de 0I.Dynamic 21 -- I.Static 23 -- File 1 -- utile -- Depend de 20I.Dynamic 20 -- I.Static 22 -- File 1 -- utile -- Depend de 19I.Dynamic 19 -- I.Static 21 -- File 1 -- utile -- Depend de 0,18,18,18,18I.Dynamic 18 -- I.Static 20 -- File 1 -- utile -- Depend de 0,17I.Dynamic 17 -- I.Static 19 -- File 1 -- utile -- Depend de 16I.Dynamic 16 -- I.Static 18 -- File 1 -- utile -- Depend de 0,3,3,3,3I.Dynamic 15 -- I.Static 17 -- File 1 -- INUTILE -- Depend de 13,14,11I.Dynamic 14 -- I.Static 16 -- File 1 -- INUTILE -- Depend de 0I.Dynamic 13 -- I.Static 15 -- File 1 -- INUTILE -- Depend de 12

53

I.Dynamic 12 -- I.Static 14 -- File 1 -- INUTILE -- Depend de 0,3,3,3,3I.Dynamic 11 -- I.Static 13 -- File 1 -- INUTILE -- Depend de 10I.Dynamic 10 -- I.Static 12 -- File 1 -- INUTILE -- Depend de 9,8I.Dynamic 9 -- I.Static 11 -- File 1 -- INUTILE -- Depend de 8I.Dynamic 8 -- I.Static 10 -- File 1 -- INUTILE -- Depend de 0,3,3,3,3I.Dynamic 7 -- I.Static 7 -- File 1 -- nop -- Depend de 0I.Dynamic 6 -- I.Static 6 -- File 1 -- utile -- Depend de 5I.Dynamic 5 -- I.Static 5 -- File 1 -- utile -- Depend de 4I.Dynamic 4 -- I.Static 4 -- File 1 -- utile -- Depend de 0,3,3,3,3I.Dynamic 3 -- I.Static 3 -- File 1 -- utile -- Depend de 0,2I.Dynamic 2 -- I.Static 2 -- File 1 -- utileI.Dynamic 1 -- I.Static 1 -- File 1 -- utile -- Depend de 0I.Dynamic 0 -- I.Static 0 -- File 0 -- utile

Table des registres fixes :Registre 39 : Modifie par l’instruction 0 et lu depuis par 7 instruction(s)Registre 43 : Modifie par l’instruction 55 et lu depuis par 1 instruction(s)Registre 44 : Modifie par l’instruction 56 et lu depuis par 1 instruction(s)Registre 45 : Modifie par l’instruction 57 et lu depuis par 1 instruction(s)Registre 74 : Modifie par l’instruction 50 et lu depuis par 2 instruction(s)

Table des registres tournants (niveau actuel : 1) :Registre 17 : Modifie par l’instruction 0 et lu depuis par 22 instruction(s)Registre 32 : Modifie par l’instruction 65 et lu depuis par 0 instruction(s)Registre 33 : Modifie par l’instruction 1 et lu depuis par 0 instruction(s)Registre 34 : Modifie par l’instruction 47 et lu depuis par 1 instruction(s)Registre 35 : Modifie par l’instruction 46 et lu depuis par 1 instruction(s)Registre 36 : Modifie par l’instruction 63 et lu depuis par 1 instruction(s)Registre 37 : Modifie par l’instruction 59 et lu depuis par 1 instruction(s)Registre 38 : Modifie par l’instruction 60 et lu depuis par 1 instruction(s)Registre 39 : Modifie par l’instruction 64 et lu depuis par 1 instruction(s)

Liste des adresses memoires :Adresse -4261820 : Modifie par l’instruction 48 et lu depuis par 13 instruction(s)Adresse -4261819 : Modifie par l’instruction 48 et lu depuis par 1 instruction(s)Adresse -4261818 : Modifie par l’instruction 48 et lu depuis par 1 instruction(s)Adresse -4261817 : Modifie par l’instruction 48 et lu depuis par 1 instruction(s)Adresse -4261816 : Modifie par l’instruction 15 et lu depuis par 0 instruction(s)Adresse -4261815 : Modifie par l’instruction 15 et lu depuis par 0 instruction(s)Adresse -4261814 : Modifie par l’instruction 15 et lu depuis par 0 instruction(s)Adresse -4261813 : Modifie par l’instruction 15 et lu depuis par 0 instruction(s)Adresse -4261812 : Modifie par l’instruction 30 et lu depuis par 1 instruction(s)Adresse -4261811 : Modifie par l’instruction 30 et lu depuis par 1 instruction(s)Adresse -4261810 : Modifie par l’instruction 30 et lu depuis par 1 instruction(s)Adresse -4261809 : Modifie par l’instruction 30 et lu depuis par 1 instruction(s)Adresse -4261808 : Modifie par l’instruction 45 et lu depuis par 0 instruction(s)Adresse -4261807 : Modifie par l’instruction 45 et lu depuis par 0 instruction(s)Adresse -4261806 : Modifie par l’instruction 45 et lu depuis par 0 instruction(s)

54

Adresse -4261805 : Modifie par l’instruction 45 et lu depuis par 0 instruction(s)

Calcul prenant en compte les "nop" :Nombre d’instructions inutiles : 16/66 soit 24.242424 %Nombre d’instructions utiles : 44/66 soit 66.666664 %Nombre de nop : 6/66 soit 9.090909 %

Calcul ne prenant pas en compte les "nop" :Nombre d’instructions inutiles : 16/60 soit 26.666666 %Nombre d’instructions utiles : 44/60 soit 73.333336 %

Nombre d’ocurences d’instructions inutiles pour une instruction statique :1 : 0/12 : 0/13 : 0/14 : 0/15 : 0/16 : 0/17 : 0/18 :9 :10 : 2/311 : 2/312 : 2/313 : 2/314 : 2/315 : 2/316 : 2/317 : 2/318 : 0/319 : 0/320 : 0/321 : 0/322 : 0/323 : 0/324 : 0/325 : 0/126 : 0/127 : 0/128 : 0/129 : 0/130 : 0/131 : 0/132 : 0/133 : 0/134 : 0/1

55

35 : 0/136 : 0/137 : 0/138 : 0/1

3.3.5 Graphe de dependance de donnee

Les nœuds de ce graphe sont etiquetes avec les numeros dynamiques des instructions. Les nœudsen gris represente les instructions inutiles alors que les nœuds en noir represente les instructionsutiles.

65

64 1

63

0

61

58 60

57 59

30

28

29

26

56

55

53

50

49

51

48

47

46

33

32

45

43

44

41

42

40

39

38

36

35

34

31

18

17

27

25

24

23

21

20

19

16

3

2

15

13

14

11

12

10

9

8

6

5

4

Fig. 3.1 – Graphe d’exemple genere par l’utilitaire « dot »

56

3.3.6 Trace d’execution dynamique 2

La trace d’execution dynamique de ce programme est donnee par le programme de verificationque ce travail est bien inutile (Seconde execution avec le meme jeu de donnees).

I.Dynamic 1 -- I.Static 1 -- File 1I.Dynamic 2 -- I.Static 2 -- File 1I.Dynamic 3 -- I.Static 3 -- File 1I.Dynamic 4 -- I.Static 4 -- File 1I.Dynamic 5 -- I.Static 5 -- File 1I.Dynamic 6 -- I.Static 6 -- File 1 -- BranchI.Dynamic 7 -- I.Static 7 -- File 1I.Dynamic 8 -- I.Static 10 -- File 1 -- Non executeeI.Dynamic 9 -- I.Static 11 -- File 1 -- Non executeeI.Dynamic 10 -- I.Static 12 -- File 1 -- Non executeeI.Dynamic 11 -- I.Static 13 -- File 1 -- Non executeeI.Dynamic 12 -- I.Static 14 -- File 1 -- Non executeeI.Dynamic 13 -- I.Static 15 -- File 1 -- Non executeeI.Dynamic 14 -- I.Static 16 -- File 1 -- Non executeeI.Dynamic 15 -- I.Static 17 -- File 1 -- Non executeeI.Dynamic 16 -- I.Static 18 -- File 1I.Dynamic 17 -- I.Static 19 -- File 1I.Dynamic 18 -- I.Static 20 -- File 1I.Dynamic 19 -- I.Static 21 -- File 1I.Dynamic 20 -- I.Static 22 -- File 1I.Dynamic 21 -- I.Static 23 -- File 1 -- BranchI.Dynamic 22 -- I.Static 24 -- File 1I.Dynamic 23 -- I.Static 10 -- File 1I.Dynamic 24 -- I.Static 11 -- File 1I.Dynamic 25 -- I.Static 12 -- File 1I.Dynamic 26 -- I.Static 13 -- File 1I.Dynamic 27 -- I.Static 14 -- File 1I.Dynamic 28 -- I.Static 15 -- File 1I.Dynamic 29 -- I.Static 16 -- File 1I.Dynamic 30 -- I.Static 17 -- File 1I.Dynamic 31 -- I.Static 18 -- File 1I.Dynamic 32 -- I.Static 19 -- File 1I.Dynamic 33 -- I.Static 20 -- File 1I.Dynamic 34 -- I.Static 21 -- File 1I.Dynamic 35 -- I.Static 22 -- File 1I.Dynamic 36 -- I.Static 23 -- File 1 -- BranchI.Dynamic 37 -- I.Static 24 -- File 1I.Dynamic 38 -- I.Static 10 -- File 1 -- Non executeeI.Dynamic 39 -- I.Static 11 -- File 1 -- Non executeeI.Dynamic 40 -- I.Static 12 -- File 1 -- Non executeeI.Dynamic 41 -- I.Static 13 -- File 1 -- Non executee

57

I.Dynamic 42 -- I.Static 14 -- File 1 -- Non executeeI.Dynamic 43 -- I.Static 15 -- File 1 -- Non executeeI.Dynamic 44 -- I.Static 16 -- File 1 -- Non executeeI.Dynamic 45 -- I.Static 17 -- File 1 -- Non executeeI.Dynamic 46 -- I.Static 18 -- File 1I.Dynamic 47 -- I.Static 19 -- File 1I.Dynamic 48 -- I.Static 20 -- File 1I.Dynamic 49 -- I.Static 21 -- File 1I.Dynamic 50 -- I.Static 22 -- File 1I.Dynamic 51 -- I.Static 23 -- File 1 -- BranchI.Dynamic 52 -- I.Static 24 -- File 1I.Dynamic 53 -- I.Static 25 -- File 1 -- BranchI.Dynamic 54 -- I.Static 26 -- File 1I.Dynamic 55 -- I.Static 27 -- File 1I.Dynamic 56 -- I.Static 28 -- File 1I.Dynamic 57 -- I.Static 29 -- File 1I.Dynamic 58 -- I.Static 30 -- File 1I.Dynamic 59 -- I.Static 31 -- File 1I.Dynamic 60 -- I.Static 32 -- File 1I.Dynamic 61 -- I.Static 33 -- File 1 -- BranchI.Dynamic 62 -- I.Static 34 -- File 1I.Dynamic 63 -- I.Static 35 -- File 1I.Dynamic 64 -- I.Static 36 -- File 1I.Dynamic 65 -- I.Static 37 -- File 1 -- BranchI.Dynamic 66 -- I.Static 38 -- File 1

58

3.4 Exemple de donnees stockees en cours d’execution

Liste chainée des instructions dynamiques(représente l'ordre d'exécution)

Instruction dynamique :Instruction statique :Numéro de fichier :

Type de l'instruction :

nmfadd



n+1m+1fstore



n+2m’fbra



n+3m’+1fload



n+4m’+2fmul

Table des registres globaux

%g0%g1%g2%g3%g4%g5%g6%g7

Table de la fenêtre de registres

%o0%o1%o2%o3%o4%o5%o6%o7

%l0%l1%l2%l3%l4%l5%l6%l7

%i0%i1%i2%i3%i4%i5%i6%i7

%o0%o1%o2%o3%o4%o5%o6%o7

%l0%l1%l2%l3%l4%l5%l6%l7

%i0%i1%i2%i3%i4%i5%i6%i7

Table des adresses mémoires

0x00000x00010x00020x00030x00040x00050x00060x0007

…

Pointeur sur l’instruction dynamique précédente (structure de la liste chainée)

Pointeur sur les instructions ayant produits les opérandes de l’instruction

Pointeur sur la dernière instruction ayant écrit dans la ressource

Fig. 3.2 – Les structures de donnees utilisees par le programme pour construire le graphe dedependance de donnee

59

3.5 Code source du programme

60

/* Défini le nom du fichier contenant les fonction définies localement par rapport au programme (pas dans une bibliothèques) */#define NOM_FICHIER_FONCTIONS_INTERNES "fonctions.txt"/* Défini le nom du fichier contenant les fonction définies hors du programme (bibliothèques) mais non redéfinies dans le fichier redefinition.c */#define NOM_FICHIER_FONCTIONS_EXTERNES_SPECIALES "fonctions_externes_speciales.txt"

void appelDeFonctionInstDebut(BB *bb, int position, unsigned int *nbInstructionsAjoutees, int numeroInst, int typeInst, char *chaineAnnulBit);void appelDeFonctionInstMilieu(BB *bb, int position, unsigned int *nbInstructionsAjoutees, char *chaineAnnulBit);void appelDeFonctionInstFin(BB *bb, int position, unsigned int *nbInstructionsAjoutees, char *chaineAnnulBit);void appelDeFonctionReg(BB *bb, int position, unsigned int *nbInstructionsAjoutees, int es, int indentificateurRessource, char *chaineAnnulBit);int tailleAccesMemoire(INST *inst);void appelDeFonctionMem(BB *bb, INST *inst, int position, unsigned int *nbInstructionsAjoutees, int es, char *acces1, char *acces2, char *chaineAnnulBit, int tailleAccesMemoire);void appelDeFonctionCopierInstDelay(BB *bb, int position, unsigned int *nbInstructionsAjoutees);void appelDeFonctionEchangerInstDelay(BB *bb, int position, unsigned int *nbInstructionsAjoutees);int rechercheChaine(char *chaine, FILE *fichier);int estPresent(char *motif, char *chaine);int typeInstruction(INST *inst);void operandeMemoire(char *instruction, char *acces1, char *acces2);// Fonction permettant de sauvagarder le contexte du programme (registres généraux et codes conditions) afin de ne pas// intervenir sur les valeurs des registres et codes conditions utilisés par le programmevoid sauvegardeContexte(BB *bb, int position, unsigned int *nbInstructionsAjoutees);// Fonction permettant de restaurer le contexte du programme (registres généraux et codes conditions) afin de ne pas// intervenir sur les valeurs des registres et codes conditions utilisés par le programmevoid restaurationContexte(BB *bb, int position, unsigned int *nbInstructionsAjoutees);int registreSalto(char *acces);void blancSuivant(char **ptr);// Insère le code permettant d’instrumenter en fonction des entrées produites par instvoid appelDeFonctionsEntrees(INST *inst, BB *bb, int position, unsigned int *nbInstructionsAjoutees, char *chaineAnnulBit);// Ajout de l’instrumentation représentant les entrées fictives des call externesvoid appelDeFonctionsEntreesAppelExterne(INST *inst, BB *bb, int position, unsigned int *nbInstructionsAjoutees);// Insère le code permettant d’instrumenter en fonction des sorties produites par instvoid appelDeFonctionsSorties(INST *inst, BB *bb, int position, unsigned int *nbInstructionsAjoutees, char *chaineAnnulBit);// Ajout de l’instrumentation représentant les sorties fictives des call externesvoid appelDeFonctionsSortiesAppelExterne(INST *inst, BB *bb, int position, unsigned int *nbInstructionsAjoutees);void instrumenter(INST *inst, BB *bb, BB *bbSuivant, int position, unsigned int *nbInstructionsAjoutees, int numeroInst);void ajouterCommentaireAppelExterne(INST *inst);void Salto_hook();

12 mai 03 13:40 Page 1/2instrumentation.hvoid Salto_init_hook(int argc, char *argv[]);void Salto_end_hook();

12 mai 03 13:40 Page 2/2instrumentation.h

Imprimé par Benjamin Vidal

mercredi 18 juin 2003 1/37instrumentation.h

#include <stdio.h>#include <fcntl.h>#include <errno.h>#include <fstream>#include <iostream>#include <sys/types.h>#include <regex.h>#include <stdlib.h>#include <string.h>

#include " salto.h"#include " instrumentation.h"#include " instrument.h"

#define FICHIER_SOURCE_ASSEMBLEUR ".s$"#define REPERTOIRE_FICHIER_INSTRUMENTES "instrumente/"

#define IN 0#define OUT 1

#define EXP_REGISTRE " ^%[golisf][0−7p]$"#define EXP_MEMOIRE " \\[[−+%a−zA−Z0−9_.()]+\\]"#define EXP_FONCTION " [ ]+call[ ]+"#define EXP_SAVE " [ ]+save[ ]+"#define EXP_RESTORE " [ ]+restore[ ]+"#define EXP_ANNUL_BIT " ,a"#define EXP_LOAD " ld[usd]?[bh]?"#define EXP_STORE " st[bhd]?"

#define ETIQUETTE_FONCTION_NOP "f_nop"

#define PREFIXE_FONCTIONS_EXTERNES "my_"

#define SAVE " save %sp,−136,%sp"#define RESTORE " restore %g0,%g0,%g0"#define NOP " nop"

// Pointeur sur le fichier dans lequel sera écrit le code instrumentéFILE *fichierSInstrumente;// Pointeur sur le fichier contenant le code original (non instrumenté)FILE *fichierSOriginal;

// Permet d’identifier de manière unique le fichier en cours de traitementunsigned char numeroFichier;

void appelDeFonctionInstDebut(BB *bb, int position, unsigned int *nbInstructionsAjoutees, int numeroInst, int typeInst, char *chaineAnnulBit){ char chaine[20],tmp[100];

// On empile un paramètre de type entier à passer à la fonction (équivaut à mov typeInst,%o0) sprintf(chaine," or %%g0,%d,%%o0",typeInst); bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(chaine)); (*nbInstructionsAjoutees)++; // Si la constante numeroInst à ranger dans %o1 peut être codée sur 13 bits (

03 jun 03 16:11 Page 1/23instrumentation.cci.e. est entre −4096 et 4095) if(numeroInst <= 4095) { // On empile un paramètre de type entier à passer à la fonction (équivaut à mov numeroInst,%o1) sprintf(chaine," or %%g0,%d,%%o1",numeroInst); bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(chaine)); (*nbInstructionsAjoutees)++; } else { // On empile ce même paramètre mais en deux fois (les 22 premiers bits du registre d’abbord) sprintf(chaine," sethi %%hi(%d),%%o1",numeroInst); bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(chaine)); (*nbInstructionsAjoutees)++; // Puis les 10 derniers bits ensuite sprintf(chaine," or %%o1,%%lo(%d),%%o1",numeroInst); bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(chaine)); (*nbInstructionsAjoutees)++; } // On empile un paramètre de type entier à passer à la fonction (équivaut à mov numeroFichier,%o1) sprintf(chaine," or %%g0,%d,%%o2",numeroFichier); bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(chaine)); (*nbInstructionsAjoutees)++; // Si l’instruction que l’on instrumente est un branchement avec un annulBit (ex : bl,a ...) on insère une instruction qui // va inhiber l’effet du call suivant lorsque l’annulation de l’exécution de l’instruction se trouvant dans le DelaySlot // sera effective (cela ne peut être vu qu’à l’exécution et donc ne peut être fait statiquement) if (chaineAnnulBit != NULL) { INST *inst_br_nop; inst_br_nop = newAsm(NOP); inst_br_nop−>addAttribute(UNPARSE_ATT, chaineAnnulBit, strlen(chaineAnnulBit)+1); bb−>insertAsm(*nbInstructionsAjoutees+position, inst_br_nop); (*nbInstructionsAjoutees)++; strcpy(tmp," b "); } else strcpy(tmp," call "); bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(strcat(tmp,NOM_FCT_DEBUT_INST))); (*nbInstructionsAjoutees)++; // On ajoute un nop afin de combler le delay slot bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(NOP)); (*nbInstructionsAjoutees)++;}

void appelDeFonctionInstMilieu(BB *bb, int position, unsigned int *nbInstructionsAjoutees, char *chaineAnnulBit){

03 jun 03 16:11 Page 2/23instrumentation.cc


mercredi 18 juin 2003 2/37instrumentation.cc

char tmp[100]; // Si l’instruction que l’on instrumente est un branchement avec un annulBit (ex : bl,a ...) on insère une instruction qui // va inhiber l’effet du call suivant lorsque l’annulation de l’exécution de l’instruction se trouvant dans le DelaySlot // sera effective (cela ne peut être vu qu’à l’exécution et donc ne peut être fait statiquement) if (chaineAnnulBit != NULL) { INST *inst_br_nop; inst_br_nop = newAsm(NOP); inst_br_nop−>addAttribute(UNPARSE_ATT, chaineAnnulBit, strlen(chaineAnnulBit)+1); bb−>insertAsm(*nbInstructionsAjoutees+position, inst_br_nop); (*nbInstructionsAjoutees)++; strcpy(tmp," b "); } else strcpy(tmp," call "); bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(strcat(tmp,NOM_FCT_MILIEU_INST))); (*nbInstructionsAjoutees)++; // On ajoute un nop afin de combler le delay slot bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(NOP)); (*nbInstructionsAjoutees)++;}

void appelDeFonctionInstFin(BB *bb, int position, unsigned int *nbInstructionsAjoutees, char *chaineAnnulBit){ char tmp[100]; // Si l’instruction que l’on instrumente est un branchement avec un annulBit (ex : bl,a ...) on insère une instruction qui // va inhiber l’effet du call suivant lorsque l’annulation de l’exécution de l’instruction se trouvant dans le DelaySlot // sera effective (cela ne peut être vu qu’à l’exécution et donc ne peut être fait statiquement) if (chaineAnnulBit != NULL) { INST *inst_br_nop; inst_br_nop = newAsm(NOP); inst_br_nop−>addAttribute(UNPARSE_ATT, chaineAnnulBit, strlen(chaineAnnulBit)+1); bb−>insertAsm(*nbInstructionsAjoutees+position, inst_br_nop); (*nbInstructionsAjoutees)++; strcpy(tmp," b "); } else strcpy(tmp," call ");

bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(strcat(tmp,NOM_FCT_FIN_INST))); (*nbInstructionsAjoutees)++;


// On ajoute un nop afin de combler le delay slot bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(NOP)); (*nbInstructionsAjoutees)++;}

void appelDeFonctionReg(BB *bb, int position, unsigned int *nbInstructionsAjoutees, int es, int indentificateurRessource, char *chaineAnnulBit){ char chaine[20],tmp[100];

// On empile le paramètre de type entier à passer à la fonction (équivaut à mov %d,%o0) sprintf(chaine," or %%g0,%d,%%o0",indentificateurRessource); bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(chaine)); (*nbInstructionsAjoutees)++; // Si l’instruction que l’on instrumente est un branchement avec un annulBit (ex : bl,a ...) on insère une instruction qui // va inhiber l’effet du call suivant lorsque l’annulation de l’exécution de l’instruction se trouvant dans le DelaySlot // sera effective (cela ne peut être vu qu’à l’exécution et donc ne peut être fait statiquement) if (chaineAnnulBit != NULL) { INST *inst_br_nop; inst_br_nop = newAsm(NOP); inst_br_nop−>addAttribute(UNPARSE_ATT, chaineAnnulBit, strlen(chaineAnnulBit)+1); bb−>insertAsm(*nbInstructionsAjoutees+position, inst_br_nop); (*nbInstructionsAjoutees)++; strcpy(tmp," b "); } else strcpy(tmp," call "); // Appel de la fonction définie "ailleurs" (fichier instrument.c) // Si le paramètre de l’instruction à instrumentée est un paramètre d’entrée if (es==IN) { // On appelle la fonction de traitement spécifique aux paramètres d’entrée bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(strcat(tmp,NOM_FCT_IN_REG))); (*nbInstructionsAjoutees)++; } // Si le paramètre de l’instruction a instrumenter est un paramètre de sortie else { // On appelle la fonction de traitement spécifique aux paramètres de sortie bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(strcat(tmp,NOM_FCT_OUT_REG))); (*nbInstructionsAjoutees)++; } // On ajoute un nop afin de combler le delay slot bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(NOP)); (*nbInstructionsAjoutees)++;}




int tailleAccesMemoire(INST *inst){ regex_t *preg = new regex_t(); size_t nmatch = 1; regmatch_t pmatch[nmatch];

// Compilation de l’expression régulière permettant de détecter si une instruction est un load if (regcomp(preg, EXP_LOAD, REG_EXTENDED)) { fprintf(STDERR," Erreur lors de la compilation de l’expression régulière \""EXP_LOAD"\"\n"); exit(4); } // Si l’instruction est un load if (regexec(preg, inst−>unparse(), nmatch, pmatch, 0) != REG_NOMATCH) { regfree(preg); // Si le dernier caractère de l’expression est un b, alors le load est un load byte if(inst−>unparse()[pmatch[0].rm_eo−1] == ’ b’) return 1; // Si le dernier caractère de l’expression est un h, alors le load est un load half−word if(inst−>unparse()[pmatch[0].rm_eo−1] == ’ h’) return 2; // Si le dernier caractère de l’expression est un d et que ce caractère est en deuxième position, alors le load est un load word if(inst−>unparse()[pmatch[0].rm_eo−1] == ’ d’ && pmatch[0].rm_eo == 3) return 4; // Si le dernier caractère de l’expression est un d et que ce caractère est en troisième position, alors le load est un load double−word if(inst−>unparse()[pmatch[0].rm_eo−1] == ’ d’ && pmatch[0].rm_eo == 4) return 8; fprintf(STDERR," Impossible de reconnaitre la taille des données lues par l’instruction \"%s\"\n",inst−>unparse()); fprintf(STDERR," Fonction tailleAccesMemoire du fichier instrumentation.cc\n"); exit(7); } // Compilation de l’expression régulière permettant de détecter si une instruction est un store if (regcomp(preg, EXP_STORE, REG_EXTENDED)) { fprintf(STDERR," Erreur lors de la compilation de l’expression régulière \""EXP_STORE"\"\n"); exit(4); } // Si l’instruction est un store if (regexec(preg, inst−>unparse(), nmatch, pmatch, 0) != REG_NOMATCH) { regfree(preg); // Si le dernier caractère de l’expression est un b, alors le store est un store byte if(inst−>unparse()[pmatch[0].rm_eo−1] == ’ b’) return 1; // Si le dernier caractère de l’expression est un h, alors le store est un store half−word if(inst−>unparse()[pmatch[0].rm_eo−1] == ’ h’) return 2; // Si le dernier caractère de l’expression est un t, alors le store est un store word if(inst−>unparse()[pmatch[0].rm_eo−1] == ’ t’) return 4; // Si le dernier caractère de l’expression est un d, alors le store est un store double−word if(inst−>unparse()[pmatch[0].rm_eo−1] == ’ d’) return 8;

03 jun 03 16:11 Page 5/23instrumentation.cc fprintf(STDERR," Impossible de reconnaitre la taille des données lues par l’instruction \"%s\"\n",inst−>unparse()); fprintf(STDERR," Fonction tailleAccesMemoire du fichier instrumentation.cc\n"); exit(7); }}

void appelDeFonctionMem(BB *bb, INST *inst, int position, unsigned int *nbInstructionsAjoutees, int es, char *acces1, char *acces2, char *chaineAnnulBit, int tailleAccesMemoire){ char chaine[200],tmp[100]; // * Sauvegarde de la valeur stockée dans %i0 dans la pile afin de pouvoir la récupérer par la suite bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(" st %i0,[%sp+124]")); (*nbInstructionsAjoutees)++; // Cette instruction permet de récupérer l’état des registres tels qu’ils était au moment // ou l’appel de l’instruction instrumentée était iminent (on descend d’un cran le contexte) restaurationContexte(bb, position, nbInstructionsAjoutees); // Insertion de l’instruction permettant de faire passer le résultat du calcul au contexte supérieure // (fenêtre de registre placée au dessus) sprintf(chaine," add %s,%s,%%o0",acces1,acces2); bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(chaine)); (*nbInstructionsAjoutees)++; // Puis on repasse dans le contexte supérieur sauvegardeContexte(bb, position, nbInstructionsAjoutees); // En fin on récupère le résultat calculé par l’addition pour le passer en paramètre à la fonction // qui va être appellée (mov %i0,%o0) bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(" or %g0,%i0,%o0")); (*nbInstructionsAjoutees)++; // * Restauration de la valeur stockée dans %o0 (valeur qui avait été sauvegardée par "st %i0,[%sp+124]") bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(" ld [%sp+124],%i0")); (*nbInstructionsAjoutees)++; // On range dans %o1 la taille de l’acces mémoire effectué (nombre d’octets lus ou écrits par l’instruction sprintf(chaine," or %%g0,%d,%%o1",tailleAccesMemoire); bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(chaine)); (*nbInstructionsAjoutees)++; // Si l’instruction que l’on instrumente est un branchement avec un annulBit (ex : bl,a ...) on insère une instruction qui // va inhiber l’effet du "call suivant" lorsque l’annulation de l’exécution de l’instruction se trouvant dans le DelaySlot // sera effective (cela ne peut être vu qu’à l’exécution et donc ne peut être fait statiquement) if (chaineAnnulBit != NULL) {




INST *inst_br_nop; inst_br_nop = newAsm(NOP); inst_br_nop−>addAttribute(UNPARSE_ATT, chaineAnnulBit, strlen(chaineAnnulBit)+1); bb−>insertAsm(*nbInstructionsAjoutees+position, inst_br_nop); (*nbInstructionsAjoutees)++; strcpy(tmp," b "); } else strcpy(tmp," call ");

// Appel de la fonction définie "ailleurs" (fichier instrument.c) // Si le paramètre de l’instruction à instrumentée est un paramètre d’entrée if (es==IN) { // On appelle la fonction de traitement spécifique aux paramètres d’entrée bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(strcat(tmp,NOM_FCT_IN_MEM))); (*nbInstructionsAjoutees)++; } // Si le paramètre de l’instruction à instrumentée est un paramètre de sortie else { // On appelle la fonction de traitement spécifique aux paramètres de sortie bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(strcat(tmp,NOM_FCT_OUT_MEM))); (*nbInstructionsAjoutees)++; } // On comble le delay slot de l’appel de fonction précédent par un nop bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(NOP)); (*nbInstructionsAjoutees)++;}

void appelDeFonctionCopierInstDelay(BB *bb, int position, unsigned int *nbInstructionsAjoutees){ bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(" call copierInstDelay")); (*nbInstructionsAjoutees)++; // On ajoute un nop afin de combler le delay slot bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(NOP)); (*nbInstructionsAjoutees)++;}

void appelDeFonctionEchangerInstDelay(BB *bb, int position, unsigned int *nbInstructionsAjoutees){ bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(" call echangerInstDelay")); (*nbInstructionsAjoutees)++; // On ajoute un nop afin de combler le delay slot bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(NOP)); (*nbInstructionsAjoutees)++;}

int rechercheChaine( char *chaine, FILE *fichier)

03 jun 03 16:11 Page 7/23instrumentation.cc{ char chaine2[100]; while (!feof(fichier)) { fscanf(fichier," %s",chaine2); if(!strcmp(chaine,chaine2)) return 1; } return 0;}

int estPresent( char *motif, char *chaine){ int i; regex_t *preg = new regex_t(); size_t nmatch = 10; regmatch_t pmatch[nmatch]; // Compilation de l’expression régulière if (regcomp(preg, motif, REG_EXTENDED)) { fprintf(STDERR," Erreur lors de la compilation de l’expression régulière \"%s\"\n",motif); exit(4); } // Exécution de l’expression régulière et renvoi du résultat en fonction if (regexec(preg, chaine, nmatch, pmatch, 0) == REG_NOMATCH) { regfree(preg); return 0; } for(i=0; i<nmatch && pmatch[i].rm_so!=−1; i++); regfree(preg); return i;}

int typeInstruction(INST *inst){ int i,j; char tmp[100]; regex_t *preg = new regex_t(); size_t nmatch = 1; regmatch_t pmatch[nmatch]; FILE *fichier;

// Si l’instruction est une instruction "save", on retourne la valeur T_SAVE if (estPresent(EXP_SAVE,inst−>unparse())) return T_SAVE; // Si l’instruction est une instruction "restore", on retourne la valeur T_RESTORE if (estPresent(EXP_RESTORE,inst−>unparse())) return T_RESTORE; // Compilation de l’expression régulière permettant de détecter si une instruction est une instruction de sortie // (printf entre autre)




if (regcomp(preg, EXP_FONCTION, REG_EXTENDED)) { fprintf(STDERR," Erreur lors de la compilation de l’expression régulière \""EXP_FONCTION"\"\n"); exit(4); } // Si l’instruction est un call if (regexec(preg, inst−>unparse(), nmatch, pmatch, 0) != REG_NOMATCH) { // On récupère dans la chaine tmp l’étiquette à laquelle on va brancher en exécutant le call for(i=0,j=pmatch[0].rm_eo; j<strlen(inst−>unparse()); j++) if((inst−>unparse())[j]!=’ ’ && (inst−>unparse())[j]!=’ \t’) tmp[i++]=(inst−>unparse())[j]; tmp[i] = ’ \0’; regfree(preg); fichier = fopen(NOM_FICHIER_FONCTIONS_INTERNES, " r"); if(fichier == NULL) { fprintf(STDERR," Problème lors de l’ouverture du fichier \""NOM_FICHIER_FONCTIONS_INTERNES" \" "); fprintf(STDERR," (fonction typeInstruction dans le fichier instrumentation.cc)\n"); exit(11); } // On recherche dans notre base de nom de fonctions définies localement si la fonction désignée par l’étiquette // fait partie du code qui à était instrumenté ou non if(rechercheChaine(tmp,fichier)) { fclose(fichier); return T_APPEL_INTERNE; } fclose(fichier); fichier = fopen(NOM_FICHIER_FONCTIONS_EXTERNES_SPECIALES," r"); if(fichier == NULL) { fprintf(STDERR," Problème lors de l’ouverture du fichier \""NOM_FICHIER_FONCTIONS_EXTERNES_SPECIALES"\" "); fprintf(STDERR," (fonction typeInstruction dans le fichier instrumentation.cc)\n"); exit(11); }

if(rechercheChaine(tmp,fichier)) { fclose(fichier); return T_APPEL_EXTERNE_SPECIAL; } fclose(fichier); return T_APPEL_EXTERNE; } // Si l’instruction est un "nop", on retourne la valeur T_NOP if (inst−>isNop()) return T_NOP; // Si l’instruction est un branchement, on retourne la valeur T_BRANCHEMENT if (inst−>isCTI()) if(estPresent(EXP_ANNUL_BIT,inst−>unparse()))

03 jun 03 16:11 Page 9/23instrumentation.cc return T_BRANCHEMENT_ANNUL_BIT; else return T_BRANCHEMENT; // Si l’instruction est une instruction "ld", on retourne la valeur T_LOAD if (estPresent(EXP_LOAD,inst−>unparse())) return T_LOAD; // Si l’instruction est une instruction "st", on retourne la valeur T_STORE if (estPresent(EXP_STORE,inst−>unparse())) return T_STORE; return T_AUTRE;}

void operandeMemoire( char *instruction, char *acces1, char *acces2){ int i,j; char tmp[10]; regex_t *preg_mem = new regex_t(); regex_t *preg_signe = new regex_t(); size_t nmatch = 1; regmatch_t pmatch_mem[nmatch]; regmatch_t pmatch_signe[nmatch]; // Compilation de l’expression régulière permettant de détecter un acces mémoire d’une instruction if (regcomp(preg_mem, EXP_MEMOIRE, REG_EXTENDED)) { fprintf(STDERR," Erreur lors de la compilation de l’expression régulière \""EXP_MEMOIRE"\"\n"); exit(4); } if (regcomp(preg_signe, " [−+]", REG_EXTENDED)) { fprintf(STDERR," Erreur lors de la compilation de l’expression régulière \"[−+]\"\n"); exit(4); } if (regexec(preg_mem, instruction, nmatch, pmatch_mem, 0) == REG_NOMATCH) { fprintf(STDERR," Erreur lors de l’exécution de l’expression régulière \""EXP_MEMOIRE"\" : impossible de "); fprintf(STDERR," trouver un motif correspondant à cette expression dans l’instruction \"%s\"\n",instruction); exit(4); } if (regexec(preg_signe, instruction, nmatch, pmatch_signe, 0) == REG_NOMATCH) { // On récupère la chaine de caractère correspondant au nom du registre auquel on accède for(i=0,j=pmatch_mem[0].rm_so+1; j<pmatch_mem[0].rm_eo−1; j++) acces1[i++]=instruction[j]; acces1[i] = ’ \0’; strcpy(acces2," 0"); } else { // On récupère la chaine de caractère correspondant au nom du premier registre auquel on accède for(i=0,j=pmatch_mem[0].rm_so+1; j<pmatch_signe[0].rm_so; j++) acces1[i++]=i




nstruction[j]; acces1[i] = ’ \0’;

i=0; // Si le signe reconnu par l’expression régulière [−+] est un moins, on le rejoute en début de chaine // possible seulement si le deuxième acces est une constante (ex : ld [%i6−60],%o0) if (instruction[pmatch_signe[0].rm_so] == ’ −’) acces2[i++] = ’ −’; // On récupère la chaine de caractère correspondant au nom du deuxième registre auquel on accède ou à la constante for(j=pmatch_signe[0].rm_eo; j<pmatch_mem[0].rm_eo−1; j++) acces2[i++] = instruction[j]; acces2[i] = ’ \0’; } regfree(preg_mem); regfree(preg_signe);}

// Fonction permettant de sauvagarder le contexte du programme (registres généraux et codes conditions) afin de ne pas// intervenir sur les valeurs des registres et codes conditions utilisés par le programmevoid sauvegardeContexte(BB *bb, int position, unsigned int *nbInstructionsAjoutees){ INST *inst_ccr; char *lectureCodesConditions = " \trd %ccr,%l0\n"; // "Empilement" du contexte du programme (création d’un contexte intermédiaire artificiel entre l’exécution du // programme et l’exécution des fonctions d’instrumentation du code. Ce contexte permet de travailler avec // les registres %o[0−5] afin de faire passer les paramètres aux fonctions d’instrumentations. bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(SAVE)); (*nbInstructionsAjoutees)++; inst_ccr = newAsm(NOP); inst_ccr−>addAttribute(UNPARSE_ATT, lectureCodesConditions, strlen(lectureCodesConditions)+1); bb−>insertAsm(*nbInstructionsAjoutees+position, inst_ccr); (*nbInstructionsAjoutees)++; // Sauvegarde en mémoire (dans la pile) des registres globaux for( int i=1; i<=4; i++) { char tmp[20]; // Sauvegarde du registre (%gi) (ex : "st %g1,[%sp+92]") sprintf(tmp," st %%g%d,[%%sp+%d]",i,88+(4*i)); bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(tmp)); (*nbInstructionsAjoutees)++; }}

// Fonction permettant de restaurer le contexte du programme (registres généraux et codes conditions) afin de ne pas// intervenir sur les valeurs des registres et codes conditions utilisés par le

03 jun 03 16:11 Page 11/23instrumentation.ccprogrammevoid restaurationContexte(BB *bb, int position, unsigned int *nbInstructionsAjoutees){ INST *inst_ccr; char *ecritureCodesConditions = " \twr %l0,%ccr\n"; // Récupération des registres globaux depuis la mémoire (depuis la pile) for( int i=1; i<=4; i++) { char tmp[20]; // Restauration du registre (%gi) (ex : "ld [%sp+92],%g1") sprintf(tmp," ld [%%sp+%d],%%g%d",88+(4*i),i); bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(tmp)); (*nbInstructionsAjoutees)++; } inst_ccr = newAsm(NOP); inst_ccr−>addAttribute(UNPARSE_ATT, ecritureCodesConditions, strlen(ecritureCodesConditions)+1); bb−>insertAsm(*nbInstructionsAjoutees+position, inst_ccr); (*nbInstructionsAjoutees)++;

// "Dépilement" du contexte du programme bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(RESTORE)); (*nbInstructionsAjoutees)++;}

int registreSalto( char *acces){ regex_t *preg = new regex_t(); size_t nmatch = 1; regmatch_t pmatch[nmatch]; // Compilation de l’expression régulière permettant de détecter un registre if (regcomp(preg, EXP_REGISTRE, REG_EXTENDED)) { fprintf(STDERR," Erreur lors de la compilation de l’expression régulière \""EXP_REGISTRE"\"\n"); exit(4); } if (regexec(preg, acces, nmatch, pmatch, 0) == REG_NOMATCH) { regfree(preg); return 0; } regfree(preg); // Traitement des cas particuliers : %sp et %fp (correspondant à %o6 et %i6) if (!strcmp(acces," %sp")) return ID_REG_SALTO_O+6; if (!strcmp(acces," %fp")) return ID_REG_SALTO_I+6; // Traitement du cas général switch (acces[1]) { case ’g’ : return ID_REG_SALTO_G+atoi(&(acces[2])); case ’o’ : return ID_REG_SALTO_O+atoi(&(acces[2])); case ’l’ : return ID_REG_SALTO_L+atoi(&(acces[2]));




case ’i’ : return ID_REG_SALTO_I+atoi(&(acces[2])); default : fprintf(STDERR," Passage impossible : fonction registreSalto dans instrumentation.cc\n"); }}

void blancSuivant( char **ptr){ while ((*ptr)[0]!=’ ’ && (*ptr)[0]!=’ \t’ && (*ptr)[0]!=’ \n’ && (*ptr)[0]!=’ \0’) (*ptr)++; while ((*ptr)[0]==’ ’ || (*ptr)[0]==’ \t’ || (*ptr)[0]==’ \n’) (*ptr)++;}

// Insère le code permettant d’instrumenter en fonction des entrées produites par instvoid appelDeFonctionsEntrees(INST *inst, BB *bb, int position, unsigned int *nbInstructionsAjoutees, char *chaineAnnulBit){ ResourceDataBase &rdb = xxx_server −> GetResT(); res_ref* in; ResId_T identificateurRessource; // Ajout de l’instrumentation représentant les entrées de l’instruction fournie par salto (lectures) for ( int i=0; i < inst−>numberOfInput(); i++) { in = inst−>getInput(i); identificateurRessource = in−>get_res_id(); // Traitement fait pour chaque opérandes d’entrée switch ((rdb.get_res(identificateurRessource))−>getType()) { case MEMORY_RTYPE : char acces1[100],acces2[100];

operandeMemoire(inst−>unparse(), acces1, acces2); appelDeFonctionMem(bb, inst, position, nbInstructionsAjoutees, IN, acces1, acces2, chaineAnnulBit, tailleAccesMemoire(inst)); break; case REGISTER_RTYPE : appelDeFonctionReg(bb, position, nbInstructionsAjoutees, IN, identificateurRessource, chaineAnnulBit); break; default : fprintf(STDERR," Passage impossible : fonction appelDeFonctionsEntrees dans instrumentation.cc\n"); } }}

// Ajout de l’instrumentation représentant les entrées fictives des call externesvoid appelDeFonctionsEntreesAppelExterne(INST *inst, BB *bb, int position, unsigned int *nbInstructionsAjoutees){ char acces[20]; char *ptr = ( char *)(inst−>attributeValue(IN,COMMENT_ATT)); int identificateurRessource;

03 jun 03 16:11 Page 13/23instrumentation.cc sscanf(ptr," %s",acces); // Tant qu’on n’a pas atteint la fin de la chaine de caractère contenant les entrées effectuées par le call traité while (ptr[0] != ’ \0’) { blancSuivant(&ptr); identificateurRessource = registreSalto(acces); if(identificateurRessource != 0) appelDeFonctionReg(bb, position, nbInstructionsAjoutees, IN, identificateurRessource, NULL); else { char tmp[20],acces1[100],acces2[100];

strcpy(tmp," ["); strcat(tmp,acces); strcat(tmp," ]"); operandeMemoire(tmp, acces1, acces2); appelDeFonctionMem(bb, inst, position, nbInstructionsAjoutees, IN, acces1, acces2, NULL, 4); } sscanf(ptr," %s",acces); } // Les fonctions définies hors du fichier local font toujours un accès en lecture à %o6 (pointeur de pile) // et à %o7 (adresse de retour) /*appelDeFonctionReg(bb, position, nbInstructionsAjoutees, IN, ID_REG_SALTO_O+6, NULL); appelDeFonctionReg(bb, position, nbInstructionsAjoutees, IN, ID_REG_SALTO_O+7, NULL);*/}

// Insère le code permettant d’instrumenter en fonction des sorties produites par instvoid appelDeFonctionsSorties(INST *inst, BB *bb, int position, unsigned int *nbInstructionsAjoutees, char *chaineAnnulBit){ ResourceDataBase &rdb = xxx_server −> GetResT(); res_ref* out; int identificateurRessource; // Ajout de l’instrumentation représentant les sorties de l’instruction fournie par salto (écritures) for ( int i=0; i < inst−>numberOfOutput(); i++) { out = inst−>getOutput(i); identificateurRessource = out−>get_res_id();

// Traitement fait pour chaque opérandes de sortie switch ((rdb.get_res(identificateurRessource))−>getType()) { case MEMORY_RTYPE : char acces1[100],acces2[100];




operandeMemoire(inst−>unparse(), acces1, acces2); appelDeFonctionMem(bb, inst, position, nbInstructionsAjoutees, OUT, acces1, acces2, chaineAnnulBit, tailleAccesMemoire(inst)); break; case REGISTER_RTYPE : appelDeFonctionReg(bb, position, nbInstructionsAjoutees, OUT, identificateurRessource, chaineAnnulBit); break; default : fprintf(STDERR," Passage impossible : fonction appelDeFonctionsSorties dans instrumentation.cc\n"); } }}

// Ajout de l’instrumentation représentant les sorties fictives des call externesvoid appelDeFonctionsSortiesAppelExterne(INST *inst, BB *bb, int position, unsigned int *nbInstructionsAjoutees){ char *acces = ( char *)(inst−>attributeValue(OUT,COMMENT_ATT)); ResId_T identificateurRessource = registreSalto(acces); if(identificateurRessource == 0) { fprintf(STDERR," Erreur : la chaine \"%s\" n’est pas reconnue comme étant un registre par la fonction ",acces); fprintf(STDERR," registreSalto(char*) (fonction appelDeFonctionsSortiesAppelExterne dans instrumentation.cc)\n"); exit(9); } appelDeFonctionReg(bb, position, nbInstructionsAjoutees, OUT, identificateurRessource, NULL);}

void instrumenter(INST *inst, BB *bb, BB *bbSuivant, int position, unsigned int *nbInstructionsAjoutees, int numeroInst){ static unsigned char flagDelaySlot = 0; // Si l’instruction est une instruction d’appel externe, on remplace "call tartampion" par "call my_tartempion" // pour détourner l’appel "normal" à la fonction de la librairie en un appel à une fonction redéfinie permettant de // rendre compte des accès mémoires fait par ces fonctions if(typeInstruction(inst) == T_APPEL_EXTERNE) { char chaine[100],chaine2[100], *tmp; sscanf(inst−>unparse()," %s %s",chaine,chaine2); strcpy(chaine, " \tcall "PREFIXE_FONCTIONS_EXTERNES); // Allocation d’une nouvelle chaine de caractère contenant la nouvelle représentation de l’instruction tmp = ( char *)malloc((strlen(chaine)+strlen(chaine2)+2)* sizeof( char )); strcpy(tmp,chaine);

03 jun 03 16:11 Page 15/23instrumentation.cc strcat(tmp,chaine2); strcat(tmp," \n"); inst−>addAttribute(UNPARSE_ATT, tmp, strlen(tmp)+1); } // Si on n’a pas à faire à une instruction se trouvant dans un DelaySlot if(flagDelaySlot == 0) // Si l’instruction n’est pas un branchement, alors, on instrumente cette instruction normalement if(!inst−>isCTI()) { sauvegardeContexte(bb, position, nbInstructionsAjoutees); appelDeFonctionInstDebut(bb, position, nbInstructionsAjoutees, numeroInst, typeInstruction(inst), NULL); appelDeFonctionsEntrees(inst, bb, position, nbInstructionsAjoutees, NULL); if(typeInstruction(inst)==T_SAVE || typeInstruction(inst)==T_RESTORE) appelDeFonctionInstMilieu(bb, position, nbInstructionsAjoutees, NULL); appelDeFonctionsSorties(inst, bb, position, nbInstructionsAjoutees, NULL);

appelDeFonctionInstFin(bb, position, nbInstructionsAjoutees, NULL); restaurationContexte(bb, position, nbInstructionsAjoutees); } // Si l’instruction courante est un branchement, alors, on l’instrumente ainsi que son DelaySlot else { char *chaineAnnulBit = ( char *)malloc(100* sizeof( char )); INST *instDelaySlot = bbSuivant−>getAsm(0); /*fprintf(STDERR,"Inst <%s>\t\t\tDelay <%s>\n",inst−>unparse(),instDelaySlot−>unparse());*/ // On met le flag à 1 pour indiquer que l’instrumentation de l’instruction se trouvant dans le DelaySlot // du branchement que l’on est en train de traiter a déjà été instrumentée flagDelaySlot = 1; sauvegardeContexte(bb, position, nbInstructionsAjoutees); // On traite le début de l’instruction de branchement appelDeFonctionInstDebut(bb, position, nbInstructionsAjoutees, numeroInst, typeInstruction(inst), NULL); // On traite les lectures de l’instruction de branchement appelDeFonctionsEntrees(inst, bb, position, nbInstructionsAjoutees, NULL); // On traite les écritures de l’instruction de branchement appelDeFonctionsSorties(inst, bb, position, nbInstructionsAjoutees, NULL);

appelDeFonctionCopierInstDelay(bb, position, nbInstructionsAjoutees); // Si le branchement est un brachement avec annul_bit (ex : bl,a ...) alors on rempli la chaine de caractère

// chaineAnnulBit en conséquence (on y met les instructions pour traiter ce cas correctement) if(typeInstruction(inst) == T_BRANCHEMENT_ANNUL_BIT)




{ int i; char tmp[20];

regex_t *preg = new regex_t(); size_t nmatch = 1; regmatch_t pmatch[nmatch];

if (regcomp(preg, EXP_ANNUL_BIT, REG_EXTENDED))

{ fprintf(STDERR," Erreur lors de la compilation de l’expression régulière \""EXP_ANNUL_BIT" \"\n"); exit(4); } if (regexec(preg, inst−>unparse(), nmatch, pmatch, 0) == REG_NOMATCH) { fprintf(STDERR," Erreur lors de l’exécution de l’expression régulière \""EXP_ANNUL_BIT" \" :\n");

fprintf(STDERR," Impossible de trouver l’expression régulière dans l’instruction \"%s\"\n",inst−>unparse()); exit(4); } regfree(preg);

for(i=0; i<pmatch[0].rm_eo; i++) tmp[i] = (inst−>unparse())[i]; tmp[i] = ’ \0’;

strcpy(chaineAnnulBit," \trd %pc,%o7\n"); strcat(chaineAnnulBit," \tadd %o7,16,%o7\n"); strcat(chaineAnnulBit," \twr %l0,%ccr\n"); strcat(chaineAnnulBit,tmp);

strcat(chaineAnnulBit," "ETIQUETTE_FONCTION_NOP"\n"); } else chaineAnnulBit = NULL; // On traite le début de l’instruction qui se trouve dans le DelaySl

ot appelDeFonctionInstDebut(bb, position, nbInstructionsAjoutees, numeroInst+1, typeInstruction(instDelaySlot), chaineAnnulBit); // On traite les lectures de l’instruction se trouvant dans le DelaySlot du branchement appelDeFonctionsEntrees(instDelaySlot, bb, position, nbInstructionsAjoutees, chaineAnnulBit); appelDeFonctionInstMilieu(bb, position, nbInstructionsAjoutees, chaineAnnulBit); // On traite les écritures de l’instruction se trouvant dans le DelaySlot du branchement appelDeFonctionsSorties(instDelaySlot, bb, position, nbInstructionsAjoutees, chaineAnnulBit);

// On traite la fin de l’instruction qui se trouve dans le DelaySlot appelDeFonctionInstFin(bb, position, nbInstructionsAjoutees, chaineAnnulBit);

appelDeFonctionEchangerInstDelay(bb, position, nbInstructionsAjoutees); // Si l’instruction est un call externe, on lui ajoute comme entrées et sorties les paramètres consommés

// et produits par cette fonction if(typeInstruction(inst) == T_APPEL_EXTERNE || typeInstruction(inst) == T_APPEL_EXTERNE_SPECIAL)

03 jun 03 16:11 Page 17/23instrumentation.cc{ switch (inst−>numberOfAttributes(COMMENT_ATT)) { case 1 : appelDeFonctionsEntreesAppelExterne(inst, bb, position, nbInstruct

ionsAjoutees); break; case 2 : appelDeFonctionsEntreesAppelExterne(inst, bb, position, nbInstruct

ionsAjoutees); appelDeFonctionsSortiesAppelExterne(inst, bb, position, nbInstruct

ionsAjoutees); break; default : fprintf(STDERR," Passage impossible : fonction instrumenter dans instrumentation.cc\n"); }}

// On traite la fin de l’instruction de branchement seulment si on n’a pas à faire à un appel externe interceptées par les

// fonctions redéfinies dans redefinition.c if(typeInstruction(inst)!=T_APPEL_EXTERNE) appelDeFonctionInstFin(bb, position, nbInstructionsAjoutees, NULL);

appelDeFonctionEchangerInstDelay(bb, position, nbInstructionsAjoutees);

restaurationContexte(bb, position, nbInstructionsAjoutees); } // Si l’instruction se trouve dans un DelaySlot, on remet le flag correspondant à 0 else flagDelaySlot = 0;}

void ajouterCommentaireAppelExterne(INST *inst){ int i,j; char etiquette[100], ligneCourante[200]; regex_t *preg_fct = new regex_t(); regex_t *preg_etiquette = new regex_t(); regex_t *preg_params = new regex_t(); regex_t *preg_result = new regex_t(); size_t nmatch = 1; regmatch_t pmatch[nmatch]; regmatch_t pmatch_params[nmatch]; regmatch_t pmatch_result[nmatch];

// Compilation de l’expression régulière permettant de détecter si une instruction est une fonction if (regcomp(preg_fct, EXP_FONCTION, REG_EXTENDED)) { fprintf(STDERR," Erreur lors de la compilation de l’expression régulière \""EXP_FONCTION"\"\n"); exit(4); }

regexec(preg_fct, inst−>unparse(), nmatch, pmatch, 0); // On récupère dans la chaine etiquette l’étiquette associée au call traité for(i=0,j=pmatch[0].rm_eo; j<strlen(inst−>unparse()); j++)




if((inst−>unparse())[j]!=’ ’ && (inst−>unparse())[j]!=’ \t’) etiquette[i++]=(inst−>unparse())[j]; etiquette[i] = ’ \0’; if (regcomp(preg_etiquette, etiquette, REG_EXTENDED)) { fprintf(STDERR," Erreur lors de la compilation de l’expression régulière \"%s\"\n",etiquette); exit(4); } if (regcomp(preg_params, " [ ]+! params =[ ]+", REG_EXTENDED)) { fprintf(STDERR," Erreur lors de la compilation de l’expression régulière \"[ \t]+! params =[ \t]+\"\n"); exit(4); } if (regcomp(preg_result, " [ ]+! Result =[ ]+", REG_EXTENDED)) { fprintf(STDERR," Erreur lors de la compilation de l’expression régulière \"[ \t]+! Result =[ \t]+\"\n"); exit(4); } // On cherche, dans le fichier assembleur original, la ligne contenant l’appel à la fonction traitée do { char c; i=0; do { c = fgetc(fichierSOriginal); ligneCourante[i++] = c; } while(c != ’ \n’); ligneCourante[i] = ’ \0’; } while (regexec(preg_fct, ligneCourante, nmatch, pmatch, 0) == REG_NOMATCH || regexec(preg_etiquette, ligneCourante, nmatch, pmatch, 0) == REG_NOMATCH || regexec(preg_params, ligneCourante, nmatch, pmatch_params, 0) == REG_NOMATCH || regexec(preg_result, ligneCourante, nmatch, pmatch_result, 0) == REG_NOMATCH ||

feof(fichierSOriginal));

regfree(preg_fct); regfree(preg_etiquette); regfree(preg_params); regfree(preg_result);

if(feof(fichierSOriginal)) { fprintf(STDERR," Erreur : fin du fichier .s original atteinte "); fprintf(STDERR," (fonction ajouterCommentaireAppelExterne dans instrumentation.cc)\n"); exit(7); } // Ici, la variable ligneCourante contient la ligne du fichier assembleur correspondant à l’appel // de la fonction traitée (qui contient donc aussi en commentaire les paramètres de cette fonction) char liste[100],*tmp;

03 jun 03 16:11 Page 19/23instrumentation.cc // On récupère la liste des paramètres d’entrée for(i=0,j=pmatch_params[0].rm_eo; j<pmatch_result[0].rm_so; j++) liste[i++]=ligneCourante[j]; liste[i] = ’ \0’; // Puis on la range dans les attributs à mettre en commentaire dans le fichier généré // NOTE : ces commentaires servent aussi par la suite à identifier quels sont les accès fait par la fonction externe tmp = ( char *)malloc((strlen(liste)+1)* sizeof( char )); strcpy(tmp,liste); inst−>addAttribute(COMMENT_ATT, tmp, strlen(liste)+1); // On récupère la liste contenant le résultat (paramètre de sortie) for(i=0,j=pmatch_result[0].rm_eo; ligneCourante[j]!=’ !’ && ligneCourante[j]!=’ ’ &&

ligneCourante[j]!=’ \t’ && ligneCourante[j]!=’ \n’; j++) liste[i++]=lign

eCourante[j]; liste[i] = ’ \0’; // Puis, si la chaine n’est pas vide, on la range dans les attributs à mettre en commentaire dans le fichier généré // NOTE : ces commentaires servent aussi par la suite à identifier quels sont les accès fait par la fonction externe if(liste[0] != ’ \0’) { tmp = ( char *)malloc((strlen(liste)+1)* sizeof( char )); strcpy(tmp,liste); inst−>addAttribute(COMMENT_ATT, tmp, strlen(tmp)+1); }}

void Salto_hook(){ CFG *proc; BB *bb,*bbSuivant; INST *inst; int numeroInst; unsigned int nbInstructionsAjoutees; // Parcours du programme permettant de récupérer les paramètres des fonctions définies à // l’extérieur des fichiers .s locaux for ( int i=0; i < numberOfCFG(); i++) { proc = getCFG(i); for ( int j=0; j < proc−>numberOfBB(); j++) { bb = proc−>getBB(j); for ( int k=0; k < bb−>numberOfAsm(); k++) {

inst = bb−>getAsm(k);

if(typeInstruction(inst) == T_APPEL_EXTERNE ||




typeInstruction(inst) == T_APPEL_EXTERNE_SPECIAL) ajouterCommentaireAppelExterne(inst); } } } // Parcours du programme permettant d’insérer le code d’instrumentation des instructions numeroInst = 0; for ( int i=0; i < numberOfCFG(); i++) { proc = getCFG(i); for ( int j=0; j < proc−>numberOfBB(); j++) { bb = proc−>getBB(j); bbSuivant = proc−>getBB(j+1); int nbAsm = bb−>numberOfAsm(); nbInstructionsAjoutees = 0; for ( int k=0; k < nbAsm; k++) {

numeroInst++;inst = bb−>getAsm(k+nbInstructionsAjoutees);

instrumenter(inst, bb, bbSuivant, k, &nbInstructionsAjoutees, numeroInst); } } }

// Parcours du programme permettant d’insérer le code pour l’initialisation des variables globales // et d’affichage de ces variables en fin d’exécution du programme. for ( int i=0; i < numberOfCFG(); i++) { proc = getCFG(i);

if(!strcmp(proc−>getName()," main")) { // Insertion d’un appel à la procédure initialisant les variables globales (proc−>getBB(0))−>insertAsm(0, newAsm(" call initVariablesGlobales")); (proc−>getBB(0))−>insertAsm(1, newAsm(NOP)); for ( int j=0; j < proc−>numberOfBB(); j++) { bb = proc−>getBB(j);

for ( int k=0; k < bb−>numberOfAsm(); k++) {

inst = bb−>getAsm(k);

// Insertion d’un appel à la procédure d’affichage des structures de données juste avant l’instruction "call exit" if(estPresent(" call",inst−>unparse()) && estPresent(" exit",inst−>unparse()))

{ bb−>insertAsm(k, newAsm(" call afficherSdd")); bb−>insertAsm(k+1, newAsm(NOP)); break; }

03 jun 03 16:11 Page 21/23instrumentation.cc}

} break; } } // Envoi du code instrumenté vers la sortie standard produceCode(fichierSInstrumente);}

void Salto_init_hook( int argc, char *argv[]){ int i,j,k; char nomFichierSortie[100];

// Récupération dans la ligne de commande entrée par l’utilisateur du nom du fichier original for(i=1; i<argc && !estPresent(" −i",argv[i]); i++); if(i == argc−1) { fprintf(STDERR," Erreur, votre ligne de commande ne comporte pas l’option \"−i\"\n"); exit(6); } // On ouvre le fichier .s original à traiter pour pouvoir s’en servir dans salto_hook() fichierSOriginal = fopen(argv[i+1]," r"); if(fichierSOriginal == NULL) { fprintf(STDERR," Problème lors de l’ouverture du fichier \"%s\" ",argv[i+1]); fprintf(STDERR," (fonction Salto_init_hook dans le fichier instrumentation.cc)\n"); exit(11); }

nomFichierSortie[0]=’ \0’; strcat(nomFichierSortie,REPERTOIRE_FICHIER_INSTRUMENTES); strcat(nomFichierSortie,argv[i+1]); // On ouvre le fichier .s instrumenté en écriture à traiter pour pouvoir s’en servir dans salto_hook() fichierSInstrumente = fopen(nomFichierSortie," w"); if(fichierSInstrumente == NULL) { fprintf(STDERR," Problème lors de l’ouverture du fichier \"%s\" ",nomFichierSortie); fprintf(STDERR," (fonction Salto_init_hook dans le fichier instrumentation2.cc)\n"); exit(11); } // Recherche de l’expression "−−" dans la ligne de commande for(; i<argc && !estPresent(" −−",argv[i]); i++); // Si cette expression n’est pas présente, on ne numérote pas les fichiers if(i == argc−1) numeroFichier = 0; else numeroFichier=atoi(argv[i+1]);}




void Salto_end_hook(){ exit(0);}




#define STDERR stdout

#define TRACE_INSTRUCTIONS_INUTILES "../trace_inutile.txt"#define TRACE_INSTRUCTIONS_STATIQUES_INUTILES "../trace_statiques_inutile.txt"#define TRACE_EVOLUTION_INUTILES "../evolution_inutile.txt"#define TRACE_VALEURS_MORTES "../evolution_valeurs_mortes.txt"

/* Défini le nom de la fonction à appeler à chaque début de bloc de base */#define NOM_FCT_IN_MEM "instrumentationEntreeMemoire"#define NOM_FCT_OUT_MEM "instrumentationSortieMemoire"

#define NOM_FCT_IN_REG "instrumentationEntreeRegistre"#define NOM_FCT_OUT_REG "instrumentationSortieRegistre"

#define NOM_FCT_DEBUT_INST "instrumentationInstructionDebut"#define NOM_FCT_MILIEU_INST "instrumentationInstructionMilieu"#define NOM_FCT_FIN_INST "instrumentationInstructionFin"#define NOM_FCT_INST "instrumentationInstruction"

/* Défini les différentes valeur que peut prendre la variable typeInstruction dans la structure instruction */#define T_APPEL_EXTERNE 0#define T_APPEL_EXTERNE_SPECIAL 1#define T_APPEL_INTERNE 2#define T_BRANCHEMENT 3#define T_BRANCHEMENT_ANNUL_BIT 4#define T_SAVE 5#define T_RESTORE 6#define T_LOAD 7#define T_STORE 8#define T_NOP 9#define T_AUTRE 10

/* Identifiant Salto du registre %g0 */#define ID_REG_SALTO_G 41/* Identifiant Salto du registre %o0 */#define ID_REG_SALTO_O 49/* Identifiant Salto du registre %l0 */#define ID_REG_SALTO_L 57/* Identifiant Salto du registre %i0 */#define ID_REG_SALTO_I 65/* Décalage, en nombre de registres, entre une fenêtre et la suivante */#define OFFSET_FENETRE 16

/* A virer dans la version optimisée */#define MAX_NB_INST_DYNAMIQUE 10000000

void instrumentationInstructionDebut(int typeInstruction, int numeroInst, int numeroFichier);void instrumentationInstructionMilieu(void );void instrumentationInstructionFin(void );void copierInstDelay(void );void echangerInstDelay(void );void instrumentationEntreeRegistre(int identificateurRessource);void instrumentationSortieRegistre(int identificateurRessource);void instrumentationEntreeMemoire(int adresseMemoire, int nbOctetsLus);void instrumentationSortieMemoire(int adresseMemoire, int nbOctetsEcrits);

16 jun 03 17:02 Page 1/1instrument.h


mercredi 18 juin 2003 14/37instrument.h

#include <stdio.h>#include <stdlib.h>#include " instrument.h"

#define NB_REGISTRES 115#define NB_REGISTRES_TOURNANTS 100000/* MAX_NB_OPERANDES doit etre égal au maximum d’opérandes que peuvent avoir les instruction +1 ! */#define MAX_NB_OPERANDES 150

/* Défini les différentes valeur que peuvent prendre les variables utiliteInst[i], i allant de 0 à MAX_NB_INST_DYNAMIQUE.*/#define INUTILE 0#define UTILE 1#define NOP 2

#define GENERER_FICHIER_DOT 1#define FICHIER_TRACE_DOT " graphe_dependances.dot"

#define MAX_NB_INST_STATIQUES 11000#define MAX_INST_STATIQUES_TOTAL 250000#define NB_FICHIERS 15

typedef unsigned char flag;

typedef struct instru { unsigned char numeroFichier; unsigned int numeroStatique; unsigned int numeroDynamique; flag typeInstruction; struct instru *origineOperandes[MAX_NB_OPERANDES]; struct instru *precedent;} instruction;

typedef struct mem { int adresse; unsigned int nbLecture; instruction *derniereEcriture; struct mem *suivant;} elementMemoire;

/* Définition des registres généraux */instruction *tableRegistres[NB_REGISTRES];unsigned int tableLectureRegistres[NB_REGISTRES];

/* Définition des registres tournants */instruction *tableRegistresTournants[NB_REGISTRES_TOURNANTS];unsigned int tableLectureRegistresTournants[NB_REGISTRES_TOURNANTS];unsigned int niveauFenetreRegistre = 0;

/* Définition des zones mémoires (point d’entrée dans la liste chainée) */elementMemoire *adresseInitiale = NULL;

/* Définition des instructions (point d’entrée dans la liste chainée et tableau

18 jun 03 17:55 Page 1/13instrument.cde flag) */flag utiliteInst[MAX_NB_INST_DYNAMIQUE];flag valeursMortes[MAX_NB_INST_DYNAMIQUE];instruction *instInitiale;instruction *instCourante = NULL;instruction *instCouranteDelay = NULL;

unsigned int occurencesInutileInstStatiques[MAX_NB_INST_STATIQUES][NB_FICHIERS];unsigned int occurencesInstStatiques[MAX_NB_INST_STATIQUES][NB_FICHIERS];

unsigned int allocation=0;

/* Utile uniquement pour la version donnant la proportion d’instruction statiques inutiles */int cptInstStatiquesTraitees;

void initVariablesGlobales( void ){ int i,j;

/* Création d’une instruction initiale fictive sur laquelle vont pointer celles qui utilisent des registres déjà initialisés lors du lancement du programme */ instInitiale = malloc( sizeof(instruction)); allocation++; if(instInitiale == NULL) { fprintf(stderr," Taille mémoire maximale allouable dépassée !! "); fprintf(stderr," (fonction initVariablesGlobales dans le fichier instrument.c)\n"); exit(10); } instInitiale−>numeroStatique = 0; instInitiale−>numeroDynamique = 0; instInitiale−>numeroFichier = 0; for(i=0; i<MAX_NB_OPERANDES; i++) instInitiale−>origineOperandes[i] = NULL; instInitiale−>typeInstruction = T_AUTRE; instInitiale−>precedent = NULL; instCourante = instInitiale; for(i=0; i<NB_REGISTRES; i++) { tableRegistres[i] = instInitiale; tableLectureRegistres[i] = 0; } for(i=0; i<NB_REGISTRES_TOURNANTS; i++) { tableRegistresTournants[i] = instInitiale; tableLectureRegistresTournants[i] = 0; } for(i=0; i<MAX_NB_INST_DYNAMIQUE; i++) { utiliteInst[i] = INUTILE; valeursMortes[i] = 0; } for(i=0; i<MAX_NB_INST_STATIQUES; i++)

18 jun 03 17:55 Page 2/13instrument.c


mercredi 18 juin 2003 15/37instrument.c

for(j=0; j<NB_FICHIERS; j++) { occurencesInstStatiques[i][j]=0; occurencesInutileInstStatiques[i][j]=0; }}

void remonterArbre(instruction *inst){ int i; /* Si on n’a pas encore parcouru l’arbre de dépendance de l’instuction inst, on le parcours pour pour positionner les flag d’utilité utiliteInst[inst−>numeroDynamique] */ if(utiliteInst[inst−>numeroDynamique]!=UTILE) { utiliteInst[inst−>numeroDynamique] = UTILE; for(i=0; inst−>origineOperandes[i]!= NULL; i++) remonterArbre(inst−>origineOperandes[i]); }}

insert( float *tableauInstStatiqueInutiles, float valeur){ int i,j,k; for(i=0; tableauInstStatiqueInutiles[i]>valeur; i++); for(k=cptInstStatiquesTraitees; k!=i; k−−) tableauInstStatiqueInutiles[k]=tableauInstStatiqueInutiles[k−1]; tableauInstStatiqueInutiles[i] = valeur; cptInstStatiquesTraitees++;}

/* Fonction de debug permettant d’afficher la liste chainée des instructions, la table des registres et enfin le pourcentage d’instructions utile et inutiles */void afficherSdd( void ){ instruction *i; elementMemoire *a; int j,k,cptUtile=0,cptInutile=0,cptNop=0,cptInstStatique=0,cptInstStatiqueOccurencesInutile=0, cptLoadInutile=0,cptLoad=0,cptStoreInutile=0,cptStore=0,cptMortes=0,nbTotalInstructions; unsigned int instInutileArtificiel; float tableauInstStatiqueInutiles[MAX_INST_STATIQUES_TOTAL]; /* Définition du fichier contenant la trace (numéro) des instructions inutiles) */ FILE *traceInstructionsInutiles = fopen(TRACE_INSTRUCTIONS_INUTILES," w"); FILE *traceInstructionsStatiquesInutiles = fopen(TRACE_INSTRUCTIONS_STATIQUES_INUTILES," w"); FILE *fichierEvolutionQtValeursMortes = fopen(TRACE_VALEURS_MORTES," w"); FILE *fichierDot;

if(GENERER_FICHIER_DOT) {

18 jun 03 17:55 Page 3/13instrument.c fichierDot = fopen(FICHIER_TRACE_DOT," w"); if(fichierDot== NULL) { fprintf(stderr," Problème lors de l’ouverture du fichier \""FICHIER_TRACE_DOT"\" "); fprintf(stderr," (fonction afficherSdd dans le fichier instrument.c)\n"); exit(11); } fprintf(fichierDot," digraph G {\n"); }

if(traceInstructionsInutiles== NULL) { fprintf(stderr," Problème lors de l’ouverture du fichier \""TRACE_INSTRUCTIONS_INUTILES" \" "); fprintf(stderr," (fonction afficherSdd dans le fichier instrument.c)\n"); exit(11); } /* Affichage des dépendances entre les instructions dynamiques (stockées dans la liste chainée d’instructions dynamiques) */ for(i=instCourante; i!= NULL; i=i−>precedent) { if(GENERER_FICHIER_DOT && utiliteInst[i−>numeroDynamique]!=NOP) { if(utiliteInst[i−>numeroDynamique]==INUTILE) fprintf(fichierDot," \t%d [color=\".0 .0 .8\",fontcolor=\".0 .0 .8\"];\n", i−>numeroDynamique); } fprintf(stdout," I.Dynamic %d\t−− I.Static %d\t−− File %d",i−>numeroDynamique,i−>numeroStatique,i−>numeroFichier); if(utiliteInst[i−>numeroDynamique]==UTILE) fprintf(stdout," \t−− utile"); else if(utiliteInst[i−>numeroDynamique]==INUTILE) fprintf(stdout," \t−− INUTILE"); else if(utiliteInst[i−>numeroDynamique]==NOP) fprintf(stdout," \t−− nop"); if(i−>origineOperandes[0]!= NULL) { fprintf(stdout," \t−− Dépend de %d",(i−>origineOperandes[0])−>numeroDynamique); if(GENERER_FICHIER_DOT && utiliteInst[i−>numeroDynamique]!=NOP) { fprintf(fichierDot," \t%d −> %d", i−>numeroDynamique, (i−>origineOperandes[0])−>numeroDynamique); if(utiliteInst[i−>numeroDynamique]==INUTILE) fprintf(fichierDot," [color=\".0 .0 .8\"]"); fprintf(fichierDot," ;\n"); } } for(j=1; j<MAX_NB_OPERANDES; j++) if(i−>origineOperandes[j]!= NULL) { fprintf(stdout," ,%d",(i−>origineOperandes[j])−>numeroDynamique); if(GENERER_FICHIER_DOT && utiliteInst[i−>numeroDynamique]!=NOP)

{ fprintf(fichierDot," \t%d −> %d", i−>numeroDynamique, (i−>origineOperandes[j])−>numeroDynamique); if(utiliteInst[i−>numeroDynamique]==INUTILE) fprintf(fichierDot," [color=\".0 .0 .8\"]"); fprintf(fichierDot," ;\n");




} } fprintf(stdout," \n");

if(utiliteInst[i−>numeroDynamique]==INUTILE) { /* Ecriture dans le fichier traceInstructionsInutiles du numéro des instructions dynamiques inutiles */ fprintf(traceInstructionsInutiles," %u\n",i−>numeroDynamique); occurencesInutileInstStatiques[i−>numeroStatique][i−>numeroFichier]++; } occurencesInstStatiques[i−>numeroStatique][i−>numeroFichier]++; switch (i−>typeInstruction) { case T_LOAD : cptLoad++; if(utiliteInst[i−>numeroDynamique]==INUTILE) cptLoadInutile++; break; case T_STORE : cptStore++;

if(utiliteInst[i−>numeroDynamique]==INUTILE) cptStoreInutile++; } } fclose(traceInstructionsInutiles); if(GENERER_FICHIER_DOT) { fprintf(fichierDot," } "); fclose(fichierDot); } /* Affichage de la table des registres fixes avec les informations qui lui sont relatives */ fprintf(stdout," \nTable des registres fixes :\n"); for(j=0; j<NB_REGISTRES; j++) { if(tableRegistres[j]−>numeroDynamique != 0 || tableLectureRegistres[j] != 0) { fprintf(stdout," Registre numéro %d\t",j); fprintf(stdout," : Modifié par l’instruction %d\t",tableRegistres[j]−>numeroDynamique); fprintf(stdout," et lu depuis par %d instruction(s)\n",tableLectureRegistres[j]); } } /* Affichage de la table des registres tournants avec les informations qui lui sont relatives */ fprintf(stdout," \nTable des registres tournants (niveau actuel : %d) :\n",niveauFenetreRegistre); for(j=0; j<NB_REGISTRES_TOURNANTS; j++) { if(tableRegistresTournants[j]−>numeroDynamique != 0 || tableLectureRegistresTournants[j] != 0) { fprintf(stdout," Registre tournant numéro %d\t",j); fprintf(stdout," : Modifié par l’instruction %d\t",tableRegistresTournants[j]−>numeroDynamique); fprintf(stdout," et lu depuis par %d instruction(s)\n",tableLectureRegistresTournants[j

18 jun 03 17:55 Page 5/13instrument.c]); } } /* Affichage de la liste chainée contenant les adresses mémoire */ fprintf(stdout," \nListe des adresses mémoires :\n"); for(a=adresseInitiale; a!= NULL; a=a−>suivant) { fprintf(stdout," Adresse mémoire %d\t",a−>adresse); fprintf(stdout," : Modifié par l’instruction %d\t",a−>derniereEcriture−>numeroDynamique); fprintf(stdout," et lu depuis par %d instruction(s)\n",a−>nbLecture); } /* On compte le nombre d’instructions utiles et inutiles afin de l’afficher */ for(j=0; j<instCourante−>numeroDynamique; j++) { switch (utiliteInst[j]) { case UTILE : cptUtile++; break; case INUTILE : cptInutile++; break; case NOP : cptNop++; break; default : fprintf(stderr," Passage impossible : fonction afficherSdd dans instrument.c\n"); } if(valeursMortes[j] == 0) cptMortes++; if(valeursMortes[j] == 0 && utiliteInst[j] != INUTILE) { fprintf(stderr," Instruction %d !!!!\n",j); } if(j%20 == 0) fprintf(fichierEvolutionQtValeursMortes," %d\t%d\n",j,cptMortes); } fclose(fichierEvolutionQtValeursMortes); nbTotalInstructions = instCourante−>numeroDynamique; fprintf(stdout," \nCalcul prenant en compte les \"nop\" :\n"); fprintf(stdout," Nombre d’instructions inutiles : %d/%d soit %f %%\n", cptInutile,nbTotalInstructions,( float )(cptInutile*100)/( float )nbTotalInstructions); fprintf(stdout," Nombre d’instructions utiles : %d/%d soit %f %%\n", cptUtile,nbTotalInstructions,( float )(cptUtile*100)/( float )nbTotalInstructions); fprintf(stdout," Nombre de nop : %d/%d soit %f %%\n\n", cptNop,nbTotalInstructions,( float )(cptNop*100)/( float )nbTotalInstructions); nbTotalInstructions = instCourante−>numeroDynamique − cptNop; fprintf(stdout," \nCalcul ne prenant pas en compte les \"nop\" :\n"); fprintf(stdout," Nombre d’instructions inutiles : %d/%d soit %f %%\n", cptInutile,nbTotalInstructions,( float )(cptInutile*100)/( float )nbTotalInstructions); fprintf(stdout," Nombre d’instructions utiles : %d/%d soit %f %%\n\n", cptUtile,nbTotalInstructions,( float )(cptUtile*100)/( float )nbTotalInstructions); fprintf(stdout," Nombre d’instructions dont le résultat est mort : %d/%d soit %f %%\n\n", cptMortes,nbTotalInstructions,( float )(cptMortes*100)/( float )nbTotalInstructions); fprintf(stdout," \n\nNombre d’ocurences d’instructions inutiles pour une instruction statique : \n");




tableauInstStatiqueInutiles[0] = 0.0; /* Lignes de la matrice */ for(k=0; k<MAX_NB_INST_STATIQUES; k++) { if(k==0) for(j=1; j<NB_FICHIERS; j++) fprintf(stdout," \t%d",j); else { fprintf(stdout," \n%d :\t",k); /* Colonnes de la matrice */ for(j=1; j<NB_FICHIERS; j++) { if(occurencesInstStatiques[k][j]!=0) {

fprintf(stdout," %u/%u\t",occurencesInutileInstStatiques[k][j],occurencesInstStatiques[k][j]);

cptInstStatique++; if(occurencesInutileInstStatiques[k][j]!=0) cptInstStatiqueOccurencesI

nutile++; insert(tableauInstStatiqueInutiles,( float )occurencesInutileInstStatiqu

es[k][j]/( float )occurencesInstStatiques[k][j]);}

else fprintf(stdout," \t"); } } } for(j=0; j<cptInstStatiquesTraitees; j++) fprintf(traceInstructionsStatiquesInutiles," %d\t%f\n",cptInstStatiquesTraitees,tableauInstStatiqueInutiles[j]); fclose(traceInstructionsStatiquesInutiles); fprintf(stdout," \nNombre d’instructions statique ayant des occurences inutiles / Nombre d’instructions statiques utilisées : %d/%d soit %f %%\n", cptInstStatiqueOccurencesInutile, cptInstStatique, ( float )(cptInstStatiqueOccurencesInutile*100)/( float )cptInstStatique); fprintf(stdout," \nNombre de load inutiles / Nombre de load dynamique total : %d/%d soit %f %%\n", cptLoadInutile,cptLoad,( float )(cptLoadInutile*100)/( float )cptLoad); fprintf(stdout," \nNombre de store inutiles / Nombre de store dynamique total : %d/%d soit %f %%\n", cptStoreInutile,cptStore,( float )(cptStoreInutile*100)/( float )cptStore); fprintf(stdout," Nombre de noeuds total dans le graphe : %d\n",allocation);}

/* Création de la représentation des instructions dynamiques en mémoire *//* !!!!! Attention, cette fonction est différente selon qu’on utilise le programme sur Sparc ou x86 (DelaySlot) */void instrumentationInstructionDebut( int typeInstruction, int numeroInst, int numeroFichier){ int i; instruction *tmp = malloc( sizeof(instruction));

18 jun 03 17:55 Page 7/13instrument.c allocation++; if(tmp == NULL) { fprintf(stderr," Taille mémoire maximale allouable dépassée !! "); fprintf(stderr," (fonction instrumentationInstructionDebut dans le fichier instrument.c)\n"); exit(10); }

if(instCourante−>numeroDynamique >= MAX_NB_INST_DYNAMIQUE) { fprintf(stderr," Nombre maximum d’instruction dépassé, veulliez augmenter la valeur de la constante "); fprintf(stderr," MAX_NB_INST_DYNAMIQUE dans le fichier instrument.c\n"); exit(1); } tmp−>numeroStatique = numeroInst; tmp−>numeroFichier = numeroFichier; tmp−>typeInstruction = typeInstruction; /* On passe pour la première fois dans cette fonction */ if(instCourante == NULL) { tmp−>numeroDynamique = 1; tmp−>precedent = instInitiale; } else { tmp−>numeroDynamique = instCourante−>numeroDynamique+1; tmp−>precedent = instCourante; } for(i=0; i<MAX_NB_OPERANDES; i++) tmp−>origineOperandes[i] = NULL; instCourante = tmp; /*fprintf(stderr,"Début statique %d dynamique %d fichier %d >",numeroInst,tmp−>numeroDynamique,tmp−>numeroFichier);*/}

/* !!!!! Attention, cette fonction n’est utile que pour les machines utilisant un DelaySolt (Sparc) */void instrumentationInstructionMilieu( void ){ /* Si l’instruction est un save, on incrémente le niveau de la fenetre de registres */ if(instCourante−>typeInstruction == T_SAVE) niveauFenetreRegistre++; /* Si c’est un restore, on décrémente le niveau de la fenetre de registres */ else if(instCourante−>typeInstruction == T_RESTORE) niveauFenetreRegistre−−;}

void instrumentationInstructionFin( void ){ /* Si l’instruction courante est un branchement quelconque, un save ou un restore, on la marque comme utile et on marque comme utile toute les instructions dont elle dépend (appel récursif à remonterArbre) */ if(instCourante−>typeInstruction == T_BRANCHEMENT || instCourante−>typeInstruction == T_BRANCHEMENT_ANNUL_BIT ||




instCourante−>typeInstruction == T_SAVE || instCourante−>typeInstruction == T_RESTORE || instCourante−>typeInstruction == T_APPEL_INTERNE || instCourante−>typeInstruction == T_APPEL_EXTERNE || instCourante−>typeInstruction == T_APPEL_EXTERNE_SPECIAL) remonterArbre(instCourante); if(instCourante−>typeInstruction == T_NOP) utiliteInst[instCourante−>numeroDynamique] = NOP; /*fprintf(stderr,"< Fin statique %d dynamique %d fichier %d\n",instCourante−>numeroStatique,instCourante−>numeroDynamique,instCourante−>numeroFichier);*/}

/* !!!!! Attention, cette fonction n’est utile que pour les machines utilisant un DelaySolt (Sparc) */void copierInstDelay( void ){ instCouranteDelay = instCourante;}

/* !!!!! Attention, cette fonction n’est utile que pour les machines utilisant un DelaySolt (Sparc) */void echangerInstDelay( void ){ instruction *tmp = instCourante; instCourante = instCouranteDelay; instCouranteDelay = tmp;}

/* Traitement fait lorsqu’on rencontre une instruction qui accède à la mémoire ou à des registres (en entrée) *//* !!!!! Attention, cette fonction est différente selon qu’on utilise le programme sur Sparc ou x86 (registres) */void instrumentationEntreeRegistre( int identificateurRessource){ int i; unsigned int identificateurRegistreTournant; /* identificateurRessource numéro ID_REG_SALTO_G = trou noir (%g0) */ if(identificateurRessource != ID_REG_SALTO_G) { /* Si le registre accédé fait partie de la fenêtre de registres tournante */ if(identificateurRessource>=ID_REG_SALTO_O && identificateurRessource<=ID_REG_SALTO_I+7) { identificateurRegistreTournant = (72−identificateurRessource)+(niveauFenetreRegistre*OFFSET_FENETRE);

if(identificateurRegistreTournant>=NB_REGISTRES_TOURNANTS) { fprintf(stderr," Nombre maximum de registres tournants dépassé, veulliez augmenter la valeur de "); fprintf(stderr," la constante NB_REGISTRES_TOURNANTS dans le fichier instrument.c\n"); exit(1); }

tableLectureRegistresTournants[identificateurRegistreTournant]++;

18 jun 03 17:55 Page 9/13instrument.c for(i=0; (instCourante−>origineOperandes)[i]!= NULL; i++) if (i >= MAX_NB_OPERANDES) { fprintf(stderr," Nombre maximum d’opérandes pour une instruction dépassé, veulliez augmenter la valeur de "); fprintf(stderr," la constante MAX_NB_OPERANDES dans le fichier instrument.c\n"); exit(8); } instCourante−>origineOperandes[i] = tableRegistresTournants[identificateurRegistreTournant]; } /* Sinon, on le considère comme un registre fixe */ else { tableLectureRegistres[identificateurRessource]++; for(i=0; (instCourante−>origineOperandes)[i]!= NULL; i++) if (i >= MAX_NB_OPERANDES) { fprintf(stderr," Nombre maximum d’opérandes pour une instruction dépassé, veulliez augmenter la valeur de "); fprintf(stderr," la constante MAX_NB_OPERANDES dans le fichier instrument.c\n"); exit(8); } instCourante−>origineOperandes[i] = tableRegistres[identificateurRessource]; } }}

/* Traitement fait lorsqu’on rencontre une instruction qui accède à la mémoire ou à des registres (en sortie) *//* !!!!! Attention, cette fonction est différente selon qu’on utilise le programme sur Sparc ou x86 (registre %g0) */void instrumentationSortieRegistre( int identificateurRessource){ unsigned int identificateurRegistreTournant; /* Mise à jour du compteur de résultat : le registre identificateurRessource est considéré comme un résultat de l’instruction instCourante */ valeursMortes[instCourante−>numeroDynamique]++; /* Si le registre dans lequel on écrit est le numéro 41 (correspondant à %g0), on n’en tient pas compte car ce registre est un trou noir (quelque soit ce qui y est écrit, on lit toujours la valeur 0 dans ce registre) */ if(identificateurRessource != ID_REG_SALTO_G) { /* Si le registre accédé fait partie de la fenêtre de registres tournante */ if(identificateurRessource>=ID_REG_SALTO_O && identificateurRessource<=ID_REG_SALTO_I+7) { identificateurRegistreTournant = (72−identificateurRessource)+(niveauFenetreRegistre*OFFSET_FENETRE);

if(identificateurRegistreTournant>=NB_REGISTRES_TOURNANTS) { fprintf(stderr," Nombre maximum de registres tournants dépassé, veulliez augmenter la valeur de




"); fprintf(stderr," la constante NB_REGISTRES_TOURNANTS dans le fichier instrument.c\n"); exit(1); } if(tableLectureRegistresTournants[identificateurRegistreTournant] == 0) valeursMortes[(tableRegistresTournants[identificateurRegistreTournant])−>numeroDynamique]−−; tableRegistresTournants[identificateurRegistreTournant] = instCourante; tableLectureRegistresTournants[identificateurRegistreTournant] = 0; } /* Sinon, on le considère comme un registre fixe */ else { if(tableLectureRegistres[identificateurRessource] == 0) valeursMortes[(tableRegistres[identificateurRessource])−>numeroDynamique]−−; tableRegistres[identificateurRessource] = instCourante; tableLectureRegistres[identificateurRessource] = 0; } }}

void lectureMemoireOctet( int adresseMemoire){ int i; elementMemoire *a;

for(a=adresseInitiale; a== NULL || adresseMemoire>a−>adresse; a=a−>suivant) if(a== NULL) { /*fprintf(stderr,"Accès à l’adresse mémoire non initialisée %d par l’instruction %d (fichier %d)\n", adresseMemoire, instCourante−>numeroStatique, instCourante−>numeroFichier);*/ return; } if(adresseMemoire != a−>adresse) { /*fprintf(stderr,"Accès à l’adresse mémoire non initialisée %d par l’instruction %d (fichier %d)\n", adresseMemoire, instCourante−>numeroStatique, instCourante−>numeroFichier);*/ return; } for(i=0; (instCourante−>origineOperandes)[i]!= NULL; i++) if (i >= MAX_NB_OPERANDES) { fprintf(stderr," Nombre maximum d’opérandes pour une instruction dépassé, veulliez augmenter la valeur de "); fprintf(stderr," la constante MAX_NB_OPERANDES dans le fichier instrument.c\n"); exit(8); } instCourante−>origineOperandes[i] = a−>derniereEcriture; a−>nbLecture++;

18 jun 03 17:55 Page 11/13instrument.c}

void instrumentationEntreeMemoire( int adresseMemoire, int nbOctetsLus){ int offset;

for(offset=0; offset<nbOctetsLus; offset++) lectureMemoireOctet(adresseMemoire+offset);}

void ecritureMemoireOctet( int adresseMemoire){ elementMemoire *nouveau, *tmp = adresseInitiale; /* Mise à jour du compteur de résultat : la case mémoire adresseMemoire est considéré comme un résultat de l’instruction instCourante */ valeursMortes[instCourante−>numeroDynamique]++; /* Cas ou la liste chainée est vide : premier accès en écriture à la mémoire */ if(adresseInitiale == NULL) { adresseInitiale = malloc( sizeof(elementMemoire)); if(adresseInitiale == NULL) { fprintf(stderr," Taille mémoire maximale allouable dépassée !! "); fprintf(stderr," (fonction ecritureMemoireOctet dans le fichier instrument.c)\n"); exit(10); } adresseInitiale−>adresse = adresseMemoire; adresseInitiale−>nbLecture = 0; adresseInitiale−>derniereEcriture = instCourante; adresseInitiale−>suivant = NULL; } else { /* Cas ou l’insertion de données concerne le premier élément de la liste chainée */ if(adresseMemoire <= adresseInitiale−>adresse) { if(adresseInitiale−>adresse == adresseMemoire) { if(adresseInitiale−>nbLecture == 0)

valeursMortes[(adresseInitiale−>derniereEcriture)−>numeroDynamique]−−; adresseInitiale−>nbLecture = 0;adresseInitiale−>derniereEcriture = instCourante;

} else { nouveau = malloc( sizeof(elementMemoire));

if(nouveau == NULL){ fprintf(stderr," Taille mémoire maximale allouable dépassée !! ");

fprintf(stderr," (fonction ecritureMemoireOctet dans le fichier instrument.c)\n"); exit(10);

} nouveau−>adresse = adresseMemoire;




nouveau−>nbLecture = 0; nouveau−>derniereEcriture = instCourante; nouveau−>suivant = adresseInitiale; adresseInitiale = nouveau; } } /* Cas général d’insertion d’un élément dans la liste chainée */ else { /* On parcours la liste chainée jusqu’a trouver l’endroit ou il faut insérer la donnée */ while(tmp−>suivant != NULL && adresseMemoire >= tmp−>suivant−>adresse) tmp = tmp−>suivant; /* Si l’adresse mémoire à déjà était accédée par le passé, on modifie le pointeur sur l’instruction qui a écrit dernièrement dans cette zone mémoire */ if(tmp−>adresse == adresseMemoire) { if(tmp−>nbLecture == 0)

valeursMortes[(tmp−>derniereEcriture)−>numeroDynamique]−−;tmp−>nbLecture = 0;

tmp−>derniereEcriture = instCourante; } /* Sinon, on créé une nouvelle cellule représentant cette zone mémoire et on l’insère dans la liste chainée */ else { nouveau = malloc( sizeof(elementMemoire));



} nouveau−>adresse = adresseMemoire; nouveau−>nbLecture = 0; nouveau−>derniereEcriture = instCourante; nouveau−>suivant = tmp−>suivant; tmp−>suivant = nouveau; } } }}

void instrumentationSortieMemoire( int adresseMemoire, int nbOctetsEcrits){ int offset; for(offset=0; offset<nbOctetsEcrits; offset++) ecritureMemoireOctet(adresseMemoire+offset);}





#define NB_REGISTRES 115#define NB_REGISTRES_TOURNANTS 100000/* MAX_NB_OPERANDES doit etre égal au maximum d’opérandes que peuvent avoir les instruction +1 ! */#define MAX_NB_OPERANDES 1400

/* Défini les différentes valeur que peuvent prendre les variables utiliteInst[i], i allant de 0 à MAX_NB_INST_DYNAMIQUE.*/#define INUTILE 0#define UTILE 1#define NOP 2


struct donnees_instruction { unsigned char numeroFichier; unsigned int numeroStatique; unsigned int numeroDynamique; flag typeInstruction; flag valeurMorte; struct instru *origineOperandes[MAX_NB_OPERANDES];};

typedef struct instru { flag utiliteInst; struct donnees_instruction *donnees; struct instru *precedent;} instruction;

typedef struct mem { int adresse; unsigned int nbLecture; instruction *derniereEcriture; struct mem *suivant;} elementMemoire;

/* Définition des registres généraux */instruction *tableRegistres[NB_REGISTRES];unsigned int tableLectureRegistres[NB_REGISTRES];

/* Définition des registres tournants */instruction *tableRegistresTournants[NB_REGISTRES_TOURNANTS];unsigned int tableLectureRegistresTournants[NB_REGISTRES_TOURNANTS];unsigned int niveauFenetreRegistre = 0;

/* Définition des zones mémoires (point d’entrée dans la liste chainée) */elementMemoire *adresseInitiale = NULL;

/* Définition des instructions (point d’entrée dans la liste chainée et tableau de flag) */instruction *instInitiale;instruction *instCourante = NULL;

18 jun 03 14:19 Page 1/10instrument_optim.cinstruction *instCouranteDelay = NULL;

unsigned int numeroDynamiqueCourant;

int cptUtile = 0, cptInutile = 0, cptNop = 0;

unsigned int allocation=0;

void initVariablesGlobales( void ){ int i; struct donnees_instruction *donnees = malloc( sizeof( struct donnees_instruction)); allocation++;

numeroDynamiqueCourant=0; /* Création d’une instruction initiale fictive sur laquelle vont pointer celles qui utilisent des registres déjà initialisés lors du lancement du programme */ instInitiale = malloc( sizeof(instruction)); if(donnees == NULL || instInitiale == NULL) { fprintf(stderr," Taille mémoire maximale allouable dépassée !! "); fprintf(stderr," (fonction initVariablesGlobales dans le fichier instrument.c)\n"); exit(10); } donnees−>numeroFichier = 0; donnees−>numeroStatique = 0; donnees−>numeroDynamique = numeroDynamiqueCourant; /* 0 ici */ donnees−>typeInstruction = T_AUTRE; donnees−>valeurMorte = 0; for(i=0; i<MAX_NB_OPERANDES; i++) donnees−>origineOperandes[i] = NULL; instInitiale−>utiliteInst = INUTILE; instInitiale−>donnees = donnees; instInitiale−>precedent = NULL; instCourante = instInitiale; for(i=0; i<NB_REGISTRES; i++) { tableRegistres[i] = instInitiale; tableLectureRegistres[i] = 0; } for(i=0; i<NB_REGISTRES_TOURNANTS; i++) { tableRegistresTournants[i] = instInitiale; tableLectureRegistresTournants[i] = 0; }}

/* Fonction de debug permettant d’afficher la liste chainée des instructions, la table des registres et enfin le pourcentage d’instructions utile et inutiles */void afficherSdd( void ){ instruction *i; elementMemoire *a;

18 jun 03 14:19 Page 2/10instrument_optim.c


mercredi 18 juin 2003 22/37instrument_optim.c

int j,nbTotalInstructions,cptInutile2=0,cptMortes=0,cptMortes2=0; /* Définition du fichier contenant la trace (numéro) des instructions inutiles) */ FILE *traceInstructionsInutiles = fopen(TRACE_INSTRUCTIONS_INUTILES," w"); FILE *fichierEvolutionQtTravailInutile = fopen(TRACE_EVOLUTION_INUTILES," w"); FILE *fichierEvolutionQtValeursMortes = fopen(TRACE_VALEURS_MORTES," w");

/* Affichage des dépendances entre les instructions dynamiques (stockées dans la liste chainée d’instructions dynamiques) */ /* Version optimisée : ne sont disponible que les données sur les instructions inutiles */ fprintf(stdout," Liste des instructions dynamiques inutiles :\n"); for(i=instCourante; i!= NULL; i=i−>precedent) { if(i−>utiliteInst==INUTILE) { struct donnees_instruction *d = i−>donnees; fprintf(stdout," I.Dynamic %d\t−− I.Static %d\t−− File %d\n",d−>numeroDynamique,d−>numeroStatique,d−>numeroFichier); /*if(d−>origineOperandes[0]!=NULL) fprintf(stdout,"\t−− Dépend de %d",(d−>origineOperandes[0])−>donnees−>numeroDynamique); for(j=1; j<MAX_NB_OPERANDES; j++) if(d−>origineOperandes[j]!=NULL) fprintf(stdout,",%d",(d−>origineOperandes[j])−>donnees−>numeroDynamique); fprintf(stdout,"\n");*/

/* Ecriture dans le fichier traceInstructionsInutiles du numéro des instructions dynamiques inutiles */ fprintf(traceInstructionsInutiles," %u\n",d−>numeroDynamique); cptInutile++; if(d−>valeurMorte == 0) cptMortes++; } } fclose(traceInstructionsInutiles); for(i=instCourante,j=numeroDynamiqueCourant; i!= NULL; i=i−>precedent,j−−) { if(i−>utiliteInst == INUTILE) { cptInutile2++; if(i−>donnees−>valeurMorte == 0) cptMortes2++; } if(j%20 == 0) { fprintf(fichierEvolutionQtTravailInutile," %d\t%d\n",j,cptInutile−cptInutile2); fprintf(fichierEvolutionQtValeursMortes," %d\t%d\n",j,cptMortes−cptMortes2); } } fclose(fichierEvolutionQtTravailInutile); fclose(fichierEvolutionQtValeursMortes); nbTotalInstructions = cptUtile + cptInutile + cptNop; fprintf(stdout," \nCalcul prenant en compte les \"nop\" :\n"); fprintf(stdout," Nombre d’instructions inutiles : %d/%d soit %f %%\n", cptInutile,nbTotalInstructions,( float )(cptInutile*100)/( float )nbTotalInstructions); fprintf(stdout," Nombre d’instructions utiles : %d/%d soit %f %%\n",

18 jun 03 14:19 Page 3/10instrument_optim.c cptUtile,nbTotalInstructions,( float )(cptUtile*100)/( float )nbTotalInstructions); fprintf(stdout," Nombre de nop : %d/%d soit %f %%\n\n", cptNop,nbTotalInstructions,( float )(cptNop*100)/( float )nbTotalInstructions); nbTotalInstructions = cptUtile + cptInutile; fprintf(stdout," \nCalcul ne prenant pas en compte les \"nop\" :\n"); fprintf(stdout," Nombre d’instructions inutiles : %d/%d soit %f %%\n", cptInutile,nbTotalInstructions,( float )(cptInutile*100)/( float )nbTotalInstructions); fprintf(stdout," Nombre d’instructions utiles : %d/%d soit %f %%\n\n", cptUtile,nbTotalInstructions,( float )(cptUtile*100)/( float )nbTotalInstructions); fprintf(stdout," Nombre de noeuds dans le graphe : %d\n",allocation);}

void remonterArbre(instruction *inst){ int i; /* Si on n’a pas encore parcouru l’arbre de dépendance de l’instuction inst, on le parcours pour pour positionner les flag d’utilité utiliteInst[inst−>numeroDynamique] */ if(inst−>utiliteInst == INUTILE) { inst−>utiliteInst = UTILE; cptUtile++; for(i=0; inst−>donnees−>origineOperandes[i]!= NULL; i++) remonterArbre(inst−>donnees−>origineOperandes[i]); /* On libère la zone mémoire allouée au champ de donnée lorsqu’on est sur que l’instruction est utile (ce champ de donnée ne nous sert plus à rien dans ce cas la) */ free(inst−>donnees); allocation−−; inst−>donnees = NULL; }}

/* Création de la représentation des instructions dynamiques en mémoire *//* !!!!! Attention, cette fonction est différente selon qu’on utilise le programme sur Sparc ou x86 (DelaySlot) */void instrumentationInstructionDebut( int typeInstruction, int numeroInst, int numeroFichier){ int i; instruction *inst = malloc( sizeof(instruction)); struct donnees_instruction *d = malloc( sizeof( struct donnees_instruction)); allocation++; if(inst== NULL || d== NULL) { fprintf(stderr," Taille mémoire maximale allouable dépassée !! "); fprintf(stderr," (fonction instrumentationInstructionDebut dans le fichier instrument.c)\n"); exit(10); }




d−>numeroFichier = numeroFichier; d−>numeroStatique = numeroInst; d−>numeroDynamique = ++numeroDynamiqueCourant; d−>typeInstruction = typeInstruction; if(typeInstruction == T_NOP) cptNop++; for(i=0; i<MAX_NB_OPERANDES; i++) d−>origineOperandes[i] = NULL; inst−>utiliteInst = INUTILE; inst−>donnees = d; inst−>precedent = instCourante; instCourante = inst; /*fprintf(stderr,"Début inst statique %d, inst dynamique %d fichier %d\n",numeroInst,tmp−>numeroDynamique,tmp−>numeroFichier);*/}

/* !!!!! Attention, cette fonction n’est utile que pour les machines utilisant un DelaySolt (Sparc) */void instrumentationInstructionMilieu( void ){ /* Si l’instruction est un save, on incrémente le niveau de la fenetre de registres */ if(instCourante−>donnees−>typeInstruction == T_SAVE) niveauFenetreRegistre++; /* Si c’est un restore, on décrémente le niveau de la fenetre de registres */ else if(instCourante−>donnees−>typeInstruction == T_RESTORE) niveauFenetreRegistre−−;}

void instrumentationInstructionFin( void ){ /*fprintf(stderr,"Fin inst statique numéro %d, inst dynamique numéro %d\n",instCourante−>numeroStatique,instCourante−>numeroDynamique);*/

/* Si l’instruction courante est un branchement quelconque, un save ou un restore, on la marque comme utile et on marque comme utile toute les instructions dont elle dépend (appel récursif à remonterArbre) */ if(instCourante−>donnees−>typeInstruction == T_BRANCHEMENT || instCourante−>donnees−>typeInstruction == T_BRANCHEMENT_ANNUL_BIT || instCourante−>donnees−>typeInstruction == T_SAVE || instCourante−>donnees−>typeInstruction == T_RESTORE || instCourante−>donnees−>typeInstruction == T_APPEL_INTERNE || instCourante−>donnees−>typeInstruction == T_APPEL_EXTERNE || instCourante−>donnees−>typeInstruction == T_APPEL_EXTERNE_SPECIAL) remonterArbre(instCourante); /* Si l’instruction courante est un nop, on la marque comme tel et on libère l’espace mémoire qui avait était alloué pour sa représentation interne dans le programme */ else if(instCourante−>donnees−>typeInstruction == T_NOP) { instCourante−>utiliteInst = NOP; free(instCourante−>donnees); allocation−−; instCourante−>donnees = NULL; }}

18 jun 03 14:19 Page 5/10instrument_optim.c/* !!!!! Attention, cette fonction n’est utile que pour les machines utilisant un DelaySolt (Sparc) */void copierInstDelay( void ){ instCouranteDelay = instCourante;}

/* !!!!! Attention, cette fonction n’est utile que pour les machines utilisant un DelaySolt (Sparc) */void echangerInstDelay( void ){ instruction *tmp = instCourante; instCourante = instCouranteDelay; instCouranteDelay = tmp;}

/* Traitement fait lorsqu’on rencontre une instruction qui accède à la mémoire ou à des registres (en entrée) *//* !!!!! Attention, cette fonction est différente selon qu’on utilise le programme sur Sparc ou x86 (registres) */void instrumentationEntreeRegistre( int identificateurRessource){ int i; unsigned int identificateurRegistreTournant; /* identificateurRessource numéro ID_REG_SALTO_G = trou noir (%g0) */ if(identificateurRessource != ID_REG_SALTO_G) { /* Si le registre accédé fait partie de la fenêtre de registres tournante */ if(identificateurRessource>=ID_REG_SALTO_O && identificateurRessource<=ID_REG_SALTO_I+7) { identificateurRegistreTournant = (72−identificateurRessource)+(niveauFenetreRegistre*OFFSET_FENETRE);

if(identificateurRegistreTournant>=NB_REGISTRES_TOURNANTS) { fprintf(stderr," Nombre maximum de registres tournants dépassé, veulliez augmenter la valeur de "); fprintf(stderr," la constante NB_REGISTRES_TOURNANTS dans le fichier instrument.c\n"); exit(1); }

tableLectureRegistresTournants[identificateurRegistreTournant]++; for(i=0; (instCourante−>donnees−>origineOperandes)[i]!= NULL; i++) if (i >= MAX_NB_OPERANDES) { fprintf(stderr," Nombre maximum d’opérandes pour une instruction dépassé, veulliez augmenter la valeur de "); fprintf(stderr," la constante MAX_NB_OPERANDES dans le fichier instrument.c\n"); exit(8); } (instCourante−>donnees−>origineOperandes)[i] = tableRegistresTournants[identificateurRegistreTournant]; } /* Sinon, on le considère comme un registre fixe */ else




{ tableLectureRegistres[identificateurRessource]++; for(i=0; (instCourante−>donnees−>origineOperandes)[i]!= NULL; i++) if (i >= MAX_NB_OPERANDES) { fprintf(stderr," Nombre maximum d’opérandes pour une instruction dépassé, veulliez augmenter la valeur de "); fprintf(stderr," la constante MAX_NB_OPERANDES dans le fichier instrument.c\n"); exit(8); } (instCourante−>donnees−>origineOperandes)[i] = tableRegistres[identificateurRessource]; } }}

/* Traitement fait lorsqu’on rencontre une instruction qui accède à la mémoire ou à des registres (en sortie) *//* !!!!! Attention, cette fonction est différente selon qu’on utilise le programme sur Sparc ou x86 (registre %g0) */void instrumentationSortieRegistre( int identificateurRessource){ unsigned int identificateurRegistreTournant; /* Mise à jour du compteur de résultat : le registre identificateurRessource est considéré comme un résultat de l’instruction instCourante */ instCourante−>donnees−>valeurMorte++; /* Si le registre dans lequel on écrit est le numéro 41 (correspondant à %g0), on n’en tient pas compte car ce registre est un trou noir (quelque soit ce qui y est écrit, on lit toujours la valeur 0 dans ce registre) */ if(identificateurRessource != ID_REG_SALTO_G) { /* Si le registre accédé fait partie de la fenêtre de registres tournante */ if(identificateurRessource>=ID_REG_SALTO_O && identificateurRessource<=ID_REG_SALTO_I+7) { identificateurRegistreTournant = (72−identificateurRessource)+(niveauFenetreRegistre*OFFSET_FENETRE);

if(identificateurRegistreTournant>=NB_REGISTRES_TOURNANTS) { fprintf(stderr," Nombre maximum de registres tournants dépassé, veulliez augmenter la valeur de "); fprintf(stderr," la constante NB_REGISTRES_TOURNANTS dans le fichier instrument.c\n"); exit(1); } if(tableLectureRegistresTournants[identificateurRegistreTournant] == 0 && tableRegistresTournants[identificateurRegistreTournant]−>utiliteInst == INUTILE) tableRegistresTournants[identificateurRegistreTournant]−>donnees−>valeurMorte−−;

tableRegistresTournants[identificateurRegistreTournant] = instCourante; tableLectureRegistresTournants[identificateurRegistreTournant] = 0; }

18 jun 03 14:19 Page 7/10instrument_optim.c /* Sinon, on le considère comme un registre fixe */ else { if(tableLectureRegistres[identificateurRessource] == 0 && tableRegistres[identificateurRessource]−>utiliteInst == INUTILE) tableRegistres[identificateurRessource]−>donnees−>valeurMorte−−; tableRegistres[identificateurRessource] = instCourante; tableLectureRegistres[identificateurRessource] = 0; } }}

void lectureMemoireOctet( int adresseMemoire){ int i; elementMemoire *a; /*static elementMemoire *lecturePrecedente = NULL;*/ /* Si l’adresse accédée est consécutive à la précédente, alors on initialise a à lecturePrecedente−>suivant */ /* Sinon, on parcourt la liste chainée pour trouver l’élément mémoire corespondant */ /*if((lecturePrecedente−>adresse)+1 == adresseMemoire) a=lecturePrecedente−>suivant; else*/ for(a=adresseInitiale; a== NULL || adresseMemoire>a−>adresse; a=a−>suivant) if(a== NULL) { /*fprintf(stderr,"Accès à l’adresse mémoire non initialisée %d par l’instruction %d (fichier %d)\n", adresseMemoire, instCourante−>donnees−>numeroStatique, instCourante−>donnees−>numeroFichier);*/ return; } if(adresseMemoire != a−>adresse) { /*fprintf(stderr,"Accès à l’adresse mémoire non initialisée %d par l’instruction %d (fichier %d)\n", adresseMemoire, instCourante−>donnees−>numeroStatique, instCourante−>donnees−>numeroFichier);*/ return; } for(i=0; (instCourante−>donnees−>origineOperandes)[i]!= NULL; i++) if (i >= MAX_NB_OPERANDES) { fprintf(stderr," Nombre maximum d’opérandes pour une instruction dépassé, veulliez augmenter la valeur de "); fprintf(stderr," la constante MAX_NB_OPERANDES dans le fichier instrument.c\n"); exit(8); } (instCourante−>donnees−>origineOperandes)[i] = a−>derniereEcriture; a−>nbLecture++; /*lecturePrecedente = a;*/}




void instrumentationEntreeMemoire( int adresseMemoire, int nbOctetsLus){ int offset;

for(offset=0; offset<nbOctetsLus; offset++) lectureMemoireOctet(adresseMemoire+offset);}

void ecritureMemoireOctet( int adresseMemoire){ elementMemoire *nouveau, *tmp = adresseInitiale; /* Mise à jour du compteur de résultat : la case mémoire adresseMemoire est considéré comme un résultat de l’instruction instCourante */ instCourante−>donnees−>valeurMorte++; /* Cas ou la liste chainée est vide : premier accès en écriture à la mémoire */ if(adresseInitiale == NULL) { adresseInitiale = malloc( sizeof(elementMemoire)); if(adresseInitiale == NULL) { fprintf(stderr," Taille mémoire maximale allouable dépassée !! "); fprintf(stderr," (fonction ecritureMemoireOctet dans le fichier instrument.c)\n"); exit(10); } adresseInitiale−>adresse = adresseMemoire; adresseInitiale−>nbLecture = 0; adresseInitiale−>derniereEcriture = instCourante; adresseInitiale−>suivant = NULL; } else { /* Cas ou l’insertion de données concerne le premier élément de la liste chainée */ if(adresseMemoire <= adresseInitiale−>adresse) { if(adresseInitiale−>adresse == adresseMemoire) { if(adresseInitiale−>nbLecture == 0 && (adresseInitiale−>derniereEcriture)−>utiliteInst == INUTILE)

(adresseInitiale−>derniereEcriture)−>donnees−>valeurMorte−−; adresseInitiale−>nbLecture = 0;adresseInitiale−>derniereEcriture = instCourante;

} else { nouveau = malloc( sizeof(elementMemoire));



} nouveau−>adresse = adresseMemoire; nouveau−>nbLecture = 0; nouveau−>derniereEcriture = instCourante;

18 jun 03 14:19 Page 9/10instrument_optim.c nouveau−>suivant = adresseInitiale; adresseInitiale = nouveau; } } /* Cas général d’insertion d’un élément dans la liste chainée */ else { /* On parcours la liste chainée jusqu’a trouver l’endroit ou il faut insérer la donnée */ while(tmp−>suivant != NULL && adresseMemoire >= tmp−>suivant−>adresse) tmp = tmp−>suivant; /* Si l’adresse mémoire à déjà était accédée par le passé, on modifie le pointeur sur l’instruction qui a écrit dernièrement dans cette zone mémoire */ if(tmp−>adresse == adresseMemoire) { if(tmp−>nbLecture == 0 && (tmp−>derniereEcriture)−>utiliteInst == INUTILE)

(tmp−>derniereEcriture)−>donnees−>valeurMorte−−;tmp−>nbLecture = 0;

tmp−>derniereEcriture = instCourante; } /* Sinon, on créé une nouvelle cellule représentant cette zone mémoire et on l’insère dans la liste chainée */ else { nouveau = malloc( sizeof(elementMemoire));



} nouveau−>adresse = adresseMemoire; nouveau−>nbLecture = 0; nouveau−>derniereEcriture = instCourante; nouveau−>suivant = tmp−>suivant; tmp−>suivant = nouveau; } } }}

void instrumentationSortieMemoire( int adresseMemoire, int nbOctetsEcrits){ int offset; for(offset=0; offset<nbOctetsEcrits; offset++) ecritureMemoireOctet(adresseMemoire+offset);}




#include <stdio.h>#include <fcntl.h>#include <errno.h>#include <fstream>#include <iostream>#include <sys/types.h>#include <regex.h>#include <stdlib.h>#include <string.h>

#include " salto.h"#include " instrument.h"

#define FICHIER_SOURCE_ASSEMBLEUR ".s$"#define REPERTOIRE_FICHIER_INSTRUMENTES "instrumente2/"

#define SAVE " save %sp,−136,%sp"#define RESTORE " restore %g0,%g0,%g0"#define NOP " nop"

#define OFFSET_INSTRUMENTATION "16"#define OFFSET_INSTRUMENTATION_2 "28"#define OFFSET_INSTRUMENTATION_DELAY_SLOT "64"#define OFFSET_2_INSTRUMENTATION_DELAY_SLOT "44"#define OFFSET_INSTRUMENTATION_ANNUL_BIT "76"

#define EXP_ANNUL_BIT " ,a[ ]+"

#define ETIQUETTE_FONCTION_NOP "f_nop"

// Pointeur sur le fichier dans lequel sera écrit le code instrumentéFILE *fichierSInstrumente;// Pointeur sur le fichier contenant le code original (non instrumenté)FILE *fichierSOriginal;

// Permet d’identifier de manière unique le fichier en cours de traitementunsigned char numeroFichier;

// Fonction permettant de sauvagarder le contexte du programme (registres généraux et codes conditions) afin de ne pas// intervenir sur les valeurs des registres et codes conditions utilisés par le programmevoid sauvegardeContexte(BB *bb, int position, unsigned int *nbInstructionsAjoutees){ INST *instCCR; char *lectureCodesConditions = " \trd %ccr,%l0\n"; // "Empilement" du contexte du programme (création d’un contexte intermédiaire artificiel entre l’exécution du // programme et l’exécution des fonctions d’instrumentation du code. Ce contexte permet de travailler avec // les registres %o[0−5] afin de faire passer les paramètres aux fonctions d’instrumentations. bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(SAVE));

19 mai 03 17:16 Page 1/9instrumentation2.cc (*nbInstructionsAjoutees)++; instCCR = newAsm(NOP); instCCR−>addAttribute(UNPARSE_ATT, lectureCodesConditions, strlen(lectureCodesConditions)+1); bb−>insertAsm(*nbInstructionsAjoutees+position, instCCR); (*nbInstructionsAjoutees)++; // Sauvegarde en mémoire (dans la pile) des registres globaux for( int i=1; i<=4; i++) { char tmp[20]; // Sauvegarde du registre (%gi) (ex : "st %g1,[%sp+92]") sprintf(tmp," st %%g%d,[%%sp+%d]",i,88+(4*i)); bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(tmp)); (*nbInstructionsAjoutees)++; }}

// Fonction permettant de restaurer le contexte du programme (registres généraux et codes conditions) afin de ne pas// intervenir sur les valeurs des registres et codes conditions utilisés par le programmevoid restaurationContexte(BB *bb, int position, unsigned int *nbInstructionsAjoutees){ INST *instCCR; char *ecritureCodesConditions = " \twr %l0,%ccr\n"; // Récupération des registres globaux depuis la mémoire (depuis la pile) for( int i=1; i<=4; i++) { char tmp[20]; // Restauration du registre (%gi) (ex : "ld [%sp+92],%g1") sprintf(tmp," ld [%%sp+%d],%%g%d",88+(4*i),i); bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(tmp)); (*nbInstructionsAjoutees)++; } instCCR = newAsm(NOP); instCCR−>addAttribute(UNPARSE_ATT, ecritureCodesConditions, strlen(ecritureCodesConditions)+1); bb−>insertAsm(*nbInstructionsAjoutees+position, instCCR); (*nbInstructionsAjoutees)++;

// "Dépilement" du contexte du programme bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(RESTORE)); (*nbInstructionsAjoutees)++;}

int estPresent( char *motif, char *chaine){ int i; regex_t *preg = new regex_t(); size_t nmatch = 10; regmatch_t pmatch[nmatch];

19 mai 03 17:16 Page 2/9instrumentation2.cc


mercredi 18 juin 2003 27/37instrumentation2.cc

// Compilation de l’expression régulière if (regcomp(preg, motif, REG_EXTENDED)) { fprintf(STDERR," Erreur lors de la compilation de l’expression régulière \"%s\"\n",motif); exit(4); } // Exécution de l’expression régulière et renvoi du résultat en fonction if (regexec(preg, chaine, nmatch, pmatch, 0) == REG_NOMATCH) { regfree(preg); return 0; } for(i=0; i<nmatch && pmatch[i].rm_so!=−1; i++); regfree(preg); return i;}

int typeInstruction(INST *inst){ if(inst−>isCTI()) if(estPresent(EXP_ANNUL_BIT,inst−>unparse())) return T_BRANCHEMENT_ANNUL_BIT; else return T_BRANCHEMENT; return T_AUTRE;}

void appelDeFonctionInst(INST *inst, BB *bb, int position, unsigned int *nbInstructionsAjoutees, int numeroInst){ static unsigned char flagDelaySlot=0; char chaine[20],tmp[100], *lecturePC = " \trd %pc,%o1\n"; static INST *dernierBranchement;

if(!flagDelaySlot) sauvegardeContexte(bb, position, nbInstructionsAjoutees); // On empile un paramètre de type entier à passer à la fonction (équivaut à mov typeInst,%o0) sprintf(chaine," or %%g0,%d,%%o0",typeInstruction(inst)); bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(chaine)); (*nbInstructionsAjoutees)++; // Si la constante numeroInst à ranger dans %o1 peut être codée sur 13 bits (i.e. est entre −4096 et 4095) if(numeroInst <= 4095) { // On empile un paramètre de type entier à passer à la fonction (équivaut à mov numeroInst,%o1) sprintf(chaine," or %%g0,%d,%%o1",numeroInst); bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(chaine)); (*nbInstructionsAjoutees)++; } else { // On empile ce même paramètre mais en deux fois (les 22 premiers bits du re

19 mai 03 17:16 Page 3/9instrumentation2.ccgistre d’abbord) sprintf(chaine," sethi %%hi(%d),%%o1",numeroInst); bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(chaine)); (*nbInstructionsAjoutees)++; // Puis les 10 derniers bits ensuite sprintf(chaine," or %%o1,%%lo(%d),%%o1",numeroInst); bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(chaine)); (*nbInstructionsAjoutees)++; } // On empile un paramètre de type entier à passer à la fonction (équivaut à mov numeroFichier,%o2) sprintf(chaine," or %%g0,%d,%%o2",numeroFichier); bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(chaine)); (*nbInstructionsAjoutees)++;

// Si le branchement est un brachement avec annul_bit (ex : bl,a ...) alors on rempli la chaine de caractère

// chaineAnnulBit en conséquence (on y met les instructions pour traiter ce cas correctement) if(flagDelaySlot && typeInstruction(dernierBranchement)==T_BRANCHEMENT_ANNUL_BIT)

{ int i;

char *chaineAnnulBit = ( char *)malloc(100* sizeof( char )); regex_t *preg = new regex_t();

size_t nmatch = 1; regmatch_t pmatch[nmatch];

INST *inst_br_nop; if (regcomp(preg, EXP_ANNUL_BIT, REG_EXTENDED))

{ fprintf(STDERR," Erreur lors de la compilation de l’expression régulière \""EXP_ANNUL_BIT" \"\n"); exit(4); } if (regexec(preg, dernierBranchement−>unparse(), nmatch, pmatch, 0) == REG_NOMATCH) { fprintf(STDERR," Erreur lors de l’exécution de l’expression régulière \""EXP_ANNUL_BIT" \" :\n");

fprintf(STDERR," Impossible de trouver l’expression régulière dans l’instruction \"%s\"\n",dernierBranchement−>unparse()); exit(4); } regfree(preg);

for(i=0; i<pmatch[0].rm_eo; i++) tmp[i] = (dernierBranchement−>unparse())[i]; tmp[i] = ’ \0’;

strcpy(chaineAnnulBit," \trd %pc,%o7\n"); strcat(chaineAnnulBit," \tadd %o7,"OFFSET_INSTRUMENTATION_2",%o7\n"); strcat(chaineAnnulBit," \twr %l0,%ccr\n"); strcat(chaineAnnulBit,tmp);

strcat(chaineAnnulBit," "ETIQUETTE_FONCTION_NOP"\n");




inst_br_nop = newAsm(NOP); inst_br_nop−>addAttribute(UNPARSE_ATT, chaineAnnulBit, strlen(chaineAnnulBit)+1); bb−>insertAsm(*nbInstructionsAjoutees+position, inst_br_nop); (*nbInstructionsAjoutees)++;

strcpy(tmp," b ");

} else strcpy(tmp," call ");

bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(strcat(tmp,NOM_FCT_INST))); (*nbInstructionsAjoutees)++; // On ajoute un nop afin de combler le delay slot bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(NOP)); (*nbInstructionsAjoutees)++; if(flagDelaySlot && typeInstruction(dernierBranchement)==T_BRANCHEMENT_ANNUL_BIT) { INST *instLecturePC; instLecturePC = newAsm(NOP); instLecturePC−>addAttribute(UNPARSE_ATT, lecturePC, strlen(lecturePC)+1); bb−>insertAsm(*nbInstructionsAjoutees+position, instLecturePC); (*nbInstructionsAjoutees)++; bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(" jmpl %o1+"OFFSET_INSTRUMENTATION_ANNUL_BIT",%g0")); (*nbInstructionsAjoutees)++; bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(NOP)); (*nbInstructionsAjoutees)++; }

if(!flagDelaySlot) { if(!inst−>isCTI()) { INST *instLecturePC;

instLecturePC = newAsm(NOP); instLecturePC−>addAttribute(UNPARSE_ATT, lecturePC, strlen(lecturePC)+1); bb−>insertAsm(*nbInstructionsAjoutees+position, instLecturePC); (*nbInstructionsAjoutees)++; // A ce stade, %o0 contient le resultat de la fonction NOM_FCT_INST et %o1 contient le PC à l’instant t−1 // (instruction précédente à celle−ci) bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(" add %o1,%o0,%o0")); (*nbInstructionsAjoutees)++;

19 mai 03 17:16 Page 5/9instrumentation2.cc bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(" jmpl %o0+"OFFSET_INSTRUMENTATION",%g0")); (*nbInstructionsAjoutees)++; bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(NOP)); (*nbInstructionsAjoutees)++; restaurationContexte(bb, position, nbInstructionsAjoutees); } else { // On met le flagDelaySlot à 1 pour signaler que la prochaine instruction se trouvera dans // le DelaySlot de celle−ci flagDelaySlot=1; // On conserve dans une variable statique un pointeur sur l’instruction en cours de traitement dernierBranchement = inst−>copy(); } } else { // On traite l’instruction se trouvant dans le DelaySlot du précédent CTI (branchement) INST *instLecturePC, *instBranchement; // On remet le flagDelaySlot à zéro pour le prochain passage flagDelaySlot=0; instLecturePC = newAsm(NOP); instLecturePC−>addAttribute(UNPARSE_ATT, lecturePC, strlen(lecturePC)+1); bb−>insertAsm(*nbInstructionsAjoutees+position, instLecturePC); (*nbInstructionsAjoutees)++; // Dans le registre %o0, se trouve 0 si on n’a pas à annuler l’instruction et 52 si on doit l’annuler (inutile) // subcc %o0,0,%g0 <=> cmp %o0,0 bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(" subcc %o0,0,%g0")); (*nbInstructionsAjoutees)++; bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(" be,a f_nop")); (*nbInstructionsAjoutees)++;

// On utilise un jmpl dans le delay slot du brnz,a pour pouvoir brancher sur une adresse contenue dans un registre // (impossible si l’on utilise brnz,a directement car il faut lui fournir une étiquette) bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(" jmpl %o1+"OFFSET_INSTRUMENTATION_DELAY_SLOT",%g0")); (*nbInstructionsAjoutees)++; // A mon avis, ce nop n’est jamais exécuté puisque l’instruction se trouvant dans un delay slot d’une instruction // se trouvant elle même dans un delay slot n’est jamais exécutée... bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(NOP)); (*nbInstructionsAjoutees)++; restaurationContexte(bb, position, nbInstructionsAjoutees);




// Insertion d’une instruction équivalente à celle représentant le branchement dont on est en train de traiter // le DelaySlot bb−>insertAsm(*nbInstructionsAjoutees+position, dernierBranchement); (*nbInstructionsAjoutees)++; // On insère un nop dans le Delay Slot puisque l’instruction se trouvant normalement dans le delay slot de ce // branchement est jugée inutile bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(NOP)); (*nbInstructionsAjoutees)++; // On lit le PC instLecturePC = newAsm(NOP); instLecturePC−>addAttribute(UNPARSE_ATT, lecturePC, strlen(lecturePC)+1); bb−>insertAsm(*nbInstructionsAjoutees+position, instLecturePC); (*nbInstructionsAjoutees)++; // Et on branche après sur la suite du programme en sautant le branchement et son delay slot dans le cas utile bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(" jmpl %o1+"OFFSET_2_INSTRUMENTATION_DELAY_SLOT",%g0")); (*nbInstructionsAjoutees)++; bb−>insertAsm(*nbInstructionsAjoutees+position, newAsm(NOP)); (*nbInstructionsAjoutees)++; restaurationContexte(bb, position, nbInstructionsAjoutees); }}

void instrumenter(INST *inst, BB *bb, BB *bbSuivant, int position, unsigned int *nbInstructionsAjoutees, int numeroInst){ static unsigned char flagDelaySlot = 0; // Si on n’a pas à faire à une instruction se trouvant dans un DelaySlot if(!flagDelaySlot) // Si l’instruction n’est pas un branchement, alors, on instrumente cette instruction normalement if(!inst−>isCTI()) appelDeFonctionInst(inst, bb, position, nbInstructionsAjoutees, numeroInst); // Si l’instruction courante est un branchement, alors, on l’instrumente ainsi que son DelaySlot else { INST *instDelaySlot = bbSuivant−>getAsm(0); // On met le flag à 1 pour indiquer que l’instrumentation de l’instruction se trouvant dans le DelaySlot // du branchement que l’on est en train de traiter a déjà été instrumentée flagDelaySlot = 1; /*fprintf(STDERR,"Inst <%s>\t\t\tDelay <%s>\n",inst−>unparse(),instDelaySlot−>unparse());*/ // On traite l’instruction de branchement appelDeFonctionInst(inst, bb, position, nbInstructionsAjoutees, numeroInst

19 mai 03 17:16 Page 7/9instrumentation2.cc); // On traite l’instruction qui se trouve dans le DelaySlot appelDeFonctionInst(instDelaySlot, bb, position, nbInstructionsAjoutees, numeroInst+1); } else flagDelaySlot = 0;}

void Salto_hook(){ CFG *proc; BB *bb, *bbSuivant; INST *inst; int numeroInst = 0; unsigned int nbInstructionsAjoutees; // Parcours du programme permettant d’insérer le code d’instrumentation des instructions for ( int i=0; i < numberOfCFG(); i++) { proc = getCFG(i); for ( int j=0; j < proc−>numberOfBB(); j++) { bb = proc−>getBB(j); bbSuivant = proc−>getBB(j+1); int nbAsm = bb−>numberOfAsm(); nbInstructionsAjoutees = 0; for ( int k=0; k < nbAsm; k++) {

numeroInst++;inst = bb−>getAsm(k+nbInstructionsAjoutees);

instrumenter(inst, bb, bbSuivant, k, &nbInstructionsAjoutees, numeroInst); } } } // Parcours du programme permettant d’insérer le code pour l’initialisation des variables globales for ( int i=0; i < numberOfCFG(); i++) { proc = getCFG(i);

if(!strcmp(proc−>getName()," main")) { // Insertion d’un appel à la procédure initialisant les variables globales (proc−>getBB(0))−>insertAsm(0, newAsm(" call initVariablesGlobales")); (proc−>getBB(0))−>insertAsm(1, newAsm(NOP)); } } // Envoi du code instrumenté vers la sortie standard produceCode(fichierSInstrumente);}




void Salto_init_hook( int argc, char *argv[]){ int i,j,k; char nomFichierSortie[100];

// Récupération dans la ligne de commande entrée par l’utilisateur du nom du fichier original for(i=1; i<argc && !estPresent(" −i",argv[i]); i++); if(i == argc−1) { fprintf(STDERR," Erreur, votre ligne de commande ne comporte pas l’option \"−i\"\n"); exit(6); } // On ouvre le fichier .s original à traiter pour pouvoir s’en servir dans salto_hook() fichierSOriginal = fopen(argv[i+1]," r"); if(fichierSOriginal == NULL) { fprintf(STDERR," Problème lors de l’ouverture du fichier \"%s\" ",argv[i+1]); fprintf(STDERR," (fonction Salto_init_hook dans le fichier instrumentation2.cc)\n"); exit(11); }

nomFichierSortie[0]=’ \0’; strcat(nomFichierSortie,REPERTOIRE_FICHIER_INSTRUMENTES); strcat(nomFichierSortie,argv[i+1]); // On ouvre le fichier .s instrumenté en écriture à traiter pour pouvoir s’en servir dans salto_hook() fichierSInstrumente = fopen(nomFichierSortie," w"); if(fichierSInstrumente == NULL) { fprintf(STDERR," Problème lors de l’ouverture du fichier \"%s\" ",nomFichierSortie); fprintf(STDERR," (fonction Salto_init_hook dans le fichier instrumentation2.cc)\n"); exit(11); } // Recherche de l’expression "−−" dans la ligne de commande for(; i<argc && !estPresent(" −−",argv[i]); i++); // Si cette expression n’est pas présente, on ne numérote pas les fichiers if(i == argc−1) numeroFichier = 0; else numeroFichier = atoi(argv[i+1]);}

void Salto_end_hook(){ exit(0);}





/* Constantes utiles pour inhiber l’action des instructions dynamiques inutiles : Si l’on doit annuler l’instruction, on renvoit la constante 68 permettant de sauter l’instruction inutile ainsi que son instrumentation. Si l’on ne doit pas annuler l’instruction, on renvoit la constante 16 permettant de faire sauter le PC à la suite du programme (instruction à ne pas annuler et son instrumentation) */#define ANNUL 52#define NON_ANNUL 0


typedef struct instru { unsigned int numeroDynamique; struct instru *precedent;} instruction;

instruction *instInitiale;instruction *instCourante = NULL;

unsigned int tailleListeInstInutile;unsigned int *listeInstInutile;

void initVariablesGlobales( void ){ int i; char c; FILE *traceInstructionsInutiles;

/* Création d’une instruction initiale fictive sur laquelle vont pointer celles qui utilisent des registres déjà initialisés lors du lancement du programme */ instInitiale = malloc( sizeof(instruction)); if(instInitiale == NULL) { fprintf(stderr," Taille mémoire maximale allouable dépassée !! "); fprintf(stderr," (fonction initVariablesGlobales dans le fichier instrument2.c)\n"); exit(10); } instInitiale−>numeroDynamique = 0; instInitiale−>precedent = NULL; instCourante = instInitiale;

tailleListeInstInutile = 0; traceInstructionsInutiles = fopen(TRACE_INSTRUCTIONS_INUTILES," r"); if(traceInstructionsInutiles == NULL) { fprintf(stderr," Problème lors de l’ouverture du fichier \""TRACE_INSTRUCTIONS_INUTILES" \" "

19 mai 03 15:50 Page 1/3instrument2.c); fprintf(stderr," (fonction initVariablesGlobales dans le fichier instrument2.c)\n"); exit(11); }

/* On compte le nombre de lignes dans le fichier */ do if(fgetc(traceInstructionsInutiles)==’ \n’) tailleListeInstInutile++; while(!feof(traceInstructionsInutiles)); fclose(traceInstructionsInutiles); listeInstInutile = malloc(tailleListeInstInutile* sizeof( unsigned int )); traceInstructionsInutiles = fopen(TRACE_INSTRUCTIONS_INUTILES," r"); if(traceInstructionsInutiles == NULL) { fprintf(stderr," Problème lors de l’ouverture du fichier \""TRACE_INSTRUCTIONS_INUTILES" \" "); fprintf(stderr," (fonction initVariablesGlobales dans le fichier instrument2.c)\n"); exit(11); }

for(i=tailleListeInstInutile−1; i>=0; i−−) fscanf(traceInstructionsInutiles, "%u", &listeInstInutile[i]);}

/* Création de la représentation des instructions dynamiques en mémoire */int instrumentationInstruction( int typeInstruction, int numeroStatique, int numeroFichier){ int i; static int indiceListeInstructions = 0; instruction *tmp = malloc( sizeof(instruction));

if(tmp == NULL) { fprintf(stderr," Taille mémoire maximale allouable dépassée !! "); fprintf(stderr," (fonction instrumentationInstruction dans le fichier instrument2.c)\n"); exit(10); }

if(instCourante−>numeroDynamique >= MAX_NB_INST_DYNAMIQUE) { fprintf(stderr," Nombre maximum d’instruction dépassé, veulliez augmenter la valeur de la constante "); fprintf(stderr," MAX_NB_INST_DYNAMIQUE dans le fichier instrument.h\n"); exit(1); }

tmp−>numeroDynamique = instCourante−>numeroDynamique+1; tmp−>precedent = instCourante; instCourante = tmp; fprintf(stderr," I.Dynamic %d\t−− I.Static %d\t−− File %d",instCourante−>numeroDynamique,numeroStatique,numeroFichier);

if(typeInstruction == T_BRANCHEMENT) {

19 mai 03 15:50 Page 2/3instrument2.c


mercredi 18 juin 2003 32/37instrument2.c

fprintf(stderr," \t−− Branch\n"); return NON_ANNUL; } if(typeInstruction == T_BRANCHEMENT_ANNUL_BIT) { fprintf(stderr," \t−− Branch annul bit\n"); return NON_ANNUL; }

/* Si le numéro de l’instruction dynamique en cours de traitement est le même que le dernier numéro testé comme étant une instruction inutile, alors on retourne la valeur ANNUL */ if(instCourante−>numeroDynamique == listeInstInutile[indiceListeInstructions] && indiceListeInstructions < tailleListeInstInutile) { indiceListeInstructions++; fprintf(stderr," \t−− Non exécutée\n"); return ANNUL; } fprintf(stderr," \n"); return NON_ANNUL;}

19 mai 03 15:50 Page 3/3instrument2.c


mercredi 18 juin 2003 33/37instrument2.c

#include <stdio.h>#include <stdlib.h>#include <string.h>#include <signal.h>#include <ctype.h>#include <errno.h>#include <sys/stat.h>#include <sys/types.h>#include "instrument.h"

void *my_memset(void *p, int i, size_t taille){ echangerInstDelay(); instrumentationSortieMemoire((int)p, taille); instrumentationInstructionFin(); echangerInstDelay(); return memset(p, i, taille);}

void *my_memcpy(void *p1, const void *p2, size_t taille){ echangerInstDelay(); instrumentationEntreeMemoire((int)p2, taille); instrumentationSortieMemoire((int)p1, taille); instrumentationInstructionFin(); echangerInstDelay(); return memcpy(p1, p2, taille);}

int my_memcmp(const void *p1, const void *p2, size_t taille){ echangerInstDelay(); instrumentationEntreeMemoire((int)p1, taille); instrumentationEntreeMemoire((int)p2, taille); instrumentationInstructionFin(); echangerInstDelay(); return memcmp(p1, p2, taille);}

int my_strcmp(const char *c1, const char *c2){ echangerInstDelay(); instrumentationEntreeMemoire((int)c1, strlen(c1)+1); instrumentationEntreeMemoire((int)c2, strlen(c2)+1); instrumentationInstructionFin(); echangerInstDelay(); return strcmp(c1, c2);}

int my_strncmp(const char *c1, const char *c2, size_t taille){ echangerInstDelay(); instrumentationEntreeMemoire((int)c1, taille); instrumentationEntreeMemoire((int)c2, taille); instrumentationInstructionFin();

21 avr 03 16:53 Page 1/7redefinition.c echangerInstDelay(); return strncmp(c1, c2, taille);}

size_t my_strlen(const char *c){ echangerInstDelay(); instrumentationEntreeMemoire((int)c, strlen(c)+1); instrumentationInstructionFin(); echangerInstDelay(); return strlen(c);}

char *my_strncpy(char *c1, const char *c2, size_t taille){ echangerInstDelay(); instrumentationEntreeMemoire((int)c2, taille); instrumentationSortieMemoire((int)c1, taille); instrumentationInstructionFin(); echangerInstDelay(); return strncpy(c1, c2, taille);}

char *my_strcpy(char *c1, const char *c2){ echangerInstDelay(); instrumentationEntreeMemoire((int)c2, strlen(c2)+1); instrumentationSortieMemoire((int)c1, strlen(c2)+1); instrumentationInstructionFin(); echangerInstDelay(); return strcpy(c1, c2);}

char *my_strcat(char *c1, const char *c2){ echangerInstDelay(); instrumentationEntreeMemoire((int)c1, strlen(c1)+1); instrumentationEntreeMemoire((int)c2, strlen(c2)+1); instrumentationSortieMemoire(((int)c1)+strlen(c1), strlen(c2)+1); instrumentationInstructionFin(); echangerInstDelay(); return strcat(c1, c2);}

char *my_strrchr(const char *c, int i){ echangerInstDelay(); instrumentationEntreeMemoire((int)c, strlen(c)+1); instrumentationInstructionFin(); echangerInstDelay(); return strrchr(c, i);}

size_t my_strcspn(const char *c1, const char *c2){

21 avr 03 16:53 Page 2/7redefinition.c


mercredi 18 juin 2003 34/37redefinition.c

echangerInstDelay(); instrumentationEntreeMemoire((int )c1, strlen(c1)+1); instrumentationEntreeMemoire((int )c2, strlen(c2)+1); instrumentationInstructionFin(); echangerInstDelay(); return strcspn(c1, c2);}

size_t my_strspn(const char *c1, const char *c2){ echangerInstDelay(); instrumentationEntreeMemoire((int )c1, strlen(c1)+1); instrumentationEntreeMemoire((int )c2, strlen(c2)+1); instrumentationInstructionFin(); echangerInstDelay(); return strspn(c1, c2);}

void *my_malloc(size_t taille){ echangerInstDelay(); instrumentationInstructionFin(); echangerInstDelay(); return malloc(taille);}

void *my_calloc(size_t taille1, size_t taille2){ echangerInstDelay(); instrumentationInstructionFin(); echangerInstDelay(); return calloc(taille1, taille2);}

void my_free(void *p){ echangerInstDelay(); instrumentationInstructionFin(); echangerInstDelay(); free(p);}

char *my_getenv(const char *c){ char *c2 = getenv(c); echangerInstDelay(); instrumentationEntreeMemoire((int )c, strlen(c)+1); if(c2!=NULL) instrumentationSortieMemoire(((int )c2), strlen(c2)+1); instrumentationInstructionFin(); echangerInstDelay(); return c2;}

int my_atoi(const char *c){

21 avr 03 16:53 Page 3/7redefinition.c echangerInstDelay(); instrumentationEntreeMemoire((int )c, strlen(c)+1); instrumentationInstructionFin(); echangerInstDelay(); return atoi(c);}

int my_fileno(FILE *f){ echangerInstDelay(); instrumentationInstructionFin(); echangerInstDelay(); return fileno(f);}

/* Cette fonction ne comportant aucun pointeur, elle ne fait aucun accès à la mémoire utilisable par l’appelant */int my_isatty(int i){ echangerInstDelay(); instrumentationInstructionFin(); echangerInstDelay(); return isatty(i);}

int my_fstat(int i, struct stat *s){ echangerInstDelay(); instrumentationEntreeMemoire((int )s, sizeof(s)); instrumentationSortieMemoire((int )s, sizeof(s)); instrumentationInstructionFin(); echangerInstDelay(); return fstat(i, s);}

/* Cette fonction ne comportant aucun pointeur, elle ne fait aucun accès à la mémoire utilisable par l’appelant */int my_close(int i){ echangerInstDelay(); instrumentationInstructionFin(); echangerInstDelay(); return close(i);}

void my_perror(const char *c){ echangerInstDelay(); instrumentationEntreeMemoire((int )c, strlen(c)+1); instrumentationInstructionFin(); echangerInstDelay(); perror(c);}

int my_unlink(const char *c){




echangerInstDelay(); instrumentationEntreeMemoire((int )c, strlen(c)+1); instrumentationInstructionFin(); echangerInstDelay(); return unlink(c);}

int my_lstat(const char *c, struct stat *s){ echangerInstDelay(); instrumentationEntreeMemoire((int )c, strlen(c)+1); instrumentationEntreeMemoire((int )s, sizeof(s)); instrumentationSortieMemoire((int )s, sizeof(s)); instrumentationInstructionFin(); echangerInstDelay(); return lstat(c, s);}

int my_stat(const char *c, struct stat *s){ echangerInstDelay(); instrumentationEntreeMemoire((int )c, strlen(c)+1); instrumentationEntreeMemoire((int )s, sizeof(s)); instrumentationSortieMemoire((int )s, sizeof(s)); instrumentationInstructionFin(); echangerInstDelay(); return stat(c, s);}

/* Cette fonction ne comportant aucun pointeur, elle ne fait aucun accès à la mémoire utilisable par l’appelant */off_t my_lseek(int i, off_t off, int j){ echangerInstDelay(); instrumentationInstructionFin(); echangerInstDelay(); return lseek(i, off, j);}

ssize_t my_read(int i, void *p, size_t taille){ int taille_reelle = read(i, p, taille);

echangerInstDelay(); instrumentationSortieMemoire((int )p, taille_reelle); instrumentationInstructionFin(); echangerInstDelay(); return taille_reelle;}

ssize_t my_write(int i, const void *p, size_t taille){ int taille_reelle = write(i, p, taille); echangerInstDelay(); instrumentationEntreeMemoire((int )p, taille_reelle); instrumentationInstructionFin();

21 avr 03 16:53 Page 5/7redefinition.c echangerInstDelay(); return taille_reelle;}

char *my_ctime(const time_t *time){ char *c = ctime(time); echangerInstDelay(); instrumentationEntreeMemoire((int )time, sizeof(time)); instrumentationSortieMemoire((int )c, 26); instrumentationInstructionFin(); echangerInstDelay(); return c;}

int my_fflush(FILE *f){ echangerInstDelay(); instrumentationInstructionFin(); echangerInstDelay(); return fflush(f);}

char *my_fgets(char *c, int i, FILE *f){ char *c2 = fgets(c, i, f); echangerInstDelay(); instrumentationSortieMemoire((int )c2, strlen(c2)+1); instrumentationInstructionFin(); echangerInstDelay(); return c2;}

int my_chmod(const char *c, mode_t mode){ echangerInstDelay(); instrumentationEntreeMemoire((int )c, strlen(c)+1); instrumentationInstructionFin(); echangerInstDelay(); return chmod(c, mode);}

int my_utime(const char *c, const void *buf){ echangerInstDelay(); instrumentationEntreeMemoire((int )c, strlen(c)+1); /*instrumentationEntreeMemoire((int)buf, sizeof(struct utimbuf));*/ instrumentationInstructionFin(); echangerInstDelay(); return utime(c, buf);}

int my_chown(const char *c, uid_t uid, gid_t gid){




echangerInstDelay(); instrumentationEntreeMemoire((int )c, strlen(c)+1); instrumentationInstructionFin(); echangerInstDelay(); return chown(c, uid, gid);}

/* Cette fonction ne comportant aucun pointeur, elle ne fait aucun accès à la mémoire utilisable par l’appelant */void my_exit(int i){ echangerInstDelay(); instrumentationInstructionFin(); echangerInstDelay(); exit(i);}




Education

Evaluation de la quantité de travail (in)utile dans l’exécution des programmes