Attribute grammar for generating MacScheme machine assembly code from a quirk21a program. [Revision 3] Revision history: Revision 3, 5 November 2004: Fixed four errors in code for tail calls (marked by !! in column 78). Revision 2, 1 November 2004: Added a missing save instruction. Repaired horrendous bug in register allocation for tail calls. Fixed the operation for gt_int and ge_int. Corrected many typos, marked by an exclamation mark (!) in column 79. Revision 1, 28 October 2004: Repaired mistakes that were noticed during lecture. The attribute grammar is defined over abstract syntax trees that have been type checked and attributed. Syntactic categories (nonterminals of the attribute grammar). P program M module D module-level declaration F lambda expression E expression L literal expression B binary operation U unary operation Attributes. F.free precomputed (see assignment #4) ! E.dleaf precomputed (see assignment #4; also note [1] below) ! E.free precomputed (see assignment #4) ! E.n1 precomputed (see assignment #3) ! P.code synthesized M.code synthesized D.maxstk synthesized D.code synthesized F.env inherited F.code synthesized E.env inherited E.stkenv inherited E.regenv inherited E.reg inherited E.stk inherited E.tail inherited E.maxstk synthesized E.code synthesized L.code synthesized B.reg inherited B.code synthesized U.reg inherited U.code synthesized Notes. ! [1] Assignment #4 should be repaired by storing E0.dleaf in the ! lambda expression E instead of storing it in the body E0. If E0 ! is a FieldExp, then E0.n1 is the offset of the field, which we ! would lose if it were overwritten by E0.dleaf. Since E0 cannot ! be a FieldExp in the quirk21a subset, this repair can be postponed ! to a future assignment, but that postponement means that F.dleaf ! will be found in the body of F rather than in F itself. ! Notation. If env is a compile-time environment, then env [I1: n1] abbreviates extend (env, I1, n1). More generally, env [I1: n1, ...] abbreviates extend (env, I1, n1) [...]. reference(I1, env, stkenv, regenv) stands for the one of the following sequences of MacScheme machine assembly code. If lookup (regenv, I1) = j, then reference(I1, env, stkenv, regenv) is reg j If lookup (stkenv, I1) = j, then reference(I1, env, stkenv, regenv) is stack j If lookup (env, I1) = j, then reference(I1, env, stkenv, regenv) is lexical 0,j Otherwise reference(I1, env, stkenv, regenv) is global I1 returnif(false, k) stands for the empty sequence of MacScheme machine assembly code. If k < 0, then returnif(true, k) stands for return If k >= 0, then returnif(true, k) stands for popstk return P --> E where M1 ... Mk E.env = E.stkenv = E.regenv = empty(); E.reg = E.stk = 0; E.tail = false; P.code = [M1.code] ... [Mk.code] save [E.maxstk] store 0,0 ! [E.code] pop [E.maxstk] return M --> export I1 ... Im from D1 ... Dn where E1 ... Ek E1.env = ... = Ek.env = empty(); E1.stkenv = ... = Ek.stkenv = empty(); E1.regenv = ... = Ek.regenv = empty(); E1.reg = ... = Ek.reg = 0; E1.stk = ... = Ek.stk = 0; E1.tail = ... = Ek.tail = false; let jmax = max (D1.maxstk, ..., Dn.maxstk, E1.maxstk, ..., Ek.maxstk) in M.code = save jmax save 0,0 [D1.code] ... [Dn.code] [E1.code] ... [Ek.code] pop jmax D --> variables I1 = E1 ... Im = Em E1.env = ... = Em.env = empty(); E1.stkenv = ... = Em.stkenv = empty(); E1.regenv = ... = Em.regenv = empty(); E1.reg = ... = Em.reg = 0; E1.stk = ... = Em.stk = 0; E1.tail = ... = Em.tail = false; D.maxstk = max (E1.maxstk, ..., Em.maxstk) D.code = [E1.code] ! setglbl I1 ... [Em.code] ! setglbl Im D --> functions I1 = F1 ... Im = Fm F1.env = ... = Fm.env = empty(); D.code = lambda [F1.code],0,#f setglbl I1 ... lambda [Fm.code],0,#f ! setglbl Im D --> types I1 = T1 ... Im = Tm (Not in quirk21a) F --> lambda (I1 : T1, ..., Im : Tm) : T0 . E0 if F.dleaf then E0.env = F.env; E0.stkenv = empty(); E0.regenv = empty() [I1: 1, ..., Im: m]; E0.reg = m; E0.stk = -1; E0.tail = true; F.code = E0.code. else E0.env = F.env; E0.stkenv = empty() [I1: 1, ..., Im: m]; E0.regenv = empty(); E0.reg = 0; E0.stk = m; E0.tail = true; F.code = save [E0.maxstk] ! store 0,0 store 1,1 ... store m,m [E0.code] E --> F let {I1, ..., Im} = F.free in if E.stk < 0 then F.env = empty() [I1: 1, ..., Im: m] E.maxstk = E.stk; E.code = save [E.reg] store 0,0 ... store [E.reg],[E.reg] reference(I1, E.env, E.stkenv, E.regenv) setreg 1 ... reference(Im, E.env, E.stkenv, E.regenv) setreg m lambda [F.code],m,#f load 0,0 ... load [E.reg],[E.reg] pop [E.reg] returnif(E.tail, E.stk) else F.env = empty() [I1: 1, ..., Im: m] E.maxstk = E.reg + E.stk; E.code = store 1,[E.stk+1] ... store [E.reg],[E.stk+E.reg] reference(I1, E.env, E.stkenv, E.regenv) setreg 1 ... reference(Im, E.env, E.stkenv, E.regenv) setreg m lambda [F.code],m,#f load 1,[E.stk+1] ... load [E.reg],[E.stk+E.reg] returnif(E.tail, E.stk) E --> let I1 = E1 ... Im = Em in E0 if E.stk < 0 then E1.env = ... = Em.env = E0.env = E.env; E1.stkenv = ... = Em.stkenv = E0.stkenv = E.stkenv; E1.regenv = E.regenv; E2.regenv = E1.regenv [I1 : E2.reg] ... Em.regenv = E{m-1}.regenv [I{m-1}: Em.reg] E0.regenv = Em.regenv [Im: E0.reg] E1.reg = E.reg; E2.reg = E1.reg + 1; ... Em.reg = E{m-1}.reg + 1; E0.reg = Em.reg + 1; E1.stk = ... = Em.stk = E0.stk = E.stk; E1.tail = ... = Em.tail = false; E0.tail = E.tail; E.maxstk = max (E1.maxstk, ..., Em.maxstk, E0.maxstk); E.code = [E1.code] setreg E1.reg+1 ... [Em.code] setreg Em.reg+1 [E0.code] else E1.env = ... = Em.env = E0.env = E.env; E1.stkenv = E.stkenv; E2.stkenv = E1.stkenv [I1: E2.stk]; ... Em.stkenv = E{m-1}.stkenv [I{m-1}: Em.stk]; E0.stkenv = Em.stkenv [Im: E0.stk]; E1.regenv = ... = Em.regenv = E0.regenv = E.regenv; E1.reg = ... = Em.reg = E0.reg = E.reg; E1.stk = E.stk; E2.stk = E1.stk + 1; ... Em.stk = E{m-1}.stk + 1; E0.stk = Em.stk + 1; E1.tail = ... = Em.tail = false; E0.tail = E.tail; E.maxstk = max (E1.maxstk, ..., Em.maxstk, ! E0.maxstk); ! E.code = [E1.code] setstk E1.stk+1 ... [Em.code] setstk Em.stk+1 [E0.code] E --> letrec I1 = F1 ... Im = Fm in E0 (not in quirk21a) E --> new I0 [ E0 ] E1 (not in quirk21a) E --> new I0 { N1 = E1 ... Nm = Em } (not in quirk21a) E --> case E0 of N1 : I1 then E1 ... Nm : Im then Em else Em+1 (not in quirk21a) E --> if E0 then E1 else E2 E0.env = E1.env = E2.env = E.env; E0.stkenv = E1.stkenv = E2.stkenv = E.stkenv; E0.regenv = E1.regenv = E2.regenv = E.regenv; E0.reg = E1.reg = E2.reg = E.reg; E0.stk = E1.stk = E2.stk = E.stk; E0.tail = false; E1.tail = E2.tail = E.tail; E.maxstk = max (E0.maxstk, E1.maxstk, E2.maxstk); let L1 = newlabel() L2 = newlabel() E.code = [E0.code] branchf L1 [E1.code] skip L2 L1: [E2.code] L2: E --> begin E1; ...; Ek end E1.env = ... = Ek.env = E.env; E1.stkenv = ... = Ek.stkenv = E.stkenv; E1.regenv = ... = Ek.regenv = E.regenv; E1.reg = ... = Ek.reg = E.reg; E1.stk = ... = Ek.stk = E.stk; E1.tail = ... = E{k-1}.tail = false; Ek.tail = E.tail; E.maxstk = max (E1.maxstk, ..., Ek.maxstk); E.code = [E1.code] ... [Ek.code] E --> E1 B E2 E1.env = E2.env = E.env; E1.stkenv = E2.stkenv = E.stkenv; E1.regenv = E2.regenv = E.regenv; E1.reg = E.reg; E2.reg = B.reg = E.reg + 1; E1.stk = E2.stk = E.stk; E1.tail = E2.tail = false; E.maxstk = max (E1.maxstk, E2.maxstk); E.code = [E1.code] setreg [E.reg+1] [E2.code] [B.code] returnif(E.tail, E.stk) E --> U E1 E1.env = E.env; E1.stkenv = E.stkenv; E1.regenv = E.regenv; E1.reg = U.reg = E.reg; E1.stk = E.stk; E1.tail = false; E.maxstk = E1.maxstk; E.code = [E1.code] [U.code] returnif(E.tail, E.stk) E --> L E.maxstk = E.stk; E.code = const L returnif(E.tail, E.stk) E --> I1 E.maxstk = E.stk; E.code = reference(I1, E.env, E.stkenv, E.regenv) returnif(E.tail, E.stk) E --> E0 (E1, ..., Em) if E.tail and E.stk < 0 then E0.env = E1.env = ... = Em.env = E.env; E0.stkenv = E1.stkenv = ... = Em.stkenv = E.stkenv; E0.regenv = E1.regenv = ... = Em.regenv = E.regenv; E0.reg = E.reg; ! E1.reg = E.reg + 1; ! ... ! Em.reg = E.reg + m; ! E0.stk = E1.stk = ... = Em.stk = E.stk; E0.tail = E1.tail = ... = Em.tail = false; E.maxstk = max (E0.maxstk, E1.maxstk, ..., Em.maxstk); E.code = [E0.code] setreg [E0.reg + 1] ! [E1.code] setreg [E1.reg + 1] ! ... [Em.code] setreg [Em.reg + 1] !! reg [E0.reg + 1] ! movereg [E1.reg + 1],1 ! ... ! movereg [Em.reg + 1],m !! invoke m else if E.tail and E.stk >= 0 then E0.env = E1.env = ... = Em.env = E.env; E0.stkenv = E1.stkenv = ... = Em.stkenv = E.stkenv; E0.regenv = E1.regenv = ... = Em.regenv = E.regenv; E0.reg = E.reg; ! E1.reg = E.reg + 1; ! ... ! Em.reg = E.reg + m; ! E0.stk = E1.stk = ... = Em.stk = E.stk; E0.tail = E1.tail = ... = Em.tail = false; E.maxstk = max (E0.maxstk, E1.maxstk, ..., Em.maxstk); E.code = [E0.code] setreg [E0.reg + 1] ! [E1.code] setreg [E1.reg + 1] ! ... [Em.code] setreg [Em.reg + 1] !! reg [E0.reg + 1] ! movereg [E1.reg + 1],1 ! ... ! movereg [Em.reg + 1],m !! popstk invoke m else E0.env = E1.env = ... = Em.env = E.env; E0.stkenv = E1.stkenv = ... = Em.stkenv = E.stkenv; E0.regenv = E1.regenv = ... = Em.regenv = E.regenv; E0.reg = E1.reg = ... = Em.reg = m + 1; E0.stk = E1.stk = ... = Em.stk = E.stk + E.reg + 1; E0.tail = E1.tail = ... = Em.tail = false; E.maxstk = max (E0.maxstk, E1.maxstk, ..., Em.maxstk); let L = newlabel() in E.code = store 1,[E.stk+1] ... store [E.reg],[E.stk+E.reg] store 0,[E.stk+E.reg+1] [E0.code] setreg m+1 [E1.code] setreg 1 ... [Em.code] setreg m reg m+1 setrtn L invoke m L: load 0,[E.stk+E.reg+1] load 1,[E.stk+1] ... load [E.reg],[E.stk+E.reg] E --> E1 . N1 (not in quirk21a) E --> E1 [ E2 ] (not in quirk21a) B --> assign (not in quirk21a) B --> eq_bool B.code = op2 eq?,[B.reg] B --> ne_bool B.code = op2 eq?,[B.reg] op1 not B --> eq_char (not in quirk21a) B --> ne_char (not in quirk21a) B --> eq_int B.code = op2 =:fix:fix,[B.reg] B --> lt_int B.code = op2 >:fix:fix,[B.reg] B --> gt_int B.code = op2 <:fix:fix,[B.reg] ! B --> ne_int B.code = op2 =:fix:fix,[B.reg] op1 not B --> le_int B.code = op2 >=:fix:fix,[B.reg] B --> ge_int B.code = op2 <=:fix:fix,[B.reg] ! B --> eq_float (not in quirk21a) B --> lt_float (not in quirk21a) B --> gt_float (not in quirk21a) B --> ne_float (not in quirk21a) B --> le_float (not in quirk21a) B --> ge_float (not in quirk21a) B --> plus_int B.code = op2 +:idx:idx,[B.reg] B --> minus_int B.code = op2 r-:idx:idx,[B.reg] B --> times_int B.code = op2 q*,[B.reg] ! B --> divide_int B.code = setglbl auxiliary_register2 reg [B.reg] setglbl auxiliary_register1 global auxiliary_register2 setreg [B.reg] global auxiliary_register1 op2 quotient,[B.reg] B --> plus_float (not in quirk21a) B --> minus_float (not in quirk21a) B --> times_float (not in quirk21a) B --> divide_float (not in quirk21a) U --> not U.code = op1 not U --> length (not in quirk21a) U --> coerce_int_to_float (not in quirk21a)