**** éléments de correction td11/12-LT-RICM2 Gen Code.**** ****Laurent Mounier et Laure Gonnord **** Exercice 1 ---------- #### Programme A On doit générer le code d'une séquence d'instructions, donc on va faire des appels concaténés Code-prog = GenCodeInst(x1:=3) GenCodeInst(x2:=3+x1+x2) GenCodeInst(si e alors c1 sinon c2) avec e=..., c1= ..., c2= GenCodeInst(x2:=0) avec GenCodeInst(x1:=3) = soit (C,i)=GencodeAexp(3) = (Add R1 R0 3, 1) et k = 4 (depl de x1) dans C||ST R1 [FP-4] donc GenCodeInst(x1:=3) = ADD R1 R0 3 ST R1 [FP-4] Ensuite : GenCodeInst(x2:=3+x1+x2)= soit (C,i)=GenCodeAexp(3+x1+x2) (R2<-calcul) et k = 8 (depl de x2) dans C|| ST R2 [FP-8] Avec GenCode Aexp(3+x1+x2) = 2 appels au code de add ... laissé au lecteur Ensuite : GenCodeInstr(si e alors c1 sinon c2) = création des nouvelles étiquettes : lsuiv=1, lvrai=2, lfaux=3 dans GenCodeBexp(non(x2=x1), 2, 3) 1: GenCodeInstr(c1) 2: GenCodeInstr(c2) 3: avec pour les instructions, aucun problème, et pour l'expression booléenne: GenCodeBexp(non(x2=x1),2,3)=GenCodeBexp(x2=x1,3,2) <-- règle du ``non'' LD R4 [FP-8] -- chargement de la valeur de x2 LD R5 [FP-4] CMP R4 R5 BEQ 3 -- si égal, aller en 3 BA 2 -- sinon, aller en 2 Le reste est laissé au lecteur. #### Programme B : GenCodeInstr(x2:=0) <-- pas de souci GenCodeInstr(tant que e c) avec e=x3, c= ... soient les étiquettes ldebut = 1,lvrai = 2, lfaux = 3 dans 1: GenCodeBexp(x3,2,3) <-- pas trop difficile 2: GenCodeInstr(x3:=non x3 et ...) BA 1 3: Le reste est laissé au lecteur. Exercice 2 ---------- #### ou exclusif C'est une expression booléenne, donc il faut écrire: GenCodeBexp(e1 xor e2,lvrai, lfaux)= e1 et e2 sont des expressions booléennes, donc il leur faut aussi leur lvrai et lfaux. On s'appuie sur un exemple, x1 xor (x3 et x4), pour ne pas faire de bêtises : GenCodeBexp(e1 xor e2,lvrai, lfaux)= soient lvrai1=nouvelleEtiq() lfaux1 = nouvelleEtiq() dans GenCodeBexp(e1,lvrai1,lfaux1) lvrai1 : GenCodeBexp(e2,lfaux,lvrai) lfaux1 : GenCodeBexp(e2,lvrai,lfaux) Sauf que ça désymétrise l'expression ... et copie le code de e2... Une autre idée ? #### repéter c jusqua e : Gencode(repeter c jusqu'à e) = on effectue d'abord une itération de c, que l'on refait si on a (non e): = soit ldebut = nouvelle_etiq() et lfin = nouvelle_etiq() dans ldebut : GenCodeInst(c) GenCodeBExp(e,lfin, ldebut) <--- oui, oui, dans ce sens ! lfin : et voilà ! Exercice 3-pre ---------- - le pgm principal (x est a FP-4) - la procédure P (x est a une indirection sur LS) - la procédure R (idem) - la procédure Q (x est a 2 indirections sur LS) Exercice 3-de-la-feuille ---------- On n'écrit ici que le code généré : P : prologue (4) -- P a une variable locale entière. -- code de P empiler FP -- lien statique de P2 call P2 ADD SP SP +4 -- remettre la pile à la position avant l'appel -- epilogue où, pour empiler FP, on fait les deux instructions : ADD SP SP -4 ST FP [SP] P.R : prologue(0) -- pas de variable locale -- code de R calcul de x+2 -- @x=[FP+16] (premier par. après la case de res.) stockage à [FP+12] -- case de résultat -- epilogue P.P1 : prologue(0) -- code de P1 -- appel à la fonction q paramètre sur l'argument 4 empiler(4) -- mettre 4 dans un registre, puis empiler ce registre ADD SP SP -4 -- place pour le résultat empiler(LS(q)) -- il est à [FP+16] !! depilage ds le sens inverse call q -- stockage dans z du résultat LD r2 [SP] -- r2 := résultat LD r1 [FP+8] -- LS(P1) = FP de P ST r2 [r1-4] -- z:=resultat ADD SP SP +16 epilogue P.P2 prologue(0) empiler R -- LS et adresse empiler P1 -- LS uniquement call P1 ADD SP SP 16 epilogue Exercice 4 - code de toutes les procédures. ---------- Source : Fabienne Lagnier, modifié par LG novembre/déc 2005 -- Code du programme = prog prog: --prologue(4) -- corps = appel à P1 empiler (FP) -- ls de P1 call P1 add sp sp +4 -- pour récuper le SP initial --épilogue -- Code de la procedure P1 prog.P1: -- Prologue (taille 3*4) ADD sp, sp, -4 ST fp, [sp] -- empiler FP ADD fp, sp, 0 -- FP <-- SP ADD sp, sp, -taille -- reserver taille octets sur la pile ---- x1 := 11 SUB r0, r0, r0 -- r0 <-- 0 ADD r2, r0, 11 -- r2 <-- 11 -- acces a x1 : niveau courant=2, niveau de x1=1 -- ==> 1 indirection sur le LS pour acceder a x1 LD r1, [fp+8] -- r1 <-- LS(P1)=fp(prog) ST r2, [r1-4] ---- Q -- parametre : son environnement de definition LS(Q)=fp(P1) -- niveau courant=2, niveau de Q=2 -- ==> LS(Q)=env. courant=fp courant empiler (fp) CALL Q ADD sp, +4, sp ---- -- Epilogue ADD sp, sp, taille -- recuperer place var. locales ST fp, [sp] -- depiler FP ADD sp, sp, +4 -- retour RET -- Code de la procedure Q prog.P1.Q: Prologue (taille 4) ----y2 := 2; z2 := 3; z3 := x2 + y2 ; -- acces a z3 : fp-4 -- acces a y2 : niveau courant=3, niveau de y2=2 -- ==> 1 indirection sur LS LD r1, [fp+8] -- y2 en r1-8 ----si on avait eu un acces a x1 de niveau 1 ----==> 2 indirections sur LS : r<--LS(Q); r<--LS(P1); ----acces avec r-4 ----P2(z3, X) empiler z3 empiler adresse de X empiler LS(X) -- niveau courant=3, niveau de X=2 -- ==> 1 indirection sur LS = env(P1) empiler LS(P2) -- niveau de P2 = 2 ==> idem CALL P2 add sp, sp, +16 Epilogue RET -- Code de la procedure P2 prog.P1.P2: Prologue (taille 4) ----x2 :=1+a ; LD r2, [fp+20] -- acces au parametre a ADD r2, r2, 1 -- a+1 LD r1, [fp+8] --niveau courant=3, niveau x2=2 ==> 1ind. sur LS ST r2, [r1-4] -- x2:= ----P3(p); empiler les deux mots du parametre p -- ie @du code de p et LS(p) on les trouve en fp+16 et fp+12 empiler LS(P3) --niveau courant=3, niveau P3=3 --on empile fp courant qui est bien LS(P3) CALL P3 add sp, sp, +12 Epilogue RET --Code de la procedure P3 -- Prologue (taille 0) ADD sp, sp, -4 ST fp,[sp] -- sauvegarde FP ADD fp, sp, 0 -- mise en place FP courant -- x3 := p(x1) -- appel p(x1) avec x1 variable locale de p -- niveau courant=4, niveau x1=1 ==> 3 ind. sur LS LD r1, [fp+8] -- r1 = LS(P3) = fp(P2) LD r1, [r1+8] -- r1 = LS(P2) = fp(P1) LD r1, [r1+8] -- r1 = LS(P1) = fp(prog) LD r1, [r1-4] -- r1 = valeur de x1 empiler(r1) ADD sp, sp, -4 -- pour le resultat de p LD r1, [fp+12] -- LS(p) empiler(r1) LD r1, [fp+16] -- R1= adresse de p CALL r1 LD r1, [sp+4] -- R1=resultat de la fonction p -- acces a x3 : niveau courant=4, niveau x3=3 -- ==> 1 ind. sur LS LD r2, [fp+8] -- R2=LS(P3) ST r1, [r2-4] -- x3:= ADD sp, sp, +12 -- R2(x3,Y) -- x3 par adresse LD r1, [fp+8] ADD r1, r1, -4 empiler(r1) -- empiler adresse de x3 -- Y fonction en paramètre, on empile son adresse et son LS SET r1, Y empiler(r1) -- empiler adresse de Y LD r1, [fp+8] LD r1, [r1+8] empiler(r1) -- empiler LS(Y) empiler LS(R2) -- c'est le meme... CALL R2 ADD sp, sp, +12 --epilogue LD fp, [sp] -- recuperation de FP en sommet de pile ADD sp, sp, +4 -- Code de la procedure R3 prog.P1.R2.R3 -- Prologue (0) ADD sp, sp, -4 ST fp,[sp] -- sauvegarde FP ADD fp, sp, 0 -- mise en place FP courant -- y2:=2, 2 indirections pour y2. LD r1 [fp+8] -- r1<- LS(R3)=fp(R2) LD r1 [r1+8] -- r1<- LS(R2)=fp(P1) -- a ce stade y2 est à l'adresse r1-8 (2ième var.loc. de P1) ADD r2 r0 2 ST r2 [r1-8] -- y2:=2 -- x2:=y2+x1+b3 -- r1 contient toujours le fp de P1, où ''vivent''x2 et y2 LD r3 [r1-8] -- r1<-val(y2) -- chargement de x1 LD r4 [r1+8] -- un coup en plus LD r4 [r4-8] -- x1 est la seule var.locale de P. -- chargement de b3, paramètre de R2, donc à fp(r2)+12 LD r5 [fp+8] -- r5<-fp(R2) LD r5 [r5+12] -- et on ajoute tout ça ADD r3 r3 r4 ADD r3 r3 r5 --y3:=1+x2 ADD r6 r0 1 LD r7 [r1-4] -- r1 contient encore fp(P1) ADD r6,r6,r7 -- y3 var.locale de R2 LD r8 [fp+8] --r8<-LS(R2) ST r6 [r8-4] --y3:=contenu(r6) --b3:=p(x1) calcul de p(x1) dans le registre r9 -- idem que pour P3 LD r10 [fp+8] -- b3 en paramètre de R2 ST r19 [r10+12] --epilogue LD fp, [sp] -- recuperation de FP en sommet de pile ADD sp, sp, +4 ****