Analyses de flot ================ Analyse de flot de données: pour chaque instruction I, on cherche à calculer la valeur d'une grandeur juste avant F(I) et juste après F'(I) l'exécution de I. F(I) et F'(I) sont généralement des ensembles (de pseudoregistres, ...) F et F' respectent la structure du graphe de flot, c.à.d. F(B) = F'(A) si A est l'unique prédecesseur de B et plus généralement F(B) = JOIN { F'(A) | A -> B est un arc du graphe de flot } (1) ou bien F'(A) = JOIN { F(B) | A -> B est un arc du graphe de flot } (2) (1) correspond à une analyse en avant: on part de l'état avant I et on cherche l'état après I. Le cas de base est l'état F(START) au point d'entrée START dans la fonction (le seul point sans prédécesseur) (2) correspond à une analyse en arrière: on part de l'état après I et on cherche l'état avant I. Le cas de base est l'état F'(I) aux instructions I qui n'ont pas de successeur (p.ex. les instructions "return" et "raise"). JOIN est soit union soit intersection suivant le type de problème. Premier exemple: détermination des pseudo-registres vivants. ------------------------------------------------------------ V(A) = pseudoregistres vivants à travers l'instruction A F(A) = pseudoregistres vivants juste avant A F'(A) = pseudoregistres vivants juste après A Si A est (r'1, ..., r'N) <- op(r1, ..., rM): V(A) = F'(A) \ {r'1 ... r'N} F(A) = V(A) union {r1 ... rM} C'est une analyse arrière, avec JOIN = union. En particulier, si A est return(r1...rM), on a: F'(A) = union de l'ensemble vide (pas de successeurs) = 0 V(A) = 0 F(A) = {r1...rM} Exemple: /*A*/ j = 1; /*B*/ if (i = 0) { /*C*/ k = 1; } else { /*D*/ k = j + 1; } /*E*/ return k F'(E) = 0 V(E) = 0 F(E) = {k} F'(C) = F(E) = {k} V(C) = 0 F(C) = 0 F'(D) = F(E) = {k} V(D) = 0 F(D) = {j} F'(B) = F(C) U F(D) = {j} V(B) = {j} F(B) = {i,j} F'(A) = F(B) = {i,j} V(A) = {i} F(A) = {i} Tant qu'on n'a pas de boucles, la résolution est immédiate. Les boucles introduisent de véritables équations. Exemple: /*A*/ i = 0; /*B*/ while (i < N) { /*C*/ i = i + 1; } Les équations entre B et C sont: F(C) = F'(C) union {i} F'(B) = F(C) F(B) = F'(B) union {i} F'(C) = F(B) Résolution itérative: plus petit point fixe d'un opérateur croissant. -------------------------------------------------------------------- On part de F(A) = F'(A) = 0 pour tout A. répéter changé = 0 pour chaque instruction A: F'(A) <- UNION { F(B) | A -> B arc du graphe de flot } ancien V(A) <- V(A) V(A) <- F'(A) \ {r1 ... rN} F(A) <- V(A) union {r'1 ... r'N} si V(A) <> ancien V(A), changé = 1 fin tant que changé Soit Ni le nombre de noeuds du graphe de flot et Nr le nombre de pseudo-registres. À chaque itération, au moins un V(A) augmente d'un élément. Il y a Ni V(A) différents, et card(V(A)) <= Nr. On fait donc au plus Ni * Nr itérations. Chaque itération fait Ni calculs ensemblistes de complexité O(Nr). Enfin, Nr = O(Ni). L'algorithme est donc en O(Ni^4). (Pour ce problème particulier, on peut montrer que on fait au plus Ni itérations, ce qui ramène la complexité en O(Ni^3), avec une constante assez petite car les opérations entre ensembles sont efficaces.) Formulation avec contrôle structuré: ------------------------------------ Si A est (r'1, ..., r'N) <- op(r1, ..., rM): F(A) = (F'(A) \ {r'1 ... r'N}) union {r1 ... rM} Si A = B ; C F'(C) = F'(A) F'(B) = F(C) F(A) = F(B) Si A = if (cond(r1,...rN)) then B1 else B2: F'(B1) = F'(B2) = F'(A) F(A) = (F(B1) union F(B2)) union {r1 ... rN} Si A = catch B with C: F'(B) = F'(C) = F'(A) pour tous les exit de B qui branchent vers C: F'(exit) = F(C) F(A) = F(B) Si A = loop B end: F'(B) = F(B) F(A) = F(B) Tout ça donne un algorithme récursif (étant donné F'(A) en entrée, on sait calculer F(A) en sortie), sauf le cas des boucles: F'(B) = F(B)... Résolution itérative: F'(B) <- 0 répéter ancien <- F'(B) F'(B) <- registres_vivants(F'(B)) tant que F'(B) <> ancien Problème: peut être exponentiel en l'imbrication des boucles Résolution structurée: On définit Def(A) = registres toujours définis par l'exécution de A et Use(A) = registres éventuellement utilisés par l'exécution de A par récurrence structurelle sur A: Si A est (r'1, ..., r'N) <- op(r1, ..., rM): Def(A) = {r'1 ... r'N} Use(A) = {r1 ... rM} Si A = B; C: Def(A) = Def(B) union Def(C) Use(A) = Use(B) union [Use(C) \ Def(B)] Si A = if (cond(r1,...rN)) then B1 else B2: Def(A) = Def(B1) inter Def(B2) Use(A) = Use(B1) union Use(B2) union {r1...rN} Si A = do B while (cond(r1, ..., rN)): Def(A) = Def(B) Use(A) = Use(B) union ({r1 ... rN} \ Def(B)) [Pour simplifier, on ne fait pas le cas général loop...end + catch...exit, mais juste le cas des boucles do ... while. Les définitions de F et F' pour A = do B while (cond(r1, ..., rN)) sont: F'(B) = F'(A) union {r1...rN} union F(B) F(A) = F(B) ] On montre par récurrence structurelle sur A que F(A) = (F'(A) \ Def(A)) union Use(A) pour tout A. Preuve: par cas sur A, tous les cas sont faciles sauf la boucle. Si A = do B while (cond(r1, ..., rN)): Par hyp.rec. on a F(B) = (F'(B) \ Def(B)) union Use(B). On reporte dans l'équation reliant F'(B) et F(B): F'(B) = F'(A) union {r1...rN} union (F'(B) \ Def(B)) union Use(B) de la forme X = C U (X \ D) avec C = F'(A) union {r1...rN} union Use(B) et D = Def(B) Le plus petit point fixe est X = C. Donc F'(B) = F'(A) union {r1...rN} union Use(B). Et F(A) = F(B) = (F'(B) \ Def(B)) union Use(B) = ((F'(A) union {r1...rN} union Use(B)) \ Def(B)) union Use(B) = (F'(A) \ Def(B)) union ({r1...rN} \ Def(B)) union Use(B) \ Def(B) union Use(B) = (F'(A) \ Def(B)) union ({r1...rN} \ Def(B)) union Use(B) = (F'(A) \ Def(A)) union Use(A) CQFD. Autre exemple: la propagation des constantes -------------------------------------------- Effectuer à la compilation les calculs dont les arguments sont tous constants (connus à la compilation), et remplacer ces calculs par un "move" du résultat dans le registre résultat. Exemple: i <- 4 i <- 4 j <- 2 devient j <- 2 k <- i+j k <- 6 Les résultats de l'analyse F(A) et F'(A) ne sont pas des ensembles de pseudoregistres, mais des fonctions d'état phi: des fonctions partielles des pseudoregistres dans les constantes (entières ou flottantes). phi(r) = c signifie que le pseudoregistre r est garanti de contenir la valeur c à ce point du programme. Dans tous les autres cas, phi(r) est indéfini. Il s'agit d'une analyse avant, et l'opérateur JOIN est l'intersection des graphes de fonctions. Autrement dit, la fonction phi = phi1 JOIN phi2 est définie par phi(r) = c si phi1(r) et phi2(r) sont tous deux définis et égaux à c et phi(r) indéfinie dans tous les autres cas. Pour A: (r'1, ..., r'N) <- op(r1, ..., rM), voici la relation entre F(A) et F'(A): * Si A est un chargement de constante r' <- c: prendre F'(A)(r') = c et F'(A)(r) = F(A)(r) pour tout r différent de r' (F'(A) est la même fonction que F(A) sauf que r' est envoyé sur c) * Si F(A)(r1) ... F(A)(rM) sont tous définis, et si le résultat de op ne dépend que de la valeur de ses arguments et ne provoque pas d'exceptions, alors: - calculer (c'1...c'N) = op(F(A)(r1) ... F(A)(rM)) - remplacer A par les instructions r'1 <- c'1 ... r'N <- c'N - prendre F'(A)(r'_i) = c'_i et F'(A)(r) = F(A)(r) pour tout r différent de r'1...r'N (la même fonction que F(A) sauf que r_i est envoyé sur c_i). * Dans tous les autres cas: - prendre F'(A) = F(A) \ {r'1...r'N} (la même fonction que F(A) sauf qu'elle est indéfinie sur r'1...r'N). Remarque: le calcul à la compilation de op(F(A)(r1) ... F(A)(rM)) n'est pas possible dans un certain nombre de cas: - op est un accès mémoire (le résultat dépend de l'état de la mémoire) - op peut déclencher une exception, p.ex. une division par zéro - op est une opération flottante inexacte (le mode d'arrondi peut être modifié par le programme) Le point de départ de l'analyse est F(START) = 0 (tous registres inconnus initialement). Exemple: pi <- 3.14 i <- 0 x < 0.0 do t <- 4.0 t <- pi / t x <- x + t i <- i + 1 while (i < n) return x Analyses inter-fonctions ------------------------ Exemple: allocation de registres inter-fonctions. A: (r1, ..., rN) <- call "f" (r'1, ..., r'M) Par défaut: on fait interférer V(A) avec tous les registres caller-save. Autre possibilité: garder trace des registres effectivement utilisés par f, R(f), et faire interférer V(A) avec R(f) seulement. Si R(f) n'est pas connu au moment de la compilation de A, on peut toujours prendre R(f) = tous les registres physiques. On essaye de compiler f avant g si g appelle f. Pour ce faire, on construit une approximation du graphe d'appel: noeuds = fonctions arc f -> g si f appelle g On alloue les registres en suivant un parcours en profondeur d'abord de ce graphe. En cas de récursion, ce graphe peut contenir des cycles, et dans ce cas on commence par une des fonctions quelconques du cycle (en ne connaissant rien sur les autres fonctions du cycle). Problème: tout ceci suppose que le graphe d'appel est déterminable statiquement. P.ex. si tous les appels sont à des fonctions nommées. Mais si les fonctions sont des valeurs de première classe? On a des appels "inconnus" de la forme A: (r1, ..., rN) <- call (r', r'1, ..., r'M) où l'adresse de la fonction appelée est calculée dans r'. Solution simple: faire interférer V(A) avec tous les registres physiques. Solution plus fine: essayer de déterminer les fonctions vers lesquelles r' peut pointer par une analyse. C'est une analyse de flot de donnée qui détermine en même temps le flot de contrôle. La 0CFA ------- (0-th order Control Flow Analysis) Choix: 1- à quel niveau on l'effectue 2- quelle approximation des valeurs On va l'effectuer sur les termes obtenus après expansion du filtrage: il s'agit donc d'un lambda-calcul classique. On suppose chaque fonction étiquetée par un nom unique: f: fun x -> e On note param(f) = x et corps(f) = e. On suppose toutes les variables nommées de manière unique. (Pas de variable liée plusieurs fois dans le programme.) On choisit les approximations suivantes a ::= bottom (rien de connu) | top (jamais évaluée) | {f1, f2, ...} (l'adresse d'une fonction parmi celles de l'ensemble) | (a1, ..., aN) (un tuple) La réunion de deux approximations est { f1, f2, ...} JOIN { f3, f4, ...} = {f1, f2, f3, f4, ...} (a1, ..., aN) JOIN (b1, ..., bN) = (a1 JOIN b1, ..., aN JOIN bN) top JOIN a = a JOIN top = a Dans tous les autres cas: a JOIN b = bottom On va construire itérativement deux fonctions d'approximation: rho: variable -> approximation des valeurs de la variable res: nom de fonction -> approximation des résultats de la fonction L'approximation d'une expression A(e) se calcule comme suit: A(x) = rho(x) A(f : fun x -> e) = {f} A((e1, ..., eN)) = (A_rho(e1), ..., A_rho(eN)) A(field_i(e)) = si A(e) = (a1, ..., a_n) avec i <= n alors a_i sinon bottom A(e1; e2) = calculer A(e1) puis renvoyer A(e2) A(let x = e1 in e2) = faire rho(x) <- JOIN(rho(x), A(e1)) puis renvoyer A(e2) A(if e1 then e2 else e3) = calculer A(e1) puis renvoyer JOIN(A(e2), A(e3)) A(e1 e2) = si A(e1) = {f1, ..., fN} alors JOIN { APPLY(fi, A(e1)) | i=1..N } sinon calculer A(e2) et renvoyer bottom dans tous les autres cas: A(e) = bottom, mais calculer A(e1) ... A(eN) pour tous les sous-termes e1...eN de e APPLY(f, a) = soit x = params(f) faire rho(x) <- JOIN(rho(x), a) et renvoyer res(f) L'algorithme d'approximation est: initialement rho(x) = top et res(f) = top répéter calculer A(programme) pour chaque fonction f, res(f) <- JOIN(res(f), A(corps(f))) tant que rho ou res a changé On calcule ensuite une approximation du graphe d'appel comme suit: pour toute application e1 e2 dans corps(f), si A(e1) = {f1, ..., fk} alors ajouter les arcs f -> f1 ... f -> fk si A(e1) = bottom alors ajouter des arcs de f vers toutes les autres fonctions du programme Exemple: let f = f: fun x -> ... in let g = g: fun y -> ... in let map = map: fun fn -> map2: fun l -> ... fn x ... in let id = id: fun z -> z in ... map (id f) l1 ... map (id g) l2 ... Premier tour: rho(z) = {f, g} puis res(id) = {f, g} Deuxième tour: rho(fn) = {f, g} D'où le graphe d'appel: main appelle map et id map appelle f et g Complexité: O(N^3).