/* Génération de code LMU pour expressions arithmétiques
   voir dans Jour2 le fichier LMU.html
*/

/* 1-  Auxiliaires d'usage général : syntaxe de LMU */

mnem(+, 'ADD'). mnem(-, 'SUB'). mnem(*, 'MUL'). mnem(/, 'DIV').

/* Confection des symboles noms de registres à partir de leurs numéros:  
par exemple     registre(3, R3)     - on rappelle que  82 = ascii('R') */
registre(Num, Nom) :- name(Num, Chn), name(Nom, [82 | Chn]). 	 

/* Confection d'une liste d'instructions LMU avec une liste différentielle */
clmu(Lcode, T-[Inst|Q], T-Q) :- Inst =.. Lcode.

/* Impression d'une liste d'instructions au format LMU.
   Comme la liste est incomplète, la précaution "nonvar(X)" dans plmu
   est utile pour éviter des erreurs au retour arrière */
   
vlmu(Linst-Q) :- maplist(plmu, Linst).
plmu(X) :- nonvar(X), tab(8), X =.. Lcode, slmu(Lcode).
slmu([]) :- nl.
slmu([T | Q]) :- write(T), tab(2), slmu(Q).

/* N.B. : On se borne ici à imprimer le code LMU sur la sortie stantard,
   comme on l'a fait en LISP.
   On pourrait aussi imprimer dans un fichier.
   Le contrôle des entrées-sorties sur fichier 
   s'effectue au moyen des prédicats de redirection de flot "see" et "tell", 
   voir la documentation de votre Prolog favori */

/* 2-  Le générateur de code simpliste avec pile explicite */

genexp0(Exp) --> {number(Exp), !}, clmu(['LDI', 'R0', Exp]).
genexp0(Exp) --> {atomic(Exp), !}, clmu(['LDR', 'R0', Exp]).
genexp0(Exp) --> {functor(Exp, Op, 2), 
				arg(1, Exp, Ag), arg(2, Exp, Ad)},
				genexp0(Ag), clmu(['PSH', 'R0']),
				genexp0(Ad), clmu(['POP', 'R1']),
				{mnem(Op, Codop)}, 
				clmu([Codop, 'R0', 'R1', 'R0']).
/*-----------------------------------------------------
 ?- genexp0(7*3-(5+3-4)).
        LDI  R0  7  
        PSH  R0  
        LDI  R0  3  
        POP  R1  
        MUL  R0  R1  R0  
        PSH  R0  
        LDI  R0  5  
        PSH  R0  
        LDI  R0  3  
        POP  R1  
        ADD  R0  R1  R0  
        PSH  R0  
        LDI  R0  4  
        POP  R1  
        SUB  R0  R1  R0  
        POP  R1  
        SUB  R0  R1  R0  
 
yes
*/
/* 3- Le générateur raisonnable avec pile dans les registres et test de débordement */

maxreg(3). 		/* seule manière de déclarer une constante en Prolog */

genexp1(Exp, PRL) --> {number(Exp), !, registre(PRL, RPRL)}, /* PRL = Premier Registre Libre */
							clmu(['LDI', RPRL, Exp]).
genexp1(Exp, PRL) --> {atomic(Exp), !, registre(PRL, RPRL)}, 
							clmu(['LDR', RPRL, Exp]).
genexp1(Exp, PRL) --> {functor(Exp, Op, 2), 
					arg(1, Exp, Ag), arg(2, Exp, Ad),
					mnem(Op, Codop), registre(PRL, RPRL)},
					genaux1(Codop, Ag, Ad, PRL, RPRL).

/* On introduit un prédicat auxiliaire genaux1 pour avoir une définition en deux clauses, 
  dont la seconde traitera le débordement dans la pile */

genaux1(Codop, Ag, Ad, PRL, RPRL) --> {maxreg(MR), PRL < MR, !,
					PRL1 is PRL+1, registre(PRL1, RPRL1)},
					genexp1(Ag, PRL), genexp1(Ad, PRL1),
					clmu([Codop, RPRL, RPRL, RPRL1]).

genaux1(Codop, Ag, Ad, PRL, RPRL) --> {PRL1 is PRL-1, 
				registre(PRL1, RPRL1)}, clmu(['PSH', RPRL1]),
				genexp1(Ag, PRL1), genexp1(Ad, PRL),
				clmu([Codop, RPRL, RPRL1, RPRL]),
				clmu(['POP', RPRL1]).

/*-----------------------------------------------------
| ?- genexp0(7*3-(5+3-4), 0).
        LDI  R0  7  
        LDI  R1  3  
        MUL  R0  R0  R1  
        LDI  R1  5  
        LDI  R2  3  
        ADD  R1  R1  R2  
        LDI  R2  4  
        SUB  R1  R1  R2  
        SUB  R0  R0  R1  

yes

| ?- genexp1(7*3-(5+3-(1+(2+1))), 0).
        LDI  R0  7  
        LDI  R1  3  
        MUL  R0  R0  R1  
        LDI  R1  5  
        LDI  R2  3  
        ADD  R1  R1  R2  
        LDI  R2  1  
        PSH  R2  
        LDI  R2  2  
        LDI  R3  1  
        ADD  R3  R2  R3  
        POP  R2  
        ADD  R2  R2  R3  
        SUB  R1  R1  R2  
        SUB  R0  R0  R1  

yes 							avec un mouvement de pile ! */

/* 4- Le générateur optimal avec calcul du nombre de registres nécessaires */

/* Les listes de Prolog vont nous permettre de contruire "au vol" 
   une structure arborescente parallèle à l'arbre d'expression 
   et portant en chacun de ses sommets le nombre minimum de registres nécessaires 
   à la séquence de code correspondant au sommet homologue de l'arbre d'expression. 
   Le prédicat nmrn(Exp, Liste) contrôlant cette construction est défini ci-après. 
   Sa définition récursive traduit directement la spécification :
       nmrn(E) = 1 si E est une constante ou une variable
       nmrn(Eg op Ed) = 
       		soit ng = nmrn (Eg), nd = nmrn(Ed)
       		max (ng, nd) si ng <> nd
       		nd+1 si ng = nd.

   On l'utilisera ainsi : */

genopt(Exp, Reg) :- {nmrn(Exp, A)}, genexp2(Exp, A, Reg).

nmrn(Exp, [1]) :- number(Exp), !.
nmrn(Exp, [1]) :- atomic(Exp), !.
nmrn(Exp, [R | [G | D]]) :- functor(Exp, Op, 2), 
				arg(1, Exp, Ag), arg(2, Exp, Ad),
				nmrn(Ag, G), nmrn(Ad, D), resrn(G, D, R).

resrn([NG |_], [ND |_], R) :- NG=ND, !, R is NG+1.
resrn([NG |_], [ND |_], NG ) :- NG>ND, !.
resrn([NG |_], [ND |_], ND) .

/*-----------------------------------------------------
| ?- nmrn(7*3-(5+3-(1+(2+1))), A).

A = [3,[2,[1],1],3,[2,[1],1],2,[1],2,[1],1]  	 vu ? 

yes
-----------------------------------------------------
*/
genexp2(Exp, ARN, PRL) --> {number(Exp), !, registre(PRL, RPRL)}, 
					clmu(['LDI', RPRL, Exp]).
genexp2(Exp, ARN, PRL) --> {atomic(Exp), !, registre(PRL, RPRL)}, 
					clmu(['LDR', RPRL, Exp]).
genexp2(Exp, [_ | [ARG | ARD]], PRL) -->	
		{functor(Exp, Op, 2), arg(1, Exp, Ag), arg(2, Exp, Ad),
		mnem(Op, Codop), registre(PRL, RPRL)},
		genaux2(Codop, Ag, Ad, ARG, ARD, PRL, RPRL).

genaux2(Codop, Ag, Ad, ARG, ARD, PRL, RPRL) --> 
				{maxreg(MR), PRL < MR, !,
				PRL1 is PRL+1, registre(PRL1, RPRL1),
				ARG = [NRG | _], ARD = [NRD | _]},
				genaux21(Codop, Ag, Ad, ARG, ARD, NRG, NRD,
				 				  PRL, RPRL, PRL1, RPRL1).

/* genaux21 : encore un prédicat auxiliaire pour traiter l'alternative */

/* Avant de le définir il faut terminer le paquet de clauses de genaux2, 
   donc traiter le cas de débordement dans lapile, suivant la même méthode que pour genexp1. 
   Cette méthode demande à être raffinée ... */

genaux2(Codop, Ag, Ad, ARG, ARD, PRL, RPRL) --> 
				{PRL1 is PRL-1, registre(PRL1, RPRL1)}, 
				clmu(['PSH', RPRL1]),
				genexp2(Ag, ARG, PRL1), genexp2(Ad, ARD, PRL),
				clmu([Codop, RPRL, RPRL1, RPRL]),
				clmu(['POP', RPRL1]).


/* et voici la définition de genaux21, 
   qui détermine l'ordre d'évaluation des sous-arbres */

genaux21(Codop, Ag, Ad, ARG, ARD, NRG, NRD, 
							PRL, RPRL, PRL1, RPRL1) -->
				{NRG > NRD, !}, 
				genexp2(Ag, ARG, PRL), genexp2(Ad, ARD, PRL1),
				clmu([Codop, RPRL, RPRL, RPRL1]).

genaux21(Codop, Ag, Ad, ARG, ARD, NRG, NRD, 
							PRL, RPRL, PRL1, RPRL1) -->
				genexp2(Ad, ARD, PRL), genexp2(Ag, ARG, PRL1),
				clmu([Codop, RPRL, RPRL1, RPRL]).

/* ---------------------------------------------------

| ?- genopt(b*b-4*(a*c), 0).
        LDR  R0  c  
        LDR  R1  a  
        MUL  R0  R1  R0  
        LDI  R1  4  
        MUL  R0  R1  R0  
        LDR  R1  b  
        LDR  R2  b  
        MUL  R1  R2  R1  
        SUB  R0  R1  R0  

yes
| ?- genexp1(b*b-4*(a*c), 0).
        LDR  R0  b  
        LDR  R1  b  
        MUL  R0  R0  R1  
        LDI  R1  4  
        LDR  R2  a  
        LDR  R3  c  
        MUL  R2  R2  R3  
        MUL  R1  R1  R2  
        SUB  R0  R0  R1  

yes
/* On gagne effectivement un registre... */

| ?- genopt(7*3-(5+3-(1+(2+1))), 0).
        LDI  R0  1  
        LDI  R1  2  
        ADD  R0  R1  R0  
        LDI  R1  1  
        ADD  R0  R1  R0  
        LDI  R1  3  
        LDI  R2  5  
        ADD  R1  R2  R1  
        SUB  R0  R1  R0  
        LDI  R1  3  
        LDI  R2  7  
        MUL  R1  R2  R1  
        SUB  R0  R1  R0  

X =  

yes */						/* sans mouvement de pile ! */

/* Essais comparatifs sur une expression spécialement conçue à cet effet */
/*

| ?- genexp1((1-(2+3))*(1-(2+3))/((1-(2+3))*(1-(2+3)))+(1-(2+3))*(1-(2+3))/((1-(2+3))*(1-(2+3))), 0).
        LDI  R0  1  
        LDI  R1  2  
        LDI  R2  3  
        ADD  R1  R1  R2  
        SUB  R0  R0  R1  
        LDI  R1  1  
        LDI  R2  2  
        LDI  R3  3  
        ADD  R2  R2  R3  
        SUB  R1  R1  R2  
        MUL  R0  R0  R1  
        LDI  R1  1  
        LDI  R2  2  
        LDI  R3  3  
        ADD  R2  R2  R3  
        SUB  R1  R1  R2  
        LDI  R2  1  
       PSH  R2  
        LDI  R2  2  
        LDI  R3  3  
        ADD  R3  R2  R3  
       POP  R2  
        SUB  R2  R2  R3  
        MUL  R1  R1  R2  
        DIV  R0  R0  R1  
        LDI  R1  1  
        LDI  R2  2  
        LDI  R3  3  
        ADD  R2  R2  R3  
        SUB  R1  R1  R2  
        LDI  R2  1  
        PSH  R2  
        LDI  R2  2  
        LDI  R3  3  
        ADD  R3  R2  R3  
        POP  R2  
        SUB  R2  R2  R3  
        MUL  R1  R1  R2  
        LDI  R2  1  
        PSH  R2  
        LDI  R2  2  
        LDI  R3  3  
        ADD  R3  R2  R3  
        POP  R2  
        SUB  R2  R2  R3  
        PSH  R2 	  <--- 
        LDI  R2  1  
        PSH  R2  
        LDI  R2  2  
        LDI  R3  3  
        ADD  R3  R2  R3  
        POP  R2  
        SUB  R3  R2  R3  
        POP  R2  	  <--- 
        MUL  R2  R2  R3  
        DIV  R1  R1  R2  
        ADD  R0  R0  R1  

X =  

yes


5 mouvements de pile, 10 intructions "inutiles".

| ?- genopt((1-(2+3))*(1-(2+3))/((1-(2+3))*(1-(2+3)))+(1-(2+3))*(1-(2+3))/((1-(2+3))*(1-(2+3))), 0).
        LDI  R0  3  
        LDI  R1  2  
        ADD  R0  R1  R0  
        LDI  R1  1  
        SUB  R0  R1  R0  
        LDI  R1  3  
        LDI  R2  2  
        ADD  R1  R2  R1  
        LDI  R2  1  
        SUB  R1  R2  R1  
        MUL  R0  R1  R0  
        LDI  R1  3  
        LDI  R2  2  
        ADD  R1  R2  R1  
        LDI  R2  1  
        SUB  R1  R2  R1  
        LDI  R2  3  
        LDI  R3  2  
        ADD  R2  R3  R2  
        LDI  R3  1  
        SUB  R2  R3  R2  
        MUL  R1  R2  R1  
        DIV  R0  R1  R0  
        LDI  R1  3  
        LDI  R2  2  
        ADD  R1  R2  R1  
        LDI  R2  1  
        SUB  R1  R2  R1  
        LDI  R2  3  
        LDI  R3  2  
        ADD  R2  R3  R2  
        LDI  R3  1  
        SUB  R2  R3  R2  
        MUL  R1  R2  R1  
        LDI  R2  3  
        LDI  R3  2  
        ADD  R2  R3  R2  
        LDI  R3  1  
        SUB  R2  R3  R2  
        PSH  R2  		<--- 
        LDI  R2  1  
        PSH  R2  
        LDI  R2  2  
        LDI  R3  3  
        ADD  R3  R2  R3  
        POP  R2  
        SUB  R3  R2  R3  
        POP  R2  		<--- 
        MUL  R2  R3  R2  
        DIV  R1  R2  R1  
        ADD  R0  R1  R0  

X = (1-(2+3))*(1-(2+3))/((1-(2+3))*(1-(2+3)))+(1-(2+3))*(1-(2+3))/((1-(2+3))*(1-(2+3))) 

yes
| ?- 


On constate un gain de 6 instructions, 2 mouvements de pile contre 5 avec genexp1. 
*/
try0(E) :- genexp0(E, X-X, Y), vlmu(Y).
try1(E) :- genexp1(E, 0, X-X, Y), vlmu(Y).
try2(E) :- genopt(E, 0, X-X, Y), vlmu(Y).
