Compilation de langage à objets Analyse de types et graphe ...privat/publications/Privat...Chapitre 2 Déﬁnitions et état de l’art 2.1 Graphes d’appels Déﬁnition 1 Un sous-programmeest

ACADÉMIE DE MONTPELLIER

UNIVERSITÉ MONTPELLIER II

- SCIENCES ET TECHNIQUES DU LANGUEDOC-

DIPLÔME D’ ÉTUDES APPROFONDIES

- INFORMATIQUE -

RAPPORT DE STAGE DE RECHERCHE

Compilation de langage à objets

Analyse de types et graphed’appels en compilation séparée

JEAN PRIVAT

Date de soutenance : 2 JUILLET 2002

Responsable de stage : ROLAND DUCOURNAU

Remerciements

Je tiens à remercier toutes les personnes qui ont contribué au bon déroulement de ce travail de re-cherche :

– Roland Ducournau, mon responsable de stage, pour sa grande disponibilité et pour tout le tempsconsacré à discuter et réfléchir sur tous les éléments nécessaires à la réalisation de ce projet ;

– Gilles Ardourel et Oliver Gout pour avoir partagé avec moi leur espace de travail mais aussi un peude leur temps ;

– mes amis qui m’ont toujours soutenu : Kamille, Nailah, Sylvain pour ne citer qu’eux ;– toutes les personnes qui ont tenté de corriger l’orthographe de ce rapport, en particulier Sylvain et

mon responsable de stage ;– Sidoine, Alexandre et Stéphane pour avoir inventé ou développé le GOTO++ ce merveilleux langage ;– mes parents qui m’ont toujours fait confiance ;– et tout particulièrement Chiêm qui a su me supporter mais aussi su me soutenir dans les moments

difficiles.

iii

Table des matières

1 Introduction 1

2 Définitions et état de l’art 32.1 Graphes d’appels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Graphes d’appels en objet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.2.1 RA et UN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2.2 CHA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2.3 RTA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.3 Analyse de types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.4 Analyses du flux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.4.1 Flux de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.4.2 Flux de types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.4.3 La technique de base : 0-CFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.4.4 Les limites de 0-CFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4.5 Techniques polyvariantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.4.6 Techniques adaptatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.4.7 Technique par fonction de Hash . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.4.8 Algorithme Itératif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.4.9 CPA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.4.10 SCS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.4.11 Techniques entre RTA et 0-CFA . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.5 Cas des attributs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3 Analyse séparée dans les langages typés 153.1 Spécification du problème traité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.2 Langage objet cible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.2.1 Classes et philosophie réaliste . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.2.2 Typage statique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.2.3 Sélection simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.2.4 Existence desuper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.2.5 Structures de contrôle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2.6 Généricité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2.7 Types ancrés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4 Analyse locale 214.1 Templates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4.1.1 Filtrage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224.1.2 Template de classe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224.1.3 Template de méthode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224.1.4 Représentation des templates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.2 Génération des templates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244.2.1 Solution basique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

v

vi TABLE DES MATIÈRES

4.2.2 Gestion de la covariance dans l’analyse basique . . . . . . . . . . . . . . . . . . . 274.3 Sûreté et précision des analyses locales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284.4 Simplifications des templates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.4.1 Simplification précise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.4.2 Simplification minimale précise . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.5 Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.5.1 Quelques solutions simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.5.2 Interface minimale précise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.6 Analyse des variables du code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.6.1 Détection des initialisations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.6.2 Analyse plus poussée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.7 Customisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.8 Limites de l’analyse locale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5 Analyse globale 395.1 Notion précise de contour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.1.1 Contour de méthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.1.2 Contour de classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.2 Réseau de type concrets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.3 Formalisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.3.1 Les domaines utilisés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.4 Les règles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5.4.1 Démarrage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425.4.2 Appels de méthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445.4.3 Instanciation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455.4.4 Lien et coercition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455.4.5 Attributs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.5 Application des règles à quelques techniques . . . . . . . . . . . . . . . . . . . . . . . . 455.5.1 Algorithme de base : 0-CFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465.5.2 Algorithmes polyvariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465.5.3 Algorithmes adaptatifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475.5.4 Proposition d’une nouvelle technique . . . . . . . . . . . . . . . . . . . . . . . . 48

5.6 Approximation de 0-CFA par l’unification . . . . . . . . . . . . . . . . . . . . . . . . . . 485.6.1 Filtrage dans les approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5.7 Précision des analyses globales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495.8 Détection du code mort et vivant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

6 Conclusion 53

Bibliographie 57

A Résumé des techniques 59

Liste des figures

2.1 La technique de 0-CFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2 Exemple de limite de 0-CFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.3 Exemple de 1-CFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.4 Exemple de limite de 1-CFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.5 Exemple de CPA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.6 Exemple de SCS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.1 Schéma de l’analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164.1 Domaines utilisés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224.2 Grammaire de définition des templates . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244.3 Représentation graphique des templates . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.4 Exemple de code dans un pseudo-langage . . . . . . . . . . . . . . . . . . . . . . . . . . 254.5 Résultat de l’exemple de la figure 4.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.6 Résultat graphique de l’exemple de la figure 4.4 . . . . . . . . . . . . . . . . . . . . . . . 264.7 Exemple de simplification précise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.8 2 templates pour la fonctionbar de l’exemple 4.4 . . . . . . . . . . . . . . . . . . . . . . 344.9 Exemple de calcul de la précédence des expressions . . . . . . . . . . . . . . . . . . . . . 375.1 2 contours de clésk et l pour la fonctionbar de l’exemple 4.4 . . . . . . . . . . . . . . . 405.2 Ensembles utilisés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425.3 Précision des informations supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . 435.4 Fonctions utiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435.5 Fonctions spécifiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435.6 Règles de l’algorithme général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465.7 Règles d’unification de noeuds des algorithmes sous 0-CFA . . . . . . . . . . . . . . . . . 495.8 Imbrication des niveaux d’analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

vii

Chapitre 1

Introduction

En programmation, la connaissance des types et la connaissance du graphe d’appels sont deux chosesimportantes. La première, par exemple, aide le développeur à détecter des erreurs en vérifiant si le typageest sûr et la seconde permet des optimisations comme la suppression du code mort.

Dans les langages orientés objets, ces deux notions sont étroitement liées. En effet, une des caractéris-tiques de ces langages est l’envoi de messages (ou liaison tardive, voire appel de méthode virtuelle). Ladifficulté de l’analyse de types et de la construction du graphe d’appels est que l’on ne peut pas calculerl’un sans avoir au préalable calculé l’autre.

Mais le jeu en vaut particulièrement la chandelle car cela permet des optimisations telles que laliaison statique d’envoi de messages monomorphe ou l’inlining de méthodes comme cela est utilisé dansSmallEiffel [Collin et al., 1997; Zendraet al., 1997].

L’objectif de ce travail est l’adaptation des techniques existantes d’analyses de types et de calculs dugraphe d’appels, qui sont intrinsèquement globales, au développement des programmes qui est, pour desquestions de modularité et de rapidité dans les compilations successives, basé sur la compilation séparée.

C’est justement suivant ce dernier principe que nous allons séparer notre analyse en deux parties, lapremière liée à la compilation séparée de classes sera dite locale (ou intra-procédurale) et la seconde,effectuée lors de l’édition de liens sera dite globale (ou inter-procédurale).

Ce mémoire est découpé en quatre parties. La première est un état de l’art des travaux précédentsafin de poser les définitions et de situer le problème dans son contexte. En effet, l’analyse de types et laconstruction du graphe d’appels sont des sujets qui ont fait couler beaucoup d’encre.

La seconde partie pose les spécificités de notre approche, en particulier en ce qui concerne le langagecible et la séparation entre l’analyse locale et l’analyse globale.

La troisième partie décrit les techniques mises en oeuvre pour l’analyse locale qui part donc du codesource pour arriver à une représentation synthétique de composantes localement indépendantes (classes etméthodes).

La quatrième partie s’interroge sur l’utilisation de ces représentations et leurs interdépendances dansun programme particulier et entier. C’est ici que sont évoquées les techniques vues dans la première partiegrâce à un schéma général.

Enfin, une conclusion terminera ce mémoire en évoquant les perspectives en matière d’implémentationet d’intégration à d’autres techniques d’optimisations globales.

1

Chapitre 2

Définitions et état de l’art

2.1 Graphes d’appels

Définition 1 Un sous-programmeest une organisation d’instructions qui peut faire appel à d’autres sous-programmes de façon statique (le sous-programme appelé est connu avant l’exécution) ou dynamique (lesous-programme appelé n’est connu qu’à l’exécution).

Un programme informatiqueest un ensemble de sous-programmes dont un en particulier, appelé prin-cipal (main) ou racine (root) est celui qui sera exécuté en premier.

Cette définition générale et incomplète1 s’adapte parfaitement aux langages procéduraux à la C ou à la Pas-cal (voire à l’assembleur), aux langages à objets à la SmallTalk ou à la Eiffel ou aux langages fonctionnelsà la LISP.

Définition 2 Le graphe d’appelsd’un programme est un graphe orienté enraciné où les sommets sont lessous-programmes et les arcs les appels entre ces sous-programmes.

Les sous-programmes qui sont atteignables à partir du sous-programme principal sont ditsvivants.Par opposition, les sous-programmes qui sont inaccessibles à partir du sous-programme principal sont ditsmorts.

La première utilisation des graphes d’appels est la suppression du code mort : en effet ce code n’étantjamais exécuté, on peut se permettre de le supprimer et de ne pas l’inclure dans l’exécutable final.

Malheureusement, le problème de la construction du graphe d’appels exact d’un programme est indé-cidable (tout autant qu’est indécidable l’arrêt d’une machine de Turing[Gil et Itai, 1998]). De ce fait lesalgorithmes de construction de graphes d’appels ne sont que des approximations.

Comme l’objectif premier est la détection du code mort, les approximations se doivent d’être complèteset non exactes : il vaut mieux considérer vivant un sous-programme mort que mort un sous-programmevivant sous peine d’avoir des problèmes à l’exécution.

De plus, de façon abusive, les algorithmes de construction de graphes d’appels ne considèrent généra-lement que la notion de code vivant et de code mort en occultant la notion de graphe d’appels.

2.2 Graphes d’appels en objet

Les appels de méthodes polymorphes sont un point fort des langages à objets mais un vrai problème ence qui concerne la compilation et l’efficacité de cette compilation.

Le premier gros problème est la détection du code mort. En effet, Dans un langage à la C, il est facile desavoir qu’un appel dans le codedessine_cercle demandera que, dans l’exécutable final, la fonctionde dessin de cercle soit incluse.

1Les gens qui travaillent sur des machines chimiques par exemple ne seront pas forcément d’accord.

3

4 CHAPITRE 2. DÉFINITIONS ET ÉTAT DE L’ART

Malheureusement, dans les langages à objets et dans les programmes qui respectent les principes debonne programmation, on a plus de chances de trouver quelque chose commeforme.dessine . Or ilexiste peut-être autant de méthodesdessine que de classes dans le programme. De ce fait, pour êtresûr de ne pas se tromper, on forcerait le compilateur à inclure dans l’exécutable toutes les méthodes, soiten gros toute la bibliothèque graphique, la bibliothèque sonore, la bibliothèque réseau,etc. Ce qui faitpeut-être un peu lourd si on ne dessine que des cercles en silence.

Le deuxième gros problème est la rapidité des appels de méthodes polymorphes. De part les implémen-tations standard des compilateurs et le fonctionnement des processeurs actuels, les appels en dur tels qu’ilsexistent en C sont beaucoup plus rapides que les appels à des méthodes polymorphes. Donc, si on se rendcompte qu’un site d’appel conduit à une seule méthode (site dit monomorphe) ou à peu de méthodes (sitedit oligomorphe), alors des optimisations comme l’appel direct ou même l’inlining sont possibles.

2.2.1 RA et UN

RA (Reachability Analysis) est la première technique mise au point[Srivastava, 1992]. Son principen’est pas très compliqué : une méthode est vivante si et seulement si son nom apparaît dans un site d’appeld’une méthode vivante.

Ceci peut être écrit sous la forme de deux règles qui construisent un ensembleR (reachable) de mé-thodes vivantes.

main ∈ R[RA : Règle 1]

m ∈ R e.n ∈ m m′ de nomn

m′ ∈ R[RA : Règle 2]

UN (unique name), dans un même ordre d’idée, permet de détecter les sites d’appel monomorphes[Calder et Grunwald, 1994]. Son comportement est très simple également : s’il existe une seule méthodede nomn alors le site d’appele.n est monomorphe. L’argument peut paraître trivial mais il n’est pas sansefficacité : en SmallTalk, sur 7 623 sélecteurs il s’applique à 3 313[Ducournau, 1997].

2.2.2 CHA

CHA (Class Hierarchiy Analysis) prend en compte les informations de types pour affiner le travailde RA : il va restreindre les méthodes potentielles à celles redéfinissant la méthode du type statique dureceveur[Dean et Chambers, 1994; Deanet al., 1995].

Soit la fonctionsub(e) qui retourne l’ensemble des sous-classes (au sens large) du type statique d’uneexpression, et soit la fonctionRes(C, n) qui retourne la méthode de nomn définie ou héritée dansC.

main ∈ R[CHA : Règle 1]

m ∈ R e.n ∈ m C ∈ sub(e)Res(C, n) ∈ R

[CHA : Règle 2]

2.2.3 RTA

RTA (Rapide Type Analysis) est l’une des méthodes de construction du graphe d’appels les plus utili-sées. Elle est plus performante que CHA car elle prend en compte les informations d’instanciation[Baconet al., 1996; Bacon et Sweeney, 1996; Bacon, 1997].

L’idée est de déterminer, en plus des méthodes, quelles sont les classes vivantes, c’est-à-dire les classesqui possèdent des instances.

Nous avons besoin ici de trois règles qui se chargeront de construire un ensembleR de méthodesvivantes et un ensembleS de classes vivantes.

main ∈ R[RTA : Règle 1]

2.3. ANALYSE DE TYPES 5

m ∈ R e.n ∈ m C ∈ sub(e) ∩ S

Res(C, n) ∈ R[RTA : Règle 2]

m ∈ R new C ∈ m

C ∈ S[RTA : Règle 3]

2.3 Analyse de types

Pour aller plus loin que RTA, il faut se rendre compte d’une chose : dans le site d’appele.m, connaîtrele type dee ou plutôt tous les types que peut avoire dans toutes les exécutions du programme permettraitde savoir plus précisément quelles sont les méthodes appelées pare.m.

Définition 3 On appelletype concret[e] d’une expressione cet ensemble de types.

Dans les langages à typage statique, il existe déjà une information sur les types. En effet, chaque ex-pression est typée (explicitement ou non) par un type unique, le type statique (notéτs). La règle est :∀t ∈ [e] t <: τs(e) (tout type du type concret est sous-type du type statique) que l’on peut écrire aussi[e] ⊆ sub(e).

Une première idée est d’approximer le type concret par l’ensemble des sous-types du type statique :c’est exactement ce que fait CHA. RTA approxime le type concret par l’ensemble des sous-types vivantsdu type statique.

Dans les langages à typage dynamique, la connaissance des types concrets a toujours suscité un grandintérêt au vu de ses nombreuses utilisations. Essentiellement pour suppléer l’absence des types statiques.Une des techniques utilisées est le calcul destypes abstraits(ou type d’interface ou types principaux) quise base sur les propriétés abstraites des objets. Un des meilleurs et des plus curieux algorithmes peut êtretrouvé dans[Milner, 1978].

L’idée est de calculer l’ensemble des types qui peuvent répondre à une expression sans erreur de type.Par exemple, le pseudo-code suivant (à la SmallTalk) :

def factorial =self<=1 ifTrue: [1] False: [self * predecessor factorial]

self doit répondre aux opérateurs<=, * mais aussi au messagepredecessor sachant que le résultatdepredecessor doive répondre àfactorial .

L’algorithme va donc analyser le code pour finalement calculer que self est de type abstrait {smallInt,BigInt, float, mutableString, immutableString, list, primitiveFailedError, time, true, false, nil,etc.}.

Pour ce qui nous intéresse (à savoir optimiser les mécanismes de compilation pour un programmeparticulier) cette technique pose deux problèmes.

Le premier est que le type abstrait n’est calculé qu’à partir d’informations abstraites et non des caracté-ristiques d’un programme donné. Ce qui nous donne des types abstraits très polymorphes alors que le typeconcret aurait été, par exemple dans ce cas précis, plus proche de {SmallInt, BigInt}.

Le deuxième est que le calcul des types abstraits met en œuvre des algorithmes lourds qui deviennentencore plus lourds en augmentant la précision. Par exemple, un des algorithmes les plus précis met 10heures pour inférer les types de l’expression 3 + 4[Phillips et Shepard, 1994].

2.4 Analyses du flux

2.4.1 Flux de données

L’analyse de flux de données permet de connaître les différentes valeurs que peuvent prendre les ex-pressions d’un programme. C’est une technique de vérification et d’optimisation connue et utilisée depuislongtemps.


y=x

new Y

y

new X

new Y

x

y

x

new Xx=new X

y=new Y

On associe un noeud par expression et on diffuse les types concrets.

Figure 2.1 – La technique de 0-CFA

Ces techniques analysent les valeurs manipulées par le programme, que cela soit au niveau des sous-programmes (analyse intra-procédurale) ou au niveau des échanges entre les sous-programmes (analyseextra-procédurale). C’est d’ailleurs à cause de cette analyse extra-procédurale que les techniques d’analysede types sont en étroite relation avec les techniques de construction de graphe d’appels.

Pour les compilateurs de langages procéduraux (C, Pascal, Ada, Fortran,etc.), ces techniques étaientla clé de voûte des optimisations : elles permettaient entre autres la détection d’invariants de boucles,l’élimination des affectations redondantes, la propagation de constantes et l’analyse d’intervalles,etc. [Ahoet Ullman, 1977].

2.4.2 Flux de types

C’est donc tout naturellement que les techniques d’analyse des flux de données ont été adaptées pourcalculer les flux de types.

Les premières techniques furent développées pour les langages fonctionnels2 [Shivers, 1988; Shivers,1991; Heintze, 1994]. Puis pour les langages à objets[Palsberg et Schwartzbach, 1991; Grove, 1995].

Des informations complémentaires peuvent être trouvées dans[Grove et Chambers, 2001].

2.4.3 La technique de base : 0-CFA

L’idée de 0-CFA (Control-Flow Analysis) est de construire un réseau où un noeud (un ensemble detypes) est associé à chaque entité typable du programme (expressions et attributs de classe) et les arcs(inclusion entre les ensemble de types) sont définis en fonction des informations contenues dans le pro-gramme,[Shivers, 1988; Shivers, 1991; Palsberg et Schwartzbach, 1991; Palsberg et Schwartzbach, 1994;Grove, 1995].

De cette façon, on approximera le type concret de chaque expression, comme le montre la figure 2.1.Abusivement, on ne fera pas de différence entre un type concret, son approximation et le noeud du réseau

2Un résumé des travaux sur les types dans les langages fonctionnels est disponible dans[Palsberg, 2001].

2.4. ANALYSES DU FLUX 7

retour de laméthode "clone"

paramètre de laméthode "clone"

piuneBrebis{Reel}

{Brebis, Reel} {Brebis, Reel}

{Brebis}

piAussidolly

Les appels partagent les même noeuds, il y a pollution.

Figure 2.2 – Exemple de limite de 0-CFA

associé. Cet abus nous poussera même à dire que certaines techniques calculent des types concrets plus pré-cis que d’autres alors qu’il aurait fallu dire que certaines techniques approximent mieux les types concretsque d’autres.

La construction du réseau se fait en suivant les règles suivantes :– À une expression qui correspond à une instanciation d’une classeC, on ajouteC au type concret de

l’expression.– À une expression d’affectation d’une expressione dans une variable ou attributv, on ajoutera un arc

d’inclusion entre le type concret dee et celui dev.– À une expressione qui correspond à un appel de méthodee′.n, pour toutes les méthodesm de

nom n connu (c’est-à-dire définies ou héritées) dans les classes du type concret dee′, on ajouteun arc entre chaque type concret de chacun des arguments (et le receveure′) et le paramètre for-mel dem correspondant. De plus, on ajoute un arc entre le type concret du résultat dem et celui dee.

La difficulté vient du fait qu’il faut faire circuler les types le long des arcs (résolution d’un problème decontraintes d’inclusion) tout en construisant le réseau. En effet, pour faire circuler les types il faut connaîtretoutes les méthodes appelées et pour connaître les méthodes appelées par site d’appel il faut connaître letype concret du receveur, donc faire circuler les types.

On verra plus tard que cette interdépendance entre la circulation des types concrets et la constructiondu réseau n’est pas seulement au niveau des appels de méthode mais aussi au niveau des instanciations detypes ancrés et des accès aux attributs.

2.4.4 Les limites de 0-CFA

Le problème majeur de 0-CFA est qu’il fait se mélanger les types concrets au niveau de chaque méthode.En effet, on se rend compte que pour une méthode donnée le type concret d’un paramètre formel seral’union des types concrets des arguments correspondants sur tous les sites d’appel, le type concret du retourd’un appel de la méthode risquant fortement d’être pollué par d’autres appels de cette méthode n’ayant rienà voir.

Un cas extrême serait par exemple la méthodeclone définie uniquement à la racine du graphe d’hé-ritage et donc héritée par toutes les classes.


Imaginons maintenant un programme avec quelque part les instructions suivantes :

uneBrebis = new Brebisdolly = uneBrebis.clone...pi = new ReelpiAussi = pi.clone

Comme le montre la figure 2.2, 0-CFA va calculer que le type concret dedolly est {Brebis, Reel},de même que pourpiAussi .

Une première amélioration est lacustomisation[Chamberset al., 1989] : cette technique consiste àrecopier chaque méthode pour chaque classe qui en hérite. De cette façon, chaque classe possède sa propreversion de ses méthodes qui n’est en aucun cas partagée avec les autres classes.

Dans l’exemple précédent avec les brebis et les réels, la customisation règle le problème mais cettetechnique n’est pas parfaite. Premièrement, la customisation d’une grande hiérarchie de classes peut amenerdes problèmes de taille (par exemple, dans la hiérarchie standard de SmallTalk3 il y a environ 1 000 classes,10 000 méthodes mais en customisant on arrive à 200 000 méthodes. Pour Eiffel4, on a 1 318 classes, 14 202méthodes mais 302 717 méthodes après customisation). Deuxièmement, même si le mélange des typesconcrets du receveur n’est plus possible, il reste possible pour les paramètres.

Plus loin, dans la méthode de Hash et dans l’algorithme général, on montrera qu’il est facile d’arriver àappliquer la customisation sans avoir à dupliquer au préalable les méthodes.

2.4.5 Techniques polyvariantes

Comme nous l’avons vu, le problème de 0-CFA est que les mêmes noeuds sont utilisés pour analyser lacirculation des types dans toutes les utilisations d’une même méthode. Ce qui donne des résultats parfoiséloignés de ses utilisations particulières.

L’idée est donc de construire un bout du réseau par utilisation particulière des méthodes, c’est ce qu’onappelle les techniquespolyvariantes.

La différence avec 0-CFA se situe donc au niveau du graphe d’appels (comme défini dans la section 2.1)où les méthodes seront analysées plusieurs fois selon un point de vue différent et à chaque fois de façonpropre à une utilisation particulière. Une utilisation particulière d’une méthode est appelée uncontour deméthode5.

La première méthode polyvariante 1-CFA (ou expansion de niveau 1)[Palsberg et Schwartzbach, 1991;Oxhoj et al., 1992] considère de travailler sur des méthodes différentes en fonction de leur site d’appel(leur position physique dans le code).

De cette façon, si dans un programme il y a plusieurs utilisations de la méthodeclone , chacuneutilisera son propre bout de graphe pour analyser ses types concrets pour une utilisation précise comme lemontre la figure 2.3.

L’intuition est bonne, mais il y a deux gros problèmes avec l’expansion de niveau 1. Premièrement, siplusieurs appels d’une méthode de mêmes valeurs au niveau des types mais provenant d’un site différentexistent, on calculera plusieurs fois la même chose pour rien. Deuxièmement, la précision n’est toujourspas au rendez-vous comme le montre la figure 2.4. En effet même si une méthode n’est pas appelée à partirdu même endroit dans le code, les sous-appels (c’est-à-dire les appels de cette méthode) le sont. Donc àpartir du deuxième niveau d’appel, les types concrets sont, à nouveau, mélangés entre eux.

L’idée est donc d’augmenter le niveau d’expansion, c’est ce que l’on appelle 2-CFA, 3-CFA et plusgénéralementk-CFA [Vitek et al., 1992; Palsberg et Schwartzbach, 1994; Plevyak et Chien, 1994; Phillips

3D’après[Ducournau, 1997].4D’après[Driesen, 1999].5Le terme de contour vient sans doute du fait que dans le graphe d’analyse de flux on peut regrouper les noeuds ayant trait à l’une

ou autre de ces utilisations particulières ce qui fait que graphiquement on entoure généralement chaque ensemble de noeuds pour quecela soit plus lisible.


piuneBrebis{Reel}

{Brebis} {Reel}

{Brebis}

piAussidolly

méthode "clone"Contour de la Contour de la

lié à l’appel"pi.clone""uneBrebis.clone"

lié à l’appelméthode "clone"

Pour chaque appel, un contour dédié est utilisé, il n’y a donc pas de pollution.

Figure 2.3 – Exemple de 1-CFA

uneBrebis

{Brebis, Reel}

{Brebis}

dolly

pi{Reel}

piAussi{Brebis, Reel}

Contour de la

méthode "cloneBis"lié à l’appel

"uneBrebis.cloneBis"

Contour de laméthode "cloneBis"

Contour de la

méthode "clone"lié à l’appel dans "cloneBis"

lié à l’appel"pi.cloneBis"

Cette fois-ci, on analysedolly = uneBrebis.cloneBis et piAussi = pi.cloneBis oùcloneBis est une méthode retournant le résultat de la méthodeclone .

Figure 2.4 – Exemple de limite de 1-CFA


et Shepard, 1994]. Ce concept est bien connu dans la communauté des flux de données[Ryder, 1979] sousle nom dechaîne d’appels (call string).

Une amélioration supplémentaire (k-l-CFA) consiste à s’intéresser également aux classes[Vitek et al.,1992; Palsberg et Schwartzbach, 1994] en considérant que les types concrets ne sont plus des classes maisdes classes différenciées par leurs positions d’instanciation dans le code (relative à une chaîne d’appelsde longueurl). L’idée est de pouvoir augmenter la précision en évitant de mélanger les types concrets desattributs.

k-CFA et k-l-CFA semblent intéressants car ils offrent une précision paramétrée : plus on augmentek (et l), plus cela nécessite de ressources et plus le résultat est précis. Malheureusement, il reste encorebeaucoup d’insuffisances. Pour un programme donné, il est difficile de savoir à l’avance quelle profondeurde chaîne d’appels est nécessaire. De plus, les problèmes de calculs redondants de 1-CFA sont ici poussésplus avant, ce qui implique, pour desk pas forcément élevés, des temps de calcul prohibitifs dans desprogrammes un peu conséquents.

2.4.6 Techniques adaptatives

L’idée qu’une analyse de types précise doit éviter de trop mélanger les types concrets semble bonne.Les mélanges se produisent au niveau des appels de méthodes quand plusieurs types concrets sont reliés àun même paramètre formel. La solution radicale (∞-CFA) est que chaque appel de méthode conduirait àune nouvelle analyse de chaque méthode potentiellement appelée, c’est-à-dire une construction du graphed’appels où chaque site d’appel posséderait son propre ensemble de méthodes.

L’idée qu’une analyse de types rapide doit éviter de construire un graphe contenant trop de noeudssemble bonne. La solution radicale (0-CFA) est de n’avoir dans le graphe d’appels qu’un seul sommet parméthode.

Il est facile de construire des techniques d’analyse de types précises et il est facile de construire destechniques d’analyse de types rapide mais est-il possible de construire une technique d’analyse de types àla fois rapide est précise ?

Pour arriver à un tel compromis, il faut partager intelligemment plusieurs sommets du graphe d’appelsentre plusieurs sites d’appel. Partager intelligemment signifie pourvoir répondre à la question : deux sitesd’appel peuvent-ils avoir des contours de méthodes communs ?

Nous pouvons déjà classer les trois algorithmes vus en fonction de la réponse apportée à cette question :– pour 0-CFA, tous les sites d’appel partagent les mêmes contours de méthode ;– pour 1-CFA, un contour de méthode est partagé si et seulement le site d’appel est le même ;– pourk-CFA, un contour de méthode est partagé si lesk derniers éléments de la chaîne d’appels sont

les mêmes.

Tous ces algorithmes basent donc leur décision sur la chaîne d’appels qui est une information statiqueet assez éloignée de la connaissance sur les types. C’est là où lestechniques adaptatives d’analyse de typestirent leur épingle du jeu. En effet ces techniques vont utiliser les informations sur les types pour partagerplus intelligemment les contours de méthode entre les sites d’appel.

La solution idéale (oualgorithme idéal) serait de ne partager les contours de méthode que si les typesconcrets du receveur et des arguments sont les mêmes. De cette façon, l’analyse du flux d’un contour deméthode pour une utilisation particulière ne serait pas polluée par les types des autres utilisations (puisquece sont les mêmes) et d’autre part pour plusieurs utilisations qui appellent une méthode avec les mêmestypes concrets, on n’aurait qu’une seule analyse de flux ! Cette solution a donc l’avantage d’être à la foisprécise et rapide.

Malheureusement, cette solution est vraiment idéale dans le sens où elle ne peut pas être implémentée.En effet, pour nos algorithmes nous avons besoin des types concrets des arguments des appels de méthode,or c’est précisément ce que nous cherchons à calculer : les types concrets. Il est généralement admis qu’ilest facile de trouver un algorithme qui calcule quelque chose sachant que le résultat est une donnée duproblème6.

6Il se trouve que pour l’analyse de types, ce genre de problème arrive souvent quand on cherche de nouvelles idées, en particulier


2.4.7 Technique par fonction de Hash

Développé dans[Agesenet al., 1993], cette technique est la première technique adaptative d’analysede types. Utilisée pour Self, elle permit d’avoir une analyse de types précise pour la première fois.

Son nom vient du fait que la technique utilise une fonction appeléehashqui associe un ensemble devaleursHash_valueà un couple (site d’appel, contour de méthode).

En réalité, Hash est une famille de techniques dont font partie d’autres techniques comme CPA ou SCS.Sachant qu’un site d’appel peut appeler plusieurs contours d’une même méthode, il est possible de

filtrer les types concrets passés d’un contour à un autre.Par exemple, la customisation peut être vue comme un cas particulier de Hash dans le sens où le type

concret du receveur définit l’ensemble des contours utilisés : un contour par type du type concret. Ainsi decette façon, le receveur sera toujours monomorphe.

2.4.8 Algorithme Itératif

Avec l’algorithme itératif, Plevyak et Chien[Plevyak et Chien, 1994; Plevyak et Chien, 1995] cassentl’inefficacité du rapport précision/vitesse dek-CFA. Pour comprendre leur technique, revenons à l’algo-rithme idéal.

Nous savons que l’algorithme idéal ne peut être implémenté car il nécessite de connaître le résultatavant de le calculer.

Plevyak et Chien ont trouvé un moyen de sortir de ce dilemme en répétant l’inférence de types. Lapremière itération est 0-CFA, puis pour chaque nouvelle itération on utilise les résultats de la précédentepour savoir quand partager ou non les contours en gardant le principe de l’algorithme idéal, c’est-à-dire :le contour est partagé si dans l’itération précédente, les types concrets du receveur et des arguments sontles mêmes.

La précision de cette technique est importante puisqu’elle est efficace pour n’importe quelle profondeurdonnée de chaîne d’appels : en effet, aprèsk itérations, la précision est la même que celle dek-CFA. Etelle est plus rapide car elle essaie de regrouper les contours qui donneront le même résultat.

L’algorithme itératif est donc précis mais la médaille a un revers voire deux. Le premier est le nombred’itérations, car si ce nombre est grand, l’algorithme est d’autant plus lent. De plus il est difficile de savoirquel nombre d’itérations est nécessaire. Le deuxième revers se situe au niveau de l’implémentation : ilest difficile de relier les informations de type avec les résultats de l’itération précédente car les graphesd’appels peuvent être très différents.

2.4.9 CPA

CPA (Cartesian Product Algorithm) fut développé par Agesen[Agesen, 1994; Agesen, 1995a; Agesen,1995b]. C’est un cas particulier de Hash.

L’idée de base est de revenir à une analogie entre l’exécution d’un programme et son analyse en créantdes contours monomorphes (les types concrets du receveur et des paramètres sont des singletons). Onrelie donc chaque site d’appel polymorphe à autant de contours qu’il y a de combinaisons entre les typespolymorphes.

Pour un appel de méthodex.f(y1, y2, . . . , yn), l’ensemble des combinaisons est le produit cartésiensoit [x]× [y1]× [y2]× · · · × [yn].

Chaque élément du produit cartésien sera donc propagé dans un contour de méthode. Si un contourde méthode existe déjà pour ce tuple de type, alors il est réutilisé, sinon un nouveau est créé et rendudisponible pour ce tuple et les tuples futurs. Voire figure 2.5.

Le principal problème de CPA est un problème de taille : il crée de très nombreux contours. De ce fait,CPA, qui est à ce jour l’algorithme le plus précis, ne pèche pas par son temps de calcul mais par l’espacemémoire qu’il demande. En effet, au pire des cas CPA, demandeO(na) contours pour un site d’appel, oùn est le nombre de méthodes du programme eta l’arité du site d’appel.

à cause de l’interdépendance entre la construction du réseau de types concrets et sa résolution.


Soit la méthodemax à un argument qui retourne le plus grand objet entre le receveur et l’argument. Leréseau du flux de types qui considère deux appels demax sera le suivant avec CPA :

Contours de "max"

Un appel de "max" Un autre appel de "max"

Le résultat dupremier appel

Le résultat dusecond appel

On a un contour par élément du produit cartésien.

Figure 2.5 – Exemple de CPA

Une solution proposée par Agesen est une version bornée de CPA. On teste pour chaque receveur ouargumentx si son type concret est mégamorphe :|[x]| ≤ c où c est un petit nombre.

Quand un receveur ou argument est mégamorphe, le produit cartésien n’est plus effectué sur celui-ci, àla place on créera des tuples de la forme(x1, x2, ∗, y3) où∗ indique un site mégamorphe.

Cette contraction des types mégamorphes est efficace pour éviter de trop grands produits cartésiens. Leprix à payer est bien sûr une perte de précision sur ces appels-là mais pas forcément flagrante car les appelsmégamorphes ne sont pas forcément nombreux dans un programme.

2.4.10 SCS

SCS (Simple Class Set) décrit dans[Groveet al., 1997] est un cas étrange de Hash car il revient àl’algorithme idéal dans le sens où on ne crée qu’un contour par méthode dans un site d’appel, celui-ci étantdéfini par les types actuellement calculés du receveur et des arguments (voir figure 2.6).

De ce fait, deux appels d’une même méthode dont les types concrets provisoirement calculés coïncidentpartagent le même contour.

Dans le pire des cas, SCS demandeO(nna

) contours pour analyser un site d’appel mais il se trouvequ’en pratique, on est très loin de ce cas limite. Dans[Grove et Chambers, 2001], l’implémentation de SCSest plus rapide que l’implémentation de la version bornée de CPA.

2.4.11 Techniques entre RTA et 0-CFA

Plusieurs techniques existent pour approximer 0-CFA, toutes se basent sur le principe de relâcher lescontraintes et calculer les choses plus globalement. Une grande partie de ces méthodes est décrite dans[DeFouwet al., 1998].

Le principe de l’unificationest de regrouper certains noeuds du réseau de flux de types. L’unificationpeut se faire en disant que la relation d’inclusion entre les types concrets devient une relation d’égalitécomme dansbinding time analysis[Henglein, 1991] oualias analysis[Steensgaard, 1996].

On peut unifier dynamiquement les noeuds avec les techniques décrites dans[DeFouwet al., 1998]qui se basent sur le principe qu’après un certain nombre de circulations de types, les noeuds peuvent êtreunifiés.

2.5. CAS DES ATTRIBUTS 13

Le réseau du flux de types qui considère deux appels demax sera le suivant avec SCS :

Un appel de "max" Un autre appel de "max"

premier appelLe résultat dusecond appel

Contours de "max"

Le résultat du

On a un contour par tuple de types concrets.

Figure 2.6 – Exemple de SCS

Tip et Palsberg avec leur algorithmes XTA, FTA, MTA et CTA[Tip et Palsberg, 2000] font une unifi-cationa priori des noeuds. De CTA où on considère un noeud par classes jusqu’à XTA où on considère unnoeud par attribut et par méthode. Cette unificationa priori permet d’analyser les programmes Java sansavoir à extraire les informations des variables dubytecode.

2.5 Cas des attributs

Un autre problème d’optimisation est la détection des attributs morts. Un attribut est mort s’il n’estsoumis à aucun accès en lecture ou à aucun accès en écriture. Détecter de tels attributs et les supprimerpeut également avoir un impact significatif sur les ressources demandées par un programme, car la placegagnée se trouve au niveau des instances (gagner quatre octets peut être intéressant si ces quatre octets sontutilisés par mille instances).

Des techniques plus élaborées et spécifiques aux attributs existent, comme laClass hierarchy specia-lisation [Tip et Sweeney, 2000] qui consiste à détecter les utilisations des attributs particulières à chaqueinstance et à remodeler les classes de façon optimale7. Mais même ces techniques très spécialisées se basentsur des approximations de types concrets et de graphe d’appels.

7Plus d’information sur la réorganisation des hiérarchies sont disponibles dans[Dicky et al., 1996; Godinet al., 1998].

Chapitre 3

Analyse séparée dans les langages typés

3.1 Spécification du problème traité

Les analyses de types et les techniques de construction de graphes d’appels sont globales car ellesnécessitent de connaître le programme dans son ensemble pour en déduire son utilisation. De ce fait, lesanalyses existantes partent directement de la totalité du code.

Cette approche esta priori incompatible avec la notion de compilation séparée. En effet, le schémagénéral de la compilation séparée est le suivant :

– compilation indépendante de chaque classe et production d’un fichier intermédiaire contenant le codecompilé et les informations de liaison, en effet pour une classe donnée seule l’interface des classesutilisée est nécessaire à la compilation, le code produit est donc indépendant de l’implémentation dureste du programme ;

– édition de lien regroupant les fichiers intermédiaires, c’est-à-dire la construction, grâce aux informa-tions de liaison, d’un fichier unique : le programme, contenant le code de chaque fichier intermé-diaire.

La phase de compilation a donc lieu avant d’avoir la connaissance globale du programme, or cetteconnaissance est nécessaire à nos analyses.

C’est pourquoi nous proposons ici d’appliquer ce schéma en deux phases à l’analyse de types et àla construction de graphe d’appels : l’analyse locale (ou analyse intra-procédurale) et l’analyse globale(ou analyse inter-procédurale), ces deux concepts étant proches de ceux très spécifiques développés dans[Diwanet al., 1996].

Ainsi, la première phase, l’analyse locale, se déroulera au même niveau que la compilation, c’est-à-direoù connaissance du programme se limite à une classe et à ses méthodes. Le but de l’analyse locale est d’unepart d’identifier les informations de types et de circulation de ces types localement à chaque méthode etd’autre part de déterminer les interfaces avec les autres classes et méthodes. Toute ces informations serontregroupées dans un fichier particulier : letemplate.

À ce niveau, notre travail est de fournir un ensemble de techniques et d’idées pour essayer de voirtous les calculs et optimisations que l’on peut faire sans connaissance globale du code, en particulier en seconcentrant sur le corps des méthodes et de ce que l’on peut en déduire.

La seconde phase, l’analyse globale, se déroulera au même niveau que l’édition de liens. Elle réunira lestemplates d’un programme et utilisera leurs informations pour calculer le résultat final. Plus les templatesfournis par l’analyse locale seront précis plus l’analyse globale sera précise et plus les templates fournisseront petits1, plus l’analyse globale sera rapide.

À ce niveau, notre travail consiste à utiliser les analyse de types et les techniques de construction dede graphe d’appels connues de façon à ce qu’elles utilisent les templates comme unique donnée de départdans le but de séparer au maximum l’analyse locale de l’analyse globale.

1C’est-à-dire qu’un maximum de choses ont déjà été faites à l’analyse locale.

15

16 CHAPITRE 3. ANALYSE SÉPARÉE DANS LES LANGAGES TYPÉS

ClasseMethodeMethodeMethode...

Analyse localeClasse

attributsmethodemethode...







Analyseglobale

Code Template

Figure 3.1 – Schéma de l’analyse

3.2 Langage objet cible

Une autre particularité de ce travail est qu’il cible des langages peu étudiés en ce qui concerne l’analysede types et le calcul de graphe d’accès. En effet, le travail se porte sur un langage objet à la Eiffel2, c’est-à-dire avec les particularités suivantes :

– classes et philosophie réaliste,– typage statique,– sélection simple,– structures de contrôles,– généricité,– types ancrés.

3.2.1 Classes et philosophie réaliste

Le langage est structuré autour de la notion de classe. Chaque objet est donc l’instance d’une classe etles classes sont rangées dans une hiérarchie d’héritage3.

De plus la relation de sous-typage est conditionnée à la notion de sous-classes.

La philosophie réaliste (au sens d’Aristote) signifie que les classes ne sont pas des objets. Donc, d’unepart les classes tendront à disparaître à la compilation et d’autre part les classes sont toutes connues aupréalable (pas de création dynamique).

On considère que la hiérarchie d’héritage possède une racine (Object, ANY,etc.) et une classe spécialesous-classe de toutes les classes (Nil, NONE,⊥, etc.) exprimant la classeabsurde, c’est-à-dire l’absence devaleur. Le fait que cette classe soit sous-classe universelle permet sa présence dans tous les types concretstout en respectant le principe de sous-typage par rapport au type statique. Ce qui permet le sophisme quiconsiste à dire que le typage est sûr alors qu’il y a des valeurs⊥.

2Eiffel a déjà été l’objet d’une implémentation de RTA avec le compilateur SmallEiffel[Collin et al., 1997].3L’héritage peut être multiple ou simple, cela n’influe en rien.

3.2. LANGAGE OBJET CIBLE 17

3.2.2 Typage statique

Dans les langages à typage statique, les entités typables (expressions, variables et attributs) possèdentun type statique. Les types que prendront à l’exécution les entités typables seront forcément sous-type dutype statique.

Les langages à typage statique possèdent une information sur les types contrairement aux langagesà typage dynamique. C’est donc sur ces derniers que la plupart des recherches sur la connaissance destypes (en particulier pour SmallTalk et Self) ont été menée. Les algorithmes existants n’utilisent que trèspeu les informations du type statique, ce qui n’est pas le cas ici où les techniques développées utilisentabondamment les critères de sûreté des types.

Dans les langages à typage dynamique il n’y a aucune information de type pour les entités typables. Ilest tout de même possible d’utiliser cette analyse en considérant que le type statique des entités typablesest à chaque fois le type racine, mais il ne sera pas possible d’appliquer les règles de typage habituelles.

3.2.2.1 Types de bases

Les types de bases (comme en C++), s’ils existent, ne sont pas représentés car ils sont purement etsimplement éliminés. En effet le type concret d’une expression dont le type statique est un type de basebest le singleton{b}. Les types de base et leurs méthodes sont toujours considérés comme vivants.

Par élimination on entend l’ignorance complète des occurrences des types de base et des expressionsstatiquement typées par des types de base (à l’exception des appels de méthode). Dans les cas extrêmes,une méthode ayant des paramètres avec de types de base perd ces paramètres (et baisse en arité). De plus,une fonction qui retourne un type de base devient une procédure.

Dans les cas où les types de base sont en réalité des classes comme les autres à la restriction près quel’on ne peut pas les spécialiser, on peut éventuellement supprimer de notre analyse de types les expressionstypées directement sur ces classes. Reste à voir si un traitement particulier de ce cas particulier apporteréellement une amélioration notable dans les performances et/ou la précision.

3.2.2.2 Typage et erreurs de types

Un dernier point important est l’utilisation des techniques d’analyse de types pour résoudre d’autresproblèmes liés aux types comme la preuve du typage sûr (la non-existence d’erreur de types).

Bien sûr, les langages de programmation fortement typés permettent de mettre en place des techniquessimples qui garantissent l’absence d’erreur de types à la compilation[Aho et al., 1985]. Malheureusementtoutes les erreurs de types ne sont pas décelables aussi facilement car contraindre l’expressivité des langagespar un sous-typage sûr (qui est contravariant) va à l’encontre des spécificités de spécialisation du paradigmeObjet (qui lui est covariant)[Ducournau, 2001c]. De ce fait les langages introduisent des mécanismes pourrelâcher cette contrainte et augmenter le pouvoir expressif, au prix de vérifications de types à faire lors del’exécution.

Or les vérifications de types ont un coût qui, dans certains cas, peut être non négligeable, notammenten héritage multiple[Ducournau, 2001b]. Pouvoir détecter que les types concrets des expressions sontconformes à leur type statique en dépit des largesses offertes par les relâchements des mécanismes desous-typage peut donc permettre d’éviter ces vérifications à l’exécution.

Le premier cas de relâchement de contrainte est lacoercition. La coercition (ou l’acte de contraindre)est un moyen offert au programmeur pour affirmer qu’une expression est d’un type donné qui généralementest plus spécifique que le type statique qui aurait été normalement associé à cette expression.

Le second cas est un relâchement de contrainte plus général qui consiste à rendre le sous-typagecovariant, le typage n’est plus alors considéré sûr. Les règles de vérification des types des langages àtypage sûr sont toujours valides, la seule limitation réside au niveau des paramètres des méthodes et desaffectations d’attributs.

Il y a erreur de type si le type concret ne se conforme pas au type statique, c’est-à-dire si la conditionsuivante n’est pas vérifiée :

[e]exact⊆ sub(τs(e))

18 CHAPITRE 3. ANALYSE SÉPARÉE DANS LES LANGAGES TYPÉS

En réalité, on peut distinguer trois cas exclusifs dans le cas où[e] 6= ∅ :– le premier cas précise que l’extension du type concret est inclus dans celle du type statique :[e]exact⊆sub(τs(e)), donc il n’y aura pas d’erreur de type ;

– le deuxième cas précise que le type concret est disjoint du type statique :[eexact] ∩ sub(τs(e)) = ∅,donc il y aura toujours une erreur de type.

– le troisième et dernier cas précise que le type concret chevauche le type statique :[e]exact ∩sub(τs(e)) 6= ∅ et [e]exact\ sub(τs(e)) 6= ∅, donc il peut y avoir une erreur de type ;

Malheureusement on ne peut pas travailler sur le type concret exact car on ne le connaît pas. Tout ceque l’on connaît est un type concret approximé qui garantit[e]exact⊆ [e].

Qu’en est-il alors pour les trois cas adaptés aux types concrets approximés ?– premier cas :[e] ⊆ sub(τs(e)) ⇒ [e]exact⊆ sub(τs(e)), donc il n’y aura pas d’erreur de types, on

peut se dispenser d’un test à l’exécution ;– deuxième cas :[e] ∩ sub(τs(e)) = ∅ ⇒ [e]exact∩ sub(τs(e)) = ∅, donc il y aura une erreur de type

systématique, on peut le signaler à la compilation au programmeur et lever systématiquement uneexception à l’exécution ;

– troisième cas :[e] ∩ sub(τs(e)) 6= ∅ ⇒ rien, on ne peut rien déduire pour le type concret exact, lestrois cas sont envisageables, on peut éventuellement le signaler mais il est nécessaire d’effectuer untest à l’exécution.

3.2.2.3 Adaptation aux receveurs vides

Lors des appels de méthodes, on doit généralement tester si le receveur est vide (nil , NULL, void ,etc.). La même méthode peut nous aider, en effet, si le type concret d’un receveur ne contient pasnil , celagarantit que ce receveur n’est pas vide et donc nous dispense également d’un test à l’exécution. De même,si le type concret contient uniquementnil , cela signifie que le receveur sera systématiquement vide, onpeut là aussi le signaler au programmeur et systématiquement lever une exception à l’exécution.

3.2.3 Sélection simple

Les méthodes sont définies dans les classes et nous nous limiterons à de la sélection simple.La sélection simple signifie qu’un site d’appel est constitué d’un nom de méthode (ousélecteur) et d’un

certain nombre de paramètre dont un particulier est appeléreceveur. La méthode réellement appelée parce site d’appel dépend uniquement du sélecteur (qui est une information statique) et du type dynamique dureceveur (qui est une information dynamique).

RemarqueIl est très facile d’étendre le modèle à de la sélection multiple. Nous avons limité à la sélec-tion simple uniquement par simplicité (et par l’absence de langage répandu à typage statique avec sélectionmultiple).

Dans le même ordre d’idée, il serait peut-être intéressant de traiter la covariance en faisant des multi-méthodes, c’est-à-dire de prévoir deux versions des méthodes, une avec les types redéfinis qui contiendraitle code de la nouvelle définition de la méthode et l’autre avec les types non redéfinis (ceux de la premièredéfinition dans les super-classes) qui signalerait une erreur de types.

3.2.4 Existence desuper

La plupart des langages introduisent des mécanismes pour pouvoir avoir accès aux anciennes définitionsdes méthodes. Le moyen le plus répandu est l’utilisation du mot clefsuper , présent de Java à SmallTalk.Un autre moyen est l’opérateur d’indirection:: de C++.

Généralement, les études précédentes ne prennent pas en compte cette particularité. Ici nous nousbornerons à la possibilité d’appeler une méthode d’une classe particulière (à la C++), format dans lequelles super de Java ou de SmallTalk peuvent être convertis (il suffit de remplacer lesuper par unappel de la méthode de même nom sur la super classe, ces deux informations étant parfaitement connuesstatiquement et localement). Par contre, les mécanismes de linéarisations (à la CLOS) ne sont pas gérés.

3.2. LANGAGE OBJET CIBLE 19

Eiffel possède également ce genre de mécanisme, le mot clefprecursor remplaçant le motsuper ,dans lequel doit être précisée la super-classe en cas d’héritage multiple, mais il est également courant devoir un autre moyen qui consiste à dupliquer la méthode puis en redéfinir une seule pour garder l’autre.

Techniquement, il faut hériter deux fois de la classe dont on souhaite redéfinir la méthode, une premièrefois en renommant la méthode et la seconde fois en redéfinissant la méthode4. Lors de la nouvelle définitionde la méthode il est donc permit d’appeler l’ancienne méthode par son nouveau nom.

Ce moyen de faire n’est, par contre, pas pris en compte car le renommage des méthodes n’est pas géré5.

3.2.5 Structures de contrôle

Unestructure de contrôleest un dispositif du langage qui permet d’exécuter les instructions de manièrenon linéaire. Dans les langages courants, les structures de contrôle les plus communes sont leif thenelse , le while et lefor mais tout un tas d’autres dispositifs permettent de contrôler l’exécution commele break ou le basiquegoto par exemple.

De plus, certains opérateurs peuvent être assimilés à des structures de contrôle car ils permettent decasser la linéarité du programme, je veux parler de l’opérateur ternaire? : du C mais aussi des opérateursbooléenset et ou qui peuvent décider de court-circuiter l’évaluation des opérandes si le résultat est déjàconnu.

Toutes ces structures de contrôle peuvent se réduire à un ensemble de primitives :– le saut inconditionnel lexical :goto , où on connaît statiquement l’exécution suivante à exécuter ;– le saut conditionnel :if then else , qui permet de faire des tests et des branches d’exécutions ;– le saut inconditionnel dynamique : l’échapement, qui permet d’aller à un endroit inconnu statique-

ment.et peuvent être traités par des transformations source à source.

Dans les langages à la SmallTalk, il n’y a pas, à proprement parler, de structures de contrôle maisl’évaluation n’est pas pour autant linéaire à cause des blocs. Mais nous ne nous y intéresserons pas.

RemarqueOn ne traite pas les structures fonctionnelles d’ordre supérieur comme les fermetures (cf.[Grove et Chambers, 2001]).

3.2.6 Généricité

Le langage peut permettre de définir des classes ou des méthodes génériques. Cette particularité seratraitée en travaillant sur les instances de ces classes ou méthodes génériques.

Ainsi Array[String] etArray[Point] seront considérés comme deux classes différentes.

3.2.7 Types ancrés

Les types statiques pouvant annoter le programme ne sont pas limités aux classes explicites (représen-tées par leur nom) mais peuvent faire référence au type dynamique du receveur (notélike self ) ou autype statique d’un attribut du type dynamique du receveur (notélike nom_attribut ).

Cette caractéristique n’est, à ma connaissance, disponible que dans Eiffel et dans divers langages uni-versitaires6 mais est relativement intéressante en ce qui concerne l’analyse de types car un type statiquedevient une fonctions d’un type dynamique.

4Comme l’héritage estvirtuel par défaut, au sens de C++, il n’y aura aucune duplication.5C’est également le cas des compilateurs Eiffel qui ne gèrent pas tous le renommage des méthodes.6mytype dans LOOM, POLYTOIL ousame dans SATHER

Chapitre 4

Analyse locale

L’analyse locale (ou analyse intra-procédurale) se base sur la connaissance du code de classes et deméthodes pour construire des templates.

4.1 Templates

Le template, terme emprunté à Agesen, représentait un réseau de circulation de types restreint à uneméthode. Dans cette approche nous étendrons cette définition, d’une part, en définissant deux sortes detemplates, les template de classes (ClassTemplate) et les template de méthodes (MethTemplate)1, et d’autrepart, en tentant de simplifier et de pré-traiter ces templates.

Un template est donc la représentation interne des flux de types dans une méthode ou dans les attributsd’une classe. Ce flux de types est caractérisé sous la forme d’un réseau de contraintes où chaqueentitétypabled’un template est une variable du réseau de contraintes. Les contraintes elles-mêmes pouvantcontenir des références à desfonctions globalesvers le monde extérieur.

On noteExpr l’ensemble des expressions, variables et attributs du code. Chacun de ces élémentsepossède un type statique notéτs(e) et un type concret noté[e] que notre objectif final à pour but d’approxi-mer.

Au niveau d’une analyse localel on va travailler sur un ensemble d’entités typablesnotéEntityl, detelle façon que chaque expression, variable et attribut soit représenté par une entité typable, la fonction dereprésentation étant notéeRepl :

Repl : Expr −→ Entityl

e 7−→ Repl(e)

Or l a pour rôle de définir ces entités typables mais aussi les contraintes liées à ces entités typablestelles que la résolution des contraintes permet de trouver pour chaque entité typablev l’ensemble minimalde type noté[v] qui respecte les contraintes.

Comme l’analyse localel calcule une approximation large du type concret des expressions, variableset attributs, on aura au final :

∀e ∈ Expr [e] ⊆ [Repl(e)]

RemarqueQuand l’analyse locale dont on parle n’est pas ambiguë, on peut omettre d’indicer systéma-tiquement.

Les contraintes sont toutes des contraintes d’inclusion (⊆) d’approximation de types concrets. On ap-pellecibled’une contrainte la partie droite d’une contrainte etsourcela partie gauche.

1Chez Agesen il n’y avait pas de template de classes pour la simple raison que Self, le langage cible de ses recherches est unlangage à prototypes et donc sans classes.

21

22 CHAPITRE 4. ANALYSE LOCALE

ClassId : Un identificateur de classe (unique globalement), le nom généralement.MethName : Un nom de méthode ou plus exactement le sélecteur.VarId : Un identificateur d’entité typable d’une méthode ou variable (unique par méthode).AttrName : Un nom d’attribut d’une classe qui correspond à l’interface de la classe.

Figure 4.1 – Domaines utilisés

4.1.1 Filtrage

Certaines contraintes demandent l’utilisation d’un filtre par un type statique. Comme nous l’avons vu,le langage étant sûr dans la plupart des cas, l’inclusion d’un type concret dans un autre est généralementvalide. Or dans le cas des coercitions et de la covariance des paramètres et des attributs, on est obligé defiltrer sur un type statique en considérant que tout type qui ne passe pas le filtre est une erreur de typepotentielle. On noteφ(C, s) ce filtre oùC est un ensemble de types ets un type statique.

Si s est une classe, le filtre ne laisse passer que les classes qui sont sous-classes, c’est-à-dire :φ(C, s) ={c ∈ C | c <: s}. De plus, on est sûr de ne pas avoir d’erreur de type si∀c ∈ C c <: s.

Or, de par la présence des types ancrés, le filtrage est beaucoup plus difficile car, à un type statiques,peut correspondre plusieurs classes. L’ensemble de ces classes étant inconnu localement, il n’est pas facilede prévoir ni quels types passeront le filtre ni s’il y a un risque d’erreur de type.

RemarqueBien sûr le filtrage n’est absolument pas nécessaire, il ne sert qu’à augmenter la précision età détecter les erreurs de types on peut donc s’en passer si on estime que sa mise en œuvre n’apporte quepeu de précision supplémentaire pour un coût trop élevé.

4.1.2 Template de classe

Les templates de classes sont identifiés de façon unique par leur nomClassId.L’interface d’une classe est l’ensemble des attributs (AttrName) définis dans la classe mais aussi les

attributs hérités. De ce fait on peut résoudre les types ancrés des attributs car chaque attribut est propre àune classe.

Les entités typables des templates de classes sont associées aux attributs. En général, une entité typablepar attribut mais on peut également associer une même entité typable à plusieurs attributs.

Pour chaque entité typablea associée à un attribut de type résoluc, on a les contraintesφ(fin, c) ⊆ [a]pour l’interface d’entrée et[a] ⊆ fout pour l’interface de sortie oùfin désigne la résolution des accès enécriture,fout la résolution des accès en lecture qui seront faites à l’analyse globale.

La première contrainte filtre les erreurs de types dues à la covariance des attributs. Dans les langages àtypage sûr où cette covariance n’est pas permise, ce filtre n’est pas nécessaire.

4.1.3 Template de méthode

Les templates de méthodes sont identifiés de façon unique par leur classe de définition et par leursélecteurMethName.

En effet, comme la sélection est simple, chaque méthode possède une classe de définition.En ce qui concerne le sélecteur, la différence entre le nom de la méthode et son sélecteur est importante

car elle permet de régler les cas de surcharge statique à la C++ ou deux méthodes peuvent avoir le mêmenom mais pas le même sélecteur. En effet le sélecteur peut contenir en plus du nom des informations sur leprototype de la méthode comme l’arité ou le type des paramètres.

Les entités typables d’une méthode représentent les expressions et les variables que nous regrouponssous le terme générique de variable (VarId). Ainsi une variable d’un template ne correspond pas forcémentà une variable du code du corps de la méthode.

4.1. TEMPLATES 23

Il existe une variable particulière? qui désigne la variable inutile (un peu le /dev/null d’unix ou lavariable _ de prolog), elle sert quand les valeurs de retour de méthodes ne nous intéressent pas ou plussimplement n’existent pas. Cette variable n’a pas d’existence propre c’est juste un bouche trou.

L’interface d’entrée d’une méthode est constituée des paramètres (dont le premier a un statut particulierpuisqu’il est le receveur) chacun désigné par une variable liée de telle façon que pour une variablev liée àun paramètrei on ait la contraintefin(i) ⊆ [v] où fin désigne la résolution des entrées des appels de cetteméthode qui sera fait à l’analyse globale.

L’interface de sortie est limitée au résultat de telle façon que pourv liée au résultat on ait la contrainte[v] ⊆ fout oùfout désigne la résolution des sorties des appels de cette méthode.

Il est nécessaire de préciser un point important, la covariance des paramètres n’apparaît pas dans l’in-terface d’entrée des méthodes, en effet pour plusieurs raisons un autre moyen sera utilisé pour exprimercette propriété, tout ceci étant expliqué dans la section 4.2.2.

Pour traduire le comportement des méthodes, on relie les variables à descommandes. Il existe 7 com-mandes :

Lien (LinkC) Indique une inclusion sûre des types concrets.Le type concret de la variable ciblev1 contient le type concret de la variable sourcev2 soit lacontrainte[v2] ⊆ [v1]. Cette commande est utilisée dans la plupart des affectations par exemple.

Coercition (CoerC) Indique une inclusion non sûre.On doit donc filtrer le type concret de la variable sourcev2 par un type statiques avant de l’incluredans le type concret de la variable ciblev1 de telle façon que si des types ne passent pas le filtre,elles déclencheront une erreur de type. Soit la contrainte :

φ([v2], s) ⊆ [v1]

Appel polymorphe (SendC) Indique un appel de méthode.Le type concret de la variable ciblev1 dépend du résultat d’un appel de méthode. Cet appel deméthode étant défini par le sélecteurn, les argumentsr, a1, a2 (r étant le receveur). Soit la contrainte :

fsend(n, ([r], [a1], [a2], . . .)) ⊆ [v]

où fsend désigne la résolution de l’appel qui sera faite à l’analyse globale. Remarque : on présumecette fonction retourne quelque chose de sûr au niveau des types.

Appel statique (CallC) Indique un appel de méthode connue statiquement. Soit la contrainte :

fcall(n, c, ([r], [a1], [a2], . . .)) ⊆ [v]

où fcall désigne la résolution de l’appel qui sera faite à l’analyse globale. C’est exactement commeun appel polymorphe sauf que la résolution de la méthode appelée est faite statiquement sur la classdonnéec. Cette commande n’est utilisée que pour lesuper , pour l’opérateur d’indirection:: oules appels non virtuels de C++ ou pour les cas où l’analyse locale à déterminer que l’appel estmonomorphe.

Instanciation (NewC) Indique l’instanciation explicite (par unnew) ou implicite (par une valeur littérale)d’un type statiques.Le type concret des variables ciblesv contient donc les classes désignées par les types statiques soitla contrainte :

Sta(s) ⊆ [v]

où Sta désigne la résolution des types statiques (à cause des types ancrés) qui sera faite à l’analyseglobale.

Lecture (ReadC) Indique que le type concret de la variable ciblev est lié à celui d’un attribut.Cet attribut étant défini par son nomn et son receveurr. Soit la contrainte :

fread(n, [r]) ⊆ [v]


ClassTemplate : :=Class ClassId Attribute* MethodTemplate*Attribute : :=attr ClassInterface*ClassInterface : :=AttrName : ClassIdMethodTemplate : :=Method MethName VarId* :VarId Command*StaticType : :=ClassId | self | likeAttrNameCommand : := LinkC | CoerC | SendC | CallC | NewC | ReadC | WriteCLinkC : := VarId = VarIdCoerC : :=VarId =coer VarId StaticTypeSendC : :=VarId =send MethName VarId*CallC : :=VarId =call MethName ClassId VarId*NewC : :=VarId =new StaticTypeReadC : :=VarId =read AttrName VarIdWriteC : :=AttrName VarId =write VarId

Figure 4.2 – Grammaire de définition des templates, les symboles terminaux sont écrits en police courrier.

oùfreaddésigne la résolution de l’accès en lecture qui sera faite à l’analyse globale et qui est sûre auniveau des types.

Écriture (WriteC) Indique que le type concret d’un attribut est lié à celui d’une variable sourcev.

Cet attribut étant défini par son nomv et son receveurr. Soit la contrainte :

[v] ⊆ fwrite(n, [r])

oùfwrite désigne la résolution de l’accès en écriture qui sera faite à l’analyse globale.

Chaque variable a unflux d’entrée de typesqui détermine à lui seul le type concret de la variable. Ceflux d’entrée de types est lui-même déterminé par l’appartenance de la variable à l’interface d’entrée etmais aussi par les commandes ayant pour cible la variable.

4.1.4 Représentation des templates

Pour représenter un template nous utiliserons la grammaire définie dans la figure 4.2. Lors de la com-pilation séparée d’un programme, à chaque compilation unitaire d’une classe ou d’un ensemble de classes,on effectuera une analyse locale qui produira donc un ensemble de templates en plus des fichiers compilés.

RemarquePour chaque variable et commande, on peut également préciser l’ensemble des portions ducode représentées (par les noeuds de l’arbre syntaxique par exemple), mais le retour au code n’étant pas lebut premier de notre problématique, nous ne préciserons pas d’avantage les moyens à mettre en oeuvre.

En plus de cette grammaire, on peut représenter les templates de façon graphique pour plus de facilité.Mais il faut faire attention car le graphe d’appels, le réseau des flux de types et les templates sont toustrois représentables graphiquement mais ne représentent pas du tout la même chose. Pour cette raison, lestemplates et leurs éléments seront représentés en utilisant les symboles définis dans la figure 4.3.

RemarqueDans la représentation graphique, la variable? n’apparaît pas car elle n’a pas d’existencepropre.

4.2 Génération des templates

Le template est, comme nous l’avons dit, une représentation du code uniquement axée sur les typesconcrets caractérisée par les entités typables (variables et attributs) et leur contraintes caractérisées parl’interface mais aussi, dans les méthodes, par les commandes.

Le problème est de savoir quels éléments et commandes construire pour une classe donnée (c’est-à-direavec ses attributs et ses méthodes).

4.2. GÉNÉRATION DES TEMPLATES 25

VariableLiee

Variable

VariableLiee

Variablefiltre

Argument

selecteur

Resultat

Argument

Receveur

Commande de lien Commande de coercition Commande d’appel

type

Variable

Receveur attribut

LieeVariable

Receveur attribut

Variable

Commande d’instanciation Commande de lecture Commande d’écriture

Figure 4.3 – Représentation graphique des templates

Class Foodef uneSuite : Suitedef bar(Int i, Array[Foo] a) : Foo

if isBigger(a.at(i))return bar2

elsereturn a.at(i).bar2

endenddef bar2() : Foo

attr = attr.nextreturn self

enddef bar3() : like self

return new like selfend

end

Figure 4.4 – Exemple de code dans un pseudo-langage


Class Fooattr uneSuite:Suite

Method bar p1 p2 p3 : retv1 =call at p3 p2v2 =call at p3 p2ret =call bar2 p1ret =call bar2 v2? =call isBigger p1 v1

Method bar2 p1 : retv1 =read uneSuite p1v2 =call next v1uneSuite p1 =write v2ret = p1

Method bar3 p1 : retret =new self

Figure 4.5 – Résultat de l’exemple de la figure 4.4

atuneSuite

next

at

isBigger

bar2 bar2

uneSuite

self

p1 p2 p3 p1

p1

retret

v2

v1v2v1

ret

Définie dans "Foo"Méthode "bar"

Définie dans "Foo"Méthode "bar2"

Définie dans "Foo"Méthode "bar3"

Classe Foo

uneSuite

Suite

Figure 4.6 – Résultat graphique de l’exemple de la figure 4.4

4.2. GÉNÉRATION DES TEMPLATES 27

4.2.1 Solution basique

Dans la première solution qui vient à l’esprit, appeléebasiqueet notéeb, l’idée est d’associer à chaquevariable, expression et attribut une entité typable d’un template.

Ainsi, pour chaque attribut d’une classe il y aura un attribut dans le template de la classe et pourchaque variable, paramètre et expression dans une méthode (sans oublier le receveur et la valeur de retour)il y aura une variable dans le template de la méthode.

En ce qui concerne les commandes au sein des méthodes, les règles de construction sont les suivantes :pour chaque instruction ou expressione du code,

– sie est une affectation sûrex = expr , on ajoute un lien entre la variable deexpr et celle dex ;– si e est un cast2 (Class)expr , on ajoute une coercition surClass entre la variable deexpr et

la variable dee ;– si e est un appel de méthode dynamiqueexpr.meth(arg1,arg2,...) , on ajoute un appel de

la méthode de sélecteur correspondant, de receveurrecv , d’argumentsarg1 , arg2 . . . et de résultate (remarque : si la méthode ne retourne pas de résultat, on associe ce dernier à la variable spéciale?) ;

– si e est un appel de méthode statiqueexpr.C::meth(arg1,arg2,...) , on ajoute un appelstatique de la méthode de sélecteur correspondant, de classeC, de receveurrecv , d’argumentsarg1 , arg2 . . . et de résultate (remarque : si la méthode ne retourne pas de résultat, on associe cedernier à la variable spéciale?) ;

– si e est une instanciationnew C (ou un littéral de la classeC), on ajoute une instanciation de laclasseCà la variable dee ;

– si e est une lecture d’attributexpr.attr , on ajoute une lecture de l’attributattr , de receveurexpr de cible la variable dee ;

– si e est une écriture d’attributexpr1.attr = expr2 , on ajoute une écriture de l’attributattr ,de receveurexpr1 de source la variable deexpr2 et on ajoute un lien entre la variable deexpr2et dee ;

– si e est la commandereturn expr , on ajoute un lien entre la variable deexpr et la variableassociée au résultat de la méthode.

Bien sûr, on ne duplique pas les commandes. S’il y a déjà un lien entre la variable dey et celle dex ,l’expressionx = y n’ajoutera pas un lien supplémentaire.

De plus, pour chaque variable localex du code, si elle a une valeur initiale (c’est-à-dire une valeurdéfinie à la déclaration), on traite cette valeur comme une affectation normale. Si elle n’a pas de valeurinitiale, alors on ajoute une instanciationpar défaut, c’est-à-dire une instanciation de la classe Nil.

RemarqueSi dans le langage, les paramètres sont considérés comme des variables, alors on doit créerdeux entités typable, une pour le paramètre et une pour la variable associée dont la valeur initiale est leparamètre, c’est-à-dire qu’un lien est ajouté entre l’entité typable associé au paramètre et l’entité typableassocié à la variable.

4.2.2 Gestion de la covariance dans l’analyse basique

Dans les langages covariants le typage n’est pas sûr. Afin d’être relativement complètes, les techniquesd’analyse de types doivent donc, pour chaque site d’appel, résoudre les types ancrés et détecter les erreursde types en plus de déterminer le type concret de receveur, d’en déduire les méthodes appelées, de définirles contours à utiliser (si besoin)3 et filtrer les paramètres en fonction des contours et/ou afin de réduire lebruit (si besoin).

L’idée, afin de simplifier et clarifier le problème, est de séparer la gestion de la covariance de la gestionde l’envoi de messages.

2ou une tentative d’affectation à la Eiffel.3Certaines techniques, ditespolyvariantesanalysent les méthodes sous plusieurs contextes d’exécutions, voir la section 2.4.5 (p.

8).


Ainsi, au lieu d’avoir un passage de paramètres pas sûr, on considère donc que le passage de paramètresest toujours sûr mais que ce paramètre est aussitôt suivi par une coercition4.

RemarqueLa gestion des attributs étant plus simple à analyser (pas de contour et pas de type ancré)que l’envoi de messages, on peut se permettre de gérer la covariance et les erreurs de types au niveaumême de l’accès en écriture des attributs. De plus, il aurait pu paraître étrange d’ajouter des commandesde coercition dans un template de classe.

La seule limitation de cette simplification est que les erreurs de types dues aux passages de paramètresseront détectées au niveau du template appelé et non au niveau de l’appel lui-même. On peut bien sûrutiliser le graphe d’appels pour remonter aux appels de la méthode et regarder au cas par cas lequel de cesappels à produit l’erreur de type.

Dans les techniques de partage des contours (CFA et en dessous) l’appel fautif sera sans doute noyédans la masse. Par contre, pour les techniques polyvariantes, la perte de précision est plus faible pour 1-CFA, CPA ou SCS. Une erreur de type au niveau d’une coercition de paramètre indiquera à coup sûr quetous les appels ne le sont pas.

À y réfléchir un peu plus, on peut tenter de se convaincre que cette limitation n’est pas si grave car onest covariant dans les techniques : plus une technique est dite précise, plus la détection et la localisationdes erreurs de types seront précises.

Concrètement, lors de la génération des templates, un paramètre défini de manière covariante à un typestatiquet (ou dont le type statiquet est un type ancré) sera lié normalement à une variablev1 et on créeraune nouvelle variablev2 lié par une coercition surt àv1, soitv2 =coer v1 t.

Par la suite,v2 représentera le paramètre et nonv1, ce dernier n’étant présent que dans la commandede coercition définie précédemment.

4.3 Sûreté et précision des analyses locales

Définition 4 Une analyse localel estsûresi elle respecte le typage, c’est-à-dire que, pour un programmecorrectement typé, elle nous garantit que le type concret de toute entité typable est cohérent avec tous lestype statiques des expressions, variables et attributs représentés.

∀e ∈ Expr ∀t ∈ [Repl(e)] t <: τ(e)

Définition 5 Une analyse localel1 est diteplus précisequ’une analyse localel2, et notél1 ≥ l2 si pourchaque expression, variable et attribut, le type concret de la variable correspondante dansl est inclus dansle type concret de la variable correspondante dansb.

∀e ∈ Expr [Repl1(e)] ⊆ [Repl2

(e)]

Théorème 1 Une analyse locale plus précise qu’une analyse locale sûre est également sûre.

PreuveSoit une analysel plus précise qu’une analysel′ qui est sûre. Commel ≥ l′ on a ∀e ∈Expr [Repl(e)] ⊆ [Repl′(e)] or l’analysel′ est sûre, donc∀e ∈ Expr,∀t ∈ [Repl′(e)] t <: τ(e)

On en déduit∀e ∈ Expr,∀t ∈ [Repl(e)] t <: τ(e), soit que l’analysel est sûre.

�

Par ces règles de construction qui respectent le type statique, on peut conjecturer que l’analyse basiqueest sûre, ainsi que toute analyse locale au moins aussi précise que l’analyse basique.

4C’est exactement ce qui se passe dans les langages contravariants comme C++ ou Java où l’absence de covariance oblige l’utili-sation de coercition.

4.4. SIMPLIFICATIONS DES TEMPLATES 29

Soit le code suivant :a = b = 1 ; a = b + 2 ; a = a + 3 ; c = 4 + 5 (en ignorant les ins-tanciations par défaut des variables).Avec la solution basique on obtient 16 variables, 10 liens, 5 instanciations et 3 appels.Après optimisation, on obtient 4 variables, 3 liens, une instanciation et 2 appels.

a=b+2

c c=4+5

+

4+5

5

Int

3

Int

4

Int

1

b=1b

2 a

a=b=1

a−3

a=a−3

−

Int

Int

+

b+2

Int

a −+

1,2,3,4,5,b,b=1,a=b=1

b+2,a=b+2,c,c=4+5

a−3,a=a−3

Solution basique Simplification précise

Figure 4.7 – Exemple de simplification précise

4.4 Simplifications des templates

4.4.1 Simplification précise

La solution précédente marche très bien. L’analyse globale réunira les templates et se chargera derésoudre les types concrets. Mais serait-il possible de déjà commencer à calculer et à prévoir les typesconcrets tout en réduisant le nombre de variables et de commandes ? Cela accélérerait l’analyse globale card’une part son travail serait pré-mâché et d’autre part les templates seront plus petits donc plus rapidementtraités.

L’idée de lasimplification précise, notéesp, est donc d’essayer d’associer à une même variable deuxexpressions dont on sait qu’elles auront le même type concret.

Pour arriver à ce template simplifié, on part d’un template tel qu’il serait fourni par la solution basiqueet on applique les règles de simplifications suivantes tant que c’est possible :

Première règle Toutes les variables (non liées aux paramètres ou au receveur) cibles des mêmes com-mandes sont confondues. Ce qui revient à regrouper les appels de même méthode et de mêmesarguments, les instanciations de mêmes classes,etc.

Deuxième règleSi une variablev1 est cible d’un lien avecv2 et quev1 n’est cible d’aucune autre com-mande ou n’est pas liée à un paramètre ou au receveur, alorsv1 etv2 sont confondus.

Troisième règle S’il existe un circuit de commandes de lien alors toutes les variables du circuit sontconfondues.

Quatrième règle Si v est à la fois source et cible d’une commande de lien, cette commande est supprimée.

Bien sûr, les doublons de commandes sont supprimés.

Théorème 2 La simplification précise est une analyse locale aussi précise que la solution basique.

PreuveIl suffit de montrer que chaque règle unifie des variables de même type concret et supprime descommandes qui n’ont aucun effet.

– Première règle : Pour chaque variable, le type concret est déterminé par son interface d’entrée et parles commandes qui la cible. L’interface d’entrée n’est limitée qu’aux paramètres et au receveur doncpour chaque variable à l’exclusion des variables liées aux paramètres et au receveur, le type concret


est déterminé par les commandes qui la cible. Donc, des variables cibles des même commandesauront le même type concret.

– Deuxième règle :v1 est cible d’un lien avecv2 donc [v2] ⊆ [v1], or v1 n’est cible d’aucuneautre commande et n’est pas liée à l’interface d’entrée donc la solution minimale qui respecte lescontraintes surv1 est[v1] = [v2].

– Troisième règle : Soientv1, v2, v3, . . . , vj telles quev1 soit cible d’une commande de lien de sourcev2, v2 soit cible d’une commande de lien de sourcev3, . . . etvj soit cible d’une commande de liende sourcev1. On a donc[v1] ⊆ [vj] ⊆ · · · ⊆ [v3] ⊆ [v2] ⊆ [v1], on en déduit donc[v1] = [v2] =[v3] = · · · = [vj].

– Quatrième règle : Soitv est à la fois source et cible d’une commande de lien, on a donc[v1] ⊆ [v1]qui est une information qui n’apporte rien car toujours vérifiée.

�

RemarqueLa simplification précise est moins précise que la solution basique si on fait circuler deschoses plus complexes que de simples classes dans nos types concrets. Lors de l’analyse globale, certainestechniques (commek-l-CFA) différencient les classes en fonction de leur position d’instanciation. Le faitde regrouper par la première règle entre elles des variables qui sont cibles de l’instanciation d’une mêmeclasse peut amener à une perte d’information car les classes ne pourront pas être différenciées. Il est tout demême possible de construire une simplification précise plus précise en considérant que chaque instanciationest différente.

4.4.2 Simplification minimale précise

La simplification précise est très performante dans la plupart des cas, mais elle n’arrive pas toujours àunifier toutes les variables dont ont pourrait prévoir, en utilisant toutes les informations localement dispo-nibles, que le type concret est identique.

L’idée de lasimplification minimale précise, notéesmp, est donc de calculer déjà le type concret denos variables, or cela est difficile : certaines données sont inconnues car ce sont des fonctions calculéesglobalement.

4.4.2.1 Variables d’entrée

Définition 6 On appellevariable d’entrée, notéVarIn, une variable liée à un paramètre, à une commandede coercition insimplifiable, à une instanciation, à un retour de méthode ou à une lecture d’attribut.

Définition 7 On appellevariable interne, une variable qui n’est pas une variable d’entrée.

Par construction, l’analyse basique, n’associe qu’une seule contrainte ciblant une variable d’entrée.On remarque alors que le type concret de chaque variable interne est entièrement déterminé par les

variables d’entrée. Nous allons donc, par transitivité des contraintes calculer pour chaque variable internev, l’ensembleEv des variables d’entrée tel que :

[v] =⋃

v′∈Ev

[v′]

4.4.2.2 Le cas des filtres

La question de la simplification des coercitions reste à résoudre. En effet, pour deux variablesv1 etv2,pour un type statiques et pour la commandev1 =coer v2 s , si on arrive à savoir que :

∀t ∈ [v1] t <: s

alors la commande de coercition peut être remplacée par un lien simple, transformant la variable d’entréev2 en variable interne.

4.4. SIMPLIFICATIONS DES TEMPLATES 31

Nous somme obligés de travailler non pas avec des classes mais avec un langage de types, car d’unepart nous ne connaissons pas toutes le classes à notre niveau local et d’autre part, les types statiquespossèdent déjà des données complexes : les types ancrés.

4.4.2.3 Types locaux

Définition 8 On appelletype locald’une variable, notéτ(v), l’ensemble des types statiques déduit descommandes qui la ciblent.

On ne doit pas confondre le type statique des expressions, qui est une indication faite par le program-meur et le type local des entités typables qui est une information calculée statiquement et localement à untemplate.

Un type local d’entité typable est donc un ensemble de types statiques. Il signifie que les classes dutype concret de cette variable sont au moins d’un des types de son type statique :

∀v ∈ Entity ∀c ∈ [v] ∃t ∈ τ(v) c <: t

On note également<: la relation de sous-typage entre deux types locaux, définie par

τ1 <: τ2 ssi ∀t ∈ τ1,∃t′ ∈ τ2 t <: t′

On note=: la relation d’équivalence de type définie par

τ1 =: τ2 ssi τ1 <: τ2 et τ2 <: τ1

4.4.2.4 Calcul des types locaux

Il en est des types locaux comme des types concrets, il peut être entièrement déterminé pour chaquevariable internev parEv :

τ(v) =⋃

v′∈Ev

τ(v′)

Il ne reste qu’à déterminer le type local des variables d’entrée. Ce type local dépend donc de l’uniquecontrainte qui cible notre variable.

On noteSta(s, r) la résolution d’un type statiques sur self , qui retournes si s est une classe, laclasse de définition de la méthode sis est une ancre sur self et la classe de l’attribut dans la classe dedéfinition de la méthode sis est une ancre sur un attribut.

On étend cette méthode à la résolution des type locauxl, avecSta(l) =⋃

s∈l Sta(s).On noteRes(c, n) le type statique résolu den dans la classec. Si n désigne un attribut, on retourne le

type statique résolu de l’attribut et sin désigne une méthode on retourne le type statique résolu du résultatde la méthode.

On étend cette méthode aux ensemble de classesC, avecRes(C, n) =⋃

c∈C Res(c, n).

Les types locaux des variables se calculent de la façon suivante. Pour toutv ∈ VarIn on a :

φ([v2], s) ⊆ [v] ⇒ τ(v) = {s}fentrée(i) ⊆ [v] ⇒ τ(v) = {s} oùs est le type statique du i-ème paramètre

fappel(n, ([r], [a1], [a2], . . .)) ⊆ [v] ⇒ τ(v) = Res(Sta(τ(r)), n)fstatique(n, c, ([r], [a1], [a2], . . .)) ⊆ [v] ⇒ τ(v) = Res(c, n)

Sta(s) ⊆ [v] ⇒ τ(v) = {s}flecture(n, [r]) ⊆ [v] ⇒ τ(v) = Res(Sta(τ(r)), n)


4.4.2.5 Supression des filtres

On peut donc essayer de supprimer des commandes de coercition : une commandev1 =coer v2 sétant remplaçable par une commande de lien si et seulement si :

τ(v2) <: {s}

4.4.2.6 Règles de la simplification minimale précise

La simplification minimale précises’effectue en appliquant les règles suivantes à partir de la solutionbasique :

Première règle Deux variables d’entrée cibles des deux mêmes contraintes sont unifiables5 ;

Deuxième règleUne variable d’entréev1 et une variable internev2 sont unifiables siEv2 = {v1} ;

Troisième règle Deux variables internes qui possèdent le même ensembleEv sont unifiables ;

Quatrième règle Si une variablev est à la fois source et cible d’une commande de lien, cette commandeest supprimée.

De plus, les variables d’entrée qui sont liées à l’instanciation d’une classe et non d’un type ancré sontmonomorphes. On peut donc déjà remplacer les envois de messages dont elle est receveur par des appelsstatiques.

4.4.2.7 Exemple

Par exemple, prenons le template :

n1 =new selfn2 =new Cn3 =new selfn4 =new Cv1 = n1v1 = n2v2 = n3v3 = v2v3 = n4

n1 n2 n3

self C

v1

n4

v2

v3

self C

Les variables d’entrée sontn1, n2, n3 etn4. On peut déjà unifiern1 avecn3 etn2 avecn4.

n13 =new selfn24 =new Cv1 = n13v1 = n24v2 = n13v3 = v2v3 = n24

self C

n13

v2 v1

v3

n24

On calcule ensuiteE pour nos variablesv1, v2 et v3 : Ev1 = {n13, n24} ; Ev2 = {n13} ;Ev3 ={n13, n24}.

On peut donc unifierv1 etv3. On obtient donc le template équivalent suivant.

5on n’est pas obligé d’unifier les instanciations si on veut garder un maximum de précision vis-à-vis de l’analyse globale

4.5. APPROXIMATIONS 33

n13 =new selfn24 =new Cv13 = n13v13 = n24v2 = n13v13 = v2

self C

n13

v2

n24

v13

4.5 Approximations

L’idée ici est de réduire encore un peu plus la taille des templates pour accélérer le traitement global,quitte à perdre en précision et donc à avoir des analyses locales non-sûres.

Plusieurs approximations sont possibles, et on peut les appliquer sur les templates de méthodes maiscertaines aussi sur les templates de classes.

4.5.1 Quelques solutions simples

La solution, radicale, consiste à regrouper tous les éléments d’un template en un seul, on appelle çade l’unification totale. D’ailleurs, si on applique l’unification totale aux templates de méthodes et qu’onexécute 0-CFA pour l’analyse globale on obtient XTA et si on applique l’unification totale aux templatesde classes et de méthodes, on obtient CTA.

Une solution moins radicale consiste à ne s’intéresser qu’aux composantes connexes, dans le sens oùon unifie les variables liées entre elles. Soit, pour deux variablesv1 etv2, on a la contrainte[v2] ⊆ [v1] quidevient la contrainte[v2] = [v1], on peut donc unifierv1 etv2.

Bien sûr, on peut également ne plus tenir compte des coercitions et les remplacer toutes par des liensnormaux. Soit, pour deux variablesv1 etv2 et un type statiquet, on a la contrainte[v2] ⊆t [v1] qui devient[v2] ⊆ [v1].

4.5.2 Interface minimale précise

Nos analyses locales ont pour but de permettre d’approximer le type concret les expressions, variableset attributs. Ainsi, après l’analyse globale qui finira l’approximation des types concrets, on sera en mesured’effectuer tout un tas d’optimisations dans le code.

Par contre, si notre but n’est pas le retour au code mais simplement la détection du code mort ou lecalcul du graphe d’appels, une partie seulement de ces expressions, variables et attributs nous intéressent,donc une partie seulement des entités typables. Ces entités typables étant celles liés à l’interface ou auxcommandes de d’appel de méthode ou d’accès aux attributs. Les autres sont donc inutiles, on peut lessupprimer !

Et ceci est tout à fait possible malgré le fait que dans les méthodes, pour calculer le type concret desvariables intéressantes on a besoin des autres variables. En effet, comme il a été vu dans la simplificationminimale précise, les variables peuvent être entièrement déterminés par les variables d’entrée. Il suffit alorsde reconstruire artificiellement un template qui contient un nombre restreint de commandes et variables defaçon à ce que les contraintes associées aux commandes et à l’interface de ce nouveau template produisentles mêmes types concrets pour les variables qui nous intéressent.

Les méthodes à mettre en oeuvre pour construire un template en fonction des relations entre les va-riables internes et les variables d’entrée sortent du cadre de notre étude et mériteraient sans doute unerecherche approfondie à elles seules.


at

isBigger

bar2 bar2

at

isBigger

bar2

Unification totale

v

p1 p2 p3

ret

v1

Solution minimale précise

Figure 4.8 – 2 templates pour la fonctionbar de l’exemple 4.4

4.6 Analyse des variables du code

Le cas des variables du code source (les vraies pas celles des templates) n’a pas vraiment été évoqué.Dans l’analyse basique, pour chaque variable locale du code source, on associait une entité typable. Cettefaçon de faire pose un gros problème : tous ces types possibles sont regroupés sans tenir compte de l’ordredes affectations et utilisations successives.

Ce qui fait que d’une part on a une perte de précision et d’autre part, on ne peut pas détecter lesinitialisations.

Par exemple, dans la méthode suivante :

a : Animal (= nil)a = new Vachea.criea = new Elephanta.crie crie

a

Nil Vache Elephant

a sera de type concret {Nil, Vache, Elephant} et les deux appels de méthodea.crie sont consi-dérés identiques alors que ces deux appels sont différents, monomorphes et de receveurs garantis non vides.

Un premier moyen pour résoudre ce problème consisterait à avoir plusieurs versions des variables,c’est-à-dire créer plusieurs variables dans le template pour une seule variable du code. Une nouvelle versionde la variable serait créée à chacune de ses instanciations.

Soit quelque chose d’équivalent à :

4.6. ANALYSE DES VARIABLES DU CODE 35

a1 : Animal = nila2 : Animal = new Vachea2.criea3 : Animal = new Elephanta3.crie

Vache Elephant

a1 a3

crie

a2

crie

Nil

Malheureusement, cette idée ne marche plus si l’ordre d’exécution des instructions n’est pas linéaire.C’est ce qui se passe s’il y a desstructures de contrôles.

4.6.1 Détection des initialisations

La première idée et la plus simple consiste à analyser avec la méthode de base, uniquement la partie dela méthode avant la première structure de contrôle.

Cette technique permet de détecter les initialisations qui sont faites au début de la méthode, ce quipermet de traiter Nil dans un certain nombre de cas.

Concrètement, à partir du début de la méthode, on va construire une nouvelle entité typable par instan-ciation, mais dès la première structure de contrôle rencontrée, on crée une dernière nouvelle entité typablequi sera utilisée pour le reste de la méthode.

Ainsi le code suivant :

a : Animala = new Vachea.crieif ... then

a.criea = new Elephanta.crie

enda.criea = new Moutona.crie

MoutonElephantVacheNil

a

crie

Deviendra :

a1 : Animala2 : Animal = new Vachea2.criedébut de structure de contrôlea3 : Animal = a2if ... then

a3.criea3 = new Elephanta3.crie

enda3.criea3 = new Moutona3.crie

MoutonElephantVacheNil

crie

a2a1 a3

crie

Des variations peuvent exister, comme de traiter toutes les parties qui ne sont pas dans des structuresde contrôles et en allant plus loin de créer une entité typable distincte par structure de contrôle.

4.6.2 Analyse plus poussée

Plutôt que de chercher des analysesad hoc, on peut s’intéresser à la sémantique des variables.Une variable sert à stocker et récupérer des valeurs. Pour ce faire, on possède deux instructions de base :

l’ affectationet la lecture.


Lors de l’affectation, on stocke une valeur dans une variable, cette valeur étant le résultat d’une expres-sion qui possède donc un type concret.

La lecture est une expression particulière qui retourne la dernière valeur stockée, donc un type concret.Soita une variable locale à une méthode,a1, a2, . . . , an ∈ Expr l’ensemble des affectations (expres-

sions affectés) à la variablea et a1, a2, . . . , am ∈ Expr l’ensemble des lectures (expressions lues) de lavariablea. Remarque, il peut y avoir une affectation par défaut due à la déclaration (dont Nil).

Sans traitement spécifique des variables et des structures de contrôles, les techniques d’analyse localenous donnent :

[Rep(a)] = [Rep(a1)] = [Rep(a2)] = . . . = [Rep(am)] =n⋃

i=1

[Rep(ai)]

Pour avoir des relations entre les types concrets plus proches de la sémantique des variables, il fautnous pencher sur la notion dedernière valeur stockée.

Hors parallélisme étrange, les expressions sont exécutées dans un ordre particulier. En réalité, il s’agitd’un préordre car on a de la transitivité mais il peut y avoir de la symétrie (dans une boucle par exemple).

Ce qui nous intéresse n’est pas cet ordre d’exécution mais une autre relation (non transitive celle-ci)entre l’ensemble des expressionsE, qui est laprécédence(notée<). La précédence indique si uneexpressionpeutêtre évaluée après une autre.

Le calcul ou plutôt l’approximation de cette relation est un travail qui sort un peu du cadre de ce stage.D’une part cela dépend assez fortement du langage, de ses règles d’évaluation, de ses structures de contrôleset d’autre part, on peut considérer plusieurs niveaux de précisions voire plusieurs techniques différentes.

Néanmoins, la façon sans doute la plus simple de faire serait de transformer chaque structure de contrôleen un ou plusieursgoto multiples (c’est-à-dire desgoto qui peuvent aller à plusieurs endroits à la fois)comme le montre l’exemple de la figure 4.9. La relation de précédence serait alors :

– entre deux expressionse1 ete2 qui se suivent,e1 < e2 ;– entre deux expressionse1 ete2 tel quee2 à besoin du résultat dee1, e1 < e2 ;– entre deux expressionse1 et e2 qui se calculent en même temps (dont l’ordre n’est pas garanti,

comme l’évaluation des paramètres des méthodes de certains langages),e1 < e2 ete2 < e1 ;– pour une expressione1 suivie par ungoto vers un ensemble de labels, alors pour chaque expressions

e2 qui suivent chacun des labels,e1 < e2.Une fois cette relation connue, on peut construire un graphe orientéG = (E,<) qui relie les

expressions entre elles.

Revenons à nos expressions particulièresa et a. On dit qu’une affectationai précède justeune lectureaj si et seulement s’il existe un chemin deai à aj qui ne passe pas parak (k ∈ [1..n]), c’est-à-dire qu’ilexiste une exécution telle qu’à une évaluation deaj , ai soit la dernière affectation exécutée sura.

Connaissant cela, pour notre analyse locale, la démarche à suivre est très simple : au lieu de passer parune seule entité typable de templatea qui centralise et regroupe tout, on va directement relier chaquea eta : pour tout coupleai, aj , on ajoute un lien entre ces entités typables si et seulement siai précède justeaj .

Cette analyse plus poussée est la plus précise possible car elle respecte à la lettre la sémantique desvariables. Malheureusement, elle peut générer un grand nombre de variables de templates et de liens mais ilsuffit d’effectuer une simplification minimale précise à la suite pour ne conserver que ce qui est nécessaire.

4.7 Customisation

Comme nous l’avons vu pour l’analyse minimale précise, pour l’interface minimale exacte ou pour lagestion des approximations, les types ancrés nous posent un problème lorsqu’il s’agit d’approximer lestypes concrets.

4.8. LIMITES DE L’ANALYSE LOCALE 37

e1e2if e3then

e4if e5then

e6else

e7end

ende8while e9do

e10if e11then

e12break

ende13

ende14

e1e2e3goto §1 §2§1: e4

e5goto §3 §4

§3: e6goto §5

§4: e7§5:

§2: e8§6: e9goto §7 §8

§7: e10e11goto §9 §10

§9: e12goto §8

§10: e13goto §6§8: e14

e1

e2

e3

e4

e5

e9

e10

e11

e12

e13

e14

e8

e7

e6

Figure 4.9 – Exemple de calcul de la précédence des expressions

Une solution serait d’appliquer la customisation6, ce qui permettrait de résoudre les types ancrés, c’est-à-dire de transformer un type ancré en une classe. Ainsi permettre une augmentation de la précision et uneréduction de la taille des templates.

La première solution serait de customiser toutes les méthodes, or cela engendrerait une explosion dunombre de template qui serait préjudiciable.

Une autre solution serait de ne customiser que les méthodes dans lesquelles apparaissent des typesancrés ce qui économiserait de la mémoire lors de l’analyse globale si elle utilise la customisation7.L’inconvénient de cette solution est une inégalité dans le traitement si l’analyse globale n’effectue pas decustomisation, en effet, certaines méthodes seront analysées plus finement car customisées.

Le principal problème posé par la customisation est le fait que l’on a besoin du code des sous-classeslors de l’analyse d’une classe, ce qui est incompatible avec la notion d’analyse séparée développée ici.

La solution est, lors de la définition d’une méthode, de créer deux template : une première versioncustomisée et optimisée, pour les instances directes de la classe et une deuxième version non customisée.Ainsi, lors de l’analyse d’une sous-classe, si cette méthode est héritée, on utilisera les informations conte-nues dans la version non customisé pour construire le template de la méthode customisé à cette classe. Laseule limitation est que l’on impose ainsi l’analyse locale des super-classes avant celles des sous-classes.

4.8 Limites de l’analyse locale

L’avantage de l’analyse locale est de pré-mâcher le travail en fournissant à l’analyse globale des infor-mations épurées et pré-traitées pour faire de l’analyse de types efficace. Mais c’est également son défaut,

6Voir la section 2.4.4 page 77La customisation par la méthode de Hash (cf. section 2.4.7 page 11) est plus efficace en terme de mémoire que le customisation

statique puisque seules les versions vivantes des méthodes seront créées.


en effet d’une part il faut s’assurer que les pré-traitements seront utiles à l’analyse globale mais d’autre partces informations épurées sont une limite aux capacités des analyses globales très précises ou tirant parti derenseignements peu orthodoxes.

Chapitre 5

Analyse globale

Une analyse globale (ou inter-procédurale)g a pour buts d’approximer le type concret de chaque entitétypables et d’approximer le graphe d’appels du programme.

Pour approximer le type concret de chaque entité typable, on va construire un réseauCg = (Xg, Dg) oùles noeudsXg représentent des ensembles et les arcsDg est la relation de dépendance entre deux noeuds.

Pour approximer le graphe d’appels du programme, on va construire un grapheGg = (Vg, Eg) où Vg

représente des méthodes vues dans un contexte particulier etEg les appels entre ces méthodes.RemarquePar la suite nous ne préciserons pas systématique leg.

Comme nous le savons, toute la difficulté de l’analyse vient du fait que l’approximation de l’un néces-site l’approximation de l’autre, c’est pourquoi nous devons résoudre les deux problèmes en même temps.

En effet, pour construire le réseau et le graphe, l’analyse globale part de la racine du programme puisdoit à la fois construire le réseau, le graphe et calculer les ensembles associés aux noeuds du réseau. Toutceci sera fait en utilisant les règles définies dans la figure 5.6 page 46.

5.1 Notion précise de contour

Les templates définis localement seront les briques de l’analyse globale. En effet, celle-ci devra lesagencer de façon à créer un schéma des exécutions du programme. Or un template en soi, par définition,ne contient pas d’information globale, c’est-à-dire d’information sur son ou ses utilisations dans un pro-gramme, c’est-à-dire soncontexte d’exécution.

Ainsi, l’analyse globale n’approximera pas les types concrets des entités typables dans les templatesen général mais approximera le type concret des entités typable pour chaque template dans un contexted’exécution vivant. A chaque entité typable vue dans un template est un contexte particulier, on associedonc un noeud du réseauC.

Définition 9 On appellecontour de template, terme emprunté à[Shivers, 1991] , une fonction entre lesentités typables de ce template (variable pour les templates de méthodes et attributs pour les templates declasses) et les noeuds du réseauC. On noteContour l’ensemble des contours de templates.

Définition 10 On appelleidentifiant de contour, notéTk, un templateT ∈ Template vu dans un contexteparticulier d’exécution, indiqué park. On appelleclé de contourl’information sur un contexte particulierd’exécution. On noteKey l’ensemble des clés de contour de templates etContourId l’ensemble desidentifiants.

Définition 11 On appelleAssoc la fonction qui associe un contour à son identifiant :

Assoc : ContourId −→ ContourTk 7−→ Assoc(Tk) : Entity −→ X

v 7−→ Assoc(Tk)(v)

39

40 CHAPITRE 5. ANALYSE GLOBALE

at

isBigger

bar2 bar2

k

l

k

l

Méthode "bar"

ret

v1

p3p2p1

k

k

k

ll

l

Définie dans "Foo"

Figure 5.1 – 2 contours de clésk et l pour la fonctionbar de l’exemple 4.4

RemarqueComme une entité typable est contenue dans un seul template, on définit la notationvk

comme :

vk = Assoc(Tk)(v) | T est le template dev

La différence principale entre les algorithmes d’analyse de types repose sur la définition des contexteset des contours.

Par la suite on confondra la notion de contour avec son identifiant.Remarquepar abus on dit qu’un contour est une duplication d’un template, or il n’en est rien. C’est

juste que, dans presque tous les algorithmes, le sous-réseau deC restreint aux noeuds de chaque contourd’un templateressembleau template lui-même.

5.1.1 Contour de méthodes

Un contour de méthode est une méthode vue sous un contexte d’exécution particulier. Comme nous lesavons, certaines techniques d’analyse, dites polyvariantes, travaillent sur des contours de méthodes afind’isoler les analyses propres à chaque contexte.

En particulier, les noeudsV du graphe d’appelsG = (V,E) sont des contours de méthodes.

Définition 12 On appellegraphe d’appelsrestreint, le grapheG = (V ,E) défini de la façon suivante :

V = {m | mk ∈ V }E = {(m,m′) | (mk,m′

k′) ∈ E}

On noteKeyM l’ensemble des clés de contour de méthodes etMethodK l’ensemble des identifiantsde contours de méthodes.

5.2. RÉSEAU DE TYPE CONCRETS 41

5.1.2 Contour de classes

De la même manière, un contour de classe est une classe vue sous un contexte d’instanciation etd’exécution particulier. La seule technique courante qui utilise des contours de classes estk-l-CFA (sec-tion 2.4.5).

Ainsi, pour généraliser, au lieu de manipuler des classes, nous allons manipuler des contours de classespour avoir une plus grande précision, car en différenciant les classes on différencie également leurs attributs.

Le type concret de chaque entité typable sera donc approximé, non pas par un ensemble de classesmais par un ensemble de contours de classes. C’est pourquoi, par abus, nous appelleronstypeun contourde classe.

Pour revenir aux types concrets originaux (c’est-à-dire aux ensemble de classes), On noteτ la restrictionaux classes de l’ensemble de contours de classesτ définie ainsi :

τ = {c | ck ∈ τ}

On noteKeyC l’ensemble des clés de contour de classes etClassK l’ensemble des identifiants decontours de classes.

5.2 Réseau de type concrets

Définition 13 Un noeud du réseaux ∈ X est une variable du réseauC. Chaque noeud représente unensemble de contours de classe, la fonctionτ associant un noeud à son ensemble de contour de classes.

τ : X −→ P(ClassK)x 7−→ τ(x)

Définition 14 Un arc de dépendanced ∈ D est un couple de deux noeuds(x, y) ∈ X2 indiquant unedépendance entre le noeudx et le noeudy, c’est-à-dire queτ(y) dépend deτ(x) ou qu’une partie deτ(x)a circulé le long de l’arc pour se retrouver dansτ(y).

RemarqueCette dépendance peut être très complexe. C’est pourquoi pour simplifier le système derègles nous ne chercherons pas à calculer cet ensemble. Il est néanmoins possible d’ajouter un arc dèsqu’un ensemble de contours de classes d’un noeud est utilisé pour définir celui d’un autre.

Définition 15 On appelle ensemble de contours de classes vivants approximé par l’analyse globaleg, notéCVg, l’ensemble défini par :

CVg =⋃

x∈Xg

τg(x)

On noteT ∗g l’ensemble des contours approximés vivants d’une template par l’analyse globaleg :

T ∗g = {T ′

k ∈ (Vg ∪ CVg) | T ′ = T}

Définition 16 On appelle type concret approximé d’une variablev par l’analyse globaleg, noté [v]g,l’ensemble défini ainsi :

[v]g =⋃

Tk∈{T∗g |T template dev}

Assocg(Tk)(v)

5.3 Formalisme

5.3.1 Les domaines utilisés

Les données utilisées par l’analyse globale sont construites en regroupant les données des analyseslocales. Les domaines définis dans la figure 5.3 s’articulent de la façon suivante :

set, map et tuple sont des domaines génériques qui permettent de construire respectivement desensembles, des fonctions et des vecteurs.


Class : L’ensemble des templates de classe de l’analyse locale.Method : L’ensemble des templates de méthodes de l’analyse locale.Template = Class ∪Method : L’ensemble des templates de l’analyse locale.Entity : L’ensemble des entités typables.KeyC : L’ensemble des clés de classes.KeyM : L’ensemble des clés de méthodes.Key = KeyC ∪KeyM : L’ensemble des clés.ClassK = Class×KeyC : L’ensemble des identifiants de contours de classes.MethodK = Method×KeyM : L’ensemble des identifiants de contours de méthodes.ContourId = ClassK ∪MethodK : L’ensemble des identifiants de contours.X ; L’ensemble des noeuds.Contour = Entity → X : L’ensemble des contours.

Figure 5.2 – Ensembles utilisés

– set[T] est un ensemble deT, il possède tous les opérateurs ensemblistes (∈,⊂, etc.) ;– map[T1,T2] est une fonction (une association d’un domaine vers un autre), il permet de récupérer

l’élément associé grâce à la constructiona(b) → T2 (avec a : map[T1,T2], b : T1) ;– tuple[T] est une spécialisation demap[integer,T], c’est-à-dire une fonction qui associe un

élément à un indice, il possède également une méthodelen qui retourne l’indice du dernier élément(soit le nombre d’éléments).

5.4 Les règles

Le but du système de règles de la figure 5.6 est de fournir une généralisation de la plupart des algo-rithmes.

Ainsi, une analyse globaleg va utiliser ces règles pour définir :– Vg : L’ensemble des contours de méthodes vivants,– Eg : L’ensemble des appels entre ces contours de méthodes,– Xg : L’ensemble des noeuds du réseau de flux de types,– τg : La fonction qui associe à un noeud son ensemble des types,– Assocg : La fonction qui associe à un contour une fonction d’association.

5.4.1 Démarrage

Le démarrage du programme est défini par un template de classeMain et un template de méthodemain de signature sans type de basemain(Main) . On considère que la première méthode appelée estcette méthodemain avec un receveur de typeMain .

Comme nous travaillons sur des contours de classes et des contours de méthode, il nous faut unepremière clef, nous noterons∅ cette clef de base.

La première règle (RootRule) caractérise le démarrage du programme en indiquant d’une part que lecontour de base de la méthodemain est vivant et d’autre part que le receveur de ce contour de méthodeest le contour de base de la classeMain .

Les règles suivantes vont analyser chaque commande des méthodes vivantes, c’est pourquoi elles com-mencent par la prémisse :

mk ∈ V

qui permet de sélectionner un contour de méthode vivantemk, puis continuent par la prémisse

e ∈ m.c

5.4. LES RÈGLES 43

Method{in : tuple[Var], ret : Var, var : set[Var], link : set[Link], coer : set[Coer], call :set[Call], new : set[New], read : set[Read], write : set[Write]} < Template : Un template deméthode.Class{attr : map[AttrName,Attr], attrs : map[AttrName,Class],meth : map[MethName,Method]} < Template : Une classe.

Static : Un type statique.StaticClass{class : Class} < Static : Un type statique connu (non ancré).StaticSelf < Static : Un type ancré sur self.StaticLike{name : AttrName} < Static : Un type ancré sur un attribut de self.

Command{var : Var} : Une commande d’une méthode.Link{from : Var} < Command : Une commande de lien.Coer{static : Static} < Link : Une commande de lien.SendCall{name : MethName, arg : tuple[Var]} < Command : Une commande d’appel deméthode.Send{class : Class} < Call : Une commande d’appel dynamique de méthode.Call{class : Class} < Call : Une commande d’appel statique de méthode.New{static : Static} < Command : Une commande d’instanciation.AAttr{name : AttrName, from : Var} < Command : Une commande d’accès d’attribut.Read < AAttr : Une commande de lecture d’attribut.Write < AAttr : Une commande d’écriture d’attribut.

Figure 5.3 – Précision des informations supplémentaires

Res(mk : MethodK, e : SendCall) → Method : Détermine les méthodes appelées par un site d’appele statique ou dynamique à partir d’un contour de méthodemk. Cette fonction est définie suivant les caspar :

Res(mk : MethodK, e : Send) → Method ={

c.meth(e.name) | c ∈ τ(e.p1k)}

Res(mk : MethodK, e : Call) → Method = {e.class.meth.get(e.name)}

Sta(s : Static, C : set[Class) → Class : Résout le type statiques d’un type ancré tout en sachant queself est de type restreint aux classC. Cette fonction est définie suivant les cas par :Sta(s : StaticClass, C : set[Class]) → set[Class] = {s.class}Sta(s : StaticSelf , C : set[Class]) → set[Class] = CSta(s : StaticLike, C : set[Class]) → set[Class] = {c.attrs(s.name) | c ∈ C}Pour des raisons pratiques on construit une autre version deSta qui va chercher directement le receveur àpartir d’un contour de méthode :

Sta(s : Static,mk : MethodK) = Sta(s, τ(m.in(1)k)

)φ(K : set[ClassK], C : set[Class]) → set[ClassK] = {ck ∈ K | c ∈ C}

Figure 5.4 – Fonctions utiles

Method Key Selection :MKS(MethodK, tuple[set[ClassK]],SendCall) → set[KeyM]Class Key Selection :CKS(MethodK,New) → set[KeyC]Parameter Filter :PF(KeyM, integer, set[ClassK]) → set[ClassK]

Figure 5.5 – Fonctions spécifiques


où c représente une catégorie de commandes particulière dans notre méthode sélectionnée.

5.4.2 Appels de méthodes

La seconde règle (CallRule) et la plus complexe est celle traitant des appels de méthodes. Cette règlecumule toutes les difficultés puisqu’il faut :

– déterminer les méthodes cibles,– déterminer les clés de contours,– mettre à jour le graphe d’appels,– relier la valeur de retour,– relier les paramètres.

C’est la fonctionRes définie dans la figure 5.4 qui sert à déterminer les méthodes cibles. Si l’appelest un appel dynamique les méthodes cibles sont donc dépendantes du type concret du receveur restreintaux classes, sinon si l’appel est statique (comme un appel àsuper par exemple), alors la classe cible estconnue et c’est dans celle-là que sera recherché le sélecteur.

Déterminer les clés de contours de méthode cibles à associer aux méthodes cibles est spécifique àchacune des techniques. C’est réalisé par la fonctionMKS définie dans la figure 5.5. On peut utiliser lachaîne d’appels (k-CFA), les types concrets des paramètres (méthode de Hash) ou fournir un contourunique (CFA). Le seule chose à remarquer est que cette clé ne dépend que de l’appelant et en aucun cas desméthodes cibles ou du moyen d’accès (statique ou dynamique).

Par exemple, un appel àsuper dans une technique de customisation (une clé par receveur potentiel)construira donc un template de la méthode antérieure spécifique à chaque type de receveur.

Ensuite, pour une méthode ciblem′ et une clé ciblek′, on va ajouter le contourm′k′ dans le graphe

d’appels, c’est le rôle des conclusions :

m′k′ ∈ V et (mk,m′

k′) ∈ E

On va également ajouter un arc entre le noeud de la variable de retour et le noeud associé à la commanded’appel, c’est le rôle de la conclusion :

τ(m′.retk′) ⊆ τ(e.vark)

Le dernier point, et le plus ardu, est celui du passage des paramètres. Il y a une difficulté majeure,dépendante de la technique utilisée, qui est le filtrage des paramètres en fonction du contour.

Par exemple dans une technique de customisation, le receveur est monomorphe. Ainsi si l’appel d’uneméthode de sélecteurn sur un type concret restreint aux classes{A,B} ne cible qu’une seule méthodem.On utilisera deux contours dem, un de receveurA et un de receveurB mais il faut s’assurer que seulAarrive au receveur du contour dem pourA et que seulB arrive au receveur du contour dem pourB. Cefiltrage est assuré par la fonctionPF de la figure 5.5.

Une autre mise en oeuvre de ce filtrage est la suppression de Nil dans le receveur. En effet, on considèrepar souci de simplicité que c’est àPF de s’en charger.

Tout ceci se fait en traitant chaque paramètre avec :

{PF(k′, n, τ(e.arg(n)k)) ⊆ τ(m′.in(n)k′)}n∈[1..e.arg.len]

RemarquePar définition, une méthode accessible est vivante. Ainsi c’est cette règle qui permet dedéfinir les contours vivants de méthodesV et par restriction les méthodes vivantes.

5.5. APPLICATION DES RÈGLES À QUELQUES TECHNIQUES 45

5.4.3 Instanciation

La troisième règle (NewRule) est très importante car c’est celle qui rend vivant des contours de classeet les introduit dans les types concrets afin qu’ils circulent.

Pour obtenir un contour de classe, il nous faut une classe. L’ensemble des classes instanciables nous estfourni par la prémisse :

Sta (e.static, mk)

La fonctionSta définie dans la figure 5.4 a pour but de résoudre un type statique en fonction du typeconcret de self restreint aux classes (c’est-à-dire du premier paramètre).

Il nous faut aussi une clé, dépendante de la technique utilisée. A vrai dire, la seule technique courantequi fait des contours de classes estk-l-CFA. On utilise pour cela la fonctionCKS de la figure 5.5.

RemarquePar définition, une classe instanciée est vivante. Ainsi c’est cette règle qui permet indirec-tement de définir les classes vivantesCV car elle est la seule règle qui introduit de nouveaux contours declasses et donc, par restriction de nouvelles classes.

5.4.4 Lien et coercition

La quatrième règle (LinkRule) est la plus simple. Elle permet de considérer qu’un type concret estinclus dans un autre. Mais une version plus évoluée existe, il s’agit de la coercition (CoerRule) où lafonction de filtreφ, de la figure 5.4, intervient pour filtrer sur le bon type.

Lors de la coercition, on ne fait passer qu’une partie des types : ceux qui satisfont le type statique,c’est-à-dire qui sont sous-type d’une des classes résolues.

En effet, avec les types ancrés il est possible de représenter plusieurs classes. Imaginons une méthodem, possédant une coercition surself , définie dans une classeA. Donnons-nous deux classes supplémen-tairesB etC, toutes deux sous-classes deA.

Maintenant appelonsm avec un receveur associé à un type concret restreint aux classes{B,C}. Notrecoercition ne devra donc laisser passer que les classes sous-classes deB ou sous-classes deC.

Il y a une erreur potentielle si certains types ne satisfont pas toutes les classes résolues. En effet, àl’exécution rien ne garantit que c’est telle ou telle classe qui servira de filtre.

Par contre, si tous les types sont sous-types de toutes les classe résolues, cela signifie qu’il n’y aura pasd’erreur de types. A l’opposé, l’erreur systématique est déclenchée si aucun type ne satisfait aucune desclasses résolues. Mais comme les types concrets n’ont pas fini d’être approximés, on doit attendre avant dedéclarer quoique ce soit.

5.4.5 Attributs

Pour un accès à un attribut il nous faut un receveur. Et c’est ce receveur qui détermine, en fonctionde son type concret, quels attributs dans quels contours de classes entrent en action. C’est d’ailleurs à cetendroit que servent les contours de classes.

Une fois les attributs et contours connus, la lecture d’un attribut (ReadRule) est très simple, c’est l’écri-ture d’attribut qui est plus ardue car il faut tester les types, covariance oblige. Ce test se fait comme pour lacoercition, grâce àφ, la différence importante est que le type statique est déjà résolu.

RemarqueCe sont ces deux règles qui introduisent la notion d’attribut vivant. Ici, un attribut est vivantpar contour de classe et de deux façons : il peut être vivant par lecture ou par écriture. Le fait qu’un attributsoit vivant par écriture peut se voir par le fait qu’il possède un arc entrant et un attribut vivant par lecturese remarquer car il possède un arc sortant.

5.5 Application des règles à quelques techniques

Les techniques spécifiques vont d’une part définir leur propre notion de contour, donc de clé et d’autrepart leur version spécifique des fonctionsMKS, CKS etPF.


main∅ ∈ V Main∅ ∈ τ(main.in(1)∅)[RootRule]

mk ∈ V e ∈ m.call m′ ∈ Res(mk, e) k′ ∈ MKS(mk, e)m′

k′ ∈ V (mk,m′k′) ∈ E τ(m′.retk′) ⊆ τ(e.vark)

{PF(k′, n, τ(e.arg(n)k)) ⊆ τ(m′.in(n)k′)}n∈[1..e.arg.len]

[CallRule]

mk ∈ V e ∈ m.new c ∈ Sta(e.static, mk) k′ ∈ CKS(k, e)ck′ ∈ τ(e.vark)

[NewRule]

mk ∈ V e ∈ m.link

τ(e.fromk) ⊆ τ(e.vark)[LinkRule]

mk ∈ V e ∈ m.coer

φ(τ(e.fromk), Sta(e.static, mk)) ⊆ τ(e.vark)[CoerRule]

mk ∈ V e ∈ m.read ck′ ∈ τ(e.fromk)τ(c.attr(e.name)k′) ⊆ τ(e.vark)

[ReadRule]

mk ∈ V e ∈ m.write ck′ ∈ τ(e.fromk)φ(τ(e.vark), {c.attrs(e.name)}) ⊆ τ(c.attr(e.name)k′)

[WriteRule]

Figure 5.6 – Règles de l’algorithme général

Du point de vue de la complexité, on peut s’intéresser au nombre de contoursK définis au pire par latechnique. On noteram le nombre de templates de méthodes,c le nombre de templates de classes,e lenombre de commandes (instanciations, appels de méthodes,etc.) eta l’arité des méthodes. Le nombre decontours étant borné par les clés possibles :km pour le nombre maximal de clés de méthode etkc pourle nombre maximal de clés de classes. On aura alors un nombre de contours de méthode enO(kmm), unnombre de contours de classes enO(kcc) soit un nombre total de contours en :

K = O(kmm + kcc)

5.5.1 Algorithme de base : 0-CFA

0-CFA, voir section 2.4.3 (p. 6), est l’algorithme de base, il ne fait pas de distinction entre les contextesd’exécution, c’est-à-dire entre les contours.

La définition des clés de contour est alors simple puisque :

KeyM = KeyC = {∅}

Ce qui nous amène à poserkm = kc = 1 soitK = O(m + c).On utilise les fonctions spécifiques suivantes :

MKS(MethodK, tuple[set[ClassK]],SendCall) → set[KeyM] = {∅}CKS(MethodK,New) → set[KeyC] = {∅}

PF(KeyM, i : integer,K : set[ClassK]) → set[ClassK] =

{K \ {Nil}, si i = 1 ;

K, si i > 1.

On considère donc ces définitions commepar défaut, ainsi, pour les autres techniques, on ne préciserapas les choses si elles ne diffèrent pas de celles présentées ici.

5.5.2 Algorithmes polyvariants

Les algorithmes polyvariants, voir section 2.4.5 (p. 8), créent plusieurs contours par template. Lescontextes d’exécutions dépendent de la chaîne d’appels, c’est pourquoi les clés sont définies de la façon

5.5. APPLICATION DES RÈGLES À QUELQUES TECHNIQUES 47

suivante :KeyM = KeyC = tuple[Command]

De plus, on définitFk une fonction de manipulation des tuples qui empile des éléments de façon bor-née1.

Fk(x : T, < y1, y2, . . . , yn >: tuple[T]) → tuple[T] =

{< x, y1, y2, . . . , yn >, si n < k ;

< x, y1, y2, . . . , yk >, sinon.

k-l-CFA, pourk et l fixé, donne donc :

MKS(mc : MethodK, p : tuple[set[ClassK]], e : SendCall) = {Fk(e, c)}CKS(mc : MethodK, e : New) = {Fl(e, c)}

Ce qui nous amène à poserkm = ek etkc = el soitK = O(mek + cel).Remarquek-CFA correspond àk-0-CFA, ce qui revient à avoirCKS avec le comportement de base. De

plus, aveck = 0 on obtient bien 0-CFA, c’est-à-dire avecMKS etCKS qui retournent∅.

5.5.3 Algorithmes adaptatifs

Les algorithmes adaptatifs, voir section 2.4.6 (p. 10), ne passent pas leurs contextes sur la chaîne d’ap-pels mais sur les types des paramètres.

5.5.3.1 0-CFA + Customisation

Dans la customisation appliquée à 0-CFA, voir section 2.4.7 (p. 11), le contexte est défini comme letype du receveur.

KeyM = ClassK ∪ {∅} KeyC = {∅}

Ce qui nous amène à poserkc = 1 etkm = mkcc = mc soitK = O(mc).

MKS(mk : MethodK, p : tuple[set[ClassK]], e : SendCall) = p(1)− {Nil}

PF(k : KeyM, i : integer,Kset[ClassK]) → set[ClassK] =

{{k}, si i = 1 ;

K, si i > 1.

5.5.3.2 CPA

Dans CPA, voir section 2.4.9 (p. 11), chaque paramètre est monomorphe, le contexte d’une méthodeétant le tuple des types de ses paramètres.

KeyM = tuple[ClassK] KeyC = {∅}

MKS(mk : MethodK, p : tuple[set[ClassK]], e : SendCall) = CP (p)PF(k : KeyM, i : integer,Kset[ClassK]) → set[ClassK] = {k.get(i)}

où CP (tuple[set[T ]]) → set[tuple[T ]] est le produit cartésien (qui au passage élimine Nil dans lereceveur).

Ce qui nous amène à poserkc = 1 etkm = (kcc)a = ca soitK = O(cam).

1Remarque, On note∅ ou<> le tuple vide, c’est-à-dire avec zéro élément.


5.5.3.3 SCS

Avec SCS, voir section 2.4.10 (p. 12), le contour est défini comme l’ensemble des paramètres.

KeyM = tuple[set[ClassK]] KeyC = {∅}

Ce qui nous amène à poserkc = 1 etkm = 2ca soitK = O(2cam).On a donc :

MKS(mk : MethodK, p : tuple[set[ClassK]], e : SendCall) = p

5.5.4 Proposition d’une nouvelle technique

CPA est, jusqu’à présent, considérée comme la meilleure technique d’analyse dans le sens de la préci-sion. Malheureusement elle ne tient pas compte de contours de classes, c’est pourquoi nous pouvons définirune technique qui considère :

KeyM = tuple[set[ClassK]] KeyC = (New ×KeyM) ∪ {∅}

avec :

MKS(mk : MethodK, p : tuple[set[ClassK]], e : Call) = CP (p)PF(k : KeyM, i : integer,Kset[ClassK]) → set[ClassK] = {k.get(i)}

CKS(mk : MethodK, e : New) = {(e, k)}

Malheureusement cette technique possède un problème de récursivité : les contextes de création declasses dépendent des contextes des méthodes et les contextes des méthodes dépendent des contextes declasses.

Exemple Prenons la méthodem(a : A) { m(new A) } et un contexte de cette méthode(m, (A, ∅)).L’instanciation va créer un nouveau contexte deA soit (A, (m, (A, ∅))).L’appel va créer un nouveau contexte pourm : (m, (A, (m, (A, ∅))))Et ainsi de suite. . . .

Pour casser cette récursivité, la solution serait de perdre en précision en ignorant le contexte d’uneclasse passée en paramètre d’une méthodem quand celui-ci contient la méthodem.

Ainsi, pour une méthodem, les contextes de classe(A, (m, (A, ∅))) et (A(m, (A, (m, (A, ∅))))) se-raient les mêmes car ils contiennentm.

5.6 Approximation de 0-CFA par l’unification

Certaines techniques, afin d’être plus efficacesunifient les noeuds, c’est-à-dire considèrent que plu-sieurs entités typables partagent le même noeud, voir la section 2.4.11 (p. 12).

Cette unification peut être faite statiquement, dite aussia priori, comme c’est le cas dans RTA, XTA oules autres techniques définies en particulier dans[Tip et Palsberg, 2000]. La figure 5.7 décrit les règles sup-plémentaires dépendantes de ces techniques d’unification statiques (sachant que les fonctions spécifiquessont celles de CFA).

Autrement les autres techniques se basent sur une unification dynamique, en particulier en fonction dunombre de dépendancesentre deux noeuds, comme expliqué dans[DeFouwet al., 1998].

5.6.1 Filtrage dans les approximations

Dans les analyses proposées ici, le type concret[e] d’une expressione est successivement approximésuivant le niveau de l’analyse.

5.7. PRÉCISION DES ANALYSES GLOBALES 49

mk ∈ V v1 ∈ m.var v2 ∈ m.var

v1k = v2k

[XTA]

mk ∈ V v1 ∈ m.var v2 ∈ m.var

v1k = v2k

[FTA1]

ck ∈ CV a1 ∈ c.attr a2 ∈ c.attr

a1k = a2k

[FTA2]

c ∈ Class m1 ∈ c.meth m2 ∈ c.meth v1 ∈ m1.var v2 ∈ m2.var

v1k = v2k

[MTA]

c ∈ Class m1 ∈ c.meth m2 ∈ c.meth v1 ∈ m1.var v2 ∈ m2.var

v1k = v2k

[CTA1]

ck ∈ V a1 ∈ c.attr a2 ∈ c.attr

a1k = a2k

[CTA2]

x ∈ X y ∈ X

x = y[RTA]

Figure 5.7 – Règles d’unification de noeuds des algorithmes sous 0-CFA

Le premier niveau de l’analyse consiste à ne regarder que le type statique et à en déduire que le typeconcret est inclus dans les sous-classes du type statique :[e]s = sub(τs(e)).

Le second niveau, consiste à analyser localement une méthode et à en déduire un type concret plusprécis :[e]l = sub(τ(Repl(e))).

Le troisième niveau est l’analyse globale qui effectue les calculs de flux et qui approxime encore unpeu mieux le type concret[e]g = [Repl(e)]g.

Si notre analyse se fait à chaque niveau sans perte d’information, on a forcément[e] ⊆ [e]g ⊆ [e]l ⊆ [e]scomme le montre la première partie de la figure 5.8.

Or, avec l’unification on a une perte d’information car le type concret de plusieurs expressions serapartagé.

Pour atténuer cette perte d’information, la solution est de filtrer par les informations des niveauxprécédents :[e] ⊆ [e]s ∪ [e]l ∪ [e]g comme le montre la seconde partie de la figure 5.8.

Dans l’analyse globale, on dispose de templates. Pour les templates de classe, le filtre est facile puisquele type de chaque attribut est donné.

Pour les templates de méthodes, il est possible de calculer le type local de chaque entité typable dutemplate. A défaut on peut filtrer par le type statique.

RemarqueQuand il s’agit d’unification statique interne à une méthode ou aux attributs d’une classe,comme dans XTA, l’analyse locale peut unifier les entités typables plutôt que de laisser à l’analyse globalele soin d’unifier les noeuds. Mais le prix à payer peut être important car il n’est plus possible de rattraperglobalement la perte de précision faite localement.

5.7 Précision des analyses globales

Pour comparer deux techniques d’analyse globale on ne peut pas se baser sur les contours à moinsde trouver un moyen de comparer les notions de contours utilisées dans chaque analyse. En effet chaqueanalyse a sa propre définition des contours. Si l’on veut comparer des analyses ils nous faut revenir auxtemplates qui sont les données de départ.

La première comparaison possible est sur le graphe d’appels. Or les analyses globales construisent


[e]

[e]g

[e]l

[e]s

[e]

[e]

[e] [e]g

l

s

Analyse sans perte d’informationApproximation avec unifications

Figure 5.8 – Imbrication des niveaux d’analyse

un graphe d’appels où les noeuds sont des contours, on ne peut donc pas les comparer. Pour revenir auxtemplates, on doit comparer le graphe d’appels restreint aux méthodesG = (V , E) comme défini dans lasection 5.1.1.

Définition 17 Une analyse globaleg est plus précise qu’une analyseg′ au niveau du graphe d’appels,notég′ ≤G g si :

Vg ⊆ Vg′ et Eg ⊆ Eg′

La deuxième comparaison possible est sur les types concrets des entités typables, de même, il faut nousintéresser aux types concrets restreint des entités typables.

Définition 18 Une analyse globaleg est plus précise qu’une analyseg′ au niveau des types concrets, notéeg′ ≤C g si :

∀v ∈ Entity [v]g ⊆ [v]g′

Comme nos analyse globales sont des approximations complètes de l’analyse exacte, notéee on a :

∀g analyse globale complète g ≤G e etg ≤C e

5.8 Détection du code mort et vivant

La notion de code vivant s’applique à trois choses distinctes : les méthodes, les classes et les attributs.Ici la notion est étendue aux contours. Ainsi la règle [CallRule] détermine les contours de méthodes vi-vants, la règle [NewRule] détermine les contours de classes vivants et les règles [ReadRule] et [WriteRule]déterminent les attributs vivants pour un contour de classe donnée.

Par restriction on peut passer des contours au templates : une méthode (resp. une classe) est vivante s’ilexiste au moins un contour vivant de cette méthode (resp. de cette classe).

Le cas des attributs est plus compliqué car un attribut est vivant en lecture s’il est accédé en lecturedans un contour de sa classe et il est vivant en écriture s’il est accédé en écriture dans un contour de saclasse. Un attribut est pleinement vivant s’il est vivant en lecture et en écriture.

L’utilisation principale du code mort et vivant est simple pour les méthodes et les classes mortes, puis-qu’il est inutile de les inclure dans l’exécutable final. Dans le cas des méthodes, cela signifie ne pas inclure

5.8. DÉTECTION DU CODE MORT ET VIVANT 51

le code et dans le cas des classes cela veut dire qu’elles peuvent être considérées comme abstraites. Cetteoptimisation aura pour effet d’avoir un exécutable plus petit et une plus faible utilisation de la mémoirestatique lors de l’exécution du programme.

Le cas des attributs vivants seulement en lecture ou en écriture est plus difficile à gérer. En effet, il seraittentant de remplacer les accès des attributs vivants uniquement en lecture par une constante et de supprimerles accès des attributs vivants uniquement en écriture, mais si ces lectures et écritures sont polymorphes leproblème devient plus ardu.

Les attributs pleinement morts peuvent également être supprimés avec précaution car, par exemple, unattribut mort dans une classe peut être vivant dans une sous-classe. Dans ce cas, une solution serait dedéplacer la définition de l’attribut.

Mais la suppression effective d’attributs peut avoir un impact important sur la mémoire dynamique carles octets gagnés par une telle optimisation seront multiplié par le nombre d’instances.

Le dernier point à souligner est l’utilisation potentielle de l’information fournie par les contours, c’est-à-dire les contextes d’exécution.

Par exemple, pour plusieurs contours vivants d’une méthode, il serait opportun de se demander s’ilserait efficace de ne pas fournir qu’une seule version compilée de la méthode, mais plutôt d’avoir uncertain nombre de versions de la méthode adaptées et optimisées pour chaque utilisation.

Dans le même ordre d’idée, il serait intéressant de savoir s’il est possible d’optimiser les classes enfonction de leur utilisation2. L’exemple type serait une classe de 100 attributs qui sont tous vivants dans uneseule instance (c’est-à-dire un seul contour) mais où un seul attribut est vivant pour 1000 autres instances.

Cette utilisation des contextes d’exécution est forcément dépendante des définitions des contours etpourrait donc être un critère de comparaison supplémentaire entre les différentes analyses globales propo-sées.

2Class hierarchy specialisationde[Tip et Sweeney, 2000].

Chapitre 6

Conclusion

Ce travail s’inscrit dans le cadre des recherches menées autour de l’utilisation de techniques globalesd’implémentation et d’optimisation en compilation séparée. De ce fait, il est axé sur deux particularités :

– la première particularité est la définition d’une analyse de types sur deux niveaux. Un premier niveaude traitement local à une classe ou à une méthode et un second niveau de traitement global appliquéau regroupement des résultats locaux sur un programme entier. Ce découpage n’influe pas sur laprécision du graphe d’appels calculé ou sur la détection des erreurs de types, les analyses séparéespouvant être aussi précises que des analyses globales. De plus la détection des erreurs de types estplus précise qu’une analyse statique séparée mais également plus précise que la règle des catcallsd’Eiffel [Meyer, 1997], c’est-à-dire l’interdiction du polymorphisme pour les méthodes dont les pa-ramètres sont redéfinis de manière covariante ou dont la protection est restreinte1. En effet, la règledes catcalls nécessite une analyse du niveau de CHA.Ce travail se démarque donc des études précédentes qui se contentaient d’une technique globale,occultant le traitement local du code. Car peu nombreux sont ceux qui se sont penchés sur les trai-tements locaux.[Diwan et al., 1996] ont posé une séparation entre l’analyse intra-procédurale etinter-procédurale mais chacune devant être exécutée alternativement jusqu’à obtenir une stabilité.D’un autre coté[Agesen, 1995b] travaille sur des templates mais ne se pose pas la question de leurstraitements locaux potentiels.

– La seconde particularité est la définition de schémas généraux pour regrouper la plupart des analysesglobales connues. Ce travail se rapproche ainsi de celui de[Grove et Chambers, 2001] mais diffèred’une part par les propriétés du langage cible, comme le traitement des fermetures mais pas celuides types ancrés par exemple, et d’autre part par un effort constant de rester relativement simple etcohérent dans le modèle.

La seule limitation d’effectuer ces analyses de façon séparée concerne l’utilisation de leurs résultatspour optimiser localement le code compilé : en effet la compilation s’effectue avant l’analyse globale.Une solution serait de compiler plusieurs versions en fonction des optimisations potentielles, l’édition delien choisissant la plus adaptée après coup[Myers, 1995]. Une autre solution peut venir des compilationset éditions de liens successives sachant qu’une nouvelle compilation peut être optimisée en utilisant lesinformations de l’analyse globale précédente pour, par exemple, intégrer des appels directs ou customiserles méthodes au cas par cas, en fonction du type concret du receveur.

L’utilisation d’une analyse séparée apporte des avantages dans le développement d’un programme, enpermettant une analyse incrémentale. En effet, une analyse de types rapide est essentielle pour certainesapplications, par exemple pour un environnement de développement. On peut sensiblement augmenter lesperformances en n’ayant pas à tout ré-analyser à chaque petite modification. Ici ré-analyser les types d’unprogramme légèrement modifié peut être rapide car la majorité des templates existent et ne sont pas affectéspar les modifications. Il suffit alors de se poser la question de l’utilisation incrémentale des techniques

1Notre étude ne s’intéresse pas à la protection des propriétés des classes.

53

54 CHAPITRE 6. CONCLUSION

globales, sujet qui est généralement débattu dans les travaux de leurs auteurs respectifs.Un autre avantage est la réutilisabilité des composants, les templates calculés pour une bibliothèque

sont entièrement réutilisables pour toutes les applications. Une question intéressante est de savoir s’ilest possible de pré-mâcher encore plus le travail de l’analyse globale avec une analyse intermédiaire quise concentre sur une sous-division des programmes comme les bibliothèques, modules et autres paquetages.

L’étape suivante dans ce travail est l’implémentation et la comparaison des différentes techniques, aussibien locales que globales, de façon individuelle mais aussi en mesurant l’impact de leurs combinaisons.L’objectif final est l’application de ces techniques àSmallEiffel, the GNU Eiffel Compilerdisponible enopen source2. S’y intégreraient également d’autres techniques globales mais adaptées pour de la compi-lation séparée comme la coloration de[Ducournau, 2001a] ou comme la spécialisation de hiérarchies declasses de[Tip et Sweeney, 2000].

2SmallEiffel, ses bibliothèques et son code source sont en effet téléchargeables depuishttp://SmallEiffel.loria.fr

http://SmallEiffel.loria.fr

Bibliographie

[Agesenet al., 1993] Ole Agesen, Jens Palsberg, et Michael I. Schwartzbach. Type inference of SELF :Analysis of objects with dynamic and multiple inheritance.Lecture Notes in Computer Science,707 :247–267, 1993.

[Agesen, 1994] Ole Agesen. Constraint-based type inference and parametric polymorphism. InFirstInternational Static Analysis Symposium, pages 78–100, 1994.

[Agesen, 1995a] Ole Agesen. The cartesian product algorithm - simple and precise type inference ofparametric polymorphism. InProc. ECOOP’95, éditeur W. Olthoff, LNCS 952, pages 2–26. Springer-Verlag, 1995.

[Agesen, 1995b] Ole Agesen.Concrete Type Inference : Delivering Object-Oriented Applications. PhDthesis, Stanford University, 1995.

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

[Aho et Ullman, 1977] Alfred V. Aho et Jeffrey D. Ullman. Principles of Compiler Design. AddisonWesley, 1977.

[Baconet al., 1996] David F. Bacon, M. Wegman, et K. Zadeck. Rapid type analysis for C++. Rapporttechnique, IBM Thomas J. Watson Research Center, 1996.

[Bacon et Sweeney, 1996] D.F. Bacon et P. Sweeney. Fast static analysis of C++ virtual function calls. InProc. OOPSLA’96, SIGPLAN Notices, 31(10), pages 324–341. ACM Press, 1996.

[Bacon, 1997] David F. Bacon. Fast and effective optimization of statically typed object-oriented lan-guages. PhD thesis, University of California, Berkeley, 1997.

[Calder et Grunwald, 1994] Brad Calder et Dirk Grunwald. Reducing indirect function call overhead inC++ programs. InConference Record of the Twenty-First ACM Symposium on Principles of Program-ming Languages, pages 397–408, 1994.

[Chamberset al., 1989] Craig Chambers, David Ungar, et Elgin Lee. An efficient implementation ofSELF, a dynamically-typed object-oriented languages based on prototypes. InProc. OOPSLA’89, pages49–70, New Orleans, 1989. ACM Press.

[Collin et al., 1997] S. Collin, D. Colnet, et O. Zendra. Type inference for late binding. the SmallEiffelcompiler. InJoint Modular Languages Conference, LNCS 1204, pages 67–81. Springer Verlag, 1997.

[Deanet al., 1995] Jeffrey Dean, David Grove, et Craig Chambers. Optimization of object-oriented pro-grams using static class hierarchy analysis. InProc. ECOOP’95, éditeur W. Olthoff, LNCS 952, pages77–101. Springer-Verlag, 1995.

[Dean et Chambers, 1994] Jeffrey Dean et Craig Chambers. Optimization of object-oriented programsusing static class hierarchy analysis. Rapport Technique 94-12-01, University of Washington, Seattle,1994.

[DeFouwet al., 1998] Greg DeFouw, David Grove, et Craig Chambers. Fast interprocedural class analysis.In Symposium on Principles of Programming Languages, pages 222–236, 1998.

[Dicky et al., 1996] H. Dicky, C. Dony, M. Huchard, et T. Libourel. On automatic class insertion withoverloading. InProc. OOPSLA’96, SIGPLAN Notices, 31(10), pages 251–267. ACM Press, 1996.

55

56 BIBLIOGRAPHIE

[Diwanet al., 1996] Amer Diwan, J. Eliot B. Moss, et Kathryn S. McKinley. Simple and effective analysisof statically typed object-oriented programs. InProc. OOPSLA’96, SIGPLAN Notices, 31(10), pages292–305. ACM Press, 1996.

[Driesen, 1999] K. Driesen. Software and Hardware Techniques for Efficient Polymorphic Calls. Phdthesis in computer science, University of California, Santa Barbara, 1999.

[Ducournau, 1997] Roland Ducournau. La compilation séparée de l’envoi de message dans les langagesdynamiques.L’Objet, 3(3) :241–276, 1997.

[Ducournau, 2001a] Roland Ducournau. La coloration : une technique pour l’implémentation des langagesà objets à typage statique. i. la coloration de classes. Rapport Technique 01-225, L.I.R.M.M., 2001.

[Ducournau, 2001b] Roland Ducournau. La compilation séparée de l’envoi de message dans les langagesstatiques. Rapport Technique 01-014, L.I.R.M.M., 2001.

[Ducournau, 2001c] Roland Ducournau. Spécialisation et sous-typage : thème et variations. RapportTechnique 01-013, L.I.R.M.M., 2001.

[Gil et Itai, 1998] J. Gil et A. Itai. The complexity of type analysis of object oriented programs. InProc.ECOOP’98, LNCS 1445, pages 601–634. Springer-Verlag, 1998.

[Godinet al., 1998] R. Godin, H. Mili, G. Mineau, R. Missaoui, M. Arfi, et T-T Chau. Design of classhierachies based on concept (galois) lattices.Theory and Practice of Object Systems, 4(2) :117–134,1998.

[Groveet al., 1997] David Grove, Greg DeFouw, Jeffrey Dean, et Craig Chambers. Call graph construc-tion in object-oriented languages. InProc. OOPSLA’97, SIGPLAN Notices, 32(10), pages 108–124.ACM Press, 1997.

[Grove et Chambers, 2001] David Grove et Craig Chambers. A framework for call graph constructionalgorithms. ACM Transactions on Programming Languages and Systems (TOPLAS), 23(6) :685–746,2001.

[Grove, 1995] David Grove. The impact of interprocedural class inference on optimization. InCAS-CON’95 Centre for Advanced Studies Conference, pages 195–203, 1995.

[Heintze, 1994] Nevin Heintze. Set-based analysis of ml programs. InACM Conference on LISP andFunctional Programming, pages 306–317, 1994.

[Henglein, 1991] Fritz Henglein. Efficient type inference for higher-order binding-time analysis. InFunc-tional Programming Languages and Computer Architecture, Cambridge, Massachusetts (Lecture Notesin Computer Science, vol. 523), éditeur J. Hughes, pages 448–472. Berlin : Springer-Verlag, 1991.

[Meyer, 1997] B. Meyer.Object-Oriented Software Construction, 2nd. edition. Prentice-Hall, 1997.

[Milner, 1978] Robin Milner. A theory of type polymorphism in programming.Journal of Computer andSystem Sciences, 17(3) :348–375, 1978.

[Myers, 1995] A. Myers. Bidirectional object layout for separate compilation. InProc. OOPSLA’95, pages124–139. ACM Press, 1995.

[Oxhojet al., 1992] Nicholas Oxhoj, Jens Palsberg, et Michael I. Schwartzbach. Making type inferencepractical. InProc. ECOOP’92, éditeur O. L. Madsen, LNCS 615, pages 329–349. Springer-Verlag,1992.

[Palsberg et Schwartzbach, 1991] Jens Palsberg et Michael I. Schwartzbach. Object-oriented type infe-rence. InProc. OOPSLA’91, SIGPLAN Notices, 26(10), pages 77–101. ACM Press, 1991.

[Palsberg et Schwartzbach, 1994] Jens Palsberg et Michael I. Schwartzbach.Object-Oriented Type Sys-tems. John Wiley & Sons, 1994.

[Palsberg, 2001] Jens Palsberg. Type-based analysis and applications. InPASTE’01 Workshop on ProgramAnalysis for Software Tools and Engineering, 2001.

[Phillips et Shepard, 1994] G. Phillips et T. Shepard. Static typing without explicit types. Rapport tech-nique, Dept. of Electrical and Computer Engineering, Royal Military College of Canada, Kingston,Ontario, Canada, 1994.

BIBLIOGRAPHIE 57

[Plevyak et Chien, 1994] John Plevyak et Andrew A. Chien. Precise concrete type inference for object-oriented languages. InProc. OOPSLA’94, SIGPLAN Notices, 29(10), pages 324–340. ACM Press,1994.

[Plevyak et Chien, 1995] John Plevyak et Andrew A. Chien. Iterative flow analysis, 1995.

[Ryder, 1979] Barbara Ryder. Constructing the call graph of a program.IEEE Transaction on SoftwareEngineering, 5(3) :216–225, 1979.

[Shivers, 1988] Olin Shivers. Control-flow analysis in scheme. InProceedings of the SIGPLAN ’88 Confe-rence on Programming Language Design and Implementation, pages 164–174, 1988.

[Shivers, 1991] Olin Shivers. Control-Flow Analysis of Higher-Order Languages. PhD thesis, CarnegieMellon University, 1991.

[Srivastava, 1992] Amitabh Srivastava. Unreachable procedures in object-oriented programming.ACMLetters on Programming Languages and Systems, 1(4) :355–364, 1992.

[Steensgaard, 1996] Bjarne Steensgaard. Points-to analysis in almost linear time. InSymposium on Prin-ciples of Programming Languages, pages 32–41, 1996.

[Tip et Palsberg, 2000] Frank Tip et Jens Palsberg. Scalable propagation-based call graph constructionalgorithms. InProc. OOPSLA’00, SIGPLAN Notices, 35(10), pages 281–293. ACM Press, 2000.

[Tip et Sweeney, 2000] Frank Tip et Peter F. Sweeney. Class hierarchy specialization.Acta Informatica,36(12) :927–982, 2000.

[Vitek et al., 1992] Jan Vitek, R. Nigel Horspool, et James S. Uhl. Compile time analysis of object-oriented programs. InProceedings of the Fourth International Conference on Compiler Construction,pages 237–250, 1992.

[Zendraet al., 1997] Olivier Zendra, Dominique Colnet, et Suzanne Collin. Efficient dynamic dispatchwithout virtual function tables : The SmallEiffel compiler. InProc. OOPSLA’97, SIGPLAN Notices,32(10), pages 125–141. ACM Press, 1997.

Annexe A

Résumé des techniques

Le tableau A.1 récapitule les principales techniques vues dans le chapitre 4. On y indique :– la précision, c’est-à-dire la capacité de permettre à l’analyse globale d’approximer les types concrets

efficacement,– la taille des templates, c’est-à-dire la quantité d’entités typables et de commandes générées,– et la vitesse, c’est-à-dire la difficulté relative de la technique, cette donnée étant une conjecture.

Nom Section Précision Taille des templates VitesseBasique 4.2.1 (p. 27) moyenne grande rapideSimplification précise 4.4.1 (p. 29) moyenne moyenne assez rapideSimplification minimale précise 4.4.2 (p. 30) moyenne petite lentInterface minimale précise 4.5.2 (p. 33) moyennea très petite lentUnification totale 4.5 (p. 33) très faible très petite très rapide+ Gestion des variables 4.6 (p. 34) plus précise plus grande plus lente+ Customisation 4.7 (p. 36) plus précise plus petiteb faible impact

aMais plus de retour au code.bPlus petite seulement si on fait des optimisations derrière. Le tout au prix de plus de templates générés.

TAB . A.1 – Récapitulatif des principales analyses locales

Le tableau A.2 récapitule les principales techniques vues dans le chapitre 5. On y indique la précisionet la vitesse, ces informations étant pour la plupart déduites des statistiques et des benchmarks de[Agesen,1995b; Grove et Chambers, 2001].

Nom Sections Précision Nombre de contoursa Vitesse moyenneRTA 2.2.3 (p. 4) très faible 1 très rapide0-CFA 2.4.3 (p. 6) faible O(m + c) rapide1-CFA 2.4.5 (p. 8) assez faible O(m2 + c) assez lentk-CFA 2.4.5 (p. 8) bonne O(mk+1 + c) très lentk-l-CFA 2.4.5 (p. 8) très bonne O(mek + cel) très lentCustomisation 2.4.6 (p. 10) bonne O(cm) assez rapideCPA 2.4.9 (p. 11) très bonne O(cam) lentSCS 2.4.10 (p. 12) très bonne O(2cam) lentApproximations 2.4.11 (p. 12) faible O(m+c)b rapide

aAvecm pour le nombre de templates de méthodes,c pour le nombre de templates de classes,e pour le nombre de commandes eta pour l’arité des méthodes.

bMais les noeuds dans les contours s’unifient.

TAB . A.2 – Récapitulatif des principales analyses globales

59

Résumé : Une grande quantité de travaux a déjà été menée sur les problèmes de la construction de graphed’appels et de l’analyse de types pour les langages orientés objets. La majorité des travaux précédents sefocalise sur la définition algorithmique d’une nouvelle technique et sur la preuve de sa validité et/ou sur lavérification empirique de son efficacité.

Notre contribution est de formaliser la décomposition en deux parties de ces analyses, l’une ne s’inté-ressant qu’à une vision locale ou intra-procédurale du programme (méthodes, classes) et l’autre, globaleou inter-procédurale, s’intéressant aux organisations et dépendances entre ces visions locales. Ces deuxparties étant articulées par une notion unique, résultat pour l’analyse locale et donnée pour l’analyse glo-bale. Le schéma d’analyse résultant est donc applicable en compilation séparée. De plus, la formalisationest suffisamment générale pour intégrer la plupart des techniques d’analyse de types et de construction degraphe d’appels connues.

Ce travail est un préalable à une implémentation de techniques globales d’analyses et d’optimisationsdans un cadre de compilation séparée, en visant en particulier des langages à typage statique comme Eiffel.

Mots clés : analyse de types, graphe d’appels, type concret, polymorphisme, langages orientés objet,détection de code mort.

Abstract: A large body of prior work has investigated the problem of call graph construction and typeanalysis for object-oriented languages. The majority of prior work has focused on algorithm definition ofa new technique and on the proof of its correctness and/or on its empirical efficiency.

Our contribution is to formalize the distinction between two parts of these analysis, the one for a localor intra-procedural vision of a program (methods, classes) and the other, global or inter-procedural, for theorganization between these local visions. Both parts are articulated by a unique notion, output of the localanalysis and input of the global analysis. This work presents also a general framework for many globaltechniques.

The aim of this work is to integrate some global optimization techniques in separate compilation, espe-cially for statically typed languages like Eiffel.

Keywords: type analysis, call graph, concrete type, polymorphism, object-oriented languages, dead codedetection.

Documents

Compilation de langage à objets Analyse de types et graphe ...privat/publications/Privat...Chapitre 2 Déﬁnitions et état de l’art 2.1 Graphes d’appels Déﬁnition 1 Un sous-programmeest