%=============================================================== %=============================================================== % Compilation d'expressions arithmetiques % Micro-Projet de Prolog % % Christophe GRENIER % Guillaume LETESSIER % Diane LEVY % Anne QUER %=============================================================== %=============================================================== %=============================================================== % Definition des fonctions de base %=============================================================== tete([X|_],X). suite([_|L],L). arg1(L,X):- suite(L,L2), tete(L2,X). arg2(L,X):- suite(L,L2), arg1(L2,X). concatene([],L,L). concatene([T|L1], L2, [T|L3]):- concatene(L1,L2,L3). %=============================================================== % Operations sur le contexte %=============================================================== affecte(Reg,Val,[],[Reg = Val]):-!. affecte(Reg,Val,[Reg=_|LReg],LReg2):- concatene([Reg = Val],LReg,LReg2),!. affecte(Reg,Val,[RegAffect|LReg],[RegAffect|LReg1]):- affecte(Reg,Val,LReg,LReg1). oublie(_,[],[]):-!. oublie(Reg,[Reg=_|LReg],LReg):-!. oublie(Reg,[RegAffect|LReg],[RegAffect|LReg2]):- oublie(Reg,LReg,LReg2). get_val_reg([Reg=Val|_],Reg,Val):-!. get_val_reg([_|LReg],Reg,Val):- get_val_reg(LReg,Reg,Val),!. ask_variable(LReg,LReg2,Variable,Val):- write('entrer la valeur de '), write(Variable), write(' '), read(Val), concatene(LReg,[Variable=Val],LReg2),!. %=============================================================== % Fonctions de test sur les expressions arithmetiques %=============================================================== meme_exp(Expr,Expr):-!. meme_exp(E1+E2,E1+E3):-meme_exp(E2,E3),!. meme_exp(E1+E2,E3+E1):-meme_exp(E2,E3),!. meme_exp(E2+E1,E3+E1):-meme_exp(E2,E3),!. %meme_exp(E1+E2,E3+E1+E4):-meme_exp(E2,E3+E4),!. meme_exp(E1*E2,E1*E3):-meme_exp(E2,E3),!. meme_exp(E2*E1,E3*E1):-meme_exp(E2,E3),!. meme_exp(E1*E2,E3*E1):-meme_exp(E2,E3),!. meme_exp(E1-E2,E1-E3):-meme_exp(E2,E3),!. meme_exp(E1/E2,E1/E3):-meme_exp(E2,E3),!. is_operation(+). is_operation(-). is_operation(*). is_operation(/). is_number(X):- number(X). is_number(Expr):- Expr=..Liste, tete(Liste,Operation), is_operation(Operation), arg1(Liste, Arg1), arg2(Liste, Arg2), is_number(Arg1), is_number(Arg2). %=============================================================== %=============================================================== % Version de base: % Compilation d'expressions arithmetiques %=============================================================== %=============================================================== compile([],[]):-!. compile([LAffect|SLAffect],LInst):- compile_affect(LAffect,LInst1,0), compile(SLAffect,LInst2), concatene(LInst1,LInst2,LInst). %=============================================================== % stv : Affectation %=============================================================== compile_affect(Var:=Expr,LInst,Reg):- compile2(Expr, SLInst, Reg), concatene(SLInst, [stv(Var,Reg)], LInst). %=============================================================== % Addition %=============================================================== compile2(Arg1 + 1,LInst,Reg):- compile2(Arg1, SLInst, Reg), concatene(SLInst, [inc(Reg)], LInst),!. compile2(1 + Arg2,LInst,Reg):- compile2(Arg2, SLInst, Reg), concatene(SLInst, [inc(Reg)], LInst),!. compile2(Arg1 + 2,LInst,Reg):- compile2(Arg1, SLInst, Reg), concatene(SLInst, [inc(Reg), inc(Reg)], LInst),!. compile2(2 + Arg2,LInst,Reg):- compile2(Arg2, SLInst, Reg), concatene(SLInst, [inc(Reg), inc(Reg)], LInst),!. compile2(Arg1 + 3,LInst,Reg):- compile2(Arg1, SLInst, Reg), concatene(SLInst, [inc(Reg), inc(Reg), inc(Reg)], LInst),!. compile2(3 + Arg2,LInst,Reg):- compile2(Arg2, SLInst, Reg), concatene(SLInst, [inc(Reg), inc(Reg), inc(Reg)],LInst),!. compile2(Expr1 + Expr2,LInst,Reg):- meme_exp(Expr1, Expr2), compile2(Expr1, LInst1, Reg), concatene(LInst1,[add(Reg,Reg)],LInst),!. compile2(Arg1 + Arg2,LInst,Reg1):- Reg2 is Reg1 + 1, compile2(Arg1, LInst1, Reg1), compile2(Arg2, LInst2, Reg2), concatene(LInst1,LInst2,LInst3), concatene(LInst3,[add(Reg1,Reg2)],LInst),!. %=============================================================== % Soustraction %=============================================================== compile2(Arg1 - 1,LInst,Reg1):- compile2(Arg1, LInst1, Reg1), concatene(LInst1,[dec(Reg1)],LInst),!. compile2(Arg1 - 2,LInst,Reg1):- compile2(Arg1, LInst1, Reg1), concatene(LInst1,[dec(Reg1),dec(Reg1)],LInst),!. compile2(Arg1 - 3,LInst,Reg1):- compile2(Arg1, LInst1, Reg1), concatene(LInst1,[dec(Reg1),dec(Reg1),dec(Reg1)],LInst),!. compile2(Arg1 - Arg2,LInst,Reg1):- Reg2 is Reg1+1, compile2(Arg1, LInst1, Reg1), compile2(Arg2, LInst2, Reg2), concatene(LInst1,LInst2,LInst3), concatene(LInst3,[sub(Reg1,Reg2)],LInst),!. %=============================================================== % Multiplication %=============================================================== compile2(2 * Expr,LInst,Reg):- compile2(Expr, LInst1, Reg), concatene(LInst1,[add(Reg,Reg)],LInst),!. compile2(Expr * 2,LInst,Reg):- compile2(Expr, LInst1, Reg), concatene(LInst1,[add(Reg,Reg)],LInst),!. compile2(4 * Expr,LInst,Reg):- compile2(Expr, LInst1, Reg), concatene(LInst1,[add(Reg,Reg), add(Reg,Reg)],LInst),!. compile2(Expr * 4,LInst,Reg):- compile2(Expr, LInst1, Reg), concatene(LInst1,[add(Reg,Reg), add(Reg,Reg)],LInst),!. compile2(Expr1 * Expr2,LInst,Reg):- meme_exp(Expr1, Expr2), compile2(Expr1, LInst1, Reg), concatene(LInst1,[mul(Reg,Reg)],LInst),!. compile2(Arg1 * Arg2,LInst,Reg1):- Reg2 is Reg1+1, compile2(Arg1, LInst1, Reg1), compile2(Arg2, LInst2, Reg2), concatene(LInst1,LInst2,LInst3), concatene(LInst3,[mul(Reg1,Reg2)],LInst),!. %=============================================================== % Divise Reg1 par Reg2 %=============================================================== compile2(Arg1 / Arg2,LInst,Reg1):- Reg2 is Reg1+1, compile2(Arg1, LInst1, Reg1), compile2(Arg2, LInst2, Reg2), concatene(LInst1,LInst2,LInst3), concatene(LInst3,[div(Reg1,Reg2)],LInst),!. %=============================================================== % ldc reg, cst %=============================================================== compile2(Tete,[ldc(Reg,Tete)],Reg):- number(Tete),!. %=============================================================== % ldv reg, var %=============================================================== compile2(Tete,[ldv(Reg,Tete)],Reg):-!. %=============================================================== %=============================================================== % OPTION 1: Lecture et affichage %=============================================================== %=============================================================== lire(LAffect):- write('entrer une affectation: '), read(Expr), lire_aux(Expr,LAffect). lire_aux(fin,[]):-!. lire_aux(Expr,[Expr|LAffect2]):- lire(LAffect2). %=============================================================== cout(ldc,2). cout(ldv,4). cout(stv,4). cout(inc,1). cout(dec,1). cout(add,2). cout(sub,2). cout(mul,3). cout(div,3). cout(move,1). get_cout(Expr,Cout):- Expr=..LExpr, tete(LExpr,Instr), cout(Instr,Cout). ecrire2([],CoutAcquis):- write('=> Cout total: '), write(CoutAcquis), nl,!. ecrire2([Expr|LInst],CoutAcquis):- get_cout(Expr,Cout), write(Expr), tab(5), write(Cout), nl, NewCoutTotal is CoutAcquis + Cout, ecrire2(LInst,NewCoutTotal). ecrire(LInst):- ecrire2(LInst,0). %=============================================================== %=============================================================== % OPTION 2: SIMPLIFICATIONS %=============================================================== %=============================================================== simplifie(LAffect,LAffect1):- simplifie_aux(LAffect, LAffect1, [], _). simplifie_aux([],[],LReg,LReg):-!. simplifie_aux([LAffect|SLAffect],LInst,LReg,LReg3):- simp_affect(LAffect,LInst1,LReg,LReg2), simplifie_aux(SLAffect,LInst2,LReg2,LReg3), concatene(LInst1,LInst2,LInst),!. simplifie_aux(L,L,LReg,LReg). %Propagation de calcul complet simp_affect(Var:=Expr,[Var:=Var2],LReg,LReg2):- simplifie2(Expr,LReg,Expr2), get_val_reg(LReg,Var2,Expr2), affecte(Var,Var2,LReg,LReg2),!. simp_affect(Var:=Var2,[],LReg,LReg):- get_val_reg(LReg,Var2,Var),!. simp_affect(Var:=Arg,[],LReg,LReg):- simplifie2(Arg, LReg, Var). simp_affect(Var:=Arg,[Var:=Val],LReg,LReg2):- simplifie2(Arg, LReg, Val), affecte(Var,Val,LReg,LReg2). %=============================================================== % Propagation de constantes %=============================================================== simplifie2(Reg,LReg,Val):- get_val_reg(LReg,Reg,Val), number(Val),!. %=============================================================== % Simplifications algebriques % x + 0 = 0 + x = x % x - 0 = x % x * 0 = 0 * x = 0 % x * 1 = 1 * x = x % x / 1 = x %=============================================================== simplifie2(Expr + 0,LReg,LInst):- simplifie2(Expr,LReg, LInst),!. simplifie2(0 + Expr, LReg, LInst):- simplifie2(Expr, LReg,LInst),!. simplifie2(Expr - 0, LReg, LInst):- simplifie2(Expr, LReg, LInst),!. simplifie2(_ * 0, LReg, LInst):- simplifie2(0, LReg, LInst),!. simplifie2(0 * _ , LReg, LInst):- simplifie2(0, LReg, LInst),!. simplifie2(Expr * 1, LReg, LInst):- simplifie2(Expr, LReg, LInst),!. simplifie2(1 * Expr, LReg, LInst):- simplifie2(Expr, LReg, LInst),!. simplifie2(Expr / 1, LReg, LInst):- simplifie2(Expr , LReg, LInst),!. %=============================================================== % Evaluation d'expressions constantes %=============================================================== simplifie2(Expr, LReg, LInst):- not number(Expr), is_number(Expr), Val is Expr, simplifie2(Val, LReg, LInst),!. simplifie2(Expr, LReg, LInst):- not number(Expr), meme_exp(Expr,A+B+C), number(B), simplifie2(B+A+C,LReg,LInst),!. simplifie2(Expr, LReg, LInst):- not number(Expr), meme_exp(Expr,A+B+C), number(C), simplifie2(C+A+B,LReg,LInst),!. % Permet une meilleur reutilisation des % registres contenant des variables %simplifie2(Expr1 + Expr2, LReg, LInst):- % number(Expr1), % not number(Expr2), % simplifie2(Expr2 + Expr1, LReg, LInst),!. %=============================================================== % Calcul symbolique % x - x = 0 % x / x = 1 %=============================================================== simplifie2(Expr1 - Expr2, LReg, LInst):- meme_exp(Expr1,Expr2), simplifie2(0, LReg, LInst),!. simplifie2(Expr1 / Expr2, LReg, LInst):- meme_exp(Expr1,Expr2), simplifie2(1, LReg, LInst),!. %=============================================================== % "Recursivite" %=============================================================== simplifie2(Expr, LReg, Inst):- Expr=..Liste, tete(Liste,Tete), is_operation(Tete), arg1(Liste,Arg1), arg2(Liste,Arg2), simplifie2(Arg1, LReg, Inst1), simplifie2(Arg2, LReg, Inst2), ((Inst1 \== Arg1);(Inst2 \== Arg2)), Simp2=..[Tete, Inst1, Inst2], simplifie2(Simp2, LReg, Inst),!. simplifie2(Expr,_,Expr):-!. %=============================================================== % Factorisation %=============================================================== factor(Expr,Res):- not number(Expr), meme_exp(Expr,A+B+C), number(B), factor(B+A+C,Res),!. factor(Expr, Res):- not number(Expr), meme_exp(Expr,A+B+C), number(C), factor(C+A+B,Res),!. factor(Expr,Res):- meme_exp(Expr,A*B+A*C), factor(A*(B+C),Res),!. factor(Expr,Res):- meme_exp(Expr,A*B-A*C), factor(A*(B-C),Res),!. factor(Expr,Res):- meme_exp(Expr,A/D+B/D), factor((A+B)/D,Res),!. factor(Expr,Res):- meme_exp(Expr,A/D+B/D), factor((A-B)/D,Res),!. factor(Expr,Res):- meme_exp(Expr,A*B+A), factor(A*(B+1),Res),!. factor(Expr,Res):- meme_exp(Expr,A*B-A), factor(A*(B-1),Res),!. factor(A1+A2,2*A1):- meme_exp(A1,A2),!. factor(A0+A1+A2,Res):- meme_exp(A1,A2), factor(A0+2*A1,Res),!. factor(Res,Res). %=============================================================== %=============================================================== % OPTION 3: % DETECTION ET OPTIMISATION DES SOUS-EXPRESSIONS COMMUNES %=============================================================== %=============================================================== optim(LInst,LInstOptim):- optim2(LInst, LInstOptim, [], _). optim2([],[],LReg,LReg):-!. optim2([Inst|SLInst],LInstOptim,LReg,LReg3):- optim3(Inst,InstOptim,LReg,LReg2), % write(Inst),write(LReg),write(LReg2),nl, optim2(SLInst,LInstOptim2,LReg2,LReg3), concatene(InstOptim,LInstOptim2,LInstOptim),!. optim3(stv(Var,Reg),[],LReg,LReg):- get_val_reg(LReg,Reg,Var),!. optim3(stv(Var,Reg), [stv(Var,Reg)], LReg, LReg2):- affecte(Reg,Var,LReg,LReg2),!. optim3(move(Reg,Reg),[],LReg,LReg):-!. optim3(ldv(Reg,Var), InstOptim,LReg,LReg2):- get_val_reg(LReg,Reg2,Var), optim3(move(Reg,Reg2),InstOptim,LReg,LReg2),!. optim3(ldv(Reg,Var), [ldv(Reg,Var)], LReg,LReg2):- affecte(Reg,Var,LReg,LReg2),!. optim3(ldc(Reg,Cst), InstOptim,LReg,LReg2):- get_val_reg(LReg,Reg2,Cst), optim3(move(Reg,Reg2),InstOptim,LReg,LReg2),!. optim3(ldc(Reg,Cst), [ldc(Reg,Cst)], LReg,LReg2):- affecte(Reg,Cst,LReg,LReg2),!. optim3(inc(Reg),[inc(Reg)],LReg,LReg2):- oublie(Reg,LReg,LReg2),!. optim3(Expr,[Expr],LReg,LReg2):- Expr=..[_,Reg,_], oublie(Reg,LReg,LReg2),!. %=============================================================== %=============================================================== % OPTION 4: EMULATEUR %=============================================================== %=============================================================== emule(ldc(Reg,Val),LReg,LReg2):- affecte(Reg,Val,LReg,LReg2),!. emule(ldv(Reg,Variable),LReg,LReg2):- get_val_reg(LReg,Variable,Val), affecte(Reg,Val,LReg,LReg2),!. emule(ldv(Reg,Variable),LReg,LReg2):- ask_variable(LReg,LReg1,Variable,Val), affecte(Reg,Val,LReg1,LReg2),!. emule(stv(Variable,Reg),LReg,LReg2):- get_val_reg(LReg,Reg,Val), affecte(Variable,Val,LReg,LReg2),!. emule(inc(Reg),LReg,LReg2):- get_val_reg(LReg,Reg,Val), NewVal is Val+1, affecte(Reg,NewVal,LReg, LReg2),!. emule(dec(Reg),LReg,LReg2):- get_val_reg(LReg,Reg,Val), NewVal is Val-1, affecte(Reg,NewVal,LReg, LReg2),!. emule(mul(Reg1,Reg2),LReg,LReg2):- get_val_reg(LReg,Reg1,Val1), get_val_reg(LReg,Reg2,Val2), NewVal is Val1*Val2, affecte(Reg1,NewVal,LReg, LReg2),!. emule(div(Reg1,Reg2),LReg,LReg2):- get_val_reg(LReg,Reg1,Val1), get_val_reg(LReg,Reg2,Val2), NewVal is Val1/Val2, affecte(Reg1,NewVal,LReg, LReg2),!. emule(sub(Reg1,Reg2),LReg,LReg2):- get_val_reg(LReg,Reg1,Val1), get_val_reg(LReg,Reg2,Val2), NewVal is Val1-Val2, affecte(Reg1,NewVal,LReg, LReg2),!. emule(add(Reg1,Reg2),LReg,LReg2):- get_val_reg(LReg,Reg1,Val1), get_val_reg(LReg,Reg2,Val2), NewVal is Val1+Val2, affecte(Reg1,NewVal,LReg, LReg2),!. aff(Var):- Var=..LReg, arg1(LReg,RegName), not number(RegName), write(Var), nl,!. aff(_). execute2([],[]):-!. execute2([],[Reg|SReg]):- aff(Reg), execute2([],SReg),!. execute2([Instr|LInstr],LReg):- emule(Instr,LReg,LReg2), execute2(LInstr,LReg2). execute(LInstr):- execute2(LInstr,[]). %=============================================================== %=============================================================== % Fonction principale %=============================================================== %=============================================================== go:- lire(LAffect), compile(LAffect,LInst), simplifie(LAffect, LAffect2), compile(LAffect2,LInst2), optim(LInst2,LInst3), write('Version de depart '), write(LAffect), nl, ecrire(LInst), nl, write('Version simplifiee '), write(LAffect2), nl, ecrire(LInst2), nl, write('Version simplifiee et optimisee'), nl, ecrire(LInst3), nl, write('Emulation de la version de base'), nl, execute(LInst). %=============================================================== %=============================================================== % Jeux d'essai %=============================================================== %=============================================================== test_affecte:- affecte(reg, val, [], [reg=val]), affecte(reg, val, [reg=val2], [reg=val]), affecte(reg, val, [reg2=val2], [reg2=val2, reg=val]), affecte(reg, val, [reg2=val2, reg=val3], [reg2=val2, reg=val]). test_oublie:- oublie(reg, [], []), oublie(reg, [reg=val], []), oublie(reg, [reg2=val], [reg2=val]), oublie(reg, [reg2=val2, reg=val], [reg2=val2]). test_get_val_reg:- not get_val_reg([], reg, _), get_val_reg([reg=val], reg, val), not get_val_reg([reg2=val2], reg, _), get_val_reg([reg2=val2, reg=val], reg, val). test_compile:- compile([y:=x*x-4*x+1,k:=y+k], [ldv(0, x), mul(0, 0), ldv(1, x), add(1, 1), add(1, 1), sub(0, 1), inc(0), stv(y, 0), ldv(0, y), ldv(1, k), add(0, 1), stv(k, 0)]). % evalutation d'expressions constantes % propagation de constante % division par 1 % multiplication par 0 % addition de 0 % multiplication par 1 % calcul symbolique test_simplifie:- simplifie([y:=2*3+1-12/2, z:=(y/1-1)*x+1*k+0], [y:=1, z:=k]), simplifie([y:=(x+1)-(1+x), z:=(x+1)/(1+x)], [y:=0, z:=1]), simplifie([y:=x+1, z:=1+x], [y:=x+1, z:=y]), simplifie([y:=2, y:=x+y, z:=y], [y:=2, y:=x+2, z:=y]). test_optim:- optim([ldv(0,x), ldv(1,x)], [ldv(0,x), move(1,0)]), optim([stv(y,0), ldv(0,y)], [stv(y,0)]). test_all:- test_optim, test_simplifie, test_get_val_reg, test_compile, test_affecte, test_oublie.