- Institute de la Francophonie pour l’Informatique Novembre 2006. - Je voudrais remercier professeur Danny Dubé au Département d’Infor- matique et de Génie Logiciel à l’Université Laval pour tout ce qu’il a fait pour moi pendant mon stage, même je n’étais pas très autonome. - Les méthodes courantes, en général, elles ajoutent quelques mor- ceaux de code sources et exécutent le programme pour calculer le profil d’un programme. - Par contre, notre méthode, elle n’exécute pas le programme mais essaye de construire un système qui modèle l’exécution du programme puis calcule le profil basé sur le résultat obtenu quand on résout le système. - Dans la deuxième phase, utilisant le résultat de la première phase, on construit et résout un système d’équation pour obtenir un résultat plus détaillé. - 2.2.5 Gestion de la mémoire de façon automatiquement. - 5.2 Système d’équation. - 5.4 Résoudre le système d’équations. - Elle se distingue ainsi de l’analyse dynamique ou test, qui revient à essayer le programme sur différentes entrées jugées représentatives, afin de vérifier s’il produit les résultats attendus sur ces entrées.. - L’analyse dynamique de programmes est une famille de techniques d’ana- lyse d’exécution qui mesure le comportement d’un programme, en particulier la fréquence et la durée des appels de fonction, quand il fonctionne. - L’instrumentation de code, au temps de la compilation, il insère le code dans le programme à analyser. - Cette méthode de profiling consiste à essayer d’estimer le résultat d’un programme et de mesurer ses comportements sans exécuter le programme.. - Le troisième type de langage de programmation est le style de programma- tion dans lequel on ne programme qu’en écrivant des fonctions qui appellent d’autres fonctions. - C’est pour cette raison qu’on peut éviter les effets de bord en utilisant ce. - Par exemple une fonction change la valeur d’une variable globale, donc quand on exécute cette fonction on peut obtenir deux résultats différents.. - Une autre propriété liée à la programmation fonctionnelle, c’est la trans- parence référentielle. - Une expression est transparente de manière référentielle si elle peut être remplacée dans le code source de programme sans changer le résultat final du programme. - Par exemple, en programmation en C, il y a une pénalité de performance pour l’inclusion d’une fonction dans une boucle, même si l’appel de fonction pourrait être dé- placé à l’extérieur de la boucle sans changer les résultats du programme. - Les langages fonctionnels traitent les fonctions en tant qu’objets de pre- mière classe. - Dans le calcul de lambda, chaque expression représente une fonction avec un argument simple. - Une fonction est anonyme définie par une expression de lambda qui exprime l’application de la fonction sur son argument.. - x + 2 serait exprimé en calcul de lambda comme λx.x + 2 (ou d’une manière équivalente comme λy.y +2, le nom de l’argument formel est peu important) et le nombre f (3) serait écrit en tant que (λx.x + 2)3. - Une fonction de deux variables est exprimée en calcul de lambda en fonc- tion d’un argument qui renvoie une fonction d’un argument. - – l’abstraction : si u est un programme dépendant (ou non) de la variable x, alors on peut former un nouveau programme λx.u, qui représente la fonction qui prend la variable x et retourne u.. - Les deux réductions dont nous aurons besoin sont l’alpha - réduction qui est l’équi- valent du renommage de variable et la bêta - réduction, qui est l’équivalent de l’appel de fonction.. - On peut constater que les deux expressions : λx.x + 1 et λy.y + 1 dénotent la même fonction : que l’argument s’appelle x ou y, c’est toujours la fonction qui ajoute 1 à son argument. - Les langages courants sont trop compliqués pour faire le profiling parce qu’ils contiennent trop de structures et de types de données (pas nécessaire pour le but de tester le profiling). - Pour les langages impératifs comme C, notre entrée - le programme à ana- lyser est considéré comme une suite de caractère, donc tout d’abord il faut faire l’analyse de jetons pour découper et regrouper les caractères consti- tuant un programme en jetons. - La première phase vise à cal- culer le résultat abstrait en utilisant un système de contrainte. - Basant sur le résultat de la première phase, on construit et résout, dans la phase suivante, un système d’équation pour obtenir un résultat plus exact.. - Après la première phase, on obtient les valeurs possibles de E sont #f ou une paire (#f, #f).. - Après la deuxième phase on obtient les valeurs possibles de E sont : #f avec la probabilité de 0% et une paire (#f, #f) avec la probabilité de 100%.. - Normalement, le résultat de notre méthode est une liste de valeurs, chaque. - Dans ce chapitre, on va présenter une analyse abstraite sur le code source d’un programme. - Le résultat de cette phase est nécessaire pour faire le pro- filing dans la deuxième phase.Cette analyse a pour but d’estimer toutes les valeurs possibles que chaque expression dans le programme puisse créer sans compter la probabilité de chaque valeur.. - Pour faciliter l’analyse abstraite, toutes les expressions dans le programme sont étiquetées (avec des étiquettes différentes). - On définit les valeurs abstraites suivantes. - – P i : une paire à la position d’un (sous)-expression ayant l’étiquette i. - λ i : une fonction à la position d’un (sous)-expression ayant l’étiquette i. - est P 1 et la valeur de l’appel de fonction E = (call 1 (#f 2 ) (#f 3. - L’idée générale de cet algorithme est qu’on essaie de calculer la valeur re- tournée d’un expression en combinant les valeurs des sous-expressions (après vérifier les relations entres les sous-expressions).. - Par exemple, pour l’expression. - Mais on constate que cette estimation est un peu faible parce qu’on ne compte pas les valeurs de e 2 . - Il nous reste un autre problème à résoudre : comment peut-t-on éliminer les codes mortes (c’est à dire les morceaux de code qui ne sont jamais exé- cutés) pour qu’on ne doive pas calculer ses valeurs, et ses valeurs n’affectent pas d’autres estimations. - On dénote δ i la valeur booléenne vraie/faux, qui indique si l’expression ayant l’étiquette i est exécutée.. - α l ⊆ ERROR – Si e l = (µ l x. - si α l 1 \π 6= alors α l ⊆ {#f}. - Contrainte additionnelle sur le programme : E = e 1 et δ 1 = vrai. - Supposons qu’on doit analyser le programme suivant. - À partir de δ 1 et les valeurs natives des expressions, on fait l’itération et la substitution jusqu’au moment où il n’y pas de changement de δ. - Le résultat final est donc comme suivant. - L’algorithme mentionné dans le chapitre précédent ne donne qu’une ana- lyse ‘abstraite’. - Dans cette méthode, on estime non seulement le résultat de chaque expression mais aussi la fréquence que chacune (sous-)expression est exécutée dans l’exécution du programme.. - On dénote Π l (v) la probabilité de e l lorsqu’évalué vaut v, v est un élément de l’ensemble de valeurs possibles - les valeurs qu’on a obtenu après la phase 1.. - l’en- semble de tous les valeurs possibles. - L’idée principale ici, c’est qu’on essaye de modeler le programme comme un système de contrainte (sous une forme d’un système d’équation entre les Π l (v),χ l et K l (v. - On espère que cette solution ‘se reflète’ les valeurs de Π et χ.. - "Si on connaît les valeurs des Π l (v),χ l et K l (v) au pas n , comment peut-on les calculer au pas n + 1 ?". - si v ∈ Val – Pour e l = x l. - Π l 0 (v ) si v ∈ V al – Pour e l = (cons l e l 0 e l 00. - quelques parties de ’vieux’ χ l et K l (l 0 ) aux nouveaux. - δ est la fonction de Dirac, tous les valeurs valent 0 sauf la valeur à l 00 vaut 1. - – Pour le programme principale.. - Nous voudrions que ce système bien simule notre programme, dons c’est important que les Π l , Π x , χ l respectent toujours quelques critères. - On va prouver que, au pas n, si on construit les valeurs de Π l , Π x , χ l basées sur les valeurs de Π l , Π x , χ l au pas n − 1, on a toujours. - En fait, ces critères sont satisfaits naturellement parce qu’en écrivant les équations, on a tenu compte de ces critères. - On peut constater facilement qu’on a ‘traversé’ toutes les valeurs possibles de e l , e l 0 et e l 00 donc P. - On dénote Π (n) l (v ) est la valeur de Π l (v) au pas n – Si e l = #f l. - A partir de l’équation. - – Pour x dans (λ l x.e l 0 ) Π x (V al. - 0 pour tout i ∈ Label – Pour x dans (µ l x.e l 0. - Alors il existe un point fixe unique x ∗ de f dans E (c’est-à-dire tel que f(x. - En générale, d’après [6], ce critère n’est pas adé- quat pour les systèmes d’équation non-linéaire.. - Malheureusement, on ne peut pas utiliser ce critère avec notre système, on peut citer des f i où le critère n’est pas satisfait, par exemple avec e l = (car l e l 0. - Supposons que l’on doit résoudre le système F (X. - 0, en omettant O(∂x 2 ) on peut appliquer l’itération suivante, à chaque itération, on résout le système d’équation non-linéaire pour trouver ∂ k. - Il nous reste un autre problème à vérifier, c’est la convergence de cette méthode. - Convergence globale Il s’agit de la convergence de notre système avec un certain point d’initialisation. - Il est difficile de l’appliquer à notre système.. - de la racine. - On utilise une autre technique appliquée dans le réseau de neutron - le taux d’apprentissage : le résultat final au pas n est la combinaison entre le résultat au pas n − 1 et le résultat ‘brut’ au pas n. - Supposons qu’on voudrait faire le profiling de ce programme : (voir l’exemple dans le chapitre précédent). - Après la phase d’analyse abstraite, on a le résultat suivant : α 1 = #f , δ 1 = #t. - Le système d’équation qu’on obtient de ce programme est : Π 1 (#f. - Au pas 0, on met toutes les valeurs de Π l (v) égales à 1. - c’est à dire toutes les valeurs possibles qu’on obtienne après la phase d’ana- lyse abstraire ont la même probabilité.. - De même, on met toutes les valeurs de χ l égales à 1. - c’est à dire toutes les expressions dans le programme ont la même probabilité à exécuter.. - Après 100 pas, on a le résultat suivant. - chi3:0.08279578902023832 chi4: 0.0823628782155107 chi8:0.08219011651595416 chi9: 0.08232266379931359 chi10:0.08272488772696303 chi11: 0.08329002758582212 chi12:0.08386778600929741 chi13: 0.0833738660462502 chi14:0.08430346984862165 chi15: 0.08447932318531196 Le résultat est bon en comparaison avec lequel en réalité.. - Dans cette mémoire, nous proposons une nouvelle méthode de profiling qui aide à donner les résultats d’évaluation d’un code source d’un programme sans exécuter le programme. - La première phase, on construit et résolve un système de contrainte des valeurs abstraites pour obtenir une estimation abstraite sur le résultat d’exécution de toutes les expressions dans le programme à analyser. - La deuxième phase, on construit un système d’équation qui simule la ’suite’ d’exécution du programme, puis on applique une technique similaire à celle utilisée dans le réseaux neutron pour trouver un point ‘stable’ de ce système. - D’autre part, dans quelques cas, le résultat n’est pas bon. - Il y a une grande différence entre le résultat de profiling et celui en réalité. - Le résultat de la première phase est sûr mais assez faible, tandis que le résultat de phase deux est incertain parce que le système d’équation qu’on a construit ne converge pas toujours quand on applique l’itération avec le taux d’apprentissage.. - Une autre limitation, c’est que ce système, il ne modelé pas bien la situa- tion où le programme ne retourne pas. - Bien qu’on ait inclus Π. - dans le système, la valeur de Π. - La raison est qu’on ne propose pas les équations qui peuvent ajouter les nouvelles valeurs à Π(⊥).