54 |
54 |
55 |
55 |
56 |
56 |
57 // Abstract syntax trees for the Fun language |
57 // Abstract syntax trees for the Fun language |
58 abstract class KExp |
58 abstract class KExp |
59 |
59 abstract class KVal |
60 case class KVar(s: String) extends KExp |
60 |
61 case class KNum(i: Int) extends KExp |
61 case class KVar(s: String) extends KVal |
62 case class KAop(o: String, x1: String, x2: String) extends KExp |
62 case class KNum(i: Int) extends KVal |
63 case class KIfeq(x1: String, x2: String, e1: KExp, e2: KExp) extends KExp { |
63 case class KAop(o: String, v1: KVal, v2: KVal) extends KVal |
64 override def toString = s"KIf $x1 == $x2 \nIF\n$e1\nELSE\n$e2" |
64 case class KBop(o: String, v1: KVal, v2: KVal) extends KVal |
65 |
65 case class KCall(o: String, vrs: List[KVal]) extends KVal |
66 } |
66 |
67 case class KCall(o: String, vrs: List[String]) extends KExp |
67 case class KIf(x1: String, e1: KExp, e2: KExp) extends KExp { |
68 case class KLet(x: String, e1: KExp, e2: KExp) extends KExp { |
68 override def toString = s"KIf $x1\nIF\n$e1\nELSE\n$e2" |
|
69 } |
|
70 case class KLet(x: String, e1: KVal, e2: KExp) extends KExp { |
69 override def toString = s"let $x = $e1 in \n$e2" |
71 override def toString = s"let $x = $e1 in \n$e2" |
70 } |
72 } |
71 |
73 case class KReturn(v: KVal) extends KExp |
72 def K(e: Exp) : KExp = e match { |
74 |
73 case Var(s) => KVar(s) |
75 def CPS(e: Exp)(k: KVal => KExp) : KExp = e match { |
74 case Num(i) => KNum(i) |
76 case Var(s) => k(KVar(s)) |
75 case Aop(o, a1, a2) => { |
77 case Num(i) => k(KNum(i)) |
76 val x1 = Fresh("tmp") |
78 case Aop(o, e1, e2) => { |
77 val x2 = Fresh("tmp") |
79 val z = Fresh("tmp") |
78 KLet(x1, K(a1), KLet(x2, K(a2), KAop(o, x1, x2))) |
80 CPS(e1)(y1 => |
79 } |
81 CPS(e2)(y2 => KLet(z, KAop(o, y1, y2), k(KVar(z))))) |
80 case Call(name: String, args: List[Exp]) => { |
82 } |
81 val args_new = args.map{a => (Fresh("tmp"), K(a))} |
83 case If(Bop(o, b1, b2), e1, e2) => { |
82 def aux(as: List[(String, KExp)]) : KExp = as match { |
84 val z = Fresh("tmp") |
83 case Nil => KCall(name, args_new.map(_._1)) |
85 CPS(b1)(y1 => |
84 case (x, a)::rest => KLet(x, a, aux(rest)) |
86 CPS(b2)(y2 => KLet(z, KBop(o, y1, y2), KIf(z, CPS(e1)(k), CPS(e2)(k))))) |
|
87 } |
|
88 case Call(name, args) => { |
|
89 def aux(args: List[Exp], vs: List[KVal]) : KExp = args match { |
|
90 case Nil => { |
|
91 val z = Fresh("tmp") |
|
92 KLet(z, KCall(name, vs), k(KVar(z))) |
|
93 } |
|
94 case e::es => CPS(e)(y => aux(es, vs ::: List(y))) |
85 } |
95 } |
86 aux(args_new) |
96 aux(args, Nil) |
87 } |
97 } |
88 case If(Bop("==", b1, b2), e1, e2) => { |
98 case Sequence(e1, e2) => { |
89 val x1 = Fresh("tmp") |
99 val z = Fresh("tmp") |
90 val x2 = Fresh("tmp") |
100 CPS(e1)(y1 => |
91 KLet(x1, K(b1), KLet(x2, K(b2), KIfeq(x1, x2, K(e1), K(e2)))) |
101 CPS(e2)(y2 => KLet("_", y1, KLet(z, y2, k(KVar(z)))))) |
92 } |
102 } |
93 } |
103 } |
94 |
104 |
95 def Denest(e: KExp) : KExp = e match { |
105 def CPSi(e: Exp) = CPS(e)(KReturn) |
96 case KLet(xt, e1, e2) => { |
106 |
97 def insert(e: KExp) : KExp = e match { |
107 val e1 = Aop("*", Var("a"), Num(3)) |
98 case KLet(yt, e3, e4) => KLet(yt, e3, insert(e4)) |
108 CPS(e1)(KReturn) |
99 case e => KLet(xt, e, Denest(e2)) |
109 |
100 } |
110 val e2 = Aop("+", Aop("*", Var("a"), Num(3)), Num(4)) |
101 insert(Denest(e1)) |
111 CPS(e2)(KReturn) |
102 } |
112 |
103 case KIfeq(x1, x2, e1, e2) => KIfeq(x1, x2, Denest(e1), Denest(e2)) |
113 val e3 = Aop("+", Num(2), Aop("*", Var("a"), Num(3))) |
104 case _ => e |
114 CPS(e3)(KReturn) |
105 } |
115 |
106 |
116 val e4 = Aop("+", Aop("-", Num(1), Num(2)), Aop("*", Var("a"), Num(3))) |
|
117 CPS(e4)(KReturn) |
|
118 |
|
119 val e5 = If(Bop("==", Num(1), Num(1)), Num(3), Num(4)) |
|
120 CPS(e5)(KReturn) |
|
121 |
|
122 val e6 = If(Bop("!=", Num(10), Num(10)), e5, Num(40)) |
|
123 CPS(e6)(KReturn) |
|
124 |
|
125 val e7 = Call("foo", List(Num(3))) |
|
126 CPS(e7)(KReturn) |
|
127 |
|
128 val e8 = Call("foo", List(Num(3), Num(4), Aop("+", Num(5), Num(6)))) |
|
129 CPS(e8)(KReturn) |
|
130 |
|
131 val e9 = Sequence(Aop("*", Var("a"), Num(3)), Aop("+", Var("b"), Num(6))) |
|
132 CPS(e9)(KReturn) |
107 |
133 |
108 val e = Aop("*", Aop("+", Num(1), Call("foo", List(Var("a"), Num(3)))), Num(4)) |
134 val e = Aop("*", Aop("+", Num(1), Call("foo", List(Var("a"), Num(3)))), Num(4)) |
109 println(K(e)) |
135 CPS(e)(KReturn) |
110 println() |
136 |
111 println(Denest(K(e))) |
|
112 println() |
|
113 |
137 |
114 |
138 |
115 |
139 |
116 // convenient string interpolations |
140 // convenient string interpolations |
117 // for instructions, labels and methods |
141 // for instructions, labels and methods |
122 def i(args: Any*): String = " " ++ sc.s(args:_*) ++ "\n" |
146 def i(args: Any*): String = " " ++ sc.s(args:_*) ++ "\n" |
123 def l(args: Any*): String = sc.s(args:_*) ++ ":\n" |
147 def l(args: Any*): String = sc.s(args:_*) ++ ":\n" |
124 def m(args: Any*): String = sc.s(args:_*) ++ "\n" |
148 def m(args: Any*): String = sc.s(args:_*) ++ "\n" |
125 } |
149 } |
126 |
150 |
127 |
151 def compile_op(op: String) = op match { |
128 type Env = Map[String, Int] |
152 case "+" => "add i32 " |
129 |
153 case "*" => "mul i32 " |
130 |
154 case "-" => "sub i32 " |
|
155 case "==" => "icmp eq i32 " |
|
156 } |
|
157 |
|
158 def compile_val(v: KVal) : String = v match { |
|
159 case KNum(i) => s"$i" |
|
160 case KVar(s) => s"%$s" |
|
161 case KAop(op, x1, x2) => |
|
162 s"${compile_op(op)} ${compile_val(x1)}, ${compile_val(x2)}" |
|
163 case KBop(op, x1, x2) => |
|
164 s"${compile_op(op)} ${compile_val(x1)}, ${compile_val(x2)}" |
|
165 case KCall(x1, args) => |
|
166 s"call i32 @$x1 (${args.map(compile_val).mkString("i32 ", ", i32 ", "")})" |
|
167 } |
131 |
168 |
132 // compile K expressions |
169 // compile K expressions |
133 def compile_exp(a: KExp) : String = a match { |
170 def compile_exp(a: KExp) : String = a match { |
134 case KNum(i) => s"?$i?" |
171 case KReturn(v) => |
135 case KVar(s) => s"?$s?" |
172 i"ret i32 ${compile_val(v)}" |
136 case KAop("+", x1, x2) => s"add i32 %$x1, i32 %$x2" |
173 case KLet(x: String, v: KVal, e: KExp) => |
137 case KAop("-", x1, x2) => s"sub i32 %$x1, i32 %$x2" |
174 i"%$x = ${compile_val(v)}" ++ compile_exp(e) |
138 case KAop("*", x1, x2) => s"mul i32 %$x1, i32 %$x2" |
175 case KIf(x, e1, e2) => { |
139 case KLet(x: String, e1: KExp, e2: KExp) => { |
|
140 val is1 = compile_exp(e1) |
|
141 val is2 = compile_exp(e2) |
|
142 i"%$x = $is1" ++ is2 |
|
143 } |
|
144 case KLet(x: String, e1: KExp, e2: KExp) => { |
|
145 val is1 = compile_exp(e1) |
|
146 val is2 = compile_exp(e2) |
|
147 i"%$x = $is1" ++ is2 |
|
148 } |
|
149 case KIfeq(x1, x2, a1, a2) => { |
|
150 val if_br = Fresh("if_br") |
176 val if_br = Fresh("if_br") |
151 val else_br = Fresh("else_br") |
177 val else_br = Fresh("else_br") |
152 val x = Fresh("tmp") |
|
153 i"%$x = icmp eq i32 %$x1, i32 %$x2" ++ |
|
154 i"br i1 %$x, label %$if_br, label %$else_br" ++ |
178 i"br i1 %$x, label %$if_br, label %$else_br" ++ |
155 l"\n$if_br" ++ |
179 l"\n$if_br" ++ |
156 compile_exp(a1) ++ |
180 compile_exp(e1) ++ |
157 l"\n$else_br" ++ |
181 l"\n$else_br" ++ |
158 compile_exp(a2) |
182 compile_exp(e2) |
159 } |
183 } |
160 case KCall(x1, args) => { |
184 } |
161 s"Call $x1 ($args)" |
185 |
162 } |
186 /* case Write(a1) => { |
163 /* |
|
164 case Call(name, args) => { |
|
165 val is = "I" * args.length |
|
166 args.map(a => compile_exp(a, env)).mkString ++ |
|
167 i"invokestatic XXX/XXX/$name($is)I" |
|
168 } |
|
169 case Sequence(a1, a2) => { |
|
170 compile_exp(a1, env) ++ i"pop" ++ compile_exp(a2, env) |
|
171 } |
|
172 case Write(a1) => { |
|
173 compile_exp(a1, env) ++ |
187 compile_exp(a1, env) ++ |
174 i"dup" ++ |
188 i"dup" ++ |
175 i"invokestatic XXX/XXX/write(I)V" |
189 i"invokestatic XXX/XXX/write(I)V" |
176 } |
190 } |
177 */ |
|
178 } |
|
179 |
|
180 /* |
|
181 // compile boolean expressions |
|
182 def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match { |
|
183 case Bop("==", a1, a2) => |
|
184 compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpne $jmp" |
|
185 case Bop("!=", a1, a2) => |
|
186 compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpeq $jmp" |
|
187 case Bop("<", a1, a2) => |
|
188 compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpge $jmp" |
|
189 case Bop("<=", a1, a2) => |
|
190 compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpgt $jmp" |
|
191 } |
|
192 */ |
191 */ |
|
192 |
|
193 |
193 |
194 |
194 // compile function for declarations and main |
195 // compile function for declarations and main |
195 def compile_decl(d: Decl) : String = d match { |
196 def compile_decl(d: Decl) : String = d match { |
196 case Def(name, args, body) => { |
197 case Def(name, args, body) => { |
197 println(s"DEF\n $name ($args) = \nBODY:") |
198 //println(s"DEF\n $name ($args) = \nBODY:") |
198 println(Denest(K(body))) |
199 //println(CPSi(body)) |
199 println() |
200 //println() |
200 counter = -1 |
201 //counter = -1 |
201 m"define i32 @$name (${args.mkString("i32 %", ", i32 %", "")}) {" ++ |
202 m"define i32 @$name (${args.mkString("i32 %", ", i32 %", "")}) {" ++ |
202 compile_exp(Denest(K(body))) ++ |
203 compile_exp(CPSi(body)) ++ |
203 m"}\n" |
204 m"}\n" |
204 } |
205 } |
205 case Main(body) => { |
206 case Main(body) => { |
206 m"define i32 @main() {" ++ |
207 m"define i32 @main() {" ++ |
207 compile_exp(Denest(K(body))) ++ |
208 compile_exp(CPSi(body)) ++ |
208 i"ret i32 0" ++ |
|
209 m"}\n" |
209 m"}\n" |
210 } |
210 } |
211 } |
211 } |
212 |
212 |
213 // main compiler functions |
213 // main compiler functions |